LLVM API Documentation
00001 //===- Pass.cpp - LLVM Pass Infrastructure Implementation -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/Pass.h" 00017 #include "llvm/PassManager.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/ModuleProvider.h" 00020 #include "llvm/ADT/STLExtras.h" 00021 #include "llvm/Support/ManagedStatic.h" 00022 #include "llvm/System/Atomic.h" 00023 #include "llvm/System/Mutex.h" 00024 #include "llvm/System/Threading.h" 00025 #include <algorithm> 00026 #include <map> 00027 #include <set> 00028 using namespace llvm; 00029 00030 //===----------------------------------------------------------------------===// 00031 // Pass Implementation 00032 // 00033 00034 // Force out-of-line virtual method. 00035 Pass::~Pass() { 00036 delete Resolver; 00037 } 00038 00039 // Force out-of-line virtual method. 00040 ModulePass::~ModulePass() { } 00041 00042 bool Pass::mustPreserveAnalysisID(const PassInfo *AnalysisID) const { 00043 return Resolver->getAnalysisIfAvailable(AnalysisID, true) != 0; 00044 } 00045 00046 // dumpPassStructure - Implement the -debug-passes=Structure option 00047 void Pass::dumpPassStructure(unsigned Offset) { 00048 cerr << std::string(Offset*2, ' ') << getPassName() << "\n"; 00049 } 00050 00051 /// getPassName - Return a nice clean name for a pass. This usually 00052 /// implemented in terms of the name that is registered by one of the 00053 /// Registration templates, but can be overloaded directly. 00054 /// 00055 const char *Pass::getPassName() const { 00056 if (const PassInfo *PI = getPassInfo()) 00057 return PI->getPassName(); 00058 return "Unnamed pass: implement Pass::getPassName()"; 00059 } 00060 00061 // print - Print out the internal state of the pass. This is called by Analyze 00062 // to print out the contents of an analysis. Otherwise it is not necessary to 00063 // implement this method. 00064 // 00065 void Pass::print(std::ostream &O,const Module*) const { 00066 O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n"; 00067 } 00068 00069 // dump - call print(cerr); 00070 void Pass::dump() const { 00071 print(*cerr.stream(), 0); 00072 } 00073 00074 //===----------------------------------------------------------------------===// 00075 // ImmutablePass Implementation 00076 // 00077 // Force out-of-line virtual method. 00078 ImmutablePass::~ImmutablePass() { } 00079 00080 //===----------------------------------------------------------------------===// 00081 // FunctionPass Implementation 00082 // 00083 00084 // run - On a module, we run this pass by initializing, runOnFunction'ing once 00085 // for every function in the module, then by finalizing. 00086 // 00087 bool FunctionPass::runOnModule(Module &M) { 00088 bool Changed = doInitialization(M); 00089 00090 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00091 if (!I->isDeclaration()) // Passes are not run on external functions! 00092 Changed |= runOnFunction(*I); 00093 00094 return Changed | doFinalization(M); 00095 } 00096 00097 // run - On a function, we simply initialize, run the function, then finalize. 00098 // 00099 bool FunctionPass::run(Function &F) { 00100 // Passes are not run on external functions! 00101 if (F.isDeclaration()) return false; 00102 00103 bool Changed = doInitialization(*F.getParent()); 00104 Changed |= runOnFunction(F); 00105 return Changed | doFinalization(*F.getParent()); 00106 } 00107 00108 //===----------------------------------------------------------------------===// 00109 // BasicBlockPass Implementation 00110 // 00111 00112 // To run this pass on a function, we simply call runOnBasicBlock once for each 00113 // function. 00114 // 00115 bool BasicBlockPass::runOnFunction(Function &F) { 00116 bool Changed = doInitialization(F); 00117 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00118 Changed |= runOnBasicBlock(*I); 00119 return Changed | doFinalization(F); 00120 } 00121 00122 //===----------------------------------------------------------------------===// 00123 // Pass Registration mechanism 00124 // 00125 namespace { 00126 class PassRegistrar { 00127 /// PassInfoMap - Keep track of the passinfo object for each registered llvm 00128 /// pass. 00129 typedef std::map<intptr_t, const PassInfo*> MapType; 00130 MapType PassInfoMap; 00131 00132 /// AnalysisGroupInfo - Keep track of information for each analysis group. 00133 struct AnalysisGroupInfo { 00134 const PassInfo *DefaultImpl; 00135 std::set<const PassInfo *> Implementations; 00136 AnalysisGroupInfo() : DefaultImpl(0) {} 00137 }; 00138 00139 /// AnalysisGroupInfoMap - Information for each analysis group. 00140 std::map<const PassInfo *, AnalysisGroupInfo> AnalysisGroupInfoMap; 00141 00142 public: 00143 00144 const PassInfo *GetPassInfo(intptr_t TI) const { 00145 MapType::const_iterator I = PassInfoMap.find(TI); 00146 return I != PassInfoMap.end() ? I->second : 0; 00147 } 00148 00149 void RegisterPass(const PassInfo &PI) { 00150 bool Inserted = 00151 PassInfoMap.insert(std::make_pair(PI.getTypeInfo(),&PI)).second; 00152 assert(Inserted && "Pass registered multiple times!"); Inserted=Inserted; 00153 } 00154 00155 void UnregisterPass(const PassInfo &PI) { 00156 MapType::iterator I = PassInfoMap.find(PI.getTypeInfo()); 00157 assert(I != PassInfoMap.end() && "Pass registered but not in map!"); 00158 00159 // Remove pass from the map. 00160 PassInfoMap.erase(I); 00161 } 00162 00163 void EnumerateWith(PassRegistrationListener *L) { 00164 for (MapType::const_iterator I = PassInfoMap.begin(), 00165 E = PassInfoMap.end(); I != E; ++I) 00166 L->passEnumerate(I->second); 00167 } 00168 00169 00170 /// Analysis Group Mechanisms. 00171 void RegisterAnalysisGroup(PassInfo *InterfaceInfo, 00172 const PassInfo *ImplementationInfo, 00173 bool isDefault) { 00174 AnalysisGroupInfo &AGI = AnalysisGroupInfoMap[InterfaceInfo]; 00175 assert(AGI.Implementations.count(ImplementationInfo) == 0 && 00176 "Cannot add a pass to the same analysis group more than once!"); 00177 AGI.Implementations.insert(ImplementationInfo); 00178 if (isDefault) { 00179 assert(AGI.DefaultImpl == 0 && InterfaceInfo->getNormalCtor() == 0 && 00180 "Default implementation for analysis group already specified!"); 00181 assert(ImplementationInfo->getNormalCtor() && 00182 "Cannot specify pass as default if it does not have a default ctor"); 00183 AGI.DefaultImpl = ImplementationInfo; 00184 InterfaceInfo->setNormalCtor(ImplementationInfo->getNormalCtor()); 00185 } 00186 } 00187 }; 00188 } 00189 00190 static std::vector<PassRegistrationListener*> *Listeners = 0; 00191 static sys::SmartMutex<true> ListenersLock; 00192 00193 // FIXME: This should use ManagedStatic to manage the pass registrar. 00194 // Unfortunately, we can't do this, because passes are registered with static 00195 // ctors, and having llvm_shutdown clear this map prevents successful 00196 // ressurection after llvm_shutdown is run. 00197 static PassRegistrar *getPassRegistrar() { 00198 static PassRegistrar *PassRegistrarObj = 0; 00199 00200 // Use double-checked locking to safely initialize the registrar when 00201 // we're running in multithreaded mode. 00202 PassRegistrar* tmp = PassRegistrarObj; 00203 if (llvm_is_multithreaded()) { 00204 sys::MemoryFence(); 00205 if (!tmp) { 00206 llvm_acquire_global_lock(); 00207 tmp = PassRegistrarObj; 00208 if (!tmp) { 00209 tmp = new PassRegistrar(); 00210 sys::MemoryFence(); 00211 PassRegistrarObj = tmp; 00212 } 00213 llvm_release_global_lock(); 00214 } 00215 } else if (!tmp) { 00216 PassRegistrarObj = new PassRegistrar(); 00217 } 00218 00219 return PassRegistrarObj; 00220 } 00221 00222 // getPassInfo - Return the PassInfo data structure that corresponds to this 00223 // pass... 00224 const PassInfo *Pass::getPassInfo() const { 00225 return lookupPassInfo(PassID); 00226 } 00227 00228 const PassInfo *Pass::lookupPassInfo(intptr_t TI) { 00229 return getPassRegistrar()->GetPassInfo(TI); 00230 } 00231 00232 void PassInfo::registerPass() { 00233 getPassRegistrar()->RegisterPass(*this); 00234 00235 // Notify any listeners. 00236 sys::SmartScopedLock<true> Lock(ListenersLock); 00237 if (Listeners) 00238 for (std::vector<PassRegistrationListener*>::iterator 00239 I = Listeners->begin(), E = Listeners->end(); I != E; ++I) 00240 (*I)->passRegistered(this); 00241 } 00242 00243 void PassInfo::unregisterPass() { 00244 getPassRegistrar()->UnregisterPass(*this); 00245 } 00246 00247 //===----------------------------------------------------------------------===// 00248 // Analysis Group Implementation Code 00249 //===----------------------------------------------------------------------===// 00250 00251 // RegisterAGBase implementation 00252 // 00253 RegisterAGBase::RegisterAGBase(const char *Name, intptr_t InterfaceID, 00254 intptr_t PassID, bool isDefault) 00255 : PassInfo(Name, InterfaceID), 00256 ImplementationInfo(0), isDefaultImplementation(isDefault) { 00257 00258 InterfaceInfo = const_cast<PassInfo*>(Pass::lookupPassInfo(InterfaceID)); 00259 if (InterfaceInfo == 0) { 00260 // First reference to Interface, register it now. 00261 registerPass(); 00262 InterfaceInfo = this; 00263 } 00264 assert(isAnalysisGroup() && 00265 "Trying to join an analysis group that is a normal pass!"); 00266 00267 if (PassID) { 00268 ImplementationInfo = Pass::lookupPassInfo(PassID); 00269 assert(ImplementationInfo && 00270 "Must register pass before adding to AnalysisGroup!"); 00271 00272 // Make sure we keep track of the fact that the implementation implements 00273 // the interface. 00274 PassInfo *IIPI = const_cast<PassInfo*>(ImplementationInfo); 00275 IIPI->addInterfaceImplemented(InterfaceInfo); 00276 00277 getPassRegistrar()->RegisterAnalysisGroup(InterfaceInfo, IIPI, isDefault); 00278 } 00279 } 00280 00281 00282 //===----------------------------------------------------------------------===// 00283 // PassRegistrationListener implementation 00284 // 00285 00286 // PassRegistrationListener ctor - Add the current object to the list of 00287 // PassRegistrationListeners... 00288 PassRegistrationListener::PassRegistrationListener() { 00289 sys::SmartScopedLock<true> Lock(ListenersLock); 00290 if (!Listeners) Listeners = new std::vector<PassRegistrationListener*>(); 00291 Listeners->push_back(this); 00292 } 00293 00294 // dtor - Remove object from list of listeners... 00295 PassRegistrationListener::~PassRegistrationListener() { 00296 sys::SmartScopedLock<true> Lock(ListenersLock); 00297 std::vector<PassRegistrationListener*>::iterator I = 00298 std::find(Listeners->begin(), Listeners->end(), this); 00299 assert(Listeners && I != Listeners->end() && 00300 "PassRegistrationListener not registered!"); 00301 Listeners->erase(I); 00302 00303 if (Listeners->empty()) { 00304 delete Listeners; 00305 Listeners = 0; 00306 } 00307 } 00308 00309 // enumeratePasses - Iterate over the registered passes, calling the 00310 // passEnumerate callback on each PassInfo object. 00311 // 00312 void PassRegistrationListener::enumeratePasses() { 00313 getPassRegistrar()->EnumerateWith(this); 00314 } 00315 00316 //===----------------------------------------------------------------------===// 00317 // AnalysisUsage Class Implementation 00318 // 00319 00320 namespace { 00321 struct GetCFGOnlyPasses : public PassRegistrationListener { 00322 typedef AnalysisUsage::VectorType VectorType; 00323 VectorType &CFGOnlyList; 00324 GetCFGOnlyPasses(VectorType &L) : CFGOnlyList(L) {} 00325 00326 void passEnumerate(const PassInfo *P) { 00327 if (P->isCFGOnlyPass()) 00328 CFGOnlyList.push_back(P); 00329 } 00330 }; 00331 } 00332 00333 // setPreservesCFG - This function should be called to by the pass, iff they do 00334 // not: 00335 // 00336 // 1. Add or remove basic blocks from the function 00337 // 2. Modify terminator instructions in any way. 00338 // 00339 // This function annotates the AnalysisUsage info object to say that analyses 00340 // that only depend on the CFG are preserved by this pass. 00341 // 00342 void AnalysisUsage::setPreservesCFG() { 00343 // Since this transformation doesn't modify the CFG, it preserves all analyses 00344 // that only depend on the CFG (like dominators, loop info, etc...) 00345 GetCFGOnlyPasses(Preserved).enumeratePasses(); 00346 } 00347 00348