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