tools/opt/Passes.cpp

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