LLVM API Documentation

Pass.cpp

Go to the documentation of this file.
00001 //===- Pass.cpp - LLVM Pass Infrastructure Implementation -----------------===//
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 implements the LLVM Pass infrastructure.  It is primarily
00011 // responsible with ensuring that passes are executed and batched together
00012 // optimally.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/PassManager.h"
00017 #include "PassManagerT.h"         // PassManagerT implementation
00018 #include "llvm/Module.h"
00019 #include "llvm/ModuleProvider.h"
00020 #include "llvm/ADT/STLExtras.h"
00021 #include "llvm/Support/TypeInfo.h"
00022 #include <iostream>
00023 #include <set>
00024 using namespace llvm;
00025 
00026 // IncludeFile - Stub function used to help linking out.
00027 IncludeFile::IncludeFile(void*) {}
00028 
00029 //===----------------------------------------------------------------------===//
00030 //   AnalysisID Class Implementation
00031 //
00032 
00033 // getCFGOnlyAnalyses - A wrapper around the CFGOnlyAnalyses which make it
00034 // initializer order independent.
00035 static std::vector<const PassInfo*> &getCFGOnlyAnalyses() {
00036   static std::vector<const PassInfo*> CFGOnlyAnalyses;
00037   return CFGOnlyAnalyses;
00038 }
00039 
00040 void RegisterPassBase::setOnlyUsesCFG() {
00041   getCFGOnlyAnalyses().push_back(&PIObj);
00042 }
00043 
00044 //===----------------------------------------------------------------------===//
00045 //   AnalysisResolver Class Implementation
00046 //
00047 
00048 AnalysisResolver::~AnalysisResolver() {
00049 }
00050 void AnalysisResolver::setAnalysisResolver(Pass *P, AnalysisResolver *AR) {
00051   assert(P->Resolver == 0 && "Pass already in a PassManager!");
00052   P->Resolver = AR;
00053 }
00054 
00055 //===----------------------------------------------------------------------===//
00056 //   AnalysisUsage Class Implementation
00057 //
00058 
00059 // setPreservesCFG - This function should be called to by the pass, iff they do
00060 // not:
00061 //
00062 //  1. Add or remove basic blocks from the function
00063 //  2. Modify terminator instructions in any way.
00064 //
00065 // This function annotates the AnalysisUsage info object to say that analyses
00066 // that only depend on the CFG are preserved by this pass.
00067 //
00068 void AnalysisUsage::setPreservesCFG() {
00069   // Since this transformation doesn't modify the CFG, it preserves all analyses
00070   // that only depend on the CFG (like dominators, loop info, etc...)
00071   //
00072   Preserved.insert(Preserved.end(),
00073                    getCFGOnlyAnalyses().begin(), getCFGOnlyAnalyses().end());
00074 }
00075 
00076 
00077 //===----------------------------------------------------------------------===//
00078 // PassManager implementation - The PassManager class is a simple Pimpl class
00079 // that wraps the PassManagerT template.
00080 //
00081 PassManager::PassManager() : PM(new ModulePassManager()) {}
00082 PassManager::~PassManager() { delete PM; }
00083 void PassManager::add(Pass *P) {
00084   ModulePass *MP = dynamic_cast<ModulePass*>(P);
00085   assert(MP && "Not a modulepass?");
00086   PM->add(MP);
00087 }
00088 bool PassManager::run(Module &M) { return PM->runOnModule(M); }
00089 
00090 //===----------------------------------------------------------------------===//
00091 // FunctionPassManager implementation - The FunctionPassManager class
00092 // is a simple Pimpl class that wraps the PassManagerT template. It
00093 // is like PassManager, but only deals in FunctionPasses.
00094 //
00095 FunctionPassManager::FunctionPassManager(ModuleProvider *P) :
00096   PM(new FunctionPassManagerT()), MP(P) {}
00097 FunctionPassManager::~FunctionPassManager() { delete PM; }
00098 void FunctionPassManager::add(FunctionPass *P) { PM->add(P); }
00099 void FunctionPassManager::add(ImmutablePass *IP) { PM->add(IP); }
00100 bool FunctionPassManager::run(Function &F) {
00101   try {
00102     MP->materializeFunction(&F);
00103   } catch (std::string& errstr) {
00104     std::cerr << "Error reading bytecode file: " << errstr << "\n";
00105     abort();
00106   } catch (...) {
00107     std::cerr << "Error reading bytecode file!\n";
00108     abort();
00109   }
00110   return PM->run(F);
00111 }
00112 
00113 
00114 //===----------------------------------------------------------------------===//
00115 // TimingInfo Class - This class is used to calculate information about the
00116 // amount of time each pass takes to execute.  This only happens with
00117 // -time-passes is enabled on the command line.
00118 //
00119 bool llvm::TimePassesIsEnabled = false;
00120 static cl::opt<bool,true>
00121 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
00122             cl::desc("Time each pass, printing elapsed time for each on exit"));
00123 
00124 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
00125 // a non null value (if the -time-passes option is enabled) or it leaves it
00126 // null.  It may be called multiple times.
00127 void TimingInfo::createTheTimeInfo() {
00128   if (!TimePassesIsEnabled || TheTimeInfo) return;
00129 
00130   // Constructed the first time this is called, iff -time-passes is enabled.
00131   // This guarantees that the object will be constructed before static globals,
00132   // thus it will be destroyed before them.
00133   static TimingInfo TTI;
00134   TheTimeInfo = &TTI;
00135 }
00136 
00137 void PMDebug::PrintArgumentInformation(const Pass *P) {
00138   // Print out passes in pass manager...
00139   if (const AnalysisResolver *PM = dynamic_cast<const AnalysisResolver*>(P)) {
00140     for (unsigned i = 0, e = PM->getNumContainedPasses(); i != e; ++i)
00141       PrintArgumentInformation(PM->getContainedPass(i));
00142 
00143   } else {  // Normal pass.  Print argument information...
00144     // Print out arguments for registered passes that are _optimizations_
00145     if (const PassInfo *PI = P->getPassInfo())
00146       if (PI->getPassType() & PassInfo::Optimization)
00147         std::cerr << " -" << PI->getPassArgument();
00148   }
00149 }
00150 
00151 void PMDebug::PrintPassInformation(unsigned Depth, const char *Action,
00152                                    Pass *P, Module *M) {
00153   if (PassDebugging >= Executions) {
00154     std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '"
00155               << P->getPassName();
00156     if (M) std::cerr << "' on Module '" << M->getModuleIdentifier() << "'\n";
00157     std::cerr << "'...\n";
00158   }
00159 }
00160 
00161 void PMDebug::PrintPassInformation(unsigned Depth, const char *Action,
00162                                    Pass *P, Function *F) {
00163   if (PassDebugging >= Executions) {
00164     std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '"
00165               << P->getPassName();
00166     if (F) std::cerr << "' on Function '" << F->getName();
00167     std::cerr << "'...\n";
00168   }
00169 }
00170 
00171 void PMDebug::PrintPassInformation(unsigned Depth, const char *Action,
00172                                    Pass *P, BasicBlock *BB) {
00173   if (PassDebugging >= Executions) {
00174     std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '"
00175               << P->getPassName();
00176     if (BB) std::cerr << "' on BasicBlock '" << BB->getName();
00177     std::cerr << "'...\n";
00178   }
00179 }
00180 
00181 void PMDebug::PrintAnalysisSetInfo(unsigned Depth, const char *Msg,
00182                                    Pass *P, const std::vector<AnalysisID> &Set){
00183   if (PassDebugging >= Details && !Set.empty()) {
00184     std::cerr << (void*)P << std::string(Depth*2+3, ' ') << Msg << " Analyses:";
00185     for (unsigned i = 0; i != Set.size(); ++i) {
00186       if (i) std::cerr << ",";
00187       std::cerr << " " << Set[i]->getPassName();
00188     }
00189     std::cerr << "\n";
00190   }
00191 }
00192 
00193 //===----------------------------------------------------------------------===//
00194 // Pass Implementation
00195 //
00196 
00197 void ModulePass::addToPassManager(ModulePassManager *PM, AnalysisUsage &AU) {
00198   PM->addPass(this, AU);
00199 }
00200 
00201 bool Pass::mustPreserveAnalysisID(const PassInfo *AnalysisID) const {
00202   return Resolver->getAnalysisToUpdate(AnalysisID) != 0;
00203 }
00204 
00205 // dumpPassStructure - Implement the -debug-passes=Structure option
00206 void Pass::dumpPassStructure(unsigned Offset) {
00207   std::cerr << std::string(Offset*2, ' ') << getPassName() << "\n";
00208 }
00209 
00210 // getPassName - Use C++ RTTI to get a SOMEWHAT intelligible name for the pass.
00211 //
00212 const char *Pass::getPassName() const {
00213   if (const PassInfo *PI = getPassInfo())
00214     return PI->getPassName();
00215   return typeid(*this).name();
00216 }
00217 
00218 // print - Print out the internal state of the pass.  This is called by Analyze
00219 // to print out the contents of an analysis.  Otherwise it is not necessary to
00220 // implement this method.
00221 //
00222 void Pass::print(std::ostream &O,const Module*) const {
00223   O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n";
00224 }
00225 
00226 // dump - call print(std::cerr);
00227 void Pass::dump() const {
00228   print(std::cerr, 0);
00229 }
00230 
00231 //===----------------------------------------------------------------------===//
00232 // ImmutablePass Implementation
00233 //
00234 void ImmutablePass::addToPassManager(ModulePassManager *PM, 
00235                                      AnalysisUsage &AU) {
00236   PM->addPass(this, AU);
00237 }
00238 
00239 
00240 //===----------------------------------------------------------------------===//
00241 // FunctionPass Implementation
00242 //
00243 
00244 // run - On a module, we run this pass by initializing, runOnFunction'ing once
00245 // for every function in the module, then by finalizing.
00246 //
00247 bool FunctionPass::runOnModule(Module &M) {
00248   bool Changed = doInitialization(M);
00249 
00250   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00251     if (!I->isExternal())      // Passes are not run on external functions!
00252     Changed |= runOnFunction(*I);
00253 
00254   return Changed | doFinalization(M);
00255 }
00256 
00257 // run - On a function, we simply initialize, run the function, then finalize.
00258 //
00259 bool FunctionPass::run(Function &F) {
00260   if (F.isExternal()) return false;// Passes are not run on external functions!
00261 
00262   bool Changed = doInitialization(*F.getParent());
00263   Changed |= runOnFunction(F);
00264   return Changed | doFinalization(*F.getParent());
00265 }
00266 
00267 void FunctionPass::addToPassManager(ModulePassManager *PM,
00268                                     AnalysisUsage &AU) {
00269   PM->addPass(this, AU);
00270 }
00271 
00272 void FunctionPass::addToPassManager(FunctionPassManagerT *PM,
00273                                     AnalysisUsage &AU) {
00274   PM->addPass(this, AU);
00275 }
00276 
00277 //===----------------------------------------------------------------------===//
00278 // BasicBlockPass Implementation
00279 //
00280 
00281 // To run this pass on a function, we simply call runOnBasicBlock once for each
00282 // function.
00283 //
00284 bool BasicBlockPass::runOnFunction(Function &F) {
00285   bool Changed = doInitialization(F);
00286   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
00287     Changed |= runOnBasicBlock(*I);
00288   return Changed | doFinalization(F);
00289 }
00290 
00291 // To run directly on the basic block, we initialize, runOnBasicBlock, then
00292 // finalize.
00293 //
00294 bool BasicBlockPass::runPass(BasicBlock &BB) {
00295   Function &F = *BB.getParent();
00296   Module &M = *F.getParent();
00297   bool Changed = doInitialization(M);
00298   Changed |= doInitialization(F);
00299   Changed |= runOnBasicBlock(BB);
00300   Changed |= doFinalization(F);
00301   Changed |= doFinalization(M);
00302   return Changed;
00303 }
00304 
00305 void BasicBlockPass::addToPassManager(FunctionPassManagerT *PM,
00306                                       AnalysisUsage &AU) {
00307   PM->addPass(this, AU);
00308 }
00309 
00310 void BasicBlockPass::addToPassManager(BasicBlockPassManager *PM,
00311                                       AnalysisUsage &AU) {
00312   PM->addPass(this, AU);
00313 }
00314 
00315 
00316 //===----------------------------------------------------------------------===//
00317 // Pass Registration mechanism
00318 //
00319 static std::map<TypeInfo, PassInfo*> *PassInfoMap = 0;
00320 static std::vector<PassRegistrationListener*> *Listeners = 0;
00321 
00322 // getPassInfo - Return the PassInfo data structure that corresponds to this
00323 // pass...
00324 const PassInfo *Pass::getPassInfo() const {
00325   if (PassInfoCache) return PassInfoCache;
00326   return lookupPassInfo(typeid(*this));
00327 }
00328 
00329 const PassInfo *Pass::lookupPassInfo(const std::type_info &TI) {
00330   if (PassInfoMap == 0) return 0;
00331   std::map<TypeInfo, PassInfo*>::iterator I = PassInfoMap->find(TI);
00332   return (I != PassInfoMap->end()) ? I->second : 0;
00333 }
00334 
00335 void RegisterPassBase::registerPass() {
00336   if (PassInfoMap == 0)
00337     PassInfoMap = new std::map<TypeInfo, PassInfo*>();
00338 
00339   assert(PassInfoMap->find(PIObj.getTypeInfo()) == PassInfoMap->end() &&
00340          "Pass already registered!");
00341   PassInfoMap->insert(std::make_pair(TypeInfo(PIObj.getTypeInfo()), &PIObj));
00342 
00343   // Notify any listeners...
00344   if (Listeners)
00345     for (std::vector<PassRegistrationListener*>::iterator
00346            I = Listeners->begin(), E = Listeners->end(); I != E; ++I)
00347       (*I)->passRegistered(&PIObj);
00348 }
00349 
00350 void RegisterPassBase::unregisterPass() {
00351   assert(PassInfoMap && "Pass registered but not in map!");
00352   std::map<TypeInfo, PassInfo*>::iterator I =
00353     PassInfoMap->find(PIObj.getTypeInfo());
00354   assert(I != PassInfoMap->end() && "Pass registered but not in map!");
00355 
00356   // Remove pass from the map...
00357   PassInfoMap->erase(I);
00358   if (PassInfoMap->empty()) {
00359     delete PassInfoMap;
00360     PassInfoMap = 0;
00361   }
00362 
00363   // Notify any listeners...
00364   if (Listeners)
00365     for (std::vector<PassRegistrationListener*>::iterator
00366            I = Listeners->begin(), E = Listeners->end(); I != E; ++I)
00367       (*I)->passUnregistered(&PIObj);
00368 }
00369 
00370 //===----------------------------------------------------------------------===//
00371 //                  Analysis Group Implementation Code
00372 //===----------------------------------------------------------------------===//
00373 
00374 struct AnalysisGroupInfo {
00375   const PassInfo *DefaultImpl;
00376   std::set<const PassInfo *> Implementations;
00377   AnalysisGroupInfo() : DefaultImpl(0) {}
00378 };
00379 
00380 static std::map<const PassInfo *, AnalysisGroupInfo> *AnalysisGroupInfoMap = 0;
00381 
00382 // RegisterAGBase implementation
00383 //
00384 RegisterAGBase::RegisterAGBase(const std::type_info &Interface,
00385                                const std::type_info *Pass, bool isDefault)
00386   : RegisterPassBase(Interface, PassInfo::AnalysisGroup),
00387     ImplementationInfo(0), isDefaultImplementation(isDefault) {
00388 
00389   InterfaceInfo = const_cast<PassInfo*>(Pass::lookupPassInfo(Interface));
00390   if (InterfaceInfo == 0) {
00391     // First reference to Interface, register it now.
00392     registerPass();
00393     InterfaceInfo = &PIObj;
00394   }
00395   assert(InterfaceInfo->getPassType() == PassInfo::AnalysisGroup &&
00396          "Trying to join an analysis group that is a normal pass!");
00397 
00398   if (Pass) {
00399     ImplementationInfo = Pass::lookupPassInfo(*Pass);
00400     assert(ImplementationInfo &&
00401            "Must register pass before adding to AnalysisGroup!");
00402 
00403     // Make sure we keep track of the fact that the implementation implements
00404     // the interface.
00405     PassInfo *IIPI = const_cast<PassInfo*>(ImplementationInfo);
00406     IIPI->addInterfaceImplemented(InterfaceInfo);
00407 
00408     // Lazily allocate to avoid nasty initialization order dependencies
00409     if (AnalysisGroupInfoMap == 0)
00410       AnalysisGroupInfoMap = new std::map<const PassInfo *,AnalysisGroupInfo>();
00411 
00412     AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo];
00413     assert(AGI.Implementations.count(ImplementationInfo) == 0 &&
00414            "Cannot add a pass to the same analysis group more than once!");
00415     AGI.Implementations.insert(ImplementationInfo);
00416     if (isDefault) {
00417       assert(AGI.DefaultImpl == 0 && InterfaceInfo->getNormalCtor() == 0 &&
00418              "Default implementation for analysis group already specified!");
00419       assert(ImplementationInfo->getNormalCtor() &&
00420            "Cannot specify pass as default if it does not have a default ctor");
00421       AGI.DefaultImpl = ImplementationInfo;
00422       InterfaceInfo->setNormalCtor(ImplementationInfo->getNormalCtor());
00423     }
00424   }
00425 }
00426 
00427 void RegisterAGBase::setGroupName(const char *Name) {
00428   assert(InterfaceInfo->getPassName()[0] == 0 && "Interface Name already set!");
00429   InterfaceInfo->setPassName(Name);
00430 }
00431 
00432 RegisterAGBase::~RegisterAGBase() {
00433   if (ImplementationInfo) {
00434     assert(AnalysisGroupInfoMap && "Inserted into map, but map doesn't exist?");
00435     AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo];
00436 
00437     assert(AGI.Implementations.count(ImplementationInfo) &&
00438            "Pass not a member of analysis group?");
00439 
00440     if (AGI.DefaultImpl == ImplementationInfo)
00441       AGI.DefaultImpl = 0;
00442 
00443     AGI.Implementations.erase(ImplementationInfo);
00444 
00445     // Last member of this analysis group? Unregister PassInfo, delete map entry
00446     if (AGI.Implementations.empty()) {
00447       assert(AGI.DefaultImpl == 0 &&
00448              "Default implementation didn't unregister?");
00449       AnalysisGroupInfoMap->erase(InterfaceInfo);
00450       if (AnalysisGroupInfoMap->empty()) {  // Delete map if empty
00451         delete AnalysisGroupInfoMap;
00452         AnalysisGroupInfoMap = 0;
00453       }
00454     }
00455   }
00456   
00457   if (InterfaceInfo == &PIObj)
00458     unregisterPass();
00459 }
00460 
00461 
00462 //===----------------------------------------------------------------------===//
00463 // PassRegistrationListener implementation
00464 //
00465 
00466 // PassRegistrationListener ctor - Add the current object to the list of
00467 // PassRegistrationListeners...
00468 PassRegistrationListener::PassRegistrationListener() {
00469   if (!Listeners) Listeners = new std::vector<PassRegistrationListener*>();
00470   Listeners->push_back(this);
00471 }
00472 
00473 // dtor - Remove object from list of listeners...
00474 PassRegistrationListener::~PassRegistrationListener() {
00475   std::vector<PassRegistrationListener*>::iterator I =
00476     std::find(Listeners->begin(), Listeners->end(), this);
00477   assert(Listeners && I != Listeners->end() &&
00478          "PassRegistrationListener not registered!");
00479   Listeners->erase(I);
00480 
00481   if (Listeners->empty()) {
00482     delete Listeners;
00483     Listeners = 0;
00484   }
00485 }
00486 
00487 // enumeratePasses - Iterate over the registered passes, calling the
00488 // passEnumerate callback on each PassInfo object.
00489 //
00490 void PassRegistrationListener::enumeratePasses() {
00491   if (PassInfoMap)
00492     for (std::map<TypeInfo, PassInfo*>::iterator I = PassInfoMap->begin(),
00493            E = PassInfoMap->end(); I != E; ++I)
00494       passEnumerate(I->second);
00495 }
00496