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