X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FPassManagerT.h;h=de0fc46f7e40496ba6f58b9e7fd080ea8e334dcd;hb=f28265402130eb03762d9a6333fd8f87765a8875;hp=3f2dc76f5140bb5d567afd6055f9910aac69bbc5;hpb=7a40d6db08e44c72f2183177718a8c745e4eb21b;p=oota-llvm.git diff --git a/lib/VMCore/PassManagerT.h b/lib/VMCore/PassManagerT.h index 3f2dc76f514..de0fc46f7e4 100644 --- a/lib/VMCore/PassManagerT.h +++ b/lib/VMCore/PassManagerT.h @@ -1,4 +1,11 @@ -//===- PassManagerT.h - Container for Passes ---------------------*- C++ -*--=// +//===- PassManagerT.h - Container for Passes --------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file defines the PassManagerT class. This class is used to hold, // maintain, and optimize execution of Pass's. The PassManager class ensures @@ -16,10 +23,13 @@ #define LLVM_PASSMANAGER_T_H #include "llvm/Pass.h" -#include "Support/CommandLine.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/LeakDetector.h" +#include "llvm/Support/Timer.h" #include #include -class Annotable; + +namespace llvm { //===----------------------------------------------------------------------===// // Pass debugging information. Often it is useful to find out what pass is @@ -42,7 +52,7 @@ PassDebugging("debug-pass", cl::Hidden, clEnumVal(Structure , "print pass structure before run()"), clEnumVal(Executions, "print pass name before it is executed"), clEnumVal(Details , "print pass details when it is executed"), - 0)); + clEnumValEnd)); //===----------------------------------------------------------------------===// // PMDebug class - a set of debugging functions, that are not to be @@ -63,7 +73,9 @@ struct PMDebug { } static void PrintArgumentInformation(const Pass *P); - static void PrintPassInformation(unsigned,const char*,Pass *, Annotable *); + static void PrintPassInformation(unsigned,const char*,Pass *, Module *); + static void PrintPassInformation(unsigned,const char*,Pass *, Function *); + static void PrintPassInformation(unsigned,const char*,Pass *, BasicBlock *); static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P, const std::vector &); }; @@ -74,48 +86,133 @@ struct PMDebug { // amount of time each pass takes to execute. This only happens when // -time-passes is enabled on the command line. // + class TimingInfo { - std::map TimingData; - TimingInfo() {} // Private ctor, must use create member + std::map TimingData; + TimerGroup TG; + + // Private ctor, must use 'create' member + TimingInfo() : TG("... Pass execution timing report ...") {} public: - // Create method. If Timing is enabled, this creates and returns a new timing - // object, otherwise it returns null. + // TimingDtor - Print out information about timing information + ~TimingInfo() { + // Delete all of the timers... + TimingData.clear(); + // TimerGroup is deleted next, printing the report. + } + + // createTheTimeInfo - This method either initializes the TheTimeInfo pointer + // to a non null value (if the -time-passes option is enabled) or it leaves it + // null. It may be called multiple times. + static void createTheTimeInfo(); + + void passStarted(Pass *P) { + if (dynamic_cast(P)) return; + std::map::iterator I = TimingData.find(P); + if (I == TimingData.end()) + I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first; + I->second.startTimer(); + } + void passEnded(Pass *P) { + if (dynamic_cast(P)) return; + std::map::iterator I = TimingData.find(P); + assert (I != TimingData.end() && "passStarted/passEnded not nested right!"); + I->second.stopTimer(); + } +}; + +static TimingInfo *TheTimeInfo; + +struct BBTraits { + typedef BasicBlock UnitType; + + // PassClass - The type of passes tracked by this PassManager + typedef BasicBlockPass PassClass; + + // SubPassClass - The types of classes that should be collated together + // This is impossible to match, so BasicBlock instantiations of PassManagerT + // do not collate. // - static TimingInfo *create(); + typedef BasicBlockPassManager SubPassClass; - // TimingDtor - Print out information about timing information - ~TimingInfo(); + // BatcherClass - The type to use for collation of subtypes... This class is + // never instantiated for the BasicBlockPassManager, but it must be an + // instance of PassClass to typecheck. + // + typedef PassClass BatcherClass; + + // ParentClass - The type of the parent PassManager... + typedef FunctionPassManagerT ParentClass; - void passStarted(Pass *P); - void passEnded(Pass *P); + // PMType - The type of this passmanager + typedef BasicBlockPassManager PMType; }; +struct FTraits { + typedef Function UnitType; + + // PassClass - The type of passes tracked by this PassManager + typedef FunctionPass PassClass; + + // SubPassClass - The types of classes that should be collated together + typedef BasicBlockPass SubPassClass; + + // BatcherClass - The type to use for collation of subtypes... + typedef BasicBlockPassManager BatcherClass; + // ParentClass - The type of the parent PassManager... + typedef ModulePassManager ParentClass; -//===----------------------------------------------------------------------===// -// Declare the PassManagerTraits which will be specialized... -// -template class PassManagerTraits; // Do not define. + // PMType - The type of this passmanager + typedef FunctionPassManagerT PMType; +}; + +struct MTraits { + typedef Module UnitType; + + // PassClass - The type of passes tracked by this PassManager + typedef ModulePass PassClass; + + // SubPassClass - The types of classes that should be collated together + typedef FunctionPass SubPassClass; + + // BatcherClass - The type to use for collation of subtypes... + typedef FunctionPassManagerT BatcherClass; + + // ParentClass - The type of the parent PassManager... + typedef AnalysisResolver ParentClass; + + // PMType - The type of this passmanager + typedef ModulePassManager PMType; +}; //===----------------------------------------------------------------------===// // PassManagerT - Container object for passes. The PassManagerT destructor -// deletes all passes contained inside of the PassManagerT, so you shouldn't +// deletes all passes contained inside of the PassManagerT, so you shouldn't // delete passes manually, and all passes should be dynamically allocated. // -template -class PassManagerT : public PassManagerTraits,public AnalysisResolver{ - typedef PassManagerTraits Traits; - typedef typename Traits::PassClass PassClass; - typedef typename Traits::SubPassClass SubPassClass; - typedef typename Traits::BatcherClass BatcherClass; - typedef typename Traits::ParentClass ParentClass; - - friend typename Traits::PassClass; - friend typename Traits::SubPassClass; - friend class Traits; +template class PassManagerT : public AnalysisResolver { + + typedef typename Trait::PassClass PassClass; + typedef typename Trait::UnitType UnitType; + typedef typename Trait::ParentClass ParentClass; + typedef typename Trait::SubPassClass SubPassClass; + typedef typename Trait::BatcherClass BatcherClass; + typedef typename Trait::PMType PMType; + + friend class ModulePass; + friend class FunctionPass; + friend class BasicBlockPass; + + friend class ImmutablePass; + + friend class BasicBlockPassManager; + friend class FunctionPassManagerT; + friend class ModulePassManager; - std::vector Passes; // List of passes to run + std::vector Passes; // List of passes to run + std::vector ImmutablePasses; // List of immutable passes // The parent of this pass manager... ParentClass * const Parent; @@ -136,106 +233,63 @@ class PassManagerT : public PassManagerTraits,public AnalysisResolver{ std::map LastUseOf; public: + + // getPMName() - Return the name of the unit the PassManager operates on for + // debugging. + virtual const char *getPMName() const =0; + + virtual const char *getPassName() const =0; + + virtual bool runPass(PassClass *P, UnitType *M) =0; + + // TODO:Figure out what pure virtuals remain. + + PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {} - ~PassManagerT() { + virtual ~PassManagerT() { // Delete all of the contained passes... for (typename std::vector::iterator I = Passes.begin(), E = Passes.end(); I != E; ++I) delete *I; + + for (std::vector::iterator + I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I) + delete *I; } // run - Run all of the queued passes on the specified module in an optimal // way. virtual bool runOnUnit(UnitType *M) { - bool MadeChanges = false; closeBatcher(); CurrentAnalyses.clear(); + TimingInfo::createTheTimeInfo(); + + addImmutablePasses(); + // LastUserOf - This contains the inverted LastUseOfMap... std::map > LastUserOf; for (std::map::iterator I = LastUseOf.begin(), E = LastUseOf.end(); I != E; ++I) LastUserOf[I->second].push_back(I->first); - // Output debug information... - if (Parent == 0) PMDebug::PerformPassStartupStuff(this); - - // Run all of the passes - for (unsigned i = 0, e = Passes.size(); i < e; ++i) { - PassClass *P = Passes[i]; - - PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, - (Annotable*)M); - - // Get information about what analyses the pass uses... - AnalysisUsage AnUsage; - P->getAnalysisUsage(AnUsage); - PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P, - AnUsage.getRequiredSet()); - -#ifndef NDEBUG - // All Required analyses should be available to the pass as it runs! - for (std::vector::const_iterator - I = AnUsage.getRequiredSet().begin(), - E = AnUsage.getRequiredSet().end(); I != E; ++I) { - assert(getAnalysisOrNullUp(*I) && "Analysis used but not available!"); - } -#endif - - // Run the sub pass! - startPass(P); - bool Changed = runPass(P, M); - endPass(P); - MadeChanges |= Changed; + assert(dynamic_cast(this) && + "It wasn't the PassClass I thought it was"); + if (Parent == 0) + PMDebug::PerformPassStartupStuff((dynamic_cast(this))); - if (Changed) - PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P, - (Annotable*)M); - PMDebug::PrintAnalysisSetInfo(getDepth(), "Preserved", P, - AnUsage.getPreservedSet()); - - - // Erase all analyses not in the preserved set... - if (!AnUsage.preservesAll()) { - const std::vector &PreservedSet = AnUsage.getPreservedSet(); - for (std::map::iterator I = CurrentAnalyses.begin(), - E = CurrentAnalyses.end(); I != E; ) - if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) != - PreservedSet.end()) - ++I; // This analysis is preserved, leave it in the available set... - else { -#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER - I = CurrentAnalyses.erase(I); // Analysis not preserved! -#else - // GCC 2.95.3 STL doesn't have correct erase member! - CurrentAnalyses.erase(I); - I = CurrentAnalyses.begin(); -#endif - } - } - - // Add the current pass to the set of passes that have been run, and are - // thus available to users. - // - if (const PassInfo *PI = P->getPassInfo()) - CurrentAnalyses[PI] = P; - - // Free memory for any passes that we are the last use of... - std::vector &DeadPass = LastUserOf[P]; - for (std::vector::iterator I = DeadPass.begin(),E = DeadPass.end(); - I != E; ++I) { - PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I, - (Annotable*)M); - (*I)->releaseMemory(); - } - } - return MadeChanges; + return runPasses(M, LastUserOf); } // dumpPassStructure - Implement the -debug-passes=PassStructure option - virtual void dumpPassStructure(unsigned Offset = 0) { - std::cerr << std::string(Offset*2, ' ') << Traits::getPMName() + inline void dumpPassStructure(unsigned Offset = 0) { + // Print out the immutable passes... + + for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) + ImmutablePasses[i]->dumpPassStructure(0); + + std::cerr << std::string(Offset*2, ' ') << this->getPMName() << " Pass Manager\n"; for (typename std::vector::iterator I = Passes.begin(), E = Passes.end(); I != E; ++I) { @@ -253,38 +307,47 @@ public: } } - Pass *getAnalysisOrNullDown(AnalysisID ID) const { - std::map::const_iterator I = CurrentAnalyses.find(ID); - if (I == CurrentAnalyses.end()) { - if (Batcher) - return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID); - return 0; + Pass *getImmutablePassOrNull(const PassInfo *ID) const { + for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { + const PassInfo *IPID = ImmutablePasses[i]->getPassInfo(); + if (IPID == ID) + return ImmutablePasses[i]; + + // This pass is the current implementation of all of the interfaces it + // implements as well. + // + const std::vector &II = + IPID->getInterfacesImplemented(); + for (unsigned j = 0, e = II.size(); j != e; ++j) + if (II[j] == ID) return ImmutablePasses[i]; } - return I->second; + return 0; } - Pass *getAnalysisOrNullUp(AnalysisID ID) const { + Pass *getAnalysisOrNullDown(const PassInfo *ID) const { std::map::const_iterator I = CurrentAnalyses.find(ID); - if (I == CurrentAnalyses.end()) { - if (Parent) - return Parent->getAnalysisOrNullUp(ID); - return 0; - } - return I->second; - } - // {start/end}Pass - Called when a pass is started, it just propogates - // information up to the top level PassManagerT object to tell it that a pass - // has started or ended. This is used to gather timing information about - // passes. - // - void startPass(Pass *P) { - if (Parent) Parent->startPass(P); - else PassStarted(P); + if (I != CurrentAnalyses.end()) + return I->second; // Found it. + + if (Pass *P = getImmutablePassOrNull(ID)) + return P; + + if (Batcher) + return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID); + return 0; } - void endPass(Pass *P) { - if (Parent) Parent->endPass(P); - else PassEnded(P); + + Pass *getAnalysisOrNullUp(const PassInfo *ID) const { + std::map::const_iterator I = CurrentAnalyses.find(ID); + if (I != CurrentAnalyses.end()) + return I->second; // Found it. + + if (Parent) // Try scanning... + return Parent->getAnalysisOrNullUp(ID); + else if (!ImmutablePasses.empty()) + return getImmutablePassOrNull(ID); + return 0; } // markPassUsed - Inform higher level pass managers (and ourselves) @@ -292,19 +355,37 @@ public: // make sure that analyses are not free'd before we have to use // them... // - void markPassUsed(AnalysisID P, Pass *User) { - std::map::iterator I = CurrentAnalyses.find(P); + void markPassUsed(const PassInfo *P, Pass *User) { + std::map::const_iterator I = CurrentAnalyses.find(P); + if (I != CurrentAnalyses.end()) { LastUseOf[I->second] = User; // Local pass, extend the lifetime + + // Prolong live range of analyses that are needed after an analysis pass + // is destroyed, for querying by subsequent passes + AnalysisUsage AnUsage; + I->second->getAnalysisUsage(AnUsage); + const std::vector &IDs = AnUsage.getRequiredTransitiveSet(); + for (std::vector::const_iterator i = IDs.begin(), + e = IDs.end(); i != e; ++i) + markPassUsed(*i, User); + } else { // Pass not in current available set, must be a higher level pass - // available to us, propogate to parent pass manager... We tell the + // available to us, propagate to parent pass manager... We tell the // parent that we (the passmanager) are using the analysis so that it // frees the analysis AFTER this pass manager runs. // - assert(Parent != 0 && "Pass available but not found! " - "Did your analysis pass 'Provide' itself?"); - Parent->markPassUsed(P, this); + if (Parent) { + assert(dynamic_cast(this) && + "It wasn't the Pass type I thought it was."); + Parent->markPassUsed(P, dynamic_cast(this)); + } else { + assert(getAnalysisOrNullUp(P) && + dynamic_cast(getAnalysisOrNullUp(P)) && + "Pass available but not found! " + "Perhaps this is a module pass requiring a function pass?"); + } } } @@ -315,12 +396,13 @@ public: } virtual unsigned getNumContainedPasses() const { return Passes.size(); } + virtual const Pass *getContainedPass(unsigned N) const { assert(N < Passes.size() && "Pass number out of range!"); return Passes[N]; } - // add - Add a pass to the queue of passes to run. This passes ownership of + // add - Add a pass to the queue of passes to run. This gives ownership of // the Pass to the PassManager. When the PassManager is destroyed, the pass // will be destroyed as well, so there is no need to delete the pass. This // implies that all passes MUST be new'd. @@ -329,24 +411,33 @@ public: // Get information about what analyses the pass uses... AnalysisUsage AnUsage; P->getAnalysisUsage(AnUsage); - const std::vector &Required = AnUsage.getRequiredSet(); - - // Loop over all of the analyses used by this pass, - for (std::vector::const_iterator I = Required.begin(), - E = Required.end(); I != E; ++I) { - if (getAnalysisOrNullDown(*I) == 0) - add((PassClass*)(*I)->createPass()); - } - + + addRequiredPasses(AnUsage.getRequiredSet()); + // Tell the pass to add itself to this PassManager... the way it does so // depends on the class of the pass, and is critical to laying out passes in // an optimal order.. // - P->addToPassManager(this, AnUsage); + assert(dynamic_cast(this) && + "It wasn't the right passmanager type."); + P->addToPassManager(static_cast(this), AnUsage); } -private: + // add - H4x0r an ImmutablePass into a PassManager that might not be + // expecting one. + // + void add(ImmutablePass *P) { + // Get information about what analyses the pass uses... + AnalysisUsage AnUsage; + P->getAnalysisUsage(AnUsage); + + addRequiredPasses(AnUsage.getRequiredSet()); + + // Add the ImmutablePass to this PassManager. + addPass(P, AnUsage); + } +private: // addPass - These functions are used to implement the subclass specific // behaviors present in PassManager. Basically the add(Pass*) method ends up // reflecting its behavior into a Pass::addToPassManager call. Subclasses of @@ -361,14 +452,13 @@ private: const std::vector &RequiredSet = AnUsage.getRequiredSet(); // FIXME: If this pass being added isn't killed by any of the passes in the - // batcher class then we can reorder to pass to execute before the batcher + // batcher class then we can reorder the pass to execute before the batcher // does, which will potentially allow us to batch more passes! // - //const std::vector &ProvidedSet = AnUsage.getProvidedSet(); - if (Batcher /*&& ProvidedSet.empty()*/) + if (Batcher) closeBatcher(); // This pass cannot be batched! - - // Set the Resolver instance variable in the Pass so that it knows where to + + // Set the Resolver instance variable in the Pass so that it knows where to // find this object... // setAnalysisResolver(P, this); @@ -382,28 +472,10 @@ private: E = RequiredSet.end(); I != E; ++I) markPassUsed(*I, P); // Mark *I as used by P - // Erase all analyses not in the preserved set... - if (!AnUsage.preservesAll()) { - const std::vector &PreservedSet = AnUsage.getPreservedSet(); - for (std::map::iterator I = CurrentAnalyses.begin(), - E = CurrentAnalyses.end(); I != E; ) - if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) != - PreservedSet.end()) - ++I; // This analysis is preserved, leave it in the available set... - else { -#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER - I = CurrentAnalyses.erase(I); // Analysis not preserved! -#else - CurrentAnalyses.erase(I);// GCC 2.95.3 STL doesn't have correct erase! - I = CurrentAnalyses.begin(); -#endif - } - } - - // Add this pass to the currently available set... - if (const PassInfo *PI = P->getPassInfo()) - CurrentAnalyses[PI] = P; - + removeNonPreservedAnalyses(AnUsage); + + makeCurrentlyAvailable(P); + // For now assume that our results are never used... LastUseOf[P] = P; } @@ -413,8 +485,13 @@ private: // together a function at a time. // void addPass(SubPassClass *MP, AnalysisUsage &AnUsage) { - if (Batcher == 0) // If we don't have a batcher yet, make one now. - Batcher = new BatcherClass(this); + + if (Batcher == 0) { // If we don't have a batcher yet, make one now. + assert(dynamic_cast(this) && + "It wasn't the PassManager type I thought it was"); + Batcher = new BatcherClass((static_cast(this))); + } + // The Batcher will queue the passes up MP->addToPassManager(Batcher, AnUsage); } @@ -426,217 +503,408 @@ private: Batcher = 0; } } -}; + void addRequiredPasses(const std::vector &Required) { + for (std::vector::const_iterator I = Required.begin(), + E = Required.end(); I != E; ++I) { + if (getAnalysisOrNullDown(*I) == 0) { + Pass *AP = (*I)->createPass(); + if (ImmutablePass *IP = dynamic_cast (AP)) add(IP); + else if (PassClass *RP = dynamic_cast (AP)) add(RP); + else assert (0 && "Wrong kind of pass for this PassManager"); + } + } + } +public: + // When an ImmutablePass is added, it gets added to the top level pass + // manager. + void addPass(ImmutablePass *IP, AnalysisUsage &AU) { + if (Parent) { // Make sure this request goes to the top level passmanager... + Parent->addPass(IP, AU); + return; + } -//===----------------------------------------------------------------------===// -// PassManagerTraits Specialization -// -// This pass manager is used to group together all of the BasicBlockPass's -// into a single unit. -// -template<> struct PassManagerTraits : public BasicBlockPass { - // PassClass - The type of passes tracked by this PassManager - typedef BasicBlockPass PassClass; + // Set the Resolver instance variable in the Pass so that it knows where to + // find this object... + // + setAnalysisResolver(IP, this); + ImmutablePasses.push_back(IP); - // SubPassClass - The types of classes that should be collated together - // This is impossible to match, so BasicBlock instantiations of PassManagerT - // do not collate. - // - typedef PassManagerT SubPassClass; + // All Required analyses should be available to the pass as it initializes! + // Here we fill in the AnalysisImpls member of the pass so that it can + // successfully use the getAnalysis() method to retrieve the implementations + // it needs. + // + IP->AnalysisImpls.clear(); + IP->AnalysisImpls.reserve(AU.getRequiredSet().size()); + for (std::vector::const_iterator + I = AU.getRequiredSet().begin(), + E = AU.getRequiredSet().end(); I != E; ++I) { + Pass *Impl = getAnalysisOrNullUp(*I); + if (Impl == 0) { + std::cerr << "Analysis '" << (*I)->getPassName() + << "' used but not available!"; + assert(0 && "Analysis used but not available!"); + } else if (PassDebugging == Details) { + if ((*I)->getPassName() != std::string(Impl->getPassName())) + std::cerr << " Interface '" << (*I)->getPassName() + << "' implemented by '" << Impl->getPassName() << "'\n"; + } + IP->AnalysisImpls.push_back(std::make_pair(*I, Impl)); + } - // BatcherClass - The type to use for collation of subtypes... This class is - // never instantiated for the PassManager, but it must be an - // instance of PassClass to typecheck. + // Initialize the immutable pass... + IP->initializePass(); + } +private: + + // Add any immutable passes to the CurrentAnalyses set... + inline void addImmutablePasses() { + for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { + ImmutablePass *IPass = ImmutablePasses[i]; + if (const PassInfo *PI = IPass->getPassInfo()) { + CurrentAnalyses[PI] = IPass; + + const std::vector &II = PI->getInterfacesImplemented(); + for (unsigned i = 0, e = II.size(); i != e; ++i) + CurrentAnalyses[II[i]] = IPass; + } + } + } + + // Run all of the passes + inline bool runPasses(UnitType *M, + std::map > &LastUserOf) { + bool MadeChanges = false; + + for (unsigned i = 0, e = Passes.size(); i < e; ++i) { + PassClass *P = Passes[i]; + + PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, M); + + // Get information about what analyses the pass uses... + AnalysisUsage AnUsage; + P->getAnalysisUsage(AnUsage); + PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P, + AnUsage.getRequiredSet()); + + initialiseAnalysisImpl(P, AnUsage); + + // Run the sub pass! + if (TheTimeInfo) TheTimeInfo->passStarted(P); + bool Changed = runPass(P, M); + if (TheTimeInfo) TheTimeInfo->passEnded(P); + MadeChanges |= Changed; + + // Check for memory leaks by the pass... + LeakDetector::checkForGarbage(std::string("after running pass '") + + P->getPassName() + "'"); + + if (Changed) + PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P, M); + PMDebug::PrintAnalysisSetInfo(getDepth(), "Preserved", P, + AnUsage.getPreservedSet()); + + // Erase all analyses not in the preserved set + removeNonPreservedAnalyses(AnUsage); + + makeCurrentlyAvailable(P); + + // free memory and remove dead passes from the CurrentAnalyses list... + removeDeadPasses(P, M, LastUserOf); + } + + return MadeChanges; + } + + // All Required analyses should be available to the pass as it runs! Here + // we fill in the AnalysisImpls member of the pass so that it can + // successfully use the getAnalysis() method to retrieve the + // implementations it needs. // - typedef PassClass BatcherClass; + inline void initialiseAnalysisImpl(PassClass *P, AnalysisUsage &AnUsage) { + P->AnalysisImpls.clear(); + P->AnalysisImpls.reserve(AnUsage.getRequiredSet().size()); + + for (std::vector::const_iterator + I = AnUsage.getRequiredSet().begin(), + E = AnUsage.getRequiredSet().end(); I != E; ++I) { + Pass *Impl = getAnalysisOrNullUp(*I); + if (Impl == 0) { + std::cerr << "Analysis '" << (*I)->getPassName() + << "' used but not available!"; + assert(0 && "Analysis used but not available!"); + } else if (PassDebugging == Details) { + if ((*I)->getPassName() != std::string(Impl->getPassName())) + std::cerr << " Interface '" << (*I)->getPassName() + << "' implemented by '" << Impl->getPassName() << "'\n"; + } + + P->AnalysisImpls.push_back(std::make_pair(*I, Impl)); + } + } + + inline void removeNonPreservedAnalyses(AnalysisUsage &AnUsage) { + if (!AnUsage.getPreservesAll()) { + const std::vector &PreservedSet = AnUsage.getPreservedSet(); + for (std::map::iterator I = CurrentAnalyses.begin(), + E = CurrentAnalyses.end(); I != E; ) + if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) != + PreservedSet.end()) + ++I; // This analysis is preserved, leave it in the available set... + else { + if (!dynamic_cast(I->second)) { + std::map::iterator J = I++; + CurrentAnalyses.erase(J); // Analysis not preserved! + } else { + ++I; + } + } + } + } + + inline void removeDeadPasses(Pass* P, UnitType *M, + std::map > &LastUserOf) { + std::vector &DeadPass = LastUserOf[P]; + for (std::vector::iterator I = DeadPass.begin(),E = DeadPass.end(); + I != E; ++I) { + PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I, M); + (*I)->releaseMemory(); + } + + for (std::map::iterator I = CurrentAnalyses.begin(); + I != CurrentAnalyses.end(); ) { + std::vector::iterator DPI = std::find(DeadPass.begin(), + DeadPass.end(), I->second); + if (DPI != DeadPass.end()) { // This pass is dead now... remove it + std::map::iterator IDead = I++; + CurrentAnalyses.erase(IDead); + } else { + ++I; // Move on to the next element... + } + } + } + + inline void makeCurrentlyAvailable(Pass* P) { + if (const PassInfo *PI = P->getPassInfo()) { + CurrentAnalyses[PI] = P; - // ParentClass - The type of the parent PassManager... - typedef PassManagerT ParentClass; + // This pass is the current implementation of all of the interfaces it + // implements as well. + // + const std::vector &II = PI->getInterfacesImplemented(); + for (unsigned i = 0, e = II.size(); i != e; ++i) + CurrentAnalyses[II[i]] = P; + } + } +}; - // PMType - The type of the passmanager that subclasses this class - typedef PassManagerT PMType; + +//===----------------------------------------------------------------------===// +// BasicBlockPassManager +// +// This pass manager is used to group together all of the BasicBlockPass's +// into a single unit. +// +class BasicBlockPassManager : public BasicBlockPass, + public BBTraits, + public PassManagerT { +public: + BasicBlockPassManager(BBTraits::ParentClass* PC) : + PassManagerT(PC) { + } + + BasicBlockPassManager(BasicBlockPassManager* BBPM) : + PassManagerT(BBPM->Parent) { + } + // runPass - Specify how the pass should be run on the UnitType - static bool runPass(PassClass *P, BasicBlock *M) { - // todo, init and finalize + virtual bool runPass(BBTraits::PassClass *P, BasicBlock *M) { + // TODO: init and finalize return P->runOnBasicBlock(*M); } - - // Dummy implementation of PassStarted/PassEnded - static void PassStarted(Pass *P) {} - static void PassEnded(Pass *P) {} - + + virtual ~BasicBlockPassManager() {} + + virtual void dumpPassStructure(unsigned Offset = 0) { + PassManagerT::dumpPassStructure(Offset); + } + // getPMName() - Return the name of the unit the PassManager operates on for // debugging. - const char *getPMName() const { return "BasicBlock"; } + virtual const char *getPMName() const { return "BasicBlock"; } + virtual const char *getPassName() const { return "BasicBlock Pass Manager"; } - - // Implement the BasicBlockPass interface... + virtual bool doInitialization(Module &M); + virtual bool doInitialization(Function &F); virtual bool runOnBasicBlock(BasicBlock &BB); + virtual bool doFinalization(Function &F); virtual bool doFinalization(Module &M); - + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } }; - - //===----------------------------------------------------------------------===// -// PassManagerTraits Specialization +// FunctionPassManager // // This pass manager is used to group together all of the FunctionPass's // into a single unit. // -template<> struct PassManagerTraits : public FunctionPass { - // PassClass - The type of passes tracked by this PassManager - typedef FunctionPass PassClass; - - // SubPassClass - The types of classes that should be collated together - typedef BasicBlockPass SubPassClass; - - // BatcherClass - The type to use for collation of subtypes... - typedef PassManagerT BatcherClass; - - // ParentClass - The type of the parent PassManager... - typedef PassManagerT ParentClass; - - // PMType - The type of the passmanager that subclasses this class - typedef PassManagerT PMType; - - // runPass - Specify how the pass should be run on the UnitType - static bool runPass(PassClass *P, Function *F) { - return P->runOnFunction(*F); +class FunctionPassManagerT : public FunctionPass, + public FTraits, + public PassManagerT { +public: + FunctionPassManagerT() : PassManagerT(0) {} + + // Parent constructor + FunctionPassManagerT(FTraits::ParentClass* PC) : PassManagerT(PC) {} + + FunctionPassManagerT(FunctionPassManagerT* FPM) : + PassManagerT(FPM->Parent) { } - - // Dummy implementation of PassStarted/PassEnded - static void PassStarted(Pass *P) {} - static void PassEnded(Pass *P) {} - + + virtual ~FunctionPassManagerT() {} + + virtual void dumpPassStructure(unsigned Offset = 0) { + PassManagerT::dumpPassStructure(Offset); + } + // getPMName() - Return the name of the unit the PassManager operates on for // debugging. - const char *getPMName() const { return "Function"; } + virtual const char *getPMName() const { return "Function"; } + virtual const char *getPassName() const { return "Function Pass Manager"; } - - // Implement the FunctionPass interface... - virtual bool doInitialization(Module &M); + virtual bool runOnFunction(Function &F); + + virtual bool doInitialization(Module &M); + virtual bool doFinalization(Module &M); - + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } + + // runPass - Specify how the pass should be run on the UnitType + virtual bool runPass(FTraits::PassClass *P, Function *F) { + return P->runOnFunction(*F); + } }; - //===----------------------------------------------------------------------===// -// PassManagerTraits Specialization +// ModulePassManager // // This is the top level PassManager implementation that holds generic passes. // -template<> struct PassManagerTraits : public Pass { - // PassClass - The type of passes tracked by this PassManager - typedef Pass PassClass; - - // SubPassClass - The types of classes that should be collated together - typedef FunctionPass SubPassClass; - - // BatcherClass - The type to use for collation of subtypes... - typedef PassManagerT BatcherClass; - - // ParentClass - The type of the parent PassManager... - typedef AnalysisResolver ParentClass; - - // runPass - Specify how the pass should be run on the UnitType - static bool runPass(PassClass *P, Module *M) { return P->run(*M); } - +class ModulePassManager : public ModulePass, + public MTraits, + public PassManagerT { +public: + ModulePassManager() : PassManagerT(0) {} + + // Batcher Constructor + ModulePassManager(MTraits::ParentClass* PC) : PassManagerT(PC) {} + + ModulePassManager(ModulePassManager* MPM) : + PassManagerT((MPM->Parent)) { + } + + virtual ~ModulePassManager() {} + + virtual void dumpPassStructure(unsigned Offset = 0) { + PassManagerT::dumpPassStructure(Offset); + } + // getPMName() - Return the name of the unit the PassManager operates on for // debugging. - const char *getPMName() const { return "Module"; } virtual const char *getPassName() const { return "Module Pass Manager"; } - - // TimingInformation - This data member maintains timing information for each - // of the passes that is executed. - // - TimingInfo *TimeInfo; - - // PassStarted/Ended - This callback is notified any time a pass is started - // or stops. This is used to collect timing information about the different - // passes being executed. - // - void PassStarted(Pass *P) { - if (TimeInfo) TimeInfo->passStarted(P); - } - void PassEnded(Pass *P) { - if (TimeInfo) TimeInfo->passEnded(P); - } - - // run - Implement the PassManager interface... - bool run(Module &M) { - TimeInfo = TimingInfo::create(); - bool Result = ((PassManagerT*)this)->runOnUnit(&M); - if (TimeInfo) { - delete TimeInfo; - TimeInfo = 0; - } - return Result; + + // getPMName() - Return the name of the unit the PassManager operates on for + // debugging. + virtual const char *getPMName() const { return "Module"; } + + // runOnModule - Implement the PassManager interface. + virtual bool runOnModule(Module &M); + + // runPass - Specify how the pass should be run on the UnitType + virtual bool runPass(MTraits::PassClass *P, Module *M) { + return P->runOnModule(*M); } - - // PassManagerTraits constructor - Create a timing info object if the user - // specified timing info should be collected on the command line. - // - PassManagerTraits() : TimeInfo(0) {} }; - - //===----------------------------------------------------------------------===// -// PassManagerTraits Method Implementations +// PassManager Method Implementations // -// PassManagerTraits Implementations +// BasicBlockPassManager Implementations // -inline bool PassManagerTraits::doInitialization(Module &M) { + +inline bool BasicBlockPassManager::runOnBasicBlock(BasicBlock &BB) { + return ((BBTraits::PMType*)this)->runOnUnit(&BB); +} + +inline bool BasicBlockPassManager::doInitialization(Module &M) { bool Changed = false; - for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i) - ((PMType*)this)->Passes[i]->doInitialization(M); + for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((BBTraits::PMType*)this)->Passes[i]->doInitialization(M); return Changed; } -inline bool PassManagerTraits::runOnBasicBlock(BasicBlock &BB) { - return ((PMType*)this)->runOnUnit(&BB); +inline bool BasicBlockPassManager::doInitialization(Function &F) { + bool Changed = false; + for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((BBTraits::PMType*)this)->Passes[i]->doInitialization(F); + return Changed; } -inline bool PassManagerTraits::doFinalization(Module &M) { +inline bool BasicBlockPassManager::doFinalization(Function &F) { bool Changed = false; - for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i) - ((PMType*)this)->Passes[i]->doFinalization(M); + for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((BBTraits::PMType*)this)->Passes[i]->doFinalization(F); return Changed; } - -// PassManagerTraits Implementations -// -inline bool PassManagerTraits::doInitialization(Module &M) { +inline bool BasicBlockPassManager::doFinalization(Module &M) { bool Changed = false; - for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i) - ((PMType*)this)->Passes[i]->doInitialization(M); + for (unsigned i=0, e = ((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((BBTraits::PMType*)this)->Passes[i]->doFinalization(M); return Changed; } -inline bool PassManagerTraits::runOnFunction(Function &F) { - return ((PMType*)this)->runOnUnit(&F); +// FunctionPassManagerT Implementations +// + +inline bool FunctionPassManagerT::runOnFunction(Function &F) { + return ((FTraits::PMType*)this)->runOnUnit(&F); +} + +inline bool FunctionPassManagerT::doInitialization(Module &M) { + bool Changed = false; + for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((FTraits::PMType*)this)->Passes[i]->doInitialization(M); + return Changed; } -inline bool PassManagerTraits::doFinalization(Module &M) { +inline bool FunctionPassManagerT::doFinalization(Module &M) { bool Changed = false; - for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i) - ((PMType*)this)->Passes[i]->doFinalization(M); + for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i) + ((FTraits::PMType*)this)->Passes[i]->doFinalization(M); return Changed; } +// ModulePassManager Implementations +// + +bool ModulePassManager::runOnModule(Module &M) { + return ((PassManagerT*)this)->runOnUnit(&M); +} + +} // End llvm namespace + #endif