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