LLVM API Documentation
00001 //===- llvm/Pass.h - Base class for Passes ----------------------*- C++ -*-===// 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 defines a base class that indicates that a specified class is a 00011 // transformation pass implementation. 00012 // 00013 // Passes are designed this way so that it is possible to run passes in a cache 00014 // and organizationally optimal order without having to specify it at the front 00015 // end. This allows arbitrary passes to be strung together and have them 00016 // executed as effeciently as possible. 00017 // 00018 // Passes should extend one of the classes below, depending on the guarantees 00019 // that it can make about what will be modified as it is run. For example, most 00020 // global optimizations should derive from FunctionPass, because they do not add 00021 // or delete functions, they operate on the internals of the function. 00022 // 00023 // Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the 00024 // bottom), so the APIs exposed by these files are also automatically available 00025 // to all users of this file. 00026 // 00027 //===----------------------------------------------------------------------===// 00028 00029 #ifndef LLVM_PASS_H 00030 #define LLVM_PASS_H 00031 00032 #include <vector> 00033 #include <map> 00034 #include <iosfwd> 00035 #include <typeinfo> 00036 #include <cassert> 00037 00038 namespace llvm { 00039 00040 class Value; 00041 class BasicBlock; 00042 class Function; 00043 class Module; 00044 class AnalysisUsage; 00045 class PassInfo; 00046 class ImmutablePass; 00047 template<class Trait> class PassManagerT; 00048 class BasicBlockPassManager; 00049 class FunctionPassManagerT; 00050 class ModulePassManager; 00051 struct AnalysisResolver; 00052 00053 // AnalysisID - Use the PassInfo to identify a pass... 00054 typedef const PassInfo* AnalysisID; 00055 00056 //===----------------------------------------------------------------------===// 00057 /// Pass interface - Implemented by all 'passes'. Subclass this if you are an 00058 /// interprocedural optimization or you do not fit into any of the more 00059 /// constrained passes described below. 00060 /// 00061 class Pass { 00062 friend struct AnalysisResolver; 00063 AnalysisResolver *Resolver; // AnalysisResolver this pass is owned by... 00064 const PassInfo *PassInfoCache; 00065 00066 // AnalysisImpls - This keeps track of which passes implement the interfaces 00067 // that are required by the current pass (to implement getAnalysis()). 00068 // 00069 std::vector<std::pair<const PassInfo*, Pass*> > AnalysisImpls; 00070 00071 void operator=(const Pass&); // DO NOT IMPLEMENT 00072 Pass(const Pass &); // DO NOT IMPLEMENT 00073 public: 00074 Pass() : Resolver(0), PassInfoCache(0) {} 00075 virtual ~Pass() {} // Destructor is virtual so we can be subclassed 00076 00077 /// getPassName - Return a nice clean name for a pass. This usually 00078 /// implemented in terms of the name that is registered by one of the 00079 /// Registration templates, but can be overloaded directly, and if nothing 00080 /// else is available, C++ RTTI will be consulted to get a SOMEWHAT 00081 /// intelligible name for the pass. 00082 /// 00083 virtual const char *getPassName() const; 00084 00085 /// getPassInfo - Return the PassInfo data structure that corresponds to this 00086 /// pass... If the pass has not been registered, this will return null. 00087 /// 00088 const PassInfo *getPassInfo() const; 00089 00090 /// runPass - Run this pass, returning true if a modification was made to the 00091 /// module argument. This should be implemented by all concrete subclasses. 00092 /// 00093 virtual bool runPass(Module &M) { return false; } 00094 virtual bool runPass(BasicBlock&) { return false; } 00095 00096 /// print - Print out the internal state of the pass. This is called by 00097 /// Analyze to print out the contents of an analysis. Otherwise it is not 00098 /// necessary to implement this method. Beware that the module pointer MAY be 00099 /// null. This automatically forwards to a virtual function that does not 00100 /// provide the Module* in case the analysis doesn't need it it can just be 00101 /// ignored. 00102 /// 00103 virtual void print(std::ostream &O, const Module *M) const; 00104 void dump() const; // dump - call print(std::cerr, 0); 00105 00106 00107 /// getAnalysisUsage - This function should be overriden by passes that need 00108 /// analysis information to do their job. If a pass specifies that it uses a 00109 /// particular analysis result to this function, it can then use the 00110 /// getAnalysis<AnalysisType>() function, below. 00111 /// 00112 virtual void getAnalysisUsage(AnalysisUsage &Info) const { 00113 // By default, no analysis results are used, all are invalidated. 00114 } 00115 00116 /// releaseMemory() - This member can be implemented by a pass if it wants to 00117 /// be able to release its memory when it is no longer needed. The default 00118 /// behavior of passes is to hold onto memory for the entire duration of their 00119 /// lifetime (which is the entire compile time). For pipelined passes, this 00120 /// is not a big deal because that memory gets recycled every time the pass is 00121 /// invoked on another program unit. For IP passes, it is more important to 00122 /// free memory when it is unused. 00123 /// 00124 /// Optionally implement this function to release pass memory when it is no 00125 /// longer used. 00126 /// 00127 virtual void releaseMemory() {} 00128 00129 // dumpPassStructure - Implement the -debug-passes=PassStructure option 00130 virtual void dumpPassStructure(unsigned Offset = 0); 00131 00132 00133 // getPassInfo - Static method to get the pass information from a class name. 00134 template<typename AnalysisClass> 00135 static const PassInfo *getClassPassInfo() { 00136 return lookupPassInfo(typeid(AnalysisClass)); 00137 } 00138 00139 // lookupPassInfo - Return the pass info object for the specified pass class, 00140 // or null if it is not known. 00141 static const PassInfo *lookupPassInfo(const std::type_info &TI); 00142 00143 /// getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses 00144 /// to get to the analysis information that might be around that needs to be 00145 /// updated. This is different than getAnalysis in that it can fail (ie the 00146 /// analysis results haven't been computed), so should only be used if you 00147 /// provide the capability to update an analysis that exists. This method is 00148 /// often used by transformation APIs to update analysis results for a pass 00149 /// automatically as the transform is performed. 00150 /// 00151 template<typename AnalysisType> 00152 AnalysisType *getAnalysisToUpdate() const; // Defined in PassAnalysisSupport.h 00153 00154 /// mustPreserveAnalysisID - This method serves the same function as 00155 /// getAnalysisToUpdate, but works if you just have an AnalysisID. This 00156 /// obviously cannot give you a properly typed instance of the class if you 00157 /// don't have the class name available (use getAnalysisToUpdate if you do), 00158 /// but it can tell you if you need to preserve the pass at least. 00159 /// 00160 bool mustPreserveAnalysisID(const PassInfo *AnalysisID) const; 00161 00162 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get 00163 /// to the analysis information that they claim to use by overriding the 00164 /// getAnalysisUsage function. 00165 /// 00166 template<typename AnalysisType> 00167 AnalysisType &getAnalysis() const { 00168 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 00169 const PassInfo *PI = getClassPassInfo<AnalysisType>(); 00170 return getAnalysisID<AnalysisType>(PI); 00171 } 00172 00173 template<typename AnalysisType> 00174 AnalysisType &getAnalysisID(const PassInfo *PI) const { 00175 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 00176 assert(PI && "getAnalysis for unregistered pass!"); 00177 00178 // PI *must* appear in AnalysisImpls. Because the number of passes used 00179 // should be a small number, we just do a linear search over a (dense) 00180 // vector. 00181 Pass *ResultPass = 0; 00182 for (unsigned i = 0; ; ++i) { 00183 assert(i != AnalysisImpls.size() && 00184 "getAnalysis*() called on an analysis that was not " 00185 "'required' by pass!"); 00186 if (AnalysisImpls[i].first == PI) { 00187 ResultPass = AnalysisImpls[i].second; 00188 break; 00189 } 00190 } 00191 00192 // Because the AnalysisType may not be a subclass of pass (for 00193 // AnalysisGroups), we must use dynamic_cast here to potentially adjust the 00194 // return pointer (because the class may multiply inherit, once from pass, 00195 // once from AnalysisType). 00196 // 00197 AnalysisType *Result = dynamic_cast<AnalysisType*>(ResultPass); 00198 assert(Result && "Pass does not implement interface required!"); 00199 return *Result; 00200 } 00201 00202 private: 00203 template<typename Trait> friend class PassManagerT; 00204 friend class ModulePassManager; 00205 friend class FunctionPassManagerT; 00206 friend class BasicBlockPassManager; 00207 }; 00208 00209 inline std::ostream &operator<<(std::ostream &OS, const Pass &P) { 00210 P.print(OS, 0); return OS; 00211 } 00212 00213 //===----------------------------------------------------------------------===// 00214 /// ModulePass class - This class is used to implement unstructured 00215 /// interprocedural optimizations and analyses. ModulePasses may do anything 00216 /// they want to the program. 00217 /// 00218 class ModulePass : public Pass { 00219 public: 00220 /// runOnModule - Virtual method overriden by subclasses to process the module 00221 /// being operated on. 00222 virtual bool runOnModule(Module &M) = 0; 00223 00224 virtual bool runPass(Module &M) { return runOnModule(M); } 00225 virtual bool runPass(BasicBlock&) { return false; } 00226 00227 virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU); 00228 }; 00229 00230 00231 //===----------------------------------------------------------------------===// 00232 /// ImmutablePass class - This class is used to provide information that does 00233 /// not need to be run. This is useful for things like target information and 00234 /// "basic" versions of AnalysisGroups. 00235 /// 00236 class ImmutablePass : public ModulePass { 00237 public: 00238 /// initializePass - This method may be overriden by immutable passes to allow 00239 /// them to perform various initialization actions they require. This is 00240 /// primarily because an ImmutablePass can "require" another ImmutablePass, 00241 /// and if it does, the overloaded version of initializePass may get access to 00242 /// these passes with getAnalysis<>. 00243 /// 00244 virtual void initializePass() {} 00245 00246 /// ImmutablePasses are never run. 00247 /// 00248 virtual bool runOnModule(Module &M) { return false; } 00249 00250 private: 00251 template<typename Trait> friend class PassManagerT; 00252 friend class ModulePassManager; 00253 virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU); 00254 }; 00255 00256 //===----------------------------------------------------------------------===// 00257 /// FunctionPass class - This class is used to implement most global 00258 /// optimizations. Optimizations should subclass this class if they meet the 00259 /// following constraints: 00260 /// 00261 /// 1. Optimizations are organized globally, i.e., a function at a time 00262 /// 2. Optimizing a function does not cause the addition or removal of any 00263 /// functions in the module 00264 /// 00265 class FunctionPass : public ModulePass { 00266 public: 00267 /// doInitialization - Virtual method overridden by subclasses to do 00268 /// any necessary per-module initialization. 00269 /// 00270 virtual bool doInitialization(Module &M) { return false; } 00271 00272 /// runOnFunction - Virtual method overriden by subclasses to do the 00273 /// per-function processing of the pass. 00274 /// 00275 virtual bool runOnFunction(Function &F) = 0; 00276 00277 /// doFinalization - Virtual method overriden by subclasses to do any post 00278 /// processing needed after all passes have run. 00279 /// 00280 virtual bool doFinalization(Module &M) { return false; } 00281 00282 /// runOnModule - On a module, we run this pass by initializing, 00283 /// ronOnFunction'ing once for every function in the module, then by 00284 /// finalizing. 00285 /// 00286 virtual bool runOnModule(Module &M); 00287 00288 /// run - On a function, we simply initialize, run the function, then 00289 /// finalize. 00290 /// 00291 bool run(Function &F); 00292 00293 private: 00294 template<typename Trait> friend class PassManagerT; 00295 friend class ModulePassManager; 00296 friend class FunctionPassManagerT; 00297 friend class BasicBlockPassManager; 00298 virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU); 00299 virtual void addToPassManager(FunctionPassManagerT *PM, AnalysisUsage &AU); 00300 }; 00301 00302 00303 00304 //===----------------------------------------------------------------------===// 00305 /// BasicBlockPass class - This class is used to implement most local 00306 /// optimizations. Optimizations should subclass this class if they 00307 /// meet the following constraints: 00308 /// 1. Optimizations are local, operating on either a basic block or 00309 /// instruction at a time. 00310 /// 2. Optimizations do not modify the CFG of the contained function, or any 00311 /// other basic block in the function. 00312 /// 3. Optimizations conform to all of the constraints of FunctionPasses. 00313 /// 00314 class BasicBlockPass : public FunctionPass { 00315 public: 00316 /// doInitialization - Virtual method overridden by subclasses to do 00317 /// any necessary per-module initialization. 00318 /// 00319 virtual bool doInitialization(Module &M) { return false; } 00320 00321 /// doInitialization - Virtual method overridden by BasicBlockPass subclasses 00322 /// to do any necessary per-function initialization. 00323 /// 00324 virtual bool doInitialization(Function &F) { return false; } 00325 00326 /// runOnBasicBlock - Virtual method overriden by subclasses to do the 00327 /// per-basicblock processing of the pass. 00328 /// 00329 virtual bool runOnBasicBlock(BasicBlock &BB) = 0; 00330 00331 /// doFinalization - Virtual method overriden by BasicBlockPass subclasses to 00332 /// do any post processing needed after all passes have run. 00333 /// 00334 virtual bool doFinalization(Function &F) { return false; } 00335 00336 /// doFinalization - Virtual method overriden by subclasses to do any post 00337 /// processing needed after all passes have run. 00338 /// 00339 virtual bool doFinalization(Module &M) { return false; } 00340 00341 00342 // To run this pass on a function, we simply call runOnBasicBlock once for 00343 // each function. 00344 // 00345 bool runOnFunction(Function &F); 00346 00347 /// To run directly on the basic block, we initialize, runOnBasicBlock, then 00348 /// finalize. 00349 /// 00350 virtual bool runPass(Module &M) { return false; } 00351 virtual bool runPass(BasicBlock &BB); 00352 00353 private: 00354 template<typename Trait> friend class PassManagerT; 00355 friend class FunctionPassManagerT; 00356 friend class BasicBlockPassManager; 00357 virtual void addToPassManager(FunctionPassManagerT *PM, AnalysisUsage &AU); 00358 virtual void addToPassManager(BasicBlockPassManager *PM,AnalysisUsage &AU); 00359 }; 00360 00361 /// If the user specifies the -time-passes argument on an LLVM tool command line 00362 /// then the value of this boolean will be true, otherwise false. 00363 /// @brief This is the storage for the -time-passes option. 00364 extern bool TimePassesIsEnabled; 00365 00366 } // End llvm namespace 00367 00368 // Include support files that contain important APIs commonly used by Passes, 00369 // but that we want to separate out to make it easier to read the header files. 00370 // 00371 #include "llvm/PassSupport.h" 00372 #include "llvm/PassAnalysisSupport.h" 00373 00374 #endif