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