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