tools/opt/Passes.cpp

   1 //===- Passes.cpp - Parsing, selection, and running of passes -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 ///
  11 /// This file provides the infrastructure to parse and build a custom pass
  12 /// manager based on a commandline flag. It also provides helpers to aid in
  13 /// analyzing, debugging, and testing pass structures.
  14 ///
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "Passes.h"
  18 #include "llvm/Analysis/AssumptionCache.h"
  19 #include "llvm/Analysis/CGSCCPassManager.h"
  20 #include "llvm/Analysis/LazyCallGraph.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/Analysis/TargetLibraryInfo.h"
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/IR/IRPrintingPasses.h"
  25 #include "llvm/IR/PassManager.h"
  26 #include "llvm/IR/Verifier.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Transforms/InstCombine/InstCombine.h"
  29 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
  30
  31 using namespace llvm;
  32
  33 namespace {
  34
  35 /// \brief No-op module pass which does nothing.
  36 struct NoOpModulePass {
  37   PreservedAnalyses run(Module &M) { return PreservedAnalyses::all(); }
  38   static StringRef name() { return "NoOpModulePass"; }
  39 };
  40
  41 /// \brief No-op module analysis.
  42 struct NoOpModuleAnalysis {
  43   struct Result {};
  44   Result run(Module &) { return Result(); }
  45   static StringRef name() { return "NoOpModuleAnalysis"; }
  46   static void *ID() { return (void *)&PassID; }
  47 private:
  48   static char PassID;
  49 };
  50
  51 char NoOpModuleAnalysis::PassID;
  52
  53 /// \brief No-op CGSCC pass which does nothing.
  54 struct NoOpCGSCCPass {
  55   PreservedAnalyses run(LazyCallGraph::SCC &C) {
  56     return PreservedAnalyses::all();
  57   }
  58   static StringRef name() { return "NoOpCGSCCPass"; }
  59 };
  60
  61 /// \brief No-op CGSCC analysis.
  62 struct NoOpCGSCCAnalysis {
  63   struct Result {};
  64   Result run(LazyCallGraph::SCC &) { return Result(); }
  65   static StringRef name() { return "NoOpCGSCCAnalysis"; }
  66   static void *ID() { return (void *)&PassID; }
  67 private:
  68   static char PassID;
  69 };
  70
  71 char NoOpCGSCCAnalysis::PassID;
  72
  73 /// \brief No-op function pass which does nothing.
  74 struct NoOpFunctionPass {
  75   PreservedAnalyses run(Function &F) { return PreservedAnalyses::all(); }
  76   static StringRef name() { return "NoOpFunctionPass"; }
  77 };
  78
  79 /// \brief No-op function analysis.
  80 struct NoOpFunctionAnalysis {
  81   struct Result {};
  82   Result run(Function &) { return Result(); }
  83   static StringRef name() { return "NoOpFunctionAnalysis"; }
  84   static void *ID() { return (void *)&PassID; }
  85 private:
  86   static char PassID;
  87 };
  88
  89 char NoOpFunctionAnalysis::PassID;
  90
  91 } // End anonymous namespace.
  92
  93 void Passes::registerModuleAnalyses(ModuleAnalysisManager &MAM) {
  94 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \
  95   MAM.registerPass(CREATE_PASS);
  96 #include "PassRegistry.def"
  97 }
  98
  99 void Passes::registerCGSCCAnalyses(CGSCCAnalysisManager &CGAM) {
 100 #define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
 101   CGAM.registerPass(CREATE_PASS);
 102 #include "PassRegistry.def"
 103 }
 104
 105 void Passes::registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
 106 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
 107   FAM.registerPass(CREATE_PASS);
 108 #include "PassRegistry.def"
 109 }
 110
 111 #ifndef NDEBUG
 112 static bool isModulePassName(StringRef Name) {
 113 #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
 114 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
 115   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
 116     return true;
 117 #include "PassRegistry.def"
 118
 119   return false;
 120 }
 121 #endif
 122
 123 static bool isCGSCCPassName(StringRef Name) {
 124 #define CGSCC_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
 125 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
 126   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
 127     return true;
 128 #include "PassRegistry.def"
 129
 130   return false;
 131 }
 132
 133 static bool isFunctionPassName(StringRef Name) {
 134 #define FUNCTION_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
 135 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
 136   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
 137     return true;
 138 #include "PassRegistry.def"
 139
 140   return false;
 141 }
 142
 143 bool Passes::parseModulePassName(ModulePassManager &MPM, StringRef Name) {
 144 #define MODULE_PASS(NAME, CREATE_PASS)                                         \
 145   if (Name == NAME) {                                                          \
 146     MPM.addPass(CREATE_PASS);                                                  \
 147     return true;                                                               \
 148   }
 149 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
 150   if (Name == "require<" NAME ">") {                                           \
 151     MPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                 \
 152     return true;                                                               \
 153   }                                                                            \
 154   if (Name == "invalidate<" NAME ">") {                                        \
 155     MPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());              \
 156     return true;                                                               \
 157   }
 158 #include "PassRegistry.def"
 159
 160   return false;
 161 }
 162
 163 bool Passes::parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name) {
 164 #define CGSCC_PASS(NAME, CREATE_PASS)                                          \
 165   if (Name == NAME) {                                                          \
 166     CGPM.addPass(CREATE_PASS);                                                 \
 167     return true;                                                               \
 168   }
 169 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
 170   if (Name == "require<" NAME ">") {                                           \
 171     CGPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                \
 172     return true;                                                               \
 173   }                                                                            \
 174   if (Name == "invalidate<" NAME ">") {                                        \
 175     CGPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());             \
 176     return true;                                                               \
 177   }
 178 #include "PassRegistry.def"
 179
 180   return false;
 181 }
 182
 183 bool Passes::parseFunctionPassName(FunctionPassManager &FPM, StringRef Name) {
 184 #define FUNCTION_PASS(NAME, CREATE_PASS)                                       \
 185   if (Name == NAME) {                                                          \
 186     FPM.addPass(CREATE_PASS);                                                  \
 187     return true;                                                               \
 188   }
 189 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
 190   if (Name == "require<" NAME ">") {                                           \
 191     FPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                 \
 192     return true;                                                               \
 193   }                                                                            \
 194   if (Name == "invalidate<" NAME ">") {                                        \
 195     FPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());              \
 196     return true;                                                               \
 197   }
 198 #include "PassRegistry.def"
 199
 200   return false;
 201 }
 202
 203 bool Passes::parseFunctionPassPipeline(FunctionPassManager &FPM,
 204                                        StringRef &PipelineText,
 205                                        bool VerifyEachPass, bool DebugLogging) {
 206   for (;;) {
 207     // Parse nested pass managers by recursing.
 208     if (PipelineText.startswith("function(")) {
 209       FunctionPassManager NestedFPM(DebugLogging);
 210
 211       // Parse the inner pipeline inte the nested manager.
 212       PipelineText = PipelineText.substr(strlen("function("));
 213       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
 214                                      DebugLogging) ||
 215           PipelineText.empty())
 216         return false;
 217       assert(PipelineText[0] == ')');
 218       PipelineText = PipelineText.substr(1);
 219
 220       // Add the nested pass manager with the appropriate adaptor.
 221       FPM.addPass(std::move(NestedFPM));
 222     } else {
 223       // Otherwise try to parse a pass name.
 224       size_t End = PipelineText.find_first_of(",)");
 225       if (!parseFunctionPassName(FPM, PipelineText.substr(0, End)))
 226         return false;
 227       if (VerifyEachPass)
 228         FPM.addPass(VerifierPass());
 229
 230       PipelineText = PipelineText.substr(End);
 231     }
 232
 233     if (PipelineText.empty() || PipelineText[0] == ')')
 234       return true;
 235
 236     assert(PipelineText[0] == ',');
 237     PipelineText = PipelineText.substr(1);
 238   }
 239 }
 240
 241 bool Passes::parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
 242                                     StringRef &PipelineText,
 243                                     bool VerifyEachPass, bool DebugLogging) {
 244   for (;;) {
 245     // Parse nested pass managers by recursing.
 246     if (PipelineText.startswith("cgscc(")) {
 247       CGSCCPassManager NestedCGPM(DebugLogging);
 248
 249       // Parse the inner pipeline into the nested manager.
 250       PipelineText = PipelineText.substr(strlen("cgscc("));
 251       if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass,
 252                                   DebugLogging) ||
 253           PipelineText.empty())
 254         return false;
 255       assert(PipelineText[0] == ')');
 256       PipelineText = PipelineText.substr(1);
 257
 258       // Add the nested pass manager with the appropriate adaptor.
 259       CGPM.addPass(std::move(NestedCGPM));
 260     } else if (PipelineText.startswith("function(")) {
 261       FunctionPassManager NestedFPM(DebugLogging);
 262
 263       // Parse the inner pipeline inte the nested manager.
 264       PipelineText = PipelineText.substr(strlen("function("));
 265       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
 266                                      DebugLogging) ||
 267           PipelineText.empty())
 268         return false;
 269       assert(PipelineText[0] == ')');
 270       PipelineText = PipelineText.substr(1);
 271
 272       // Add the nested pass manager with the appropriate adaptor.
 273       CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(NestedFPM)));
 274     } else {
 275       // Otherwise try to parse a pass name.
 276       size_t End = PipelineText.find_first_of(",)");
 277       if (!parseCGSCCPassName(CGPM, PipelineText.substr(0, End)))
 278         return false;
 279       // FIXME: No verifier support for CGSCC passes!
 280
 281       PipelineText = PipelineText.substr(End);
 282     }
 283
 284     if (PipelineText.empty() || PipelineText[0] == ')')
 285       return true;
 286
 287     assert(PipelineText[0] == ',');
 288     PipelineText = PipelineText.substr(1);
 289   }
 290 }
 291
 292 bool Passes::parseModulePassPipeline(ModulePassManager &MPM,
 293                                      StringRef &PipelineText,
 294                                      bool VerifyEachPass, bool DebugLogging) {
 295   for (;;) {
 296     // Parse nested pass managers by recursing.
 297     if (PipelineText.startswith("module(")) {
 298       ModulePassManager NestedMPM(DebugLogging);
 299
 300       // Parse the inner pipeline into the nested manager.
 301       PipelineText = PipelineText.substr(strlen("module("));
 302       if (!parseModulePassPipeline(NestedMPM, PipelineText, VerifyEachPass,
 303                                    DebugLogging) ||
 304           PipelineText.empty())
 305         return false;
 306       assert(PipelineText[0] == ')');
 307       PipelineText = PipelineText.substr(1);
 308
 309       // Now add the nested manager as a module pass.
 310       MPM.addPass(std::move(NestedMPM));
 311     } else if (PipelineText.startswith("cgscc(")) {
 312       CGSCCPassManager NestedCGPM(DebugLogging);
 313
 314       // Parse the inner pipeline inte the nested manager.
 315       PipelineText = PipelineText.substr(strlen("cgscc("));
 316       if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass,
 317                                   DebugLogging) ||
 318           PipelineText.empty())
 319         return false;
 320       assert(PipelineText[0] == ')');
 321       PipelineText = PipelineText.substr(1);
 322
 323       // Add the nested pass manager with the appropriate adaptor.
 324       MPM.addPass(
 325           createModuleToPostOrderCGSCCPassAdaptor(std::move(NestedCGPM)));
 326     } else if (PipelineText.startswith("function(")) {
 327       FunctionPassManager NestedFPM(DebugLogging);
 328
 329       // Parse the inner pipeline inte the nested manager.
 330       PipelineText = PipelineText.substr(strlen("function("));
 331       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
 332                                      DebugLogging) ||
 333           PipelineText.empty())
 334         return false;
 335       assert(PipelineText[0] == ')');
 336       PipelineText = PipelineText.substr(1);
 337
 338       // Add the nested pass manager with the appropriate adaptor.
 339       MPM.addPass(createModuleToFunctionPassAdaptor(std::move(NestedFPM)));
 340     } else {
 341       // Otherwise try to parse a pass name.
 342       size_t End = PipelineText.find_first_of(",)");
 343       if (!parseModulePassName(MPM, PipelineText.substr(0, End)))
 344         return false;
 345       if (VerifyEachPass)
 346         MPM.addPass(VerifierPass());
 347
 348       PipelineText = PipelineText.substr(End);
 349     }
 350
 351     if (PipelineText.empty() || PipelineText[0] == ')')
 352       return true;
 353
 354     assert(PipelineText[0] == ',');
 355     PipelineText = PipelineText.substr(1);
 356   }
 357 }
 358
 359 // Primary pass pipeline description parsing routine.
 360 // FIXME: Should this routine accept a TargetMachine or require the caller to
 361 // pre-populate the analysis managers with target-specific stuff?
 362 bool Passes::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText,
 363                                bool VerifyEachPass, bool DebugLogging) {
 364   // By default, try to parse the pipeline as-if it were within an implicit
 365   // 'module(...)' pass pipeline. If this will parse at all, it needs to
 366   // consume the entire string.
 367   if (parseModulePassPipeline(MPM, PipelineText, VerifyEachPass, DebugLogging))
 368     return PipelineText.empty();
 369
 370   // This isn't parsable as a module pipeline, look for the end of a pass name
 371   // and directly drop down to that layer.
 372   StringRef FirstName =
 373       PipelineText.substr(0, PipelineText.find_first_of(",)"));
 374   assert(!isModulePassName(FirstName) &&
 375          "Already handled all module pipeline options.");
 376
 377   // If this looks like a CGSCC pass, parse the whole thing as a CGSCC
 378   // pipeline.
 379   if (isCGSCCPassName(FirstName)) {
 380     CGSCCPassManager CGPM(DebugLogging);
 381     if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass,
 382                                 DebugLogging) ||
 383         !PipelineText.empty())
 384       return false;
 385     MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
 386     return true;
 387   }
 388
 389   // Similarly, if this looks like a Function pass, parse the whole thing as
 390   // a Function pipelien.
 391   if (isFunctionPassName(FirstName)) {
 392     FunctionPassManager FPM(DebugLogging);
 393     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass,
 394                                    DebugLogging) ||
 395         !PipelineText.empty())
 396       return false;
 397     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
 398     return true;
 399   }
 400
 401   return false;
 402 }