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 } 398