1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/System/Mutex.h"
24 #include "llvm/System/Threading.h"
25 #include "llvm/Analysis/Dominators.h"
26 #include "llvm-c/Core.h"
32 // See PassManagers.h for Pass Manager infrastructure overview.
36 //===----------------------------------------------------------------------===//
37 // Pass debugging information. Often it is useful to find out what pass is
38 // running when a crash occurs in a utility. When this library is compiled with
39 // debugging on, a command line option (--debug-pass) is enabled that causes the
40 // pass name to be printed before it executes.
43 // Different debug levels that can be enabled...
45 None, Arguments, Structure, Executions, Details
48 // Always verify dominfo if expensive checking is enabled.
50 bool VerifyDomInfo = true;
52 bool VerifyDomInfo = false;
54 static cl::opt<bool,true>
55 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
56 cl::desc("Verify dominator info (time consuming)"));
58 static cl::opt<enum PassDebugLevel>
59 PassDebugging("debug-pass", cl::Hidden,
60 cl::desc("Print PassManager debugging information"),
62 clEnumVal(None , "disable debug output"),
63 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
64 clEnumVal(Structure , "print pass structure before run()"),
65 clEnumVal(Executions, "print pass name before it is executed"),
66 clEnumVal(Details , "print pass details when it is executed"),
68 } // End of llvm namespace
70 void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
72 OS << "Releasing pass '";
74 OS << "Running pass '";
76 OS << P->getPassName() << "'";
79 OS << " on module '" << M->getModuleIdentifier() << "'.\n";
90 else if (isa<BasicBlock>(V))
96 WriteAsOperand(OS, V, /*PrintTy=*/false, M);
103 //===----------------------------------------------------------------------===//
106 /// BBPassManager manages BasicBlockPass. It batches all the
107 /// pass together and sequence them to process one basic block before
108 /// processing next basic block.
109 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager,
110 public FunctionPass {
114 explicit BBPassManager(int Depth)
115 : PMDataManager(Depth), FunctionPass(&ID) {}
117 /// Execute all of the passes scheduled for execution. Keep track of
118 /// whether any of the passes modifies the function, and if so, return true.
119 bool runOnFunction(Function &F);
121 /// Pass Manager itself does not invalidate any analysis info.
122 void getAnalysisUsage(AnalysisUsage &Info) const {
123 Info.setPreservesAll();
126 bool doInitialization(Module &M);
127 bool doInitialization(Function &F);
128 bool doFinalization(Module &M);
129 bool doFinalization(Function &F);
131 virtual const char *getPassName() const {
132 return "BasicBlock Pass Manager";
135 // Print passes managed by this manager
136 void dumpPassStructure(unsigned Offset) {
137 llvm::cerr << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n";
138 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
139 BasicBlockPass *BP = getContainedPass(Index);
140 BP->dumpPassStructure(Offset + 1);
141 dumpLastUses(BP, Offset+1);
145 BasicBlockPass *getContainedPass(unsigned N) {
146 assert(N < PassVector.size() && "Pass number out of range!");
147 BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
151 virtual PassManagerType getPassManagerType() const {
152 return PMT_BasicBlockPassManager;
156 char BBPassManager::ID = 0;
161 //===----------------------------------------------------------------------===//
162 // FunctionPassManagerImpl
164 /// FunctionPassManagerImpl manages FPPassManagers
165 class FunctionPassManagerImpl : public Pass,
166 public PMDataManager,
167 public PMTopLevelManager {
170 explicit FunctionPassManagerImpl(int Depth) :
171 Pass(&ID), PMDataManager(Depth),
172 PMTopLevelManager(TLM_Function) { }
174 /// add - Add a pass to the queue of passes to run. This passes ownership of
175 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
176 /// will be destroyed as well, so there is no need to delete the pass. This
177 /// implies that all passes MUST be allocated with 'new'.
182 /// run - Execute all of the passes scheduled for execution. Keep track of
183 /// whether any of the passes modifies the module, and if so, return true.
184 bool run(Function &F);
186 /// doInitialization - Run all of the initializers for the function passes.
188 bool doInitialization(Module &M);
190 /// doFinalization - Run all of the finalizers for the function passes.
192 bool doFinalization(Module &M);
194 /// Pass Manager itself does not invalidate any analysis info.
195 void getAnalysisUsage(AnalysisUsage &Info) const {
196 Info.setPreservesAll();
199 inline void addTopLevelPass(Pass *P) {
201 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
203 // P is a immutable pass and it will be managed by this
204 // top level manager. Set up analysis resolver to connect them.
205 AnalysisResolver *AR = new AnalysisResolver(*this);
207 initializeAnalysisImpl(P);
208 addImmutablePass(IP);
209 recordAvailableAnalysis(IP);
211 P->assignPassManager(activeStack);
216 FPPassManager *getContainedManager(unsigned N) {
217 assert(N < PassManagers.size() && "Pass number out of range!");
218 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
223 char FunctionPassManagerImpl::ID = 0;
224 //===----------------------------------------------------------------------===//
227 /// MPPassManager manages ModulePasses and function pass managers.
228 /// It batches all Module passes and function pass managers together and
229 /// sequences them to process one module.
230 class MPPassManager : public Pass, public PMDataManager {
233 explicit MPPassManager(int Depth) :
234 Pass(&ID), PMDataManager(Depth) { }
236 // Delete on the fly managers.
237 virtual ~MPPassManager() {
238 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
239 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
241 FunctionPassManagerImpl *FPP = I->second;
246 /// run - Execute all of the passes scheduled for execution. Keep track of
247 /// whether any of the passes modifies the module, and if so, return true.
248 bool runOnModule(Module &M);
250 /// Pass Manager itself does not invalidate any analysis info.
251 void getAnalysisUsage(AnalysisUsage &Info) const {
252 Info.setPreservesAll();
255 /// Add RequiredPass into list of lower level passes required by pass P.
256 /// RequiredPass is run on the fly by Pass Manager when P requests it
257 /// through getAnalysis interface.
258 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
260 /// Return function pass corresponding to PassInfo PI, that is
261 /// required by module pass MP. Instantiate analysis pass, by using
262 /// its runOnFunction() for function F.
263 virtual Pass* getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F);
265 virtual const char *getPassName() const {
266 return "Module Pass Manager";
269 // Print passes managed by this manager
270 void dumpPassStructure(unsigned Offset) {
271 llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
272 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
273 ModulePass *MP = getContainedPass(Index);
274 MP->dumpPassStructure(Offset + 1);
275 if (FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP])
276 FPP->dumpPassStructure(Offset + 2);
277 dumpLastUses(MP, Offset+1);
281 ModulePass *getContainedPass(unsigned N) {
282 assert(N < PassVector.size() && "Pass number out of range!");
283 return static_cast<ModulePass *>(PassVector[N]);
286 virtual PassManagerType getPassManagerType() const {
287 return PMT_ModulePassManager;
291 /// Collection of on the fly FPPassManagers. These managers manage
292 /// function passes that are required by module passes.
293 std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
296 char MPPassManager::ID = 0;
297 //===----------------------------------------------------------------------===//
301 /// PassManagerImpl manages MPPassManagers
302 class PassManagerImpl : public Pass,
303 public PMDataManager,
304 public PMTopLevelManager {
308 explicit PassManagerImpl(int Depth) :
309 Pass(&ID), PMDataManager(Depth), PMTopLevelManager(TLM_Pass) { }
311 /// add - Add a pass to the queue of passes to run. This passes ownership of
312 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
313 /// will be destroyed as well, so there is no need to delete the pass. This
314 /// implies that all passes MUST be allocated with 'new'.
319 /// run - Execute all of the passes scheduled for execution. Keep track of
320 /// whether any of the passes modifies the module, and if so, return true.
323 /// Pass Manager itself does not invalidate any analysis info.
324 void getAnalysisUsage(AnalysisUsage &Info) const {
325 Info.setPreservesAll();
328 inline void addTopLevelPass(Pass *P) {
329 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
331 // P is a immutable pass and it will be managed by this
332 // top level manager. Set up analysis resolver to connect them.
333 AnalysisResolver *AR = new AnalysisResolver(*this);
335 initializeAnalysisImpl(P);
336 addImmutablePass(IP);
337 recordAvailableAnalysis(IP);
339 P->assignPassManager(activeStack);
343 MPPassManager *getContainedManager(unsigned N) {
344 assert(N < PassManagers.size() && "Pass number out of range!");
345 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
350 char PassManagerImpl::ID = 0;
351 } // End of llvm namespace
355 //===----------------------------------------------------------------------===//
356 /// TimingInfo Class - This class is used to calculate information about the
357 /// amount of time each pass takes to execute. This only happens when
358 /// -time-passes is enabled on the command line.
361 static ManagedStatic<sys::Mutex> TimingInfoMutex;
363 class VISIBILITY_HIDDEN TimingInfo {
364 std::map<Pass*, Timer> TimingData;
368 // Use 'create' member to get this.
369 TimingInfo() : TG("... Pass execution timing report ...") {}
371 // TimingDtor - Print out information about timing information
373 // Delete all of the timers...
375 // TimerGroup is deleted next, printing the report.
378 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
379 // to a non null value (if the -time-passes option is enabled) or it leaves it
380 // null. It may be called multiple times.
381 static void createTheTimeInfo();
383 void passStarted(Pass *P) {
384 if (dynamic_cast<PMDataManager *>(P))
387 if (llvm_is_multithreaded()) TimingInfoMutex->acquire();
388 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
389 if (I == TimingData.end())
390 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
391 I->second.startTimer();
392 if (llvm_is_multithreaded()) TimingInfoMutex->release();
394 void passEnded(Pass *P) {
395 if (dynamic_cast<PMDataManager *>(P))
398 if (llvm_is_multithreaded()) TimingInfoMutex->acquire();
399 std::map<Pass*, Timer>::iterator I = TimingData.find(P);
400 assert(I != TimingData.end() && "passStarted/passEnded not nested right!");
401 I->second.stopTimer();
402 if (llvm_is_multithreaded()) TimingInfoMutex->release();
406 } // End of anon namespace
408 static TimingInfo *TheTimeInfo;
410 //===----------------------------------------------------------------------===//
411 // PMTopLevelManager implementation
413 /// Initialize top level manager. Create first pass manager.
414 PMTopLevelManager::PMTopLevelManager(enum TopLevelManagerType t) {
416 MPPassManager *MPP = new MPPassManager(1);
417 MPP->setTopLevelManager(this);
419 activeStack.push(MPP);
420 } else if (t == TLM_Function) {
421 FPPassManager *FPP = new FPPassManager(1);
422 FPP->setTopLevelManager(this);
424 activeStack.push(FPP);
428 /// Set pass P as the last user of the given analysis passes.
429 void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses,
431 for (SmallVector<Pass *, 12>::iterator I = AnalysisPasses.begin(),
432 E = AnalysisPasses.end(); I != E; ++I) {
439 // If AP is the last user of other passes then make P last user of
441 for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
442 LUE = LastUser.end(); LUI != LUE; ++LUI) {
443 if (LUI->second == AP)
444 // DenseMap iterator is not invalidated here because
445 // this is just updating exisitng entry.
446 LastUser[LUI->first] = P;
451 /// Collect passes whose last user is P
452 void PMTopLevelManager::collectLastUses(SmallVector<Pass *, 12> &LastUses,
454 DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
455 InversedLastUser.find(P);
456 if (DMI == InversedLastUser.end())
459 SmallPtrSet<Pass *, 8> &LU = DMI->second;
460 for (SmallPtrSet<Pass *, 8>::iterator I = LU.begin(),
461 E = LU.end(); I != E; ++I) {
462 LastUses.push_back(*I);
467 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
468 AnalysisUsage *AnUsage = NULL;
469 DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.find(P);
470 if (DMI != AnUsageMap.end())
471 AnUsage = DMI->second;
473 AnUsage = new AnalysisUsage();
474 P->getAnalysisUsage(*AnUsage);
475 AnUsageMap[P] = AnUsage;
480 /// Schedule pass P for execution. Make sure that passes required by
481 /// P are run before P is run. Update analysis info maintained by
482 /// the manager. Remove dead passes. This is a recursive function.
483 void PMTopLevelManager::schedulePass(Pass *P) {
485 // TODO : Allocate function manager for this pass, other wise required set
486 // may be inserted into previous function manager
488 // Give pass a chance to prepare the stage.
489 P->preparePassManager(activeStack);
491 // If P is an analysis pass and it is available then do not
492 // generate the analysis again. Stale analysis info should not be
493 // available at this point.
494 if (P->getPassInfo() &&
495 P->getPassInfo()->isAnalysis() && findAnalysisPass(P->getPassInfo())) {
500 AnalysisUsage *AnUsage = findAnalysisUsage(P);
502 bool checkAnalysis = true;
503 while (checkAnalysis) {
504 checkAnalysis = false;
506 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
507 for (AnalysisUsage::VectorType::const_iterator I = RequiredSet.begin(),
508 E = RequiredSet.end(); I != E; ++I) {
510 Pass *AnalysisPass = findAnalysisPass(*I);
512 AnalysisPass = (*I)->createPass();
513 if (P->getPotentialPassManagerType () ==
514 AnalysisPass->getPotentialPassManagerType())
515 // Schedule analysis pass that is managed by the same pass manager.
516 schedulePass(AnalysisPass);
517 else if (P->getPotentialPassManagerType () >
518 AnalysisPass->getPotentialPassManagerType()) {
519 // Schedule analysis pass that is managed by a new manager.
520 schedulePass(AnalysisPass);
521 // Recheck analysis passes to ensure that required analysises that
522 // are already checked are still available.
523 checkAnalysis = true;
526 // Do not schedule this analysis. Lower level analsyis
527 // passes are run on the fly.
533 // Now all required passes are available.
537 /// Find the pass that implements Analysis AID. Search immutable
538 /// passes and all pass managers. If desired pass is not found
539 /// then return NULL.
540 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
543 // Check pass managers
544 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
545 E = PassManagers.end(); P == NULL && I != E; ++I) {
546 PMDataManager *PMD = *I;
547 P = PMD->findAnalysisPass(AID, false);
550 // Check other pass managers
551 for (SmallVector<PMDataManager *, 8>::iterator
552 I = IndirectPassManagers.begin(),
553 E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
554 P = (*I)->findAnalysisPass(AID, false);
556 for (SmallVector<ImmutablePass *, 8>::iterator I = ImmutablePasses.begin(),
557 E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
558 const PassInfo *PI = (*I)->getPassInfo();
562 // If Pass not found then check the interfaces implemented by Immutable Pass
564 const std::vector<const PassInfo*> &ImmPI =
565 PI->getInterfacesImplemented();
566 if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end())
574 // Print passes managed by this top level manager.
575 void PMTopLevelManager::dumpPasses() const {
577 if (PassDebugging < Structure)
580 // Print out the immutable passes
581 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
582 ImmutablePasses[i]->dumpPassStructure(0);
585 // Every class that derives from PMDataManager also derives from Pass
586 // (sometimes indirectly), but there's no inheritance relationship
587 // between PMDataManager and Pass, so we have to dynamic_cast to get
588 // from a PMDataManager* to a Pass*.
589 for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(),
590 E = PassManagers.end(); I != E; ++I)
591 dynamic_cast<Pass *>(*I)->dumpPassStructure(1);
594 void PMTopLevelManager::dumpArguments() const {
596 if (PassDebugging < Arguments)
599 cerr << "Pass Arguments: ";
600 for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(),
601 E = PassManagers.end(); I != E; ++I)
602 (*I)->dumpPassArguments();
606 void PMTopLevelManager::initializeAllAnalysisInfo() {
607 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
608 E = PassManagers.end(); I != E; ++I)
609 (*I)->initializeAnalysisInfo();
611 // Initailize other pass managers
612 for (SmallVector<PMDataManager *, 8>::iterator I = IndirectPassManagers.begin(),
613 E = IndirectPassManagers.end(); I != E; ++I)
614 (*I)->initializeAnalysisInfo();
616 for (DenseMap<Pass *, Pass *>::iterator DMI = LastUser.begin(),
617 DME = LastUser.end(); DMI != DME; ++DMI) {
618 DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator InvDMI =
619 InversedLastUser.find(DMI->second);
620 if (InvDMI != InversedLastUser.end()) {
621 SmallPtrSet<Pass *, 8> &L = InvDMI->second;
622 L.insert(DMI->first);
624 SmallPtrSet<Pass *, 8> L; L.insert(DMI->first);
625 InversedLastUser[DMI->second] = L;
631 PMTopLevelManager::~PMTopLevelManager() {
632 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
633 E = PassManagers.end(); I != E; ++I)
636 for (SmallVector<ImmutablePass *, 8>::iterator
637 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
640 for (DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.begin(),
641 DME = AnUsageMap.end(); DMI != DME; ++DMI)
645 //===----------------------------------------------------------------------===//
646 // PMDataManager implementation
648 /// Augement AvailableAnalysis by adding analysis made available by pass P.
649 void PMDataManager::recordAvailableAnalysis(Pass *P) {
650 const PassInfo *PI = P->getPassInfo();
653 AvailableAnalysis[PI] = P;
655 //This pass is the current implementation of all of the interfaces it
656 //implements as well.
657 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
658 for (unsigned i = 0, e = II.size(); i != e; ++i)
659 AvailableAnalysis[II[i]] = P;
662 // Return true if P preserves high level analysis used by other
663 // passes managed by this manager
664 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
665 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
666 if (AnUsage->getPreservesAll())
669 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
670 for (SmallVector<Pass *, 8>::iterator I = HigherLevelAnalysis.begin(),
671 E = HigherLevelAnalysis.end(); I != E; ++I) {
673 if (!dynamic_cast<ImmutablePass*>(P1) &&
674 std::find(PreservedSet.begin(), PreservedSet.end(),
675 P1->getPassInfo()) ==
683 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
684 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
685 // Don't do this unless assertions are enabled.
689 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
690 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
692 // Verify preserved analysis
693 for (AnalysisUsage::VectorType::const_iterator I = PreservedSet.begin(),
694 E = PreservedSet.end(); I != E; ++I) {
696 if (Pass *AP = findAnalysisPass(AID, true))
697 AP->verifyAnalysis();
701 /// verifyDomInfo - Verify dominator information if it is available.
702 void PMDataManager::verifyDomInfo(Pass &P, Function &F) {
703 if (!VerifyDomInfo || !P.getResolver())
706 DominatorTree *DT = P.getAnalysisIfAvailable<DominatorTree>();
710 DominatorTree OtherDT;
711 OtherDT.getBase().recalculate(F);
712 if (DT->compare(OtherDT)) {
713 cerr << "Dominator Information for " << F.getNameStart() << "\n";
714 cerr << "Pass '" << P.getPassName() << "'\n";
715 cerr << "----- Valid -----\n";
717 cerr << "----- Invalid -----\n";
719 assert(0 && "Invalid dominator info");
722 DominanceFrontier *DF = P.getAnalysisIfAvailable<DominanceFrontier>();
726 DominanceFrontier OtherDF;
727 std::vector<BasicBlock*> DTRoots = DT->getRoots();
728 OtherDF.calculate(*DT, DT->getNode(DTRoots[0]));
729 if (DF->compare(OtherDF)) {
730 cerr << "Dominator Information for " << F.getNameStart() << "\n";
731 cerr << "Pass '" << P.getPassName() << "'\n";
732 cerr << "----- Valid -----\n";
734 cerr << "----- Invalid -----\n";
736 assert(0 && "Invalid dominator info");
740 /// Remove Analysis not preserved by Pass P
741 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
742 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
743 if (AnUsage->getPreservesAll())
746 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
747 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
748 E = AvailableAnalysis.end(); I != E; ) {
749 std::map<AnalysisID, Pass*>::iterator Info = I++;
750 if (!dynamic_cast<ImmutablePass*>(Info->second)
751 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
752 PreservedSet.end()) {
753 // Remove this analysis
754 if (PassDebugging >= Details) {
755 Pass *S = Info->second;
756 cerr << " -- '" << P->getPassName() << "' is not preserving '";
757 cerr << S->getPassName() << "'\n";
759 AvailableAnalysis.erase(Info);
763 // Check inherited analysis also. If P is not preserving analysis
764 // provided by parent manager then remove it here.
765 for (unsigned Index = 0; Index < PMT_Last; ++Index) {
767 if (!InheritedAnalysis[Index])
770 for (std::map<AnalysisID, Pass*>::iterator
771 I = InheritedAnalysis[Index]->begin(),
772 E = InheritedAnalysis[Index]->end(); I != E; ) {
773 std::map<AnalysisID, Pass *>::iterator Info = I++;
774 if (!dynamic_cast<ImmutablePass*>(Info->second) &&
775 std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
777 // Remove this analysis
778 InheritedAnalysis[Index]->erase(Info);
783 /// Remove analysis passes that are not used any longer
784 void PMDataManager::removeDeadPasses(Pass *P, const char *Msg,
785 enum PassDebuggingString DBG_STR) {
787 SmallVector<Pass *, 12> DeadPasses;
789 // If this is a on the fly manager then it does not have TPM.
793 TPM->collectLastUses(DeadPasses, P);
795 if (PassDebugging >= Details && !DeadPasses.empty()) {
796 cerr << " -*- '" << P->getPassName();
797 cerr << "' is the last user of following pass instances.";
798 cerr << " Free these instances\n";
801 for (SmallVector<Pass *, 12>::iterator I = DeadPasses.begin(),
802 E = DeadPasses.end(); I != E; ++I) {
804 dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg);
807 // If the pass crashes releasing memory, remember this.
808 PassManagerPrettyStackEntry X(*I);
810 if (TheTimeInfo) TheTimeInfo->passStarted(*I);
811 (*I)->releaseMemory();
812 if (TheTimeInfo) TheTimeInfo->passEnded(*I);
814 if (const PassInfo *PI = (*I)->getPassInfo()) {
815 std::map<AnalysisID, Pass*>::iterator Pos =
816 AvailableAnalysis.find(PI);
818 // It is possible that pass is already removed from the AvailableAnalysis
819 if (Pos != AvailableAnalysis.end())
820 AvailableAnalysis.erase(Pos);
822 // Remove all interfaces this pass implements, for which it is also
823 // listed as the available implementation.
824 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
825 for (unsigned i = 0, e = II.size(); i != e; ++i) {
826 Pos = AvailableAnalysis.find(II[i]);
827 if (Pos != AvailableAnalysis.end() && Pos->second == *I)
828 AvailableAnalysis.erase(Pos);
834 /// Add pass P into the PassVector. Update
835 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
836 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
837 // This manager is going to manage pass P. Set up analysis resolver
839 AnalysisResolver *AR = new AnalysisResolver(*this);
842 // If a FunctionPass F is the last user of ModulePass info M
843 // then the F's manager, not F, records itself as a last user of M.
844 SmallVector<Pass *, 12> TransferLastUses;
846 if (!ProcessAnalysis) {
848 PassVector.push_back(P);
852 // At the moment, this pass is the last user of all required passes.
853 SmallVector<Pass *, 12> LastUses;
854 SmallVector<Pass *, 8> RequiredPasses;
855 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
857 unsigned PDepth = this->getDepth();
859 collectRequiredAnalysis(RequiredPasses,
860 ReqAnalysisNotAvailable, P);
861 for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(),
862 E = RequiredPasses.end(); I != E; ++I) {
863 Pass *PRequired = *I;
866 assert(PRequired->getResolver() && "Analysis Resolver is not set");
867 PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
868 RDepth = DM.getDepth();
870 if (PDepth == RDepth)
871 LastUses.push_back(PRequired);
872 else if (PDepth > RDepth) {
873 // Let the parent claim responsibility of last use
874 TransferLastUses.push_back(PRequired);
875 // Keep track of higher level analysis used by this manager.
876 HigherLevelAnalysis.push_back(PRequired);
878 assert(0 && "Unable to accomodate Required Pass");
881 // Set P as P's last user until someone starts using P.
882 // However, if P is a Pass Manager then it does not need
883 // to record its last user.
884 if (!dynamic_cast<PMDataManager *>(P))
885 LastUses.push_back(P);
886 TPM->setLastUser(LastUses, P);
888 if (!TransferLastUses.empty()) {
889 Pass *My_PM = dynamic_cast<Pass *>(this);
890 TPM->setLastUser(TransferLastUses, My_PM);
891 TransferLastUses.clear();
894 // Now, take care of required analysises that are not available.
895 for (SmallVector<AnalysisID, 8>::iterator
896 I = ReqAnalysisNotAvailable.begin(),
897 E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
898 Pass *AnalysisPass = (*I)->createPass();
899 this->addLowerLevelRequiredPass(P, AnalysisPass);
902 // Take a note of analysis required and made available by this pass.
903 // Remove the analysis not preserved by this pass
904 removeNotPreservedAnalysis(P);
905 recordAvailableAnalysis(P);
908 PassVector.push_back(P);
912 /// Populate RP with analysis pass that are required by
913 /// pass P and are available. Populate RP_NotAvail with analysis
914 /// pass that are required by pass P but are not available.
915 void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP,
916 SmallVector<AnalysisID, 8> &RP_NotAvail,
918 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
919 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
920 for (AnalysisUsage::VectorType::const_iterator
921 I = RequiredSet.begin(), E = RequiredSet.end(); I != E; ++I) {
922 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
923 RP.push_back(AnalysisPass);
925 RP_NotAvail.push_back(*I);
928 const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
929 for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(),
930 E = IDs.end(); I != E; ++I) {
931 if (Pass *AnalysisPass = findAnalysisPass(*I, true))
932 RP.push_back(AnalysisPass);
934 RP_NotAvail.push_back(*I);
938 // All Required analyses should be available to the pass as it runs! Here
939 // we fill in the AnalysisImpls member of the pass so that it can
940 // successfully use the getAnalysis() method to retrieve the
941 // implementations it needs.
943 void PMDataManager::initializeAnalysisImpl(Pass *P) {
944 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
946 for (AnalysisUsage::VectorType::const_iterator
947 I = AnUsage->getRequiredSet().begin(),
948 E = AnUsage->getRequiredSet().end(); I != E; ++I) {
949 Pass *Impl = findAnalysisPass(*I, true);
951 // This may be analysis pass that is initialized on the fly.
952 // If that is not the case then it will raise an assert when it is used.
954 AnalysisResolver *AR = P->getResolver();
955 assert(AR && "Analysis Resolver is not set");
956 AR->addAnalysisImplsPair(*I, Impl);
960 /// Find the pass that implements Analysis AID. If desired pass is not found
961 /// then return NULL.
962 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
964 // Check if AvailableAnalysis map has one entry.
965 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID);
967 if (I != AvailableAnalysis.end())
970 // Search Parents through TopLevelManager
972 return TPM->findAnalysisPass(AID);
977 // Print list of passes that are last used by P.
978 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
980 SmallVector<Pass *, 12> LUses;
982 // If this is a on the fly manager then it does not have TPM.
986 TPM->collectLastUses(LUses, P);
988 for (SmallVector<Pass *, 12>::iterator I = LUses.begin(),
989 E = LUses.end(); I != E; ++I) {
990 llvm::cerr << "--" << std::string(Offset*2, ' ');
991 (*I)->dumpPassStructure(0);
995 void PMDataManager::dumpPassArguments() const {
996 for (SmallVector<Pass *, 8>::const_iterator I = PassVector.begin(),
997 E = PassVector.end(); I != E; ++I) {
998 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
999 PMD->dumpPassArguments();
1001 if (const PassInfo *PI = (*I)->getPassInfo())
1002 if (!PI->isAnalysisGroup())
1003 cerr << " -" << PI->getPassArgument();
1007 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
1008 enum PassDebuggingString S2,
1010 if (PassDebugging < Executions)
1012 cerr << (void*)this << std::string(getDepth()*2+1, ' ');
1015 cerr << "Executing Pass '" << P->getPassName();
1017 case MODIFICATION_MSG:
1018 cerr << "Made Modification '" << P->getPassName();
1021 cerr << " Freeing Pass '" << P->getPassName();
1027 case ON_BASICBLOCK_MSG:
1028 cerr << "' on BasicBlock '" << Msg << "'...\n";
1030 case ON_FUNCTION_MSG:
1031 cerr << "' on Function '" << Msg << "'...\n";
1034 cerr << "' on Module '" << Msg << "'...\n";
1037 cerr << "' on Loop " << Msg << "'...\n";
1040 cerr << "' on Call Graph " << Msg << "'...\n";
1047 void PMDataManager::dumpRequiredSet(const Pass *P) const {
1048 if (PassDebugging < Details)
1051 AnalysisUsage analysisUsage;
1052 P->getAnalysisUsage(analysisUsage);
1053 dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
1056 void PMDataManager::dumpPreservedSet(const Pass *P) const {
1057 if (PassDebugging < Details)
1060 AnalysisUsage analysisUsage;
1061 P->getAnalysisUsage(analysisUsage);
1062 dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
1065 void PMDataManager::dumpAnalysisUsage(const char *Msg, const Pass *P,
1066 const AnalysisUsage::VectorType &Set) const {
1067 assert(PassDebugging >= Details);
1070 cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
1071 for (unsigned i = 0; i != Set.size(); ++i) {
1073 cerr << " " << Set[i]->getPassName();
1078 /// Add RequiredPass into list of lower level passes required by pass P.
1079 /// RequiredPass is run on the fly by Pass Manager when P requests it
1080 /// through getAnalysis interface.
1081 /// This should be handled by specific pass manager.
1082 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1084 TPM->dumpArguments();
1088 // Module Level pass may required Function Level analysis info
1089 // (e.g. dominator info). Pass manager uses on the fly function pass manager
1090 // to provide this on demand. In that case, in Pass manager terminology,
1091 // module level pass is requiring lower level analysis info managed by
1092 // lower level pass manager.
1094 // When Pass manager is not able to order required analysis info, Pass manager
1095 // checks whether any lower level manager will be able to provide this
1096 // analysis info on demand or not.
1098 cerr << "Unable to schedule '" << RequiredPass->getPassName();
1099 cerr << "' required by '" << P->getPassName() << "'\n";
1101 assert(0 && "Unable to schedule pass");
1105 PMDataManager::~PMDataManager() {
1106 for (SmallVector<Pass *, 8>::iterator I = PassVector.begin(),
1107 E = PassVector.end(); I != E; ++I)
1111 //===----------------------------------------------------------------------===//
1112 // NOTE: Is this the right place to define this method ?
1113 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
1114 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
1115 return PM.findAnalysisPass(ID, dir);
1118 Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI,
1120 return PM.getOnTheFlyPass(P, AnalysisPI, F);
1123 //===----------------------------------------------------------------------===//
1124 // BBPassManager implementation
1126 /// Execute all of the passes scheduled for execution by invoking
1127 /// runOnBasicBlock method. Keep track of whether any of the passes modifies
1128 /// the function, and if so, return true.
1129 bool BBPassManager::runOnFunction(Function &F) {
1130 if (F.isDeclaration())
1133 bool Changed = doInitialization(F);
1135 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
1136 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1137 BasicBlockPass *BP = getContainedPass(Index);
1139 dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getNameStart());
1140 dumpRequiredSet(BP);
1142 initializeAnalysisImpl(BP);
1145 // If the pass crashes, remember this.
1146 PassManagerPrettyStackEntry X(BP, *I);
1148 if (TheTimeInfo) TheTimeInfo->passStarted(BP);
1149 Changed |= BP->runOnBasicBlock(*I);
1150 if (TheTimeInfo) TheTimeInfo->passEnded(BP);
1154 dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
1156 dumpPreservedSet(BP);
1158 verifyPreservedAnalysis(BP);
1159 removeNotPreservedAnalysis(BP);
1160 recordAvailableAnalysis(BP);
1161 removeDeadPasses(BP, I->getNameStart(), ON_BASICBLOCK_MSG);
1164 return Changed |= doFinalization(F);
1167 // Implement doInitialization and doFinalization
1168 bool BBPassManager::doInitialization(Module &M) {
1169 bool Changed = false;
1171 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1172 Changed |= getContainedPass(Index)->doInitialization(M);
1177 bool BBPassManager::doFinalization(Module &M) {
1178 bool Changed = false;
1180 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1181 Changed |= getContainedPass(Index)->doFinalization(M);
1186 bool BBPassManager::doInitialization(Function &F) {
1187 bool Changed = false;
1189 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1190 BasicBlockPass *BP = getContainedPass(Index);
1191 Changed |= BP->doInitialization(F);
1197 bool BBPassManager::doFinalization(Function &F) {
1198 bool Changed = false;
1200 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1201 BasicBlockPass *BP = getContainedPass(Index);
1202 Changed |= BP->doFinalization(F);
1209 //===----------------------------------------------------------------------===//
1210 // FunctionPassManager implementation
1212 /// Create new Function pass manager
1213 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
1214 FPM = new FunctionPassManagerImpl(0);
1215 // FPM is the top level manager.
1216 FPM->setTopLevelManager(FPM);
1218 AnalysisResolver *AR = new AnalysisResolver(*FPM);
1219 FPM->setResolver(AR);
1224 FunctionPassManager::~FunctionPassManager() {
1228 /// add - Add a pass to the queue of passes to run. This passes
1229 /// ownership of the Pass to the PassManager. When the
1230 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1231 /// there is no need to delete the pass. (TODO delete passes.)
1232 /// This implies that all passes MUST be allocated with 'new'.
1233 void FunctionPassManager::add(Pass *P) {
1237 /// run - Execute all of the passes scheduled for execution. Keep
1238 /// track of whether any of the passes modifies the function, and if
1239 /// so, return true.
1241 bool FunctionPassManager::run(Function &F) {
1243 if (MP->materializeFunction(&F, &errstr)) {
1244 cerr << "Error reading bitcode file: " << errstr << "\n";
1251 /// doInitialization - Run all of the initializers for the function passes.
1253 bool FunctionPassManager::doInitialization() {
1254 return FPM->doInitialization(*MP->getModule());
1257 /// doFinalization - Run all of the finalizers for the function passes.
1259 bool FunctionPassManager::doFinalization() {
1260 return FPM->doFinalization(*MP->getModule());
1263 //===----------------------------------------------------------------------===//
1264 // FunctionPassManagerImpl implementation
1266 bool FunctionPassManagerImpl::doInitialization(Module &M) {
1267 bool Changed = false;
1269 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1270 Changed |= getContainedManager(Index)->doInitialization(M);
1275 bool FunctionPassManagerImpl::doFinalization(Module &M) {
1276 bool Changed = false;
1278 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1279 Changed |= getContainedManager(Index)->doFinalization(M);
1284 /// cleanup - After running all passes, clean up pass manager cache.
1285 void FPPassManager::cleanup() {
1286 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1287 FunctionPass *FP = getContainedPass(Index);
1288 AnalysisResolver *AR = FP->getResolver();
1289 assert(AR && "Analysis Resolver is not set");
1290 AR->clearAnalysisImpls();
1294 // Execute all the passes managed by this top level manager.
1295 // Return true if any function is modified by a pass.
1296 bool FunctionPassManagerImpl::run(Function &F) {
1297 bool Changed = false;
1298 TimingInfo::createTheTimeInfo();
1303 initializeAllAnalysisInfo();
1304 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1305 Changed |= getContainedManager(Index)->runOnFunction(F);
1307 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1308 getContainedManager(Index)->cleanup();
1313 //===----------------------------------------------------------------------===//
1314 // FPPassManager implementation
1316 char FPPassManager::ID = 0;
1317 /// Print passes managed by this manager
1318 void FPPassManager::dumpPassStructure(unsigned Offset) {
1319 llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
1320 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1321 FunctionPass *FP = getContainedPass(Index);
1322 FP->dumpPassStructure(Offset + 1);
1323 dumpLastUses(FP, Offset+1);
1328 /// Execute all of the passes scheduled for execution by invoking
1329 /// runOnFunction method. Keep track of whether any of the passes modifies
1330 /// the function, and if so, return true.
1331 bool FPPassManager::runOnFunction(Function &F) {
1332 if (F.isDeclaration())
1335 bool Changed = false;
1337 // Collect inherited analysis from Module level pass manager.
1338 populateInheritedAnalysis(TPM->activeStack);
1340 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1341 FunctionPass *FP = getContainedPass(Index);
1343 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getNameStart());
1344 dumpRequiredSet(FP);
1346 initializeAnalysisImpl(FP);
1349 PassManagerPrettyStackEntry X(FP, F);
1351 if (TheTimeInfo) TheTimeInfo->passStarted(FP);
1352 Changed |= FP->runOnFunction(F);
1353 if (TheTimeInfo) TheTimeInfo->passEnded(FP);
1357 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getNameStart());
1358 dumpPreservedSet(FP);
1360 verifyPreservedAnalysis(FP);
1361 removeNotPreservedAnalysis(FP);
1362 recordAvailableAnalysis(FP);
1363 removeDeadPasses(FP, F.getNameStart(), ON_FUNCTION_MSG);
1365 // If dominator information is available then verify the info if requested.
1366 verifyDomInfo(*FP, F);
1371 bool FPPassManager::runOnModule(Module &M) {
1372 bool Changed = doInitialization(M);
1374 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1377 return Changed |= doFinalization(M);
1380 bool FPPassManager::doInitialization(Module &M) {
1381 bool Changed = false;
1383 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1384 Changed |= getContainedPass(Index)->doInitialization(M);
1389 bool FPPassManager::doFinalization(Module &M) {
1390 bool Changed = false;
1392 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1393 Changed |= getContainedPass(Index)->doFinalization(M);
1398 //===----------------------------------------------------------------------===//
1399 // MPPassManager implementation
1401 /// Execute all of the passes scheduled for execution by invoking
1402 /// runOnModule method. Keep track of whether any of the passes modifies
1403 /// the module, and if so, return true.
1405 MPPassManager::runOnModule(Module &M) {
1406 bool Changed = false;
1408 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1409 ModulePass *MP = getContainedPass(Index);
1411 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG,
1412 M.getModuleIdentifier().c_str());
1413 dumpRequiredSet(MP);
1415 initializeAnalysisImpl(MP);
1418 PassManagerPrettyStackEntry X(MP, M);
1419 if (TheTimeInfo) TheTimeInfo->passStarted(MP);
1420 Changed |= MP->runOnModule(M);
1421 if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1425 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1426 M.getModuleIdentifier().c_str());
1427 dumpPreservedSet(MP);
1429 verifyPreservedAnalysis(MP);
1430 removeNotPreservedAnalysis(MP);
1431 recordAvailableAnalysis(MP);
1432 removeDeadPasses(MP, M.getModuleIdentifier().c_str(), ON_MODULE_MSG);
1437 /// Add RequiredPass into list of lower level passes required by pass P.
1438 /// RequiredPass is run on the fly by Pass Manager when P requests it
1439 /// through getAnalysis interface.
1440 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1441 assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
1442 "Unable to handle Pass that requires lower level Analysis pass");
1443 assert((P->getPotentialPassManagerType() <
1444 RequiredPass->getPotentialPassManagerType()) &&
1445 "Unable to handle Pass that requires lower level Analysis pass");
1447 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1449 FPP = new FunctionPassManagerImpl(0);
1450 // FPP is the top level manager.
1451 FPP->setTopLevelManager(FPP);
1453 OnTheFlyManagers[P] = FPP;
1455 FPP->add(RequiredPass);
1457 // Register P as the last user of RequiredPass.
1458 SmallVector<Pass *, 12> LU;
1459 LU.push_back(RequiredPass);
1460 FPP->setLastUser(LU, P);
1463 /// Return function pass corresponding to PassInfo PI, that is
1464 /// required by module pass MP. Instantiate analysis pass, by using
1465 /// its runOnFunction() for function F.
1466 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F){
1467 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1468 assert(FPP && "Unable to find on the fly pass");
1471 return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(PI);
1475 //===----------------------------------------------------------------------===//
1476 // PassManagerImpl implementation
1478 /// run - Execute all of the passes scheduled for execution. Keep track of
1479 /// whether any of the passes modifies the module, and if so, return true.
1480 bool PassManagerImpl::run(Module &M) {
1481 bool Changed = false;
1482 TimingInfo::createTheTimeInfo();
1487 initializeAllAnalysisInfo();
1488 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1489 Changed |= getContainedManager(Index)->runOnModule(M);
1493 //===----------------------------------------------------------------------===//
1494 // PassManager implementation
1496 /// Create new pass manager
1497 PassManager::PassManager() {
1498 PM = new PassManagerImpl(0);
1499 // PM is the top level manager
1500 PM->setTopLevelManager(PM);
1503 PassManager::~PassManager() {
1507 /// add - Add a pass to the queue of passes to run. This passes ownership of
1508 /// the Pass to the PassManager. When the PassManager is destroyed, the pass
1509 /// will be destroyed as well, so there is no need to delete the pass. This
1510 /// implies that all passes MUST be allocated with 'new'.
1511 void PassManager::add(Pass *P) {
1515 /// run - Execute all of the passes scheduled for execution. Keep track of
1516 /// whether any of the passes modifies the module, and if so, return true.
1517 bool PassManager::run(Module &M) {
1521 //===----------------------------------------------------------------------===//
1522 // TimingInfo Class - This class is used to calculate information about the
1523 // amount of time each pass takes to execute. This only happens with
1524 // -time-passes is enabled on the command line.
1526 bool llvm::TimePassesIsEnabled = false;
1527 static cl::opt<bool,true>
1528 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1529 cl::desc("Time each pass, printing elapsed time for each on exit"));
1531 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1532 // a non null value (if the -time-passes option is enabled) or it leaves it
1533 // null. It may be called multiple times.
1534 void TimingInfo::createTheTimeInfo() {
1535 if (!TimePassesIsEnabled || TheTimeInfo) return;
1537 // Constructed the first time this is called, iff -time-passes is enabled.
1538 // This guarantees that the object will be constructed before static globals,
1539 // thus it will be destroyed before them.
1540 static ManagedStatic<TimingInfo> TTI;
1541 TheTimeInfo = &*TTI;
1544 /// If TimingInfo is enabled then start pass timer.
1545 void StartPassTimer(Pass *P) {
1547 TheTimeInfo->passStarted(P);
1550 /// If TimingInfo is enabled then stop pass timer.
1551 void StopPassTimer(Pass *P) {
1553 TheTimeInfo->passEnded(P);
1556 //===----------------------------------------------------------------------===//
1557 // PMStack implementation
1560 // Pop Pass Manager from the stack and clear its analysis info.
1561 void PMStack::pop() {
1563 PMDataManager *Top = this->top();
1564 Top->initializeAnalysisInfo();
1569 // Push PM on the stack and set its top level manager.
1570 void PMStack::push(PMDataManager *PM) {
1571 assert(PM && "Unable to push. Pass Manager expected");
1573 if (!this->empty()) {
1574 PMTopLevelManager *TPM = this->top()->getTopLevelManager();
1576 assert(TPM && "Unable to find top level manager");
1577 TPM->addIndirectPassManager(PM);
1578 PM->setTopLevelManager(TPM);
1584 // Dump content of the pass manager stack.
1585 void PMStack::dump() {
1586 for (std::deque<PMDataManager *>::iterator I = S.begin(),
1587 E = S.end(); I != E; ++I)
1588 printf("%s ", dynamic_cast<Pass *>(*I)->getPassName());
1594 /// Find appropriate Module Pass Manager in the PM Stack and
1595 /// add self into that manager.
1596 void ModulePass::assignPassManager(PMStack &PMS,
1597 PassManagerType PreferredType) {
1598 // Find Module Pass Manager
1599 while(!PMS.empty()) {
1600 PassManagerType TopPMType = PMS.top()->getPassManagerType();
1601 if (TopPMType == PreferredType)
1602 break; // We found desired pass manager
1603 else if (TopPMType > PMT_ModulePassManager)
1604 PMS.pop(); // Pop children pass managers
1608 assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
1609 PMS.top()->add(this);
1612 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1613 /// in the PM Stack and add self into that manager.
1614 void FunctionPass::assignPassManager(PMStack &PMS,
1615 PassManagerType PreferredType) {
1617 // Find Module Pass Manager
1618 while(!PMS.empty()) {
1619 if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1624 FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1626 // Create new Function Pass Manager
1628 assert(!PMS.empty() && "Unable to create Function Pass Manager");
1629 PMDataManager *PMD = PMS.top();
1631 // [1] Create new Function Pass Manager
1632 FPP = new FPPassManager(PMD->getDepth() + 1);
1633 FPP->populateInheritedAnalysis(PMS);
1635 // [2] Set up new manager's top level manager
1636 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1637 TPM->addIndirectPassManager(FPP);
1639 // [3] Assign manager to manage this new manager. This may create
1640 // and push new managers into PMS
1641 FPP->assignPassManager(PMS, PMD->getPassManagerType());
1643 // [4] Push new manager into PMS
1647 // Assign FPP as the manager of this pass.
1651 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1652 /// in the PM Stack and add self into that manager.
1653 void BasicBlockPass::assignPassManager(PMStack &PMS,
1654 PassManagerType PreferredType) {
1655 BBPassManager *BBP = NULL;
1657 // Basic Pass Manager is a leaf pass manager. It does not handle
1658 // any other pass manager.
1660 BBP = dynamic_cast<BBPassManager *>(PMS.top());
1662 // If leaf manager is not Basic Block Pass manager then create new
1663 // basic Block Pass manager.
1666 assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1667 PMDataManager *PMD = PMS.top();
1669 // [1] Create new Basic Block Manager
1670 BBP = new BBPassManager(PMD->getDepth() + 1);
1672 // [2] Set up new manager's top level manager
1673 // Basic Block Pass Manager does not live by itself
1674 PMTopLevelManager *TPM = PMD->getTopLevelManager();
1675 TPM->addIndirectPassManager(BBP);
1677 // [3] Assign manager to manage this new manager. This may create
1678 // and push new managers into PMS
1679 BBP->assignPassManager(PMS);
1681 // [4] Push new manager into PMS
1685 // Assign BBP as the manager of this pass.
1689 PassManagerBase::~PassManagerBase() {}
1691 /*===-- C Bindings --------------------------------------------------------===*/
1693 LLVMPassManagerRef LLVMCreatePassManager() {
1694 return wrap(new PassManager());
1697 LLVMPassManagerRef LLVMCreateFunctionPassManager(LLVMModuleProviderRef P) {
1698 return wrap(new FunctionPassManager(unwrap(P)));
1701 int LLVMRunPassManager(LLVMPassManagerRef PM, LLVMModuleRef M) {
1702 return unwrap<PassManager>(PM)->run(*unwrap(M));
1705 int LLVMInitializeFunctionPassManager(LLVMPassManagerRef FPM) {
1706 return unwrap<FunctionPassManager>(FPM)->doInitialization();
1709 int LLVMRunFunctionPassManager(LLVMPassManagerRef FPM, LLVMValueRef F) {
1710 return unwrap<FunctionPassManager>(FPM)->run(*unwrap<Function>(F));
1713 int LLVMFinalizeFunctionPassManager(LLVMPassManagerRef FPM) {
1714 return unwrap<FunctionPassManager>(FPM)->doFinalization();
1717 void LLVMDisposePassManager(LLVMPassManagerRef PM) {