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