1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements the LLVM Pass Manager infrastructure.
12 //===----------------------------------------------------------------------===//
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"
26 //===----------------------------------------------------------------------===//
28 // The Pass Manager Infrastructure manages passes. It's responsibilities are:
30 // o Manage optimization pass execution order
31 // o Make required Analysis information available before pass P is run
32 // o Release memory occupied by dead passes
33 // o If Analysis information is dirtied by a pass then regenerate Analysis
34 // information before it is consumed by another pass.
36 // Pass Manager Infrastructure uses multipe pass managers. They are PassManager,
37 // FunctionPassManager, ModulePassManager, BasicBlockPassManager. This class
38 // hierarcy uses multiple inheritance but pass managers do not derive from
39 // another pass manager.
41 // PassManager and FunctionPassManager are two top level pass manager that
42 // represents the external interface of this entire pass manager infrastucture.
44 // Important classes :
46 // [o] class PMTopLevelManager;
48 // Two top level managers, PassManager and FunctionPassManager, derive from
49 // PMTopLevelManager. PMTopLevelManager manages information used by top level
50 // managers such as last user info.
52 // [o] class PMDataManager;
54 // PMDataManager manages information, e.g. list of available analysis info,
55 // used by a pass manager to manage execution order of passes. It also provides
56 // a place to implement common pass manager APIs. All pass managers derive from
59 // [o] class BasicBlockPassManager : public FunctionPass, public PMDataManager;
61 // BasicBlockPassManager manages BasicBlockPasses.
63 // [o] class FunctionPassManager;
65 // This is a external interface used by JIT to manage FunctionPasses. This
66 // interface relies on FunctionPassManagerImpl to do all the tasks.
68 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager,
69 // public PMTopLevelManager;
71 // FunctionPassManagerImpl is a top level manager. It manages FunctionPasses
72 // and BasicBlockPassManagers.
74 // [o] class ModulePassManager : public Pass, public PMDataManager;
76 // ModulePassManager manages ModulePasses and FunctionPassManagerImpls.
78 // [o] class PassManager;
80 // This is a external interface used by various tools to manages passes. It
81 // relies on PassManagerImpl to do all the tasks.
83 // [o] class PassManagerImpl : public Pass, public PMDataManager,
84 // public PMDTopLevelManager
86 // PassManagerImpl is a top level pass manager responsible for managing
87 // ModulePassManagers.
88 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
93 // Pass debugging information. Often it is useful to find out what pass is
94 // running when a crash occurs in a utility. When this library is compiled with
95 // debugging on, a command line option (--debug-pass) is enabled that causes the
96 // pass name to be printed before it executes.
99 // Different debug levels that can be enabled...
100 enum PassDebugLevel {
101 None, Arguments, Structure, Executions, Details
104 static cl::opt<enum PassDebugLevel>
105 PassDebugging_New("debug-pass", cl::Hidden,
106 cl::desc("Print PassManager debugging information"),
108 clEnumVal(None , "disable debug output"),
109 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
110 clEnumVal(Structure , "print pass structure before run()"),
111 clEnumVal(Executions, "print pass name before it is executed"),
112 clEnumVal(Details , "print pass details when it is executed"),
114 } // End of llvm namespace
116 #ifndef USE_OLD_PASSMANAGER
121 //===----------------------------------------------------------------------===//
124 /// PMTopLevelManager manages LastUser info and collects common APIs used by
125 /// top level pass managers.
126 class PMTopLevelManager {
130 inline std::vector<Pass *>::iterator passManagersBegin() {
131 return PassManagers.begin();
134 inline std::vector<Pass *>::iterator passManagersEnd() {
135 return PassManagers.end();
138 /// Schedule pass P for execution. Make sure that passes required by
139 /// P are run before P is run. Update analysis info maintained by
140 /// the manager. Remove dead passes. This is a recursive function.
141 void schedulePass(Pass *P);
143 /// This is implemented by top level pass manager and used by
144 /// schedulePass() to add analysis info passes that are not available.
145 virtual void addTopLevelPass(Pass *P) = 0;
147 /// Set pass P as the last user of the given analysis passes.
148 void setLastUser(std::vector<Pass *> &AnalysisPasses, Pass *P);
150 /// Collect passes whose last user is P
151 void collectLastUses(std::vector<Pass *> &LastUses, Pass *P);
153 /// Find the pass that implements Analysis AID. Search immutable
154 /// passes and all pass managers. If desired pass is not found
155 /// then return NULL.
156 Pass *findAnalysisPass(AnalysisID AID);
158 inline void clearManagers() {
159 PassManagers.clear();
162 virtual ~PMTopLevelManager() {
164 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
165 E = PassManagers.end(); I != E; ++I)
168 for (std::vector<ImmutablePass *>::iterator
169 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
172 PassManagers.clear();
175 /// Add immutable pass and initialize it.
176 inline void addImmutablePass(ImmutablePass *P) {
178 ImmutablePasses.push_back(P);
181 inline std::vector<ImmutablePass *>& getImmutablePasses() {
182 return ImmutablePasses;
185 void addPassManager(Pass *Manager) {
186 PassManagers.push_back(Manager);
189 // Add Manager into the list of managers that are not directly
190 // maintained by this top level pass manager
191 inline void addIndirectPassManager(PMDataManager *Manager) {
192 IndirectPassManagers.push_back(Manager);
195 // Print passes managed by this top level manager.
197 void dumpArguments();
201 /// Collection of pass managers
202 std::vector<Pass *> PassManagers;
204 /// Collection of pass managers that are not directly maintained
205 /// by this pass manager
206 std::vector<PMDataManager *> IndirectPassManagers;
208 // Map to keep track of last user of the analysis pass.
209 // LastUser->second is the last user of Lastuser->first.
210 std::map<Pass *, Pass *> LastUser;
212 /// Immutable passes are managed by top level manager.
213 std::vector<ImmutablePass *> ImmutablePasses;
216 //===----------------------------------------------------------------------===//
219 /// PMDataManager provides the common place to manage the analysis data
220 /// used by pass managers.
221 class PMDataManager {
225 PMDataManager(int D) : TPM(NULL), Depth(D) {
226 initializeAnalysisInfo();
229 virtual ~PMDataManager() {
231 for (std::vector<Pass *>::iterator I = PassVector.begin(),
232 E = PassVector.end(); I != E; ++I)
238 /// Return true IFF pass P's required analysis set does not required new
240 bool manageablePass(Pass *P);
242 /// Augment AvailableAnalysis by adding analysis made available by pass P.
243 void recordAvailableAnalysis(Pass *P);
245 /// Remove Analysis that is not preserved by the pass
246 void removeNotPreservedAnalysis(Pass *P);
248 /// Remove dead passes
249 void removeDeadPasses(Pass *P, std::string &Msg);
251 /// Add pass P into the PassVector. Update
252 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
253 void addPassToManager (Pass *P, bool ProcessAnalysis = true);
255 /// Initialize available analysis information.
256 void initializeAnalysisInfo() {
257 ForcedLastUses.clear();
258 AvailableAnalysis.clear();
261 /// Populate RequiredPasses with the analysis pass that are required by
263 void collectRequiredAnalysisPasses(std::vector<Pass *> &RequiredPasses,
266 /// All Required analyses should be available to the pass as it runs! Here
267 /// we fill in the AnalysisImpls member of the pass so that it can
268 /// successfully use the getAnalysis() method to retrieve the
269 /// implementations it needs.
270 void initializeAnalysisImpl(Pass *P);
272 /// Find the pass that implements Analysis AID. If desired pass is not found
273 /// then return NULL.
274 Pass *findAnalysisPass(AnalysisID AID, bool Direction);
276 inline std::vector<Pass *>::iterator passVectorBegin() {
277 return PassVector.begin();
280 inline std::vector<Pass *>::iterator passVectorEnd() {
281 return PassVector.end();
284 // Access toplevel manager
285 PMTopLevelManager *getTopLevelManager() { return TPM; }
286 void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
288 unsigned getDepth() { return Depth; }
290 // Print list of passes that are last used by P.
291 void dumpLastUses(Pass *P, unsigned Offset) {
293 std::vector<Pass *> LUses;
295 assert (TPM && "Top Level Manager is missing");
296 TPM->collectLastUses(LUses, P);
298 for (std::vector<Pass *>::iterator I = LUses.begin(),
299 E = LUses.end(); I != E; ++I) {
300 llvm::cerr << "--" << std::string(Offset*2, ' ');
301 (*I)->dumpPassStructure(0);
305 void dumpPassArguments() {
306 for(std::vector<Pass *>::iterator I = PassVector.begin(),
307 E = PassVector.end(); I != E; ++I) {
308 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
309 PMD->dumpPassArguments();
311 if (const PassInfo *PI = (*I)->getPassInfo())
312 if (!PI->isAnalysisGroup())
313 cerr << " -" << PI->getPassArgument();
317 void dumpPassInfo(Pass *P, std::string &Msg1, std::string &Msg2) {
318 if (PassDebugging_New < Executions)
320 cerr << (void*)this << std::string(getDepth()*2+1, ' ');
322 cerr << P->getPassName();
326 void dumpAnalysisSetInfo(const char *Msg, Pass *P,
327 const std::vector<AnalysisID> &Set) {
328 if (PassDebugging_New >= Details && !Set.empty()) {
329 cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
330 for (unsigned i = 0; i != Set.size(); ++i) {
332 cerr << " " << Set[i]->getPassName();
339 // Collection of pass whose last user asked this manager to claim
340 // last use. If a FunctionPass F is the last user of ModulePass info M
341 // then the F's manager, not F, records itself as a last user of M.
342 std::vector<Pass *> ForcedLastUses;
344 // Top level manager.
345 PMTopLevelManager *TPM;
348 // Set of available Analysis. This information is used while scheduling
349 // pass. If a pass requires an analysis which is not not available then
350 // equired analysis pass is scheduled to run before the pass itself is
352 std::map<AnalysisID, Pass*> AvailableAnalysis;
354 // Collection of pass that are managed by this manager
355 std::vector<Pass *> PassVector;
360 //===----------------------------------------------------------------------===//
361 // BasicBlockPassManager
363 /// BasicBlockPassManager manages BasicBlockPass. It batches all the
364 /// pass together and sequence them to process one basic block before
365 /// processing next basic block.
366 class BasicBlockPassManager : public PMDataManager,
367 public FunctionPass {
370 BasicBlockPassManager(int D) : PMDataManager(D) { }
372 /// Add a pass into a passmanager queue.
373 bool addPass(Pass *p);
375 /// Execute all of the passes scheduled for execution. Keep track of
376 /// whether any of the passes modifies the function, and if so, return true.
377 bool runOnFunction(Function &F);
379 /// Pass Manager itself does not invalidate any analysis info.
380 void getAnalysisUsage(AnalysisUsage &Info) const {
381 Info.setPreservesAll();
384 bool doInitialization(Module &M);
385 bool doInitialization(Function &F);
386 bool doFinalization(Module &M);
387 bool doFinalization(Function &F);
389 // Print passes managed by this manager
390 void dumpPassStructure(unsigned Offset) {
391 llvm::cerr << std::string(Offset*2, ' ') << "BasicBLockPass Manager\n";
392 for (std::vector<Pass *>::iterator I = passVectorBegin(),
393 E = passVectorEnd(); I != E; ++I) {
394 (*I)->dumpPassStructure(Offset + 1);
395 dumpLastUses(*I, Offset+1);
400 //===----------------------------------------------------------------------===//
401 // FunctionPassManagerImpl_New
403 /// FunctionPassManagerImpl_New manages FunctionPasses and
404 /// BasicBlockPassManagers. It batches all function passes and basic block pass
405 /// managers together and sequence them to process one function at a time before
406 /// processing next function.
407 class FunctionPassManagerImpl_New : public ModulePass,
408 public PMDataManager,
409 public PMTopLevelManager {
411 FunctionPassManagerImpl_New(int D) : PMDataManager(D) {
412 activeBBPassManager = NULL;
414 ~FunctionPassManagerImpl_New() { /* TODO */ };
416 inline void addTopLevelPass(Pass *P) {
418 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
420 // P is a immutable pass then it will be managed by this
421 // top level manager. Set up analysis resolver to connect them.
422 AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
424 initializeAnalysisImpl(P);
425 addImmutablePass(IP);
426 recordAvailableAnalysis(IP);
432 /// add - Add a pass to the queue of passes to run. This passes
433 /// ownership of the Pass to the PassManager. When the
434 /// PassManager_X is destroyed, the pass will be destroyed as well, so
435 /// there is no need to delete the pass. (TODO delete passes.)
436 /// This implies that all passes MUST be allocated with 'new'.
441 /// Add pass into the pass manager queue.
442 bool addPass(Pass *P);
444 /// Execute all of the passes scheduled for execution. Keep
445 /// track of whether any of the passes modifies the function, and if
447 bool runOnModule(Module &M);
448 bool runOnFunction(Function &F);
449 bool run(Function &F);
451 /// doInitialization - Run all of the initializers for the function passes.
453 bool doInitialization(Module &M);
455 /// doFinalization - Run all of the initializers for the function passes.
457 bool doFinalization(Module &M);
459 /// Pass Manager itself does not invalidate any analysis info.
460 void getAnalysisUsage(AnalysisUsage &Info) const {
461 Info.setPreservesAll();
464 // Print passes managed by this manager
465 void dumpPassStructure(unsigned Offset) {
466 llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
467 for (std::vector<Pass *>::iterator I = passVectorBegin(),
468 E = passVectorEnd(); I != E; ++I) {
469 (*I)->dumpPassStructure(Offset + 1);
470 dumpLastUses(*I, Offset+1);
475 // Active Pass Managers
476 BasicBlockPassManager *activeBBPassManager;
479 //===----------------------------------------------------------------------===//
482 /// ModulePassManager manages ModulePasses and function pass managers.
483 /// It batches all Module passes passes and function pass managers together and
484 /// sequence them to process one module.
485 class ModulePassManager : public Pass,
486 public PMDataManager {
489 ModulePassManager(int D) : PMDataManager(D) {
490 activeFunctionPassManager = NULL;
493 /// Add a pass into a passmanager queue.
494 bool addPass(Pass *p);
496 /// run - Execute all of the passes scheduled for execution. Keep track of
497 /// whether any of the passes modifies the module, and if so, return true.
498 bool runOnModule(Module &M);
500 /// Pass Manager itself does not invalidate any analysis info.
501 void getAnalysisUsage(AnalysisUsage &Info) const {
502 Info.setPreservesAll();
505 // Print passes managed by this manager
506 void dumpPassStructure(unsigned Offset) {
507 llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
508 for (std::vector<Pass *>::iterator I = passVectorBegin(),
509 E = passVectorEnd(); I != E; ++I) {
510 (*I)->dumpPassStructure(Offset + 1);
511 dumpLastUses(*I, Offset+1);
516 // Active Pass Manager
517 FunctionPassManagerImpl_New *activeFunctionPassManager;
520 //===----------------------------------------------------------------------===//
521 // PassManagerImpl_New
523 /// PassManagerImpl_New manages ModulePassManagers
524 class PassManagerImpl_New : public Pass,
525 public PMDataManager,
526 public PMTopLevelManager {
530 PassManagerImpl_New(int D) : PMDataManager(D) {
531 activeManager = NULL;
534 /// add - Add a pass to the queue of passes to run. This passes ownership of
535 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
536 /// will be destroyed as well, so there is no need to delete the pass. This
537 /// implies that all passes MUST be allocated with 'new'.
542 /// run - Execute all of the passes scheduled for execution. Keep track of
543 /// whether any of the passes modifies the module, and if so, return true.
546 /// Pass Manager itself does not invalidate any analysis info.
547 void getAnalysisUsage(AnalysisUsage &Info) const {
548 Info.setPreservesAll();
551 inline void addTopLevelPass(Pass *P) {
553 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
555 // P is a immutable pass and it will be managed by this
556 // top level manager. Set up analysis resolver to connect them.
557 AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
559 initializeAnalysisImpl(P);
560 addImmutablePass(IP);
561 recordAvailableAnalysis(IP);
569 /// Add a pass into a passmanager queue.
570 bool addPass(Pass *p);
572 // Active Pass Manager
573 ModulePassManager *activeManager;
576 //===----------------------------------------------------------------------===//
577 // TimingInfo Class - This class is used to calculate information about the
578 // amount of time each pass takes to execute. This only happens when
579 // -time-passes is enabled on the command line.
583 std::map<Pass*, Timer> TimingData;
587 // Use 'create' member to get this.
588 TimingInfo() : TG("... Pass execution timing report ...") {}
590 // TimingDtor - Print out information about timing information
592 // Delete all of the timers...
594 // TimerGroup is deleted next, printing the report.
597 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
598 // to a non null value (if the -time-passes option is enabled) or it leaves it
599 // null. It may be called multiple times.
600 static void createTheTimeInfo();
602 void passStarted(Pass *P) {
604 if (dynamic_cast<PMDataManager *>(P))
607 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
608 if (I == TimingData.end())
609 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
610 I->second.startTimer();
612 void passEnded(Pass *P) {
614 if (dynamic_cast<PMDataManager *>(P))
617 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
618 assert (I != TimingData.end() && "passStarted/passEnded not nested right!");
619 I->second.stopTimer();
623 static TimingInfo *TheTimeInfo;
625 } // End of llvm namespace
627 //===----------------------------------------------------------------------===//
628 // PMTopLevelManager implementation
630 /// Set pass P as the last user of the given analysis passes.
631 void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses,
634 for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(),
635 E = AnalysisPasses.end(); I != E; ++I) {
638 // If AP is the last user of other passes then make P last user of
640 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
641 LUE = LastUser.end(); LUI != LUE; ++LUI) {
642 if (LUI->second == AP)
643 LastUser[LUI->first] = P;
648 /// Collect passes whose last user is P
649 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses,
651 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
652 LUE = LastUser.end(); LUI != LUE; ++LUI)
653 if (LUI->second == P)
654 LastUses.push_back(LUI->first);
657 /// Schedule pass P for execution. Make sure that passes required by
658 /// P are run before P is run. Update analysis info maintained by
659 /// the manager. Remove dead passes. This is a recursive function.
660 void PMTopLevelManager::schedulePass(Pass *P) {
662 // TODO : Allocate function manager for this pass, other wise required set
663 // may be inserted into previous function manager
665 AnalysisUsage AnUsage;
666 P->getAnalysisUsage(AnUsage);
667 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
668 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
669 E = RequiredSet.end(); I != E; ++I) {
671 Pass *AnalysisPass = findAnalysisPass(*I);
673 // Schedule this analysis run first.
674 AnalysisPass = (*I)->createPass();
675 schedulePass(AnalysisPass);
679 // Now all required passes are available.
683 /// Find the pass that implements Analysis AID. Search immutable
684 /// passes and all pass managers. If desired pass is not found
685 /// then return NULL.
686 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
689 // Check pass managers
690 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
691 E = PassManagers.end(); P == NULL && I != E; ++I) {
692 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
693 assert(PMD && "This is not a PassManager");
694 P = PMD->findAnalysisPass(AID, false);
697 // Check other pass managers
698 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
699 E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
700 P = (*I)->findAnalysisPass(AID, false);
702 for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(),
703 E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
704 const PassInfo *PI = (*I)->getPassInfo();
708 // If Pass not found then check the interfaces implemented by Immutable Pass
710 const std::vector<const PassInfo*> &ImmPI =
711 PI->getInterfacesImplemented();
712 for (unsigned Index = 0, End = ImmPI.size();
713 P == NULL && Index != End; ++Index)
714 if (ImmPI[Index] == AID)
722 // Print passes managed by this top level manager.
723 void PMTopLevelManager::dumpPasses() {
725 // Print out the immutable passes
726 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
727 ImmutablePasses[i]->dumpPassStructure(0);
730 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
731 E = PassManagers.end(); I != E; ++I)
732 (*I)->dumpPassStructure(1);
736 void PMTopLevelManager::dumpArguments() {
738 if (PassDebugging_New < Arguments)
741 cerr << "Pass Arguments: ";
742 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
743 E = PassManagers.end(); I != E; ++I) {
744 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
745 assert(PMD && "This is not a PassManager");
746 PMD->dumpPassArguments();
751 //===----------------------------------------------------------------------===//
752 // PMDataManager implementation
754 /// Return true IFF pass P's required analysis set does not required new
756 bool PMDataManager::manageablePass(Pass *P) {
759 // If this pass is not preserving information that is required by a
760 // pass maintained by higher level pass manager then do not insert
761 // this pass into current manager. Use new manager. For example,
762 // For example, If FunctionPass F is not preserving ModulePass Info M1
763 // that is used by another ModulePass M2 then do not insert F in
764 // current function pass manager.
768 /// Augement AvailableAnalysis by adding analysis made available by pass P.
769 void PMDataManager::recordAvailableAnalysis(Pass *P) {
771 if (const PassInfo *PI = P->getPassInfo()) {
772 AvailableAnalysis[PI] = P;
774 //This pass is the current implementation of all of the interfaces it
775 //implements as well.
776 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
777 for (unsigned i = 0, e = II.size(); i != e; ++i)
778 AvailableAnalysis[II[i]] = P;
782 /// Remove Analyss not preserved by Pass P
783 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
784 AnalysisUsage AnUsage;
785 P->getAnalysisUsage(AnUsage);
787 if (AnUsage.getPreservesAll())
790 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
791 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
792 E = AvailableAnalysis.end(); I != E; ) {
793 if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) ==
794 PreservedSet.end()) {
795 // Remove this analysis
796 if (!dynamic_cast<ImmutablePass*>(I->second)) {
797 std::map<AnalysisID, Pass*>::iterator J = I++;
798 AvailableAnalysis.erase(J);
806 /// Remove analysis passes that are not used any longer
807 void PMDataManager::removeDeadPasses(Pass *P, std::string &Msg) {
809 std::vector<Pass *> DeadPasses;
810 TPM->collectLastUses(DeadPasses, P);
812 for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
813 E = DeadPasses.end(); I != E; ++I) {
815 std::string Msg1 = " Freeing Pass '";
816 dumpPassInfo(*I, Msg1, Msg);
818 if (TheTimeInfo) TheTimeInfo->passStarted(P);
819 (*I)->releaseMemory();
820 if (TheTimeInfo) TheTimeInfo->passEnded(P);
822 std::map<AnalysisID, Pass*>::iterator Pos =
823 AvailableAnalysis.find((*I)->getPassInfo());
825 // It is possible that pass is already removed from the AvailableAnalysis
826 if (Pos != AvailableAnalysis.end())
827 AvailableAnalysis.erase(Pos);
831 /// Add pass P into the PassVector. Update
832 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
833 void PMDataManager::addPassToManager(Pass *P,
834 bool ProcessAnalysis) {
836 // This manager is going to manage pass P. Set up analysis resolver
838 AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
841 if (ProcessAnalysis) {
843 // At the moment, this pass is the last user of all required passes.
844 std::vector<Pass *> LastUses;
845 std::vector<Pass *> RequiredPasses;
846 unsigned PDepth = this->getDepth();
848 collectRequiredAnalysisPasses(RequiredPasses, P);
849 for (std::vector<Pass *>::iterator I = RequiredPasses.begin(),
850 E = RequiredPasses.end(); I != E; ++I) {
851 Pass *PRequired = *I;
854 PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
855 RDepth = DM.getDepth();
857 if (PDepth == RDepth)
858 LastUses.push_back(PRequired);
859 else if (PDepth > RDepth) {
860 // Let the parent claim responsibility of last use
861 ForcedLastUses.push_back(PRequired);
863 // Note : This feature is not yet implemented
865 "Unable to handle Pass that requires lower level Analysis pass");
869 if (!LastUses.empty())
870 TPM->setLastUser(LastUses, P);
872 // Take a note of analysis required and made available by this pass.
873 // Remove the analysis not preserved by this pass
874 removeNotPreservedAnalysis(P);
875 recordAvailableAnalysis(P);
879 PassVector.push_back(P);
882 /// Populate RequiredPasses with the analysis pass that are required by
884 void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP,
886 AnalysisUsage AnUsage;
887 P->getAnalysisUsage(AnUsage);
888 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
889 for (std::vector<AnalysisID>::const_iterator
890 I = RequiredSet.begin(), E = RequiredSet.end();
892 Pass *AnalysisPass = findAnalysisPass(*I, true);
893 assert (AnalysisPass && "Analysis pass is not available");
894 RP.push_back(AnalysisPass);
897 const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
898 for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
899 E = IDs.end(); I != E; ++I) {
900 Pass *AnalysisPass = findAnalysisPass(*I, true);
901 assert (AnalysisPass && "Analysis pass is not available");
902 RP.push_back(AnalysisPass);
906 // All Required analyses should be available to the pass as it runs! Here
907 // we fill in the AnalysisImpls member of the pass so that it can
908 // successfully use the getAnalysis() method to retrieve the
909 // implementations it needs.
911 void PMDataManager::initializeAnalysisImpl(Pass *P) {
912 AnalysisUsage AnUsage;
913 P->getAnalysisUsage(AnUsage);
915 for (std::vector<const PassInfo *>::const_iterator
916 I = AnUsage.getRequiredSet().begin(),
917 E = AnUsage.getRequiredSet().end(); I != E; ++I) {
918 Pass *Impl = findAnalysisPass(*I, true);
920 assert(0 && "Analysis used but not available!");
921 AnalysisResolver_New *AR = P->getResolver();
922 AR->addAnalysisImplsPair(*I, Impl);
926 /// Find the pass that implements Analysis AID. If desired pass is not found
927 /// then return NULL.
928 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
930 // Check if AvailableAnalysis map has one entry.
931 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID);
933 if (I != AvailableAnalysis.end())
936 // Search Parents through TopLevelManager
938 return TPM->findAnalysisPass(AID);
944 //===----------------------------------------------------------------------===//
945 // NOTE: Is this the right place to define this method ?
946 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
947 Pass *AnalysisResolver_New::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
948 return PM.findAnalysisPass(ID, dir);
951 //===----------------------------------------------------------------------===//
952 // BasicBlockPassManager implementation
954 /// Add pass P into PassVector and return true. If this pass is not
955 /// manageable by this manager then return false.
957 BasicBlockPassManager::addPass(Pass *P) {
959 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
963 // If this pass does not preserve anlysis that is used by other passes
964 // managed by this manager than it is not a suiable pass for this manager.
965 if (!manageablePass(P))
968 addPassToManager (BP);
973 /// Execute all of the passes scheduled for execution by invoking
974 /// runOnBasicBlock method. Keep track of whether any of the passes modifies
975 /// the function, and if so, return true.
977 BasicBlockPassManager::runOnFunction(Function &F) {
982 bool Changed = doInitialization(F);
983 initializeAnalysisInfo();
985 std::string Msg1 = "Executing Pass '";
986 std::string Msg3 = "' Made Modification '";
988 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
989 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
990 e = passVectorEnd(); itr != e; ++itr) {
992 AnalysisUsage AnUsage;
993 P->getAnalysisUsage(AnUsage);
995 std::string Msg2 = "' on BasicBlock '" + (*I).getName() + "'...\n";
996 dumpPassInfo(P, Msg1, Msg2);
997 dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet());
999 initializeAnalysisImpl(P);
1001 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
1002 if (TheTimeInfo) TheTimeInfo->passStarted(P);
1003 Changed |= BP->runOnBasicBlock(*I);
1004 if (TheTimeInfo) TheTimeInfo->passEnded(P);
1007 dumpPassInfo(P, Msg3, Msg2);
1008 dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet());
1010 removeNotPreservedAnalysis(P);
1011 recordAvailableAnalysis(P);
1012 removeDeadPasses(P, Msg2);
1014 return Changed | doFinalization(F);
1017 // Implement doInitialization and doFinalization
1018 inline bool BasicBlockPassManager::doInitialization(Module &M) {
1019 bool Changed = false;
1021 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1022 e = passVectorEnd(); itr != e; ++itr) {
1024 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
1025 Changed |= BP->doInitialization(M);
1031 inline bool BasicBlockPassManager::doFinalization(Module &M) {
1032 bool Changed = false;
1034 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1035 e = passVectorEnd(); itr != e; ++itr) {
1037 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
1038 Changed |= BP->doFinalization(M);
1044 inline bool BasicBlockPassManager::doInitialization(Function &F) {
1045 bool Changed = false;
1047 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1048 e = passVectorEnd(); itr != e; ++itr) {
1050 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
1051 Changed |= BP->doInitialization(F);
1057 inline bool BasicBlockPassManager::doFinalization(Function &F) {
1058 bool Changed = false;
1060 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1061 e = passVectorEnd(); itr != e; ++itr) {
1063 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
1064 Changed |= BP->doFinalization(F);
1071 //===----------------------------------------------------------------------===//
1072 // FunctionPassManager implementation
1074 /// Create new Function pass manager
1075 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
1076 FPM = new FunctionPassManagerImpl_New(0);
1077 // FPM is the top level manager.
1078 FPM->setTopLevelManager(FPM);
1080 PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
1081 AnalysisResolver_New *AR = new AnalysisResolver_New(*PMD);
1082 FPM->setResolver(AR);
1084 FPM->addPassManager(FPM);
1088 FunctionPassManager::~FunctionPassManager() {
1089 // Note : FPM maintains one entry in PassManagers vector.
1090 // This one entry is FPM itself. This is not ideal. One
1091 // alternative is have one additional layer between
1092 // FunctionPassManager and FunctionPassManagerImpl.
1093 // Meanwhile, to avoid going into infinte loop, first
1094 // remove FPM from its PassMangers vector.
1095 FPM->clearManagers();
1099 /// add - Add a pass to the queue of passes to run. This passes
1100 /// ownership of the Pass to the PassManager. When the
1101 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1102 /// there is no need to delete the pass. (TODO delete passes.)
1103 /// This implies that all passes MUST be allocated with 'new'.
1104 void FunctionPassManager::add(Pass *P) {
1108 /// run - Execute all of the passes scheduled for execution. Keep
1109 /// track of whether any of the passes modifies the function, and if
1110 /// so, return true.
1112 bool FunctionPassManager::run(Function &F) {
1114 if (MP->materializeFunction(&F, &errstr)) {
1115 cerr << "Error reading bytecode file: " << errstr << "\n";
1122 /// doInitialization - Run all of the initializers for the function passes.
1124 bool FunctionPassManager::doInitialization() {
1125 return FPM->doInitialization(*MP->getModule());
1128 /// doFinalization - Run all of the initializers for the function passes.
1130 bool FunctionPassManager::doFinalization() {
1131 return FPM->doFinalization(*MP->getModule());
1134 //===----------------------------------------------------------------------===//
1135 // FunctionPassManagerImpl_New implementation
1137 /// Add pass P into the pass manager queue. If P is a BasicBlockPass then
1138 /// either use it into active basic block pass manager or create new basic
1139 /// block pass manager to handle pass P.
1141 FunctionPassManagerImpl_New::addPass(Pass *P) {
1143 // If P is a BasicBlockPass then use BasicBlockPassManager.
1144 if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) {
1146 if (!activeBBPassManager || !activeBBPassManager->addPass(BP)) {
1148 // If active manager exists then clear its analysis info.
1149 if (activeBBPassManager)
1150 activeBBPassManager->initializeAnalysisInfo();
1152 // Create and add new manager
1153 activeBBPassManager =
1154 new BasicBlockPassManager(getDepth() + 1);
1155 // Inherit top level manager
1156 activeBBPassManager->setTopLevelManager(this->getTopLevelManager());
1158 // Add new manager into current manager's list.
1159 addPassToManager(activeBBPassManager, false);
1161 // Add new manager into top level manager's indirect passes list
1162 PMDataManager *PMD = dynamic_cast<PMDataManager *>(activeBBPassManager);
1163 assert (PMD && "Manager is not Pass Manager");
1164 TPM->addIndirectPassManager(PMD);
1166 // Add pass into new manager. This time it must succeed.
1167 if (!activeBBPassManager->addPass(BP))
1168 assert(0 && "Unable to add Pass");
1171 if (!ForcedLastUses.empty())
1172 TPM->setLastUser(ForcedLastUses, this);
1177 FunctionPass *FP = dynamic_cast<FunctionPass *>(P);
1181 // If this pass does not preserve anlysis that is used by other passes
1182 // managed by this manager than it is not a suiable pass for this manager.
1183 if (!manageablePass(P))
1186 addPassToManager (FP);
1188 // If active manager exists then clear its analysis info.
1189 if (activeBBPassManager) {
1190 activeBBPassManager->initializeAnalysisInfo();
1191 activeBBPassManager = NULL;
1197 /// Execute all of the passes scheduled for execution by invoking
1198 /// runOnFunction method. Keep track of whether any of the passes modifies
1199 /// the function, and if so, return true.
1200 bool FunctionPassManagerImpl_New::runOnModule(Module &M) {
1202 bool Changed = doInitialization(M);
1203 initializeAnalysisInfo();
1205 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1206 this->runOnFunction(*I);
1208 return Changed | doFinalization(M);
1211 /// Execute all of the passes scheduled for execution by invoking
1212 /// runOnFunction method. Keep track of whether any of the passes modifies
1213 /// the function, and if so, return true.
1214 bool FunctionPassManagerImpl_New::runOnFunction(Function &F) {
1216 bool Changed = false;
1221 initializeAnalysisInfo();
1223 std::string Msg1 = "Executing Pass '";
1224 std::string Msg3 = "' Made Modification '";
1226 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1227 e = passVectorEnd(); itr != e; ++itr) {
1229 AnalysisUsage AnUsage;
1230 P->getAnalysisUsage(AnUsage);
1232 std::string Msg2 = "' on Function '" + F.getName() + "'...\n";
1233 dumpPassInfo(P, Msg1, Msg2);
1234 dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet());
1236 initializeAnalysisImpl(P);
1237 FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1239 if (TheTimeInfo) TheTimeInfo->passStarted(P);
1240 Changed |= FP->runOnFunction(F);
1241 if (TheTimeInfo) TheTimeInfo->passEnded(P);
1244 dumpPassInfo(P, Msg3, Msg2);
1245 dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet());
1247 removeNotPreservedAnalysis(P);
1248 recordAvailableAnalysis(P);
1249 removeDeadPasses(P, Msg2);
1255 inline bool FunctionPassManagerImpl_New::doInitialization(Module &M) {
1256 bool Changed = false;
1258 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1259 e = passVectorEnd(); itr != e; ++itr) {
1262 FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1263 Changed |= FP->doInitialization(M);
1269 inline bool FunctionPassManagerImpl_New::doFinalization(Module &M) {
1270 bool Changed = false;
1272 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1273 e = passVectorEnd(); itr != e; ++itr) {
1276 FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1277 Changed |= FP->doFinalization(M);
1283 // Execute all the passes managed by this top level manager.
1284 // Return true if any function is modified by a pass.
1285 bool FunctionPassManagerImpl_New::run(Function &F) {
1287 bool Changed = false;
1288 for (std::vector<Pass *>::iterator I = passManagersBegin(),
1289 E = passManagersEnd(); I != E; ++I) {
1290 FunctionPassManagerImpl_New *FP =
1291 dynamic_cast<FunctionPassManagerImpl_New *>(*I);
1292 Changed |= FP->runOnFunction(F);
1297 //===----------------------------------------------------------------------===//
1298 // ModulePassManager implementation
1300 /// Add P into pass vector if it is manageble. If P is a FunctionPass
1301 /// then use FunctionPassManagerImpl_New to manage it. Return false if P
1302 /// is not manageable by this manager.
1304 ModulePassManager::addPass(Pass *P) {
1306 // If P is FunctionPass then use function pass maanager.
1307 if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) {
1309 if (!activeFunctionPassManager || !activeFunctionPassManager->addPass(P)) {
1311 // If active manager exists then clear its analysis info.
1312 if (activeFunctionPassManager)
1313 activeFunctionPassManager->initializeAnalysisInfo();
1315 // Create and add new manager
1316 activeFunctionPassManager =
1317 new FunctionPassManagerImpl_New(getDepth() + 1);
1319 // Add new manager into current manager's list
1320 addPassToManager(activeFunctionPassManager, false);
1322 // Inherit top level manager
1323 activeFunctionPassManager->setTopLevelManager(this->getTopLevelManager());
1325 // Add new manager into top level manager's indirect passes list
1326 PMDataManager *PMD =
1327 dynamic_cast<PMDataManager *>(activeFunctionPassManager);
1328 assert(PMD && "Manager is not Pass Manager");
1329 TPM->addIndirectPassManager(PMD);
1331 // Add pass into new manager. This time it must succeed.
1332 if (!activeFunctionPassManager->addPass(FP))
1333 assert(0 && "Unable to add pass");
1336 if (!ForcedLastUses.empty())
1337 TPM->setLastUser(ForcedLastUses, this);
1342 ModulePass *MP = dynamic_cast<ModulePass *>(P);
1346 // If this pass does not preserve anlysis that is used by other passes
1347 // managed by this manager than it is not a suiable pass for this manager.
1348 if (!manageablePass(P))
1351 addPassToManager(MP);
1352 // If active manager exists then clear its analysis info.
1353 if (activeFunctionPassManager) {
1354 activeFunctionPassManager->initializeAnalysisInfo();
1355 activeFunctionPassManager = NULL;
1362 /// Execute all of the passes scheduled for execution by invoking
1363 /// runOnModule method. Keep track of whether any of the passes modifies
1364 /// the module, and if so, return true.
1366 ModulePassManager::runOnModule(Module &M) {
1367 bool Changed = false;
1368 initializeAnalysisInfo();
1370 std::string Msg1 = "Executing Pass '";
1371 std::string Msg3 = "' Made Modification '";
1373 for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1374 e = passVectorEnd(); itr != e; ++itr) {
1376 AnalysisUsage AnUsage;
1377 P->getAnalysisUsage(AnUsage);
1379 std::string Msg2 = "' on Module '" + M.getModuleIdentifier() + "'...\n";
1380 dumpPassInfo(P, Msg1, Msg2);
1381 dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet());
1383 initializeAnalysisImpl(P);
1384 ModulePass *MP = dynamic_cast<ModulePass*>(P);
1386 if (TheTimeInfo) TheTimeInfo->passStarted(P);
1387 Changed |= MP->runOnModule(M);
1388 if (TheTimeInfo) TheTimeInfo->passEnded(P);
1391 dumpPassInfo(P, Msg3, Msg2);
1392 dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet());
1394 removeNotPreservedAnalysis(P);
1395 recordAvailableAnalysis(P);
1396 removeDeadPasses(P, Msg2);
1401 //===----------------------------------------------------------------------===//
1402 // PassManagerImpl implementation
1404 /// Add P into active pass manager or use new module pass manager to
1406 bool PassManagerImpl_New::addPass(Pass *P) {
1408 if (!activeManager || !activeManager->addPass(P)) {
1409 activeManager = new ModulePassManager(getDepth() + 1);
1410 // Inherit top level manager
1411 activeManager->setTopLevelManager(this->getTopLevelManager());
1413 // This top level manager is going to manage activeManager.
1414 // Set up analysis resolver to connect them.
1415 AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
1416 activeManager->setResolver(AR);
1418 addPassManager(activeManager);
1419 return activeManager->addPass(P);
1424 /// run - Execute all of the passes scheduled for execution. Keep track of
1425 /// whether any of the passes modifies the module, and if so, return true.
1426 bool PassManagerImpl_New::run(Module &M) {
1428 bool Changed = false;
1430 TimingInfo::createTheTimeInfo();
1433 if (PassDebugging_New >= Structure)
1436 for (std::vector<Pass *>::iterator I = passManagersBegin(),
1437 E = passManagersEnd(); I != E; ++I) {
1438 ModulePassManager *MP = dynamic_cast<ModulePassManager *>(*I);
1439 Changed |= MP->runOnModule(M);
1444 //===----------------------------------------------------------------------===//
1445 // PassManager implementation
1447 /// Create new pass manager
1448 PassManager::PassManager() {
1449 PM = new PassManagerImpl_New(0);
1450 // PM is the top level manager
1451 PM->setTopLevelManager(PM);
1454 PassManager::~PassManager() {
1458 /// add - Add a pass to the queue of passes to run. This passes ownership of
1459 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
1460 /// will be destroyed as well, so there is no need to delete the pass. This
1461 /// implies that all passes MUST be allocated with 'new'.
1463 PassManager::add(Pass *P) {
1467 /// run - Execute all of the passes scheduled for execution. Keep track of
1468 /// whether any of the passes modifies the module, and if so, return true.
1470 PassManager::run(Module &M) {
1474 //===----------------------------------------------------------------------===//
1475 // TimingInfo Class - This class is used to calculate information about the
1476 // amount of time each pass takes to execute. This only happens with
1477 // -time-passes is enabled on the command line.
1479 bool llvm::TimePassesIsEnabled = false;
1480 static cl::opt<bool,true>
1481 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1482 cl::desc("Time each pass, printing elapsed time for each on exit"));
1484 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1485 // a non null value (if the -time-passes option is enabled) or it leaves it
1486 // null. It may be called multiple times.
1487 void TimingInfo::createTheTimeInfo() {
1488 if (!TimePassesIsEnabled || TheTimeInfo) return;
1490 // Constructed the first time this is called, iff -time-passes is enabled.
1491 // This guarantees that the object will be constructed before static globals,
1492 // thus it will be destroyed before them.
1493 static ManagedStatic<TimingInfo> TTI;
1494 TheTimeInfo = &*TTI;