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