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