LLVM API Documentation

PassManagerT.h

Go to the documentation of this file.
00001 //===- PassManagerT.h - Container for Passes --------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the PassManagerT class.  This class is used to hold,
00011 // maintain, and optimize execution of Pass's.  The PassManager class ensures
00012 // that analysis results are available before a pass runs, and that Pass's are
00013 // destroyed when the PassManager is destroyed.
00014 //
00015 // The PassManagerT template is instantiated three times to do its job.  The
00016 // public PassManager class is a Pimpl around the PassManagerT<Module> interface
00017 // to avoid having all of the PassManager clients being exposed to the
00018 // implementation details herein.
00019 //
00020 //===----------------------------------------------------------------------===//
00021 
00022 #ifndef LLVM_PASSMANAGER_T_H
00023 #define LLVM_PASSMANAGER_T_H
00024 
00025 #include "llvm/Pass.h"
00026 #include "llvm/Support/CommandLine.h"
00027 #include "llvm/Support/LeakDetector.h"
00028 #include "llvm/Support/Timer.h"
00029 #include <algorithm>
00030 #include <iostream>
00031 
00032 namespace llvm {
00033 
00034 //===----------------------------------------------------------------------===//
00035 // Pass debugging information.  Often it is useful to find out what pass is
00036 // running when a crash occurs in a utility.  When this library is compiled with
00037 // debugging on, a command line option (--debug-pass) is enabled that causes the
00038 // pass name to be printed before it executes.
00039 //
00040 
00041 // Different debug levels that can be enabled...
00042 enum PassDebugLevel {
00043   None, Arguments, Structure, Executions, Details
00044 };
00045 
00046 static cl::opt<enum PassDebugLevel>
00047 PassDebugging("debug-pass", cl::Hidden,
00048               cl::desc("Print PassManager debugging information"),
00049               cl::values(
00050   clEnumVal(None      , "disable debug output"),
00051   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
00052   clEnumVal(Structure , "print pass structure before run()"),
00053   clEnumVal(Executions, "print pass name before it is executed"),
00054   clEnumVal(Details   , "print pass details when it is executed"),
00055                          clEnumValEnd));
00056 
00057 //===----------------------------------------------------------------------===//
00058 // PMDebug class - a set of debugging functions, that are not to be
00059 // instantiated by the template.
00060 //
00061 struct PMDebug {
00062   static void PerformPassStartupStuff(Pass *P) {
00063     // If debugging is enabled, print out argument information...
00064     if (PassDebugging >= Arguments) {
00065       std::cerr << "Pass Arguments: ";
00066       PrintArgumentInformation(P);
00067       std::cerr << "\n";
00068 
00069       // Print the pass execution structure
00070       if (PassDebugging >= Structure)
00071         P->dumpPassStructure();
00072     }
00073   }
00074 
00075   static void PrintArgumentInformation(const Pass *P);
00076   static void PrintPassInformation(unsigned,const char*,Pass *, Module *);
00077   static void PrintPassInformation(unsigned,const char*,Pass *, Function *);
00078   static void PrintPassInformation(unsigned,const char*,Pass *, BasicBlock *);
00079   static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P,
00080                                    const std::vector<AnalysisID> &);
00081 };
00082 
00083 
00084 //===----------------------------------------------------------------------===//
00085 // TimingInfo Class - This class is used to calculate information about the
00086 // amount of time each pass takes to execute.  This only happens when
00087 // -time-passes is enabled on the command line.
00088 //
00089 
00090 class TimingInfo {
00091   std::map<Pass*, Timer> TimingData;
00092   TimerGroup TG;
00093 
00094   // Private ctor, must use 'create' member
00095   TimingInfo() : TG("... Pass execution timing report ...") {}
00096 public:
00097   // TimingDtor - Print out information about timing information
00098   ~TimingInfo() {
00099     // Delete all of the timers...
00100     TimingData.clear();
00101     // TimerGroup is deleted next, printing the report.
00102   }
00103 
00104   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
00105   // to a non null value (if the -time-passes option is enabled) or it leaves it
00106   // null.  It may be called multiple times.
00107   static void createTheTimeInfo();
00108 
00109   void passStarted(Pass *P) {
00110     if (dynamic_cast<AnalysisResolver*>(P)) return;
00111     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
00112     if (I == TimingData.end())
00113       I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
00114     I->second.startTimer();
00115   }
00116   void passEnded(Pass *P) {
00117     if (dynamic_cast<AnalysisResolver*>(P)) return;
00118     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
00119     assert (I != TimingData.end() && "passStarted/passEnded not nested right!");
00120     I->second.stopTimer();
00121   }
00122 };
00123 
00124 static TimingInfo *TheTimeInfo;
00125 
00126 struct BBTraits {
00127   typedef BasicBlock UnitType;
00128   
00129   // PassClass - The type of passes tracked by this PassManager
00130   typedef BasicBlockPass PassClass;
00131 
00132   // SubPassClass - The types of classes that should be collated together
00133   // This is impossible to match, so BasicBlock instantiations of PassManagerT
00134   // do not collate.
00135   //
00136   typedef BasicBlockPassManager SubPassClass;
00137 
00138   // BatcherClass - The type to use for collation of subtypes... This class is
00139   // never instantiated for the BasicBlockPassManager, but it must be an
00140   // instance of PassClass to typecheck.
00141   //
00142   typedef PassClass BatcherClass;
00143 
00144   // ParentClass - The type of the parent PassManager...
00145   typedef FunctionPassManagerT ParentClass;
00146 
00147   // PMType - The type of this passmanager
00148   typedef BasicBlockPassManager PMType;
00149 };
00150 
00151 struct FTraits {
00152   typedef Function UnitType;
00153   
00154   // PassClass - The type of passes tracked by this PassManager
00155   typedef FunctionPass PassClass;
00156 
00157   // SubPassClass - The types of classes that should be collated together
00158   typedef BasicBlockPass SubPassClass;
00159 
00160   // BatcherClass - The type to use for collation of subtypes...
00161   typedef BasicBlockPassManager BatcherClass;
00162 
00163   // ParentClass - The type of the parent PassManager...
00164   typedef ModulePassManager ParentClass;
00165 
00166   // PMType - The type of this passmanager
00167   typedef FunctionPassManagerT PMType;
00168 };
00169 
00170 struct MTraits {
00171   typedef Module UnitType;
00172   
00173   // PassClass - The type of passes tracked by this PassManager
00174   typedef ModulePass PassClass;
00175 
00176   // SubPassClass - The types of classes that should be collated together
00177   typedef FunctionPass SubPassClass;
00178 
00179   // BatcherClass - The type to use for collation of subtypes...
00180   typedef FunctionPassManagerT BatcherClass;
00181 
00182   // ParentClass - The type of the parent PassManager...
00183   typedef AnalysisResolver ParentClass;
00184   
00185   // PMType - The type of this passmanager
00186   typedef ModulePassManager PMType;
00187 };
00188 
00189 
00190 //===----------------------------------------------------------------------===//
00191 // PassManagerT - Container object for passes.  The PassManagerT destructor
00192 // deletes all passes contained inside of the PassManagerT, so you shouldn't
00193 // delete passes manually, and all passes should be dynamically allocated.
00194 //
00195 template<typename Trait> class PassManagerT : public AnalysisResolver {
00196   
00197   typedef typename Trait::PassClass    PassClass;
00198   typedef typename Trait::UnitType     UnitType;
00199   typedef typename Trait::ParentClass  ParentClass;
00200   typedef typename Trait::SubPassClass SubPassClass;
00201   typedef typename Trait::BatcherClass BatcherClass;
00202   typedef typename Trait::PMType       PMType;
00203   
00204   friend class ModulePass;
00205   friend class FunctionPass;
00206   friend class BasicBlockPass;
00207   
00208   friend class ImmutablePass;
00209   
00210   friend class BasicBlockPassManager;
00211   friend class FunctionPassManagerT;
00212   friend class ModulePassManager;
00213 
00214   std::vector<PassClass*> Passes;               // List of passes to run
00215   std::vector<ImmutablePass*> ImmutablePasses;  // List of immutable passes
00216 
00217   // The parent of this pass manager...
00218   ParentClass * const Parent;
00219 
00220   // The current batcher if one is in use, or null
00221   BatcherClass *Batcher;
00222 
00223   // CurrentAnalyses - As the passes are being run, this map contains the
00224   // analyses that are available to the current pass for use.  This is accessed
00225   // through the getAnalysis() function in this class and in Pass.
00226   //
00227   std::map<AnalysisID, Pass*> CurrentAnalyses;
00228 
00229   // LastUseOf - This map keeps track of the last usage in our pipeline of a
00230   // particular pass.  When executing passes, the memory for .first is free'd
00231   // after .second is run.
00232   //
00233   std::map<Pass*, Pass*> LastUseOf;
00234 
00235 public:
00236   
00237   // getPMName() - Return the name of the unit the PassManager operates on for
00238   // debugging.
00239   virtual const char *getPMName() const =0;
00240   
00241   virtual const char *getPassName() const =0;
00242 
00243   virtual bool runPass(PassClass *P, UnitType *M) =0;
00244   
00245   // TODO:Figure out what pure virtuals remain.
00246   
00247   
00248   PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {}
00249   virtual ~PassManagerT() {
00250     // Delete all of the contained passes...
00251     for (typename std::vector<PassClass*>::iterator
00252            I = Passes.begin(), E = Passes.end(); I != E; ++I)
00253       delete *I;
00254 
00255     for (std::vector<ImmutablePass*>::iterator
00256            I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
00257       delete *I;
00258   }
00259 
00260   // run - Run all of the queued passes on the specified module in an optimal
00261   // way.
00262   virtual bool runOnUnit(UnitType *M) {
00263     closeBatcher();
00264     CurrentAnalyses.clear();
00265 
00266     TimingInfo::createTheTimeInfo();
00267 
00268     addImmutablePasses();
00269 
00270     // LastUserOf - This contains the inverted LastUseOfMap...
00271     std::map<Pass *, std::vector<Pass*> > LastUserOf;
00272     for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
00273                                           E = LastUseOf.end(); I != E; ++I)
00274       LastUserOf[I->second].push_back(I->first);
00275 
00276     // Output debug information...
00277     assert(dynamic_cast<PassClass*>(this) && 
00278            "It wasn't the PassClass I thought it was");
00279     if (Parent == 0) 
00280       PMDebug::PerformPassStartupStuff((dynamic_cast<PMType*>(this)));
00281 
00282     return runPasses(M, LastUserOf);
00283   }
00284 
00285   // dumpPassStructure - Implement the -debug-passes=PassStructure option
00286   inline void dumpPassStructure(unsigned Offset = 0) {
00287     // Print out the immutable passes...
00288     
00289     for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i)
00290       ImmutablePasses[i]->dumpPassStructure(0);
00291 
00292     std::cerr << std::string(Offset*2, ' ') << this->getPMName()
00293               << " Pass Manager\n";
00294     for (typename std::vector<PassClass*>::iterator
00295            I = Passes.begin(), E = Passes.end(); I != E; ++I) {
00296       PassClass *P = *I;
00297       P->dumpPassStructure(Offset+1);
00298 
00299       // Loop through and see which classes are destroyed after this one...
00300       for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
00301                                             E = LastUseOf.end(); I != E; ++I) {
00302         if (P == I->second) {
00303           std::cerr << "--" << std::string(Offset*2, ' ');
00304           I->first->dumpPassStructure(0);
00305         }
00306       }
00307     }
00308   }
00309 
00310   Pass *getImmutablePassOrNull(const PassInfo *ID) const {
00311     for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
00312       const PassInfo *IPID = ImmutablePasses[i]->getPassInfo();
00313       if (IPID == ID)
00314         return ImmutablePasses[i];
00315 
00316       // This pass is the current implementation of all of the interfaces it
00317       // implements as well.
00318       //
00319       const std::vector<const PassInfo*> &II =
00320         IPID->getInterfacesImplemented();
00321       for (unsigned j = 0, e = II.size(); j != e; ++j)
00322         if (II[j] == ID) return ImmutablePasses[i];
00323     }
00324     return 0;
00325   }
00326 
00327   Pass *getAnalysisOrNullDown(const PassInfo *ID) const {
00328     std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
00329 
00330     if (I != CurrentAnalyses.end())
00331       return I->second;  // Found it.
00332 
00333     if (Pass *P = getImmutablePassOrNull(ID))
00334       return P;
00335 
00336     if (Batcher)
00337       return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID);
00338     return 0;
00339   }
00340 
00341   Pass *getAnalysisOrNullUp(const PassInfo *ID) const {
00342     std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
00343     if (I != CurrentAnalyses.end())
00344       return I->second;  // Found it.
00345 
00346     if (Parent)          // Try scanning...
00347       return Parent->getAnalysisOrNullUp(ID);
00348     else if (!ImmutablePasses.empty())
00349       return getImmutablePassOrNull(ID);
00350     return 0;
00351   }
00352 
00353   // markPassUsed - Inform higher level pass managers (and ourselves)
00354   // that these analyses are being used by this pass.  This is used to
00355   // make sure that analyses are not free'd before we have to use
00356   // them...
00357   //
00358   void markPassUsed(const PassInfo *P, Pass *User) {
00359     std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(P);
00360 
00361     if (I != CurrentAnalyses.end()) {
00362       LastUseOf[I->second] = User;    // Local pass, extend the lifetime
00363 
00364       // Prolong live range of analyses that are needed after an analysis pass
00365       // is destroyed, for querying by subsequent passes
00366       AnalysisUsage AnUsage;
00367       I->second->getAnalysisUsage(AnUsage);
00368       const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
00369       for (std::vector<AnalysisID>::const_iterator i = IDs.begin(),
00370              e = IDs.end(); i != e; ++i)
00371         markPassUsed(*i, User);
00372 
00373     } else {
00374       // Pass not in current available set, must be a higher level pass
00375       // available to us, propagate to parent pass manager...  We tell the
00376       // parent that we (the passmanager) are using the analysis so that it
00377       // frees the analysis AFTER this pass manager runs.
00378       //
00379       if (Parent) {
00380         assert(dynamic_cast<Pass*>(this) && 
00381                "It wasn't the Pass type I thought it was.");
00382         Parent->markPassUsed(P, dynamic_cast<Pass*>(this));
00383       } else {
00384         assert(getAnalysisOrNullUp(P) &&
00385                dynamic_cast<ImmutablePass*>(getAnalysisOrNullUp(P)) &&
00386                "Pass available but not found! "
00387                "Perhaps this is a module pass requiring a function pass?");
00388       }
00389     }
00390   }
00391 
00392   // Return the number of parent PassManagers that exist
00393   virtual unsigned getDepth() const {
00394     if (Parent == 0) return 0;
00395     return 1 + Parent->getDepth();
00396   }
00397 
00398   virtual unsigned getNumContainedPasses() const { return Passes.size(); }
00399   
00400   virtual const Pass *getContainedPass(unsigned N) const {
00401     assert(N < Passes.size() && "Pass number out of range!");
00402     return Passes[N];
00403   }
00404 
00405   // add - Add a pass to the queue of passes to run.  This gives ownership of
00406   // the Pass to the PassManager.  When the PassManager is destroyed, the pass
00407   // will be destroyed as well, so there is no need to delete the pass.  This
00408   // implies that all passes MUST be new'd.
00409   //
00410   void add(PassClass *P) {
00411     // Get information about what analyses the pass uses...
00412     AnalysisUsage AnUsage;
00413     P->getAnalysisUsage(AnUsage);
00414     
00415     addRequiredPasses(AnUsage.getRequiredSet());
00416     
00417     // Tell the pass to add itself to this PassManager... the way it does so
00418     // depends on the class of the pass, and is critical to laying out passes in
00419     // an optimal order..
00420     //
00421     assert(dynamic_cast<PMType*>(this) && 
00422         "It wasn't the right passmanager type.");
00423     P->addToPassManager(static_cast<PMType*>(this), AnUsage);
00424   }
00425 
00426   // add - H4x0r an ImmutablePass into a PassManager that might not be
00427   // expecting one.
00428   //
00429   void add(ImmutablePass *P) {
00430     // Get information about what analyses the pass uses...
00431     AnalysisUsage AnUsage;
00432     P->getAnalysisUsage(AnUsage);
00433     
00434     addRequiredPasses(AnUsage.getRequiredSet());
00435     
00436     // Add the ImmutablePass to this PassManager.
00437     addPass(P, AnUsage);
00438   }
00439 
00440 private:
00441   // addPass - These functions are used to implement the subclass specific
00442   // behaviors present in PassManager.  Basically the add(Pass*) method ends up
00443   // reflecting its behavior into a Pass::addToPassManager call.  Subclasses of
00444   // Pass override it specifically so that they can reflect the type
00445   // information inherent in "this" back to the PassManager.
00446   //
00447   // For generic Pass subclasses (which are interprocedural passes), we simply
00448   // add the pass to the end of the pass list and terminate any accumulation of
00449   // FunctionPass's that are present.
00450   //
00451   void addPass(PassClass *P, AnalysisUsage &AnUsage) {
00452     const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
00453 
00454     // FIXME: If this pass being added isn't killed by any of the passes in the
00455     // batcher class then we can reorder the pass to execute before the batcher
00456     // does, which will potentially allow us to batch more passes!
00457     //
00458     if (Batcher)
00459       closeBatcher();                     // This pass cannot be batched!
00460 
00461     // Set the Resolver instance variable in the Pass so that it knows where to
00462     // find this object...
00463     //
00464     setAnalysisResolver(P, this);
00465     Passes.push_back(P);
00466 
00467     // Inform higher level pass managers (and ourselves) that these analyses are
00468     // being used by this pass.  This is used to make sure that analyses are not
00469     // free'd before we have to use them...
00470     //
00471     for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
00472            E = RequiredSet.end(); I != E; ++I)
00473       markPassUsed(*I, P);     // Mark *I as used by P
00474 
00475     removeNonPreservedAnalyses(AnUsage);
00476     
00477     makeCurrentlyAvailable(P);
00478     
00479     // For now assume that our results are never used...
00480     LastUseOf[P] = P;
00481   }
00482   
00483   // For FunctionPass subclasses, we must be sure to batch the FunctionPass's
00484   // together in a BatcherClass object so that all of the analyses are run
00485   // together a function at a time.
00486   //
00487   void addPass(SubPassClass *MP, AnalysisUsage &AnUsage) {
00488 
00489     if (Batcher == 0) { // If we don't have a batcher yet, make one now.
00490       assert(dynamic_cast<PMType*>(this) && 
00491              "It wasn't the PassManager type I thought it was");
00492       Batcher = new BatcherClass((static_cast<PMType*>(this)));
00493     }
00494 
00495     // The Batcher will queue the passes up
00496     MP->addToPassManager(Batcher, AnUsage);
00497   }
00498 
00499   // closeBatcher - Terminate the batcher that is being worked on.
00500   void closeBatcher() {
00501     if (Batcher) {
00502       Passes.push_back(Batcher);
00503       Batcher = 0;
00504     }
00505   }
00506 
00507   void addRequiredPasses(const std::vector<AnalysisID> &Required) {
00508     for (std::vector<AnalysisID>::const_iterator I = Required.begin(),
00509          E = Required.end(); I != E; ++I) {
00510       if (getAnalysisOrNullDown(*I) == 0) {
00511         Pass *AP = (*I)->createPass();
00512         if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (AP)) add(IP);
00513         else if (PassClass *RP = dynamic_cast<PassClass *> (AP)) add(RP);
00514         else assert (0 && "Wrong kind of pass for this PassManager");
00515       }
00516     }
00517   }
00518 
00519 public:
00520   // When an ImmutablePass is added, it gets added to the top level pass
00521   // manager.
00522   void addPass(ImmutablePass *IP, AnalysisUsage &AU) {
00523     if (Parent) { // Make sure this request goes to the top level passmanager...
00524       Parent->addPass(IP, AU);
00525       return;
00526     }
00527 
00528     // Set the Resolver instance variable in the Pass so that it knows where to
00529     // find this object...
00530     //
00531     setAnalysisResolver(IP, this);
00532     ImmutablePasses.push_back(IP);
00533 
00534     // All Required analyses should be available to the pass as it initializes!
00535     // Here we fill in the AnalysisImpls member of the pass so that it can
00536     // successfully use the getAnalysis() method to retrieve the implementations
00537     // it needs.
00538     //
00539     IP->AnalysisImpls.clear();
00540     IP->AnalysisImpls.reserve(AU.getRequiredSet().size());
00541     for (std::vector<const PassInfo *>::const_iterator
00542            I = AU.getRequiredSet().begin(),
00543            E = AU.getRequiredSet().end(); I != E; ++I) {
00544       Pass *Impl = getAnalysisOrNullUp(*I);
00545       if (Impl == 0) {
00546         std::cerr << "Analysis '" << (*I)->getPassName()
00547                   << "' used but not available!";
00548         assert(0 && "Analysis used but not available!");
00549       } else if (PassDebugging == Details) {
00550         if ((*I)->getPassName() != std::string(Impl->getPassName()))
00551           std::cerr << "    Interface '" << (*I)->getPassName()
00552                     << "' implemented by '" << Impl->getPassName() << "'\n";
00553       }
00554       IP->AnalysisImpls.push_back(std::make_pair(*I, Impl));
00555     }
00556 
00557     // Initialize the immutable pass...
00558     IP->initializePass();
00559   }
00560 private:
00561   
00562   // Add any immutable passes to the CurrentAnalyses set...
00563   inline void addImmutablePasses() { 
00564     for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
00565       ImmutablePass *IPass = ImmutablePasses[i];
00566       if (const PassInfo *PI = IPass->getPassInfo()) {
00567         CurrentAnalyses[PI] = IPass;
00568 
00569         const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
00570         for (unsigned i = 0, e = II.size(); i != e; ++i)
00571           CurrentAnalyses[II[i]] = IPass;
00572       }
00573     }
00574   }
00575   
00576   // Run all of the passes
00577   inline bool runPasses(UnitType *M, 
00578                  std::map<Pass *, std::vector<Pass*> > &LastUserOf) { 
00579     bool MadeChanges = false;
00580     
00581     for (unsigned i = 0, e = Passes.size(); i < e; ++i) {
00582       PassClass *P = Passes[i];
00583 
00584       PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, M);
00585 
00586       // Get information about what analyses the pass uses...
00587       AnalysisUsage AnUsage;
00588       P->getAnalysisUsage(AnUsage);
00589       PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P,
00590                                     AnUsage.getRequiredSet());
00591       
00592       initialiseAnalysisImpl(P, AnUsage);
00593       
00594       // Run the sub pass!
00595       if (TheTimeInfo) TheTimeInfo->passStarted(P);
00596       bool Changed = runPass(P, M);
00597       if (TheTimeInfo) TheTimeInfo->passEnded(P);
00598       MadeChanges |= Changed;
00599 
00600       // Check for memory leaks by the pass...
00601       LeakDetector::checkForGarbage(std::string("after running pass '") +
00602                                     P->getPassName() + "'");
00603 
00604       if (Changed)
00605         PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P, M);
00606       PMDebug::PrintAnalysisSetInfo(getDepth(), "Preserved", P,
00607                                     AnUsage.getPreservedSet());
00608       
00609       // Erase all analyses not in the preserved set
00610       removeNonPreservedAnalyses(AnUsage);
00611       
00612       makeCurrentlyAvailable(P);
00613       
00614       // free memory and remove dead passes from the CurrentAnalyses list...
00615       removeDeadPasses(P, M, LastUserOf);
00616     }
00617     
00618     return MadeChanges;
00619   }
00620   
00621   // All Required analyses should be available to the pass as it runs!  Here
00622   // we fill in the AnalysisImpls member of the pass so that it can
00623   // successfully use the getAnalysis() method to retrieve the
00624   // implementations it needs.
00625   //
00626   inline void initialiseAnalysisImpl(PassClass *P, AnalysisUsage &AnUsage) { 
00627     P->AnalysisImpls.clear();
00628     P->AnalysisImpls.reserve(AnUsage.getRequiredSet().size());
00629     
00630     for (std::vector<const PassInfo *>::const_iterator
00631          I = AnUsage.getRequiredSet().begin(),
00632          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
00633       Pass *Impl = getAnalysisOrNullUp(*I);
00634       if (Impl == 0) {
00635         std::cerr << "Analysis '" << (*I)->getPassName()
00636                   << "' used but not available!";
00637         assert(0 && "Analysis used but not available!");
00638       } else if (PassDebugging == Details) {
00639         if ((*I)->getPassName() != std::string(Impl->getPassName()))
00640           std::cerr << "    Interface '" << (*I)->getPassName()
00641                   << "' implemented by '" << Impl->getPassName() << "'\n";
00642       }
00643       
00644       P->AnalysisImpls.push_back(std::make_pair(*I, Impl));
00645     }
00646   }
00647   
00648   inline void removeNonPreservedAnalyses(AnalysisUsage &AnUsage) { 
00649     if (!AnUsage.getPreservesAll()) {
00650       const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
00651       for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin(),
00652            E = CurrentAnalyses.end(); I != E; )
00653         if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) !=
00654             PreservedSet.end())
00655           ++I; // This analysis is preserved, leave it in the available set...
00656       else {
00657         if (!dynamic_cast<ImmutablePass*>(I->second)) {
00658           std::map<AnalysisID, Pass*>::iterator J = I++;
00659           CurrentAnalyses.erase(J);   // Analysis not preserved!
00660         } else {
00661           ++I;
00662         }
00663       }
00664     }
00665   }
00666   
00667   inline void removeDeadPasses(Pass* P, UnitType *M, 
00668               std::map<Pass *, std::vector<Pass*> > &LastUserOf) { 
00669     std::vector<Pass*> &DeadPass = LastUserOf[P];
00670     for (std::vector<Pass*>::iterator I = DeadPass.begin(),E = DeadPass.end();
00671           I != E; ++I) {
00672       PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I, M);
00673       (*I)->releaseMemory();
00674     }
00675     
00676     for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin();
00677           I != CurrentAnalyses.end(); ) {
00678       std::vector<Pass*>::iterator DPI = std::find(DeadPass.begin(),
00679                                                     DeadPass.end(), I->second);
00680       if (DPI != DeadPass.end()) {    // This pass is dead now... remove it
00681         std::map<AnalysisID, Pass*>::iterator IDead = I++;
00682         CurrentAnalyses.erase(IDead);
00683       } else {
00684         ++I;  // Move on to the next element...
00685       }
00686     }
00687   }
00688   
00689   inline void makeCurrentlyAvailable(Pass* P) { 
00690     if (const PassInfo *PI = P->getPassInfo()) {
00691       CurrentAnalyses[PI] = P;
00692 
00693       // This pass is the current implementation of all of the interfaces it
00694       // implements as well.
00695       //
00696       const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
00697       for (unsigned i = 0, e = II.size(); i != e; ++i)
00698         CurrentAnalyses[II[i]] = P;
00699     }
00700   }
00701 };
00702 
00703 
00704 
00705 //===----------------------------------------------------------------------===//
00706 // BasicBlockPassManager
00707 //
00708 // This pass manager is used to group together all of the BasicBlockPass's
00709 // into a single unit.
00710 //
00711 class BasicBlockPassManager : public BasicBlockPass, 
00712                               public BBTraits, 
00713                               public PassManagerT<BBTraits> {
00714 public:
00715   BasicBlockPassManager(BBTraits::ParentClass* PC) : 
00716     PassManagerT<BBTraits>(PC) {
00717   }
00718   
00719   BasicBlockPassManager(BasicBlockPassManager* BBPM) : 
00720     PassManagerT<BBTraits>(BBPM->Parent) {
00721   }
00722   
00723   // runPass - Specify how the pass should be run on the UnitType
00724   virtual bool runPass(BBTraits::PassClass *P, BasicBlock *M) {
00725     // TODO: init and finalize
00726     return P->runOnBasicBlock(*M);
00727   }
00728   
00729   virtual ~BasicBlockPassManager() {}
00730   
00731   virtual void dumpPassStructure(unsigned Offset = 0) { 
00732     PassManagerT<BBTraits>::dumpPassStructure(Offset);
00733   }
00734   
00735   // getPMName() - Return the name of the unit the PassManager operates on for
00736   // debugging.
00737   virtual const char *getPMName() const { return "BasicBlock"; }
00738   
00739   virtual const char *getPassName() const { return "BasicBlock Pass Manager"; }
00740   
00741   virtual bool doInitialization(Module &M);
00742   virtual bool doInitialization(Function &F);
00743   virtual bool runOnBasicBlock(BasicBlock &BB);
00744   virtual bool doFinalization(Function &F);
00745   virtual bool doFinalization(Module &M);
00746   
00747   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00748     AU.setPreservesAll();
00749   }
00750 };
00751 
00752 //===----------------------------------------------------------------------===//
00753 // FunctionPassManager
00754 //
00755 // This pass manager is used to group together all of the FunctionPass's
00756 // into a single unit.
00757 //
00758 class FunctionPassManagerT : public FunctionPass, 
00759                              public FTraits, 
00760                              public PassManagerT<FTraits> {
00761 public:
00762   FunctionPassManagerT() : PassManagerT<FTraits>(0) {}
00763   
00764   // Parent constructor
00765   FunctionPassManagerT(FTraits::ParentClass* PC) : PassManagerT<FTraits>(PC) {}
00766   
00767   FunctionPassManagerT(FunctionPassManagerT* FPM) : 
00768     PassManagerT<FTraits>(FPM->Parent) {
00769   }
00770   
00771   virtual ~FunctionPassManagerT() {}
00772   
00773   virtual void dumpPassStructure(unsigned Offset = 0) { 
00774     PassManagerT<FTraits>::dumpPassStructure(Offset);
00775   }
00776   
00777   // getPMName() - Return the name of the unit the PassManager operates on for
00778   // debugging.
00779   virtual const char *getPMName() const { return "Function"; }
00780   
00781   virtual const char *getPassName() const { return "Function Pass Manager"; }
00782   
00783   virtual bool runOnFunction(Function &F);
00784   
00785   virtual bool doInitialization(Module &M);
00786   
00787   virtual bool doFinalization(Module &M);
00788   
00789   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00790     AU.setPreservesAll();
00791   }
00792   
00793   // runPass - Specify how the pass should be run on the UnitType
00794   virtual bool runPass(FTraits::PassClass *P, Function *F) {
00795     return P->runOnFunction(*F);
00796   }
00797 };
00798 
00799 
00800 //===----------------------------------------------------------------------===//
00801 // ModulePassManager
00802 //
00803 // This is the top level PassManager implementation that holds generic passes.
00804 //
00805 class ModulePassManager : public ModulePass, 
00806                           public MTraits, 
00807                           public PassManagerT<MTraits> {
00808 public:
00809   ModulePassManager() : PassManagerT<MTraits>(0) {}
00810   
00811   // Batcher Constructor
00812   ModulePassManager(MTraits::ParentClass* PC) : PassManagerT<MTraits>(PC) {}
00813   
00814   ModulePassManager(ModulePassManager* MPM) : 
00815     PassManagerT<MTraits>((MPM->Parent)) {
00816   }
00817   
00818   virtual ~ModulePassManager() {}
00819   
00820   virtual void dumpPassStructure(unsigned Offset = 0) { 
00821     PassManagerT<MTraits>::dumpPassStructure(Offset);
00822   }
00823   
00824   // getPMName() - Return the name of the unit the PassManager operates on for
00825   // debugging.
00826   virtual const char *getPassName() const { return "Module Pass Manager"; }
00827   
00828   // getPMName() - Return the name of the unit the PassManager operates on for
00829   // debugging.
00830   virtual const char *getPMName() const { return "Module"; }
00831   
00832   // runOnModule - Implement the PassManager interface.
00833   virtual bool runOnModule(Module &M);
00834   
00835   // runPass - Specify how the pass should be run on the UnitType
00836   virtual bool runPass(MTraits::PassClass *P, Module *M) {
00837     return P->runOnModule(*M);
00838   }
00839 };
00840 
00841 //===----------------------------------------------------------------------===//
00842 // PassManager Method Implementations
00843 //
00844 
00845 // BasicBlockPassManager Implementations
00846 //
00847 
00848 inline bool BasicBlockPassManager::runOnBasicBlock(BasicBlock &BB) {
00849   return ((BBTraits::PMType*)this)->runOnUnit(&BB);
00850 }
00851 
00852 inline bool BasicBlockPassManager::doInitialization(Module &M) {
00853   bool Changed = false;
00854   for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i)
00855     ((BBTraits::PMType*)this)->Passes[i]->doInitialization(M);
00856   return Changed;
00857 }
00858 
00859 inline bool BasicBlockPassManager::doInitialization(Function &F) {
00860   bool Changed = false;
00861   for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i)
00862     ((BBTraits::PMType*)this)->Passes[i]->doInitialization(F);
00863   return Changed;
00864 }
00865 
00866 inline bool BasicBlockPassManager::doFinalization(Function &F) {
00867   bool Changed = false;
00868   for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i)
00869     ((BBTraits::PMType*)this)->Passes[i]->doFinalization(F);
00870   return Changed;
00871 }
00872 
00873 inline bool BasicBlockPassManager::doFinalization(Module &M) {
00874   bool Changed = false;
00875   for (unsigned i=0, e = ((BBTraits::PMType*)this)->Passes.size(); i != e; ++i)
00876     ((BBTraits::PMType*)this)->Passes[i]->doFinalization(M);
00877   return Changed;
00878 }
00879 
00880 // FunctionPassManagerT Implementations
00881 //
00882 
00883 inline bool FunctionPassManagerT::runOnFunction(Function &F) {
00884   return ((FTraits::PMType*)this)->runOnUnit(&F);
00885 }
00886 
00887 inline bool FunctionPassManagerT::doInitialization(Module &M) {
00888   bool Changed = false;
00889   for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i)
00890     ((FTraits::PMType*)this)->Passes[i]->doInitialization(M);
00891   return Changed;
00892 }
00893 
00894 inline bool FunctionPassManagerT::doFinalization(Module &M) {
00895   bool Changed = false;
00896   for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i)
00897     ((FTraits::PMType*)this)->Passes[i]->doFinalization(M);
00898   return Changed;
00899 }
00900 
00901 // ModulePassManager Implementations
00902 //
00903 
00904 bool ModulePassManager::runOnModule(Module &M) {
00905   return ((PassManagerT<MTraits>*)this)->runOnUnit(&M);
00906 }
00907 
00908 } // End llvm namespace
00909 
00910 #endif