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