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