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 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 }