LLVM API Documentation

Pass.h

Go to the documentation of this file.
00001 //===- llvm/Pass.h - Base class for Passes ----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines a base class that indicates that a specified class is a
00011 // transformation pass implementation.
00012 //
00013 // Passes are designed this way so that it is possible to run passes in a cache
00014 // and organizationally optimal order without having to specify it at the front
00015 // end.  This allows arbitrary passes to be strung together and have them
00016 // executed as effeciently as possible.
00017 //
00018 // Passes should extend one of the classes below, depending on the guarantees
00019 // that it can make about what will be modified as it is run.  For example, most
00020 // global optimizations should derive from FunctionPass, because they do not add
00021 // or delete functions, they operate on the internals of the function.
00022 //
00023 // Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the
00024 // bottom), so the APIs exposed by these files are also automatically available
00025 // to all users of this file.
00026 //
00027 //===----------------------------------------------------------------------===//
00028 
00029 #ifndef LLVM_PASS_H
00030 #define LLVM_PASS_H
00031 
00032 #include <vector>
00033 #include <map>
00034 #include <iosfwd>
00035 #include <typeinfo>
00036 #include <cassert>
00037 
00038 namespace llvm {
00039 
00040 class Value;
00041 class BasicBlock;
00042 class Function;
00043 class Module;
00044 class AnalysisUsage;
00045 class PassInfo;
00046 class ImmutablePass;
00047 template<class Trait> class PassManagerT;
00048 class BasicBlockPassManager;
00049 class FunctionPassManagerT;
00050 class ModulePassManager;
00051 struct AnalysisResolver;
00052 
00053 // AnalysisID - Use the PassInfo to identify a pass...
00054 typedef const PassInfo* AnalysisID;
00055 
00056 //===----------------------------------------------------------------------===//
00057 /// Pass interface - Implemented by all 'passes'.  Subclass this if you are an
00058 /// interprocedural optimization or you do not fit into any of the more
00059 /// constrained passes described below.
00060 ///
00061 class Pass {
00062   friend struct AnalysisResolver;
00063   AnalysisResolver *Resolver;  // AnalysisResolver this pass is owned by...
00064   const PassInfo *PassInfoCache;
00065 
00066   // AnalysisImpls - This keeps track of which passes implement the interfaces
00067   // that are required by the current pass (to implement getAnalysis()).
00068   //
00069   std::vector<std::pair<const PassInfo*, Pass*> > AnalysisImpls;
00070 
00071   void operator=(const Pass&);  // DO NOT IMPLEMENT
00072   Pass(const Pass &);           // DO NOT IMPLEMENT
00073 public:
00074   Pass() : Resolver(0), PassInfoCache(0) {}
00075   virtual ~Pass() {} // Destructor is virtual so we can be subclassed
00076 
00077   /// getPassName - Return a nice clean name for a pass.  This usually
00078   /// implemented in terms of the name that is registered by one of the
00079   /// Registration templates, but can be overloaded directly, and if nothing
00080   /// else is available, C++ RTTI will be consulted to get a SOMEWHAT
00081   /// intelligible name for the pass.
00082   ///
00083   virtual const char *getPassName() const;
00084 
00085   /// getPassInfo - Return the PassInfo data structure that corresponds to this
00086   /// pass...  If the pass has not been registered, this will return null.
00087   ///
00088   const PassInfo *getPassInfo() const;
00089 
00090   /// runPass - Run this pass, returning true if a modification was made to the
00091   /// module argument.  This should be implemented by all concrete subclasses.
00092   ///
00093   virtual bool runPass(Module &M) { return false; }
00094   virtual bool runPass(BasicBlock&) { return false; }
00095 
00096   /// print - Print out the internal state of the pass.  This is called by
00097   /// Analyze to print out the contents of an analysis.  Otherwise it is not
00098   /// necessary to implement this method.  Beware that the module pointer MAY be
00099   /// null.  This automatically forwards to a virtual function that does not
00100   /// provide the Module* in case the analysis doesn't need it it can just be
00101   /// ignored.
00102   ///
00103   virtual void print(std::ostream &O, const Module *M) const;
00104   void dump() const; // dump - call print(std::cerr, 0);
00105 
00106 
00107   /// getAnalysisUsage - This function should be overriden by passes that need
00108   /// analysis information to do their job.  If a pass specifies that it uses a
00109   /// particular analysis result to this function, it can then use the
00110   /// getAnalysis<AnalysisType>() function, below.
00111   ///
00112   virtual void getAnalysisUsage(AnalysisUsage &Info) const {
00113     // By default, no analysis results are used, all are invalidated.
00114   }
00115 
00116   /// releaseMemory() - This member can be implemented by a pass if it wants to
00117   /// be able to release its memory when it is no longer needed.  The default
00118   /// behavior of passes is to hold onto memory for the entire duration of their
00119   /// lifetime (which is the entire compile time).  For pipelined passes, this
00120   /// is not a big deal because that memory gets recycled every time the pass is
00121   /// invoked on another program unit.  For IP passes, it is more important to
00122   /// free memory when it is unused.
00123   ///
00124   /// Optionally implement this function to release pass memory when it is no
00125   /// longer used.
00126   ///
00127   virtual void releaseMemory() {}
00128 
00129   // dumpPassStructure - Implement the -debug-passes=PassStructure option
00130   virtual void dumpPassStructure(unsigned Offset = 0);
00131 
00132 
00133   // getPassInfo - Static method to get the pass information from a class name.
00134   template<typename AnalysisClass>
00135   static const PassInfo *getClassPassInfo() {
00136     return lookupPassInfo(typeid(AnalysisClass));
00137   }
00138 
00139   // lookupPassInfo - Return the pass info object for the specified pass class,
00140   // or null if it is not known.
00141   static const PassInfo *lookupPassInfo(const std::type_info &TI);
00142 
00143   /// getAnalysisToUpdate<AnalysisType>() - This function is used by subclasses
00144   /// to get to the analysis information that might be around that needs to be
00145   /// updated.  This is different than getAnalysis in that it can fail (ie the
00146   /// analysis results haven't been computed), so should only be used if you
00147   /// provide the capability to update an analysis that exists.  This method is
00148   /// often used by transformation APIs to update analysis results for a pass
00149   /// automatically as the transform is performed.
00150   ///
00151   template<typename AnalysisType>
00152   AnalysisType *getAnalysisToUpdate() const; // Defined in PassAnalysisSupport.h
00153 
00154   /// mustPreserveAnalysisID - This method serves the same function as
00155   /// getAnalysisToUpdate, but works if you just have an AnalysisID.  This
00156   /// obviously cannot give you a properly typed instance of the class if you
00157   /// don't have the class name available (use getAnalysisToUpdate if you do),
00158   /// but it can tell you if you need to preserve the pass at least.
00159   ///
00160   bool mustPreserveAnalysisID(const PassInfo *AnalysisID) const;
00161 
00162   /// getAnalysis<AnalysisType>() - This function is used by subclasses to get
00163   /// to the analysis information that they claim to use by overriding the
00164   /// getAnalysisUsage function.
00165   ///
00166   template<typename AnalysisType>
00167   AnalysisType &getAnalysis() const {
00168     assert(Resolver && "Pass has not been inserted into a PassManager object!");
00169     const PassInfo *PI = getClassPassInfo<AnalysisType>();
00170     return getAnalysisID<AnalysisType>(PI);
00171   }
00172 
00173   template<typename AnalysisType>
00174   AnalysisType &getAnalysisID(const PassInfo *PI) const {
00175     assert(Resolver && "Pass has not been inserted into a PassManager object!");
00176     assert(PI && "getAnalysis for unregistered pass!");
00177 
00178     // PI *must* appear in AnalysisImpls.  Because the number of passes used
00179     // should be a small number, we just do a linear search over a (dense)
00180     // vector.
00181     Pass *ResultPass = 0;
00182     for (unsigned i = 0; ; ++i) {
00183       assert(i != AnalysisImpls.size() &&
00184              "getAnalysis*() called on an analysis that was not "
00185              "'required' by pass!");
00186       if (AnalysisImpls[i].first == PI) {
00187         ResultPass = AnalysisImpls[i].second;
00188         break;
00189       }
00190     }
00191 
00192     // Because the AnalysisType may not be a subclass of pass (for
00193     // AnalysisGroups), we must use dynamic_cast here to potentially adjust the
00194     // return pointer (because the class may multiply inherit, once from pass,
00195     // once from AnalysisType).
00196     //
00197     AnalysisType *Result = dynamic_cast<AnalysisType*>(ResultPass);
00198     assert(Result && "Pass does not implement interface required!");
00199     return *Result;
00200   }
00201 
00202 private:
00203   template<typename Trait> friend class PassManagerT;
00204   friend class ModulePassManager;
00205   friend class FunctionPassManagerT;
00206   friend class BasicBlockPassManager;
00207 };
00208 
00209 inline std::ostream &operator<<(std::ostream &OS, const Pass &P) {
00210   P.print(OS, 0); return OS;
00211 }
00212 
00213 //===----------------------------------------------------------------------===//
00214 /// ModulePass class - This class is used to implement unstructured
00215 /// interprocedural optimizations and analyses.  ModulePasses may do anything
00216 /// they want to the program.
00217 ///
00218 class ModulePass : public Pass {
00219 public:
00220   /// runOnModule - Virtual method overriden by subclasses to process the module
00221   /// being operated on.
00222   virtual bool runOnModule(Module &M) = 0;
00223 
00224   virtual bool runPass(Module &M) { return runOnModule(M); }
00225   virtual bool runPass(BasicBlock&) { return false; }
00226 
00227   virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU);
00228 };
00229 
00230 
00231 //===----------------------------------------------------------------------===//
00232 /// ImmutablePass class - This class is used to provide information that does
00233 /// not need to be run.  This is useful for things like target information and
00234 /// "basic" versions of AnalysisGroups.
00235 ///
00236 class ImmutablePass : public ModulePass {
00237 public:
00238   /// initializePass - This method may be overriden by immutable passes to allow
00239   /// them to perform various initialization actions they require.  This is
00240   /// primarily because an ImmutablePass can "require" another ImmutablePass,
00241   /// and if it does, the overloaded version of initializePass may get access to
00242   /// these passes with getAnalysis<>.
00243   ///
00244   virtual void initializePass() {}
00245 
00246   /// ImmutablePasses are never run.
00247   ///
00248   virtual bool runOnModule(Module &M) { return false; }
00249 
00250 private:
00251   template<typename Trait> friend class PassManagerT;
00252   friend class ModulePassManager;
00253   virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU);
00254 };
00255 
00256 //===----------------------------------------------------------------------===//
00257 /// FunctionPass class - This class is used to implement most global
00258 /// optimizations.  Optimizations should subclass this class if they meet the
00259 /// following constraints:
00260 ///
00261 ///  1. Optimizations are organized globally, i.e., a function at a time
00262 ///  2. Optimizing a function does not cause the addition or removal of any
00263 ///     functions in the module
00264 ///
00265 class FunctionPass : public ModulePass {
00266 public:
00267   /// doInitialization - Virtual method overridden by subclasses to do
00268   /// any necessary per-module initialization.
00269   ///
00270   virtual bool doInitialization(Module &M) { return false; }
00271 
00272   /// runOnFunction - Virtual method overriden by subclasses to do the
00273   /// per-function processing of the pass.
00274   ///
00275   virtual bool runOnFunction(Function &F) = 0;
00276 
00277   /// doFinalization - Virtual method overriden by subclasses to do any post
00278   /// processing needed after all passes have run.
00279   ///
00280   virtual bool doFinalization(Module &M) { return false; }
00281 
00282   /// runOnModule - On a module, we run this pass by initializing,
00283   /// ronOnFunction'ing once for every function in the module, then by
00284   /// finalizing.
00285   ///
00286   virtual bool runOnModule(Module &M);
00287 
00288   /// run - On a function, we simply initialize, run the function, then
00289   /// finalize.
00290   ///
00291   bool run(Function &F);
00292 
00293 private:
00294   template<typename Trait> friend class PassManagerT;
00295   friend class ModulePassManager;
00296   friend class FunctionPassManagerT;
00297   friend class BasicBlockPassManager;
00298   virtual void addToPassManager(ModulePassManager *PM, AnalysisUsage &AU);
00299   virtual void addToPassManager(FunctionPassManagerT *PM, AnalysisUsage &AU);
00300 };
00301 
00302 
00303 
00304 //===----------------------------------------------------------------------===//
00305 /// BasicBlockPass class - This class is used to implement most local
00306 /// optimizations.  Optimizations should subclass this class if they
00307 /// meet the following constraints:
00308 ///   1. Optimizations are local, operating on either a basic block or
00309 ///      instruction at a time.
00310 ///   2. Optimizations do not modify the CFG of the contained function, or any
00311 ///      other basic block in the function.
00312 ///   3. Optimizations conform to all of the constraints of FunctionPasses.
00313 ///
00314 class BasicBlockPass : public FunctionPass {
00315 public:
00316   /// doInitialization - Virtual method overridden by subclasses to do
00317   /// any necessary per-module initialization.
00318   ///
00319   virtual bool doInitialization(Module &M) { return false; }
00320 
00321   /// doInitialization - Virtual method overridden by BasicBlockPass subclasses
00322   /// to do any necessary per-function initialization.
00323   ///
00324   virtual bool doInitialization(Function &F) { return false; }
00325 
00326   /// runOnBasicBlock - Virtual method overriden by subclasses to do the
00327   /// per-basicblock processing of the pass.
00328   ///
00329   virtual bool runOnBasicBlock(BasicBlock &BB) = 0;
00330 
00331   /// doFinalization - Virtual method overriden by BasicBlockPass subclasses to
00332   /// do any post processing needed after all passes have run.
00333   ///
00334   virtual bool doFinalization(Function &F) { return false; }
00335 
00336   /// doFinalization - Virtual method overriden by subclasses to do any post
00337   /// processing needed after all passes have run.
00338   ///
00339   virtual bool doFinalization(Module &M) { return false; }
00340 
00341 
00342   // To run this pass on a function, we simply call runOnBasicBlock once for
00343   // each function.
00344   //
00345   bool runOnFunction(Function &F);
00346 
00347   /// To run directly on the basic block, we initialize, runOnBasicBlock, then
00348   /// finalize.
00349   ///
00350   virtual bool runPass(Module &M) { return false; }
00351   virtual bool runPass(BasicBlock &BB);
00352 
00353 private:
00354   template<typename Trait> friend class PassManagerT;
00355   friend class FunctionPassManagerT;
00356   friend class BasicBlockPassManager;
00357   virtual void addToPassManager(FunctionPassManagerT *PM, AnalysisUsage &AU);
00358   virtual void addToPassManager(BasicBlockPassManager *PM,AnalysisUsage &AU);
00359 };
00360 
00361 /// If the user specifies the -time-passes argument on an LLVM tool command line
00362 /// then the value of this boolean will be true, otherwise false.
00363 /// @brief This is the storage for the -time-passes option.
00364 extern bool TimePassesIsEnabled;
00365 
00366 } // End llvm namespace
00367 
00368 // Include support files that contain important APIs commonly used by Passes,
00369 // but that we want to separate out to make it easier to read the header files.
00370 //
00371 #include "llvm/PassSupport.h"
00372 #include "llvm/PassAnalysisSupport.h"
00373 
00374 #endif