Pass.h revision 6fe2e871bb7c5c5eeebc6aad43002b8aa22c23b4
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 MethodPass, because they do not add 14// or delete methods, they operate on the internals of the method. 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 AnalysisID; 28class Pass; 29template<class UnitType> class PassManagerT; 30struct AnalysisResolver; 31 32// PassManager - Top level PassManagerT instantiation intended to be used. 33// Implemented in PassManager.h 34typedef PassManagerT<Module> PassManager; 35 36 37//===----------------------------------------------------------------------===// 38// Pass interface - Implemented by all 'passes'. Subclass this if you are an 39// interprocedural optimization or you do not fit into any of the more 40// constrained passes described below. 41// 42class Pass { 43 friend class AnalysisResolver; 44 AnalysisResolver *Resolver; // AnalysisResolver this pass is owned by... 45public: 46 typedef std::vector<AnalysisID> AnalysisSet; 47 48 inline Pass(AnalysisResolver *AR = 0) : Resolver(AR) {} 49 inline virtual ~Pass() {} // Destructor is virtual so we can be subclassed 50 51 52 // run - Run this pass, returning true if a modification was made to the 53 // module argument. This should be implemented by all concrete subclasses. 54 // 55 virtual bool run(Module *M) = 0; 56 57 // getAnalysisUsageInfo - This function should be overriden by passes that 58 // need analysis information to do their job. If a pass specifies that it 59 // uses a particular analysis result to this function, it can then use the 60 // getAnalysis<AnalysisType>() function, below. 61 // 62 // The Destroyed vector is used to communicate what analyses are invalidated 63 // by this pass. This is critical to specify so that the PassManager knows 64 // which analysis must be rerun after this pass has proceeded. Analysis are 65 // only invalidated if run() returns true. 66 // 67 // The Provided vector is used for passes that provide analysis information, 68 // these are the analysis passes themselves. All analysis passes should 69 // override this method to return themselves in the provided set. 70 // 71 virtual void getAnalysisUsageInfo(AnalysisSet &Required, 72 AnalysisSet &Destroyed, 73 AnalysisSet &Provided) { 74 // By default, no analysis results are used or destroyed. 75 } 76 77 // releaseMemory() - This member can be implemented by a pass if it wants to 78 // be able to release its memory when it is no longer needed. The default 79 // behavior of passes is to hold onto memory for the entire duration of their 80 // lifetime (which is the entire compile time). For pipelined passes, this 81 // is not a big deal because that memory gets recycled every time the pass is 82 // invoked on another program unit. For IP passes, it is more important to 83 // free memory when it is unused. 84 // 85 // Optionally implement this function to release pass memory when it is no 86 // longer used. 87 // 88 virtual void releaseMemory() {} 89 90 // dumpPassStructure - Implement the -debug-passes=PassStructure option 91 virtual void dumpPassStructure(unsigned Offset = 0); 92 93protected: 94 // getAnalysis<AnalysisType>() - This function is used by subclasses to get to 95 // the analysis information that they claim to use by overriding the 96 // getAnalysisUsageInfo function. 97 // 98 template<typename AnalysisType> 99 AnalysisType &getAnalysis(AnalysisID AID = AnalysisType::ID) { 100 assert(Resolver && "Pass not resident in a PassManager object!"); 101 return *(AnalysisType*)Resolver->getAnalysis(AID); 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, AnalysisSet &Req, 109 AnalysisSet &Destroyed, AnalysisSet &Provided); 110}; 111 112 113//===----------------------------------------------------------------------===// 114// MethodPass class - This class is used to implement most global optimizations. 115// Optimizations should subclass this class if they meet the following 116// constraints: 117// 1. Optimizations are organized globally, ie a method at a time 118// 2. Optimizing a method does not cause the addition or removal of any methods 119// in the module 120// 121struct MethodPass : 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 // runOnMethod - Virtual method overriden by subclasses to do the per-method 128 // processing of the pass. 129 // 130 virtual bool runOnMethod(Function *M) = 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, ronOnMethod'ing once 138 // for every method in the module, then by finalizing. 139 // 140 virtual bool run(Module *M); 141 142 // run - On a method, we simply initialize, run the method, then finalize. 143 // 144 bool run(Function *M); 145 146private: 147 friend class PassManagerT<Module>; 148 friend class PassManagerT<Function>; 149 friend class PassManagerT<BasicBlock>; 150 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisSet &Req, 151 AnalysisSet &Dest, AnalysisSet &Prov); 152 virtual void addToPassManager(PassManagerT<Function> *PM,AnalysisSet &Req, 153 AnalysisSet &Dest, AnalysisSet &Prov); 154}; 155 156 157 158//===----------------------------------------------------------------------===// 159// BasicBlockPass class - This class is used to implement most local 160// optimizations. Optimizations should subclass this class if they 161// meet the following constraints: 162// 1. Optimizations are local, operating on either a basic block or 163// instruction at a time. 164// 2. Optimizations do not modify the CFG of the contained method, or any 165// other basic block in the method. 166// 3. Optimizations conform to all of the contstraints of MethodPass's. 167// 168struct BasicBlockPass : public MethodPass { 169 // runOnBasicBlock - Virtual method overriden by subclasses to do the 170 // per-basicblock processing of the pass. 171 // 172 virtual bool runOnBasicBlock(BasicBlock *M) = 0; 173 174 // To run this pass on a method, we simply call runOnBasicBlock once for each 175 // method. 176 // 177 virtual bool runOnMethod(Function *F); 178 179 // To run directly on the basic block, we initialize, runOnBasicBlock, then 180 // finalize. 181 // 182 bool run(BasicBlock *BB); 183 184private: 185 friend class PassManagerT<Function>; 186 friend class PassManagerT<BasicBlock>; 187 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisSet &, 188 AnalysisSet &, AnalysisSet &); 189 virtual void addToPassManager(PassManagerT<BasicBlock> *PM, AnalysisSet &, 190 AnalysisSet &, AnalysisSet &); 191}; 192 193 194// CreatePass - Helper template to invoke the constructor for the AnalysisID 195// class. Note that this should be a template internal to AnalysisID, but 196// GCC 2.95.3 crashes if we do that, doh. 197// 198template<class AnalysisType> 199static Pass *CreatePass(AnalysisID ID) { return new AnalysisType(ID); } 200 201//===----------------------------------------------------------------------===// 202// AnalysisID - This class is used to uniquely identify an analysis pass that 203// is referenced by a transformation. 204// 205class AnalysisID { 206 static unsigned NextID; // Next ID # to deal out... 207 unsigned ID; // Unique ID for this analysis 208 Pass *(*Constructor)(AnalysisID); // Constructor to return the Analysis 209 210 AnalysisID(); // Disable default ctor 211 AnalysisID(unsigned id, Pass *(*Ct)(AnalysisID)) : ID(id), Constructor(Ct) {} 212public: 213 // create - the only way to define a new AnalysisID. This static method is 214 // supposed to be used to define the class static AnalysisID's that are 215 // provided by analysis passes. In the implementation (.cpp) file for the 216 // class, there should be a line that looks like this (using CallGraph as an 217 // example): 218 // 219 // AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>()); 220 // 221 template<class AnalysisType> 222 static AnalysisID create() { 223 return AnalysisID(NextID++, CreatePass<AnalysisType>); 224 } 225 226 inline Pass *createPass() const { return Constructor(*this); } 227 228 inline bool operator==(const AnalysisID &A) const { 229 return A.ID == ID; 230 } 231 inline bool operator!=(const AnalysisID &A) const { 232 return A.ID != ID; 233 } 234 inline bool operator<(const AnalysisID &A) const { 235 return ID < A.ID; 236 } 237}; 238 239 240//===----------------------------------------------------------------------===// 241// AnalysisResolver - Simple interface implemented by PassManagers objects that 242// is used to pull analysis information out of them. 243// 244struct AnalysisResolver { 245 virtual Pass *getAnalysisOrNullUp(AnalysisID ID) const = 0; 246 virtual Pass *getAnalysisOrNullDown(AnalysisID ID) const = 0; 247 Pass *getAnalysis(AnalysisID ID) { 248 Pass *Result = getAnalysisOrNullUp(ID); 249 assert(Result && "Pass has an incorrect analysis uses set!"); 250 return Result; 251 } 252 virtual unsigned getDepth() const = 0; 253 254 virtual void markPassUsed(AnalysisID P, Pass *User) = 0; 255protected: 256 void setAnalysisResolver(Pass *P, AnalysisResolver *AR); 257}; 258 259 260 261#endif 262