1 //===- llvm/Pass.h - Base class for XForm Passes -----------------*- C++ -*--=//
3 // This file defines a base class that indicates that a specified class is a
4 // transformation pass implementation.
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.
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.
16 //===----------------------------------------------------------------------===//
29 template<class UnitType> class PassManagerT;
30 struct AnalysisResolver;
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.
38 friend class AnalysisResolver;
39 AnalysisResolver *Resolver; // AnalysisResolver this pass is owned by...
41 inline Pass(AnalysisResolver *AR = 0) : Resolver(AR) {}
42 inline virtual ~Pass() {} // Destructor is virtual so we can be subclassed
45 // run - Run this pass, returning true if a modification was made to the
46 // module argument. This should be implemented by all concrete subclasses.
48 virtual bool run(Module *M) = 0;
50 // getAnalysisUsage - This function should be overriden by passes that need
51 // analysis information to do their job. If a pass specifies that it uses a
52 // particular analysis result to this function, it can then use the
53 // getAnalysis<AnalysisType>() function, below.
55 virtual void getAnalysisUsage(AnalysisUsage &Info) const {
56 // By default, no analysis results are used, all are invalidated.
59 // releaseMemory() - This member can be implemented by a pass if it wants to
60 // be able to release its memory when it is no longer needed. The default
61 // behavior of passes is to hold onto memory for the entire duration of their
62 // lifetime (which is the entire compile time). For pipelined passes, this
63 // is not a big deal because that memory gets recycled every time the pass is
64 // invoked on another program unit. For IP passes, it is more important to
65 // free memory when it is unused.
67 // Optionally implement this function to release pass memory when it is no
70 virtual void releaseMemory() {}
72 // dumpPassStructure - Implement the -debug-passes=PassStructure option
73 virtual void dumpPassStructure(unsigned Offset = 0);
76 // getAnalysis<AnalysisType>() - This function is used by subclasses to get to
77 // the analysis information that they claim to use by overriding the
78 // getAnalysisUsage function.
80 template<typename AnalysisType>
81 AnalysisType &getAnalysis(AnalysisID AID = AnalysisType::ID) {
82 assert(Resolver && "Pass not resident in a PassManager object!");
83 return *(AnalysisType*)Resolver->getAnalysis(AID);
86 // getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses
87 // to get to the analysis information that might be around that needs to be
88 // updated. This is different than getAnalysis in that it can fail (ie the
89 // analysis results haven't been computed), so should only be used if you
90 // provide the capability to update an analysis that exists.
92 template<typename AnalysisType>
93 AnalysisType *getAnalysisToUpdate(AnalysisID AID = AnalysisType::ID) {
94 assert(Resolver && "Pass not resident in a PassManager object!");
95 return (AnalysisType*)Resolver->getAnalysisToUpdate(AID);
100 friend class PassManagerT<Module>;
101 friend class PassManagerT<Function>;
102 friend class PassManagerT<BasicBlock>;
103 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
107 //===----------------------------------------------------------------------===//
108 // FunctionPass class - This class is used to implement most global
109 // optimizations. Optimizations should subclass this class if they meet the
110 // following constraints:
112 // 1. Optimizations are organized globally, ie a function at a time
113 // 2. Optimizing a function does not cause the addition or removal of any
114 // functions in the module
116 struct FunctionPass : public Pass {
117 // doInitialization - Virtual method overridden by subclasses to do
118 // any neccesary per-module initialization.
120 virtual bool doInitialization(Module *M) { return false; }
122 // runOnFunction - Virtual method overriden by subclasses to do the
123 // per-function processing of the pass.
125 virtual bool runOnFunction(Function *F) = 0;
127 // doFinalization - Virtual method overriden by subclasses to do any post
128 // processing needed after all passes have run.
130 virtual bool doFinalization(Module *M) { return false; }
132 // run - On a module, we run this pass by initializing, ronOnFunction'ing once
133 // for every function in the module, then by finalizing.
135 virtual bool run(Module *M);
137 // run - On a function, we simply initialize, run the function, then finalize.
139 bool run(Function *F);
142 // doesNotModifyCFG - This function should be called by our subclasses to
143 // implement the getAnalysisUsage virtual function, iff they do not:
145 // 1. Add or remove basic blocks from the function
146 // 2. Modify terminator instructions in any way.
148 // This function annotates the AnalysisUsage info object to say that analyses
149 // that only depend on the CFG are preserved by this pass.
151 void doesNotModifyCFG(AnalysisUsage &Info);
154 friend class PassManagerT<Module>;
155 friend class PassManagerT<Function>;
156 friend class PassManagerT<BasicBlock>;
157 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
158 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
163 //===----------------------------------------------------------------------===//
164 // BasicBlockPass class - This class is used to implement most local
165 // optimizations. Optimizations should subclass this class if they
166 // meet the following constraints:
167 // 1. Optimizations are local, operating on either a basic block or
168 // instruction at a time.
169 // 2. Optimizations do not modify the CFG of the contained function, or any
170 // other basic block in the function.
171 // 3. Optimizations conform to all of the contstraints of FunctionPass's.
173 struct BasicBlockPass : public FunctionPass {
174 // runOnBasicBlock - Virtual method overriden by subclasses to do the
175 // per-basicblock processing of the pass.
177 virtual bool runOnBasicBlock(BasicBlock *M) = 0;
179 // To run this pass on a function, we simply call runOnBasicBlock once for
182 virtual bool runOnFunction(Function *F);
184 // To run directly on the basic block, we initialize, runOnBasicBlock, then
187 bool run(BasicBlock *BB);
190 friend class PassManagerT<Function>;
191 friend class PassManagerT<BasicBlock>;
192 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
193 virtual void addToPassManager(PassManagerT<BasicBlock> *PM,AnalysisUsage &AU);
197 // CreatePass - Helper template to invoke the constructor for the AnalysisID
198 // class. Note that this should be a template internal to AnalysisID, but
199 // GCC 2.95.3 crashes if we do that, doh.
201 template<class AnalysisType>
202 static Pass *CreatePass(AnalysisID ID) { return new AnalysisType(ID); }
204 //===----------------------------------------------------------------------===//
205 // AnalysisID - This class is used to uniquely identify an analysis pass that
206 // is referenced by a transformation.
209 static unsigned NextID; // Next ID # to deal out...
210 unsigned ID; // Unique ID for this analysis
211 Pass *(*Constructor)(AnalysisID); // Constructor to return the Analysis
213 AnalysisID(); // Disable default ctor
214 AnalysisID(unsigned id, Pass *(*Ct)(AnalysisID)) : ID(id), Constructor(Ct) {}
216 // create - the only way to define a new AnalysisID. This static method is
217 // supposed to be used to define the class static AnalysisID's that are
218 // provided by analysis passes. In the implementation (.cpp) file for the
219 // class, there should be a line that looks like this (using CallGraph as an
222 // AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>());
224 template<class AnalysisType>
225 static AnalysisID create() {
226 return AnalysisID(NextID++, CreatePass<AnalysisType>);
229 inline Pass *createPass() const { return Constructor(*this); }
231 inline bool operator==(const AnalysisID &A) const {
234 inline bool operator!=(const AnalysisID &A) const {
237 inline bool operator<(const AnalysisID &A) const {
242 //===----------------------------------------------------------------------===//
243 // AnalysisUsage - Represent the analysis usage information of a pass. This
244 // tracks analyses that the pass REQUIRES (must available when the pass runs),
245 // and analyses that the pass PRESERVES (the pass does not invalidate the
246 // results of these analyses). This information is provided by a pass to the
247 // Pass infrastructure through the getAnalysisUsage virtual function.
249 class AnalysisUsage {
250 // Sets of analyses required and preserved by a pass
251 std::vector<AnalysisID> Required, Preserved, Provided;
254 AnalysisUsage() : PreservesAll(false) {}
256 // addRequires - Add the specified ID to the required set of the usage info
259 AnalysisUsage &addRequired(AnalysisID ID) {
260 Required.push_back(ID);
264 // addPreserves - Add the specified ID to the set of analyses preserved by
267 AnalysisUsage &addPreserved(AnalysisID ID) {
268 Preserved.push_back(ID);
272 void addProvided(AnalysisID ID) {
273 Provided.push_back(ID);
276 // PreservesAll - Set by analyses that do not transform their input at all
277 void setPreservesAll() { PreservesAll = true; }
278 bool preservesAll() const { return PreservesAll; }
280 const std::vector<AnalysisID> &getRequiredSet() const { return Required; }
281 const std::vector<AnalysisID> &getPreservedSet() const { return Preserved; }
282 const std::vector<AnalysisID> &getProvidedSet() const { return Provided; }
287 //===----------------------------------------------------------------------===//
288 // AnalysisResolver - Simple interface implemented by PassManagers objects that
289 // is used to pull analysis information out of them.
291 struct AnalysisResolver {
292 virtual Pass *getAnalysisOrNullUp(AnalysisID ID) const = 0;
293 virtual Pass *getAnalysisOrNullDown(AnalysisID ID) const = 0;
294 Pass *getAnalysis(AnalysisID ID) {
295 Pass *Result = getAnalysisOrNullUp(ID);
296 assert(Result && "Pass has an incorrect analysis uses set!");
300 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
301 Pass *getAnalysisToUpdate(AnalysisID ID) {
302 Pass *Result = getAnalysisOrNullUp(ID);
306 virtual unsigned getDepth() const = 0;
308 virtual void markPassUsed(AnalysisID P, Pass *User) = 0;
310 void setAnalysisResolver(Pass *P, AnalysisResolver *AR);