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 friend class PassManagerT<Module>;
143 friend class PassManagerT<Function>;
144 friend class PassManagerT<BasicBlock>;
145 virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
146 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
151 //===----------------------------------------------------------------------===//
152 // BasicBlockPass class - This class is used to implement most local
153 // optimizations. Optimizations should subclass this class if they
154 // meet the following constraints:
155 // 1. Optimizations are local, operating on either a basic block or
156 // instruction at a time.
157 // 2. Optimizations do not modify the CFG of the contained function, or any
158 // other basic block in the function.
159 // 3. Optimizations conform to all of the contstraints of FunctionPass's.
161 struct BasicBlockPass : public FunctionPass {
162 // runOnBasicBlock - Virtual method overriden by subclasses to do the
163 // per-basicblock processing of the pass.
165 virtual bool runOnBasicBlock(BasicBlock *M) = 0;
167 // To run this pass on a function, we simply call runOnBasicBlock once for
170 virtual bool runOnFunction(Function *F);
172 // To run directly on the basic block, we initialize, runOnBasicBlock, then
175 bool run(BasicBlock *BB);
178 friend class PassManagerT<Function>;
179 friend class PassManagerT<BasicBlock>;
180 virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
181 virtual void addToPassManager(PassManagerT<BasicBlock> *PM,AnalysisUsage &AU);
185 // CreatePass - Helper template to invoke the constructor for the AnalysisID
186 // class. Note that this should be a template internal to AnalysisID, but
187 // GCC 2.95.3 crashes if we do that, doh.
189 template<class AnalysisType>
190 static Pass *CreatePass(AnalysisID ID) { return new AnalysisType(ID); }
192 //===----------------------------------------------------------------------===//
193 // AnalysisID - This class is used to uniquely identify an analysis pass that
194 // is referenced by a transformation.
197 static unsigned NextID; // Next ID # to deal out...
198 unsigned ID; // Unique ID for this analysis
199 Pass *(*Constructor)(AnalysisID); // Constructor to return the Analysis
201 AnalysisID(); // Disable default ctor
202 AnalysisID(unsigned id, Pass *(*Ct)(AnalysisID)) : ID(id), Constructor(Ct) {}
204 // create - the only way to define a new AnalysisID. This static method is
205 // supposed to be used to define the class static AnalysisID's that are
206 // provided by analysis passes. In the implementation (.cpp) file for the
207 // class, there should be a line that looks like this (using CallGraph as an
210 // AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>());
212 template<class AnalysisType>
213 static AnalysisID create() {
214 return AnalysisID(NextID++, CreatePass<AnalysisType>);
217 inline Pass *createPass() const { return Constructor(*this); }
219 inline bool operator==(const AnalysisID &A) const {
222 inline bool operator!=(const AnalysisID &A) const {
225 inline bool operator<(const AnalysisID &A) const {
230 //===----------------------------------------------------------------------===//
231 // AnalysisUsage - Represent the analysis usage information of a pass. This
232 // tracks analyses that the pass REQUIRES (must available when the pass runs),
233 // and analyses that the pass PRESERVES (the pass does not invalidate the
234 // results of these analyses). This information is provided by a pass to the
235 // Pass infrastructure through the getAnalysisUsage virtual function.
237 class AnalysisUsage {
238 // Sets of analyses required and preserved by a pass
239 std::vector<AnalysisID> Required, Preserved, Provided;
242 AnalysisUsage() : PreservesAll(false) {}
244 // addRequires - Add the specified ID to the required set of the usage info
247 AnalysisUsage &addRequired(AnalysisID ID) {
248 Required.push_back(ID);
252 // addPreserves - Add the specified ID to the set of analyses preserved by
255 AnalysisUsage &addPreserved(AnalysisID ID) {
256 Preserved.push_back(ID);
260 void addProvided(AnalysisID ID) {
261 Provided.push_back(ID);
264 // PreservesAll - Set by analyses that do not transform their input at all
265 void setPreservesAll() { PreservesAll = true; }
266 bool preservesAll() const { return PreservesAll; }
268 // preservesCFG - This function should be called to by the pass, iff they do
271 // 1. Add or remove basic blocks from the function
272 // 2. Modify terminator instructions in any way.
274 // This function annotates the AnalysisUsage info object to say that analyses
275 // that only depend on the CFG are preserved by this pass.
279 const std::vector<AnalysisID> &getRequiredSet() const { return Required; }
280 const std::vector<AnalysisID> &getPreservedSet() const { return Preserved; }
281 const std::vector<AnalysisID> &getProvidedSet() const { return Provided; }
286 //===----------------------------------------------------------------------===//
287 // AnalysisResolver - Simple interface implemented by PassManagers objects that
288 // is used to pull analysis information out of them.
290 struct AnalysisResolver {
291 virtual Pass *getAnalysisOrNullUp(AnalysisID ID) const = 0;
292 virtual Pass *getAnalysisOrNullDown(AnalysisID ID) const = 0;
293 Pass *getAnalysis(AnalysisID ID) {
294 Pass *Result = getAnalysisOrNullUp(ID);
295 assert(Result && "Pass has an incorrect analysis uses set!");
299 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
300 Pass *getAnalysisToUpdate(AnalysisID ID) {
301 Pass *Result = getAnalysisOrNullUp(ID);
305 virtual unsigned getDepth() const = 0;
307 virtual void markPassUsed(AnalysisID P, Pass *User) = 0;
309 void setAnalysisResolver(Pass *P, AnalysisResolver *AR);