include/llvm/Pass.h

   1 //===- llvm/Pass.h - Base class for Passes ----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a base class that indicates that a specified class is a
  11 // transformation pass implementation.
  12 //
  13 // Pass's are designed this way so that it is possible to run passes in a cache
  14 // and organizationally optimal order without having to specify it at the front
  15 // end.  This allows arbitrary passes to be strung together and have them
  16 // executed as effeciently as possible.
  17 //
  18 // Passes should extend one of the classes below, depending on the guarantees
  19 // that it can make about what will be modified as it is run.  For example, most
  20 // global optimizations should derive from FunctionPass, because they do not add
  21 // or delete functions, they operate on the internals of the function.
  22 //
  23 // Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the
  24 // bottom), so the APIs exposed by these files are also automatically available
  25 // to all users of this file.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #ifndef LLVM_PASS_H
  30 #define LLVM_PASS_H
  31
  32 #include <vector>
  33 #include <map>
  34 #include <iosfwd>
  35 #include <typeinfo>
  36 #include <cassert>
  37 class Value;
  38 class BasicBlock;
  39 class Function;
  40 class Module;
  41 class AnalysisUsage;
  42 class PassInfo;
  43 class ImmutablePass;
  44 template<class UnitType> class PassManagerT;
  45 struct AnalysisResolver;
  46
  47 // AnalysisID - Use the PassInfo to identify a pass...
  48 typedef const PassInfo* AnalysisID;
  49
  50 //===----------------------------------------------------------------------===//
  51 /// Pass interface - Implemented by all 'passes'.  Subclass this if you are an
  52 /// interprocedural optimization or you do not fit into any of the more
  53 /// constrained passes described below.
  54 ///
  55 class Pass {
  56   friend class AnalysisResolver;
  57   AnalysisResolver *Resolver;  // AnalysisResolver this pass is owned by...
  58   const PassInfo *PassInfoCache;
  59
  60   // AnalysisImpls - This keeps track of which passes implement the interfaces
  61   // that are required by the current pass (to implement getAnalysis()).
  62   //
  63   std::vector<std::pair<const PassInfo*, Pass*> > AnalysisImpls;
  64
  65   void operator=(const Pass&);  // DO NOT IMPLEMENT
  66   Pass(const Pass &);           // DO NOT IMPLEMENT
  67 public:
  68   Pass() : Resolver(0), PassInfoCache(0) {}
  69   virtual ~Pass() {} // Destructor is virtual so we can be subclassed
  70
  71   /// getPassName - Return a nice clean name for a pass.  This usually
  72   /// implemented in terms of the name that is registered by one of the
  73   /// Registration templates, but can be overloaded directly, and if nothing
  74   /// else is available, C++ RTTI will be consulted to get a SOMEWHAT
  75   /// intelligible name for the pass.
  76   ///
  77   virtual const char *getPassName() const;
  78
  79   /// getPassInfo - Return the PassInfo data structure that corresponds to this
  80   /// pass...  If the pass has not been registered, this will return null.
  81   ///
  82   const PassInfo *getPassInfo() const;
  83
  84   /// run - Run this pass, returning true if a modification was made to the
  85   /// module argument.  This should be implemented by all concrete subclasses.
  86   ///
  87   virtual bool run(Module &M) = 0;
  88
  89   /// print - Print out the internal state of the pass.  This is called by
  90   /// Analyze to print out the contents of an analysis.  Otherwise it is not
  91   /// necessary to implement this method.  Beware that the module pointer MAY be
  92   /// null.  This automatically forwards to a virtual function that does not
  93   /// provide the Module* in case the analysis doesn't need it it can just be
  94   /// ignored.
  95   ///
  96   virtual void print(std::ostream &O, const Module *M) const { print(O); }
  97   virtual void print(std::ostream &O) const;
  98   void dump() const; // dump - call print(std::cerr, 0);
  99
 100
 101   /// getAnalysisUsage - This function should be overriden by passes that need
 102   /// analysis information to do their job.  If a pass specifies that it uses a
 103   /// particular analysis result to this function, it can then use the
 104   /// getAnalysis<AnalysisType>() function, below.
 105   ///
 106   virtual void getAnalysisUsage(AnalysisUsage &Info) const {
 107     // By default, no analysis results are used, all are invalidated.
 108   }
 109
 110   /// releaseMemory() - This member can be implemented by a pass if it wants to
 111   /// be able to release its memory when it is no longer needed.  The default
 112   /// behavior of passes is to hold onto memory for the entire duration of their
 113   /// lifetime (which is the entire compile time).  For pipelined passes, this
 114   /// is not a big deal because that memory gets recycled every time the pass is
 115   /// invoked on another program unit.  For IP passes, it is more important to
 116   /// free memory when it is unused.
 117   ///
 118   /// Optionally implement this function to release pass memory when it is no
 119   /// longer used.
 120   ///
 121   virtual void releaseMemory() {}
 122
 123   // dumpPassStructure - Implement the -debug-passes=PassStructure option
 124   virtual void dumpPassStructure(unsigned Offset = 0);
 125
 126
 127   // getPassInfo - Static method to get the pass information from a class name.
 128   template<typename AnalysisClass>
 129   static const PassInfo *getClassPassInfo() {
 130     return lookupPassInfo(typeid(AnalysisClass));
 131   }
 132
 133   // lookupPassInfo - Return the pass info object for the specified pass class,
 134   // or null if it is not known.
 135   static const PassInfo *lookupPassInfo(const std::type_info &TI);
 136
 137   /// getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses
 138   /// to get to the analysis information that might be around that needs to be
 139   /// updated.  This is different than getAnalysis in that it can fail (ie the
 140   /// analysis results haven't been computed), so should only be used if you
 141   /// provide the capability to update an analysis that exists.  This method is
 142   /// often used by transformation APIs to update analysis results for a pass
 143   /// automatically as the transform is performed.
 144   ///
 145   template<typename AnalysisType>
 146   AnalysisType *getAnalysisToUpdate() const; // Defined in PassAnalysisSupport.h
 147
 148   /// mustPreserveAnalysisID - This method serves the same function as
 149   /// getAnalysisToUpdate, but works if you just have an AnalysisID.  This
 150   /// obviously cannot give you a properly typed instance of the class if you
 151   /// don't have the class name available (use getAnalysisToUpdate if you do),
 152   /// but it can tell you if you need to preserve the pass at least.
 153   ///
 154   bool mustPreserveAnalysisID(const PassInfo *AnalysisID) const;
 155
 156   /// getAnalysis<AnalysisType>() - This function is used by subclasses to get
 157   /// to the analysis information that they claim to use by overriding the
 158   /// getAnalysisUsage function.
 159   ///
 160   template<typename AnalysisType>
 161   AnalysisType &getAnalysis() const {
 162     assert(Resolver && "Pass has not been inserted into a PassManager object!");
 163     const PassInfo *PI = getClassPassInfo<AnalysisType>();
 164     return getAnalysisID<AnalysisType>(PI);
 165   }
 166
 167   template<typename AnalysisType>
 168   AnalysisType &getAnalysisID(const PassInfo *PI) const {
 169     assert(Resolver && "Pass has not been inserted into a PassManager object!");
 170     assert(PI && "getAnalysis for unregistered pass!");
 171
 172     // PI *must* appear in AnalysisImpls.  Because the number of passes used
 173     // should be a small number, we just do a linear search over a (dense)
 174     // vector.
 175     Pass *ResultPass = 0;
 176     for (unsigned i = 0; ; ++i) {
 177       assert(i != AnalysisImpls.size() &&
 178              "getAnalysis*() called on an analysis that we not "
 179              "'required' by pass!");
 180       if (AnalysisImpls[i].first == PI) {
 181         ResultPass = AnalysisImpls[i].second;
 182         break;
 183       }
 184     }
 185
 186     // Because the AnalysisType may not be a subclass of pass (for
 187     // AnalysisGroups), we must use dynamic_cast here to potentially adjust the
 188     // return pointer (because the class may multiply inherit, once from pass,
 189     // once from AnalysisType).
 190     //
 191     AnalysisType *Result = dynamic_cast<AnalysisType*>(ResultPass);
 192     assert(Result && "Pass does not implement interface required!");
 193     return *Result;
 194   }
 195
 196 private:
 197   friend class PassManagerT<Module>;
 198   friend class PassManagerT<Function>;
 199   friend class PassManagerT<BasicBlock>;
 200   virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
 201 };
 202
 203 inline std::ostream &operator<<(std::ostream &OS, const Pass &P) {
 204   P.print(OS, 0); return OS;
 205 }
 206
 207
 208
 209 //===----------------------------------------------------------------------===//
 210 /// ImmutablePass class - This class is used to provide information that does
 211 /// not need to be run.  This is useful for things like target information and
 212 /// "basic" versions of AnalysisGroups.
 213 ///
 214 struct ImmutablePass : public Pass {
 215   /// initializePass - This method may be overriden by immutable passes to allow
 216   /// them to perform various initialization actions they require.  This is
 217   /// primarily because an ImmutablePass can "require" another ImmutablePass,
 218   /// and if it does, the overloaded version of initializePass may get access to
 219   /// these passes with getAnalysis<>.
 220   ///
 221   virtual void initializePass() {}
 222
 223   /// ImmutablePasses are never run.
 224   ///
 225   virtual bool run(Module &M) { return false; }
 226
 227 private:
 228   friend class PassManagerT<Module>;
 229   virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
 230 };
 231
 232
 233 //===----------------------------------------------------------------------===//
 234 /// FunctionPass class - This class is used to implement most global
 235 /// optimizations.  Optimizations should subclass this class if they meet the
 236 /// following constraints:
 237 ///
 238 ///  1. Optimizations are organized globally, i.e., a function at a time
 239 ///  2. Optimizing a function does not cause the addition or removal of any
 240 ///     functions in the module
 241 ///
 242 struct FunctionPass : public Pass {
 243   /// doInitialization - Virtual method overridden by subclasses to do
 244   /// any necessary per-module initialization.
 245   ///
 246   virtual bool doInitialization(Module &M) { return false; }
 247
 248   /// runOnFunction - Virtual method overriden by subclasses to do the
 249   /// per-function processing of the pass.
 250   ///
 251   virtual bool runOnFunction(Function &F) = 0;
 252
 253   /// doFinalization - Virtual method overriden by subclasses to do any post
 254   /// processing needed after all passes have run.
 255   ///
 256   virtual bool doFinalization(Module &M) { return false; }
 257
 258   /// run - On a module, we run this pass by initializing, ronOnFunction'ing
 259   /// once for every function in the module, then by finalizing.
 260   ///
 261   virtual bool run(Module &M);
 262
 263   /// run - On a function, we simply initialize, run the function, then
 264   /// finalize.
 265   ///
 266   bool run(Function &F);
 267
 268 private:
 269   friend class PassManagerT<Module>;
 270   friend class PassManagerT<Function>;
 271   friend class PassManagerT<BasicBlock>;
 272   virtual void addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU);
 273   virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
 274 };
 275
 276
 277
 278 //===----------------------------------------------------------------------===//
 279 /// BasicBlockPass class - This class is used to implement most local
 280 /// optimizations.  Optimizations should subclass this class if they
 281 /// meet the following constraints:
 282 ///   1. Optimizations are local, operating on either a basic block or
 283 ///      instruction at a time.
 284 ///   2. Optimizations do not modify the CFG of the contained function, or any
 285 ///      other basic block in the function.
 286 ///   3. Optimizations conform to all of the constraints of FunctionPass's.
 287 ///
 288 struct BasicBlockPass : public FunctionPass {
 289   /// doInitialization - Virtual method overridden by subclasses to do
 290   /// any necessary per-module initialization.
 291   ///
 292   virtual bool doInitialization(Module &M) { return false; }
 293
 294   /// doInitialization - Virtual method overridden by BasicBlockPass subclasses
 295   /// to do any necessary per-function initialization.
 296   ///
 297   virtual bool doInitialization(Function &F) { return false; }
 298
 299   /// runOnBasicBlock - Virtual method overriden by subclasses to do the
 300   /// per-basicblock processing of the pass.
 301   ///
 302   virtual bool runOnBasicBlock(BasicBlock &BB) = 0;
 303
 304   /// doFinalization - Virtual method overriden by BasicBlockPass subclasses to
 305   /// do any post processing needed after all passes have run.
 306   ///
 307   virtual bool doFinalization(Function &F) { return false; }
 308
 309   /// doFinalization - Virtual method overriden by subclasses to do any post
 310   /// processing needed after all passes have run.
 311   ///
 312   virtual bool doFinalization(Module &M) { return false; }
 313
 314
 315   // To run this pass on a function, we simply call runOnBasicBlock once for
 316   // each function.
 317   //
 318   bool runOnFunction(Function &F);
 319
 320   /// To run directly on the basic block, we initialize, runOnBasicBlock, then
 321   /// finalize.
 322   ///
 323   bool run(BasicBlock &BB);
 324
 325 private:
 326   friend class PassManagerT<Function>;
 327   friend class PassManagerT<BasicBlock>;
 328   virtual void addToPassManager(PassManagerT<Function> *PM, AnalysisUsage &AU);
 329   virtual void addToPassManager(PassManagerT<BasicBlock> *PM,AnalysisUsage &AU);
 330 };
 331
 332 // Include support files that contain important APIs commonly used by Passes,
 333 // but that we want to separate out to make it easier to read the header files.
 334 //
 335 #include "llvm/PassSupport.h"
 336 #include "llvm/PassAnalysisSupport.h"
 337
 338 #endif