LLVM API Documentation
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