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