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