1 //===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the legacy LLVM Pass Manager infrastructure. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/IR/LegacyPassManager.h" 14 #include "llvm/ADT/MapVector.h" 15 #include "llvm/IR/DiagnosticInfo.h" 16 #include "llvm/IR/IRPrintingPasses.h" 17 #include "llvm/IR/LLVMContext.h" 18 #include "llvm/IR/LegacyPassManagers.h" 19 #include "llvm/IR/Module.h" 20 #include "llvm/IR/PassTimingInfo.h" 21 #include "llvm/IR/PrintPasses.h" 22 #include "llvm/Support/Chrono.h" 23 #include "llvm/Support/CommandLine.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/Error.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/TimeProfiler.h" 28 #include "llvm/Support/Timer.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include <algorithm> 31 32 using namespace llvm; 33 34 extern cl::opt<bool> UseNewDbgInfoFormat; 35 // See PassManagers.h for Pass Manager infrastructure overview. 36 37 //===----------------------------------------------------------------------===// 38 // Pass debugging information. Often it is useful to find out what pass is 39 // running when a crash occurs in a utility. When this library is compiled with 40 // debugging on, a command line option (--debug-pass) is enabled that causes the 41 // pass name to be printed before it executes. 42 // 43 44 namespace { 45 // Different debug levels that can be enabled... 46 enum PassDebugLevel { 47 Disabled, Arguments, Structure, Executions, Details 48 }; 49 } // namespace 50 51 static cl::opt<enum PassDebugLevel> PassDebugging( 52 "debug-pass", cl::Hidden, 53 cl::desc("Print legacy PassManager debugging information"), 54 cl::values(clEnumVal(Disabled, "disable debug output"), 55 clEnumVal(Arguments, "print pass arguments to pass to 'opt'"), 56 clEnumVal(Structure, "print pass structure before run()"), 57 clEnumVal(Executions, "print pass name before it is executed"), 58 clEnumVal(Details, "print pass details when it is executed"))); 59 60 /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions 61 /// or higher is specified. 62 bool PMDataManager::isPassDebuggingExecutionsOrMore() const { 63 return PassDebugging >= Executions; 64 } 65 66 unsigned PMDataManager::initSizeRemarkInfo( 67 Module &M, StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount) { 68 // Only calculate getInstructionCount if the size-info remark is requested. 69 unsigned InstrCount = 0; 70 71 // Collect instruction counts for every function. We'll use this to emit 72 // per-function size remarks later. 73 for (Function &F : M) { 74 unsigned FCount = F.getInstructionCount(); 75 76 // Insert a record into FunctionToInstrCount keeping track of the current 77 // size of the function as the first member of a pair. Set the second 78 // member to 0; if the function is deleted by the pass, then when we get 79 // here, we'll be able to let the user know that F no longer contributes to 80 // the module. 81 FunctionToInstrCount[F.getName().str()] = 82 std::pair<unsigned, unsigned>(FCount, 0); 83 InstrCount += FCount; 84 } 85 return InstrCount; 86 } 87 88 void PMDataManager::emitInstrCountChangedRemark( 89 Pass *P, Module &M, int64_t Delta, unsigned CountBefore, 90 StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount, 91 Function *F) { 92 // If it's a pass manager, don't emit a remark. (This hinges on the assumption 93 // that the only passes that return non-null with getAsPMDataManager are pass 94 // managers.) The reason we have to do this is to avoid emitting remarks for 95 // CGSCC passes. 96 if (P->getAsPMDataManager()) 97 return; 98 99 // Set to true if this isn't a module pass or CGSCC pass. 100 bool CouldOnlyImpactOneFunction = (F != nullptr); 101 102 // Helper lambda that updates the changes to the size of some function. 103 auto UpdateFunctionChanges = 104 [&FunctionToInstrCount](Function &MaybeChangedFn) { 105 // Update the total module count. 106 unsigned FnSize = MaybeChangedFn.getInstructionCount(); 107 auto It = FunctionToInstrCount.find(MaybeChangedFn.getName()); 108 109 // If we created a new function, then we need to add it to the map and 110 // say that it changed from 0 instructions to FnSize. 111 if (It == FunctionToInstrCount.end()) { 112 FunctionToInstrCount[MaybeChangedFn.getName()] = 113 std::pair<unsigned, unsigned>(0, FnSize); 114 return; 115 } 116 // Insert the new function size into the second member of the pair. This 117 // tells us whether or not this function changed in size. 118 It->second.second = FnSize; 119 }; 120 121 // We need to initially update all of the function sizes. 122 // If no function was passed in, then we're either a module pass or an 123 // CGSCC pass. 124 if (!CouldOnlyImpactOneFunction) 125 std::for_each(M.begin(), M.end(), UpdateFunctionChanges); 126 else 127 UpdateFunctionChanges(*F); 128 129 // Do we have a function we can use to emit a remark? 130 if (!CouldOnlyImpactOneFunction) { 131 // We need a function containing at least one basic block in order to output 132 // remarks. Since it's possible that the first function in the module 133 // doesn't actually contain a basic block, we have to go and find one that's 134 // suitable for emitting remarks. 135 auto It = llvm::find_if(M, [](const Function &Fn) { return !Fn.empty(); }); 136 137 // Didn't find a function. Quit. 138 if (It == M.end()) 139 return; 140 141 // We found a function containing at least one basic block. 142 F = &*It; 143 } 144 int64_t CountAfter = static_cast<int64_t>(CountBefore) + Delta; 145 BasicBlock &BB = *F->begin(); 146 OptimizationRemarkAnalysis R("size-info", "IRSizeChange", 147 DiagnosticLocation(), &BB); 148 // FIXME: Move ore namespace to DiagnosticInfo so that we can use it. This 149 // would let us use NV instead of DiagnosticInfoOptimizationBase::Argument. 150 R << DiagnosticInfoOptimizationBase::Argument("Pass", P->getPassName()) 151 << ": IR instruction count changed from " 152 << DiagnosticInfoOptimizationBase::Argument("IRInstrsBefore", CountBefore) 153 << " to " 154 << DiagnosticInfoOptimizationBase::Argument("IRInstrsAfter", CountAfter) 155 << "; Delta: " 156 << DiagnosticInfoOptimizationBase::Argument("DeltaInstrCount", Delta); 157 F->getContext().diagnose(R); // Not using ORE for layering reasons. 158 159 // Emit per-function size change remarks separately. 160 std::string PassName = P->getPassName().str(); 161 162 // Helper lambda that emits a remark when the size of a function has changed. 163 auto EmitFunctionSizeChangedRemark = [&FunctionToInstrCount, &F, &BB, 164 &PassName](StringRef Fname) { 165 unsigned FnCountBefore, FnCountAfter; 166 std::pair<unsigned, unsigned> &Change = FunctionToInstrCount[Fname]; 167 std::tie(FnCountBefore, FnCountAfter) = Change; 168 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) - 169 static_cast<int64_t>(FnCountBefore); 170 171 if (FnDelta == 0) 172 return; 173 174 // FIXME: We shouldn't use BB for the location here. Unfortunately, because 175 // the function that we're looking at could have been deleted, we can't use 176 // it for the source location. We *want* remarks when a function is deleted 177 // though, so we're kind of stuck here as is. (This remark, along with the 178 // whole-module size change remarks really ought not to have source 179 // locations at all.) 180 OptimizationRemarkAnalysis FR("size-info", "FunctionIRSizeChange", 181 DiagnosticLocation(), &BB); 182 FR << DiagnosticInfoOptimizationBase::Argument("Pass", PassName) 183 << ": Function: " 184 << DiagnosticInfoOptimizationBase::Argument("Function", Fname) 185 << ": IR instruction count changed from " 186 << DiagnosticInfoOptimizationBase::Argument("IRInstrsBefore", 187 FnCountBefore) 188 << " to " 189 << DiagnosticInfoOptimizationBase::Argument("IRInstrsAfter", 190 FnCountAfter) 191 << "; Delta: " 192 << DiagnosticInfoOptimizationBase::Argument("DeltaInstrCount", FnDelta); 193 F->getContext().diagnose(FR); 194 195 // Update the function size. 196 Change.first = FnCountAfter; 197 }; 198 199 // Are we looking at more than one function? If so, emit remarks for all of 200 // the functions in the module. Otherwise, only emit one remark. 201 if (!CouldOnlyImpactOneFunction) 202 std::for_each(FunctionToInstrCount.keys().begin(), 203 FunctionToInstrCount.keys().end(), 204 EmitFunctionSizeChangedRemark); 205 else 206 EmitFunctionSizeChangedRemark(F->getName().str()); 207 } 208 209 void PassManagerPrettyStackEntry::print(raw_ostream &OS) const { 210 if (!V && !M) 211 OS << "Releasing pass '"; 212 else 213 OS << "Running pass '"; 214 215 OS << P->getPassName() << "'"; 216 217 if (M) { 218 OS << " on module '" << M->getModuleIdentifier() << "'.\n"; 219 return; 220 } 221 if (!V) { 222 OS << '\n'; 223 return; 224 } 225 226 OS << " on "; 227 if (isa<Function>(V)) 228 OS << "function"; 229 else if (isa<BasicBlock>(V)) 230 OS << "basic block"; 231 else 232 OS << "value"; 233 234 OS << " '"; 235 V->printAsOperand(OS, /*PrintType=*/false, M); 236 OS << "'\n"; 237 } 238 239 namespace llvm { 240 namespace legacy { 241 bool debugPassSpecified() { return PassDebugging != Disabled; } 242 243 //===----------------------------------------------------------------------===// 244 // FunctionPassManagerImpl 245 // 246 /// FunctionPassManagerImpl manages FPPassManagers 247 class FunctionPassManagerImpl : public Pass, 248 public PMDataManager, 249 public PMTopLevelManager { 250 virtual void anchor(); 251 private: 252 bool wasRun; 253 public: 254 static char ID; 255 explicit FunctionPassManagerImpl() 256 : Pass(PT_PassManager, ID), PMTopLevelManager(new FPPassManager()), 257 wasRun(false) {} 258 259 /// \copydoc FunctionPassManager::add() 260 void add(Pass *P) { 261 schedulePass(P); 262 } 263 264 /// createPrinterPass - Get a function printer pass. 265 Pass *createPrinterPass(raw_ostream &O, 266 const std::string &Banner) const override { 267 return createPrintFunctionPass(O, Banner); 268 } 269 270 // Prepare for running an on the fly pass, freeing memory if needed 271 // from a previous run. 272 void releaseMemoryOnTheFly(); 273 274 /// run - Execute all of the passes scheduled for execution. Keep track of 275 /// whether any of the passes modifies the module, and if so, return true. 276 bool run(Function &F); 277 278 /// doInitialization - Run all of the initializers for the function passes. 279 /// 280 bool doInitialization(Module &M) override; 281 282 /// doFinalization - Run all of the finalizers for the function passes. 283 /// 284 bool doFinalization(Module &M) override; 285 286 287 PMDataManager *getAsPMDataManager() override { return this; } 288 Pass *getAsPass() override { return this; } 289 PassManagerType getTopLevelPassManagerType() override { 290 return PMT_FunctionPassManager; 291 } 292 293 /// Pass Manager itself does not invalidate any analysis info. 294 void getAnalysisUsage(AnalysisUsage &Info) const override { 295 Info.setPreservesAll(); 296 } 297 298 FPPassManager *getContainedManager(unsigned N) { 299 assert(N < PassManagers.size() && "Pass number out of range!"); 300 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]); 301 return FP; 302 } 303 304 void dumpPassStructure(unsigned Offset) override { 305 for (unsigned I = 0; I < getNumContainedManagers(); ++I) 306 getContainedManager(I)->dumpPassStructure(Offset); 307 } 308 }; 309 310 void FunctionPassManagerImpl::anchor() {} 311 312 char FunctionPassManagerImpl::ID = 0; 313 314 //===----------------------------------------------------------------------===// 315 // FunctionPassManagerImpl implementation 316 // 317 bool FunctionPassManagerImpl::doInitialization(Module &M) { 318 bool Changed = false; 319 320 dumpArguments(); 321 dumpPasses(); 322 323 for (ImmutablePass *ImPass : getImmutablePasses()) 324 Changed |= ImPass->doInitialization(M); 325 326 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 327 Changed |= getContainedManager(Index)->doInitialization(M); 328 329 return Changed; 330 } 331 332 bool FunctionPassManagerImpl::doFinalization(Module &M) { 333 bool Changed = false; 334 335 for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index) 336 Changed |= getContainedManager(Index)->doFinalization(M); 337 338 for (ImmutablePass *ImPass : getImmutablePasses()) 339 Changed |= ImPass->doFinalization(M); 340 341 return Changed; 342 } 343 344 void FunctionPassManagerImpl::releaseMemoryOnTheFly() { 345 if (!wasRun) 346 return; 347 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 348 FPPassManager *FPPM = getContainedManager(Index); 349 for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) { 350 FPPM->getContainedPass(Index)->releaseMemory(); 351 } 352 } 353 wasRun = false; 354 } 355 356 // Execute all the passes managed by this top level manager. 357 // Return true if any function is modified by a pass. 358 bool FunctionPassManagerImpl::run(Function &F) { 359 bool Changed = false; 360 361 initializeAllAnalysisInfo(); 362 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 363 Changed |= getContainedManager(Index)->runOnFunction(F); 364 F.getContext().yield(); 365 } 366 367 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 368 getContainedManager(Index)->cleanup(); 369 370 wasRun = true; 371 return Changed; 372 } 373 } // namespace legacy 374 } // namespace llvm 375 376 namespace { 377 //===----------------------------------------------------------------------===// 378 // MPPassManager 379 // 380 /// MPPassManager manages ModulePasses and function pass managers. 381 /// It batches all Module passes and function pass managers together and 382 /// sequences them to process one module. 383 class MPPassManager : public Pass, public PMDataManager { 384 public: 385 static char ID; 386 explicit MPPassManager() : Pass(PT_PassManager, ID) {} 387 388 // Delete on the fly managers. 389 ~MPPassManager() override { 390 for (auto &OnTheFlyManager : OnTheFlyManagers) { 391 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 392 delete FPP; 393 } 394 } 395 396 /// createPrinterPass - Get a module printer pass. 397 Pass *createPrinterPass(raw_ostream &O, 398 const std::string &Banner) const override { 399 return createPrintModulePass(O, Banner); 400 } 401 402 /// run - Execute all of the passes scheduled for execution. Keep track of 403 /// whether any of the passes modifies the module, and if so, return true. 404 bool runOnModule(Module &M); 405 406 using llvm::Pass::doInitialization; 407 using llvm::Pass::doFinalization; 408 409 /// Pass Manager itself does not invalidate any analysis info. 410 void getAnalysisUsage(AnalysisUsage &Info) const override { 411 Info.setPreservesAll(); 412 } 413 414 /// Add RequiredPass into list of lower level passes required by pass P. 415 /// RequiredPass is run on the fly by Pass Manager when P requests it 416 /// through getAnalysis interface. 417 void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override; 418 419 /// Return function pass corresponding to PassInfo PI, that is 420 /// required by module pass MP. Instantiate analysis pass, by using 421 /// its runOnFunction() for function F. 422 std::tuple<Pass *, bool> getOnTheFlyPass(Pass *MP, AnalysisID PI, 423 Function &F) override; 424 425 StringRef getPassName() const override { return "Module Pass Manager"; } 426 427 PMDataManager *getAsPMDataManager() override { return this; } 428 Pass *getAsPass() override { return this; } 429 430 // Print passes managed by this manager 431 void dumpPassStructure(unsigned Offset) override { 432 dbgs().indent(Offset*2) << "ModulePass Manager\n"; 433 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 434 ModulePass *MP = getContainedPass(Index); 435 MP->dumpPassStructure(Offset + 1); 436 MapVector<Pass *, legacy::FunctionPassManagerImpl *>::const_iterator I = 437 OnTheFlyManagers.find(MP); 438 if (I != OnTheFlyManagers.end()) 439 I->second->dumpPassStructure(Offset + 2); 440 dumpLastUses(MP, Offset+1); 441 } 442 } 443 444 ModulePass *getContainedPass(unsigned N) { 445 assert(N < PassVector.size() && "Pass number out of range!"); 446 return static_cast<ModulePass *>(PassVector[N]); 447 } 448 449 PassManagerType getPassManagerType() const override { 450 return PMT_ModulePassManager; 451 } 452 453 private: 454 /// Collection of on the fly FPPassManagers. These managers manage 455 /// function passes that are required by module passes. 456 MapVector<Pass *, legacy::FunctionPassManagerImpl *> OnTheFlyManagers; 457 }; 458 459 char MPPassManager::ID = 0; 460 } // End anonymous namespace 461 462 namespace llvm { 463 namespace legacy { 464 //===----------------------------------------------------------------------===// 465 // PassManagerImpl 466 // 467 468 /// PassManagerImpl manages MPPassManagers 469 class PassManagerImpl : public Pass, 470 public PMDataManager, 471 public PMTopLevelManager { 472 virtual void anchor(); 473 474 public: 475 static char ID; 476 explicit PassManagerImpl() 477 : Pass(PT_PassManager, ID), PMTopLevelManager(new MPPassManager()) {} 478 479 /// \copydoc PassManager::add() 480 void add(Pass *P) { 481 schedulePass(P); 482 } 483 484 /// createPrinterPass - Get a module printer pass. 485 Pass *createPrinterPass(raw_ostream &O, 486 const std::string &Banner) const override { 487 return createPrintModulePass(O, Banner); 488 } 489 490 /// run - Execute all of the passes scheduled for execution. Keep track of 491 /// whether any of the passes modifies the module, and if so, return true. 492 bool run(Module &M); 493 494 using llvm::Pass::doInitialization; 495 using llvm::Pass::doFinalization; 496 497 /// Pass Manager itself does not invalidate any analysis info. 498 void getAnalysisUsage(AnalysisUsage &Info) const override { 499 Info.setPreservesAll(); 500 } 501 502 PMDataManager *getAsPMDataManager() override { return this; } 503 Pass *getAsPass() override { return this; } 504 PassManagerType getTopLevelPassManagerType() override { 505 return PMT_ModulePassManager; 506 } 507 508 MPPassManager *getContainedManager(unsigned N) { 509 assert(N < PassManagers.size() && "Pass number out of range!"); 510 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]); 511 return MP; 512 } 513 }; 514 515 void PassManagerImpl::anchor() {} 516 517 char PassManagerImpl::ID = 0; 518 519 //===----------------------------------------------------------------------===// 520 // PassManagerImpl implementation 521 522 // 523 /// run - Execute all of the passes scheduled for execution. Keep track of 524 /// whether any of the passes modifies the module, and if so, return true. 525 bool PassManagerImpl::run(Module &M) { 526 bool Changed = false; 527 528 dumpArguments(); 529 dumpPasses(); 530 531 // RemoveDIs: if a command line flag is given, convert to the DPValue 532 // representation of debug-info for the duration of these passes. 533 if (UseNewDbgInfoFormat) 534 M.convertToNewDbgValues(); 535 536 for (ImmutablePass *ImPass : getImmutablePasses()) 537 Changed |= ImPass->doInitialization(M); 538 539 initializeAllAnalysisInfo(); 540 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 541 Changed |= getContainedManager(Index)->runOnModule(M); 542 M.getContext().yield(); 543 } 544 545 for (ImmutablePass *ImPass : getImmutablePasses()) 546 Changed |= ImPass->doFinalization(M); 547 548 M.convertFromNewDbgValues(); 549 550 return Changed; 551 } 552 } // namespace legacy 553 } // namespace llvm 554 555 //===----------------------------------------------------------------------===// 556 // PMTopLevelManager implementation 557 558 /// Initialize top level manager. Create first pass manager. 559 PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) { 560 PMDM->setTopLevelManager(this); 561 addPassManager(PMDM); 562 activeStack.push(PMDM); 563 } 564 565 /// Set pass P as the last user of the given analysis passes. 566 void 567 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) { 568 unsigned PDepth = 0; 569 if (P->getResolver()) 570 PDepth = P->getResolver()->getPMDataManager().getDepth(); 571 572 for (Pass *AP : AnalysisPasses) { 573 // Record P as the new last user of AP. 574 auto &LastUserOfAP = LastUser[AP]; 575 if (LastUserOfAP) 576 InversedLastUser[LastUserOfAP].erase(AP); 577 LastUserOfAP = P; 578 InversedLastUser[P].insert(AP); 579 580 if (P == AP) 581 continue; 582 583 // Update the last users of passes that are required transitive by AP. 584 AnalysisUsage *AnUsage = findAnalysisUsage(AP); 585 const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet(); 586 SmallVector<Pass *, 12> LastUses; 587 SmallVector<Pass *, 12> LastPMUses; 588 for (AnalysisID ID : IDs) { 589 Pass *AnalysisPass = findAnalysisPass(ID); 590 assert(AnalysisPass && "Expected analysis pass to exist."); 591 AnalysisResolver *AR = AnalysisPass->getResolver(); 592 assert(AR && "Expected analysis resolver to exist."); 593 unsigned APDepth = AR->getPMDataManager().getDepth(); 594 595 if (PDepth == APDepth) 596 LastUses.push_back(AnalysisPass); 597 else if (PDepth > APDepth) 598 LastPMUses.push_back(AnalysisPass); 599 } 600 601 setLastUser(LastUses, P); 602 603 // If this pass has a corresponding pass manager, push higher level 604 // analysis to this pass manager. 605 if (P->getResolver()) 606 setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass()); 607 608 // If AP is the last user of other passes then make P last user of 609 // such passes. 610 auto &LastUsedByAP = InversedLastUser[AP]; 611 for (Pass *L : LastUsedByAP) 612 LastUser[L] = P; 613 InversedLastUser[P].insert(LastUsedByAP.begin(), LastUsedByAP.end()); 614 LastUsedByAP.clear(); 615 } 616 } 617 618 /// Collect passes whose last user is P 619 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses, 620 Pass *P) { 621 auto DMI = InversedLastUser.find(P); 622 if (DMI == InversedLastUser.end()) 623 return; 624 625 auto &LU = DMI->second; 626 LastUses.append(LU.begin(), LU.end()); 627 } 628 629 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) { 630 AnalysisUsage *AnUsage = nullptr; 631 auto DMI = AnUsageMap.find(P); 632 if (DMI != AnUsageMap.end()) 633 AnUsage = DMI->second; 634 else { 635 // Look up the analysis usage from the pass instance (different instances 636 // of the same pass can produce different results), but unique the 637 // resulting object to reduce memory usage. This helps to greatly reduce 638 // memory usage when we have many instances of only a few pass types 639 // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set 640 // of dependencies. 641 AnalysisUsage AU; 642 P->getAnalysisUsage(AU); 643 644 AUFoldingSetNode* Node = nullptr; 645 FoldingSetNodeID ID; 646 AUFoldingSetNode::Profile(ID, AU); 647 void *IP = nullptr; 648 if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP)) 649 Node = N; 650 else { 651 Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU); 652 UniqueAnalysisUsages.InsertNode(Node, IP); 653 } 654 assert(Node && "cached analysis usage must be non null"); 655 656 AnUsageMap[P] = &Node->AU; 657 AnUsage = &Node->AU; 658 } 659 return AnUsage; 660 } 661 662 /// Schedule pass P for execution. Make sure that passes required by 663 /// P are run before P is run. Update analysis info maintained by 664 /// the manager. Remove dead passes. This is a recursive function. 665 void PMTopLevelManager::schedulePass(Pass *P) { 666 667 // TODO : Allocate function manager for this pass, other wise required set 668 // may be inserted into previous function manager 669 670 // Give pass a chance to prepare the stage. 671 P->preparePassManager(activeStack); 672 673 // If P is an analysis pass and it is available then do not 674 // generate the analysis again. Stale analysis info should not be 675 // available at this point. 676 const PassInfo *PI = findAnalysisPassInfo(P->getPassID()); 677 if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) { 678 // Remove any cached AnalysisUsage information. 679 AnUsageMap.erase(P); 680 delete P; 681 return; 682 } 683 684 AnalysisUsage *AnUsage = findAnalysisUsage(P); 685 686 bool checkAnalysis = true; 687 while (checkAnalysis) { 688 checkAnalysis = false; 689 690 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet(); 691 for (const AnalysisID ID : RequiredSet) { 692 693 Pass *AnalysisPass = findAnalysisPass(ID); 694 if (!AnalysisPass) { 695 const PassInfo *PI = findAnalysisPassInfo(ID); 696 697 if (!PI) { 698 // Pass P is not in the global PassRegistry 699 dbgs() << "Pass '" << P->getPassName() << "' is not initialized." << "\n"; 700 dbgs() << "Verify if there is a pass dependency cycle." << "\n"; 701 dbgs() << "Required Passes:" << "\n"; 702 for (const AnalysisID ID2 : RequiredSet) { 703 if (ID == ID2) 704 break; 705 Pass *AnalysisPass2 = findAnalysisPass(ID2); 706 if (AnalysisPass2) { 707 dbgs() << "\t" << AnalysisPass2->getPassName() << "\n"; 708 } else { 709 dbgs() << "\t" << "Error: Required pass not found! Possible causes:" << "\n"; 710 dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)" << "\n"; 711 dbgs() << "\t\t" << "- Corruption of the global PassRegistry" << "\n"; 712 } 713 } 714 } 715 716 assert(PI && "Expected required passes to be initialized"); 717 AnalysisPass = PI->createPass(); 718 if (P->getPotentialPassManagerType () == 719 AnalysisPass->getPotentialPassManagerType()) 720 // Schedule analysis pass that is managed by the same pass manager. 721 schedulePass(AnalysisPass); 722 else if (P->getPotentialPassManagerType () > 723 AnalysisPass->getPotentialPassManagerType()) { 724 // Schedule analysis pass that is managed by a new manager. 725 schedulePass(AnalysisPass); 726 // Recheck analysis passes to ensure that required analyses that 727 // are already checked are still available. 728 checkAnalysis = true; 729 } else 730 // Do not schedule this analysis. Lower level analysis 731 // passes are run on the fly. 732 delete AnalysisPass; 733 } 734 } 735 } 736 737 // Now all required passes are available. 738 if (ImmutablePass *IP = P->getAsImmutablePass()) { 739 // P is a immutable pass and it will be managed by this 740 // top level manager. Set up analysis resolver to connect them. 741 PMDataManager *DM = getAsPMDataManager(); 742 AnalysisResolver *AR = new AnalysisResolver(*DM); 743 P->setResolver(AR); 744 DM->initializeAnalysisImpl(P); 745 addImmutablePass(IP); 746 DM->recordAvailableAnalysis(IP); 747 return; 748 } 749 750 if (PI && !PI->isAnalysis() && shouldPrintBeforePass(PI->getPassArgument())) { 751 Pass *PP = 752 P->createPrinterPass(dbgs(), ("*** IR Dump Before " + P->getPassName() + 753 " (" + PI->getPassArgument() + ") ***") 754 .str()); 755 PP->assignPassManager(activeStack, getTopLevelPassManagerType()); 756 } 757 758 // Add the requested pass to the best available pass manager. 759 P->assignPassManager(activeStack, getTopLevelPassManagerType()); 760 761 if (PI && !PI->isAnalysis() && shouldPrintAfterPass(PI->getPassArgument())) { 762 Pass *PP = 763 P->createPrinterPass(dbgs(), ("*** IR Dump After " + P->getPassName() + 764 " (" + PI->getPassArgument() + ") ***") 765 .str()); 766 PP->assignPassManager(activeStack, getTopLevelPassManagerType()); 767 } 768 } 769 770 /// Find the pass that implements Analysis AID. Search immutable 771 /// passes and all pass managers. If desired pass is not found 772 /// then return NULL. 773 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) { 774 // For immutable passes we have a direct mapping from ID to pass, so check 775 // that first. 776 if (Pass *P = ImmutablePassMap.lookup(AID)) 777 return P; 778 779 // Check pass managers 780 for (PMDataManager *PassManager : PassManagers) 781 if (Pass *P = PassManager->findAnalysisPass(AID, false)) 782 return P; 783 784 // Check other pass managers 785 for (PMDataManager *IndirectPassManager : IndirectPassManagers) 786 if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false)) 787 return P; 788 789 return nullptr; 790 } 791 792 const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const { 793 const PassInfo *&PI = AnalysisPassInfos[AID]; 794 if (!PI) 795 PI = PassRegistry::getPassRegistry()->getPassInfo(AID); 796 else 797 assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) && 798 "The pass info pointer changed for an analysis ID!"); 799 800 return PI; 801 } 802 803 void PMTopLevelManager::addImmutablePass(ImmutablePass *P) { 804 P->initializePass(); 805 ImmutablePasses.push_back(P); 806 807 // Add this pass to the map from its analysis ID. We clobber any prior runs 808 // of the pass in the map so that the last one added is the one found when 809 // doing lookups. 810 AnalysisID AID = P->getPassID(); 811 ImmutablePassMap[AID] = P; 812 813 // Also add any interfaces implemented by the immutable pass to the map for 814 // fast lookup. 815 const PassInfo *PassInf = findAnalysisPassInfo(AID); 816 assert(PassInf && "Expected all immutable passes to be initialized"); 817 for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented()) 818 ImmutablePassMap[ImmPI->getTypeInfo()] = P; 819 } 820 821 // Print passes managed by this top level manager. 822 void PMTopLevelManager::dumpPasses() const { 823 824 if (PassDebugging < Structure) 825 return; 826 827 // Print out the immutable passes 828 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 829 ImmutablePasses[i]->dumpPassStructure(0); 830 } 831 832 // Every class that derives from PMDataManager also derives from Pass 833 // (sometimes indirectly), but there's no inheritance relationship 834 // between PMDataManager and Pass, so we have to getAsPass to get 835 // from a PMDataManager* to a Pass*. 836 for (PMDataManager *Manager : PassManagers) 837 Manager->getAsPass()->dumpPassStructure(1); 838 } 839 840 void PMTopLevelManager::dumpArguments() const { 841 842 if (PassDebugging < Arguments) 843 return; 844 845 dbgs() << "Pass Arguments: "; 846 for (ImmutablePass *P : ImmutablePasses) 847 if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) { 848 assert(PI && "Expected all immutable passes to be initialized"); 849 if (!PI->isAnalysisGroup()) 850 dbgs() << " -" << PI->getPassArgument(); 851 } 852 for (PMDataManager *PM : PassManagers) 853 PM->dumpPassArguments(); 854 dbgs() << "\n"; 855 } 856 857 void PMTopLevelManager::initializeAllAnalysisInfo() { 858 for (PMDataManager *PM : PassManagers) 859 PM->initializeAnalysisInfo(); 860 861 // Initailize other pass managers 862 for (PMDataManager *IPM : IndirectPassManagers) 863 IPM->initializeAnalysisInfo(); 864 } 865 866 /// Destructor 867 PMTopLevelManager::~PMTopLevelManager() { 868 for (PMDataManager *PM : PassManagers) 869 delete PM; 870 871 for (ImmutablePass *P : ImmutablePasses) 872 delete P; 873 } 874 875 //===----------------------------------------------------------------------===// 876 // PMDataManager implementation 877 878 /// Augement AvailableAnalysis by adding analysis made available by pass P. 879 void PMDataManager::recordAvailableAnalysis(Pass *P) { 880 AnalysisID PI = P->getPassID(); 881 882 AvailableAnalysis[PI] = P; 883 884 assert(!AvailableAnalysis.empty()); 885 886 // This pass is the current implementation of all of the interfaces it 887 // implements as well. 888 const PassInfo *PInf = TPM->findAnalysisPassInfo(PI); 889 if (!PInf) return; 890 for (const PassInfo *PI : PInf->getInterfacesImplemented()) 891 AvailableAnalysis[PI->getTypeInfo()] = P; 892 } 893 894 // Return true if P preserves high level analysis used by other 895 // passes managed by this manager 896 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) { 897 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 898 if (AnUsage->getPreservesAll()) 899 return true; 900 901 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 902 for (Pass *P1 : HigherLevelAnalysis) { 903 if (P1->getAsImmutablePass() == nullptr && 904 !is_contained(PreservedSet, P1->getPassID())) 905 return false; 906 } 907 908 return true; 909 } 910 911 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P. 912 void PMDataManager::verifyPreservedAnalysis(Pass *P) { 913 // Don't do this unless assertions are enabled. 914 #ifdef NDEBUG 915 return; 916 #endif 917 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 918 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 919 920 // Verify preserved analysis 921 for (AnalysisID AID : PreservedSet) { 922 if (Pass *AP = findAnalysisPass(AID, true)) { 923 TimeRegion PassTimer(getPassTimer(AP)); 924 AP->verifyAnalysis(); 925 } 926 } 927 } 928 929 /// Remove Analysis not preserved by Pass P 930 void PMDataManager::removeNotPreservedAnalysis(Pass *P) { 931 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 932 if (AnUsage->getPreservesAll()) 933 return; 934 935 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 936 for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(), 937 E = AvailableAnalysis.end(); I != E; ) { 938 DenseMap<AnalysisID, Pass*>::iterator Info = I++; 939 if (Info->second->getAsImmutablePass() == nullptr && 940 !is_contained(PreservedSet, Info->first)) { 941 // Remove this analysis 942 if (PassDebugging >= Details) { 943 Pass *S = Info->second; 944 dbgs() << " -- '" << P->getPassName() << "' is not preserving '"; 945 dbgs() << S->getPassName() << "'\n"; 946 } 947 AvailableAnalysis.erase(Info); 948 } 949 } 950 951 // Check inherited analysis also. If P is not preserving analysis 952 // provided by parent manager then remove it here. 953 for (DenseMap<AnalysisID, Pass *> *IA : InheritedAnalysis) { 954 if (!IA) 955 continue; 956 957 for (DenseMap<AnalysisID, Pass *>::iterator I = IA->begin(), 958 E = IA->end(); 959 I != E;) { 960 DenseMap<AnalysisID, Pass *>::iterator Info = I++; 961 if (Info->second->getAsImmutablePass() == nullptr && 962 !is_contained(PreservedSet, Info->first)) { 963 // Remove this analysis 964 if (PassDebugging >= Details) { 965 Pass *S = Info->second; 966 dbgs() << " -- '" << P->getPassName() << "' is not preserving '"; 967 dbgs() << S->getPassName() << "'\n"; 968 } 969 IA->erase(Info); 970 } 971 } 972 } 973 } 974 975 /// Remove analysis passes that are not used any longer 976 void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg, 977 enum PassDebuggingString DBG_STR) { 978 979 SmallVector<Pass *, 12> DeadPasses; 980 981 // If this is a on the fly manager then it does not have TPM. 982 if (!TPM) 983 return; 984 985 TPM->collectLastUses(DeadPasses, P); 986 987 if (PassDebugging >= Details && !DeadPasses.empty()) { 988 dbgs() << " -*- '" << P->getPassName(); 989 dbgs() << "' is the last user of following pass instances."; 990 dbgs() << " Free these instances\n"; 991 } 992 993 for (Pass *P : DeadPasses) 994 freePass(P, Msg, DBG_STR); 995 } 996 997 void PMDataManager::freePass(Pass *P, StringRef Msg, 998 enum PassDebuggingString DBG_STR) { 999 dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg); 1000 1001 { 1002 // If the pass crashes releasing memory, remember this. 1003 PassManagerPrettyStackEntry X(P); 1004 TimeRegion PassTimer(getPassTimer(P)); 1005 1006 P->releaseMemory(); 1007 } 1008 1009 AnalysisID PI = P->getPassID(); 1010 if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) { 1011 // Remove the pass itself (if it is not already removed). 1012 AvailableAnalysis.erase(PI); 1013 1014 // Remove all interfaces this pass implements, for which it is also 1015 // listed as the available implementation. 1016 for (const PassInfo *PI : PInf->getInterfacesImplemented()) { 1017 DenseMap<AnalysisID, Pass *>::iterator Pos = 1018 AvailableAnalysis.find(PI->getTypeInfo()); 1019 if (Pos != AvailableAnalysis.end() && Pos->second == P) 1020 AvailableAnalysis.erase(Pos); 1021 } 1022 } 1023 } 1024 1025 /// Add pass P into the PassVector. Update 1026 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 1027 void PMDataManager::add(Pass *P, bool ProcessAnalysis) { 1028 // This manager is going to manage pass P. Set up analysis resolver 1029 // to connect them. 1030 AnalysisResolver *AR = new AnalysisResolver(*this); 1031 P->setResolver(AR); 1032 1033 // If a FunctionPass F is the last user of ModulePass info M 1034 // then the F's manager, not F, records itself as a last user of M. 1035 SmallVector<Pass *, 12> TransferLastUses; 1036 1037 if (!ProcessAnalysis) { 1038 // Add pass 1039 PassVector.push_back(P); 1040 return; 1041 } 1042 1043 // At the moment, this pass is the last user of all required passes. 1044 SmallVector<Pass *, 12> LastUses; 1045 SmallVector<Pass *, 8> UsedPasses; 1046 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable; 1047 1048 unsigned PDepth = this->getDepth(); 1049 1050 collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P); 1051 for (Pass *PUsed : UsedPasses) { 1052 unsigned RDepth = 0; 1053 1054 assert(PUsed->getResolver() && "Analysis Resolver is not set"); 1055 PMDataManager &DM = PUsed->getResolver()->getPMDataManager(); 1056 RDepth = DM.getDepth(); 1057 1058 if (PDepth == RDepth) 1059 LastUses.push_back(PUsed); 1060 else if (PDepth > RDepth) { 1061 // Let the parent claim responsibility of last use 1062 TransferLastUses.push_back(PUsed); 1063 // Keep track of higher level analysis used by this manager. 1064 HigherLevelAnalysis.push_back(PUsed); 1065 } else 1066 llvm_unreachable("Unable to accommodate Used Pass"); 1067 } 1068 1069 // Set P as P's last user until someone starts using P. 1070 // However, if P is a Pass Manager then it does not need 1071 // to record its last user. 1072 if (!P->getAsPMDataManager()) 1073 LastUses.push_back(P); 1074 TPM->setLastUser(LastUses, P); 1075 1076 if (!TransferLastUses.empty()) { 1077 Pass *My_PM = getAsPass(); 1078 TPM->setLastUser(TransferLastUses, My_PM); 1079 TransferLastUses.clear(); 1080 } 1081 1082 // Now, take care of required analyses that are not available. 1083 for (AnalysisID ID : ReqAnalysisNotAvailable) { 1084 const PassInfo *PI = TPM->findAnalysisPassInfo(ID); 1085 Pass *AnalysisPass = PI->createPass(); 1086 this->addLowerLevelRequiredPass(P, AnalysisPass); 1087 } 1088 1089 // Take a note of analysis required and made available by this pass. 1090 // Remove the analysis not preserved by this pass 1091 removeNotPreservedAnalysis(P); 1092 recordAvailableAnalysis(P); 1093 1094 // Add pass 1095 PassVector.push_back(P); 1096 } 1097 1098 1099 /// Populate UP with analysis pass that are used or required by 1100 /// pass P and are available. Populate RP_NotAvail with analysis 1101 /// pass that are required by pass P but are not available. 1102 void PMDataManager::collectRequiredAndUsedAnalyses( 1103 SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail, 1104 Pass *P) { 1105 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 1106 1107 for (const auto &UsedID : AnUsage->getUsedSet()) 1108 if (Pass *AnalysisPass = findAnalysisPass(UsedID, true)) 1109 UP.push_back(AnalysisPass); 1110 1111 for (const auto &RequiredID : AnUsage->getRequiredSet()) 1112 if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true)) 1113 UP.push_back(AnalysisPass); 1114 else 1115 RP_NotAvail.push_back(RequiredID); 1116 } 1117 1118 // All Required analyses should be available to the pass as it runs! Here 1119 // we fill in the AnalysisImpls member of the pass so that it can 1120 // successfully use the getAnalysis() method to retrieve the 1121 // implementations it needs. 1122 // 1123 void PMDataManager::initializeAnalysisImpl(Pass *P) { 1124 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 1125 1126 for (const AnalysisID ID : AnUsage->getRequiredSet()) { 1127 Pass *Impl = findAnalysisPass(ID, true); 1128 if (!Impl) 1129 // This may be analysis pass that is initialized on the fly. 1130 // If that is not the case then it will raise an assert when it is used. 1131 continue; 1132 AnalysisResolver *AR = P->getResolver(); 1133 assert(AR && "Analysis Resolver is not set"); 1134 AR->addAnalysisImplsPair(ID, Impl); 1135 } 1136 } 1137 1138 /// Find the pass that implements Analysis AID. If desired pass is not found 1139 /// then return NULL. 1140 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) { 1141 1142 // Check if AvailableAnalysis map has one entry. 1143 DenseMap<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID); 1144 1145 if (I != AvailableAnalysis.end()) 1146 return I->second; 1147 1148 // Search Parents through TopLevelManager 1149 if (SearchParent) 1150 return TPM->findAnalysisPass(AID); 1151 1152 return nullptr; 1153 } 1154 1155 // Print list of passes that are last used by P. 1156 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{ 1157 if (PassDebugging < Details) 1158 return; 1159 1160 SmallVector<Pass *, 12> LUses; 1161 1162 // If this is a on the fly manager then it does not have TPM. 1163 if (!TPM) 1164 return; 1165 1166 TPM->collectLastUses(LUses, P); 1167 1168 for (Pass *P : LUses) { 1169 dbgs() << "--" << std::string(Offset*2, ' '); 1170 P->dumpPassStructure(0); 1171 } 1172 } 1173 1174 void PMDataManager::dumpPassArguments() const { 1175 for (Pass *P : PassVector) { 1176 if (PMDataManager *PMD = P->getAsPMDataManager()) 1177 PMD->dumpPassArguments(); 1178 else 1179 if (const PassInfo *PI = 1180 TPM->findAnalysisPassInfo(P->getPassID())) 1181 if (!PI->isAnalysisGroup()) 1182 dbgs() << " -" << PI->getPassArgument(); 1183 } 1184 } 1185 1186 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1, 1187 enum PassDebuggingString S2, 1188 StringRef Msg) { 1189 if (PassDebugging < Executions) 1190 return; 1191 dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this 1192 << std::string(getDepth() * 2 + 1, ' '); 1193 switch (S1) { 1194 case EXECUTION_MSG: 1195 dbgs() << "Executing Pass '" << P->getPassName(); 1196 break; 1197 case MODIFICATION_MSG: 1198 dbgs() << "Made Modification '" << P->getPassName(); 1199 break; 1200 case FREEING_MSG: 1201 dbgs() << " Freeing Pass '" << P->getPassName(); 1202 break; 1203 default: 1204 break; 1205 } 1206 switch (S2) { 1207 case ON_FUNCTION_MSG: 1208 dbgs() << "' on Function '" << Msg << "'...\n"; 1209 break; 1210 case ON_MODULE_MSG: 1211 dbgs() << "' on Module '" << Msg << "'...\n"; 1212 break; 1213 case ON_REGION_MSG: 1214 dbgs() << "' on Region '" << Msg << "'...\n"; 1215 break; 1216 case ON_LOOP_MSG: 1217 dbgs() << "' on Loop '" << Msg << "'...\n"; 1218 break; 1219 case ON_CG_MSG: 1220 dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n"; 1221 break; 1222 default: 1223 break; 1224 } 1225 } 1226 1227 void PMDataManager::dumpRequiredSet(const Pass *P) const { 1228 if (PassDebugging < Details) 1229 return; 1230 1231 AnalysisUsage analysisUsage; 1232 P->getAnalysisUsage(analysisUsage); 1233 dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet()); 1234 } 1235 1236 void PMDataManager::dumpPreservedSet(const Pass *P) const { 1237 if (PassDebugging < Details) 1238 return; 1239 1240 AnalysisUsage analysisUsage; 1241 P->getAnalysisUsage(analysisUsage); 1242 dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet()); 1243 } 1244 1245 void PMDataManager::dumpUsedSet(const Pass *P) const { 1246 if (PassDebugging < Details) 1247 return; 1248 1249 AnalysisUsage analysisUsage; 1250 P->getAnalysisUsage(analysisUsage); 1251 dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet()); 1252 } 1253 1254 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P, 1255 const AnalysisUsage::VectorType &Set) const { 1256 assert(PassDebugging >= Details); 1257 if (Set.empty()) 1258 return; 1259 dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:"; 1260 for (unsigned i = 0; i != Set.size(); ++i) { 1261 if (i) dbgs() << ','; 1262 const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]); 1263 if (!PInf) { 1264 // Some preserved passes, such as AliasAnalysis, may not be initialized by 1265 // all drivers. 1266 dbgs() << " Uninitialized Pass"; 1267 continue; 1268 } 1269 dbgs() << ' ' << PInf->getPassName(); 1270 } 1271 dbgs() << '\n'; 1272 } 1273 1274 /// Add RequiredPass into list of lower level passes required by pass P. 1275 /// RequiredPass is run on the fly by Pass Manager when P requests it 1276 /// through getAnalysis interface. 1277 /// This should be handled by specific pass manager. 1278 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 1279 if (TPM) { 1280 TPM->dumpArguments(); 1281 TPM->dumpPasses(); 1282 } 1283 1284 // Module Level pass may required Function Level analysis info 1285 // (e.g. dominator info). Pass manager uses on the fly function pass manager 1286 // to provide this on demand. In that case, in Pass manager terminology, 1287 // module level pass is requiring lower level analysis info managed by 1288 // lower level pass manager. 1289 1290 // When Pass manager is not able to order required analysis info, Pass manager 1291 // checks whether any lower level manager will be able to provide this 1292 // analysis info on demand or not. 1293 #ifndef NDEBUG 1294 dbgs() << "Unable to schedule '" << RequiredPass->getPassName(); 1295 dbgs() << "' required by '" << P->getPassName() << "'\n"; 1296 #endif 1297 llvm_unreachable("Unable to schedule pass"); 1298 } 1299 1300 std::tuple<Pass *, bool> PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, 1301 Function &F) { 1302 llvm_unreachable("Unable to find on the fly pass"); 1303 } 1304 1305 // Destructor 1306 PMDataManager::~PMDataManager() { 1307 for (Pass *P : PassVector) 1308 delete P; 1309 } 1310 1311 //===----------------------------------------------------------------------===// 1312 // NOTE: Is this the right place to define this method ? 1313 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist. 1314 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID) const { 1315 return PM.findAnalysisPass(ID, true); 1316 } 1317 1318 std::tuple<Pass *, bool> 1319 AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI, Function &F) { 1320 return PM.getOnTheFlyPass(P, AnalysisPI, F); 1321 } 1322 1323 namespace llvm { 1324 namespace legacy { 1325 1326 //===----------------------------------------------------------------------===// 1327 // FunctionPassManager implementation 1328 1329 /// Create new Function pass manager 1330 FunctionPassManager::FunctionPassManager(Module *m) : M(m) { 1331 FPM = new legacy::FunctionPassManagerImpl(); 1332 // FPM is the top level manager. 1333 FPM->setTopLevelManager(FPM); 1334 1335 AnalysisResolver *AR = new AnalysisResolver(*FPM); 1336 FPM->setResolver(AR); 1337 } 1338 1339 FunctionPassManager::~FunctionPassManager() { 1340 delete FPM; 1341 } 1342 1343 void FunctionPassManager::add(Pass *P) { 1344 FPM->add(P); 1345 } 1346 1347 /// run - Execute all of the passes scheduled for execution. Keep 1348 /// track of whether any of the passes modifies the function, and if 1349 /// so, return true. 1350 /// 1351 bool FunctionPassManager::run(Function &F) { 1352 handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) { 1353 report_fatal_error(Twine("Error reading bitcode file: ") + EIB.message()); 1354 }); 1355 return FPM->run(F); 1356 } 1357 1358 1359 /// doInitialization - Run all of the initializers for the function passes. 1360 /// 1361 bool FunctionPassManager::doInitialization() { 1362 return FPM->doInitialization(*M); 1363 } 1364 1365 /// doFinalization - Run all of the finalizers for the function passes. 1366 /// 1367 bool FunctionPassManager::doFinalization() { 1368 return FPM->doFinalization(*M); 1369 } 1370 } // namespace legacy 1371 } // namespace llvm 1372 1373 /// cleanup - After running all passes, clean up pass manager cache. 1374 void FPPassManager::cleanup() { 1375 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1376 FunctionPass *FP = getContainedPass(Index); 1377 AnalysisResolver *AR = FP->getResolver(); 1378 assert(AR && "Analysis Resolver is not set"); 1379 AR->clearAnalysisImpls(); 1380 } 1381 } 1382 1383 1384 //===----------------------------------------------------------------------===// 1385 // FPPassManager implementation 1386 1387 char FPPassManager::ID = 0; 1388 /// Print passes managed by this manager 1389 void FPPassManager::dumpPassStructure(unsigned Offset) { 1390 dbgs().indent(Offset*2) << "FunctionPass Manager\n"; 1391 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1392 FunctionPass *FP = getContainedPass(Index); 1393 FP->dumpPassStructure(Offset + 1); 1394 dumpLastUses(FP, Offset+1); 1395 } 1396 } 1397 1398 /// Execute all of the passes scheduled for execution by invoking 1399 /// runOnFunction method. Keep track of whether any of the passes modifies 1400 /// the function, and if so, return true. 1401 bool FPPassManager::runOnFunction(Function &F) { 1402 if (F.isDeclaration()) 1403 return false; 1404 1405 bool Changed = false; 1406 Module &M = *F.getParent(); 1407 // Collect inherited analysis from Module level pass manager. 1408 populateInheritedAnalysis(TPM->activeStack); 1409 1410 unsigned InstrCount, FunctionSize = 0; 1411 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; 1412 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); 1413 // Collect the initial size of the module. 1414 if (EmitICRemark) { 1415 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); 1416 FunctionSize = F.getInstructionCount(); 1417 } 1418 1419 // Store name outside of loop to avoid redundant calls. 1420 const StringRef Name = F.getName(); 1421 llvm::TimeTraceScope FunctionScope("OptFunction", Name); 1422 1423 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1424 FunctionPass *FP = getContainedPass(Index); 1425 bool LocalChanged = false; 1426 1427 // Call getPassName only when required. The call itself is fairly cheap, but 1428 // still virtual and repeated calling adds unnecessary overhead. 1429 llvm::TimeTraceScope PassScope( 1430 "RunPass", [FP]() { return std::string(FP->getPassName()); }); 1431 1432 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, Name); 1433 dumpRequiredSet(FP); 1434 1435 initializeAnalysisImpl(FP); 1436 1437 { 1438 PassManagerPrettyStackEntry X(FP, F); 1439 TimeRegion PassTimer(getPassTimer(FP)); 1440 #ifdef EXPENSIVE_CHECKS 1441 uint64_t RefHash = FP->structuralHash(F); 1442 #endif 1443 LocalChanged |= FP->runOnFunction(F); 1444 1445 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG) 1446 if (!LocalChanged && (RefHash != FP->structuralHash(F))) { 1447 llvm::errs() << "Pass modifies its input and doesn't report it: " 1448 << FP->getPassName() << "\n"; 1449 llvm_unreachable("Pass modifies its input and doesn't report it"); 1450 } 1451 #endif 1452 1453 if (EmitICRemark) { 1454 unsigned NewSize = F.getInstructionCount(); 1455 1456 // Update the size of the function, emit a remark, and update the size 1457 // of the module. 1458 if (NewSize != FunctionSize) { 1459 int64_t Delta = static_cast<int64_t>(NewSize) - 1460 static_cast<int64_t>(FunctionSize); 1461 emitInstrCountChangedRemark(FP, M, Delta, InstrCount, 1462 FunctionToInstrCount, &F); 1463 InstrCount = static_cast<int64_t>(InstrCount) + Delta; 1464 FunctionSize = NewSize; 1465 } 1466 } 1467 } 1468 1469 Changed |= LocalChanged; 1470 if (LocalChanged) 1471 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, Name); 1472 dumpPreservedSet(FP); 1473 dumpUsedSet(FP); 1474 1475 verifyPreservedAnalysis(FP); 1476 if (LocalChanged) 1477 removeNotPreservedAnalysis(FP); 1478 recordAvailableAnalysis(FP); 1479 removeDeadPasses(FP, Name, ON_FUNCTION_MSG); 1480 } 1481 1482 return Changed; 1483 } 1484 1485 bool FPPassManager::runOnModule(Module &M) { 1486 bool Changed = false; 1487 1488 for (Function &F : M) 1489 Changed |= runOnFunction(F); 1490 1491 return Changed; 1492 } 1493 1494 bool FPPassManager::doInitialization(Module &M) { 1495 bool Changed = false; 1496 1497 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 1498 Changed |= getContainedPass(Index)->doInitialization(M); 1499 1500 return Changed; 1501 } 1502 1503 bool FPPassManager::doFinalization(Module &M) { 1504 bool Changed = false; 1505 1506 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index) 1507 Changed |= getContainedPass(Index)->doFinalization(M); 1508 1509 return Changed; 1510 } 1511 1512 //===----------------------------------------------------------------------===// 1513 // MPPassManager implementation 1514 1515 /// Execute all of the passes scheduled for execution by invoking 1516 /// runOnModule method. Keep track of whether any of the passes modifies 1517 /// the module, and if so, return true. 1518 bool 1519 MPPassManager::runOnModule(Module &M) { 1520 llvm::TimeTraceScope TimeScope("OptModule", M.getName()); 1521 1522 bool Changed = false; 1523 1524 // Initialize on-the-fly passes 1525 for (auto &OnTheFlyManager : OnTheFlyManagers) { 1526 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 1527 Changed |= FPP->doInitialization(M); 1528 } 1529 1530 // Initialize module passes 1531 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 1532 Changed |= getContainedPass(Index)->doInitialization(M); 1533 1534 unsigned InstrCount; 1535 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; 1536 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); 1537 // Collect the initial size of the module. 1538 if (EmitICRemark) 1539 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); 1540 1541 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1542 ModulePass *MP = getContainedPass(Index); 1543 bool LocalChanged = false; 1544 1545 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier()); 1546 dumpRequiredSet(MP); 1547 1548 initializeAnalysisImpl(MP); 1549 1550 { 1551 PassManagerPrettyStackEntry X(MP, M); 1552 TimeRegion PassTimer(getPassTimer(MP)); 1553 1554 #ifdef EXPENSIVE_CHECKS 1555 uint64_t RefHash = MP->structuralHash(M); 1556 #endif 1557 1558 LocalChanged |= MP->runOnModule(M); 1559 1560 #ifdef EXPENSIVE_CHECKS 1561 assert((LocalChanged || (RefHash == MP->structuralHash(M))) && 1562 "Pass modifies its input and doesn't report it."); 1563 #endif 1564 1565 if (EmitICRemark) { 1566 // Update the size of the module. 1567 unsigned ModuleCount = M.getInstructionCount(); 1568 if (ModuleCount != InstrCount) { 1569 int64_t Delta = static_cast<int64_t>(ModuleCount) - 1570 static_cast<int64_t>(InstrCount); 1571 emitInstrCountChangedRemark(MP, M, Delta, InstrCount, 1572 FunctionToInstrCount); 1573 InstrCount = ModuleCount; 1574 } 1575 } 1576 } 1577 1578 Changed |= LocalChanged; 1579 if (LocalChanged) 1580 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG, 1581 M.getModuleIdentifier()); 1582 dumpPreservedSet(MP); 1583 dumpUsedSet(MP); 1584 1585 verifyPreservedAnalysis(MP); 1586 if (LocalChanged) 1587 removeNotPreservedAnalysis(MP); 1588 recordAvailableAnalysis(MP); 1589 removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG); 1590 } 1591 1592 // Finalize module passes 1593 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index) 1594 Changed |= getContainedPass(Index)->doFinalization(M); 1595 1596 // Finalize on-the-fly passes 1597 for (auto &OnTheFlyManager : OnTheFlyManagers) { 1598 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 1599 // We don't know when is the last time an on-the-fly pass is run, 1600 // so we need to releaseMemory / finalize here 1601 FPP->releaseMemoryOnTheFly(); 1602 Changed |= FPP->doFinalization(M); 1603 } 1604 1605 return Changed; 1606 } 1607 1608 /// Add RequiredPass into list of lower level passes required by pass P. 1609 /// RequiredPass is run on the fly by Pass Manager when P requests it 1610 /// through getAnalysis interface. 1611 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 1612 assert(RequiredPass && "No required pass?"); 1613 assert(P->getPotentialPassManagerType() == PMT_ModulePassManager && 1614 "Unable to handle Pass that requires lower level Analysis pass"); 1615 assert((P->getPotentialPassManagerType() < 1616 RequiredPass->getPotentialPassManagerType()) && 1617 "Unable to handle Pass that requires lower level Analysis pass"); 1618 1619 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[P]; 1620 if (!FPP) { 1621 FPP = new legacy::FunctionPassManagerImpl(); 1622 // FPP is the top level manager. 1623 FPP->setTopLevelManager(FPP); 1624 1625 OnTheFlyManagers[P] = FPP; 1626 } 1627 const PassInfo *RequiredPassPI = 1628 TPM->findAnalysisPassInfo(RequiredPass->getPassID()); 1629 1630 Pass *FoundPass = nullptr; 1631 if (RequiredPassPI && RequiredPassPI->isAnalysis()) { 1632 FoundPass = 1633 ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID()); 1634 } 1635 if (!FoundPass) { 1636 FoundPass = RequiredPass; 1637 // This should be guaranteed to add RequiredPass to the passmanager given 1638 // that we checked for an available analysis above. 1639 FPP->add(RequiredPass); 1640 } 1641 // Register P as the last user of FoundPass or RequiredPass. 1642 SmallVector<Pass *, 1> LU; 1643 LU.push_back(FoundPass); 1644 FPP->setLastUser(LU, P); 1645 } 1646 1647 /// Return function pass corresponding to PassInfo PI, that is 1648 /// required by module pass MP. Instantiate analysis pass, by using 1649 /// its runOnFunction() for function F. 1650 std::tuple<Pass *, bool> MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, 1651 Function &F) { 1652 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP]; 1653 assert(FPP && "Unable to find on the fly pass"); 1654 1655 FPP->releaseMemoryOnTheFly(); 1656 bool Changed = FPP->run(F); 1657 return std::make_tuple(((PMTopLevelManager *)FPP)->findAnalysisPass(PI), 1658 Changed); 1659 } 1660 1661 namespace llvm { 1662 namespace legacy { 1663 1664 //===----------------------------------------------------------------------===// 1665 // PassManager implementation 1666 1667 /// Create new pass manager 1668 PassManager::PassManager() { 1669 PM = new PassManagerImpl(); 1670 // PM is the top level manager 1671 PM->setTopLevelManager(PM); 1672 } 1673 1674 PassManager::~PassManager() { 1675 delete PM; 1676 } 1677 1678 void PassManager::add(Pass *P) { 1679 PM->add(P); 1680 } 1681 1682 /// run - Execute all of the passes scheduled for execution. Keep track of 1683 /// whether any of the passes modifies the module, and if so, return true. 1684 bool PassManager::run(Module &M) { 1685 return PM->run(M); 1686 } 1687 } // namespace legacy 1688 } // namespace llvm 1689 1690 //===----------------------------------------------------------------------===// 1691 // PMStack implementation 1692 // 1693 1694 // Pop Pass Manager from the stack and clear its analysis info. 1695 void PMStack::pop() { 1696 1697 PMDataManager *Top = this->top(); 1698 Top->initializeAnalysisInfo(); 1699 1700 S.pop_back(); 1701 } 1702 1703 // Push PM on the stack and set its top level manager. 1704 void PMStack::push(PMDataManager *PM) { 1705 assert(PM && "Unable to push. Pass Manager expected"); 1706 assert(PM->getDepth()==0 && "Pass Manager depth set too early"); 1707 1708 if (!this->empty()) { 1709 assert(PM->getPassManagerType() > this->top()->getPassManagerType() 1710 && "pushing bad pass manager to PMStack"); 1711 PMTopLevelManager *TPM = this->top()->getTopLevelManager(); 1712 1713 assert(TPM && "Unable to find top level manager"); 1714 TPM->addIndirectPassManager(PM); 1715 PM->setTopLevelManager(TPM); 1716 PM->setDepth(this->top()->getDepth()+1); 1717 } else { 1718 assert((PM->getPassManagerType() == PMT_ModulePassManager 1719 || PM->getPassManagerType() == PMT_FunctionPassManager) 1720 && "pushing bad pass manager to PMStack"); 1721 PM->setDepth(1); 1722 } 1723 1724 S.push_back(PM); 1725 } 1726 1727 // Dump content of the pass manager stack. 1728 LLVM_DUMP_METHOD void PMStack::dump() const { 1729 for (PMDataManager *Manager : S) 1730 dbgs() << Manager->getAsPass()->getPassName() << ' '; 1731 1732 if (!S.empty()) 1733 dbgs() << '\n'; 1734 } 1735 1736 /// Find appropriate Module Pass Manager in the PM Stack and 1737 /// add self into that manager. 1738 void ModulePass::assignPassManager(PMStack &PMS, 1739 PassManagerType PreferredType) { 1740 // Find Module Pass Manager 1741 PassManagerType T; 1742 while ((T = PMS.top()->getPassManagerType()) > PMT_ModulePassManager && 1743 T != PreferredType) 1744 PMS.pop(); 1745 PMS.top()->add(this); 1746 } 1747 1748 /// Find appropriate Function Pass Manager or Call Graph Pass Manager 1749 /// in the PM Stack and add self into that manager. 1750 void FunctionPass::assignPassManager(PMStack &PMS, 1751 PassManagerType /*PreferredType*/) { 1752 // Find Function Pass Manager 1753 PMDataManager *PM; 1754 while (PM = PMS.top(), PM->getPassManagerType() > PMT_FunctionPassManager) 1755 PMS.pop(); 1756 1757 // Create new Function Pass Manager if needed. 1758 if (PM->getPassManagerType() != PMT_FunctionPassManager) { 1759 // [1] Create new Function Pass Manager 1760 auto *FPP = new FPPassManager; 1761 FPP->populateInheritedAnalysis(PMS); 1762 1763 // [2] Set up new manager's top level manager 1764 PM->getTopLevelManager()->addIndirectPassManager(FPP); 1765 1766 // [3] Assign manager to manage this new manager. This may create 1767 // and push new managers into PMS 1768 FPP->assignPassManager(PMS, PM->getPassManagerType()); 1769 1770 // [4] Push new manager into PMS 1771 PMS.push(FPP); 1772 PM = FPP; 1773 } 1774 1775 // Assign FPP as the manager of this pass. 1776 PM->add(this); 1777 } 1778 1779 legacy::PassManagerBase::~PassManagerBase() = default; 1780