Pass.h revision df9ec1052b089f7c7520823addd74b3fd97ba674
1//===- llvm/Pass.h - Base class for XForm Passes -----------------*- C++ -*--=// 2// 3// This file defines a base class that indicates that a specified class is a 4// transformation pass implementation. 5// 6// Pass's are designed this way so that it is possible to run passes in a cache 7// and organizationally optimal order without having to specify it at the front 8// end. This allows arbitrary passes to be strung together and have them 9// executed as effeciently as possible. 10// 11// Passes should extend one of the classes below, depending on the guarantees 12// that it can make about what will be modified as it is run. For example, most 13// global optimizations should derive from FunctionPass, because they do not add 14// or delete functions, they operate on the internals of the function. 15// 16// Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the 17// bottom), so the APIs exposed by these files are also automatically available 18// to all users of this file. 19// 20//===----------------------------------------------------------------------===// 21 22#ifndef LLVM_PASS_H 23#define LLVM_PASS_H 24 25#include <vector> 26#include <map> 27#include <iosfwd> 28#include <typeinfo> 29#include <cassert> 30class Value; 31class BasicBlock; 32class Function; 33class Module; 34class AnalysisUsage; 35class PassInfo; 36class ImmutablePass; 37template<class UnitType> class PassManagerT; 38struct AnalysisResolver; 39 40// AnalysisID - Use the PassInfo to identify a pass... 41typedef const PassInfo* AnalysisID; 42 43//===----------------------------------------------------------------------===// 44/// Pass interface - Implemented by all 'passes'. Subclass this if you are an 45/// interprocedural optimization or you do not fit into any of the more 46/// constrained passes described below. 47/// 48class Pass { 49 friend class AnalysisResolver; 50 AnalysisResolver *Resolver; // AnalysisResolver this pass is owned by... 51 const PassInfo *PassInfoCache; 52 53 // AnalysisImpls - This keeps track of which passes implement the interfaces 54 // that are required by the current pass (to implement getAnalysis()). 55 // 56 std::vector<std::pair<const PassInfo*, Pass*> > AnalysisImpls; 57 58 void operator=(const Pass&); // DO NOT IMPLEMENT 59 Pass(const Pass &); // DO NOT IMPLEMENT 60public: 61 Pass() : Resolver(0), PassInfoCache(0) {} 62 virtual ~Pass() {} // Destructor is virtual so we can be subclassed 63 64 /// getPassName - Return a nice clean name for a pass. This usually 65 /// implemented in terms of the name that is registered by one of the 66 /// Registration templates, but can be overloaded directly, and if nothing 67 /// else is available, C++ RTTI will be consulted to get a SOMEWHAT 68 /// intelligable name for the pass. 69 /// 70 virtual const char *getPassName() const; 71 72 /// getPassInfo - Return the PassInfo data structure that corresponds to this 73 /// pass... If the pass has not been registered, this will return null. 74 /// 75 const PassInfo *getPassInfo() const; 76 77 /// run - Run this pass, returning true if a modification was made to the 78 /// module argument. This should be implemented by all concrete subclasses. 79 /// 80 virtual bool run(Module &M) = 0; 81 82 /// print - Print out the internal state of the pass. This is called by 83 /// Analyze to print out the contents of an analysis. Otherwise it is not 84 /// necessary to implement this method. Beware that the module pointer MAY be 85 /// null. This automatically forwards to a virtual function that does not 86 /// provide the Module* in case the analysis doesn't need it it can just be 87 /// ignored. 88 /// 89 virtual void print(std::ostream &O, const Module *M) const { print(O); } 90 virtual void print(std::ostream &O) const; 91 void dump() const; // dump - call print(std::cerr, 0); 92 93 94 /// getAnalysisUsage - This function should be overriden by passes that need 95 /// analysis information to do their job. If a pass specifies that it uses a 96 /// particular analysis result to this function, it can then use the 97 /// getAnalysis<AnalysisType>() function, below. 98 /// 99 virtual void getAnalysisUsage(AnalysisUsage &Info) const { 100 // By default, no analysis results are used, all are invalidated. 101 } 102 103 /// releaseMemory() - This member can be implemented by a pass if it wants to 104 /// be able to release its memory when it is no longer needed. The default 105 /// behavior of passes is to hold onto memory for the entire duration of their 106 /// lifetime (which is the entire compile time). For pipelined passes, this 107 /// is not a big deal because that memory gets recycled every time the pass is 108 /// invoked on another program unit. For IP passes, it is more important to 109 /// free memory when it is unused. 110 /// 111 /// Optionally implement this function to release pass memory when it is no 112 /// longer used. 113 /// 114 virtual void releaseMemory() {} 115 116 // dumpPassStructure - Implement the -debug-passes=PassStructure option 117 virtual void dumpPassStructure(unsigned Offset = 0); 118 119 120 // getPassInfo - Static method to get the pass information from a class name. 121 template<typename AnalysisClass> 122 static const PassInfo *getClassPassInfo() { 123 return lookupPassInfo(typeid(AnalysisClass)); 124 } 125 126 // lookupPassInfo - Return the pass info object for the specified pass class, 127 // or null if it is not known. 128 static const PassInfo *lookupPassInfo(const std::type_info &TI); 129 130 /// getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses 131 /// to get to the analysis information that might be around that needs to be 132 /// updated. This is different than getAnalysis in that it can fail (ie the 133 /// analysis results haven't been computed), so should only be used if you 134 /// provide the capability to update an analysis that exists. This method is 135 /// often used by transformation APIs to update analysis results for a pass 136 /// automatically as the transform is performed. 137 /// 138 template<typename AnalysisType> 139 AnalysisType *getAnalysisToUpdate() const; // Defined in PassAnalysisSupport.h 140 141 /// mustPreserveAnalysisID - This method serves the same function as 142 /// getAnalysisToUpdate, but works if you just have an AnalysisID. This 143 /// obviously cannot give you a properly typed instance of the class if you 144 /// don't have the class name available (use getAnalysisToUpdate if you do), 145 /// but it can tell you if you need to preserve the pass at least. 146 /// 147 bool mustPreserveAnalysisID(const PassInfo *AnalysisID) const; 148 149 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get 150 /// to the analysis information that they claim to use by overriding the 151 /// getAnalysisUsage function. 152 /// 153 template<typename AnalysisType> 154 AnalysisType &getAnalysis() const { 155 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 156 const PassInfo *PI = getClassPassInfo<AnalysisType>(); 157 return getAnalysisID<AnalysisType>(PI); 158 } 159 160 template<typename AnalysisType> 161 AnalysisType &getAnalysisID(const PassInfo *PI) const { 162 assert(Resolver && "Pass has not been inserted into a PassManager object!"); 163 assert(PI && "getAnalysis for unregistered pass!"); 164 165 // PI *must* appear in AnalysisImpls. Because the number of passes used 166 // should be a small number, we just do a linear search over a (dense) 167 // vector. 168 Pass *ResultPass = 0; 169 for (unsigned i = 0; ; ++i) { 170 assert(i != AnalysisImpls.size() && 171 "getAnalysis*() called on an analysis that we not " 172 "'required' by pass!"); 173 if (AnalysisImpls[i].first == PI) { 174 ResultPass = AnalysisImpls[i].second; 175 break; 176 } 177 } 178 179 // Because the AnalysisType may not be a subclass of pass (for 180 // AnalysisGroups), we must use dynamic_cast here to potentially adjust the 181 // return pointer (because the class may multiply inherit, once from pass, 182 // once from AnalysisType). 183 // 184 AnalysisType *Result = dynamic_cast<AnalysisType*>(ResultPass); 185 assert(Result && "Pass does not implement interface required!"); 186 return *Result; 187 } 188 189private: 190 friend class PassManagerT<Module>; 191 friend class PassManagerT<Function>; 192 friend class PassManagerT<BasicBlock>; 193 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU); 194}; 195 196inline std::ostream &operator<<(std::ostream &OS, const Pass &P) { 197 P.print(OS, 0); return OS; 198} 199 200 201 202//===----------------------------------------------------------------------===// 203/// ImmutablePass class - This class is used to provide information that does 204/// not need to be run. This is useful for things like target information and 205/// "basic" versions of AnalysisGroups. 206/// 207struct ImmutablePass : public Pass { 208 /// initializePass - This method may be overriden by immutable passes to allow 209 /// them to perform various initialization actions they require. This is 210 /// primarily because an ImmutablePass can "require" another ImmutablePass, 211 /// and if it does, the overloaded version of initializePass may get access to 212 /// these passes with getAnalysis<>. 213 /// 214 virtual void initializePass() {} 215 216 /// ImmutablePasses are never run. 217 /// 218 virtual bool run(Module &M) { return false; } 219 220private: 221 friend class PassManagerT<Module>; 222 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU); 223}; 224 225 226//===----------------------------------------------------------------------===// 227/// FunctionPass class - This class is used to implement most global 228/// optimizations. Optimizations should subclass this class if they meet the 229/// following constraints: 230/// 231/// 1. Optimizations are organized globally, i.e., a function at a time 232/// 2. Optimizing a function does not cause the addition or removal of any 233/// functions in the module 234/// 235struct FunctionPass : public Pass { 236 /// doInitialization - Virtual method overridden by subclasses to do 237 /// any necessary per-module initialization. 238 /// 239 virtual bool doInitialization(Module &M) { return false; } 240 241 /// runOnFunction - Virtual method overriden by subclasses to do the 242 /// per-function processing of the pass. 243 /// 244 virtual bool runOnFunction(Function &F) = 0; 245 246 /// doFinalization - Virtual method overriden by subclasses to do any post 247 /// processing needed after all passes have run. 248 /// 249 virtual bool doFinalization(Module &M) { return false; } 250 251 /// run - On a module, we run this pass by initializing, ronOnFunction'ing 252 /// once for every function in the module, then by finalizing. 253 /// 254 virtual bool run(Module &M); 255 256 /// run - On a function, we simply initialize, run the function, then 257 /// finalize. 258 /// 259 bool run(Function &F); 260 261private: 262 friend class PassManagerT<Module>; 263 friend class PassManagerT<Function>; 264 friend class PassManagerT<BasicBlock>; 265 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU); 266 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU); 267}; 268 269 270 271//===----------------------------------------------------------------------===// 272/// BasicBlockPass class - This class is used to implement most local 273/// optimizations. Optimizations should subclass this class if they 274/// meet the following constraints: 275/// 1. Optimizations are local, operating on either a basic block or 276/// instruction at a time. 277/// 2. Optimizations do not modify the CFG of the contained function, or any 278/// other basic block in the function. 279/// 3. Optimizations conform to all of the constraints of FunctionPass's. 280/// 281struct BasicBlockPass : public FunctionPass { 282 /// doInitialization - Virtual method overridden by subclasses to do 283 /// any necessary per-module initialization. 284 /// 285 virtual bool doInitialization(Module &M) { return false; } 286 287 /// doInitialization - Virtual method overridden by BasicBlockPass subclasses 288 /// to do any necessary per-function initialization. 289 /// 290 virtual bool doInitialization(Function &F) { return false; } 291 292 /// runOnBasicBlock - Virtual method overriden by subclasses to do the 293 /// per-basicblock processing of the pass. 294 /// 295 virtual bool runOnBasicBlock(BasicBlock &BB) = 0; 296 297 /// doFinalization - Virtual method overriden by BasicBlockPass subclasses to 298 /// do any post processing needed after all passes have run. 299 /// 300 virtual bool doFinalization(Function &F) { return false; } 301 302 /// doFinalization - Virtual method overriden by subclasses to do any post 303 /// processing needed after all passes have run. 304 /// 305 virtual bool doFinalization(Module &M) { return false; } 306 307 308 // To run this pass on a function, we simply call runOnBasicBlock once for 309 // each function. 310 // 311 bool runOnFunction(Function &F); 312 313 /// To run directly on the basic block, we initialize, runOnBasicBlock, then 314 /// finalize. 315 /// 316 bool run(BasicBlock &BB); 317 318private: 319 friend class PassManagerT<Function>; 320 friend class PassManagerT<BasicBlock>; 321 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU); 322 virtual void addToPassManager(PassManagerT<BasicBlock> *PM,AnalysisUsage &AU); 323}; 324 325// Include support files that contain important APIs commonly used by Passes, 326// but that we want to separate out to make it easier to read the header files. 327// 328#include "llvm/PassSupport.h" 329#include "llvm/PassAnalysisSupport.h" 330 331#endif 332