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