LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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