Pass.h revision 4445519fab769d36f5a97466f5cfe1c618c44921
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//===----------------------------------------------------------------------===// 17 18#ifndef LLVM_PASS_H 19#define LLVM_PASS_H 20 21#include <vector> 22#include <map> 23class Value; 24class BasicBlock; 25class Function; 26class Module; 27class AnalysisUsage; 28class AnalysisID; 29template<class UnitType> class PassManagerT; 30struct AnalysisResolver; 31 32//===----------------------------------------------------------------------===// 33// Pass interface - Implemented by all 'passes'. Subclass this if you are an 34// interprocedural optimization or you do not fit into any of the more 35// constrained passes described below. 36// 37class Pass { 38 friend class AnalysisResolver; 39 AnalysisResolver *Resolver; // AnalysisResolver this pass is owned by... 40public: 41 inline Pass(AnalysisResolver *AR = 0) : Resolver(AR) {} 42 inline virtual ~Pass() {} // Destructor is virtual so we can be subclassed 43 44 // getPassName - Return a nice clean name for a pass. This should be 45 // overloaded by the pass, but if it is not, C++ RTTI will be consulted to get 46 // a SOMEWHAT intelligable name for the pass. 47 // 48 virtual const char *getPassName() const; 49 50 // run - Run this pass, returning true if a modification was made to the 51 // module argument. This should be implemented by all concrete subclasses. 52 // 53 virtual bool run(Module *M) = 0; 54 55 // getAnalysisUsage - This function should be overriden by passes that need 56 // analysis information to do their job. If a pass specifies that it uses a 57 // particular analysis result to this function, it can then use the 58 // getAnalysis<AnalysisType>() function, below. 59 // 60 virtual void getAnalysisUsage(AnalysisUsage &Info) const { 61 // By default, no analysis results are used, all are invalidated. 62 } 63 64 // releaseMemory() - This member can be implemented by a pass if it wants to 65 // be able to release its memory when it is no longer needed. The default 66 // behavior of passes is to hold onto memory for the entire duration of their 67 // lifetime (which is the entire compile time). For pipelined passes, this 68 // is not a big deal because that memory gets recycled every time the pass is 69 // invoked on another program unit. For IP passes, it is more important to 70 // free memory when it is unused. 71 // 72 // Optionally implement this function to release pass memory when it is no 73 // longer used. 74 // 75 virtual void releaseMemory() {} 76 77 // dumpPassStructure - Implement the -debug-passes=PassStructure option 78 virtual void dumpPassStructure(unsigned Offset = 0); 79 80protected: 81 // getAnalysis<AnalysisType>() - This function is used by subclasses to get to 82 // the analysis information that they claim to use by overriding the 83 // getAnalysisUsage function. 84 // 85 template<typename AnalysisType> 86 AnalysisType &getAnalysis(AnalysisID AID = AnalysisType::ID) { 87 assert(Resolver && "Pass not resident in a PassManager object!"); 88 return *(AnalysisType*)Resolver->getAnalysis(AID); 89 } 90 91 // getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses 92 // to get to the analysis information that might be around that needs to be 93 // updated. This is different than getAnalysis in that it can fail (ie the 94 // analysis results haven't been computed), so should only be used if you 95 // provide the capability to update an analysis that exists. 96 // 97 template<typename AnalysisType> 98 AnalysisType *getAnalysisToUpdate(AnalysisID AID = AnalysisType::ID) { 99 assert(Resolver && "Pass not resident in a PassManager object!"); 100 return (AnalysisType*)Resolver->getAnalysisToUpdate(AID); 101 } 102 103 104private: 105 friend class PassManagerT<Module>; 106 friend class PassManagerT<Function>; 107 friend class PassManagerT<BasicBlock>; 108 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU); 109}; 110 111 112//===----------------------------------------------------------------------===// 113// FunctionPass class - This class is used to implement most global 114// optimizations. Optimizations should subclass this class if they meet the 115// following constraints: 116// 117// 1. Optimizations are organized globally, ie a function at a time 118// 2. Optimizing a function does not cause the addition or removal of any 119// functions in the module 120// 121struct FunctionPass : public Pass { 122 // doInitialization - Virtual method overridden by subclasses to do 123 // any neccesary per-module initialization. 124 // 125 virtual bool doInitialization(Module *M) { return false; } 126 127 // runOnFunction - Virtual method overriden by subclasses to do the 128 // per-function processing of the pass. 129 // 130 virtual bool runOnFunction(Function *F) = 0; 131 132 // doFinalization - Virtual method overriden by subclasses to do any post 133 // processing needed after all passes have run. 134 // 135 virtual bool doFinalization(Module *M) { return false; } 136 137 // run - On a module, we run this pass by initializing, ronOnFunction'ing once 138 // for every function in the module, then by finalizing. 139 // 140 virtual bool run(Module *M); 141 142 // run - On a function, we simply initialize, run the function, then finalize. 143 // 144 bool run(Function *F); 145 146private: 147 friend class PassManagerT<Module>; 148 friend class PassManagerT<Function>; 149 friend class PassManagerT<BasicBlock>; 150 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU); 151 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU); 152}; 153 154 155 156//===----------------------------------------------------------------------===// 157// BasicBlockPass class - This class is used to implement most local 158// optimizations. Optimizations should subclass this class if they 159// meet the following constraints: 160// 1. Optimizations are local, operating on either a basic block or 161// instruction at a time. 162// 2. Optimizations do not modify the CFG of the contained function, or any 163// other basic block in the function. 164// 3. Optimizations conform to all of the contstraints of FunctionPass's. 165// 166struct BasicBlockPass : public FunctionPass { 167 // runOnBasicBlock - Virtual method overriden by subclasses to do the 168 // per-basicblock processing of the pass. 169 // 170 virtual bool runOnBasicBlock(BasicBlock *M) = 0; 171 172 // To run this pass on a function, we simply call runOnBasicBlock once for 173 // each function. 174 // 175 virtual bool runOnFunction(Function *F); 176 177 // To run directly on the basic block, we initialize, runOnBasicBlock, then 178 // finalize. 179 // 180 bool run(BasicBlock *BB); 181 182private: 183 friend class PassManagerT<Function>; 184 friend class PassManagerT<BasicBlock>; 185 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU); 186 virtual void addToPassManager(PassManagerT<BasicBlock> *PM,AnalysisUsage &AU); 187}; 188 189 190// CreatePass - Helper template to invoke the constructor for the AnalysisID 191// class. Note that this should be a template internal to AnalysisID, but 192// GCC 2.95.3 crashes if we do that, doh. 193// 194template<class AnalysisType> 195static Pass *CreatePass(AnalysisID ID) { return new AnalysisType(ID); } 196 197//===----------------------------------------------------------------------===// 198// AnalysisID - This class is used to uniquely identify an analysis pass that 199// is referenced by a transformation. 200// 201class AnalysisID { 202 static unsigned NextID; // Next ID # to deal out... 203 unsigned ID; // Unique ID for this analysis 204 Pass *(*Constructor)(AnalysisID); // Constructor to return the Analysis 205 206 AnalysisID(); // Disable default ctor 207 AnalysisID(unsigned id, Pass *(*Ct)(AnalysisID)) : ID(id), Constructor(Ct) {} 208public: 209 // create - the only way to define a new AnalysisID. This static method is 210 // supposed to be used to define the class static AnalysisID's that are 211 // provided by analysis passes. In the implementation (.cpp) file for the 212 // class, there should be a line that looks like this (using CallGraph as an 213 // example): 214 // 215 // AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>()); 216 // 217 template<class AnalysisType> 218 static AnalysisID create() { 219 return AnalysisID(NextID++, CreatePass<AnalysisType>); 220 } 221 222 // Special Copy Constructor - This is how analysis passes declare that they 223 // only depend on the CFG of the function they are working on, so they are not 224 // invalidated by other passes that do not modify the CFG. This should be 225 // used like this: 226 // AnalysisID DominatorSet::ID(AnalysisID::create<DominatorSet>(), true); 227 // 228 AnalysisID(const AnalysisID &AID, bool DependsOnlyOnCFG = false); 229 230 231 inline Pass *createPass() const { return Constructor(*this); } 232 233 inline bool operator==(const AnalysisID &A) const { 234 return A.ID == ID; 235 } 236 inline bool operator!=(const AnalysisID &A) const { 237 return A.ID != ID; 238 } 239 inline bool operator<(const AnalysisID &A) const { 240 return ID < A.ID; 241 } 242}; 243 244//===----------------------------------------------------------------------===// 245// AnalysisUsage - Represent the analysis usage information of a pass. This 246// tracks analyses that the pass REQUIRES (must available when the pass runs), 247// and analyses that the pass PRESERVES (the pass does not invalidate the 248// results of these analyses). This information is provided by a pass to the 249// Pass infrastructure through the getAnalysisUsage virtual function. 250// 251class AnalysisUsage { 252 // Sets of analyses required and preserved by a pass 253 std::vector<AnalysisID> Required, Preserved, Provided; 254 bool PreservesAll; 255public: 256 AnalysisUsage() : PreservesAll(false) {} 257 258 // addRequires - Add the specified ID to the required set of the usage info 259 // for a pass. 260 // 261 AnalysisUsage &addRequired(AnalysisID ID) { 262 Required.push_back(ID); 263 return *this; 264 } 265 266 // addPreserves - Add the specified ID to the set of analyses preserved by 267 // this pass 268 // 269 AnalysisUsage &addPreserved(AnalysisID ID) { 270 Preserved.push_back(ID); 271 return *this; 272 } 273 274 void addProvided(AnalysisID ID) { 275 Provided.push_back(ID); 276 } 277 278 // PreservesAll - Set by analyses that do not transform their input at all 279 void setPreservesAll() { PreservesAll = true; } 280 bool preservesAll() const { return PreservesAll; } 281 282 // preservesCFG - This function should be called to by the pass, iff they do 283 // not: 284 // 285 // 1. Add or remove basic blocks from the function 286 // 2. Modify terminator instructions in any way. 287 // 288 // This function annotates the AnalysisUsage info object to say that analyses 289 // that only depend on the CFG are preserved by this pass. 290 // 291 void preservesCFG(); 292 293 const std::vector<AnalysisID> &getRequiredSet() const { return Required; } 294 const std::vector<AnalysisID> &getPreservedSet() const { return Preserved; } 295 const std::vector<AnalysisID> &getProvidedSet() const { return Provided; } 296}; 297 298 299 300//===----------------------------------------------------------------------===// 301// AnalysisResolver - Simple interface implemented by PassManagers objects that 302// is used to pull analysis information out of them. 303// 304struct AnalysisResolver { 305 virtual Pass *getAnalysisOrNullUp(AnalysisID ID) const = 0; 306 virtual Pass *getAnalysisOrNullDown(AnalysisID ID) const = 0; 307 Pass *getAnalysis(AnalysisID ID) { 308 Pass *Result = getAnalysisOrNullUp(ID); 309 assert(Result && "Pass has an incorrect analysis uses set!"); 310 return Result; 311 } 312 313 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist 314 Pass *getAnalysisToUpdate(AnalysisID ID) { 315 Pass *Result = getAnalysisOrNullUp(ID); 316 return Result; 317 } 318 319 virtual unsigned getDepth() const = 0; 320 321 virtual void markPassUsed(AnalysisID P, Pass *User) = 0; 322 323 void startPass(Pass *P) {} 324 void endPass(Pass *P) {} 325protected: 326 void setAnalysisResolver(Pass *P, AnalysisResolver *AR); 327}; 328 329#endif 330