PassManager.cpp revision 7e601a70fcaf0a3090368425bbb339aab038d3e3
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/Module.h" 17#include "llvm/ModuleProvider.h" 18#include "llvm/Support/Streams.h" 19#include <vector> 20#include <map> 21using namespace llvm; 22 23//===----------------------------------------------------------------------===// 24// Overview: 25// The Pass Manager Infrastructure manages passes. It's responsibilities are: 26// 27// o Manage optimization pass execution order 28// o Make required Analysis information available before pass P is run 29// o Release memory occupied by dead passes 30// o If Analysis information is dirtied by a pass then regenerate Analysis 31// information before it is consumed by another pass. 32// 33// Pass Manager Infrastructure uses multipe pass managers. They are PassManager, 34// FunctionPassManager, ModulePassManager, BasicBlockPassManager. This class 35// hierarcy uses multiple inheritance but pass managers do not derive from 36// another pass manager. 37// 38// PassManager and FunctionPassManager are two top level pass manager that 39// represents the external interface of this entire pass manager infrastucture. 40// 41// Important classes : 42// 43// [o] class PMTopLevelManager; 44// 45// Two top level managers, PassManager and FunctionPassManager, derive from 46// PMTopLevelManager. PMTopLevelManager manages information used by top level 47// managers such as last user info. 48// 49// [o] class PMDataManager; 50// 51// PMDataManager manages information, e.g. list of available analysis info, 52// used by a pass manager to manage execution order of passes. It also provides 53// a place to implement common pass manager APIs. All pass managers derive from 54// PMDataManager. 55// 56// [o] class BasicBlockPassManager : public FunctionPass, public PMDataManager; 57// 58// BasicBlockPassManager manages BasicBlockPasses. 59// 60// [o] class FunctionPassManager; 61// 62// This is a external interface used by JIT to manage FunctionPasses. This 63// interface relies on FunctionPassManagerImpl to do all the tasks. 64// 65// [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager, 66// public PMTopLevelManager; 67// 68// FunctionPassManagerImpl is a top level manager. It manages FunctionPasses 69// and BasicBlockPassManagers. 70// 71// [o] class ModulePassManager : public Pass, public PMDataManager; 72// 73// ModulePassManager manages ModulePasses and FunctionPassManagerImpls. 74// 75// [o] class PassManager; 76// 77// This is a external interface used by various tools to manages passes. It 78// relies on PassManagerImpl to do all the tasks. 79// 80// [o] class PassManagerImpl : public Pass, public PMDataManager, 81// public PMDTopLevelManager 82// 83// PassManagerImpl is a top level pass manager responsible for managing 84// ModulePassManagers. 85//===----------------------------------------------------------------------===// 86 87namespace llvm { 88 89class PMDataManager; 90 91//===----------------------------------------------------------------------===// 92// PMTopLevelManager 93// 94/// PMTopLevelManager manages LastUser info and collects common APIs used by 95/// top level pass managers. 96class PMTopLevelManager { 97 98public: 99 100 inline std::vector<Pass *>::iterator passManagersBegin() { 101 return PassManagers.begin(); 102 } 103 104 inline std::vector<Pass *>::iterator passManagersEnd() { 105 return PassManagers.end(); 106 } 107 108 /// Schedule pass P for execution. Make sure that passes required by 109 /// P are run before P is run. Update analysis info maintained by 110 /// the manager. Remove dead passes. This is a recursive function. 111 void schedulePass(Pass *P); 112 113 /// This is implemented by top level pass manager and used by 114 /// schedulePass() to add analysis info passes that are not available. 115 virtual void addTopLevelPass(Pass *P) = 0; 116 117 /// Set pass P as the last user of the given analysis passes. 118 void setLastUser(std::vector<Pass *> &AnalysisPasses, Pass *P); 119 120 /// Collect passes whose last user is P 121 void collectLastUses(std::vector<Pass *> &LastUses, Pass *P); 122 123 /// Find the pass that implements Analysis AID. Search immutable 124 /// passes and all pass managers. If desired pass is not found 125 /// then return NULL. 126 Pass *findAnalysisPass(AnalysisID AID); 127 128 virtual ~PMTopLevelManager() { 129 PassManagers.clear(); 130 } 131 132 /// Add immutable pass and initialize it. 133 inline void addImmutablePass(ImmutablePass *P) { 134 P->initializePass(); 135 ImmutablePasses.push_back(P); 136 } 137 138 inline std::vector<ImmutablePass *>& getImmutablePasses() { 139 return ImmutablePasses; 140 } 141 142 void addPassManager(Pass *Manager) { 143 PassManagers.push_back(Manager); 144 } 145 146 // Add Manager into the list of managers that are not directly 147 // maintained by this top level pass manager 148 inline void addIndirectPassManager(PMDataManager *Manager) { 149 IndirectPassManagers.push_back(Manager); 150 } 151 152private: 153 154 /// Collection of pass managers 155 std::vector<Pass *> PassManagers; 156 157 /// Collection of pass managers that are not directly maintained 158 /// by this pass manager 159 std::vector<PMDataManager *> IndirectPassManagers; 160 161 // Map to keep track of last user of the analysis pass. 162 // LastUser->second is the last user of Lastuser->first. 163 std::map<Pass *, Pass *> LastUser; 164 165 /// Immutable passes are managed by top level manager. 166 std::vector<ImmutablePass *> ImmutablePasses; 167}; 168 169//===----------------------------------------------------------------------===// 170// PMDataManager 171 172/// PMDataManager provides the common place to manage the analysis data 173/// used by pass managers. 174class PMDataManager { 175 176public: 177 178 PMDataManager(int D) : TPM(NULL), Depth(D) { 179 initializeAnalysisInfo(); 180 } 181 182 /// Return true IFF pass P's required analysis set does not required new 183 /// manager. 184 bool manageablePass(Pass *P); 185 186 /// Augment AvailableAnalysis by adding analysis made available by pass P. 187 void recordAvailableAnalysis(Pass *P); 188 189 /// Remove Analysis that is not preserved by the pass 190 void removeNotPreservedAnalysis(Pass *P); 191 192 /// Remove dead passes 193 void removeDeadPasses(Pass *P); 194 195 /// Add pass P into the PassVector. Update 196 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 197 void addPassToManager (Pass *P, bool ProcessAnalysis = true); 198 199 /// Initialize available analysis information. 200 void initializeAnalysisInfo() { 201 ForcedLastUses.clear(); 202 AvailableAnalysis.clear(); 203 204 // Include immutable passes into AvailableAnalysis vector. 205 std::vector<ImmutablePass *> &ImmutablePasses = TPM->getImmutablePasses(); 206 for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(), 207 E = ImmutablePasses.end(); I != E; ++I) 208 recordAvailableAnalysis(*I); 209 } 210 211 /// Populate RequiredPasses with the analysis pass that are required by 212 /// pass P. 213 void collectRequiredAnalysisPasses(std::vector<Pass *> &RequiredPasses, 214 Pass *P); 215 216 /// All Required analyses should be available to the pass as it runs! Here 217 /// we fill in the AnalysisImpls member of the pass so that it can 218 /// successfully use the getAnalysis() method to retrieve the 219 /// implementations it needs. 220 void initializeAnalysisImpl(Pass *P); 221 222 /// Find the pass that implements Analysis AID. If desired pass is not found 223 /// then return NULL. 224 Pass *findAnalysisPass(AnalysisID AID, bool Direction); 225 226 inline std::vector<Pass *>::iterator passVectorBegin() { 227 return PassVector.begin(); 228 } 229 230 inline std::vector<Pass *>::iterator passVectorEnd() { 231 return PassVector.end(); 232 } 233 234 // Access toplevel manager 235 PMTopLevelManager *getTopLevelManager() { return TPM; } 236 void setTopLevelManager(PMTopLevelManager *T) { TPM = T; } 237 238 unsigned getDepth() { return Depth; } 239 240protected: 241 242 // Collection of pass whose last user asked this manager to claim 243 // last use. If a FunctionPass F is the last user of ModulePass info M 244 // then the F's manager, not F, records itself as a last user of M. 245 std::vector<Pass *> ForcedLastUses; 246 247 // Top level manager. 248 PMTopLevelManager *TPM; 249 250private: 251 // Set of available Analysis. This information is used while scheduling 252 // pass. If a pass requires an analysis which is not not available then 253 // equired analysis pass is scheduled to run before the pass itself is 254 // scheduled to run. 255 std::map<AnalysisID, Pass*> AvailableAnalysis; 256 257 // Collection of pass that are managed by this manager 258 std::vector<Pass *> PassVector; 259 260 unsigned Depth; 261}; 262 263//===----------------------------------------------------------------------===// 264// BasicBlockPassManager_New 265// 266/// BasicBlockPassManager_New manages BasicBlockPass. It batches all the 267/// pass together and sequence them to process one basic block before 268/// processing next basic block. 269class BasicBlockPassManager_New : public PMDataManager, 270 public FunctionPass { 271 272public: 273 BasicBlockPassManager_New(int D) : PMDataManager(D) { } 274 275 /// Add a pass into a passmanager queue. 276 bool addPass(Pass *p); 277 278 /// Execute all of the passes scheduled for execution. Keep track of 279 /// whether any of the passes modifies the function, and if so, return true. 280 bool runOnFunction(Function &F); 281 282 /// Pass Manager itself does not invalidate any analysis info. 283 void getAnalysisUsage(AnalysisUsage &Info) const { 284 Info.setPreservesAll(); 285 } 286 287 bool doInitialization(Module &M); 288 bool doInitialization(Function &F); 289 bool doFinalization(Module &M); 290 bool doFinalization(Function &F); 291 292}; 293 294//===----------------------------------------------------------------------===// 295// FunctionPassManagerImpl_New 296// 297/// FunctionPassManagerImpl_New manages FunctionPasses and BasicBlockPassManagers. 298/// It batches all function passes and basic block pass managers together and 299/// sequence them to process one function at a time before processing next 300/// function. 301class FunctionPassManagerImpl_New : public ModulePass, 302 public PMDataManager, 303 public PMTopLevelManager { 304public: 305 FunctionPassManagerImpl_New(ModuleProvider *P, int D) : 306 PMDataManager(D) { /* TODO */ } 307 FunctionPassManagerImpl_New(int D) : PMDataManager(D) { 308 activeBBPassManager = NULL; 309 } 310 ~FunctionPassManagerImpl_New() { /* TODO */ }; 311 312 inline void addTopLevelPass(Pass *P) { 313 314 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 315 316 // P is a immutable pass then it will be managed by this 317 // top level manager. Set up analysis resolver to connect them. 318 AnalysisResolver_New *AR = new AnalysisResolver_New(*this); 319 P->setResolver(AR); 320 initializeAnalysisImpl(P); 321 addImmutablePass(IP); 322 recordAvailableAnalysis(IP); 323 } 324 else 325 addPass(P); 326 } 327 328 /// add - Add a pass to the queue of passes to run. This passes 329 /// ownership of the Pass to the PassManager. When the 330 /// PassManager_X is destroyed, the pass will be destroyed as well, so 331 /// there is no need to delete the pass. (TODO delete passes.) 332 /// This implies that all passes MUST be allocated with 'new'. 333 void add(Pass *P) { 334 schedulePass(P); 335 } 336 337 /// Add pass into the pass manager queue. 338 bool addPass(Pass *P); 339 340 /// Execute all of the passes scheduled for execution. Keep 341 /// track of whether any of the passes modifies the function, and if 342 /// so, return true. 343 bool runOnModule(Module &M); 344 bool runOnFunction(Function &F); 345 bool run(Function &F); 346 347 /// doInitialization - Run all of the initializers for the function passes. 348 /// 349 bool doInitialization(Module &M); 350 351 /// doFinalization - Run all of the initializers for the function passes. 352 /// 353 bool doFinalization(Module &M); 354 355 /// Pass Manager itself does not invalidate any analysis info. 356 void getAnalysisUsage(AnalysisUsage &Info) const { 357 Info.setPreservesAll(); 358 } 359 360private: 361 // Active Pass Managers 362 BasicBlockPassManager_New *activeBBPassManager; 363}; 364 365//===----------------------------------------------------------------------===// 366// ModulePassManager_New 367// 368/// ModulePassManager_New manages ModulePasses and function pass managers. 369/// It batches all Module passes passes and function pass managers together and 370/// sequence them to process one module. 371class ModulePassManager_New : public Pass, 372 public PMDataManager { 373 374public: 375 ModulePassManager_New(int D) : PMDataManager(D) { 376 activeFunctionPassManager = NULL; 377 } 378 379 /// Add a pass into a passmanager queue. 380 bool addPass(Pass *p); 381 382 /// run - Execute all of the passes scheduled for execution. Keep track of 383 /// whether any of the passes modifies the module, and if so, return true. 384 bool runOnModule(Module &M); 385 386 /// Pass Manager itself does not invalidate any analysis info. 387 void getAnalysisUsage(AnalysisUsage &Info) const { 388 Info.setPreservesAll(); 389 } 390 391private: 392 // Active Pass Manager 393 FunctionPassManagerImpl_New *activeFunctionPassManager; 394}; 395 396//===----------------------------------------------------------------------===// 397// PassManagerImpl_New 398// 399/// PassManagerImpl_New manages ModulePassManagers 400class PassManagerImpl_New : public Pass, 401 public PMDataManager, 402 public PMTopLevelManager { 403 404public: 405 406 PassManagerImpl_New(int D) : PMDataManager(D) {} 407 408 /// add - Add a pass to the queue of passes to run. This passes ownership of 409 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 410 /// will be destroyed as well, so there is no need to delete the pass. This 411 /// implies that all passes MUST be allocated with 'new'. 412 void add(Pass *P) { 413 schedulePass(P); 414 } 415 416 /// run - Execute all of the passes scheduled for execution. Keep track of 417 /// whether any of the passes modifies the module, and if so, return true. 418 bool run(Module &M); 419 420 /// Pass Manager itself does not invalidate any analysis info. 421 void getAnalysisUsage(AnalysisUsage &Info) const { 422 Info.setPreservesAll(); 423 } 424 425 inline void addTopLevelPass(Pass *P) { 426 427 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 428 429 // P is a immutable pass and it will be managed by this 430 // top level manager. Set up analysis resolver to connect them. 431 AnalysisResolver_New *AR = new AnalysisResolver_New(*this); 432 P->setResolver(AR); 433 initializeAnalysisImpl(P); 434 addImmutablePass(IP); 435 recordAvailableAnalysis(IP); 436 } 437 else 438 addPass(P); 439 } 440 441private: 442 443 /// Add a pass into a passmanager queue. 444 bool addPass(Pass *p); 445 446 // Active Pass Manager 447 ModulePassManager_New *activeManager; 448}; 449 450} // End of llvm namespace 451 452//===----------------------------------------------------------------------===// 453// PMTopLevelManager implementation 454 455/// Set pass P as the last user of the given analysis passes. 456void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses, 457 Pass *P) { 458 459 for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(), 460 E = AnalysisPasses.end(); I != E; ++I) { 461 Pass *AP = *I; 462 LastUser[AP] = P; 463 // If AP is the last user of other passes then make P last user of 464 // such passes. 465 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(), 466 LUE = LastUser.end(); LUI != LUE; ++LUI) { 467 if (LUI->second == AP) 468 LastUser[LUI->first] = P; 469 } 470 } 471 472} 473 474/// Collect passes whose last user is P 475void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses, 476 Pass *P) { 477 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(), 478 LUE = LastUser.end(); LUI != LUE; ++LUI) 479 if (LUI->second == P) 480 LastUses.push_back(LUI->first); 481} 482 483/// Schedule pass P for execution. Make sure that passes required by 484/// P are run before P is run. Update analysis info maintained by 485/// the manager. Remove dead passes. This is a recursive function. 486void PMTopLevelManager::schedulePass(Pass *P) { 487 488 // TODO : Allocate function manager for this pass, other wise required set 489 // may be inserted into previous function manager 490 491 AnalysisUsage AnUsage; 492 P->getAnalysisUsage(AnUsage); 493 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 494 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(), 495 E = RequiredSet.end(); I != E; ++I) { 496 497 Pass *AnalysisPass = findAnalysisPass(*I); 498 if (!AnalysisPass) { 499 // Schedule this analysis run first. 500 AnalysisPass = (*I)->createPass(); 501 schedulePass(AnalysisPass); 502 } 503 } 504 505 // Now all required passes are available. 506 addTopLevelPass(P); 507} 508 509/// Find the pass that implements Analysis AID. Search immutable 510/// passes and all pass managers. If desired pass is not found 511/// then return NULL. 512Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) { 513 514 Pass *P = NULL; 515 for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(), 516 E = ImmutablePasses.end(); P == NULL && I != E; ++I) { 517 const PassInfo *PI = (*I)->getPassInfo(); 518 if (PI == AID) 519 P = *I; 520 521 // If Pass not found then check the interfaces implemented by Immutable Pass 522 if (!P) { 523 const std::vector<const PassInfo*> &ImmPI = 524 PI->getInterfacesImplemented(); 525 for (unsigned Index = 0, End = ImmPI.size(); 526 P == NULL && Index != End; ++Index) 527 if (ImmPI[Index] == AID) 528 P = *I; 529 } 530 } 531 532 // Check pass managers 533 for (std::vector<Pass *>::iterator I = PassManagers.begin(), 534 E = PassManagers.end(); P == NULL && I != E; ++I) { 535 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I); 536 assert(PMD && "This is not a PassManager"); 537 P = PMD->findAnalysisPass(AID, false); 538 } 539 540 // Check other pass managers 541 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(), 542 E = IndirectPassManagers.end(); P == NULL && I != E; ++I) 543 P = (*I)->findAnalysisPass(AID, false); 544 545 return P; 546} 547 548//===----------------------------------------------------------------------===// 549// PMDataManager implementation 550 551/// Return true IFF pass P's required analysis set does not required new 552/// manager. 553bool PMDataManager::manageablePass(Pass *P) { 554 555 // TODO 556 // If this pass is not preserving information that is required by a 557 // pass maintained by higher level pass manager then do not insert 558 // this pass into current manager. Use new manager. For example, 559 // For example, If FunctionPass F is not preserving ModulePass Info M1 560 // that is used by another ModulePass M2 then do not insert F in 561 // current function pass manager. 562 return true; 563} 564 565/// Augement AvailableAnalysis by adding analysis made available by pass P. 566void PMDataManager::recordAvailableAnalysis(Pass *P) { 567 568 if (const PassInfo *PI = P->getPassInfo()) { 569 AvailableAnalysis[PI] = P; 570 571 //This pass is the current implementation of all of the interfaces it 572 //implements as well. 573 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 574 for (unsigned i = 0, e = II.size(); i != e; ++i) 575 AvailableAnalysis[II[i]] = P; 576 } 577} 578 579/// Remove Analyss not preserved by Pass P 580void PMDataManager::removeNotPreservedAnalysis(Pass *P) { 581 AnalysisUsage AnUsage; 582 P->getAnalysisUsage(AnUsage); 583 584 if (AnUsage.getPreservesAll()) 585 return; 586 587 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 588 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(), 589 E = AvailableAnalysis.end(); I != E; ++I ) { 590 if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) == 591 PreservedSet.end()) { 592 // Remove this analysis 593 std::map<AnalysisID, Pass*>::iterator J = I++; 594 AvailableAnalysis.erase(J); 595 } 596 } 597} 598 599/// Remove analysis passes that are not used any longer 600void PMDataManager::removeDeadPasses(Pass *P) { 601 602 std::vector<Pass *> DeadPasses; 603 TPM->collectLastUses(DeadPasses, P); 604 605 for (std::vector<Pass *>::iterator I = DeadPasses.begin(), 606 E = DeadPasses.end(); I != E; ++I) { 607 (*I)->releaseMemory(); 608 609 std::map<AnalysisID, Pass*>::iterator Pos = 610 AvailableAnalysis.find((*I)->getPassInfo()); 611 612 // It is possible that pass is already removed from the AvailableAnalysis 613 if (Pos != AvailableAnalysis.end()) 614 AvailableAnalysis.erase(Pos); 615 } 616} 617 618/// Add pass P into the PassVector. Update 619/// AvailableAnalysis appropriately if ProcessAnalysis is true. 620void PMDataManager::addPassToManager(Pass *P, 621 bool ProcessAnalysis) { 622 623 // This manager is going to manage pass P. Set up analysis resolver 624 // to connect them. 625 AnalysisResolver_New *AR = new AnalysisResolver_New(*this); 626 P->setResolver(AR); 627 628 if (ProcessAnalysis) { 629 630 // At the moment, this pass is the last user of all required passes. 631 std::vector<Pass *> LastUses; 632 std::vector<Pass *> RequiredPasses; 633 unsigned PDepth = this->getDepth(); 634 635 collectRequiredAnalysisPasses(RequiredPasses, P); 636 for (std::vector<Pass *>::iterator I = RequiredPasses.begin(), 637 E = RequiredPasses.end(); I != E; ++I) { 638 Pass *PRequired = *I; 639 unsigned RDepth = 0; 640 641 PMDataManager &DM = PRequired->getResolver()->getPMDataManager(); 642 RDepth = DM.getDepth(); 643 644 if (PDepth == RDepth) 645 LastUses.push_back(PRequired); 646 else if (PDepth > RDepth) { 647 // Let the parent claim responsibility of last use 648 ForcedLastUses.push_back(PRequired); 649 } else { 650 // Note : This feature is not yet implemented 651 assert (0 && 652 "Unable to handle Pass that requires lower level Analysis pass"); 653 } 654 } 655 656 if (!LastUses.empty()) 657 TPM->setLastUser(LastUses, P); 658 659 // Take a note of analysis required and made available by this pass. 660 // Remove the analysis not preserved by this pass 661 removeNotPreservedAnalysis(P); 662 recordAvailableAnalysis(P); 663 } 664 665 // Add pass 666 PassVector.push_back(P); 667} 668 669/// Populate RequiredPasses with the analysis pass that are required by 670/// pass P. 671void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP, 672 Pass *P) { 673 AnalysisUsage AnUsage; 674 P->getAnalysisUsage(AnUsage); 675 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 676 for (std::vector<AnalysisID>::const_iterator 677 I = RequiredSet.begin(), E = RequiredSet.end(); 678 I != E; ++I) { 679 Pass *AnalysisPass = findAnalysisPass(*I, true); 680 assert (AnalysisPass && "Analysis pass is not available"); 681 RP.push_back(AnalysisPass); 682 } 683} 684 685// All Required analyses should be available to the pass as it runs! Here 686// we fill in the AnalysisImpls member of the pass so that it can 687// successfully use the getAnalysis() method to retrieve the 688// implementations it needs. 689// 690void PMDataManager::initializeAnalysisImpl(Pass *P) { 691 AnalysisUsage AnUsage; 692 P->getAnalysisUsage(AnUsage); 693 694 for (std::vector<const PassInfo *>::const_iterator 695 I = AnUsage.getRequiredSet().begin(), 696 E = AnUsage.getRequiredSet().end(); I != E; ++I) { 697 Pass *Impl = findAnalysisPass(*I, true); 698 if (Impl == 0) 699 assert(0 && "Analysis used but not available!"); 700 AnalysisResolver_New *AR = P->getResolver(); 701 AR->addAnalysisImplsPair(*I, Impl); 702 } 703} 704 705/// Find the pass that implements Analysis AID. If desired pass is not found 706/// then return NULL. 707Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) { 708 709 // Check if AvailableAnalysis map has one entry. 710 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID); 711 712 if (I != AvailableAnalysis.end()) 713 return I->second; 714 715 // Search Parents through TopLevelManager 716 if (SearchParent) 717 return TPM->findAnalysisPass(AID); 718 719 return NULL; 720} 721 722 723//===----------------------------------------------------------------------===// 724// NOTE: Is this the right place to define this method ? 725// getAnalysisToUpdate - Return an analysis result or null if it doesn't exist 726Pass *AnalysisResolver_New::getAnalysisToUpdate(AnalysisID ID, bool dir) const { 727 return PM.findAnalysisPass(ID, dir); 728} 729 730//===----------------------------------------------------------------------===// 731// BasicBlockPassManager_New implementation 732 733/// Add pass P into PassVector and return true. If this pass is not 734/// manageable by this manager then return false. 735bool 736BasicBlockPassManager_New::addPass(Pass *P) { 737 738 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 739 if (!BP) 740 return false; 741 742 // If this pass does not preserve anlysis that is used by other passes 743 // managed by this manager than it is not a suiable pass for this manager. 744 if (!manageablePass(P)) 745 return false; 746 747 addPassToManager (BP); 748 749 return true; 750} 751 752/// Execute all of the passes scheduled for execution by invoking 753/// runOnBasicBlock method. Keep track of whether any of the passes modifies 754/// the function, and if so, return true. 755bool 756BasicBlockPassManager_New::runOnFunction(Function &F) { 757 758 bool Changed = doInitialization(F); 759 initializeAnalysisInfo(); 760 761 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 762 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 763 e = passVectorEnd(); itr != e; ++itr) { 764 Pass *P = *itr; 765 766 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 767 Changed |= BP->runOnBasicBlock(*I); 768 removeNotPreservedAnalysis(P); 769 recordAvailableAnalysis(P); 770 removeDeadPasses(P); 771 } 772 return Changed | doFinalization(F); 773} 774 775// Implement doInitialization and doFinalization 776inline bool BasicBlockPassManager_New::doInitialization(Module &M) { 777 bool Changed = false; 778 779 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 780 e = passVectorEnd(); itr != e; ++itr) { 781 Pass *P = *itr; 782 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 783 Changed |= BP->doInitialization(M); 784 } 785 786 return Changed; 787} 788 789inline bool BasicBlockPassManager_New::doFinalization(Module &M) { 790 bool Changed = false; 791 792 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 793 e = passVectorEnd(); itr != e; ++itr) { 794 Pass *P = *itr; 795 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 796 Changed |= BP->doFinalization(M); 797 } 798 799 return Changed; 800} 801 802inline bool BasicBlockPassManager_New::doInitialization(Function &F) { 803 bool Changed = false; 804 805 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 806 e = passVectorEnd(); itr != e; ++itr) { 807 Pass *P = *itr; 808 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 809 Changed |= BP->doInitialization(F); 810 } 811 812 return Changed; 813} 814 815inline bool BasicBlockPassManager_New::doFinalization(Function &F) { 816 bool Changed = false; 817 818 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 819 e = passVectorEnd(); itr != e; ++itr) { 820 Pass *P = *itr; 821 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 822 Changed |= BP->doFinalization(F); 823 } 824 825 return Changed; 826} 827 828 829//===----------------------------------------------------------------------===// 830// FunctionPassManager_New implementation 831 832/// Create new Function pass manager 833FunctionPassManager_New::FunctionPassManager_New() { 834 FPM = new FunctionPassManagerImpl_New(0); 835} 836 837FunctionPassManager_New::FunctionPassManager_New(ModuleProvider *P) { 838 FPM = new FunctionPassManagerImpl_New(0); 839 // FPM is the top level manager. 840 FPM->setTopLevelManager(FPM); 841 MP = P; 842} 843 844/// add - Add a pass to the queue of passes to run. This passes 845/// ownership of the Pass to the PassManager. When the 846/// PassManager_X is destroyed, the pass will be destroyed as well, so 847/// there is no need to delete the pass. (TODO delete passes.) 848/// This implies that all passes MUST be allocated with 'new'. 849void FunctionPassManager_New::add(Pass *P) { 850 FPM->add(P); 851} 852 853/// Execute all of the passes scheduled for execution. Keep 854/// track of whether any of the passes modifies the function, and if 855/// so, return true. 856bool FunctionPassManager_New::runOnModule(Module &M) { 857 return FPM->runOnModule(M); 858} 859 860/// run - Execute all of the passes scheduled for execution. Keep 861/// track of whether any of the passes modifies the function, and if 862/// so, return true. 863/// 864bool FunctionPassManager_New::run(Function &F) { 865 std::string errstr; 866 if (MP->materializeFunction(&F, &errstr)) { 867 cerr << "Error reading bytecode file: " << errstr << "\n"; 868 abort(); 869 } 870 return FPM->run(F); 871} 872 873 874/// doInitialization - Run all of the initializers for the function passes. 875/// 876bool FunctionPassManager_New::doInitialization() { 877 return FPM->doInitialization(*MP->getModule()); 878} 879 880/// doFinalization - Run all of the initializers for the function passes. 881/// 882bool FunctionPassManager_New::doFinalization() { 883 return FPM->doFinalization(*MP->getModule()); 884} 885 886//===----------------------------------------------------------------------===// 887// FunctionPassManagerImpl_New implementation 888 889/// Add pass P into the pass manager queue. If P is a BasicBlockPass then 890/// either use it into active basic block pass manager or create new basic 891/// block pass manager to handle pass P. 892bool 893FunctionPassManagerImpl_New::addPass(Pass *P) { 894 895 // If P is a BasicBlockPass then use BasicBlockPassManager_New. 896 if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) { 897 898 if (!activeBBPassManager || !activeBBPassManager->addPass(BP)) { 899 900 // If active manager exists then clear its analysis info. 901 if (activeBBPassManager) 902 activeBBPassManager->initializeAnalysisInfo(); 903 904 // Create and add new manager 905 activeBBPassManager = 906 new BasicBlockPassManager_New(getDepth() + 1); 907 // Inherit top level manager 908 activeBBPassManager->setTopLevelManager(this->getTopLevelManager()); 909 910 // Add new manager into current manager's list. 911 addPassToManager(activeBBPassManager, false); 912 913 // Add new manager into top level manager's indirect passes list 914 PMDataManager *PMD = dynamic_cast<PMDataManager *>(activeBBPassManager); 915 assert (PMD && "Manager is not Pass Manager"); 916 TPM->addIndirectPassManager(PMD); 917 918 // Add pass into new manager. This time it must succeed. 919 if (!activeBBPassManager->addPass(BP)) 920 assert(0 && "Unable to add Pass"); 921 } 922 923 if (!ForcedLastUses.empty()) 924 TPM->setLastUser(ForcedLastUses, this); 925 926 return true; 927 } 928 929 FunctionPass *FP = dynamic_cast<FunctionPass *>(P); 930 if (!FP) 931 return false; 932 933 // If this pass does not preserve anlysis that is used by other passes 934 // managed by this manager than it is not a suiable pass for this manager. 935 if (!manageablePass(P)) 936 return false; 937 938 addPassToManager (FP); 939 940 // If active manager exists then clear its analysis info. 941 if (activeBBPassManager) { 942 activeBBPassManager->initializeAnalysisInfo(); 943 activeBBPassManager = NULL; 944 } 945 946 return true; 947} 948 949/// Execute all of the passes scheduled for execution by invoking 950/// runOnFunction method. Keep track of whether any of the passes modifies 951/// the function, and if so, return true. 952bool FunctionPassManagerImpl_New::runOnModule(Module &M) { 953 954 bool Changed = doInitialization(M); 955 initializeAnalysisInfo(); 956 957 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 958 this->runOnFunction(*I); 959 960 return Changed | doFinalization(M); 961} 962 963/// Execute all of the passes scheduled for execution by invoking 964/// runOnFunction method. Keep track of whether any of the passes modifies 965/// the function, and if so, return true. 966bool FunctionPassManagerImpl_New::runOnFunction(Function &F) { 967 968 bool Changed = false; 969 initializeAnalysisInfo(); 970 971 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 972 e = passVectorEnd(); itr != e; ++itr) { 973 Pass *P = *itr; 974 975 FunctionPass *FP = dynamic_cast<FunctionPass*>(P); 976 Changed |= FP->runOnFunction(F); 977 removeNotPreservedAnalysis(P); 978 recordAvailableAnalysis(P); 979 removeDeadPasses(P); 980 } 981 return Changed; 982} 983 984 985inline bool FunctionPassManagerImpl_New::doInitialization(Module &M) { 986 bool Changed = false; 987 988 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 989 e = passVectorEnd(); itr != e; ++itr) { 990 Pass *P = *itr; 991 992 FunctionPass *FP = dynamic_cast<FunctionPass*>(P); 993 Changed |= FP->doInitialization(M); 994 } 995 996 return Changed; 997} 998 999inline bool FunctionPassManagerImpl_New::doFinalization(Module &M) { 1000 bool Changed = false; 1001 1002 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 1003 e = passVectorEnd(); itr != e; ++itr) { 1004 Pass *P = *itr; 1005 1006 FunctionPass *FP = dynamic_cast<FunctionPass*>(P); 1007 Changed |= FP->doFinalization(M); 1008 } 1009 1010 return Changed; 1011} 1012 1013// Execute all the passes managed by this top level manager. 1014// Return true if any function is modified by a pass. 1015bool FunctionPassManagerImpl_New::run(Function &F) { 1016 1017 bool Changed = false; 1018 for (std::vector<Pass *>::iterator I = passManagersBegin(), 1019 E = passManagersEnd(); I != E; ++I) { 1020 FunctionPass *FP = dynamic_cast<FunctionPass *>(*I); 1021 Changed |= FP->runOnFunction(F); 1022 } 1023 return Changed; 1024} 1025 1026//===----------------------------------------------------------------------===// 1027// ModulePassManager implementation 1028 1029/// Add P into pass vector if it is manageble. If P is a FunctionPass 1030/// then use FunctionPassManagerImpl_New to manage it. Return false if P 1031/// is not manageable by this manager. 1032bool 1033ModulePassManager_New::addPass(Pass *P) { 1034 1035 // If P is FunctionPass then use function pass maanager. 1036 if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) { 1037 1038 if (!activeFunctionPassManager || !activeFunctionPassManager->addPass(P)) { 1039 1040 // If active manager exists then clear its analysis info. 1041 if (activeFunctionPassManager) 1042 activeFunctionPassManager->initializeAnalysisInfo(); 1043 1044 // Create and add new manager 1045 activeFunctionPassManager = 1046 new FunctionPassManagerImpl_New(getDepth() + 1); 1047 1048 // Add new manager into current manager's list 1049 addPassToManager(activeFunctionPassManager, false); 1050 1051 // Inherit top level manager 1052 activeFunctionPassManager->setTopLevelManager(this->getTopLevelManager()); 1053 1054 // Add new manager into top level manager's indirect passes list 1055 PMDataManager *PMD = dynamic_cast<PMDataManager *>(activeFunctionPassManager); 1056 assert (PMD && "Manager is not Pass Manager"); 1057 TPM->addIndirectPassManager(PMD); 1058 1059 // Add pass into new manager. This time it must succeed. 1060 if (!activeFunctionPassManager->addPass(FP)) 1061 assert(0 && "Unable to add pass"); 1062 } 1063 1064 if (!ForcedLastUses.empty()) 1065 TPM->setLastUser(ForcedLastUses, this); 1066 1067 return true; 1068 } 1069 1070 ModulePass *MP = dynamic_cast<ModulePass *>(P); 1071 if (!MP) 1072 return false; 1073 1074 // If this pass does not preserve anlysis that is used by other passes 1075 // managed by this manager than it is not a suiable pass for this manager. 1076 if (!manageablePass(P)) 1077 return false; 1078 1079 addPassToManager(MP); 1080 // If active manager exists then clear its analysis info. 1081 if (activeFunctionPassManager) { 1082 activeFunctionPassManager->initializeAnalysisInfo(); 1083 activeFunctionPassManager = NULL; 1084 } 1085 1086 return true; 1087} 1088 1089 1090/// Execute all of the passes scheduled for execution by invoking 1091/// runOnModule method. Keep track of whether any of the passes modifies 1092/// the module, and if so, return true. 1093bool 1094ModulePassManager_New::runOnModule(Module &M) { 1095 bool Changed = false; 1096 initializeAnalysisInfo(); 1097 1098 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 1099 e = passVectorEnd(); itr != e; ++itr) { 1100 Pass *P = *itr; 1101 1102 ModulePass *MP = dynamic_cast<ModulePass*>(P); 1103 Changed |= MP->runOnModule(M); 1104 removeNotPreservedAnalysis(P); 1105 recordAvailableAnalysis(P); 1106 removeDeadPasses(P); 1107 } 1108 return Changed; 1109} 1110 1111//===----------------------------------------------------------------------===// 1112// PassManagerImpl implementation 1113 1114// PassManager_New implementation 1115/// Add P into active pass manager or use new module pass manager to 1116/// manage it. 1117bool PassManagerImpl_New::addPass(Pass *P) { 1118 1119 if (!activeManager || !activeManager->addPass(P)) { 1120 activeManager = new ModulePassManager_New(getDepth() + 1); 1121 // Inherit top level manager 1122 activeManager->setTopLevelManager(this->getTopLevelManager()); 1123 1124 // This top level manager is going to manage activeManager. 1125 // Set up analysis resolver to connect them. 1126 AnalysisResolver_New *AR = new AnalysisResolver_New(*this); 1127 activeManager->setResolver(AR); 1128 1129 addPassManager(activeManager); 1130 return activeManager->addPass(P); 1131 } 1132 return true; 1133} 1134 1135/// run - Execute all of the passes scheduled for execution. Keep track of 1136/// whether any of the passes modifies the module, and if so, return true. 1137bool PassManagerImpl_New::run(Module &M) { 1138 1139 bool Changed = false; 1140 for (std::vector<Pass *>::iterator I = passManagersBegin(), 1141 E = passManagersEnd(); I != E; ++I) { 1142 ModulePassManager_New *MP = dynamic_cast<ModulePassManager_New *>(*I); 1143 Changed |= MP->runOnModule(M); 1144 } 1145 return Changed; 1146} 1147 1148//===----------------------------------------------------------------------===// 1149// PassManager implementation 1150 1151/// Create new pass manager 1152PassManager_New::PassManager_New() { 1153 PM = new PassManagerImpl_New(0); 1154 // PM is the top level manager 1155 PM->setTopLevelManager(PM); 1156} 1157 1158/// add - Add a pass to the queue of passes to run. This passes ownership of 1159/// the Pass to the PassManager. When the PassManager is destroyed, the pass 1160/// will be destroyed as well, so there is no need to delete the pass. This 1161/// implies that all passes MUST be allocated with 'new'. 1162void 1163PassManager_New::add(Pass *P) { 1164 PM->add(P); 1165} 1166 1167/// run - Execute all of the passes scheduled for execution. Keep track of 1168/// whether any of the passes modifies the module, and if so, return true. 1169bool 1170PassManager_New::run(Module &M) { 1171 return PM->run(M); 1172} 1173 1174