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