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