LLVM API Documentation
00001 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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 // The ScalarEvolution class is an LLVM pass which can be used to analyze and 00011 // catagorize scalar expressions in loops. It specializes in recognizing 00012 // general induction variables, representing them with the abstract and opaque 00013 // SCEV class. Given this analysis, trip counts of loops and other important 00014 // properties can be obtained. 00015 // 00016 // This analysis is primarily useful for induction variable substitution and 00017 // strength reduction. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 00022 #define LLVM_ANALYSIS_SCALAREVOLUTION_H 00023 00024 #include "llvm/Pass.h" 00025 #include <set> 00026 00027 namespace llvm { 00028 class Instruction; 00029 class Type; 00030 class ConstantRange; 00031 class Loop; 00032 class LoopInfo; 00033 class SCEVHandle; 00034 00035 /// SCEV - This class represent an analyzed expression in the program. These 00036 /// are reference counted opaque objects that the client is not allowed to 00037 /// do much with directly. 00038 /// 00039 class SCEV { 00040 const unsigned SCEVType; // The SCEV baseclass this node corresponds to 00041 unsigned RefCount; 00042 00043 friend class SCEVHandle; 00044 void addRef() { ++RefCount; } 00045 void dropRef() { 00046 if (--RefCount == 0) 00047 delete this; 00048 } 00049 00050 SCEV(const SCEV &); // DO NOT IMPLEMENT 00051 void operator=(const SCEV &); // DO NOT IMPLEMENT 00052 protected: 00053 virtual ~SCEV(); 00054 public: 00055 SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 00056 00057 unsigned getSCEVType() const { return SCEVType; } 00058 00059 /// getValueRange - Return the tightest constant bounds that this value is 00060 /// known to have. This method is only valid on integer SCEV objects. 00061 virtual ConstantRange getValueRange() const; 00062 00063 /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 00064 /// the specified loop. 00065 virtual bool isLoopInvariant(const Loop *L) const = 0; 00066 00067 /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 00068 /// known way in the specified loop. This property being true implies that 00069 /// the value is variant in the loop AND that we can emit an expression to 00070 /// compute the value of the expression at any particular loop iteration. 00071 virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 00072 00073 /// getType - Return the LLVM type of this SCEV expression. 00074 /// 00075 virtual const Type *getType() const = 0; 00076 00077 /// print - Print out the internal representation of this scalar to the 00078 /// specified stream. This should really only be used for debugging 00079 /// purposes. 00080 virtual void print(std::ostream &OS) const = 0; 00081 00082 /// dump - This method is used for debugging. 00083 /// 00084 void dump() const; 00085 }; 00086 00087 inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 00088 S.print(OS); 00089 return OS; 00090 } 00091 00092 /// SCEVCouldNotCompute - An object of this class is returned by queries that 00093 /// could not be answered. For example, if you ask for the number of 00094 /// iterations of a linked-list traversal loop, you will get one of these. 00095 /// None of the standard SCEV operations are valid on this class, it is just a 00096 /// marker. 00097 struct SCEVCouldNotCompute : public SCEV { 00098 SCEVCouldNotCompute(); 00099 00100 // None of these methods are valid for this object. 00101 virtual bool isLoopInvariant(const Loop *L) const; 00102 virtual const Type *getType() const; 00103 virtual bool hasComputableLoopEvolution(const Loop *L) const; 00104 virtual void print(std::ostream &OS) const; 00105 00106 00107 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00108 static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 00109 static bool classof(const SCEV *S); 00110 }; 00111 00112 /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 00113 /// freeing the objects when the last reference is dropped. 00114 class SCEVHandle { 00115 SCEV *S; 00116 SCEVHandle(); // DO NOT IMPLEMENT 00117 public: 00118 SCEVHandle(SCEV *s) : S(s) { 00119 assert(S && "Cannot create a handle to a null SCEV!"); 00120 S->addRef(); 00121 } 00122 SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 00123 S->addRef(); 00124 } 00125 ~SCEVHandle() { S->dropRef(); } 00126 00127 operator SCEV*() const { return S; } 00128 00129 SCEV &operator*() const { return *S; } 00130 SCEV *operator->() const { return S; } 00131 00132 bool operator==(SCEV *RHS) const { return S == RHS; } 00133 bool operator!=(SCEV *RHS) const { return S != RHS; } 00134 00135 const SCEVHandle &operator=(SCEV *RHS) { 00136 if (S != RHS) { 00137 S->dropRef(); 00138 S = RHS; 00139 S->addRef(); 00140 } 00141 return *this; 00142 } 00143 00144 const SCEVHandle &operator=(const SCEVHandle &RHS) { 00145 if (S != RHS.S) { 00146 S->dropRef(); 00147 S = RHS.S; 00148 S->addRef(); 00149 } 00150 return *this; 00151 } 00152 }; 00153 00154 template<typename From> struct simplify_type; 00155 template<> struct simplify_type<const SCEVHandle> { 00156 typedef SCEV* SimpleType; 00157 static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 00158 return Node; 00159 } 00160 }; 00161 template<> struct simplify_type<SCEVHandle> 00162 : public simplify_type<const SCEVHandle> {}; 00163 00164 /// ScalarEvolution - This class is the main scalar evolution driver. Because 00165 /// client code (intentionally) can't do much with the SCEV objects directly, 00166 /// they must ask this class for services. 00167 /// 00168 class ScalarEvolution : public FunctionPass { 00169 void *Impl; // ScalarEvolution uses the pimpl pattern 00170 public: 00171 ScalarEvolution() : Impl(0) {} 00172 00173 /// getSCEV - Return a SCEV expression handle for the full generality of the 00174 /// specified expression. 00175 SCEVHandle getSCEV(Value *V) const; 00176 00177 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 00178 /// at the specified scope in the program. The L value specifies a loop 00179 /// nest to evaluate the expression at, where null is the top-level or a 00180 /// specified loop is immediately inside of the loop. 00181 /// 00182 /// This method can be used to compute the exit value for a variable defined 00183 /// in a loop by querying what the value will hold in the parent loop. 00184 /// 00185 /// If this value is not computable at this scope, a SCEVCouldNotCompute 00186 /// object is returned. 00187 SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 00188 00189 /// getIterationCount - If the specified loop has a predictable iteration 00190 /// count, return it, otherwise return a SCEVCouldNotCompute object. 00191 SCEVHandle getIterationCount(const Loop *L) const; 00192 00193 /// hasLoopInvariantIterationCount - Return true if the specified loop has 00194 /// an analyzable loop-invariant iteration count. 00195 bool hasLoopInvariantIterationCount(const Loop *L) const; 00196 00197 /// deleteInstructionFromRecords - This method should be called by the 00198 /// client before it removes an instruction from the program, to make sure 00199 /// that no dangling references are left around. 00200 void deleteInstructionFromRecords(Instruction *I) const; 00201 00202 virtual bool runOnFunction(Function &F); 00203 virtual void releaseMemory(); 00204 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00205 virtual void print(std::ostream &OS) const; 00206 }; 00207 } 00208 00209 #endif