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 /// Remove Analyss not preserved by Pass P
598 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
599 AnalysisUsage AnUsage;
600 P->getAnalysisUsage(AnUsage);
602 if (AnUsage.getPreservesAll())
605 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
606 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
607 E = AvailableAnalysis.end(); I != E; ) {
608 std::map<AnalysisID, Pass*>::iterator Info = I++;
609 if (!dynamic_cast<ImmutablePass*>(Info->second)
610 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
612 // Remove this analysis
613 AvailableAnalysis.erase(Info);
616 // Check inherited analysis also. If P is not preserving analysis
617 // provided by parent manager then remove it here.
618 for (unsigned Index = 0; Index < PMT_Last; ++Index) {
620 if (!InheritedAnalysis[Index])
623 for (std::map<AnalysisID, Pass*>::iterator
624 I = InheritedAnalysis[Index]->begin(),
625 E = InheritedAnalysis[Index]->end(); I != E; ) {
626 std::map<AnalysisID, Pass *>::iterator Info = I++;
627 if (!dynamic_cast<ImmutablePass*>(Info->second)
628 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
630 // Remove this analysis
631 InheritedAnalysis[Index]->erase(Info);
637 /// Remove analysis passes that are not used any longer
638 void PMDataManager::removeDeadPasses(Pass *P, std::string Msg,
639 enum PassDebuggingString DBG_STR) {
641 std::vector<Pass *> DeadPasses;
643 // If this is a on the fly manager then it does not have TPM.
647 TPM->collectLastUses(DeadPasses, P);
649 for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
650 E = DeadPasses.end(); I != E; ++I) {
652 dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg);
654 if (TheTimeInfo) TheTimeInfo->passStarted(*I);
655 (*I)->releaseMemory();
656 if (TheTimeInfo) TheTimeInfo->passEnded(*I);
658 std::map<AnalysisID, Pass*>::iterator Pos =
659 AvailableAnalysis.find((*I)->getPassInfo());
661 // It is possible that pass is already removed from the AvailableAnalysis
662 if (Pos != AvailableAnalysis.end())
663 AvailableAnalysis.erase(Pos);
667 /// Add pass P into the PassVector. Update
668 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
669 void PMDataManager::add(Pass *P,
670 bool ProcessAnalysis) {
672 // This manager is going to manage pass P. Set up analysis resolver
674 AnalysisResolver *AR = new AnalysisResolver(*this);
677 // If a FunctionPass F is the last user of ModulePass info M
678 // then the F's manager, not F, records itself as a last user of M.
679 std::vector<Pass *> TransferLastUses;
681 if (ProcessAnalysis) {
683 // At the moment, this pass is the last user of all required passes.
684 std::vector<Pass *> LastUses;
685 SmallVector<Pass *, 8> RequiredPasses;
686 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
688 unsigned PDepth = this->getDepth();
690 collectRequiredAnalysis(RequiredPasses,
691 ReqAnalysisNotAvailable, P);
692 for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(),
693 E = RequiredPasses.end(); I != E; ++I) {
694 Pass *PRequired = *I;
697 PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
698 RDepth = DM.getDepth();
700 if (PDepth == RDepth)
701 LastUses.push_back(PRequired);
702 else if (PDepth > RDepth) {
703 // Let the parent claim responsibility of last use
704 TransferLastUses.push_back(PRequired);
705 // Keep track of higher level analysis used by this manager.
706 HigherLevelAnalysis.push_back(PRequired);
708 assert (0 && "Unable to accomodate Required Pass");
711 // Set P as P's last user until someone starts using P.
712 // However, if P is a Pass Manager then it does not need
713 // to record its last user.
714 if (!dynamic_cast<PMDataManager *>(P))
715 LastUses.push_back(P);
716 TPM->setLastUser(LastUses, P);
718 if (!TransferLastUses.empty()) {
719 Pass *My_PM = dynamic_cast<Pass *>(this);
720 TPM->setLastUser(TransferLastUses, My_PM);
721 TransferLastUses.clear();
724 // Now, take care of required analysises that are not available.
725 for (SmallVector<AnalysisID, 8>::iterator
726 I = ReqAnalysisNotAvailable.begin(),
727 E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
728 Pass *AnalysisPass = (*I)->createPass();
729 this->addLowerLevelRequiredPass(P, AnalysisPass);
732 // Take a note of analysis required and made available by this pass.
733 // Remove the analysis not preserved by this pass
734 removeNotPreservedAnalysis(P);
735 recordAvailableAnalysis(P);
739 PassVector.push_back(P);
743 /// Populate RP with analysis pass that are required by
744 /// pass P and are available. Populate RP_NotAvail with analysis
745 /// pass that are required by pass P but are not available.
746 void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP,
747 SmallVector<AnalysisID, 8> &RP_NotAvail,
749 AnalysisUsage AnUsage;
750 P->getAnalysisUsage(AnUsage);
751 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
752 for (std::vector<AnalysisID>::const_iterator
753 I = RequiredSet.begin(), E = RequiredSet.end();
756 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
757 RP.push_back(AnalysisPass);
759 RP_NotAvail.push_back(AID);
762 const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
763 for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
764 E = IDs.end(); I != E; ++I) {
766 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
767 RP.push_back(AnalysisPass);
769 RP_NotAvail.push_back(AID);
773 // All Required analyses should be available to the pass as it runs! Here
774 // we fill in the AnalysisImpls member of the pass so that it can
775 // successfully use the getAnalysis() method to retrieve the
776 // implementations it needs.
778 void PMDataManager::initializeAnalysisImpl(Pass *P) {
779 AnalysisUsage AnUsage;
780 P->getAnalysisUsage(AnUsage);
782 for (std::vector<const PassInfo *>::const_iterator
783 I = AnUsage.getRequiredSet().begin(),
784 E = AnUsage.getRequiredSet().end(); I != E; ++I) {
785 Pass *Impl = findAnalysisPass(*I, true);
787 // This may be analysis pass that is initialized on the fly.
788 // If that is not the case then it will raise an assert when it is used.
790 AnalysisResolver *AR = P->getResolver();
791 AR->addAnalysisImplsPair(*I, Impl);
795 /// Find the pass that implements Analysis AID. If desired pass is not found
796 /// then return NULL.
797 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
799 // Check if AvailableAnalysis map has one entry.
800 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID);
802 if (I != AvailableAnalysis.end())
805 // Search Parents through TopLevelManager
807 return TPM->findAnalysisPass(AID);
812 // Print list of passes that are last used by P.
813 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
815 std::vector<Pass *> LUses;
817 // If this is a on the fly manager then it does not have TPM.
821 TPM->collectLastUses(LUses, P);
823 for (std::vector<Pass *>::iterator I = LUses.begin(),
824 E = LUses.end(); I != E; ++I) {
825 llvm::cerr << "--" << std::string(Offset*2, ' ');
826 (*I)->dumpPassStructure(0);
830 void PMDataManager::dumpPassArguments() const {
831 for(std::vector<Pass *>::const_iterator I = PassVector.begin(),
832 E = PassVector.end(); I != E; ++I) {
833 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
834 PMD->dumpPassArguments();
836 if (const PassInfo *PI = (*I)->getPassInfo())
837 if (!PI->isAnalysisGroup())
838 cerr << " -" << PI->getPassArgument();
842 void PMDataManager:: dumpPassInfo(Pass *P, enum PassDebuggingString S1,
843 enum PassDebuggingString S2,
845 if (PassDebugging < Executions)
847 cerr << (void*)this << std::string(getDepth()*2+1, ' ');
850 cerr << "Executing Pass '" << P->getPassName();
852 case MODIFICATION_MSG:
853 cerr << "Made Modification '" << P->getPassName();
856 cerr << " Freeing Pass '" << P->getPassName();
862 case ON_BASICBLOCK_MSG:
863 cerr << "' on BasicBlock '" << Msg << "'...\n";
865 case ON_FUNCTION_MSG:
866 cerr << "' on Function '" << Msg << "'...\n";
869 cerr << "' on Module '" << Msg << "'...\n";
872 cerr << "' on Loop " << Msg << "'...\n";
875 cerr << "' on Call Graph " << Msg << "'...\n";
882 void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P,
883 const std::vector<AnalysisID> &Set)
885 if (PassDebugging >= Details && !Set.empty()) {
886 cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
887 for (unsigned i = 0; i != Set.size(); ++i) {
889 cerr << " " << Set[i]->getPassName();
896 PMDataManager::~PMDataManager() {
898 for (std::vector<Pass *>::iterator I = PassVector.begin(),
899 E = PassVector.end(); I != E; ++I)
905 //===----------------------------------------------------------------------===//
906 // NOTE: Is this the right place to define this method ?
907 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
908 Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
909 return PM.findAnalysisPass(ID, dir);
912 Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI,
914 return PM.getOnTheFlyPass(P, AnalysisPI, F);
917 //===----------------------------------------------------------------------===//
918 // BBPassManager implementation
920 /// Execute all of the passes scheduled for execution by invoking
921 /// runOnBasicBlock method. Keep track of whether any of the passes modifies
922 /// the function, and if so, return true.
924 BBPassManager::runOnFunction(Function &F) {
926 if (F.isDeclaration())
929 bool Changed = doInitialization(F);
931 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
932 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
933 BasicBlockPass *BP = getContainedPass(Index);
934 AnalysisUsage AnUsage;
935 BP->getAnalysisUsage(AnUsage);
937 dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, (*I).getName());
938 dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet());
940 initializeAnalysisImpl(BP);
942 if (TheTimeInfo) TheTimeInfo->passStarted(BP);
943 Changed |= BP->runOnBasicBlock(*I);
944 if (TheTimeInfo) TheTimeInfo->passEnded(BP);
947 dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG, (*I).getName());
948 dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet());
950 removeNotPreservedAnalysis(BP);
951 recordAvailableAnalysis(BP);
952 removeDeadPasses(BP, (*I).getName(), ON_BASICBLOCK_MSG);
955 return Changed |= doFinalization(F);
958 // Implement doInitialization and doFinalization
959 inline bool BBPassManager::doInitialization(Module &M) {
960 bool Changed = false;
962 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
963 BasicBlockPass *BP = getContainedPass(Index);
964 Changed |= BP->doInitialization(M);
970 inline bool BBPassManager::doFinalization(Module &M) {
971 bool Changed = false;
973 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
974 BasicBlockPass *BP = getContainedPass(Index);
975 Changed |= BP->doFinalization(M);
981 inline bool BBPassManager::doInitialization(Function &F) {
982 bool Changed = false;
984 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
985 BasicBlockPass *BP = getContainedPass(Index);
986 Changed |= BP->doInitialization(F);
992 inline bool BBPassManager::doFinalization(Function &F) {
993 bool Changed = false;
995 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
996 BasicBlockPass *BP = getContainedPass(Index);
997 Changed |= BP->doFinalization(F);
1004 //===----------------------------------------------------------------------===//
1005 // FunctionPassManager implementation
1007 /// Create new Function pass manager
1008 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
1009 FPM = new FunctionPassManagerImpl(0);
1010 // FPM is the top level manager.
1011 FPM->setTopLevelManager(FPM);
1013 PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
1014 AnalysisResolver *AR = new AnalysisResolver(*PMD);
1015 FPM->setResolver(AR);
1020 FunctionPassManager::~FunctionPassManager() {
1024 /// add - Add a pass to the queue of passes to run. This passes
1025 /// ownership of the Pass to the PassManager. When the
1026 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1027 /// there is no need to delete the pass. (TODO delete passes.)
1028 /// This implies that all passes MUST be allocated with 'new'.
1029 void FunctionPassManager::add(Pass *P) {
1033 /// run - Execute all of the passes scheduled for execution. Keep
1034 /// track of whether any of the passes modifies the function, and if
1035 /// so, return true.
1037 bool FunctionPassManager::run(Function &F) {
1039 if (MP->materializeFunction(&F, &errstr)) {
1040 cerr << "Error reading bytecode file: " << errstr << "\n";
1047 /// doInitialization - Run all of the initializers for the function passes.
1049 bool FunctionPassManager::doInitialization() {
1050 return FPM->doInitialization(*MP->getModule());
1053 /// doFinalization - Run all of the initializers for the function passes.
1055 bool FunctionPassManager::doFinalization() {
1056 return FPM->doFinalization(*MP->getModule());
1059 //===----------------------------------------------------------------------===//
1060 // FunctionPassManagerImpl implementation
1062 inline bool FunctionPassManagerImpl::doInitialization(Module &M) {
1063 bool Changed = false;
1065 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1066 FPPassManager *FP = getContainedManager(Index);
1067 Changed |= FP->doInitialization(M);
1073 inline bool FunctionPassManagerImpl::doFinalization(Module &M) {
1074 bool Changed = false;
1076 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1077 FPPassManager *FP = getContainedManager(Index);
1078 Changed |= FP->doFinalization(M);
1084 // Execute all the passes managed by this top level manager.
1085 // Return true if any function is modified by a pass.
1086 bool FunctionPassManagerImpl::run(Function &F) {
1088 bool Changed = false;
1090 TimingInfo::createTheTimeInfo();
1095 initializeAllAnalysisInfo();
1096 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1097 FPPassManager *FP = getContainedManager(Index);
1098 Changed |= FP->runOnFunction(F);
1103 //===----------------------------------------------------------------------===//
1104 // FPPassManager implementation
1106 char FPPassManager::ID = 0;
1107 /// Print passes managed by this manager
1108 void FPPassManager::dumpPassStructure(unsigned Offset) {
1109 llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
1110 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1111 FunctionPass *FP = getContainedPass(Index);
1112 FP->dumpPassStructure(Offset + 1);
1113 dumpLastUses(FP, Offset+1);
1118 /// Execute all of the passes scheduled for execution by invoking
1119 /// runOnFunction method. Keep track of whether any of the passes modifies
1120 /// the function, and if so, return true.
1121 bool FPPassManager::runOnFunction(Function &F) {
1123 bool Changed = false;
1125 if (F.isDeclaration())
1128 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1129 FunctionPass *FP = getContainedPass(Index);
1131 AnalysisUsage AnUsage;
1132 FP->getAnalysisUsage(AnUsage);
1134 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
1135 dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet());
1137 initializeAnalysisImpl(FP);
1139 if (TheTimeInfo) TheTimeInfo->passStarted(FP);
1140 Changed |= FP->runOnFunction(F);
1141 if (TheTimeInfo) TheTimeInfo->passEnded(FP);
1144 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
1145 dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet());
1147 removeNotPreservedAnalysis(FP);
1148 recordAvailableAnalysis(FP);
1149 removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
1154 bool FPPassManager::runOnModule(Module &M) {
1156 bool Changed = doInitialization(M);
1158 for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1159 this->runOnFunction(*I);
1161 return Changed |= doFinalization(M);
1164 inline bool FPPassManager::doInitialization(Module &M) {
1165 bool Changed = false;
1167 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1168 FunctionPass *FP = getContainedPass(Index);
1169 Changed |= FP->doInitialization(M);
1175 inline bool FPPassManager::doFinalization(Module &M) {
1176 bool Changed = false;
1178 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1179 FunctionPass *FP = getContainedPass(Index);
1180 Changed |= FP->doFinalization(M);
1186 //===----------------------------------------------------------------------===//
1187 // MPPassManager implementation
1189 /// Execute all of the passes scheduled for execution by invoking
1190 /// runOnModule method. Keep track of whether any of the passes modifies
1191 /// the module, and if so, return true.
1193 MPPassManager::runOnModule(Module &M) {
1194 bool Changed = false;
1196 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1197 ModulePass *MP = getContainedPass(Index);
1199 AnalysisUsage AnUsage;
1200 MP->getAnalysisUsage(AnUsage);
1202 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
1203 dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet());
1205 initializeAnalysisImpl(MP);
1207 if (TheTimeInfo) TheTimeInfo->passStarted(MP);
1208 Changed |= MP->runOnModule(M);
1209 if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1212 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1213 M.getModuleIdentifier());
1214 dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet());
1216 removeNotPreservedAnalysis(MP);
1217 recordAvailableAnalysis(MP);
1218 removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
1223 /// Add RequiredPass into list of lower level passes required by pass P.
1224 /// RequiredPass is run on the fly by Pass Manager when P requests it
1225 /// through getAnalysis interface.
1226 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1228 assert (P->getPotentialPassManagerType() == PMT_ModulePassManager
1229 && "Unable to handle Pass that requires lower level Analysis pass");
1230 assert ((P->getPotentialPassManagerType() <
1231 RequiredPass->getPotentialPassManagerType())
1232 && "Unable to handle Pass that requires lower level Analysis pass");
1234 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1236 FPP = new FunctionPassManagerImpl(0);
1237 // FPP is the top level manager.
1238 FPP->setTopLevelManager(FPP);
1240 OnTheFlyManagers[P] = FPP;
1242 FPP->add(RequiredPass);
1244 // Register P as the last user of RequiredPass.
1245 std::vector<Pass *> LU;
1246 LU.push_back(RequiredPass);
1247 FPP->setLastUser(LU, P);
1250 /// Return function pass corresponding to PassInfo PI, that is
1251 /// required by module pass MP. Instantiate analysis pass, by using
1252 /// its runOnFunction() for function F.
1253 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI,
1255 AnalysisID AID = PI;
1256 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1257 assert (FPP && "Unable to find on the fly pass");
1260 return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(AID);
1264 //===----------------------------------------------------------------------===//
1265 // PassManagerImpl implementation
1267 /// run - Execute all of the passes scheduled for execution. Keep track of
1268 /// whether any of the passes modifies the module, and if so, return true.
1269 bool PassManagerImpl::run(Module &M) {
1271 bool Changed = false;
1273 TimingInfo::createTheTimeInfo();
1278 initializeAllAnalysisInfo();
1279 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1280 MPPassManager *MP = getContainedManager(Index);
1281 Changed |= MP->runOnModule(M);
1286 //===----------------------------------------------------------------------===//
1287 // PassManager implementation
1289 /// Create new pass manager
1290 PassManager::PassManager() {
1291 PM = new PassManagerImpl(0);
1292 // PM is the top level manager
1293 PM->setTopLevelManager(PM);
1296 PassManager::~PassManager() {
1300 /// add - Add a pass to the queue of passes to run. This passes ownership of
1301 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
1302 /// will be destroyed as well, so there is no need to delete the pass. This
1303 /// implies that all passes MUST be allocated with 'new'.
1305 PassManager::add(Pass *P) {
1309 /// run - Execute all of the passes scheduled for execution. Keep track of
1310 /// whether any of the passes modifies the module, and if so, return true.
1312 PassManager::run(Module &M) {
1316 //===----------------------------------------------------------------------===//
1317 // TimingInfo Class - This class is used to calculate information about the
1318 // amount of time each pass takes to execute. This only happens with
1319 // -time-passes is enabled on the command line.
1321 bool llvm::TimePassesIsEnabled = false;
1322 static cl::opt<bool,true>
1323 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1324 cl::desc("Time each pass, printing elapsed time for each on exit"));
1326 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1327 // a non null value (if the -time-passes option is enabled) or it leaves it
1328 // null. It may be called multiple times.
1329 void TimingInfo::createTheTimeInfo() {
1330 if (!TimePassesIsEnabled || TheTimeInfo) return;
1332 // Constructed the first time this is called, iff -time-passes is enabled.
1333 // This guarantees that the object will be constructed before static globals,
1334 // thus it will be destroyed before them.
1335 static ManagedStatic<TimingInfo> TTI;
1336 TheTimeInfo = &*TTI;
1339 /// If TimingInfo is enabled then start pass timer.
1340 void StartPassTimer(Pass *P) {
1342 TheTimeInfo->passStarted(P);
1345 /// If TimingInfo is enabled then stop pass timer.
1346 void StopPassTimer(Pass *P) {
1348 TheTimeInfo->passEnded(P);
1351 //===----------------------------------------------------------------------===//
1352 // PMStack implementation
1355 // Pop Pass Manager from the stack and clear its analysis info.
1356 void PMStack::pop() {
1358 PMDataManager *Top = this->top();
1359 Top->initializeAnalysisInfo();
1364 // Push PM on the stack and set its top level manager.
1365 void PMStack::push(Pass *P) {
1367 PMDataManager *Top = NULL;
1368 PMDataManager *PM = dynamic_cast<PMDataManager *>(P);
1369 assert (PM && "Unable to push. Pass Manager expected");
1371 if (this->empty()) {
1376 PMTopLevelManager *TPM = Top->getTopLevelManager();
1378 assert (TPM && "Unable to find top level manager");
1379 TPM->addIndirectPassManager(PM);
1380 PM->setTopLevelManager(TPM);
1383 AnalysisResolver *AR = new AnalysisResolver(*Top);
1389 // Dump content of the pass manager stack.
1390 void PMStack::dump() {
1391 for(std::deque<PMDataManager *>::iterator I = S.begin(),
1392 E = S.end(); I != E; ++I) {
1393 Pass *P = dynamic_cast<Pass *>(*I);
1394 printf ("%s ", P->getPassName());
1400 /// Find appropriate Module Pass Manager in the PM Stack and
1401 /// add self into that manager.
1402 void ModulePass::assignPassManager(PMStack &PMS,
1403 PassManagerType PreferredType) {
1405 // Find Module Pass Manager
1406 while(!PMS.empty()) {
1407 PassManagerType TopPMType = PMS.top()->getPassManagerType();
1408 if (TopPMType == PreferredType)
1409 break; // We found desired pass manager
1410 else if (TopPMType > PMT_ModulePassManager)
1411 PMS.pop(); // Pop children pass managers
1416 PMS.top()->add(this);
1419 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1420 /// in the PM Stack and add self into that manager.
1421 void FunctionPass::assignPassManager(PMStack &PMS,
1422 PassManagerType PreferredType) {
1424 // Find Module Pass Manager (TODO : Or Call Graph Pass Manager)
1425 while(!PMS.empty()) {
1426 if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1431 FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1433 // Create new Function Pass Manager
1435 assert(!PMS.empty() && "Unable to create Function Pass Manager");
1436 PMDataManager *PMD = PMS.top();
1438 // [1] Create new Function Pass Manager
1439 FPP = new FPPassManager(PMD->getDepth() + 1);
1441 // [2] Set up new manager's top level manager
1442 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1443 TPM->addIndirectPassManager(FPP);
1445 // [3] Assign manager to manage this new manager. This may create
1446 // and push new managers into PMS
1447 Pass *P = dynamic_cast<Pass *>(FPP);
1449 // If Call Graph Pass Manager is active then use it to manage
1450 // this new Function Pass manager.
1451 if (PMD->getPassManagerType() == PMT_CallGraphPassManager)
1452 P->assignPassManager(PMS, PMT_CallGraphPassManager);
1454 P->assignPassManager(PMS);
1456 // [4] Push new manager into PMS
1460 // Assign FPP as the manager of this pass.
1464 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1465 /// in the PM Stack and add self into that manager.
1466 void BasicBlockPass::assignPassManager(PMStack &PMS,
1467 PassManagerType PreferredType) {
1469 BBPassManager *BBP = NULL;
1471 // Basic Pass Manager is a leaf pass manager. It does not handle
1472 // any other pass manager.
1474 BBP = dynamic_cast<BBPassManager *>(PMS.top());
1477 // If leaf manager is not Basic Block Pass manager then create new
1478 // basic Block Pass manager.
1481 assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1482 PMDataManager *PMD = PMS.top();
1484 // [1] Create new Basic Block Manager
1485 BBP = new BBPassManager(PMD->getDepth() + 1);
1487 // [2] Set up new manager's top level manager
1488 // Basic Block Pass Manager does not live by itself
1489 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1490 TPM->addIndirectPassManager(BBP);
1492 // [3] Assign manager to manage this new manager. This may create
1493 // and push new managers into PMS
1494 Pass *P = dynamic_cast<Pass *>(BBP);
1495 P->assignPassManager(PMS);
1497 // [4] Push new manager into PMS
1501 // Assign BBP as the manager of this pass.