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