LLVM API Documentation

PassManager.cpp

Go to the documentation of this file.
00001 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the LLVM Pass Manager infrastructure. 
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 
00015 #include "llvm/PassManagers.h"
00016 #include "llvm/Support/CommandLine.h"
00017 #include "llvm/Support/Timer.h"
00018 #include "llvm/Module.h"
00019 #include "llvm/ModuleProvider.h"
00020 #include "llvm/Support/ErrorHandling.h"
00021 #include "llvm/Support/Streams.h"
00022 #include "llvm/Support/ManagedStatic.h"
00023 #include "llvm/Support/raw_ostream.h"
00024 #include "llvm/System/Mutex.h"
00025 #include "llvm/System/Threading.h"
00026 #include "llvm/Analysis/Dominators.h"
00027 #include "llvm-c/Core.h"
00028 #include <algorithm>
00029 #include <cstdio>
00030 #include <map>
00031 using namespace llvm;
00032 
00033 // See PassManagers.h for Pass Manager infrastructure overview.
00034 
00035 namespace llvm {
00036 
00037 //===----------------------------------------------------------------------===//
00038 // Pass debugging information.  Often it is useful to find out what pass is
00039 // running when a crash occurs in a utility.  When this library is compiled with
00040 // debugging on, a command line option (--debug-pass) is enabled that causes the
00041 // pass name to be printed before it executes.
00042 //
00043 
00044 // Different debug levels that can be enabled...
00045 enum PassDebugLevel {
00046   None, Arguments, Structure, Executions, Details
00047 };
00048 
00049 // Always verify dominfo if expensive checking is enabled.
00050 #ifdef XDEBUG
00051 bool VerifyDomInfo = true;
00052 #else
00053 bool VerifyDomInfo = false;
00054 #endif
00055 static cl::opt<bool,true>
00056 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
00057                cl::desc("Verify dominator info (time consuming)"));
00058 
00059 static cl::opt<enum PassDebugLevel>
00060 PassDebugging("debug-pass", cl::Hidden,
00061                   cl::desc("Print PassManager debugging information"),
00062                   cl::values(
00063   clEnumVal(None      , "disable debug output"),
00064   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
00065   clEnumVal(Structure , "print pass structure before run()"),
00066   clEnumVal(Executions, "print pass name before it is executed"),
00067   clEnumVal(Details   , "print pass details when it is executed"),
00068                              clEnumValEnd));
00069 } // End of llvm namespace
00070 
00071 void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
00072   if (V == 0 && M == 0)
00073     OS << "Releasing pass '";
00074   else
00075     OS << "Running pass '";
00076   
00077   OS << P->getPassName() << "'";
00078   
00079   if (M) {
00080     OS << " on module '" << M->getModuleIdentifier() << "'.\n";
00081     return;
00082   }
00083   if (V == 0) {
00084     OS << '\n';
00085     return;
00086   }
00087 
00088   OS << " on ";
00089   if (isa<Function>(V))
00090     OS << "function";
00091   else if (isa<BasicBlock>(V))
00092     OS << "basic block";
00093   else
00094     OS << "value";
00095 
00096   OS << " '";
00097   WriteAsOperand(OS, V, /*PrintTy=*/false, M);
00098   OS << "'\n";
00099 }
00100 
00101 
00102 namespace {
00103 
00104 //===----------------------------------------------------------------------===//
00105 // BBPassManager
00106 //
00107 /// BBPassManager manages BasicBlockPass. It batches all the
00108 /// pass together and sequence them to process one basic block before
00109 /// processing next basic block.
00110 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager, 
00111                                         public FunctionPass {
00112 
00113 public:
00114   static char ID;
00115   explicit BBPassManager(int Depth) 
00116     : PMDataManager(Depth), FunctionPass(&ID) {}
00117 
00118   /// Execute all of the passes scheduled for execution.  Keep track of
00119   /// whether any of the passes modifies the function, and if so, return true.
00120   bool runOnFunction(Function &F);
00121 
00122   /// Pass Manager itself does not invalidate any analysis info.
00123   void getAnalysisUsage(AnalysisUsage &Info) const {
00124     Info.setPreservesAll();
00125   }
00126 
00127   bool doInitialization(Module &M);
00128   bool doInitialization(Function &F);
00129   bool doFinalization(Module &M);
00130   bool doFinalization(Function &F);
00131 
00132   virtual const char *getPassName() const {
00133     return "BasicBlock Pass Manager";
00134   }
00135 
00136   // Print passes managed by this manager
00137   void dumpPassStructure(unsigned Offset) {
00138     llvm::errs() << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n";
00139     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00140       BasicBlockPass *BP = getContainedPass(Index);
00141       BP->dumpPassStructure(Offset + 1);
00142       dumpLastUses(BP, Offset+1);
00143     }
00144   }
00145 
00146   BasicBlockPass *getContainedPass(unsigned N) {
00147     assert(N < PassVector.size() && "Pass number out of range!");
00148     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
00149     return BP;
00150   }
00151 
00152   virtual PassManagerType getPassManagerType() const { 
00153     return PMT_BasicBlockPassManager; 
00154   }
00155 };
00156 
00157 char BBPassManager::ID = 0;
00158 }
00159 
00160 namespace llvm {
00161 
00162 //===----------------------------------------------------------------------===//
00163 // FunctionPassManagerImpl
00164 //
00165 /// FunctionPassManagerImpl manages FPPassManagers
00166 class FunctionPassManagerImpl : public Pass,
00167                                 public PMDataManager,
00168                                 public PMTopLevelManager {
00169 private:
00170   bool wasRun;
00171 public:
00172   static char ID;
00173   explicit FunctionPassManagerImpl(int Depth) : 
00174     Pass(&ID), PMDataManager(Depth), 
00175     PMTopLevelManager(TLM_Function), wasRun(false) { }
00176 
00177   /// add - Add a pass to the queue of passes to run.  This passes ownership of
00178   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
00179   /// will be destroyed as well, so there is no need to delete the pass.  This
00180   /// implies that all passes MUST be allocated with 'new'.
00181   void add(Pass *P) {
00182     schedulePass(P);
00183   }
00184  
00185   // Prepare for running an on the fly pass, freeing memory if needed
00186   // from a previous run.
00187   void releaseMemoryOnTheFly();
00188 
00189   /// run - Execute all of the passes scheduled for execution.  Keep track of
00190   /// whether any of the passes modifies the module, and if so, return true.
00191   bool run(Function &F);
00192 
00193   /// doInitialization - Run all of the initializers for the function passes.
00194   ///
00195   bool doInitialization(Module &M);
00196   
00197   /// doFinalization - Run all of the finalizers for the function passes.
00198   ///
00199   bool doFinalization(Module &M);
00200 
00201   /// Pass Manager itself does not invalidate any analysis info.
00202   void getAnalysisUsage(AnalysisUsage &Info) const {
00203     Info.setPreservesAll();
00204   }
00205 
00206   inline void addTopLevelPass(Pass *P) {
00207 
00208     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
00209       
00210       // P is a immutable pass and it will be managed by this
00211       // top level manager. Set up analysis resolver to connect them.
00212       AnalysisResolver *AR = new AnalysisResolver(*this);
00213       P->setResolver(AR);
00214       initializeAnalysisImpl(P);
00215       addImmutablePass(IP);
00216       recordAvailableAnalysis(IP);
00217     } else {
00218       P->assignPassManager(activeStack);
00219     }
00220 
00221   }
00222 
00223   FPPassManager *getContainedManager(unsigned N) {
00224     assert(N < PassManagers.size() && "Pass number out of range!");
00225     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
00226     return FP;
00227   }
00228 };
00229 
00230 char FunctionPassManagerImpl::ID = 0;
00231 //===----------------------------------------------------------------------===//
00232 // MPPassManager
00233 //
00234 /// MPPassManager manages ModulePasses and function pass managers.
00235 /// It batches all Module passes and function pass managers together and
00236 /// sequences them to process one module.
00237 class MPPassManager : public Pass, public PMDataManager {
00238 public:
00239   static char ID;
00240   explicit MPPassManager(int Depth) :
00241     Pass(&ID), PMDataManager(Depth) { }
00242 
00243   // Delete on the fly managers.
00244   virtual ~MPPassManager() {
00245     for (std::map<Pass *, FunctionPassManagerImpl *>::iterator 
00246            I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
00247          I != E; ++I) {
00248       FunctionPassManagerImpl *FPP = I->second;
00249       delete FPP;
00250     }
00251   }
00252 
00253   /// run - Execute all of the passes scheduled for execution.  Keep track of
00254   /// whether any of the passes modifies the module, and if so, return true.
00255   bool runOnModule(Module &M);
00256 
00257   /// Pass Manager itself does not invalidate any analysis info.
00258   void getAnalysisUsage(AnalysisUsage &Info) const {
00259     Info.setPreservesAll();
00260   }
00261 
00262   /// Add RequiredPass into list of lower level passes required by pass P.
00263   /// RequiredPass is run on the fly by Pass Manager when P requests it
00264   /// through getAnalysis interface.
00265   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
00266 
00267   /// Return function pass corresponding to PassInfo PI, that is 
00268   /// required by module pass MP. Instantiate analysis pass, by using
00269   /// its runOnFunction() for function F.
00270   virtual Pass* getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F);
00271 
00272   virtual const char *getPassName() const {
00273     return "Module Pass Manager";
00274   }
00275 
00276   // Print passes managed by this manager
00277   void dumpPassStructure(unsigned Offset) {
00278     llvm::errs() << std::string(Offset*2, ' ') << "ModulePass Manager\n";
00279     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00280       ModulePass *MP = getContainedPass(Index);
00281       MP->dumpPassStructure(Offset + 1);
00282       std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I =
00283         OnTheFlyManagers.find(MP);
00284       if (I != OnTheFlyManagers.end())
00285         I->second->dumpPassStructure(Offset + 2);
00286       dumpLastUses(MP, Offset+1);
00287     }
00288   }
00289 
00290   ModulePass *getContainedPass(unsigned N) {
00291     assert(N < PassVector.size() && "Pass number out of range!");
00292     return static_cast<ModulePass *>(PassVector[N]);
00293   }
00294 
00295   virtual PassManagerType getPassManagerType() const { 
00296     return PMT_ModulePassManager; 
00297   }
00298 
00299  private:
00300   /// Collection of on the fly FPPassManagers. These managers manage
00301   /// function passes that are required by module passes.
00302   std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
00303 };
00304 
00305 char MPPassManager::ID = 0;
00306 //===----------------------------------------------------------------------===//
00307 // PassManagerImpl
00308 //
00309 
00310 /// PassManagerImpl manages MPPassManagers
00311 class PassManagerImpl : public Pass,
00312                         public PMDataManager,
00313                         public PMTopLevelManager {
00314 
00315 public:
00316   static char ID;
00317   explicit PassManagerImpl(int Depth) :
00318     Pass(&ID), PMDataManager(Depth), PMTopLevelManager(TLM_Pass) { }
00319 
00320   /// add - Add a pass to the queue of passes to run.  This passes ownership of
00321   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
00322   /// will be destroyed as well, so there is no need to delete the pass.  This
00323   /// implies that all passes MUST be allocated with 'new'.
00324   void add(Pass *P) {
00325     schedulePass(P);
00326   }
00327  
00328   /// run - Execute all of the passes scheduled for execution.  Keep track of
00329   /// whether any of the passes modifies the module, and if so, return true.
00330   bool run(Module &M);
00331 
00332   /// Pass Manager itself does not invalidate any analysis info.
00333   void getAnalysisUsage(AnalysisUsage &Info) const {
00334     Info.setPreservesAll();
00335   }
00336 
00337   inline void addTopLevelPass(Pass *P) {
00338     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
00339       
00340       // P is a immutable pass and it will be managed by this
00341       // top level manager. Set up analysis resolver to connect them.
00342       AnalysisResolver *AR = new AnalysisResolver(*this);
00343       P->setResolver(AR);
00344       initializeAnalysisImpl(P);
00345       addImmutablePass(IP);
00346       recordAvailableAnalysis(IP);
00347     } else {
00348       P->assignPassManager(activeStack);
00349     }
00350   }
00351 
00352   MPPassManager *getContainedManager(unsigned N) {
00353     assert(N < PassManagers.size() && "Pass number out of range!");
00354     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
00355     return MP;
00356   }
00357 };
00358 
00359 char PassManagerImpl::ID = 0;
00360 } // End of llvm namespace
00361 
00362 namespace {
00363 
00364 //===----------------------------------------------------------------------===//
00365 /// TimingInfo Class - This class is used to calculate information about the
00366 /// amount of time each pass takes to execute.  This only happens when
00367 /// -time-passes is enabled on the command line.
00368 ///
00369 
00370 static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex;
00371 
00372 class VISIBILITY_HIDDEN TimingInfo {
00373   std::map<Pass*, Timer> TimingData;
00374   TimerGroup TG;
00375 
00376 public:
00377   // Use 'create' member to get this.
00378   TimingInfo() : TG("... Pass execution timing report ...") {}
00379   
00380   // TimingDtor - Print out information about timing information
00381   ~TimingInfo() {
00382     // Delete all of the timers...
00383     TimingData.clear();
00384     // TimerGroup is deleted next, printing the report.
00385   }
00386 
00387   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
00388   // to a non null value (if the -time-passes option is enabled) or it leaves it
00389   // null.  It may be called multiple times.
00390   static void createTheTimeInfo();
00391 
00392   void passStarted(Pass *P) {
00393     if (dynamic_cast<PMDataManager *>(P)) 
00394       return;
00395 
00396     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
00397     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
00398     if (I == TimingData.end())
00399       I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
00400     I->second.startTimer();
00401   }
00402   
00403   void passEnded(Pass *P) {
00404     if (dynamic_cast<PMDataManager *>(P)) 
00405       return;
00406 
00407     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
00408     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
00409     assert(I != TimingData.end() && "passStarted/passEnded not nested right!");
00410     I->second.stopTimer();
00411   }
00412 };
00413 
00414 } // End of anon namespace
00415 
00416 static TimingInfo *TheTimeInfo;
00417 
00418 //===----------------------------------------------------------------------===//
00419 // PMTopLevelManager implementation
00420 
00421 /// Initialize top level manager. Create first pass manager.
00422 PMTopLevelManager::PMTopLevelManager(enum TopLevelManagerType t) {
00423   if (t == TLM_Pass) {
00424     MPPassManager *MPP = new MPPassManager(1);
00425     MPP->setTopLevelManager(this);
00426     addPassManager(MPP);
00427     activeStack.push(MPP);
00428   } else if (t == TLM_Function) {
00429     FPPassManager *FPP = new FPPassManager(1);
00430     FPP->setTopLevelManager(this);
00431     addPassManager(FPP);
00432     activeStack.push(FPP);
00433   } 
00434 }
00435 
00436 /// Set pass P as the last user of the given analysis passes.
00437 void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses, 
00438                                     Pass *P) {
00439   for (SmallVector<Pass *, 12>::iterator I = AnalysisPasses.begin(),
00440          E = AnalysisPasses.end(); I != E; ++I) {
00441     Pass *AP = *I;
00442     LastUser[AP] = P;
00443     
00444     if (P == AP)
00445       continue;
00446 
00447     // If AP is the last user of other passes then make P last user of
00448     // such passes.
00449     for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
00450            LUE = LastUser.end(); LUI != LUE; ++LUI) {
00451       if (LUI->second == AP)
00452         // DenseMap iterator is not invalidated here because
00453         // this is just updating exisitng entry.
00454         LastUser[LUI->first] = P;
00455     }
00456   }
00457 }
00458 
00459 /// Collect passes whose last user is P
00460 void PMTopLevelManager::collectLastUses(SmallVector<Pass *, 12> &LastUses,
00461                                         Pass *P) {
00462   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI = 
00463     InversedLastUser.find(P);
00464   if (DMI == InversedLastUser.end())
00465     return;
00466 
00467   SmallPtrSet<Pass *, 8> &LU = DMI->second;
00468   for (SmallPtrSet<Pass *, 8>::iterator I = LU.begin(),
00469          E = LU.end(); I != E; ++I) {
00470     LastUses.push_back(*I);
00471   }
00472 
00473 }
00474 
00475 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
00476   AnalysisUsage *AnUsage = NULL;
00477   DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.find(P);
00478   if (DMI != AnUsageMap.end()) 
00479     AnUsage = DMI->second;
00480   else {
00481     AnUsage = new AnalysisUsage();
00482     P->getAnalysisUsage(*AnUsage);
00483     AnUsageMap[P] = AnUsage;
00484   }
00485   return AnUsage;
00486 }
00487 
00488 /// Schedule pass P for execution. Make sure that passes required by
00489 /// P are run before P is run. Update analysis info maintained by
00490 /// the manager. Remove dead passes. This is a recursive function.
00491 void PMTopLevelManager::schedulePass(Pass *P) {
00492 
00493   // TODO : Allocate function manager for this pass, other wise required set
00494   // may be inserted into previous function manager
00495 
00496   // Give pass a chance to prepare the stage.
00497   P->preparePassManager(activeStack);
00498 
00499   // If P is an analysis pass and it is available then do not
00500   // generate the analysis again. Stale analysis info should not be
00501   // available at this point.
00502   if (P->getPassInfo() &&
00503       P->getPassInfo()->isAnalysis() && findAnalysisPass(P->getPassInfo())) {
00504     delete P;
00505     return;
00506   }
00507 
00508   AnalysisUsage *AnUsage = findAnalysisUsage(P);
00509 
00510   bool checkAnalysis = true;
00511   while (checkAnalysis) {
00512     checkAnalysis = false;
00513   
00514     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
00515     for (AnalysisUsage::VectorType::const_iterator I = RequiredSet.begin(),
00516            E = RequiredSet.end(); I != E; ++I) {
00517       
00518       Pass *AnalysisPass = findAnalysisPass(*I);
00519       if (!AnalysisPass) {
00520         AnalysisPass = (*I)->createPass();
00521         if (P->getPotentialPassManagerType () ==
00522             AnalysisPass->getPotentialPassManagerType())
00523           // Schedule analysis pass that is managed by the same pass manager.
00524           schedulePass(AnalysisPass);
00525         else if (P->getPotentialPassManagerType () >
00526                  AnalysisPass->getPotentialPassManagerType()) {
00527           // Schedule analysis pass that is managed by a new manager.
00528           schedulePass(AnalysisPass);
00529           // Recheck analysis passes to ensure that required analysises that
00530           // are already checked are still available.
00531           checkAnalysis = true;
00532         }
00533         else
00534           // Do not schedule this analysis. Lower level analsyis 
00535           // passes are run on the fly.
00536           delete AnalysisPass;
00537       }
00538     }
00539   }
00540 
00541   // Now all required passes are available.
00542   addTopLevelPass(P);
00543 }
00544 
00545 /// Find the pass that implements Analysis AID. Search immutable
00546 /// passes and all pass managers. If desired pass is not found
00547 /// then return NULL.
00548 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
00549 
00550   Pass *P = NULL;
00551   // Check pass managers
00552   for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
00553          E = PassManagers.end(); P == NULL && I != E; ++I) {
00554     PMDataManager *PMD = *I;
00555     P = PMD->findAnalysisPass(AID, false);
00556   }
00557 
00558   // Check other pass managers
00559   for (SmallVector<PMDataManager *, 8>::iterator
00560          I = IndirectPassManagers.begin(),
00561          E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
00562     P = (*I)->findAnalysisPass(AID, false);
00563 
00564   for (SmallVector<ImmutablePass *, 8>::iterator I = ImmutablePasses.begin(),
00565          E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
00566     const PassInfo *PI = (*I)->getPassInfo();
00567     if (PI == AID)
00568       P = *I;
00569 
00570     // If Pass not found then check the interfaces implemented by Immutable Pass
00571     if (!P) {
00572       const std::vector<const PassInfo*> &ImmPI =
00573         PI->getInterfacesImplemented();
00574       if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end())
00575         P = *I;
00576     }
00577   }
00578 
00579   return P;
00580 }
00581 
00582 // Print passes managed by this top level manager.
00583 void PMTopLevelManager::dumpPasses() const {
00584 
00585   if (PassDebugging < Structure)
00586     return;
00587 
00588   // Print out the immutable passes
00589   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
00590     ImmutablePasses[i]->dumpPassStructure(0);
00591   }
00592   
00593   // Every class that derives from PMDataManager also derives from Pass
00594   // (sometimes indirectly), but there's no inheritance relationship
00595   // between PMDataManager and Pass, so we have to dynamic_cast to get
00596   // from a PMDataManager* to a Pass*.
00597   for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(),
00598          E = PassManagers.end(); I != E; ++I)
00599     dynamic_cast<Pass *>(*I)->dumpPassStructure(1);
00600 }
00601 
00602 void PMTopLevelManager::dumpArguments() const {
00603 
00604   if (PassDebugging < Arguments)
00605     return;
00606 
00607   errs() << "Pass Arguments: ";
00608   for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(),
00609          E = PassManagers.end(); I != E; ++I)
00610     (*I)->dumpPassArguments();
00611   errs() << "\n";
00612 }
00613 
00614 void PMTopLevelManager::initializeAllAnalysisInfo() {
00615   for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
00616          E = PassManagers.end(); I != E; ++I)
00617     (*I)->initializeAnalysisInfo();
00618   
00619   // Initailize other pass managers
00620   for (SmallVector<PMDataManager *, 8>::iterator I = IndirectPassManagers.begin(),
00621          E = IndirectPassManagers.end(); I != E; ++I)
00622     (*I)->initializeAnalysisInfo();
00623 
00624   for (DenseMap<Pass *, Pass *>::iterator DMI = LastUser.begin(),
00625         DME = LastUser.end(); DMI != DME; ++DMI) {
00626     DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator InvDMI = 
00627       InversedLastUser.find(DMI->second);
00628     if (InvDMI != InversedLastUser.end()) {
00629       SmallPtrSet<Pass *, 8> &L = InvDMI->second;
00630       L.insert(DMI->first);
00631     } else {
00632       SmallPtrSet<Pass *, 8> L; L.insert(DMI->first);
00633       InversedLastUser[DMI->second] = L;
00634     }
00635   }
00636 }
00637 
00638 /// Destructor
00639 PMTopLevelManager::~PMTopLevelManager() {
00640   for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(),
00641          E = PassManagers.end(); I != E; ++I)
00642     delete *I;
00643   
00644   for (SmallVector<ImmutablePass *, 8>::iterator
00645          I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
00646     delete *I;
00647 
00648   for (DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.begin(),
00649          DME = AnUsageMap.end(); DMI != DME; ++DMI)
00650     delete DMI->second;
00651 }
00652 
00653 //===----------------------------------------------------------------------===//
00654 // PMDataManager implementation
00655 
00656 /// Augement AvailableAnalysis by adding analysis made available by pass P.
00657 void PMDataManager::recordAvailableAnalysis(Pass *P) {
00658   const PassInfo *PI = P->getPassInfo();
00659   if (PI == 0) return;
00660   
00661   AvailableAnalysis[PI] = P;
00662 
00663   //This pass is the current implementation of all of the interfaces it
00664   //implements as well.
00665   const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
00666   for (unsigned i = 0, e = II.size(); i != e; ++i)
00667     AvailableAnalysis[II[i]] = P;
00668 }
00669 
00670 // Return true if P preserves high level analysis used by other
00671 // passes managed by this manager
00672 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
00673   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
00674   if (AnUsage->getPreservesAll())
00675     return true;
00676   
00677   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
00678   for (SmallVector<Pass *, 8>::iterator I = HigherLevelAnalysis.begin(),
00679          E = HigherLevelAnalysis.end(); I  != E; ++I) {
00680     Pass *P1 = *I;
00681     if (!dynamic_cast<ImmutablePass*>(P1) &&
00682         std::find(PreservedSet.begin(), PreservedSet.end(),
00683                   P1->getPassInfo()) == 
00684            PreservedSet.end())
00685       return false;
00686   }
00687   
00688   return true;
00689 }
00690 
00691 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
00692 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
00693   // Don't do this unless assertions are enabled.
00694 #ifdef NDEBUG
00695   return;
00696 #endif
00697   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
00698   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
00699 
00700   // Verify preserved analysis
00701   for (AnalysisUsage::VectorType::const_iterator I = PreservedSet.begin(),
00702          E = PreservedSet.end(); I != E; ++I) {
00703     AnalysisID AID = *I;
00704     if (Pass *AP = findAnalysisPass(AID, true))
00705       AP->verifyAnalysis();
00706   }
00707 }
00708 
00709 /// verifyDomInfo - Verify dominator information if it is available.
00710 void PMDataManager::verifyDomInfo(Pass &P, Function &F) {
00711   if (!VerifyDomInfo || !P.getResolver())
00712     return;
00713 
00714   DominatorTree *DT = P.getAnalysisIfAvailable<DominatorTree>();
00715   if (!DT)
00716     return;
00717 
00718   DominatorTree OtherDT;
00719   OtherDT.getBase().recalculate(F);
00720   if (DT->compare(OtherDT)) {
00721     errs() << "Dominator Information for " << F.getName() << "\n";
00722     errs() << "Pass '" << P.getPassName() << "'\n";
00723     errs() << "----- Valid -----\n";
00724     OtherDT.dump();
00725     errs() << "----- Invalid -----\n";
00726     DT->dump();
00727     llvm_unreachable("Invalid dominator info");
00728   }
00729 
00730   DominanceFrontier *DF = P.getAnalysisIfAvailable<DominanceFrontier>();
00731   if (!DF) 
00732     return;
00733 
00734   DominanceFrontier OtherDF;
00735   std::vector<BasicBlock*> DTRoots = DT->getRoots();
00736   OtherDF.calculate(*DT, DT->getNode(DTRoots[0]));
00737   if (DF->compare(OtherDF)) {
00738     errs() << "Dominator Information for " << F.getName() << "\n";
00739     errs() << "Pass '" << P.getPassName() << "'\n";
00740     errs() << "----- Valid -----\n";
00741     OtherDF.dump();
00742     errs() << "----- Invalid -----\n";
00743     DF->dump();
00744     llvm_unreachable("Invalid dominator info");
00745   }
00746 }
00747 
00748 /// Remove Analysis not preserved by Pass P
00749 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
00750   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
00751   if (AnUsage->getPreservesAll())
00752     return;
00753 
00754   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
00755   for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
00756          E = AvailableAnalysis.end(); I != E; ) {
00757     std::map<AnalysisID, Pass*>::iterator Info = I++;
00758     if (!dynamic_cast<ImmutablePass*>(Info->second)
00759         && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 
00760         PreservedSet.end()) {
00761       // Remove this analysis
00762       if (PassDebugging >= Details) {
00763         Pass *S = Info->second;
00764         errs() << " -- '" <<  P->getPassName() << "' is not preserving '";
00765         errs() << S->getPassName() << "'\n";
00766       }
00767       AvailableAnalysis.erase(Info);
00768     }
00769   }
00770 
00771   // Check inherited analysis also. If P is not preserving analysis
00772   // provided by parent manager then remove it here.
00773   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
00774 
00775     if (!InheritedAnalysis[Index])
00776       continue;
00777 
00778     for (std::map<AnalysisID, Pass*>::iterator 
00779            I = InheritedAnalysis[Index]->begin(),
00780            E = InheritedAnalysis[Index]->end(); I != E; ) {
00781       std::map<AnalysisID, Pass *>::iterator Info = I++;
00782       if (!dynamic_cast<ImmutablePass*>(Info->second) &&
00783           std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 
00784              PreservedSet.end())
00785         // Remove this analysis
00786         InheritedAnalysis[Index]->erase(Info);
00787     }
00788   }
00789 }
00790 
00791 /// Remove analysis passes that are not used any longer
00792 void PMDataManager::removeDeadPasses(Pass *P, const StringRef &Msg,
00793                                      enum PassDebuggingString DBG_STR) {
00794 
00795   SmallVector<Pass *, 12> DeadPasses;
00796 
00797   // If this is a on the fly manager then it does not have TPM.
00798   if (!TPM)
00799     return;
00800 
00801   TPM->collectLastUses(DeadPasses, P);
00802 
00803   if (PassDebugging >= Details && !DeadPasses.empty()) {
00804     errs() << " -*- '" <<  P->getPassName();
00805     errs() << "' is the last user of following pass instances.";
00806     errs() << " Free these instances\n";
00807   }
00808 
00809   for (SmallVector<Pass *, 12>::iterator I = DeadPasses.begin(),
00810          E = DeadPasses.end(); I != E; ++I) {
00811 
00812     dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg);
00813 
00814     {
00815       // If the pass crashes releasing memory, remember this.
00816       PassManagerPrettyStackEntry X(*I);
00817       
00818       if (TheTimeInfo) TheTimeInfo->passStarted(*I);
00819       (*I)->releaseMemory();
00820       if (TheTimeInfo) TheTimeInfo->passEnded(*I);
00821     }
00822     if (const PassInfo *PI = (*I)->getPassInfo()) {
00823       std::map<AnalysisID, Pass*>::iterator Pos =
00824         AvailableAnalysis.find(PI);
00825 
00826       // It is possible that pass is already removed from the AvailableAnalysis
00827       if (Pos != AvailableAnalysis.end())
00828         AvailableAnalysis.erase(Pos);
00829 
00830       // Remove all interfaces this pass implements, for which it is also
00831       // listed as the available implementation.
00832       const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
00833       for (unsigned i = 0, e = II.size(); i != e; ++i) {
00834         Pos = AvailableAnalysis.find(II[i]);
00835         if (Pos != AvailableAnalysis.end() && Pos->second == *I)
00836           AvailableAnalysis.erase(Pos);
00837       }
00838     }
00839   }
00840 }
00841 
00842 /// Add pass P into the PassVector. Update 
00843 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
00844 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
00845   // This manager is going to manage pass P. Set up analysis resolver
00846   // to connect them.
00847   AnalysisResolver *AR = new AnalysisResolver(*this);
00848   P->setResolver(AR);
00849 
00850   // If a FunctionPass F is the last user of ModulePass info M
00851   // then the F's manager, not F, records itself as a last user of M.
00852   SmallVector<Pass *, 12> TransferLastUses;
00853 
00854   if (!ProcessAnalysis) {
00855     // Add pass
00856     PassVector.push_back(P);
00857     return;
00858   }
00859 
00860   // At the moment, this pass is the last user of all required passes.
00861   SmallVector<Pass *, 12> LastUses;
00862   SmallVector<Pass *, 8> RequiredPasses;
00863   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
00864 
00865   unsigned PDepth = this->getDepth();
00866 
00867   collectRequiredAnalysis(RequiredPasses, 
00868                           ReqAnalysisNotAvailable, P);
00869   for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(),
00870          E = RequiredPasses.end(); I != E; ++I) {
00871     Pass *PRequired = *I;
00872     unsigned RDepth = 0;
00873 
00874     assert(PRequired->getResolver() && "Analysis Resolver is not set");
00875     PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
00876     RDepth = DM.getDepth();
00877 
00878     if (PDepth == RDepth)
00879       LastUses.push_back(PRequired);
00880     else if (PDepth > RDepth) {
00881       // Let the parent claim responsibility of last use
00882       TransferLastUses.push_back(PRequired);
00883       // Keep track of higher level analysis used by this manager.
00884       HigherLevelAnalysis.push_back(PRequired);
00885     } else 
00886       llvm_unreachable("Unable to accomodate Required Pass");
00887   }
00888 
00889   // Set P as P's last user until someone starts using P.
00890   // However, if P is a Pass Manager then it does not need
00891   // to record its last user.
00892   if (!dynamic_cast<PMDataManager *>(P))
00893     LastUses.push_back(P);
00894   TPM->setLastUser(LastUses, P);
00895 
00896   if (!TransferLastUses.empty()) {
00897     Pass *My_PM = dynamic_cast<Pass *>(this);
00898     TPM->setLastUser(TransferLastUses, My_PM);
00899     TransferLastUses.clear();
00900   }
00901 
00902   // Now, take care of required analysises that are not available.
00903   for (SmallVector<AnalysisID, 8>::iterator 
00904          I = ReqAnalysisNotAvailable.begin(), 
00905          E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
00906     Pass *AnalysisPass = (*I)->createPass();
00907     this->addLowerLevelRequiredPass(P, AnalysisPass);
00908   }
00909 
00910   // Take a note of analysis required and made available by this pass.
00911   // Remove the analysis not preserved by this pass
00912   removeNotPreservedAnalysis(P);
00913   recordAvailableAnalysis(P);
00914 
00915   // Add pass
00916   PassVector.push_back(P);
00917 }
00918 
00919 
00920 /// Populate RP with analysis pass that are required by
00921 /// pass P and are available. Populate RP_NotAvail with analysis
00922 /// pass that are required by pass P but are not available.
00923 void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP,
00924                                        SmallVector<AnalysisID, 8> &RP_NotAvail,
00925                                             Pass *P) {
00926   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
00927   const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
00928   for (AnalysisUsage::VectorType::const_iterator 
00929          I = RequiredSet.begin(), E = RequiredSet.end(); I != E; ++I) {
00930     if (Pass *AnalysisPass = findAnalysisPass(*I, true))
00931       RP.push_back(AnalysisPass);   
00932     else
00933       RP_NotAvail.push_back(*I);
00934   }
00935 
00936   const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
00937   for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(),
00938          E = IDs.end(); I != E; ++I) {
00939     if (Pass *AnalysisPass = findAnalysisPass(*I, true))
00940       RP.push_back(AnalysisPass);   
00941     else
00942       RP_NotAvail.push_back(*I);
00943   }
00944 }
00945 
00946 // All Required analyses should be available to the pass as it runs!  Here
00947 // we fill in the AnalysisImpls member of the pass so that it can
00948 // successfully use the getAnalysis() method to retrieve the
00949 // implementations it needs.
00950 //
00951 void PMDataManager::initializeAnalysisImpl(Pass *P) {
00952   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
00953 
00954   for (AnalysisUsage::VectorType::const_iterator
00955          I = AnUsage->getRequiredSet().begin(),
00956          E = AnUsage->getRequiredSet().end(); I != E; ++I) {
00957     Pass *Impl = findAnalysisPass(*I, true);
00958     if (Impl == 0)
00959       // This may be analysis pass that is initialized on the fly.
00960       // If that is not the case then it will raise an assert when it is used.
00961       continue;
00962     AnalysisResolver *AR = P->getResolver();
00963     assert(AR && "Analysis Resolver is not set");
00964     AR->addAnalysisImplsPair(*I, Impl);
00965   }
00966 }
00967 
00968 /// Find the pass that implements Analysis AID. If desired pass is not found
00969 /// then return NULL.
00970 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
00971 
00972   // Check if AvailableAnalysis map has one entry.
00973   std::map<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
00974 
00975   if (I != AvailableAnalysis.end())
00976     return I->second;
00977 
00978   // Search Parents through TopLevelManager
00979   if (SearchParent)
00980     return TPM->findAnalysisPass(AID);
00981   
00982   return NULL;
00983 }
00984 
00985 // Print list of passes that are last used by P.
00986 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
00987 
00988   SmallVector<Pass *, 12> LUses;
00989 
00990   // If this is a on the fly manager then it does not have TPM.
00991   if (!TPM)
00992     return;
00993 
00994   TPM->collectLastUses(LUses, P);
00995   
00996   for (SmallVector<Pass *, 12>::iterator I = LUses.begin(),
00997          E = LUses.end(); I != E; ++I) {
00998     llvm::errs() << "--" << std::string(Offset*2, ' ');
00999     (*I)->dumpPassStructure(0);
01000   }
01001 }
01002 
01003 void PMDataManager::dumpPassArguments() const {
01004   for (SmallVector<Pass *, 8>::const_iterator I = PassVector.begin(),
01005         E = PassVector.end(); I != E; ++I) {
01006     if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
01007       PMD->dumpPassArguments();
01008     else
01009       if (const PassInfo *PI = (*I)->getPassInfo())
01010         if (!PI->isAnalysisGroup())
01011           errs() << " -" << PI->getPassArgument();
01012   }
01013 }
01014 
01015 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
01016                                  enum PassDebuggingString S2,
01017                                  const StringRef &Msg) {
01018   if (PassDebugging < Executions)
01019     return;
01020   errs() << (void*)this << std::string(getDepth()*2+1, ' ');
01021   switch (S1) {
01022   case EXECUTION_MSG:
01023     errs() << "Executing Pass '" << P->getPassName();
01024     break;
01025   case MODIFICATION_MSG:
01026     errs() << "Made Modification '" << P->getPassName();
01027     break;
01028   case FREEING_MSG:
01029     errs() << " Freeing Pass '" << P->getPassName();
01030     break;
01031   default:
01032     break;
01033   }
01034   switch (S2) {
01035   case ON_BASICBLOCK_MSG:
01036     errs() << "' on BasicBlock '" << Msg << "'...\n";
01037     break;
01038   case ON_FUNCTION_MSG:
01039     errs() << "' on Function '" << Msg << "'...\n";
01040     break;
01041   case ON_MODULE_MSG:
01042     errs() << "' on Module '"  << Msg << "'...\n";
01043     break;
01044   case ON_LOOP_MSG:
01045     errs() << "' on Loop " << Msg << "'...\n";
01046     break;
01047   case ON_CG_MSG:
01048     errs() << "' on Call Graph " << Msg << "'...\n";
01049     break;
01050   default:
01051     break;
01052   }
01053 }
01054 
01055 void PMDataManager::dumpRequiredSet(const Pass *P) const {
01056   if (PassDebugging < Details)
01057     return;
01058     
01059   AnalysisUsage analysisUsage;
01060   P->getAnalysisUsage(analysisUsage);
01061   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
01062 }
01063 
01064 void PMDataManager::dumpPreservedSet(const Pass *P) const {
01065   if (PassDebugging < Details)
01066     return;
01067     
01068   AnalysisUsage analysisUsage;
01069   P->getAnalysisUsage(analysisUsage);
01070   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
01071 }
01072 
01073 void PMDataManager::dumpAnalysisUsage(const StringRef &Msg, const Pass *P,
01074                                    const AnalysisUsage::VectorType &Set) const {
01075   assert(PassDebugging >= Details);
01076   if (Set.empty())
01077     return;
01078   errs() << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
01079   for (unsigned i = 0; i != Set.size(); ++i) {
01080     if (i) errs() << ",";
01081     errs() << " " << Set[i]->getPassName();
01082   }
01083   errs() << "\n";
01084 }
01085 
01086 /// Add RequiredPass into list of lower level passes required by pass P.
01087 /// RequiredPass is run on the fly by Pass Manager when P requests it
01088 /// through getAnalysis interface.
01089 /// This should be handled by specific pass manager.
01090 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
01091   if (TPM) {
01092     TPM->dumpArguments();
01093     TPM->dumpPasses();
01094   }
01095 
01096   // Module Level pass may required Function Level analysis info 
01097   // (e.g. dominator info). Pass manager uses on the fly function pass manager 
01098   // to provide this on demand. In that case, in Pass manager terminology, 
01099   // module level pass is requiring lower level analysis info managed by
01100   // lower level pass manager.
01101 
01102   // When Pass manager is not able to order required analysis info, Pass manager
01103   // checks whether any lower level manager will be able to provide this 
01104   // analysis info on demand or not.
01105 #ifndef NDEBUG
01106   errs() << "Unable to schedule '" << RequiredPass->getPassName();
01107   errs() << "' required by '" << P->getPassName() << "'\n";
01108 #endif
01109   llvm_unreachable("Unable to schedule pass");
01110 }
01111 
01112 // Destructor
01113 PMDataManager::~PMDataManager() {
01114   for (SmallVector<Pass *, 8>::iterator I = PassVector.begin(),
01115          E = PassVector.end(); I != E; ++I)
01116     delete *I;
01117 }
01118 
01119 //===----------------------------------------------------------------------===//
01120 // NOTE: Is this the right place to define this method ?
01121 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
01122 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
01123   return PM.findAnalysisPass(ID, dir);
01124 }
01125 
01126 Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI, 
01127                                      Function &F) {
01128   return PM.getOnTheFlyPass(P, AnalysisPI, F);
01129 }
01130 
01131 //===----------------------------------------------------------------------===//
01132 // BBPassManager implementation
01133 
01134 /// Execute all of the passes scheduled for execution by invoking 
01135 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies 
01136 /// the function, and if so, return true.
01137 bool BBPassManager::runOnFunction(Function &F) {
01138   if (F.isDeclaration())
01139     return false;
01140 
01141   bool Changed = doInitialization(F);
01142 
01143   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
01144     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01145       BasicBlockPass *BP = getContainedPass(Index);
01146 
01147       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getName());
01148       dumpRequiredSet(BP);
01149 
01150       initializeAnalysisImpl(BP);
01151 
01152       {
01153         // If the pass crashes, remember this.
01154         PassManagerPrettyStackEntry X(BP, *I);
01155       
01156         if (TheTimeInfo) TheTimeInfo->passStarted(BP);
01157         Changed |= BP->runOnBasicBlock(*I);
01158         if (TheTimeInfo) TheTimeInfo->passEnded(BP);
01159       }
01160 
01161       if (Changed) 
01162         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
01163                      I->getName());
01164       dumpPreservedSet(BP);
01165 
01166       verifyPreservedAnalysis(BP);
01167       removeNotPreservedAnalysis(BP);
01168       recordAvailableAnalysis(BP);
01169       removeDeadPasses(BP, I->getName(), ON_BASICBLOCK_MSG);
01170     }
01171 
01172   return Changed |= doFinalization(F);
01173 }
01174 
01175 // Implement doInitialization and doFinalization
01176 bool BBPassManager::doInitialization(Module &M) {
01177   bool Changed = false;
01178 
01179   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
01180     Changed |= getContainedPass(Index)->doInitialization(M);
01181 
01182   return Changed;
01183 }
01184 
01185 bool BBPassManager::doFinalization(Module &M) {
01186   bool Changed = false;
01187 
01188   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
01189     Changed |= getContainedPass(Index)->doFinalization(M);
01190 
01191   return Changed;
01192 }
01193 
01194 bool BBPassManager::doInitialization(Function &F) {
01195   bool Changed = false;
01196 
01197   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01198     BasicBlockPass *BP = getContainedPass(Index);
01199     Changed |= BP->doInitialization(F);
01200   }
01201 
01202   return Changed;
01203 }
01204 
01205 bool BBPassManager::doFinalization(Function &F) {
01206   bool Changed = false;
01207 
01208   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01209     BasicBlockPass *BP = getContainedPass(Index);
01210     Changed |= BP->doFinalization(F);
01211   }
01212 
01213   return Changed;
01214 }
01215 
01216 
01217 //===----------------------------------------------------------------------===//
01218 // FunctionPassManager implementation
01219 
01220 /// Create new Function pass manager
01221 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
01222   FPM = new FunctionPassManagerImpl(0);
01223   // FPM is the top level manager.
01224   FPM->setTopLevelManager(FPM);
01225 
01226   AnalysisResolver *AR = new AnalysisResolver(*FPM);
01227   FPM->setResolver(AR);
01228   
01229   MP = P;
01230 }
01231 
01232 FunctionPassManager::~FunctionPassManager() {
01233   delete FPM;
01234 }
01235 
01236 /// add - Add a pass to the queue of passes to run.  This passes
01237 /// ownership of the Pass to the PassManager.  When the
01238 /// PassManager_X is destroyed, the pass will be destroyed as well, so
01239 /// there is no need to delete the pass. (TODO delete passes.)
01240 /// This implies that all passes MUST be allocated with 'new'.
01241 void FunctionPassManager::add(Pass *P) { 
01242   FPM->add(P);
01243 }
01244 
01245 /// run - Execute all of the passes scheduled for execution.  Keep
01246 /// track of whether any of the passes modifies the function, and if
01247 /// so, return true.
01248 ///
01249 bool FunctionPassManager::run(Function &F) {
01250   std::string errstr;
01251   if (MP->materializeFunction(&F, &errstr)) {
01252     llvm_report_error("Error reading bitcode file: " + errstr);
01253   }
01254   return FPM->run(F);
01255 }
01256 
01257 
01258 /// doInitialization - Run all of the initializers for the function passes.
01259 ///
01260 bool FunctionPassManager::doInitialization() {
01261   return FPM->doInitialization(*MP->getModule());
01262 }
01263 
01264 /// doFinalization - Run all of the finalizers for the function passes.
01265 ///
01266 bool FunctionPassManager::doFinalization() {
01267   return FPM->doFinalization(*MP->getModule());
01268 }
01269 
01270 //===----------------------------------------------------------------------===//
01271 // FunctionPassManagerImpl implementation
01272 //
01273 bool FunctionPassManagerImpl::doInitialization(Module &M) {
01274   bool Changed = false;
01275 
01276   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
01277     Changed |= getContainedManager(Index)->doInitialization(M);
01278 
01279   return Changed;
01280 }
01281 
01282 bool FunctionPassManagerImpl::doFinalization(Module &M) {
01283   bool Changed = false;
01284 
01285   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
01286     Changed |= getContainedManager(Index)->doFinalization(M);
01287 
01288   return Changed;
01289 }
01290 
01291 /// cleanup - After running all passes, clean up pass manager cache.
01292 void FPPassManager::cleanup() {
01293  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01294     FunctionPass *FP = getContainedPass(Index);
01295     AnalysisResolver *AR = FP->getResolver();
01296     assert(AR && "Analysis Resolver is not set");
01297     AR->clearAnalysisImpls();
01298  }
01299 }
01300 
01301 void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
01302   if (!wasRun)
01303     return;
01304   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
01305     FPPassManager *FPPM = getContainedManager(Index);
01306     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
01307       FPPM->getContainedPass(Index)->releaseMemory();
01308     }
01309   }
01310   wasRun = false;
01311 }
01312 
01313 // Execute all the passes managed by this top level manager.
01314 // Return true if any function is modified by a pass.
01315 bool FunctionPassManagerImpl::run(Function &F) {
01316   bool Changed = false;
01317   TimingInfo::createTheTimeInfo();
01318 
01319   dumpArguments();
01320   dumpPasses();
01321 
01322   initializeAllAnalysisInfo();
01323   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
01324     Changed |= getContainedManager(Index)->runOnFunction(F);
01325 
01326   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
01327     getContainedManager(Index)->cleanup();
01328 
01329   wasRun = true;
01330   return Changed;
01331 }
01332 
01333 //===----------------------------------------------------------------------===//
01334 // FPPassManager implementation
01335 
01336 char FPPassManager::ID = 0;
01337 /// Print passes managed by this manager
01338 void FPPassManager::dumpPassStructure(unsigned Offset) {
01339   llvm::errs() << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
01340   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01341     FunctionPass *FP = getContainedPass(Index);
01342     FP->dumpPassStructure(Offset + 1);
01343     dumpLastUses(FP, Offset+1);
01344   }
01345 }
01346 
01347 
01348 /// Execute all of the passes scheduled for execution by invoking 
01349 /// runOnFunction method.  Keep track of whether any of the passes modifies 
01350 /// the function, and if so, return true.
01351 bool FPPassManager::runOnFunction(Function &F) {
01352   if (F.isDeclaration())
01353     return false;
01354 
01355   bool Changed = false;
01356 
01357   // Collect inherited analysis from Module level pass manager.
01358   populateInheritedAnalysis(TPM->activeStack);
01359 
01360   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01361     FunctionPass *FP = getContainedPass(Index);
01362 
01363     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
01364     dumpRequiredSet(FP);
01365 
01366     initializeAnalysisImpl(FP);
01367 
01368     {
01369       PassManagerPrettyStackEntry X(FP, F);
01370 
01371       if (TheTimeInfo) TheTimeInfo->passStarted(FP);
01372       Changed |= FP->runOnFunction(F);
01373       if (TheTimeInfo) TheTimeInfo->passEnded(FP);
01374     }
01375 
01376     if (Changed) 
01377       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
01378     dumpPreservedSet(FP);
01379 
01380     verifyPreservedAnalysis(FP);
01381     removeNotPreservedAnalysis(FP);
01382     recordAvailableAnalysis(FP);
01383     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
01384 
01385     // If dominator information is available then verify the info if requested.
01386     verifyDomInfo(*FP, F);
01387   }
01388   return Changed;
01389 }
01390 
01391 bool FPPassManager::runOnModule(Module &M) {
01392   bool Changed = doInitialization(M);
01393 
01394   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
01395     runOnFunction(*I);
01396 
01397   return Changed |= doFinalization(M);
01398 }
01399 
01400 bool FPPassManager::doInitialization(Module &M) {
01401   bool Changed = false;
01402 
01403   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
01404     Changed |= getContainedPass(Index)->doInitialization(M);
01405 
01406   return Changed;
01407 }
01408 
01409 bool FPPassManager::doFinalization(Module &M) {
01410   bool Changed = false;
01411 
01412   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
01413     Changed |= getContainedPass(Index)->doFinalization(M);
01414 
01415   return Changed;
01416 }
01417 
01418 //===----------------------------------------------------------------------===//
01419 // MPPassManager implementation
01420 
01421 /// Execute all of the passes scheduled for execution by invoking 
01422 /// runOnModule method.  Keep track of whether any of the passes modifies 
01423 /// the module, and if so, return true.
01424 bool
01425 MPPassManager::runOnModule(Module &M) {
01426   bool Changed = false;
01427 
01428   // Initialize on-the-fly passes
01429   for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
01430        I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
01431        I != E; ++I) {
01432     FunctionPassManagerImpl *FPP = I->second;
01433     Changed |= FPP->doInitialization(M);
01434   }
01435 
01436   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
01437     ModulePass *MP = getContainedPass(Index);
01438 
01439     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG,
01440                  M.getModuleIdentifier().c_str());
01441     dumpRequiredSet(MP);
01442 
01443     initializeAnalysisImpl(MP);
01444 
01445     {
01446       PassManagerPrettyStackEntry X(MP, M);
01447       if (TheTimeInfo) TheTimeInfo->passStarted(MP);
01448       Changed |= MP->runOnModule(M);
01449       if (TheTimeInfo) TheTimeInfo->passEnded(MP);
01450     }
01451 
01452     if (Changed) 
01453       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
01454                    M.getModuleIdentifier().c_str());
01455     dumpPreservedSet(MP);
01456     
01457     verifyPreservedAnalysis(MP);
01458     removeNotPreservedAnalysis(MP);
01459     recordAvailableAnalysis(MP);
01460     removeDeadPasses(MP, M.getModuleIdentifier().c_str(), ON_MODULE_MSG);
01461   }
01462 
01463   // Finalize on-the-fly passes
01464   for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
01465        I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
01466        I != E; ++I) {
01467     FunctionPassManagerImpl *FPP = I->second;
01468     // We don't know when is the last time an on-the-fly pass is run,
01469     // so we need to releaseMemory / finalize here
01470     FPP->releaseMemoryOnTheFly();
01471     Changed |= FPP->doFinalization(M);
01472   }
01473   return Changed;
01474 }
01475 
01476 /// Add RequiredPass into list of lower level passes required by pass P.
01477 /// RequiredPass is run on the fly by Pass Manager when P requests it
01478 /// through getAnalysis interface.
01479 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
01480   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
01481          "Unable to handle Pass that requires lower level Analysis pass");
01482   assert((P->getPotentialPassManagerType() < 
01483           RequiredPass->getPotentialPassManagerType()) &&
01484          "Unable to handle Pass that requires lower level Analysis pass");
01485 
01486   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
01487   if (!FPP) {
01488     FPP = new FunctionPassManagerImpl(0);
01489     // FPP is the top level manager.
01490     FPP->setTopLevelManager(FPP);
01491 
01492     OnTheFlyManagers[P] = FPP;
01493   }
01494   FPP->add(RequiredPass);
01495 
01496   // Register P as the last user of RequiredPass.
01497   SmallVector<Pass *, 12> LU;
01498   LU.push_back(RequiredPass);
01499   FPP->setLastUser(LU,  P);
01500 }
01501 
01502 /// Return function pass corresponding to PassInfo PI, that is 
01503 /// required by module pass MP. Instantiate analysis pass, by using
01504 /// its runOnFunction() for function F.
01505 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F){
01506   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
01507   assert(FPP && "Unable to find on the fly pass");
01508   
01509   FPP->releaseMemoryOnTheFly();
01510   FPP->run(F);
01511   return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(PI);
01512 }
01513 
01514 
01515 //===----------------------------------------------------------------------===//
01516 // PassManagerImpl implementation
01517 //
01518 /// run - Execute all of the passes scheduled for execution.  Keep track of
01519 /// whether any of the passes modifies the module, and if so, return true.
01520 bool PassManagerImpl::run(Module &M) {
01521   bool Changed = false;
01522   TimingInfo::createTheTimeInfo();
01523 
01524   dumpArguments();
01525   dumpPasses();
01526 
01527   initializeAllAnalysisInfo();
01528   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
01529     Changed |= getContainedManager(Index)->runOnModule(M);
01530   return Changed;
01531 }
01532 
01533 //===----------------------------------------------------------------------===//
01534 // PassManager implementation
01535 
01536 /// Create new pass manager
01537 PassManager::PassManager() {
01538   PM = new PassManagerImpl(0);
01539   // PM is the top level manager
01540   PM->setTopLevelManager(PM);
01541 }
01542 
01543 PassManager::~PassManager() {
01544   delete PM;
01545 }
01546 
01547 /// add - Add a pass to the queue of passes to run.  This passes ownership of
01548 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
01549 /// will be destroyed as well, so there is no need to delete the pass.  This
01550 /// implies that all passes MUST be allocated with 'new'.
01551 void PassManager::add(Pass *P) {
01552   PM->add(P);
01553 }
01554 
01555 /// run - Execute all of the passes scheduled for execution.  Keep track of
01556 /// whether any of the passes modifies the module, and if so, return true.
01557 bool PassManager::run(Module &M) {
01558   return PM->run(M);
01559 }
01560 
01561 //===----------------------------------------------------------------------===//
01562 // TimingInfo Class - This class is used to calculate information about the
01563 // amount of time each pass takes to execute.  This only happens with
01564 // -time-passes is enabled on the command line.
01565 //
01566 bool llvm::TimePassesIsEnabled = false;
01567 static cl::opt<bool,true>
01568 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
01569             cl::desc("Time each pass, printing elapsed time for each on exit"));
01570 
01571 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
01572 // a non null value (if the -time-passes option is enabled) or it leaves it
01573 // null.  It may be called multiple times.
01574 void TimingInfo::createTheTimeInfo() {
01575   if (!TimePassesIsEnabled || TheTimeInfo) return;
01576 
01577   // Constructed the first time this is called, iff -time-passes is enabled.
01578   // This guarantees that the object will be constructed before static globals,
01579   // thus it will be destroyed before them.
01580   static ManagedStatic<TimingInfo> TTI;
01581   TheTimeInfo = &*TTI;
01582 }
01583 
01584 /// If TimingInfo is enabled then start pass timer.
01585 void llvm::StartPassTimer(Pass *P) {
01586   if (TheTimeInfo) 
01587     TheTimeInfo->passStarted(P);
01588 }
01589 
01590 /// If TimingInfo is enabled then stop pass timer.
01591 void llvm::StopPassTimer(Pass *P) {
01592   if (TheTimeInfo) 
01593     TheTimeInfo->passEnded(P);
01594 }
01595 
01596 //===----------------------------------------------------------------------===//
01597 // PMStack implementation
01598 //
01599 
01600 // Pop Pass Manager from the stack and clear its analysis info.
01601 void PMStack::pop() {
01602 
01603   PMDataManager *Top = this->top();
01604   Top->initializeAnalysisInfo();
01605 
01606   S.pop_back();
01607 }
01608 
01609 // Push PM on the stack and set its top level manager.
01610 void PMStack::push(PMDataManager *PM) {
01611   assert(PM && "Unable to push. Pass Manager expected");
01612 
01613   if (!this->empty()) {
01614     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
01615 
01616     assert(TPM && "Unable to find top level manager");
01617     TPM->addIndirectPassManager(PM);
01618     PM->setTopLevelManager(TPM);
01619   }
01620 
01621   S.push_back(PM);
01622 }
01623 
01624 // Dump content of the pass manager stack.
01625 void PMStack::dump() {
01626   for (std::deque<PMDataManager *>::iterator I = S.begin(),
01627          E = S.end(); I != E; ++I)
01628     printf("%s ", dynamic_cast<Pass *>(*I)->getPassName());
01629 
01630   if (!S.empty())
01631     printf("\n");
01632 }
01633 
01634 /// Find appropriate Module Pass Manager in the PM Stack and
01635 /// add self into that manager. 
01636 void ModulePass::assignPassManager(PMStack &PMS, 
01637                                    PassManagerType PreferredType) {
01638   // Find Module Pass Manager
01639   while(!PMS.empty()) {
01640     PassManagerType TopPMType = PMS.top()->getPassManagerType();
01641     if (TopPMType == PreferredType)
01642       break; // We found desired pass manager
01643     else if (TopPMType > PMT_ModulePassManager)
01644       PMS.pop();    // Pop children pass managers
01645     else
01646       break;
01647   }
01648   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
01649   PMS.top()->add(this);
01650 }
01651 
01652 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
01653 /// in the PM Stack and add self into that manager. 
01654 void FunctionPass::assignPassManager(PMStack &PMS,
01655                                      PassManagerType PreferredType) {
01656 
01657   // Find Module Pass Manager
01658   while(!PMS.empty()) {
01659     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
01660       PMS.pop();
01661     else
01662       break; 
01663   }
01664   FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
01665 
01666   // Create new Function Pass Manager
01667   if (!FPP) {
01668     assert(!PMS.empty() && "Unable to create Function Pass Manager");
01669     PMDataManager *PMD = PMS.top();
01670 
01671     // [1] Create new Function Pass Manager
01672     FPP = new FPPassManager(PMD->getDepth() + 1);
01673     FPP->populateInheritedAnalysis(PMS);
01674 
01675     // [2] Set up new manager's top level manager
01676     PMTopLevelManager *TPM = PMD->getTopLevelManager();
01677     TPM->addIndirectPassManager(FPP);
01678 
01679     // [3] Assign manager to manage this new manager. This may create
01680     // and push new managers into PMS
01681     FPP->assignPassManager(PMS, PMD->getPassManagerType());
01682 
01683     // [4] Push new manager into PMS
01684     PMS.push(FPP);
01685   }
01686 
01687   // Assign FPP as the manager of this pass.
01688   FPP->add(this);
01689 }
01690 
01691 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
01692 /// in the PM Stack and add self into that manager. 
01693 void BasicBlockPass::assignPassManager(PMStack &PMS,
01694                                        PassManagerType PreferredType) {
01695   BBPassManager *BBP = NULL;
01696 
01697   // Basic Pass Manager is a leaf pass manager. It does not handle
01698   // any other pass manager.
01699   if (!PMS.empty())
01700     BBP = dynamic_cast<BBPassManager *>(PMS.top());
01701 
01702   // If leaf manager is not Basic Block Pass manager then create new
01703   // basic Block Pass manager.
01704 
01705   if (!BBP) {
01706     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
01707     PMDataManager *PMD = PMS.top();
01708 
01709     // [1] Create new Basic Block Manager
01710     BBP = new BBPassManager(PMD->getDepth() + 1);
01711 
01712     // [2] Set up new manager's top level manager
01713     // Basic Block Pass Manager does not live by itself
01714     PMTopLevelManager *TPM = PMD->getTopLevelManager();
01715     TPM->addIndirectPassManager(BBP);
01716 
01717     // [3] Assign manager to manage this new manager. This may create
01718     // and push new managers into PMS
01719     BBP->assignPassManager(PMS);
01720 
01721     // [4] Push new manager into PMS
01722     PMS.push(BBP);
01723   }
01724 
01725   // Assign BBP as the manager of this pass.
01726   BBP->add(this);
01727 }
01728 
01729 PassManagerBase::~PassManagerBase() {}
01730   
01731 /*===-- C Bindings --------------------------------------------------------===*/
01732 
01733 LLVMPassManagerRef LLVMCreatePassManager() {
01734   return wrap(new PassManager());
01735 }
01736 
01737 LLVMPassManagerRef LLVMCreateFunctionPassManager(LLVMModuleProviderRef P) {
01738   return wrap(new FunctionPassManager(unwrap(P)));
01739 }
01740 
01741 int LLVMRunPassManager(LLVMPassManagerRef PM, LLVMModuleRef M) {
01742   return unwrap<PassManager>(PM)->run(*unwrap(M));
01743 }
01744 
01745 int LLVMInitializeFunctionPassManager(LLVMPassManagerRef FPM) {
01746   return unwrap<FunctionPassManager>(FPM)->doInitialization();
01747 }
01748 
01749 int LLVMRunFunctionPassManager(LLVMPassManagerRef FPM, LLVMValueRef F) {
01750   return unwrap<FunctionPassManager>(FPM)->run(*unwrap<Function>(F));
01751 }
01752 
01753 int LLVMFinalizeFunctionPassManager(LLVMPassManagerRef FPM) {
01754   return unwrap<FunctionPassManager>(FPM)->doFinalization();
01755 }
01756 
01757 void LLVMDisposePassManager(LLVMPassManagerRef PM) {
01758   delete unwrap(PM);
01759 }