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