LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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