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