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/PassManagers.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 // See PassManagers.h for Pass Manager infrastructure overview.
30 //===----------------------------------------------------------------------===//
31 // Pass debugging information. Often it is useful to find out what pass is
32 // running when a crash occurs in a utility. When this library is compiled with
33 // debugging on, a command line option (--debug-pass) is enabled that causes the
34 // pass name to be printed before it executes.
37 // Different debug levels that can be enabled...
39 None, Arguments, Structure, Executions, Details
42 static cl::opt<enum PassDebugLevel>
43 PassDebugging("debug-pass", cl::Hidden,
44 cl::desc("Print PassManager debugging information"),
46 clEnumVal(None , "disable debug output"),
47 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
48 clEnumVal(Structure , "print pass structure before run()"),
49 clEnumVal(Executions, "print pass name before it is executed"),
50 clEnumVal(Details , "print pass details when it is executed"),
52 } // End of llvm namespace
56 //===----------------------------------------------------------------------===//
59 /// BBPassManager manages BasicBlockPass. It batches all the
60 /// pass together and sequence them to process one basic block before
61 /// processing next basic block.
62 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager,
67 BBPassManager(int Depth)
68 : PMDataManager(Depth), FunctionPass((intptr_t)&ID) {}
70 /// Execute all of the passes scheduled for execution. Keep track of
71 /// whether any of the passes modifies the function, and if so, return true.
72 bool runOnFunction(Function &F);
74 /// Pass Manager itself does not invalidate any analysis info.
75 void getAnalysisUsage(AnalysisUsage &Info) const {
76 Info.setPreservesAll();
79 bool doInitialization(Module &M);
80 bool doInitialization(Function &F);
81 bool doFinalization(Module &M);
82 bool doFinalization(Function &F);
84 virtual const char *getPassName() const {
85 return "BasicBlock Pass Manager";
88 // Print passes managed by this manager
89 void dumpPassStructure(unsigned Offset) {
90 llvm::cerr << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n";
91 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
92 BasicBlockPass *BP = getContainedPass(Index);
93 BP->dumpPassStructure(Offset + 1);
94 dumpLastUses(BP, Offset+1);
98 BasicBlockPass *getContainedPass(unsigned N) {
99 assert ( N < PassVector.size() && "Pass number out of range!");
100 BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
104 virtual PassManagerType getPassManagerType() const {
105 return PMT_BasicBlockPassManager;
109 char BBPassManager::ID = 0;
114 //===----------------------------------------------------------------------===//
115 // FunctionPassManagerImpl
117 /// FunctionPassManagerImpl manages FPPassManagers
118 class FunctionPassManagerImpl : public Pass,
119 public PMDataManager,
120 public PMTopLevelManager {
123 FunctionPassManagerImpl(int Depth) :
124 Pass((intptr_t)&ID), PMDataManager(Depth),
125 PMTopLevelManager(TLM_Function) { }
127 /// add - Add a pass to the queue of passes to run. This passes ownership of
128 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
129 /// will be destroyed as well, so there is no need to delete the pass. This
130 /// implies that all passes MUST be allocated with 'new'.
135 /// run - Execute all of the passes scheduled for execution. Keep track of
136 /// whether any of the passes modifies the module, and if so, return true.
137 bool run(Function &F);
139 /// doInitialization - Run all of the initializers for the function passes.
141 bool doInitialization(Module &M);
143 /// doFinalization - Run all of the initializers for the function passes.
145 bool doFinalization(Module &M);
147 /// Pass Manager itself does not invalidate any analysis info.
148 void getAnalysisUsage(AnalysisUsage &Info) const {
149 Info.setPreservesAll();
152 inline void addTopLevelPass(Pass *P) {
154 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
156 // P is a immutable pass and it will be managed by this
157 // top level manager. Set up analysis resolver to connect them.
158 AnalysisResolver *AR = new AnalysisResolver(*this);
160 initializeAnalysisImpl(P);
161 addImmutablePass(IP);
162 recordAvailableAnalysis(IP);
164 P->assignPassManager(activeStack);
169 FPPassManager *getContainedManager(unsigned N) {
170 assert ( N < PassManagers.size() && "Pass number out of range!");
171 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
176 char FunctionPassManagerImpl::ID = 0;
177 //===----------------------------------------------------------------------===//
180 /// MPPassManager manages ModulePasses and function pass managers.
181 /// It batches all Module passes passes and function pass managers together and
182 /// sequence them to process one module.
183 class MPPassManager : public Pass, public PMDataManager {
187 MPPassManager(int Depth) : Pass((intptr_t)&ID), PMDataManager(Depth) { }
189 // Delete on the fly managers.
190 virtual ~MPPassManager() {
191 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
192 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
194 FunctionPassManagerImpl *FPP = I->second;
199 /// run - Execute all of the passes scheduled for execution. Keep track of
200 /// whether any of the passes modifies the module, and if so, return true.
201 bool runOnModule(Module &M);
203 /// Pass Manager itself does not invalidate any analysis info.
204 void getAnalysisUsage(AnalysisUsage &Info) const {
205 Info.setPreservesAll();
208 /// Add RequiredPass into list of lower level passes required by pass P.
209 /// RequiredPass is run on the fly by Pass Manager when P requests it
210 /// through getAnalysis interface.
211 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
213 /// Return function pass corresponding to PassInfo PI, that is
214 /// required by module pass MP. Instantiate analysis pass, by using
215 /// its runOnFunction() for function F.
216 virtual Pass* getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F);
218 virtual const char *getPassName() const {
219 return "Module Pass Manager";
222 // Print passes managed by this manager
223 void dumpPassStructure(unsigned Offset) {
224 llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
225 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
226 ModulePass *MP = getContainedPass(Index);
227 MP->dumpPassStructure(Offset + 1);
228 if (FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP])
229 FPP->dumpPassStructure(Offset + 2);
230 dumpLastUses(MP, Offset+1);
234 ModulePass *getContainedPass(unsigned N) {
235 assert ( N < PassVector.size() && "Pass number out of range!");
236 ModulePass *MP = static_cast<ModulePass *>(PassVector[N]);
240 virtual PassManagerType getPassManagerType() const {
241 return PMT_ModulePassManager;
245 /// Collection of on the fly FPPassManagers. These managers manage
246 /// function passes that are required by module passes.
247 std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
250 char MPPassManager::ID = 0;
251 //===----------------------------------------------------------------------===//
255 /// PassManagerImpl manages MPPassManagers
256 class PassManagerImpl : public Pass,
257 public PMDataManager,
258 public PMTopLevelManager {
262 PassManagerImpl(int Depth) : Pass((intptr_t)&ID), PMDataManager(Depth),
263 PMTopLevelManager(TLM_Pass) { }
265 /// add - Add a pass to the queue of passes to run. This passes ownership of
266 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
267 /// will be destroyed as well, so there is no need to delete the pass. This
268 /// implies that all passes MUST be allocated with 'new'.
273 /// run - Execute all of the passes scheduled for execution. Keep track of
274 /// whether any of the passes modifies the module, and if so, return true.
277 /// Pass Manager itself does not invalidate any analysis info.
278 void getAnalysisUsage(AnalysisUsage &Info) const {
279 Info.setPreservesAll();
282 inline void addTopLevelPass(Pass *P) {
284 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
286 // P is a immutable pass and it will be managed by this
287 // top level manager. Set up analysis resolver to connect them.
288 AnalysisResolver *AR = new AnalysisResolver(*this);
290 initializeAnalysisImpl(P);
291 addImmutablePass(IP);
292 recordAvailableAnalysis(IP);
294 P->assignPassManager(activeStack);
299 MPPassManager *getContainedManager(unsigned N) {
300 assert ( N < PassManagers.size() && "Pass number out of range!");
301 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
307 char PassManagerImpl::ID = 0;
308 } // End of llvm namespace
312 //===----------------------------------------------------------------------===//
313 // TimingInfo Class - This class is used to calculate information about the
314 // amount of time each pass takes to execute. This only happens when
315 // -time-passes is enabled on the command line.
318 class VISIBILITY_HIDDEN TimingInfo {
319 std::map<Pass*, Timer> TimingData;
323 // Use 'create' member to get this.
324 TimingInfo() : TG("... Pass execution timing report ...") {}
326 // TimingDtor - Print out information about timing information
328 // Delete all of the timers...
330 // TimerGroup is deleted next, printing the report.
333 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
334 // to a non null value (if the -time-passes option is enabled) or it leaves it
335 // null. It may be called multiple times.
336 static void createTheTimeInfo();
338 void passStarted(Pass *P) {
340 if (dynamic_cast<PMDataManager *>(P))
343 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
344 if (I == TimingData.end())
345 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
346 I->second.startTimer();
348 void passEnded(Pass *P) {
350 if (dynamic_cast<PMDataManager *>(P))
353 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
354 assert (I != TimingData.end() && "passStarted/passEnded not nested right!");
355 I->second.stopTimer();
359 static TimingInfo *TheTimeInfo;
361 } // End of anon namespace
363 //===----------------------------------------------------------------------===//
364 // PMTopLevelManager implementation
366 /// Initialize top level manager. Create first pass manager.
367 PMTopLevelManager::PMTopLevelManager (enum TopLevelManagerType t) {
370 MPPassManager *MPP = new MPPassManager(1);
371 MPP->setTopLevelManager(this);
373 activeStack.push(MPP);
375 else if (t == TLM_Function) {
376 FPPassManager *FPP = new FPPassManager(1);
377 FPP->setTopLevelManager(this);
379 activeStack.push(FPP);
383 /// Set pass P as the last user of the given analysis passes.
384 void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses,
387 for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(),
388 E = AnalysisPasses.end(); I != E; ++I) {
395 // If AP is the last user of other passes then make P last user of
397 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
398 LUE = LastUser.end(); LUI != LUE; ++LUI) {
399 if (LUI->second == AP)
400 LastUser[LUI->first] = P;
405 /// Collect passes whose last user is P
406 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses,
408 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
409 LUE = LastUser.end(); LUI != LUE; ++LUI)
410 if (LUI->second == P)
411 LastUses.push_back(LUI->first);
414 /// Schedule pass P for execution. Make sure that passes required by
415 /// P are run before P is run. Update analysis info maintained by
416 /// the manager. Remove dead passes. This is a recursive function.
417 void PMTopLevelManager::schedulePass(Pass *P) {
419 // TODO : Allocate function manager for this pass, other wise required set
420 // may be inserted into previous function manager
422 // Give pass a chance to prepare the stage.
423 P->preparePassManager(activeStack);
425 AnalysisUsage AnUsage;
426 P->getAnalysisUsage(AnUsage);
427 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
428 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
429 E = RequiredSet.end(); I != E; ++I) {
431 Pass *AnalysisPass = findAnalysisPass(*I);
433 AnalysisPass = (*I)->createPass();
434 // Schedule this analysis run first only if it is not a lower level
435 // analysis pass. Lower level analsyis passes are run on the fly.
436 if (P->getPotentialPassManagerType () >=
437 AnalysisPass->getPotentialPassManagerType())
438 schedulePass(AnalysisPass);
444 // Now all required passes are available.
448 /// Find the pass that implements Analysis AID. Search immutable
449 /// passes and all pass managers. If desired pass is not found
450 /// then return NULL.
451 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
454 // Check pass managers
455 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
456 E = PassManagers.end(); P == NULL && I != E; ++I) {
457 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
458 assert(PMD && "This is not a PassManager");
459 P = PMD->findAnalysisPass(AID, false);
462 // Check other pass managers
463 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
464 E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
465 P = (*I)->findAnalysisPass(AID, false);
467 for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(),
468 E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
469 const PassInfo *PI = (*I)->getPassInfo();
473 // If Pass not found then check the interfaces implemented by Immutable Pass
475 const std::vector<const PassInfo*> &ImmPI = PI->getInterfacesImplemented();
476 if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end())
484 // Print passes managed by this top level manager.
485 void PMTopLevelManager::dumpPasses() const {
487 if (PassDebugging < Structure)
490 // Print out the immutable passes
491 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
492 ImmutablePasses[i]->dumpPassStructure(0);
495 for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
496 E = PassManagers.end(); I != E; ++I)
497 (*I)->dumpPassStructure(1);
500 void PMTopLevelManager::dumpArguments() const {
502 if (PassDebugging < Arguments)
505 cerr << "Pass Arguments: ";
506 for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
507 E = PassManagers.end(); I != E; ++I) {
508 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
509 assert(PMD && "This is not a PassManager");
510 PMD->dumpPassArguments();
515 void PMTopLevelManager::initializeAllAnalysisInfo() {
517 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
518 E = PassManagers.end(); I != E; ++I) {
519 PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
520 assert(PMD && "This is not a PassManager");
521 PMD->initializeAnalysisInfo();
524 // Initailize other pass managers
525 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
526 E = IndirectPassManagers.end(); I != E; ++I)
527 (*I)->initializeAnalysisInfo();
531 PMTopLevelManager::~PMTopLevelManager() {
532 for (std::vector<Pass *>::iterator I = PassManagers.begin(),
533 E = PassManagers.end(); I != E; ++I)
536 for (std::vector<ImmutablePass *>::iterator
537 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
540 PassManagers.clear();
543 //===----------------------------------------------------------------------===//
544 // PMDataManager implementation
546 /// Return true IFF pass P's required analysis set does not required new
548 bool PMDataManager::manageablePass(Pass *P) {
551 // If this pass is not preserving information that is required by a
552 // pass maintained by higher level pass manager then do not insert
553 // this pass into current manager. Use new manager. For example,
554 // For example, If FunctionPass F is not preserving ModulePass Info M1
555 // that is used by another ModulePass M2 then do not insert F in
556 // current function pass manager.
560 /// Augement AvailableAnalysis by adding analysis made available by pass P.
561 void PMDataManager::recordAvailableAnalysis(Pass *P) {
563 if (const PassInfo *PI = P->getPassInfo()) {
564 AvailableAnalysis[PI] = P;
566 //This pass is the current implementation of all of the interfaces it
567 //implements as well.
568 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
569 for (unsigned i = 0, e = II.size(); i != e; ++i)
570 AvailableAnalysis[II[i]] = P;
574 // Return true if P preserves high level analysis used by other
575 // passes managed by this manager
576 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
578 AnalysisUsage AnUsage;
579 P->getAnalysisUsage(AnUsage);
581 if (AnUsage.getPreservesAll())
584 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
585 for (std::vector<Pass *>::iterator I = HigherLevelAnalysis.begin(),
586 E = HigherLevelAnalysis.end(); I != E; ++I) {
588 if (!dynamic_cast<ImmutablePass*>(P1)
589 && std::find(PreservedSet.begin(), PreservedSet.end(), P1->getPassInfo()) ==
597 /// verifyPreservedAnalysis -- Verify analysis presreved by pass P.
598 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
599 AnalysisUsage AnUsage;
600 P->getAnalysisUsage(AnUsage);
601 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
603 // Verify preserved analysis
604 for (std::vector<AnalysisID>::const_iterator I = PreservedSet.begin(),
605 E = PreservedSet.end(); I != E; ++I) {
607 Pass *AP = findAnalysisPass(AID, true);
609 AP->verifyAnalysis();
613 /// Remove Analyss not preserved by Pass P
614 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
615 AnalysisUsage AnUsage;
616 P->getAnalysisUsage(AnUsage);
617 if (AnUsage.getPreservesAll())
620 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
621 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
622 E = AvailableAnalysis.end(); I != E; ) {
623 std::map<AnalysisID, Pass*>::iterator Info = I++;
624 if (!dynamic_cast<ImmutablePass*>(Info->second)
625 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
627 // Remove this analysis
628 AvailableAnalysis.erase(Info);
631 // Check inherited analysis also. If P is not preserving analysis
632 // provided by parent manager then remove it here.
633 for (unsigned Index = 0; Index < PMT_Last; ++Index) {
635 if (!InheritedAnalysis[Index])
638 for (std::map<AnalysisID, Pass*>::iterator
639 I = InheritedAnalysis[Index]->begin(),
640 E = InheritedAnalysis[Index]->end(); I != E; ) {
641 std::map<AnalysisID, Pass *>::iterator Info = I++;
642 if (!dynamic_cast<ImmutablePass*>(Info->second)
643 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
645 // Remove this analysis
646 InheritedAnalysis[Index]->erase(Info);
652 /// Remove analysis passes that are not used any longer
653 void PMDataManager::removeDeadPasses(Pass *P, std::string Msg,
654 enum PassDebuggingString DBG_STR) {
656 std::vector<Pass *> DeadPasses;
658 // If this is a on the fly manager then it does not have TPM.
662 TPM->collectLastUses(DeadPasses, P);
664 for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
665 E = DeadPasses.end(); I != E; ++I) {
667 dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg);
669 if (TheTimeInfo) TheTimeInfo->passStarted(*I);
670 (*I)->releaseMemory();
671 if (TheTimeInfo) TheTimeInfo->passEnded(*I);
673 std::map<AnalysisID, Pass*>::iterator Pos =
674 AvailableAnalysis.find((*I)->getPassInfo());
676 // It is possible that pass is already removed from the AvailableAnalysis
677 if (Pos != AvailableAnalysis.end())
678 AvailableAnalysis.erase(Pos);
682 /// Add pass P into the PassVector. Update
683 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
684 void PMDataManager::add(Pass *P,
685 bool ProcessAnalysis) {
687 // This manager is going to manage pass P. Set up analysis resolver
689 AnalysisResolver *AR = new AnalysisResolver(*this);
692 // If a FunctionPass F is the last user of ModulePass info M
693 // then the F's manager, not F, records itself as a last user of M.
694 std::vector<Pass *> TransferLastUses;
696 if (ProcessAnalysis) {
698 // At the moment, this pass is the last user of all required passes.
699 std::vector<Pass *> LastUses;
700 SmallVector<Pass *, 8> RequiredPasses;
701 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
703 unsigned PDepth = this->getDepth();
705 collectRequiredAnalysis(RequiredPasses,
706 ReqAnalysisNotAvailable, P);
707 for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(),
708 E = RequiredPasses.end(); I != E; ++I) {
709 Pass *PRequired = *I;
712 PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
713 RDepth = DM.getDepth();
715 if (PDepth == RDepth)
716 LastUses.push_back(PRequired);
717 else if (PDepth > RDepth) {
718 // Let the parent claim responsibility of last use
719 TransferLastUses.push_back(PRequired);
720 // Keep track of higher level analysis used by this manager.
721 HigherLevelAnalysis.push_back(PRequired);
723 assert (0 && "Unable to accomodate Required Pass");
726 // Set P as P's last user until someone starts using P.
727 // However, if P is a Pass Manager then it does not need
728 // to record its last user.
729 if (!dynamic_cast<PMDataManager *>(P))
730 LastUses.push_back(P);
731 TPM->setLastUser(LastUses, P);
733 if (!TransferLastUses.empty()) {
734 Pass *My_PM = dynamic_cast<Pass *>(this);
735 TPM->setLastUser(TransferLastUses, My_PM);
736 TransferLastUses.clear();
739 // Now, take care of required analysises that are not available.
740 for (SmallVector<AnalysisID, 8>::iterator
741 I = ReqAnalysisNotAvailable.begin(),
742 E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
743 Pass *AnalysisPass = (*I)->createPass();
744 this->addLowerLevelRequiredPass(P, AnalysisPass);
747 // Take a note of analysis required and made available by this pass.
748 // Remove the analysis not preserved by this pass
749 removeNotPreservedAnalysis(P);
750 recordAvailableAnalysis(P);
754 PassVector.push_back(P);
758 /// Populate RP with analysis pass that are required by
759 /// pass P and are available. Populate RP_NotAvail with analysis
760 /// pass that are required by pass P but are not available.
761 void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP,
762 SmallVector<AnalysisID, 8> &RP_NotAvail,
764 AnalysisUsage AnUsage;
765 P->getAnalysisUsage(AnUsage);
766 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
767 for (std::vector<AnalysisID>::const_iterator
768 I = RequiredSet.begin(), E = RequiredSet.end();
771 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
772 RP.push_back(AnalysisPass);
774 RP_NotAvail.push_back(AID);
777 const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
778 for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
779 E = IDs.end(); I != E; ++I) {
781 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
782 RP.push_back(AnalysisPass);
784 RP_NotAvail.push_back(AID);
788 // All Required analyses should be available to the pass as it runs! Here
789 // we fill in the AnalysisImpls member of the pass so that it can
790 // successfully use the getAnalysis() method to retrieve the
791 // implementations it needs.
793 void PMDataManager::initializeAnalysisImpl(Pass *P) {
794 AnalysisUsage AnUsage;
795 P->getAnalysisUsage(AnUsage);
797 for (std::vector<const PassInfo *>::const_iterator
798 I = AnUsage.getRequiredSet().begin(),
799 E = AnUsage.getRequiredSet().end(); I != E; ++I) {
800 Pass *Impl = findAnalysisPass(*I, true);
802 // This may be analysis pass that is initialized on the fly.
803 // If that is not the case then it will raise an assert when it is used.
805 AnalysisResolver *AR = P->getResolver();
806 AR->addAnalysisImplsPair(*I, Impl);
810 /// Find the pass that implements Analysis AID. If desired pass is not found
811 /// then return NULL.
812 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
814 // Check if AvailableAnalysis map has one entry.
815 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID);
817 if (I != AvailableAnalysis.end())
820 // Search Parents through TopLevelManager
822 return TPM->findAnalysisPass(AID);
827 // Print list of passes that are last used by P.
828 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
830 std::vector<Pass *> LUses;
832 // If this is a on the fly manager then it does not have TPM.
836 TPM->collectLastUses(LUses, P);
838 for (std::vector<Pass *>::iterator I = LUses.begin(),
839 E = LUses.end(); I != E; ++I) {
840 llvm::cerr << "--" << std::string(Offset*2, ' ');
841 (*I)->dumpPassStructure(0);
845 void PMDataManager::dumpPassArguments() const {
846 for(std::vector<Pass *>::const_iterator I = PassVector.begin(),
847 E = PassVector.end(); I != E; ++I) {
848 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
849 PMD->dumpPassArguments();
851 if (const PassInfo *PI = (*I)->getPassInfo())
852 if (!PI->isAnalysisGroup())
853 cerr << " -" << PI->getPassArgument();
857 void PMDataManager:: dumpPassInfo(Pass *P, enum PassDebuggingString S1,
858 enum PassDebuggingString S2,
860 if (PassDebugging < Executions)
862 cerr << (void*)this << std::string(getDepth()*2+1, ' ');
865 cerr << "Executing Pass '" << P->getPassName();
867 case MODIFICATION_MSG:
868 cerr << "Made Modification '" << P->getPassName();
871 cerr << " Freeing Pass '" << P->getPassName();
877 case ON_BASICBLOCK_MSG:
878 cerr << "' on BasicBlock '" << Msg << "'...\n";
880 case ON_FUNCTION_MSG:
881 cerr << "' on Function '" << Msg << "'...\n";
884 cerr << "' on Module '" << Msg << "'...\n";
887 cerr << "' on Loop " << Msg << "'...\n";
890 cerr << "' on Call Graph " << Msg << "'...\n";
897 void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P,
898 const std::vector<AnalysisID> &Set)
900 if (PassDebugging >= Details && !Set.empty()) {
901 cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
902 for (unsigned i = 0; i != Set.size(); ++i) {
904 cerr << " " << Set[i]->getPassName();
911 PMDataManager::~PMDataManager() {
913 for (std::vector<Pass *>::iterator I = PassVector.begin(),
914 E = PassVector.end(); I != E; ++I)
920 //===----------------------------------------------------------------------===//
921 // NOTE: Is this the right place to define this method ?
922 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
923 Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
924 return PM.findAnalysisPass(ID, dir);
927 Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI,
929 return PM.getOnTheFlyPass(P, AnalysisPI, F);
932 //===----------------------------------------------------------------------===//
933 // BBPassManager implementation
935 /// Execute all of the passes scheduled for execution by invoking
936 /// runOnBasicBlock method. Keep track of whether any of the passes modifies
937 /// the function, and if so, return true.
939 BBPassManager::runOnFunction(Function &F) {
941 if (F.isDeclaration())
944 bool Changed = doInitialization(F);
946 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
947 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
948 BasicBlockPass *BP = getContainedPass(Index);
949 AnalysisUsage AnUsage;
950 BP->getAnalysisUsage(AnUsage);
952 dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, (*I).getName());
953 dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet());
955 initializeAnalysisImpl(BP);
957 if (TheTimeInfo) TheTimeInfo->passStarted(BP);
958 Changed |= BP->runOnBasicBlock(*I);
959 if (TheTimeInfo) TheTimeInfo->passEnded(BP);
962 dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG, (*I).getName());
963 dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet());
965 verifyPreservedAnalysis(BP);
966 removeNotPreservedAnalysis(BP);
967 recordAvailableAnalysis(BP);
968 removeDeadPasses(BP, (*I).getName(), ON_BASICBLOCK_MSG);
971 return Changed |= doFinalization(F);
974 // Implement doInitialization and doFinalization
975 inline bool BBPassManager::doInitialization(Module &M) {
976 bool Changed = false;
978 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
979 BasicBlockPass *BP = getContainedPass(Index);
980 Changed |= BP->doInitialization(M);
986 inline bool BBPassManager::doFinalization(Module &M) {
987 bool Changed = false;
989 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
990 BasicBlockPass *BP = getContainedPass(Index);
991 Changed |= BP->doFinalization(M);
997 inline bool BBPassManager::doInitialization(Function &F) {
998 bool Changed = false;
1000 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1001 BasicBlockPass *BP = getContainedPass(Index);
1002 Changed |= BP->doInitialization(F);
1008 inline bool BBPassManager::doFinalization(Function &F) {
1009 bool Changed = false;
1011 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1012 BasicBlockPass *BP = getContainedPass(Index);
1013 Changed |= BP->doFinalization(F);
1020 //===----------------------------------------------------------------------===//
1021 // FunctionPassManager implementation
1023 /// Create new Function pass manager
1024 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
1025 FPM = new FunctionPassManagerImpl(0);
1026 // FPM is the top level manager.
1027 FPM->setTopLevelManager(FPM);
1029 PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
1030 AnalysisResolver *AR = new AnalysisResolver(*PMD);
1031 FPM->setResolver(AR);
1036 FunctionPassManager::~FunctionPassManager() {
1040 /// add - Add a pass to the queue of passes to run. This passes
1041 /// ownership of the Pass to the PassManager. When the
1042 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1043 /// there is no need to delete the pass. (TODO delete passes.)
1044 /// This implies that all passes MUST be allocated with 'new'.
1045 void FunctionPassManager::add(Pass *P) {
1049 /// run - Execute all of the passes scheduled for execution. Keep
1050 /// track of whether any of the passes modifies the function, and if
1051 /// so, return true.
1053 bool FunctionPassManager::run(Function &F) {
1055 if (MP->materializeFunction(&F, &errstr)) {
1056 cerr << "Error reading bitcode file: " << errstr << "\n";
1063 /// doInitialization - Run all of the initializers for the function passes.
1065 bool FunctionPassManager::doInitialization() {
1066 return FPM->doInitialization(*MP->getModule());
1069 /// doFinalization - Run all of the initializers for the function passes.
1071 bool FunctionPassManager::doFinalization() {
1072 return FPM->doFinalization(*MP->getModule());
1075 //===----------------------------------------------------------------------===//
1076 // FunctionPassManagerImpl implementation
1078 inline bool FunctionPassManagerImpl::doInitialization(Module &M) {
1079 bool Changed = false;
1081 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1082 FPPassManager *FP = getContainedManager(Index);
1083 Changed |= FP->doInitialization(M);
1089 inline bool FunctionPassManagerImpl::doFinalization(Module &M) {
1090 bool Changed = false;
1092 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1093 FPPassManager *FP = getContainedManager(Index);
1094 Changed |= FP->doFinalization(M);
1100 // Execute all the passes managed by this top level manager.
1101 // Return true if any function is modified by a pass.
1102 bool FunctionPassManagerImpl::run(Function &F) {
1104 bool Changed = false;
1106 TimingInfo::createTheTimeInfo();
1111 initializeAllAnalysisInfo();
1112 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1113 FPPassManager *FP = getContainedManager(Index);
1114 Changed |= FP->runOnFunction(F);
1119 //===----------------------------------------------------------------------===//
1120 // FPPassManager implementation
1122 char FPPassManager::ID = 0;
1123 /// Print passes managed by this manager
1124 void FPPassManager::dumpPassStructure(unsigned Offset) {
1125 llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
1126 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1127 FunctionPass *FP = getContainedPass(Index);
1128 FP->dumpPassStructure(Offset + 1);
1129 dumpLastUses(FP, Offset+1);
1134 /// Execute all of the passes scheduled for execution by invoking
1135 /// runOnFunction method. Keep track of whether any of the passes modifies
1136 /// the function, and if so, return true.
1137 bool FPPassManager::runOnFunction(Function &F) {
1139 bool Changed = false;
1141 if (F.isDeclaration())
1144 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1145 FunctionPass *FP = getContainedPass(Index);
1147 AnalysisUsage AnUsage;
1148 FP->getAnalysisUsage(AnUsage);
1150 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
1151 dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet());
1153 initializeAnalysisImpl(FP);
1155 if (TheTimeInfo) TheTimeInfo->passStarted(FP);
1156 Changed |= FP->runOnFunction(F);
1157 if (TheTimeInfo) TheTimeInfo->passEnded(FP);
1160 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
1161 dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet());
1163 verifyPreservedAnalysis(FP);
1164 removeNotPreservedAnalysis(FP);
1165 recordAvailableAnalysis(FP);
1166 removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
1171 bool FPPassManager::runOnModule(Module &M) {
1173 bool Changed = doInitialization(M);
1175 for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1176 this->runOnFunction(*I);
1178 return Changed |= doFinalization(M);
1181 inline bool FPPassManager::doInitialization(Module &M) {
1182 bool Changed = false;
1184 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1185 FunctionPass *FP = getContainedPass(Index);
1186 Changed |= FP->doInitialization(M);
1192 inline bool FPPassManager::doFinalization(Module &M) {
1193 bool Changed = false;
1195 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1196 FunctionPass *FP = getContainedPass(Index);
1197 Changed |= FP->doFinalization(M);
1203 //===----------------------------------------------------------------------===//
1204 // MPPassManager implementation
1206 /// Execute all of the passes scheduled for execution by invoking
1207 /// runOnModule method. Keep track of whether any of the passes modifies
1208 /// the module, and if so, return true.
1210 MPPassManager::runOnModule(Module &M) {
1211 bool Changed = false;
1213 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1214 ModulePass *MP = getContainedPass(Index);
1216 AnalysisUsage AnUsage;
1217 MP->getAnalysisUsage(AnUsage);
1219 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
1220 dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet());
1222 initializeAnalysisImpl(MP);
1224 if (TheTimeInfo) TheTimeInfo->passStarted(MP);
1225 Changed |= MP->runOnModule(M);
1226 if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1229 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1230 M.getModuleIdentifier());
1231 dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet());
1233 verifyPreservedAnalysis(MP);
1234 removeNotPreservedAnalysis(MP);
1235 recordAvailableAnalysis(MP);
1236 removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
1241 /// Add RequiredPass into list of lower level passes required by pass P.
1242 /// RequiredPass is run on the fly by Pass Manager when P requests it
1243 /// through getAnalysis interface.
1244 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1246 assert (P->getPotentialPassManagerType() == PMT_ModulePassManager
1247 && "Unable to handle Pass that requires lower level Analysis pass");
1248 assert ((P->getPotentialPassManagerType() <
1249 RequiredPass->getPotentialPassManagerType())
1250 && "Unable to handle Pass that requires lower level Analysis pass");
1252 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1254 FPP = new FunctionPassManagerImpl(0);
1255 // FPP is the top level manager.
1256 FPP->setTopLevelManager(FPP);
1258 OnTheFlyManagers[P] = FPP;
1260 FPP->add(RequiredPass);
1262 // Register P as the last user of RequiredPass.
1263 std::vector<Pass *> LU;
1264 LU.push_back(RequiredPass);
1265 FPP->setLastUser(LU, P);
1268 /// Return function pass corresponding to PassInfo PI, that is
1269 /// required by module pass MP. Instantiate analysis pass, by using
1270 /// its runOnFunction() for function F.
1271 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI,
1273 AnalysisID AID = PI;
1274 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1275 assert (FPP && "Unable to find on the fly pass");
1278 return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(AID);
1282 //===----------------------------------------------------------------------===//
1283 // PassManagerImpl implementation
1285 /// run - Execute all of the passes scheduled for execution. Keep track of
1286 /// whether any of the passes modifies the module, and if so, return true.
1287 bool PassManagerImpl::run(Module &M) {
1289 bool Changed = false;
1291 TimingInfo::createTheTimeInfo();
1296 initializeAllAnalysisInfo();
1297 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1298 MPPassManager *MP = getContainedManager(Index);
1299 Changed |= MP->runOnModule(M);
1304 //===----------------------------------------------------------------------===//
1305 // PassManager implementation
1307 /// Create new pass manager
1308 PassManager::PassManager() {
1309 PM = new PassManagerImpl(0);
1310 // PM is the top level manager
1311 PM->setTopLevelManager(PM);
1314 PassManager::~PassManager() {
1318 /// add - Add a pass to the queue of passes to run. This passes ownership of
1319 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
1320 /// will be destroyed as well, so there is no need to delete the pass. This
1321 /// implies that all passes MUST be allocated with 'new'.
1323 PassManager::add(Pass *P) {
1327 /// run - Execute all of the passes scheduled for execution. Keep track of
1328 /// whether any of the passes modifies the module, and if so, return true.
1330 PassManager::run(Module &M) {
1334 //===----------------------------------------------------------------------===//
1335 // TimingInfo Class - This class is used to calculate information about the
1336 // amount of time each pass takes to execute. This only happens with
1337 // -time-passes is enabled on the command line.
1339 bool llvm::TimePassesIsEnabled = false;
1340 static cl::opt<bool,true>
1341 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1342 cl::desc("Time each pass, printing elapsed time for each on exit"));
1344 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1345 // a non null value (if the -time-passes option is enabled) or it leaves it
1346 // null. It may be called multiple times.
1347 void TimingInfo::createTheTimeInfo() {
1348 if (!TimePassesIsEnabled || TheTimeInfo) return;
1350 // Constructed the first time this is called, iff -time-passes is enabled.
1351 // This guarantees that the object will be constructed before static globals,
1352 // thus it will be destroyed before them.
1353 static ManagedStatic<TimingInfo> TTI;
1354 TheTimeInfo = &*TTI;
1357 /// If TimingInfo is enabled then start pass timer.
1358 void StartPassTimer(Pass *P) {
1360 TheTimeInfo->passStarted(P);
1363 /// If TimingInfo is enabled then stop pass timer.
1364 void StopPassTimer(Pass *P) {
1366 TheTimeInfo->passEnded(P);
1369 //===----------------------------------------------------------------------===//
1370 // PMStack implementation
1373 // Pop Pass Manager from the stack and clear its analysis info.
1374 void PMStack::pop() {
1376 PMDataManager *Top = this->top();
1377 Top->initializeAnalysisInfo();
1382 // Push PM on the stack and set its top level manager.
1383 void PMStack::push(Pass *P) {
1385 PMDataManager *Top = NULL;
1386 PMDataManager *PM = dynamic_cast<PMDataManager *>(P);
1387 assert (PM && "Unable to push. Pass Manager expected");
1389 if (this->empty()) {
1394 PMTopLevelManager *TPM = Top->getTopLevelManager();
1396 assert (TPM && "Unable to find top level manager");
1397 TPM->addIndirectPassManager(PM);
1398 PM->setTopLevelManager(TPM);
1404 // Dump content of the pass manager stack.
1405 void PMStack::dump() {
1406 for(std::deque<PMDataManager *>::iterator I = S.begin(),
1407 E = S.end(); I != E; ++I) {
1408 Pass *P = dynamic_cast<Pass *>(*I);
1409 printf ("%s ", P->getPassName());
1415 /// Find appropriate Module Pass Manager in the PM Stack and
1416 /// add self into that manager.
1417 void ModulePass::assignPassManager(PMStack &PMS,
1418 PassManagerType PreferredType) {
1420 // Find Module Pass Manager
1421 while(!PMS.empty()) {
1422 PassManagerType TopPMType = PMS.top()->getPassManagerType();
1423 if (TopPMType == PreferredType)
1424 break; // We found desired pass manager
1425 else if (TopPMType > PMT_ModulePassManager)
1426 PMS.pop(); // Pop children pass managers
1431 PMS.top()->add(this);
1434 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1435 /// in the PM Stack and add self into that manager.
1436 void FunctionPass::assignPassManager(PMStack &PMS,
1437 PassManagerType PreferredType) {
1439 // Find Module Pass Manager (TODO : Or Call Graph Pass Manager)
1440 while(!PMS.empty()) {
1441 if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1446 FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1448 // Create new Function Pass Manager
1450 assert(!PMS.empty() && "Unable to create Function Pass Manager");
1451 PMDataManager *PMD = PMS.top();
1453 // [1] Create new Function Pass Manager
1454 FPP = new FPPassManager(PMD->getDepth() + 1);
1456 // [2] Set up new manager's top level manager
1457 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1458 TPM->addIndirectPassManager(FPP);
1460 // [3] Assign manager to manage this new manager. This may create
1461 // and push new managers into PMS
1462 Pass *P = dynamic_cast<Pass *>(FPP);
1464 // If Call Graph Pass Manager is active then use it to manage
1465 // this new Function Pass manager.
1466 if (PMD->getPassManagerType() == PMT_CallGraphPassManager)
1467 P->assignPassManager(PMS, PMT_CallGraphPassManager);
1469 P->assignPassManager(PMS);
1471 // [4] Push new manager into PMS
1475 // Assign FPP as the manager of this pass.
1479 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1480 /// in the PM Stack and add self into that manager.
1481 void BasicBlockPass::assignPassManager(PMStack &PMS,
1482 PassManagerType PreferredType) {
1484 BBPassManager *BBP = NULL;
1486 // Basic Pass Manager is a leaf pass manager. It does not handle
1487 // any other pass manager.
1489 BBP = dynamic_cast<BBPassManager *>(PMS.top());
1492 // If leaf manager is not Basic Block Pass manager then create new
1493 // basic Block Pass manager.
1496 assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1497 PMDataManager *PMD = PMS.top();
1499 // [1] Create new Basic Block Manager
1500 BBP = new BBPassManager(PMD->getDepth() + 1);
1502 // [2] Set up new manager's top level manager
1503 // Basic Block Pass Manager does not live by itself
1504 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1505 TPM->addIndirectPassManager(BBP);
1507 // [3] Assign manager to manage this new manager. This may create
1508 // and push new managers into PMS
1509 Pass *P = dynamic_cast<Pass *>(BBP);
1510 P->assignPassManager(PMS);
1512 // [4] Push new manager into PMS
1516 // Assign BBP as the manager of this pass.