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