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