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