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