X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FPass.cpp;h=85c4dec5fe722876aba27eb79f1a533512f219e2;hb=4d7a75a9e31a1b45e68b9cd3f50f18bd90dd0850;hp=13df79390102756576830973a094ef55946f381e;hpb=e21206268d267b8eaa416e21ac8e12353cf6bda9;p=oota-llvm.git diff --git a/lib/VMCore/Pass.cpp b/lib/VMCore/Pass.cpp index 13df7939010..85c4dec5fe7 100644 --- a/lib/VMCore/Pass.cpp +++ b/lib/VMCore/Pass.cpp @@ -6,175 +6,558 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Pass.h" +#include "llvm/PassManager.h" +#include "PassManagerT.h" // PassManagerT implementation +#include "llvm/Module.h" #include "Support/STLExtras.h" -#include +#include "Support/TypeInfo.h" +#include +#include +#include +#include +#include -// Pass debugging information. Often it is useful to find out what pass is -// running when a crash occurs in a utility. When this library is compiled with -// debugging on, a command line option (--debug-pass) is enabled that causes the -// pass name to be printed before it executes. +// IncludeFile - Stub function used to help linking out. +IncludeFile::IncludeFile(void*) {} + +//===----------------------------------------------------------------------===// +// AnalysisID Class Implementation // -#ifdef NDEBUG -// If not debugging, remove the option -inline static void PrintPassInformation(const char *, Pass *, Value *) { } -#else -#include "Support/CommandLine.h" -#include -#include +static std::vector CFGOnlyAnalyses; + +void RegisterPassBase::setPreservesCFG() { + CFGOnlyAnalyses.push_back(PIObj); +} + +//===----------------------------------------------------------------------===// +// AnalysisResolver Class Implementation +// + +void AnalysisResolver::setAnalysisResolver(Pass *P, AnalysisResolver *AR) { + assert(P->Resolver == 0 && "Pass already in a PassManager!"); + P->Resolver = AR; +} -// The option is hidden from --help by default -static cl::Flag PassDebugEnabled("debug-pass", - "Print pass names as they are executed by the PassManager", cl::Hidden); +//===----------------------------------------------------------------------===// +// AnalysisUsage Class Implementation +// -static void PrintPassInformation(const char *Action, Pass *P, Value *V) { - if (PassDebugEnabled) - std::cerr << Action << " Pass '" << typeid(*P).name() << "' on " - << typeid(*V).name() << " '" << V->getName() << "'...\n"; +// preservesCFG - This function should be called to by the pass, iff they do +// not: +// +// 1. Add or remove basic blocks from the function +// 2. Modify terminator instructions in any way. +// +// This function annotates the AnalysisUsage info object to say that analyses +// that only depend on the CFG are preserved by this pass. +// +void AnalysisUsage::preservesCFG() { + // Since this transformation doesn't modify the CFG, it preserves all analyses + // that only depend on the CFG (like dominators, loop info, etc...) + // + Preserved.insert(Preserved.end(), + CFGOnlyAnalyses.begin(), CFGOnlyAnalyses.end()); } + + +//===----------------------------------------------------------------------===// +// PassManager implementation - The PassManager class is a simple Pimpl class +// that wraps the PassManagerT template. +// +PassManager::PassManager() : PM(new PassManagerT()) {} +PassManager::~PassManager() { delete PM; } +void PassManager::add(Pass *P) { PM->add(P); } +bool PassManager::run(Module &M) { return PM->run(M); } + + +//===----------------------------------------------------------------------===// +// TimingInfo Class - This class is used to calculate information about the +// amount of time each pass takes to execute. This only happens with +// -time-passes is enabled on the command line. +// +static cl::opt +EnableTiming("time-passes", + cl::desc("Time each pass, printing elapsed time for each on exit")); + +static TimeRecord getTimeRecord() { + static unsigned long PageSize = 0; + + if (PageSize == 0) { +#ifdef _SC_PAGE_SIZE + PageSize = sysconf(_SC_PAGE_SIZE); +#else +#ifdef _SC_PAGESIZE + PageSize = sysconf(_SC_PAGESIZE); +#else + PageSize = getpagesize(); +#endif #endif + } + struct rusage RU; + struct timeval T; + gettimeofday(&T, 0); + if (getrusage(RUSAGE_SELF, &RU)) { + perror("getrusage call failed: -time-passes info incorrect!"); + } + TimeRecord Result; + Result.Elapsed = T.tv_sec + T.tv_usec/1000000.0; + Result.UserTime = RU.ru_utime.tv_sec + RU.ru_utime.tv_usec/1000000.0; + Result.SystemTime = RU.ru_stime.tv_sec + RU.ru_stime.tv_usec/1000000.0; + Result.MaxRSS = RU.ru_maxrss*PageSize; -PassManager::~PassManager() { - for_each(Passes.begin(), Passes.end(), deleter); + return Result; +} + +bool TimeRecord::operator<(const TimeRecord &TR) const { + // Primary sort key is User+System time + if (UserTime+SystemTime < TR.UserTime+TR.SystemTime) + return true; + if (UserTime+SystemTime > TR.UserTime+TR.SystemTime) + return false; + + // Secondary sort key is Wall Time + return Elapsed < TR.Elapsed; +} + +void TimeRecord::passStart(const TimeRecord &T) { + Elapsed -= T.Elapsed; + UserTime -= T.UserTime; + SystemTime -= T.SystemTime; + RSSTemp = T.MaxRSS; +} + +void TimeRecord::passEnd(const TimeRecord &T) { + Elapsed += T.Elapsed; + UserTime += T.UserTime; + SystemTime += T.SystemTime; + RSSTemp = T.MaxRSS - RSSTemp; + MaxRSS = std::max(MaxRSS, RSSTemp); +} + +static void printVal(double Val, double Total) { + if (Total < 1e-7) // Avoid dividing by zero... + fprintf(stderr, " ----- "); + else + fprintf(stderr, " %7.4f (%5.1f%%)", Val, Val*100/Total); +} + +void TimeRecord::print(const char *PassName, const TimeRecord &Total) const { + printVal(UserTime, Total.UserTime); + printVal(SystemTime, Total.SystemTime); + printVal(UserTime+SystemTime, Total.UserTime+Total.SystemTime); + printVal(Elapsed, Total.Elapsed); + + fprintf(stderr, " "); + + if (Total.MaxRSS) + std::cerr << MaxRSS << "\t"; + std::cerr << PassName << "\n"; } -class BasicBlockPassBatcher : public MethodPass { - typedef std::vector SubPassesType; - SubPassesType SubPasses; -public: - ~BasicBlockPassBatcher() { - for_each(SubPasses.begin(), SubPasses.end(), deleter); - } - void add(BasicBlockPass *P) { SubPasses.push_back(P); } +// Create method. If Timing is enabled, this creates and returns a new timing +// object, otherwise it returns null. +// +TimingInfo *TimingInfo::create() { + return EnableTiming ? new TimingInfo() : 0; +} + +void TimingInfo::passStarted(Pass *P) { + TimingData[P].passStart(getTimeRecord()); +} +void TimingInfo::passEnded(Pass *P) { + TimingData[P].passEnd(getTimeRecord()); +} +void TimeRecord::sum(const TimeRecord &TR) { + Elapsed += TR.Elapsed; + UserTime += TR.UserTime; + SystemTime += TR.SystemTime; + MaxRSS += TR.MaxRSS; +} - virtual bool doInitialization(Module *M) { - bool Changed = false; - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Initializing", *I, M); - Changed |= (*I)->doInitialization(M); +// TimingDtor - Print out information about timing information +TimingInfo::~TimingInfo() { + // Iterate over all of the data, converting it into the dual of the data map, + // so that the data is sorted by amount of time taken, instead of pointer. + // + std::vector > Data; + TimeRecord Total; + for (std::map::iterator I = TimingData.begin(), + E = TimingData.end(); I != E; ++I) + // Throw out results for "grouping" pass managers... + if (!dynamic_cast(I->first)) { + Data.push_back(std::make_pair(I->second, I->first)); + Total.sum(I->second); } - return Changed; + + // Sort the data by time as the primary key, in reverse order... + std::sort(Data.begin(), Data.end(), + std::greater >()); + + // Print out timing header... + std::cerr << std::string(79, '=') << "\n" + << " ... Pass execution timing report ...\n" + << std::string(79, '=') << "\n Total Execution Time: " + << (Total.UserTime+Total.SystemTime) << " seconds (" + << Total.Elapsed << " wall clock)\n\n ---User Time--- " + << "--System Time-- --User+System-- ---Wall Time---"; + + if (Total.MaxRSS) + std::cerr << " ---Mem---"; + std::cerr << " --- Pass Name ---\n"; + + // Loop through all of the timing data, printing it out... + for (unsigned i = 0, e = Data.size(); i != e; ++i) + Data[i].first.print(Data[i].second->getPassName(), Total); + + Total.print("TOTAL", Total); +} + + +void PMDebug::PrintArgumentInformation(const Pass *P) { + // Print out passes in pass manager... + if (const AnalysisResolver *PM = dynamic_cast(P)) { + for (unsigned i = 0, e = PM->getNumContainedPasses(); i != e; ++i) + PrintArgumentInformation(PM->getContainedPass(i)); + + } else { // Normal pass. Print argument information... + // Print out arguments for registered passes that are _optimizations_ + if (const PassInfo *PI = P->getPassInfo()) + if (PI->getPassType() & PassInfo::Optimization) + std::cerr << " -" << PI->getPassArgument(); } +} - virtual bool runOnMethod(Method *M) { - bool Changed = false; +void PMDebug::PrintPassInformation(unsigned Depth, const char *Action, + Pass *P, Annotable *V) { + if (PassDebugging >= Executions) { + std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '" + << P->getPassName(); + if (V) { + std::cerr << "' on "; - for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Executing", *I, *MI); - Changed |= (*I)->runOnBasicBlock(*MI); - } - return Changed; + if (dynamic_cast(V)) { + std::cerr << "Module\n"; return; + } else if (Function *F = dynamic_cast(V)) + std::cerr << "Function '" << F->getName(); + else if (BasicBlock *BB = dynamic_cast(V)) + std::cerr << "BasicBlock '" << BB->getName(); + else if (Value *Val = dynamic_cast(V)) + std::cerr << typeid(*Val).name() << " '" << Val->getName(); + } + std::cerr << "'...\n"; } +} - virtual bool doFinalization(Module *M) { - bool Changed = false; - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Finalizing", *I, M); - Changed |= (*I)->doFinalization(M); +void PMDebug::PrintAnalysisSetInfo(unsigned Depth, const char *Msg, + Pass *P, const std::vector &Set){ + if (PassDebugging >= Details && !Set.empty()) { + std::cerr << (void*)P << std::string(Depth*2+3, ' ') << Msg << " Analyses:"; + for (unsigned i = 0; i != Set.size(); ++i) { + if (i) std::cerr << ","; + std::cerr << " " << Set[i]->getPassName(); } - return Changed; + std::cerr << "\n"; } -}; +} + +//===----------------------------------------------------------------------===// +// Pass Implementation +// + +void Pass::addToPassManager(PassManagerT *PM, AnalysisUsage &AU) { + PM->addPass(this, AU); +} -class MethodPassBatcher : public Pass { - typedef std::vector SubPassesType; - SubPassesType SubPasses; - BasicBlockPassBatcher *BBPBatcher; -public: - inline MethodPassBatcher() : BBPBatcher(0) {} +// dumpPassStructure - Implement the -debug-passes=Structure option +void Pass::dumpPassStructure(unsigned Offset) { + std::cerr << std::string(Offset*2, ' ') << getPassName() << "\n"; +} + +// getPassName - Use C++ RTTI to get a SOMEWHAT intelligable name for the pass. +// +const char *Pass::getPassName() const { + if (const PassInfo *PI = getPassInfo()) + return PI->getPassName(); + return typeid(*this).name(); +} + +// print - Print out the internal state of the pass. This is called by Analyse +// to print out the contents of an analysis. Otherwise it is not neccesary to +// implement this method. +// +void Pass::print(std::ostream &O) const { + O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n"; +} + +// dump - call print(std::cerr); +void Pass::dump() const { + print(std::cerr, 0); +} - inline ~MethodPassBatcher() { - for_each(SubPasses.begin(), SubPasses.end(), deleter); +//===----------------------------------------------------------------------===// +// ImmutablePass Implementation +// +void ImmutablePass::addToPassManager(PassManagerT *PM, + AnalysisUsage &AU) { + PM->addPass(this, AU); +} + + +//===----------------------------------------------------------------------===// +// FunctionPass Implementation +// + +// run - On a module, we run this pass by initializing, runOnFunction'ing once +// for every function in the module, then by finalizing. +// +bool FunctionPass::run(Module &M) { + bool Changed = doInitialization(M); + + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + if (!I->isExternal()) // Passes are not run on external functions! + Changed |= runOnFunction(*I); + + return Changed | doFinalization(M); +} + +// run - On a function, we simply initialize, run the function, then finalize. +// +bool FunctionPass::run(Function &F) { + if (F.isExternal()) return false;// Passes are not run on external functions! + + return doInitialization(*F.getParent()) | runOnFunction(F) + | doFinalization(*F.getParent()); +} + +void FunctionPass::addToPassManager(PassManagerT *PM, + AnalysisUsage &AU) { + PM->addPass(this, AU); +} + +void FunctionPass::addToPassManager(PassManagerT *PM, + AnalysisUsage &AU) { + PM->addPass(this, AU); +} + +//===----------------------------------------------------------------------===// +// BasicBlockPass Implementation +// + +// To run this pass on a function, we simply call runOnBasicBlock once for each +// function. +// +bool BasicBlockPass::runOnFunction(Function &F) { + bool Changed = doInitialization(F); + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + Changed |= runOnBasicBlock(*I); + return Changed | doFinalization(F); +} + +// To run directly on the basic block, we initialize, runOnBasicBlock, then +// finalize. +// +bool BasicBlockPass::run(BasicBlock &BB) { + Function &F = *BB.getParent(); + Module &M = *F.getParent(); + return doInitialization(M) | doInitialization(F) | runOnBasicBlock(BB) | + doFinalization(F) | doFinalization(M); +} + +void BasicBlockPass::addToPassManager(PassManagerT *PM, + AnalysisUsage &AU) { + PM->addPass(this, AU); +} + +void BasicBlockPass::addToPassManager(PassManagerT *PM, + AnalysisUsage &AU) { + PM->addPass(this, AU); +} + + +//===----------------------------------------------------------------------===// +// Pass Registration mechanism +// +static std::map *PassInfoMap = 0; +static std::vector *Listeners = 0; + +// getPassInfo - Return the PassInfo data structure that corresponds to this +// pass... +const PassInfo *Pass::getPassInfo() const { + if (PassInfoCache) return PassInfoCache; + return lookupPassInfo(typeid(*this)); +} + +const PassInfo *Pass::lookupPassInfo(const std::type_info &TI) { + if (PassInfoMap == 0) return 0; + std::map::iterator I = PassInfoMap->find(TI); + return (I != PassInfoMap->end()) ? I->second : 0; +} + +void RegisterPassBase::registerPass(PassInfo *PI) { + if (PassInfoMap == 0) + PassInfoMap = new std::map(); + + assert(PassInfoMap->find(PI->getTypeInfo()) == PassInfoMap->end() && + "Pass already registered!"); + PIObj = PI; + PassInfoMap->insert(std::make_pair(TypeInfo(PI->getTypeInfo()), PI)); + + // Notify any listeners... + if (Listeners) + for (std::vector::iterator + I = Listeners->begin(), E = Listeners->end(); I != E; ++I) + (*I)->passRegistered(PI); +} + +void RegisterPassBase::unregisterPass(PassInfo *PI) { + assert(PassInfoMap && "Pass registered but not in map!"); + std::map::iterator I = + PassInfoMap->find(PI->getTypeInfo()); + assert(I != PassInfoMap->end() && "Pass registered but not in map!"); + + // Remove pass from the map... + PassInfoMap->erase(I); + if (PassInfoMap->empty()) { + delete PassInfoMap; + PassInfoMap = 0; } - void add(BasicBlockPass *BBP) { - if (BBPBatcher == 0) { - BBPBatcher = new BasicBlockPassBatcher(); - SubPasses.push_back(BBPBatcher); - } - BBPBatcher->add(BBP); + // Notify any listeners... + if (Listeners) + for (std::vector::iterator + I = Listeners->begin(), E = Listeners->end(); I != E; ++I) + (*I)->passUnregistered(PI); + + // Delete the PassInfo object itself... + delete PI; +} + +//===----------------------------------------------------------------------===// +// Analysis Group Implementation Code +//===----------------------------------------------------------------------===// + +struct AnalysisGroupInfo { + const PassInfo *DefaultImpl; + std::set Implementations; + AnalysisGroupInfo() : DefaultImpl(0) {} +}; + +static std::map *AnalysisGroupInfoMap = 0; + +// RegisterAGBase implementation +// +RegisterAGBase::RegisterAGBase(const std::type_info &Interface, + const std::type_info *Pass, bool isDefault) + : ImplementationInfo(0), isDefaultImplementation(isDefault) { + + InterfaceInfo = const_cast(Pass::lookupPassInfo(Interface)); + if (InterfaceInfo == 0) { // First reference to Interface, add it now. + InterfaceInfo = // Create the new PassInfo for the interface... + new PassInfo("", "", Interface, PassInfo::AnalysisGroup, 0, 0); + registerPass(InterfaceInfo); + PIObj = 0; } + assert(InterfaceInfo->getPassType() == PassInfo::AnalysisGroup && + "Trying to join an analysis group that is a normal pass!"); + + if (Pass) { + ImplementationInfo = Pass::lookupPassInfo(*Pass); + assert(ImplementationInfo && + "Must register pass before adding to AnalysisGroup!"); - void add(MethodPass *P) { - if (BasicBlockPass *BBP = dynamic_cast(P)) { - add(BBP); - } else { - BBPBatcher = 0; // Ensure that passes don't get accidentally reordered - SubPasses.push_back(P); + // Make sure we keep track of the fact that the implementation implements + // the interface. + PassInfo *IIPI = const_cast(ImplementationInfo); + IIPI->addInterfaceImplemented(InterfaceInfo); + + // Lazily allocate to avoid nasty initialization order dependencies + if (AnalysisGroupInfoMap == 0) + AnalysisGroupInfoMap = new std::map(); + + AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo]; + assert(AGI.Implementations.count(ImplementationInfo) == 0 && + "Cannot add a pass to the same analysis group more than once!"); + AGI.Implementations.insert(ImplementationInfo); + if (isDefault) { + assert(AGI.DefaultImpl == 0 && InterfaceInfo->getNormalCtor() == 0 && + "Default implementation for analysis group already specified!"); + assert(ImplementationInfo->getNormalCtor() && + "Cannot specify pass as default if it does not have a default ctor"); + AGI.DefaultImpl = ImplementationInfo; + InterfaceInfo->setNormalCtor(ImplementationInfo->getNormalCtor()); } } +} - virtual bool run(Module *M) { - bool Changed = false; - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Initializing", *I, M); - Changed |= (*I)->doInitialization(M); - } +void RegisterAGBase::setGroupName(const char *Name) { + assert(InterfaceInfo->getPassName()[0] == 0 && "Interface Name already set!"); + InterfaceInfo->setPassName(Name); +} - for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Executing", *I, M); - Changed |= (*I)->runOnMethod(*MI); +RegisterAGBase::~RegisterAGBase() { + if (ImplementationInfo) { + assert(AnalysisGroupInfoMap && "Inserted into map, but map doesn't exist?"); + AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo]; + + assert(AGI.Implementations.count(ImplementationInfo) && + "Pass not a member of analysis group?"); + + if (AGI.DefaultImpl == ImplementationInfo) + AGI.DefaultImpl = 0; + + AGI.Implementations.erase(ImplementationInfo); + + // Last member of this analysis group? Unregister PassInfo, delete map entry + if (AGI.Implementations.empty()) { + assert(AGI.DefaultImpl == 0 && + "Default implementation didn't unregister?"); + AnalysisGroupInfoMap->erase(InterfaceInfo); + if (AnalysisGroupInfoMap->empty()) { // Delete map if empty + delete AnalysisGroupInfoMap; + AnalysisGroupInfoMap = 0; } - for (SubPassesType::iterator I = SubPasses.begin(), E = SubPasses.end(); - I != E; ++I) { - PrintPassInformation("Finalizing", *I, M); - Changed |= (*I)->doFinalization(M); + unregisterPass(InterfaceInfo); } - return Changed; } -}; - -// add(BasicBlockPass*) - If we know it's a BasicBlockPass, we don't have to do -// any checking... -// -void PassManager::add(BasicBlockPass *BBP) { - if (Batcher == 0) // If we don't have a batcher yet, make one now. - add((MethodPass*)BBP); - else - Batcher->add(BBP); } -// add(MethodPass*) - MethodPass's must be batched together... make sure this -// happens now. +//===----------------------------------------------------------------------===// +// PassRegistrationListener implementation // -void PassManager::add(MethodPass *MP) { - if (Batcher == 0) { // If we don't have a batcher yet, make one now. - Batcher = new MethodPassBatcher(); - Passes.push_back(Batcher); - } - Batcher->add(MP); // The Batcher will queue them passes up -} -// add - Add a pass to the PassManager, batching it up as appropriate... -void PassManager::add(Pass *P) { - if (MethodPass *MP = dynamic_cast(P)) { - add(MP); // Use the methodpass specific code to do the addition - } else { - Batcher = 0; // Ensure that passes don't get accidentally reordered - Passes.push_back(P); - } +// PassRegistrationListener ctor - Add the current object to the list of +// PassRegistrationListeners... +PassRegistrationListener::PassRegistrationListener() { + if (!Listeners) Listeners = new std::vector(); + Listeners->push_back(this); } +// dtor - Remove object from list of listeners... +PassRegistrationListener::~PassRegistrationListener() { + std::vector::iterator I = + std::find(Listeners->begin(), Listeners->end(), this); + assert(Listeners && I != Listeners->end() && + "PassRegistrationListener not registered!"); + Listeners->erase(I); -bool PassManager::run(Module *M) { - bool MadeChanges = false; - // Run all of the pass initializers - for (unsigned i = 0, e = Passes.size(); i < e; ++i) { - PrintPassInformation("Executing", Passes[i], M); - MadeChanges |= Passes[i]->run(M); + if (Listeners->empty()) { + delete Listeners; + Listeners = 0; } - return MadeChanges; +} + +// enumeratePasses - Iterate over the registered passes, calling the +// passEnumerate callback on each PassInfo object. +// +void PassRegistrationListener::enumeratePasses() { + if (PassInfoMap) + for (std::map::iterator I = PassInfoMap->begin(), + E = PassInfoMap->end(); I != E; ++I) + passEnumerate(I->second); }