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 mutable unsigned RefCount; 00042 00043 friend class SCEVHandle; 00044 void addRef() const { ++RefCount; } 00045 void dropRef() const { 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 /// getNegativeSCEV - Return the SCEV object corresponding to -V. 00058 /// 00059 static SCEVHandle getNegativeSCEV(const SCEVHandle &V); 00060 00061 /// getMinusSCEV - Return LHS-RHS. 00062 /// 00063 static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 00064 const SCEVHandle &RHS); 00065 00066 00067 unsigned getSCEVType() const { return SCEVType; } 00068 00069 /// getValueRange - Return the tightest constant bounds that this value is 00070 /// known to have. This method is only valid on integer SCEV objects. 00071 virtual ConstantRange getValueRange() const; 00072 00073 /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 00074 /// the specified loop. 00075 virtual bool isLoopInvariant(const Loop *L) const = 0; 00076 00077 /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 00078 /// known way in the specified loop. This property being true implies that 00079 /// the value is variant in the loop AND that we can emit an expression to 00080 /// compute the value of the expression at any particular loop iteration. 00081 virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 00082 00083 /// getType - Return the LLVM type of this SCEV expression. 00084 /// 00085 virtual const Type *getType() const = 0; 00086 00087 /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 00088 /// the symbolic value "Sym", construct and return a new SCEV that produces 00089 /// the same value, but which uses the concrete value Conc instead of the 00090 /// symbolic value. If this SCEV does not use the symbolic value, it 00091 /// returns itself. 00092 virtual SCEVHandle 00093 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00094 const SCEVHandle &Conc) const = 0; 00095 00096 /// print - Print out the internal representation of this scalar to the 00097 /// specified stream. This should really only be used for debugging 00098 /// purposes. 00099 virtual void print(std::ostream &OS) const = 0; 00100 00101 /// dump - This method is used for debugging. 00102 /// 00103 void dump() const; 00104 }; 00105 00106 inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 00107 S.print(OS); 00108 return OS; 00109 } 00110 00111 /// SCEVCouldNotCompute - An object of this class is returned by queries that 00112 /// could not be answered. For example, if you ask for the number of 00113 /// iterations of a linked-list traversal loop, you will get one of these. 00114 /// None of the standard SCEV operations are valid on this class, it is just a 00115 /// marker. 00116 struct SCEVCouldNotCompute : public SCEV { 00117 SCEVCouldNotCompute(); 00118 00119 // None of these methods are valid for this object. 00120 virtual bool isLoopInvariant(const Loop *L) const; 00121 virtual const Type *getType() const; 00122 virtual bool hasComputableLoopEvolution(const Loop *L) const; 00123 virtual void print(std::ostream &OS) const; 00124 virtual SCEVHandle 00125 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00126 const SCEVHandle &Conc) const; 00127 00128 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00129 static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 00130 static bool classof(const SCEV *S); 00131 }; 00132 00133 /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 00134 /// freeing the objects when the last reference is dropped. 00135 class SCEVHandle { 00136 SCEV *S; 00137 SCEVHandle(); // DO NOT IMPLEMENT 00138 public: 00139 SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) { 00140 assert(S && "Cannot create a handle to a null SCEV!"); 00141 S->addRef(); 00142 } 00143 SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 00144 S->addRef(); 00145 } 00146 ~SCEVHandle() { S->dropRef(); } 00147 00148 operator SCEV*() const { return S; } 00149 00150 SCEV &operator*() const { return *S; } 00151 SCEV *operator->() const { return S; } 00152 00153 bool operator==(SCEV *RHS) const { return S == RHS; } 00154 bool operator!=(SCEV *RHS) const { return S != RHS; } 00155 00156 const SCEVHandle &operator=(SCEV *RHS) { 00157 if (S != RHS) { 00158 S->dropRef(); 00159 S = RHS; 00160 S->addRef(); 00161 } 00162 return *this; 00163 } 00164 00165 const SCEVHandle &operator=(const SCEVHandle &RHS) { 00166 if (S != RHS.S) { 00167 S->dropRef(); 00168 S = RHS.S; 00169 S->addRef(); 00170 } 00171 return *this; 00172 } 00173 }; 00174 00175 template<typename From> struct simplify_type; 00176 template<> struct simplify_type<const SCEVHandle> { 00177 typedef SCEV* SimpleType; 00178 static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 00179 return Node; 00180 } 00181 }; 00182 template<> struct simplify_type<SCEVHandle> 00183 : public simplify_type<const SCEVHandle> {}; 00184 00185 /// ScalarEvolution - This class is the main scalar evolution driver. Because 00186 /// client code (intentionally) can't do much with the SCEV objects directly, 00187 /// they must ask this class for services. 00188 /// 00189 class ScalarEvolution : public FunctionPass { 00190 void *Impl; // ScalarEvolution uses the pimpl pattern 00191 public: 00192 ScalarEvolution() : Impl(0) {} 00193 00194 /// getSCEV - Return a SCEV expression handle for the full generality of the 00195 /// specified expression. 00196 SCEVHandle getSCEV(Value *V) const; 00197 00198 /// hasSCEV - Return true if the SCEV for this value has already been 00199 /// computed. 00200 bool hasSCEV(Value *V) const; 00201 00202 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 00203 /// the specified value. 00204 void setSCEV(Value *V, const SCEVHandle &H); 00205 00206 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 00207 /// at the specified scope in the program. The L value specifies a loop 00208 /// nest to evaluate the expression at, where null is the top-level or a 00209 /// specified loop is immediately inside of the loop. 00210 /// 00211 /// This method can be used to compute the exit value for a variable defined 00212 /// in a loop by querying what the value will hold in the parent loop. 00213 /// 00214 /// If this value is not computable at this scope, a SCEVCouldNotCompute 00215 /// object is returned. 00216 SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 00217 00218 /// getIterationCount - If the specified loop has a predictable iteration 00219 /// count, return it, otherwise return a SCEVCouldNotCompute object. 00220 SCEVHandle getIterationCount(const Loop *L) const; 00221 00222 /// hasLoopInvariantIterationCount - Return true if the specified loop has 00223 /// an analyzable loop-invariant iteration count. 00224 bool hasLoopInvariantIterationCount(const Loop *L) const; 00225 00226 /// deleteInstructionFromRecords - This method should be called by the 00227 /// client before it removes an instruction from the program, to make sure 00228 /// that no dangling references are left around. 00229 void deleteInstructionFromRecords(Instruction *I) const; 00230 00231 virtual bool runOnFunction(Function &F); 00232 virtual void releaseMemory(); 00233 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00234 virtual void print(std::ostream &OS, const Module* = 0) const; 00235 }; 00236 } 00237 00238 #endif