include/llvm/Pass.h

   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>
  23 class Value;
  24 class BasicBlock;
  25 class Method;
  26 class Module;
  27 class AnalysisID;
  28 class Pass;
  29 template<class UnitType> class PassManagerT;
  30 struct 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 //
  37 class Pass {
  38   friend class AnalysisResolver;
  39   AnalysisResolver *Resolver;  // AnalysisResolver this pass is owned by...
  40 public:
  41   typedef std::vector<AnalysisID> AnalysisSet;
  42
  43   inline Pass(AnalysisResolver *AR = 0) : Resolver(AR) {}
  44   inline virtual ~Pass() {} // Destructor is virtual so we can be subclassed
  45
  46
  47   // run - Run this pass, returning true if a modification was made to the
  48   // module argument.  This should be implemented by all concrete subclasses.
  49   //
  50   virtual bool run(Module *M) = 0;
  51
  52   // getAnalysisUsageInfo - This function should be overriden by passes that
  53   // need analysis information to do their job.  If a pass specifies that it
  54   // uses a particular analysis result to this function, it can then use the
  55   // getAnalysis<AnalysisType>() function, below.
  56   //
  57   // The Destroyed vector is used to communicate what analyses are invalidated
  58   // by this pass.  This is critical to specify so that the PassManager knows
  59   // which analysis must be rerun after this pass has proceeded.  Analysis are
  60   // only invalidated if run() returns true.
  61   //
  62   // The Provided vector is used for passes that provide analysis information,
  63   // these are the analysis passes themselves.  All analysis passes should
  64   // override this method to return themselves in the provided set.
  65   //
  66   virtual void getAnalysisUsageInfo(AnalysisSet &Required,
  67                                     AnalysisSet &Destroyed,
  68                                     AnalysisSet &Provided) {
  69     // By default, no analysis results are used or destroyed.
  70   }
  71
  72 #ifndef NDEBUG
  73   // dumpPassStructure - Implement the -debug-passes=PassStructure option
  74   virtual void dumpPassStructure(unsigned Offset = 0);
  75 #endif
  76
  77 protected:
  78   // getAnalysis<AnalysisType>() - This function is used by subclasses to get to
  79   // the analysis information that they claim to use by overriding the
  80   // getAnalysisUsageInfo function.
  81   //
  82   template<typename AnalysisType>
  83   AnalysisType &getAnalysis(AnalysisID AID = AnalysisType::ID) {
  84     assert(Resolver && "Pass not resident in a PassManager object!");
  85     return *(AnalysisType*)Resolver->getAnalysis(AID);
  86   }
  87
  88 private:
  89   friend class PassManagerT<Module>;
  90   friend class PassManagerT<Method>;
  91   friend class PassManagerT<BasicBlock>;
  92   virtual void addToPassManager(PassManagerT<Module> *PM,
  93                                 AnalysisSet &Destroyed,
  94                                 AnalysisSet &Provided);
  95 };
  96
  97
  98 //===----------------------------------------------------------------------===//
  99 // MethodPass class - This class is used to implement most global optimizations.
 100 // Optimizations should subclass this class if they meet the following
 101 // constraints:
 102 //  1. Optimizations are organized globally, ie a method at a time
 103 //  2. Optimizing a method does not cause the addition or removal of any methods
 104 //     in the module
 105 //
 106 struct MethodPass : public Pass {
 107   // doInitialization - Virtual method overridden by subclasses to do
 108   // any neccesary per-module initialization.
 109   //
 110   virtual bool doInitialization(Module *M) { return false; }
 111
 112   // runOnMethod - Virtual method overriden by subclasses to do the per-method
 113   // processing of the pass.
 114   //
 115   virtual bool runOnMethod(Method *M) = 0;
 116
 117   // doFinalization - Virtual method overriden by subclasses to do any post
 118   // processing needed after all passes have run.
 119   //
 120   virtual bool doFinalization(Module *M) { return false; }
 121
 122   // run - On a module, we run this pass by initializing, ronOnMethod'ing once
 123   // for every method in the module, then by finalizing.
 124   //
 125   virtual bool run(Module *M);
 126
 127   // run - On a method, we simply initialize, run the method, then finalize.
 128   //
 129   bool run(Method *M);
 130
 131 private:
 132   friend class PassManagerT<Module>;
 133   friend class PassManagerT<Method>;
 134   friend class PassManagerT<BasicBlock>;
 135   virtual void addToPassManager(PassManagerT<Module> *PM,AnalysisSet &Destroyed,
 136                                 AnalysisSet &Provided);
 137   virtual void addToPassManager(PassManagerT<Method> *PM,AnalysisSet &Destroyed,
 138                                 AnalysisSet &Provided);
 139 };
 140
 141
 142
 143 //===----------------------------------------------------------------------===//
 144 // BasicBlockPass class - This class is used to implement most local
 145 // optimizations.  Optimizations should subclass this class if they
 146 // meet the following constraints:
 147 //   1. Optimizations are local, operating on either a basic block or
 148 //      instruction at a time.
 149 //   2. Optimizations do not modify the CFG of the contained method, or any
 150 //      other basic block in the method.
 151 //   3. Optimizations conform to all of the contstraints of MethodPass's.
 152 //
 153 struct BasicBlockPass : public MethodPass {
 154   // runOnBasicBlock - Virtual method overriden by subclasses to do the
 155   // per-basicblock processing of the pass.
 156   //
 157   virtual bool runOnBasicBlock(BasicBlock *M) = 0;
 158
 159   // To run this pass on a method, we simply call runOnBasicBlock once for each
 160   // method.
 161   //
 162   virtual bool runOnMethod(Method *BB);
 163
 164   // To run directly on the basic block, we initialize, runOnBasicBlock, then
 165   // finalize.
 166   //
 167   bool run(BasicBlock *BB);
 168
 169 private:
 170   friend class PassManagerT<Method>;
 171   friend class PassManagerT<BasicBlock>;
 172   virtual void addToPassManager(PassManagerT<Method> *PM,AnalysisSet &Destroyed,
 173                                 AnalysisSet &Provided);
 174   virtual void addToPassManager(PassManagerT<BasicBlock> *PM,
 175                                 AnalysisSet &Destroyed,
 176                                 AnalysisSet &Provided);
 177 };
 178
 179
 180 // CreatePass - Helper template to invoke the constructor for the AnalysisID
 181 // class. Note that this should be a template internal to AnalysisID, but
 182 // GCC 2.95.3 crashes if we do that, doh.
 183 //
 184 template<class AnalysisType>
 185 static Pass *CreatePass(AnalysisID ID) { return new AnalysisType(ID); }
 186
 187 //===----------------------------------------------------------------------===//
 188 // AnalysisID - This class is used to uniquely identify an analysis pass that
 189 //              is referenced by a transformation.
 190 //
 191 class AnalysisID {
 192   static unsigned NextID;               // Next ID # to deal out...
 193   unsigned ID;                          // Unique ID for this analysis
 194   Pass *(*Constructor)(AnalysisID);     // Constructor to return the Analysis
 195
 196   AnalysisID();                         // Disable default ctor
 197   AnalysisID(unsigned id, Pass *(*Ct)(AnalysisID)) : ID(id), Constructor(Ct) {}
 198 public:
 199   // create - the only way to define a new AnalysisID.  This static method is
 200   // supposed to be used to define the class static AnalysisID's that are
 201   // provided by analysis passes.  In the implementation (.cpp) file for the
 202   // class, there should be a line that looks like this (using CallGraph as an
 203   // example):
 204   //
 205   //  AnalysisID CallGraph::ID(AnalysisID::create<CallGraph>());
 206   //
 207   template<class AnalysisType>
 208   static AnalysisID create() {
 209     return AnalysisID(NextID++, CreatePass<AnalysisType>);
 210   }
 211
 212   inline Pass *createPass() const { return Constructor(*this); }
 213
 214   inline bool operator==(const AnalysisID &A) const {
 215     return A.ID == ID;
 216   }
 217   inline bool operator!=(const AnalysisID &A) const {
 218     return A.ID != ID;
 219   }
 220   inline bool operator<(const AnalysisID &A) const {
 221     return ID < A.ID;
 222   }
 223 };
 224
 225
 226 //===----------------------------------------------------------------------===//
 227 // AnalysisResolver - Simple interface implemented by PassManagers objects that
 228 // is used to pull analysis information out of them.
 229 //
 230 struct AnalysisResolver {
 231   virtual Pass *getAnalysisOrNullUp(AnalysisID ID) = 0;
 232   virtual Pass *getAnalysisOrNullDown(AnalysisID ID) = 0;
 233   Pass *getAnalysis(AnalysisID ID) {
 234     Pass *Result = getAnalysisOrNullUp(ID);
 235     assert(Result && "Pass has an incorrect analysis uses set!");
 236     return Result;
 237   }
 238   virtual unsigned getDepth() const = 0;
 239 protected:
 240   void setAnalysisResolver(Pass *P, AnalysisResolver *AR);
 241 };
 242
 243
 244
 245 #endif