X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FPass.cpp;h=b593d475ca0efe3119cb0edf5b5779d1f57a4de4;hb=e934fefd6b6c83816e81bc86389cd593fb930773;hp=06e77e7fe16ba0d305eeccd0c0ac02b8b95e3384;hpb=44050fb25a37a72ba74da9b0c8b41973325a7995;p=oota-llvm.git diff --git a/lib/VMCore/Pass.cpp b/lib/VMCore/Pass.cpp index 06e77e7fe16..b593d475ca0 100644 --- a/lib/VMCore/Pass.cpp +++ b/lib/VMCore/Pass.cpp @@ -1,4 +1,11 @@ -//===- Pass.cpp - LLVM Pass Infrastructure Impementation ------------------===// +//===- Pass.cpp - LLVM Pass Infrastructure Implementation -----------------===// +// +// 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 implements the LLVM Pass infrastructure. It is primarily // responsible with ensuring that passes are executed and batched together @@ -7,215 +14,32 @@ //===----------------------------------------------------------------------===// #include "llvm/PassManager.h" -#include "PassManagerT.h" // PassManagerT implementation #include "llvm/Module.h" -#include "Support/STLExtras.h" -#include "Support/CommandLine.h" -#include "Support/TypeInfo.h" -#include -#include -#include -#include - -//===----------------------------------------------------------------------===// -// AnalysisID Class Implementation -// - -static std::vector CFGOnlyAnalyses; -#if 0 -// Source of unique analysis ID #'s. -unsigned AnalysisID::NextID = 0; - -AnalysisID::AnalysisID(const AnalysisID &AID, bool DependsOnlyOnCFG) { - ID = AID.ID; // Implement the copy ctor part... - Constructor = AID.Constructor; - - // If this analysis only depends on the CFG of the function, add it to the CFG - // only list... - if (DependsOnlyOnCFG) - CFGOnlyAnalyses.push_back(AID); -} -#endif +#include "llvm/ModuleProvider.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/TypeInfo.h" +#include +#include +using namespace llvm; //===----------------------------------------------------------------------===// -// AnalysisResolver Class Implementation -// - -void AnalysisResolver::setAnalysisResolver(Pass *P, AnalysisResolver *AR) { - assert(P->Resolver == 0 && "Pass already in a PassManager!"); - P->Resolver = AR; -} - -//===----------------------------------------------------------------------===// -// AnalysisUsage Class Implementation -// - -// 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 double getTime() { - struct timeval T; - gettimeofday(&T, 0); - return T.tv_sec + T.tv_usec/1000000.0; -} - -// 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] -= getTime(); } -void TimingInfo::passEnded(Pass *P) { TimingData[P] += getTime(); } - -// 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; - double TotalTime = 0; - 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)); - TotalTime += I->second; - } - - // 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: " << TotalTime - << " seconds\n\n % Time: Seconds:\tPass Name:\n"; - - // Loop through all of the timing data, printing it out... - for (unsigned i = 0, e = Data.size(); i != e; ++i) { - fprintf(stderr, " %6.2f%% %fs\t%s\n", Data[i].first*100 / TotalTime, - Data[i].first, Data[i].second->getPassName()); - } - std::cerr << " 100.00% " << TotalTime << "s\tTOTAL\n" - << std::string(79, '=') << "\n"; -} - - -//===----------------------------------------------------------------------===// -// 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. +// Pass Implementation // -// Different debug levels that can be enabled... -enum PassDebugLevel { - None, Structure, Executions, Details -}; - -static cl::opt -PassDebugging("debug-pass", cl::Hidden, - cl::desc("Print PassManager debugging information"), - cl::values( - clEnumVal(None , "disable debug output"), - // TODO: add option to print out pass names "PassOptions" - 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)); - -void PMDebug::PrintPassStructure(Pass *P) { - if (PassDebugging >= Structure) - P->dumpPassStructure(); -} +// Force out-of-line virtual method. +ModulePass::~ModulePass() { } -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 "; - - 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"; - } -} - -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) { - // FIXME: This can use the local pass map! - Pass *P = Set[i]->createPass(); // Good thing this is just debug code... - std::cerr << " " << P->getPassName(); - delete P; - } - std::cerr << "\n"; - } +bool Pass::mustPreserveAnalysisID(const PassInfo *AnalysisID) const { + return Resolver->getAnalysisToUpdate(AnalysisID, true) != 0; } // dumpPassStructure - Implement the -debug-passes=Structure option void Pass::dumpPassStructure(unsigned Offset) { - std::cerr << std::string(Offset*2, ' ') << getPassName() << "\n"; + cerr << std::string(Offset*2, ' ') << getPassName() << "\n"; } - -//===----------------------------------------------------------------------===// -// Pass Implementation -// - -void Pass::addToPassManager(PassManagerT *PM, AnalysisUsage &AU) { - PM->addPass(this, AU); -} - - -// getPassName - Use C++ RTTI to get a SOMEWHAT intelligable name for the pass. +// getPassName - Use C++ RTTI to get a SOMEWHAT intelligible name for the pass. // const char *Pass::getPassName() const { if (const PassInfo *PI = getPassInfo()) @@ -223,19 +47,25 @@ const char *Pass::getPassName() const { 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 +// print - Print out the internal state of the pass. This is called by Analyze +// to print out the contents of an analysis. Otherwise it is not necessary to // implement this method. // -void Pass::print(std::ostream &O) const { +void Pass::print(std::ostream &O,const Module*) const { O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n"; } -// dump - call print(std::cerr); +// dump - call print(cerr); void Pass::dump() const { - print(std::cerr, 0); + print(*cerr.stream(), 0); } +//===----------------------------------------------------------------------===// +// ImmutablePass Implementation +// +// Force out-of-line virtual method. +ImmutablePass::~ImmutablePass() { } + //===----------------------------------------------------------------------===// // FunctionPass Implementation // @@ -243,33 +73,24 @@ void Pass::dump() const { // 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 FunctionPass::runOnModule(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! + if (!I->isDeclaration()) // 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); -} + if (F.isDeclaration()) return false;// Passes are not run on external functions! -void FunctionPass::addToPassManager(PassManagerT *PM, - AnalysisUsage &AU) { - PM->addPass(this, AU); + bool Changed = doInitialization(*F.getParent()); + Changed |= runOnFunction(F); + return Changed | doFinalization(*F.getParent()); } //===----------------------------------------------------------------------===// @@ -280,85 +101,160 @@ void FunctionPass::addToPassManager(PassManagerT *PM, // function. // bool BasicBlockPass::runOnFunction(Function &F) { - bool Changed = false; + bool Changed = doInitialization(F); for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) Changed |= runOnBasicBlock(*I); - return Changed; + return Changed | doFinalization(F); } // To run directly on the basic block, we initialize, runOnBasicBlock, then // finalize. // -bool BasicBlockPass::run(BasicBlock &BB) { - Module &M = *BB.getParent()->getParent(); - return doInitialization(M) | runOnBasicBlock(BB) | doFinalization(M); -} - -void BasicBlockPass::addToPassManager(PassManagerT *PM, - AnalysisUsage &AU) { - PM->addPass(this, AU); -} - -void BasicBlockPass::addToPassManager(PassManagerT *PM, - AnalysisUsage &AU) { - PM->addPass(this, AU); +bool BasicBlockPass::runPass(BasicBlock &BB) { + Function &F = *BB.getParent(); + Module &M = *F.getParent(); + bool Changed = doInitialization(M); + Changed |= doInitialization(F); + Changed |= runOnBasicBlock(BB); + Changed |= doFinalization(F); + Changed |= doFinalization(M); + return Changed; } - //===----------------------------------------------------------------------===// // Pass Registration mechanism // -static std::map *PassInfoMap = 0; +namespace { +class PassRegistrar { + /// PassInfoMap - Keep track of the passinfo object for each registered llvm + /// pass. + std::map PassInfoMap; + + /// AnalysisGroupInfo - Keep track of information for each analysis group. + struct AnalysisGroupInfo { + const PassInfo *DefaultImpl; + std::set Implementations; + AnalysisGroupInfo() : DefaultImpl(0) {} + }; + + /// AnalysisGroupInfoMap - Information for each analysis group. + std::map AnalysisGroupInfoMap; + +public: + + const PassInfo *GetPassInfo(const std::type_info &TI) const { + std::map::const_iterator I = PassInfoMap.find(TI); + return I != PassInfoMap.end() ? I->second : 0; + } + + void RegisterPass(PassInfo &PI) { + bool Inserted = + PassInfoMap.insert(std::make_pair(TypeInfo(PI.getTypeInfo()),&PI)).second; + assert(Inserted && "Pass registered multiple times!"); + } + + void UnregisterPass(PassInfo &PI) { + 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); + } + + void EnumerateWith(PassRegistrationListener *L) { + for (std::map::const_iterator I = PassInfoMap.begin(), + E = PassInfoMap.end(); I != E; ++I) + L->passEnumerate(I->second); + } + + + /// Analysis Group Mechanisms. + void RegisterAnalysisGroup(PassInfo *InterfaceInfo, + const PassInfo *ImplementationInfo, + bool isDefault) { + 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()); + } + } +}; +} + +static ManagedStatic PassRegistrarObj; 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; - if (PassInfoMap == 0) return 0; - std::map::iterator I = PassInfoMap->find(typeid(*this)); - return (I != PassInfoMap->end()) ? I->second : 0; + return lookupPassInfo(typeid(*this)); } -void RegisterPassBase::registerPass(PassInfo *PI) { - if (PassInfoMap == 0) - PassInfoMap = new std::map(); +const PassInfo *Pass::lookupPassInfo(const std::type_info &TI) { + return PassRegistrarObj->GetPassInfo(TI); +} - assert(PassInfoMap->find(PI->getTypeInfo()) == PassInfoMap->end() && - "Pass already registered!"); - PIObj = PI; - PassInfoMap->insert(std::make_pair(TypeInfo(PI->getTypeInfo()), PI)); +void RegisterPassBase::registerPass() { + PassRegistrarObj->RegisterPass(PIObj); - // Notify any listeners... + // Notify any listeners. if (Listeners) for (std::vector::iterator I = Listeners->begin(), E = Listeners->end(); I != E; ++I) - (*I)->passRegistered(PI); + (*I)->passRegistered(&PIObj); } -RegisterPassBase::~RegisterPassBase() { - assert(PassInfoMap && "Pass registered but not in map!"); - std::map::iterator I = - PassInfoMap->find(PIObj->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 RegisterPassBase::unregisterPass() { + PassRegistrarObj->UnregisterPass(PIObj); +} - // Notify any listeners... - if (Listeners) - for (std::vector::iterator - I = Listeners->begin(), E = Listeners->end(); I != E; ++I) - (*I)->passUnregistered(PIObj); +//===----------------------------------------------------------------------===// +// Analysis Group Implementation Code +//===----------------------------------------------------------------------===// - // Delete the PassInfo object itself... - delete PIObj; +// RegisterAGBase implementation +// +RegisterAGBase::RegisterAGBase(const std::type_info &Interface, + const std::type_info *Pass, bool isDefault) + : RegisterPassBase(Interface), + ImplementationInfo(0), isDefaultImplementation(isDefault) { + + InterfaceInfo = const_cast(Pass::lookupPassInfo(Interface)); + if (InterfaceInfo == 0) { + // First reference to Interface, register it now. + registerPass(); + InterfaceInfo = &PIObj; + } + assert(PIObj.isAnalysisGroup() && + "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!"); + + // Make sure we keep track of the fact that the implementation implements + // the interface. + PassInfo *IIPI = const_cast(ImplementationInfo); + IIPI->addInterfaceImplemented(InterfaceInfo); + + PassRegistrarObj->RegisterAnalysisGroup(InterfaceInfo, IIPI, isDefault); + } } +void RegisterAGBase::setGroupName(const char *Name) { + assert(InterfaceInfo->getPassName()[0] == 0 && "Interface Name already set!"); + InterfaceInfo->setPassName(Name); +} //===----------------------------------------------------------------------===// @@ -390,8 +286,38 @@ PassRegistrationListener::~PassRegistrationListener() { // 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); + PassRegistrarObj->EnumerateWith(this); +} + +//===----------------------------------------------------------------------===// +// AnalysisUsage Class Implementation +// + +namespace { + struct GetCFGOnlyPasses : public PassRegistrationListener { + std::vector &CFGOnlyList; + GetCFGOnlyPasses(std::vector &L) : CFGOnlyList(L) {} + + void passEnumerate(const PassInfo *P) { + if (P->isCFGOnlyPass()) + CFGOnlyList.push_back(P); + } + }; } + +// setPreservesCFG - 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::setPreservesCFG() { + // Since this transformation doesn't modify the CFG, it preserves all analyses + // that only depend on the CFG (like dominators, loop info, etc...) + GetCFGOnlyPasses(Preserved).enumeratePasses(); +} + +