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