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