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