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