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