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