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/AliasAnalysis.h" 20 #include "llvm/Analysis/AliasAnalysisEvaluator.h" 21 #include "llvm/Analysis/AssumptionCache.h" 22 #include "llvm/Analysis/BasicAliasAnalysis.h" 23 #include "llvm/Analysis/CFLAliasAnalysis.h" 24 #include "llvm/Analysis/CGSCCPassManager.h" 25 #include "llvm/Analysis/DominanceFrontier.h" 26 #include "llvm/Analysis/LazyCallGraph.h" 27 #include "llvm/Analysis/LoopInfo.h" 28 #include "llvm/Analysis/PostDominators.h" 29 #include "llvm/Analysis/RegionInfo.h" 30 #include "llvm/Analysis/ScalarEvolution.h" 31 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 32 #include "llvm/Analysis/ScopedNoAliasAA.h" 33 #include "llvm/Analysis/TargetLibraryInfo.h" 34 #include "llvm/Analysis/TargetTransformInfo.h" 35 #include "llvm/Analysis/TypeBasedAliasAnalysis.h" 36 #include "llvm/IR/Dominators.h" 37 #include "llvm/IR/IRPrintingPasses.h" 38 #include "llvm/IR/PassManager.h" 39 #include "llvm/IR/Verifier.h" 40 #include "llvm/Support/Debug.h" 41 #include "llvm/Target/TargetMachine.h" 42 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h" 43 #include "llvm/Transforms/IPO/FunctionAttrs.h" 44 #include "llvm/Transforms/IPO/InferFunctionAttrs.h" 45 #include "llvm/Transforms/IPO/StripDeadPrototypes.h" 46 #include "llvm/Transforms/InstCombine/InstCombine.h" 47 #include "llvm/Transforms/Scalar/ADCE.h" 48 #include "llvm/Transforms/Scalar/EarlyCSE.h" 49 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" 50 #include "llvm/Transforms/Scalar/SROA.h" 51 #include "llvm/Transforms/Scalar/SimplifyCFG.h" 52 #include <type_traits> 53 54 using namespace llvm; 55 56 namespace { 57 58 /// \brief No-op module pass which does nothing. 59 struct NoOpModulePass { 60 PreservedAnalyses run(Module &M) { return PreservedAnalyses::all(); } 61 static StringRef name() { return "NoOpModulePass"; } 62 }; 63 64 /// \brief No-op module analysis. 65 struct NoOpModuleAnalysis : AnalysisBase<NoOpModuleAnalysis> { 66 struct Result {}; 67 Result run(Module &) { return Result(); } 68 static StringRef name() { return "NoOpModuleAnalysis"; } 69 }; 70 71 /// \brief No-op CGSCC pass which does nothing. 72 struct NoOpCGSCCPass { 73 PreservedAnalyses run(LazyCallGraph::SCC &C) { 74 return PreservedAnalyses::all(); 75 } 76 static StringRef name() { return "NoOpCGSCCPass"; } 77 }; 78 79 /// \brief No-op CGSCC analysis. 80 struct NoOpCGSCCAnalysis : AnalysisBase<NoOpCGSCCAnalysis> { 81 struct Result {}; 82 Result run(LazyCallGraph::SCC &) { return Result(); } 83 static StringRef name() { return "NoOpCGSCCAnalysis"; } 84 }; 85 86 /// \brief No-op function pass which does nothing. 87 struct NoOpFunctionPass { 88 PreservedAnalyses run(Function &F) { return PreservedAnalyses::all(); } 89 static StringRef name() { return "NoOpFunctionPass"; } 90 }; 91 92 /// \brief No-op function analysis. 93 struct NoOpFunctionAnalysis : AnalysisBase<NoOpFunctionAnalysis> { 94 struct Result {}; 95 Result run(Function &) { return Result(); } 96 static StringRef name() { return "NoOpFunctionAnalysis"; } 97 }; 98 99 /// \brief No-op loop pass which does nothing. 100 struct NoOpLoopPass { 101 PreservedAnalyses run(Loop &L) { return PreservedAnalyses::all(); } 102 static StringRef name() { return "NoOpLoopPass"; } 103 }; 104 105 /// \brief No-op loop analysis. 106 struct NoOpLoopAnalysis : AnalysisBase<NoOpLoopAnalysis> { 107 struct Result {}; 108 Result run(Loop &) { return Result(); } 109 static StringRef name() { return "NoOpLoopAnalysis"; } 110 }; 111 112 } // End anonymous namespace. 113 114 void PassBuilder::registerModuleAnalyses(ModuleAnalysisManager &MAM) { 115 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \ 116 MAM.registerPass([&] { return CREATE_PASS; }); 117 #include "PassRegistry.def" 118 } 119 120 void PassBuilder::registerCGSCCAnalyses(CGSCCAnalysisManager &CGAM) { 121 #define CGSCC_ANALYSIS(NAME, CREATE_PASS) \ 122 CGAM.registerPass([&] { return CREATE_PASS; }); 123 #include "PassRegistry.def" 124 } 125 126 void PassBuilder::registerFunctionAnalyses(FunctionAnalysisManager &FAM) { 127 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \ 128 FAM.registerPass([&] { return CREATE_PASS; }); 129 #include "PassRegistry.def" 130 } 131 132 void PassBuilder::registerLoopAnalyses(LoopAnalysisManager &LAM) { 133 #define LOOP_ANALYSIS(NAME, CREATE_PASS) \ 134 LAM.registerPass([&] { return CREATE_PASS; }); 135 #include "PassRegistry.def" 136 } 137 138 #ifndef NDEBUG 139 static bool isModulePassName(StringRef Name) { 140 #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; 141 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \ 142 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ 143 return true; 144 #include "PassRegistry.def" 145 146 return false; 147 } 148 #endif 149 150 static bool isCGSCCPassName(StringRef Name) { 151 #define CGSCC_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; 152 #define CGSCC_ANALYSIS(NAME, CREATE_PASS) \ 153 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ 154 return true; 155 #include "PassRegistry.def" 156 157 return false; 158 } 159 160 static bool isFunctionPassName(StringRef Name) { 161 #define FUNCTION_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; 162 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \ 163 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ 164 return true; 165 #include "PassRegistry.def" 166 167 return false; 168 } 169 170 static bool isLoopPassName(StringRef Name) { 171 #define LOOP_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; 172 #define LOOP_ANALYSIS(NAME, CREATE_PASS) \ 173 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ 174 return true; 175 #include "PassRegistry.def" 176 177 return false; 178 } 179 180 bool PassBuilder::parseModulePassName(ModulePassManager &MPM, StringRef Name) { 181 #define MODULE_PASS(NAME, CREATE_PASS) \ 182 if (Name == NAME) { \ 183 MPM.addPass(CREATE_PASS); \ 184 return true; \ 185 } 186 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \ 187 if (Name == "require<" NAME ">") { \ 188 MPM.addPass(RequireAnalysisPass< \ 189 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 190 return true; \ 191 } \ 192 if (Name == "invalidate<" NAME ">") { \ 193 MPM.addPass(InvalidateAnalysisPass< \ 194 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 195 return true; \ 196 } 197 #include "PassRegistry.def" 198 199 return false; 200 } 201 202 bool PassBuilder::parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name) { 203 #define CGSCC_PASS(NAME, CREATE_PASS) \ 204 if (Name == NAME) { \ 205 CGPM.addPass(CREATE_PASS); \ 206 return true; \ 207 } 208 #define CGSCC_ANALYSIS(NAME, CREATE_PASS) \ 209 if (Name == "require<" NAME ">") { \ 210 CGPM.addPass(RequireAnalysisPass< \ 211 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 212 return true; \ 213 } \ 214 if (Name == "invalidate<" NAME ">") { \ 215 CGPM.addPass(InvalidateAnalysisPass< \ 216 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 217 return true; \ 218 } 219 #include "PassRegistry.def" 220 221 return false; 222 } 223 224 bool PassBuilder::parseFunctionPassName(FunctionPassManager &FPM, 225 StringRef Name) { 226 #define FUNCTION_PASS(NAME, CREATE_PASS) \ 227 if (Name == NAME) { \ 228 FPM.addPass(CREATE_PASS); \ 229 return true; \ 230 } 231 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \ 232 if (Name == "require<" NAME ">") { \ 233 FPM.addPass(RequireAnalysisPass< \ 234 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 235 return true; \ 236 } \ 237 if (Name == "invalidate<" NAME ">") { \ 238 FPM.addPass(InvalidateAnalysisPass< \ 239 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 240 return true; \ 241 } 242 #include "PassRegistry.def" 243 244 return false; 245 } 246 247 bool PassBuilder::parseLoopPassName(LoopPassManager &FPM, 248 StringRef Name) { 249 #define LOOP_PASS(NAME, CREATE_PASS) \ 250 if (Name == NAME) { \ 251 FPM.addPass(CREATE_PASS); \ 252 return true; \ 253 } 254 #define LOOP_ANALYSIS(NAME, CREATE_PASS) \ 255 if (Name == "require<" NAME ">") { \ 256 FPM.addPass(RequireAnalysisPass< \ 257 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 258 return true; \ 259 } \ 260 if (Name == "invalidate<" NAME ">") { \ 261 FPM.addPass(InvalidateAnalysisPass< \ 262 std::remove_reference<decltype(CREATE_PASS)>::type>()); \ 263 return true; \ 264 } 265 #include "PassRegistry.def" 266 267 return false; 268 } 269 270 bool PassBuilder::parseAAPassName(AAManager &AA, StringRef Name) { 271 #define FUNCTION_ALIAS_ANALYSIS(NAME, CREATE_PASS) \ 272 if (Name == NAME) { \ 273 AA.registerFunctionAnalysis< \ 274 std::remove_reference<decltype(CREATE_PASS)>::type>(); \ 275 return true; \ 276 } 277 #include "PassRegistry.def" 278 279 return false; 280 } 281 282 bool PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM, 283 StringRef &PipelineText, 284 bool VerifyEachPass, 285 bool DebugLogging) { 286 for (;;) { 287 // Parse nested pass managers by recursing. 288 if (PipelineText.startswith("loop(")) { 289 LoopPassManager NestedLPM(DebugLogging); 290 291 // Parse the inner pipeline inte the nested manager. 292 PipelineText = PipelineText.substr(strlen("loop(")); 293 if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass, 294 DebugLogging) || 295 PipelineText.empty()) 296 return false; 297 assert(PipelineText[0] == ')'); 298 PipelineText = PipelineText.substr(1); 299 300 // Add the nested pass manager with the appropriate adaptor. 301 LPM.addPass(std::move(NestedLPM)); 302 } else { 303 // Otherwise try to parse a pass name. 304 size_t End = PipelineText.find_first_of(",)"); 305 if (!parseLoopPassName(LPM, PipelineText.substr(0, End))) 306 return false; 307 // TODO: Ideally, we would run a LoopVerifierPass() here in the 308 // VerifyEachPass case, but we don't have such a verifier yet. 309 310 PipelineText = PipelineText.substr(End); 311 } 312 313 if (PipelineText.empty() || PipelineText[0] == ')') 314 return true; 315 316 assert(PipelineText[0] == ','); 317 PipelineText = PipelineText.substr(1); 318 } 319 } 320 321 bool PassBuilder::parseFunctionPassPipeline(FunctionPassManager &FPM, 322 StringRef &PipelineText, 323 bool VerifyEachPass, 324 bool DebugLogging) { 325 for (;;) { 326 // Parse nested pass managers by recursing. 327 if (PipelineText.startswith("function(")) { 328 FunctionPassManager NestedFPM(DebugLogging); 329 330 // Parse the inner pipeline inte the nested manager. 331 PipelineText = PipelineText.substr(strlen("function(")); 332 if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass, 333 DebugLogging) || 334 PipelineText.empty()) 335 return false; 336 assert(PipelineText[0] == ')'); 337 PipelineText = PipelineText.substr(1); 338 339 // Add the nested pass manager with the appropriate adaptor. 340 FPM.addPass(std::move(NestedFPM)); 341 } else if (PipelineText.startswith("loop(")) { 342 LoopPassManager NestedLPM(DebugLogging); 343 344 // Parse the inner pipeline inte the nested manager. 345 PipelineText = PipelineText.substr(strlen("loop(")); 346 if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass, 347 DebugLogging) || 348 PipelineText.empty()) 349 return false; 350 assert(PipelineText[0] == ')'); 351 PipelineText = PipelineText.substr(1); 352 353 // Add the nested pass manager with the appropriate adaptor. 354 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(NestedLPM))); 355 } else { 356 // Otherwise try to parse a pass name. 357 size_t End = PipelineText.find_first_of(",)"); 358 if (!parseFunctionPassName(FPM, PipelineText.substr(0, End))) 359 return false; 360 if (VerifyEachPass) 361 FPM.addPass(VerifierPass()); 362 363 PipelineText = PipelineText.substr(End); 364 } 365 366 if (PipelineText.empty() || PipelineText[0] == ')') 367 return true; 368 369 assert(PipelineText[0] == ','); 370 PipelineText = PipelineText.substr(1); 371 } 372 } 373 374 bool PassBuilder::parseCGSCCPassPipeline(CGSCCPassManager &CGPM, 375 StringRef &PipelineText, 376 bool VerifyEachPass, 377 bool DebugLogging) { 378 for (;;) { 379 // Parse nested pass managers by recursing. 380 if (PipelineText.startswith("cgscc(")) { 381 CGSCCPassManager NestedCGPM(DebugLogging); 382 383 // Parse the inner pipeline into the nested manager. 384 PipelineText = PipelineText.substr(strlen("cgscc(")); 385 if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass, 386 DebugLogging) || 387 PipelineText.empty()) 388 return false; 389 assert(PipelineText[0] == ')'); 390 PipelineText = PipelineText.substr(1); 391 392 // Add the nested pass manager with the appropriate adaptor. 393 CGPM.addPass(std::move(NestedCGPM)); 394 } else if (PipelineText.startswith("function(")) { 395 FunctionPassManager NestedFPM(DebugLogging); 396 397 // Parse the inner pipeline inte the nested manager. 398 PipelineText = PipelineText.substr(strlen("function(")); 399 if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass, 400 DebugLogging) || 401 PipelineText.empty()) 402 return false; 403 assert(PipelineText[0] == ')'); 404 PipelineText = PipelineText.substr(1); 405 406 // Add the nested pass manager with the appropriate adaptor. 407 CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(NestedFPM))); 408 } else { 409 // Otherwise try to parse a pass name. 410 size_t End = PipelineText.find_first_of(",)"); 411 if (!parseCGSCCPassName(CGPM, PipelineText.substr(0, End))) 412 return false; 413 // FIXME: No verifier support for CGSCC passes! 414 415 PipelineText = PipelineText.substr(End); 416 } 417 418 if (PipelineText.empty() || PipelineText[0] == ')') 419 return true; 420 421 assert(PipelineText[0] == ','); 422 PipelineText = PipelineText.substr(1); 423 } 424 } 425 426 bool PassBuilder::parseModulePassPipeline(ModulePassManager &MPM, 427 StringRef &PipelineText, 428 bool VerifyEachPass, 429 bool DebugLogging) { 430 for (;;) { 431 // Parse nested pass managers by recursing. 432 if (PipelineText.startswith("module(")) { 433 ModulePassManager NestedMPM(DebugLogging); 434 435 // Parse the inner pipeline into the nested manager. 436 PipelineText = PipelineText.substr(strlen("module(")); 437 if (!parseModulePassPipeline(NestedMPM, PipelineText, VerifyEachPass, 438 DebugLogging) || 439 PipelineText.empty()) 440 return false; 441 assert(PipelineText[0] == ')'); 442 PipelineText = PipelineText.substr(1); 443 444 // Now add the nested manager as a module pass. 445 MPM.addPass(std::move(NestedMPM)); 446 } else if (PipelineText.startswith("cgscc(")) { 447 CGSCCPassManager NestedCGPM(DebugLogging); 448 449 // Parse the inner pipeline inte the nested manager. 450 PipelineText = PipelineText.substr(strlen("cgscc(")); 451 if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass, 452 DebugLogging) || 453 PipelineText.empty()) 454 return false; 455 assert(PipelineText[0] == ')'); 456 PipelineText = PipelineText.substr(1); 457 458 // Add the nested pass manager with the appropriate adaptor. 459 MPM.addPass( 460 createModuleToPostOrderCGSCCPassAdaptor(std::move(NestedCGPM))); 461 } else if (PipelineText.startswith("function(")) { 462 FunctionPassManager NestedFPM(DebugLogging); 463 464 // Parse the inner pipeline inte the nested manager. 465 PipelineText = PipelineText.substr(strlen("function(")); 466 if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass, 467 DebugLogging) || 468 PipelineText.empty()) 469 return false; 470 assert(PipelineText[0] == ')'); 471 PipelineText = PipelineText.substr(1); 472 473 // Add the nested pass manager with the appropriate adaptor. 474 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(NestedFPM))); 475 } else { 476 // Otherwise try to parse a pass name. 477 size_t End = PipelineText.find_first_of(",)"); 478 if (!parseModulePassName(MPM, PipelineText.substr(0, End))) 479 return false; 480 if (VerifyEachPass) 481 MPM.addPass(VerifierPass()); 482 483 PipelineText = PipelineText.substr(End); 484 } 485 486 if (PipelineText.empty() || PipelineText[0] == ')') 487 return true; 488 489 assert(PipelineText[0] == ','); 490 PipelineText = PipelineText.substr(1); 491 } 492 } 493 494 // Primary pass pipeline description parsing routine. 495 // FIXME: Should this routine accept a TargetMachine or require the caller to 496 // pre-populate the analysis managers with target-specific stuff? 497 bool PassBuilder::parsePassPipeline(ModulePassManager &MPM, 498 StringRef PipelineText, bool VerifyEachPass, 499 bool DebugLogging) { 500 // By default, try to parse the pipeline as-if it were within an implicit 501 // 'module(...)' pass pipeline. If this will parse at all, it needs to 502 // consume the entire string. 503 if (parseModulePassPipeline(MPM, PipelineText, VerifyEachPass, DebugLogging)) 504 return PipelineText.empty(); 505 506 // This isn't parsable as a module pipeline, look for the end of a pass name 507 // and directly drop down to that layer. 508 StringRef FirstName = 509 PipelineText.substr(0, PipelineText.find_first_of(",)")); 510 assert(!isModulePassName(FirstName) && 511 "Already handled all module pipeline options."); 512 513 // If this looks like a CGSCC pass, parse the whole thing as a CGSCC 514 // pipeline. 515 if (PipelineText.startswith("cgscc(") || isCGSCCPassName(FirstName)) { 516 CGSCCPassManager CGPM(DebugLogging); 517 if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass, 518 DebugLogging) || 519 !PipelineText.empty()) 520 return false; 521 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); 522 return true; 523 } 524 525 // Similarly, if this looks like a Function pass, parse the whole thing as 526 // a Function pipelien. 527 if (PipelineText.startswith("function(") || isFunctionPassName(FirstName)) { 528 FunctionPassManager FPM(DebugLogging); 529 if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass, 530 DebugLogging) || 531 !PipelineText.empty()) 532 return false; 533 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 534 return true; 535 } 536 537 // If this looks like a Loop pass, parse the whole thing as a Loop pipeline. 538 if (PipelineText.startswith("loop(") || isLoopPassName(FirstName)) { 539 LoopPassManager LPM(DebugLogging); 540 if (!parseLoopPassPipeline(LPM, PipelineText, VerifyEachPass, 541 DebugLogging) || 542 !PipelineText.empty()) 543 return false; 544 FunctionPassManager FPM(DebugLogging); 545 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 546 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 547 return true; 548 } 549 550 551 return false; 552 } 553 554 bool PassBuilder::parseAAPipeline(AAManager &AA, StringRef PipelineText) { 555 while (!PipelineText.empty()) { 556 StringRef Name; 557 std::tie(Name, PipelineText) = PipelineText.split(','); 558 if (!parseAAPassName(AA, Name)) 559 return false; 560 } 561 562 return true; 563 } 564