lib/Passes/PassBuilder.cpp

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