ScalarEvolution.h revision e1beb8f59d076536b0022496d663344a792a8cab
1//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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// The ScalarEvolution class is an LLVM pass which can be used to analyze and 11// catagorize scalar expressions in loops. It specializes in recognizing 12// general induction variables, representing them with the abstract and opaque 13// SCEV class. Given this analysis, trip counts of loops and other important 14// properties can be obtained. 15// 16// This analysis is primarily useful for induction variable substitution and 17// strength reduction. 18// 19//===----------------------------------------------------------------------===// 20 21#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 22#define LLVM_ANALYSIS_SCALAREVOLUTION_H 23 24#include "llvm/Pass.h" 25#include <set> 26 27namespace llvm { 28 class Instruction; 29 class Type; 30 class ConstantRange; 31 class Loop; 32 class LoopInfo; 33 class SCEVHandle; 34 class ScalarEvolutionRewriter; 35 36 /// SCEV - This class represent an analyzed expression in the program. These 37 /// are reference counted opaque objects that the client is not allowed to 38 /// do much with directly. 39 /// 40 class SCEV { 41 const unsigned SCEVType; // The SCEV baseclass this node corresponds to 42 unsigned RefCount; 43 44 friend class SCEVHandle; 45 void addRef() { ++RefCount; } 46 void dropRef() { 47 if (--RefCount == 0) 48 delete this; 49 } 50 51 SCEV(const SCEV &); // DO NOT IMPLEMENT 52 void operator=(const SCEV &); // DO NOT IMPLEMENT 53 protected: 54 virtual ~SCEV(); 55 public: 56 SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 57 58 unsigned getSCEVType() const { return SCEVType; } 59 60 /// getValueRange - Return the tightest constant bounds that this value is 61 /// known to have. This method is only valid on integer SCEV objects. 62 virtual ConstantRange getValueRange() const; 63 64 /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 65 /// the specified loop. 66 virtual bool isLoopInvariant(const Loop *L) const = 0; 67 68 /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 69 /// known way in the specified loop. This property being true implies that 70 /// the value is variant in the loop AND that we can emit an expression to 71 /// compute the value of the expression at any particular loop iteration. 72 virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 73 74 /// getType - Return the LLVM type of this SCEV expression. 75 /// 76 virtual const Type *getType() const = 0; 77 78 /// expandCodeFor - Given a rewriter object, expand this SCEV into a closed 79 /// form expression and return a Value corresponding to the expression in 80 /// question. 81 virtual Value *expandCodeFor(ScalarEvolutionRewriter &SER, 82 Instruction *InsertPt) = 0; 83 84 85 /// print - Print out the internal representation of this scalar to the 86 /// specified stream. This should really only be used for debugging 87 /// purposes. 88 virtual void print(std::ostream &OS) const = 0; 89 90 /// dump - This method is used for debugging. 91 /// 92 void dump() const; 93 }; 94 95 inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 96 S.print(OS); 97 return OS; 98 } 99 100 /// SCEVCouldNotCompute - An object of this class is returned by queries that 101 /// could not be answered. For example, if you ask for the number of 102 /// iterations of a linked-list traversal loop, you will get one of these. 103 /// None of the standard SCEV operations are valid on this class, it is just a 104 /// marker. 105 struct SCEVCouldNotCompute : public SCEV { 106 SCEVCouldNotCompute(); 107 108 // None of these methods are valid for this object. 109 virtual bool isLoopInvariant(const Loop *L) const; 110 virtual const Type *getType() const; 111 virtual bool hasComputableLoopEvolution(const Loop *L) const; 112 virtual Value *expandCodeFor(ScalarEvolutionRewriter &, Instruction *); 113 virtual void print(std::ostream &OS) const; 114 115 116 /// Methods for support type inquiry through isa, cast, and dyn_cast: 117 static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 118 static bool classof(const SCEV *S); 119 }; 120 121 /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 122 /// freeing the objects when the last reference is dropped. 123 class SCEVHandle { 124 SCEV *S; 125 SCEVHandle(); // DO NOT IMPLEMENT 126 public: 127 SCEVHandle(SCEV *s) : S(s) { 128 assert(S && "Cannot create a handle to a null SCEV!"); 129 S->addRef(); 130 } 131 SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 132 S->addRef(); 133 } 134 ~SCEVHandle() { S->dropRef(); } 135 136 operator SCEV*() const { return S; } 137 138 SCEV &operator*() const { return *S; } 139 SCEV *operator->() const { return S; } 140 141 bool operator==(SCEV *RHS) const { return S == RHS; } 142 bool operator!=(SCEV *RHS) const { return S != RHS; } 143 144 const SCEVHandle &operator=(SCEV *RHS) { 145 if (S != RHS) { 146 S->dropRef(); 147 S = RHS; 148 S->addRef(); 149 } 150 return *this; 151 } 152 153 const SCEVHandle &operator=(const SCEVHandle &RHS) { 154 if (S != RHS.S) { 155 S->dropRef(); 156 S = RHS.S; 157 S->addRef(); 158 } 159 return *this; 160 } 161 }; 162 163 template<typename From> struct simplify_type; 164 template<> struct simplify_type<const SCEVHandle> { 165 typedef SCEV* SimpleType; 166 static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 167 return Node; 168 } 169 }; 170 template<> struct simplify_type<SCEVHandle> 171 : public simplify_type<const SCEVHandle> {}; 172 173 /// ScalarEvolution - This class is the main scalar evolution driver. Because 174 /// client code (intentionally) can't do much with the SCEV objects directly, 175 /// they must ask this class for services. 176 /// 177 class ScalarEvolution : public FunctionPass { 178 void *Impl; // ScalarEvolution uses the pimpl pattern 179 public: 180 ScalarEvolution() : Impl(0) {} 181 182 /// getSCEV - Return a SCEV expression handle for the full generality of the 183 /// specified expression. 184 SCEVHandle getSCEV(Value *V) const; 185 186 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 187 /// at the specified scope in the program. The L value specifies a loop 188 /// nest to evaluate the expression at, where null is the top-level or a 189 /// specified loop is immediately inside of the loop. 190 /// 191 /// This method can be used to compute the exit value for a variable defined 192 /// in a loop by querying what the value will hold in the parent loop. 193 /// 194 /// If this value is not computable at this scope, a SCEVCouldNotCompute 195 /// object is returned. 196 SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 197 198 /// getIterationCount - If the specified loop has a predictable iteration 199 /// count, return it, otherwise return a SCEVCouldNotCompute object. 200 SCEVHandle getIterationCount(const Loop *L) const; 201 202 /// hasLoopInvariantIterationCount - Return true if the specified loop has 203 /// an analyzable loop-invariant iteration count. 204 bool hasLoopInvariantIterationCount(const Loop *L) const; 205 206 /// deleteInstructionFromRecords - This method should be called by the 207 /// client before it removes an instruction from the program, to make sure 208 /// that no dangling references are left around. 209 void deleteInstructionFromRecords(Instruction *I) const; 210 211 /// shouldSubstituteIndVar - Return true if we should perform induction 212 /// variable substitution for this variable. This is a hack because we 213 /// don't have a strength reduction pass yet. When we do we will promote 214 /// all vars, because we can strength reduce them later as desired. 215 bool shouldSubstituteIndVar(const SCEV *S) const; 216 217 virtual bool runOnFunction(Function &F); 218 virtual void releaseMemory(); 219 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 220 virtual void print(std::ostream &OS) const; 221 }; 222 223 /// ScalarEvolutionRewriter - This class uses information about analyze 224 /// scalars to rewrite expressions in canonical form. This can be used for 225 /// induction variable substitution, strength reduction, or loop exit value 226 /// replacement. 227 /// 228 /// Clients should create an instance of this class when rewriting is needed, 229 /// and destroying it when finished to allow the release of the associated 230 /// memory. 231 class ScalarEvolutionRewriter { 232 ScalarEvolution &SE; 233 LoopInfo &LI; 234 std::map<SCEVHandle, Value*> InsertedExpressions; 235 std::set<Instruction*> InsertedInstructions; 236 public: 237 ScalarEvolutionRewriter(ScalarEvolution &se, LoopInfo &li) 238 : SE(se), LI(li) {} 239 240 /// isInsertedInstruction - Return true if the specified instruction was 241 /// inserted by the code rewriter. If so, the client should not modify the 242 /// instruction. 243 bool isInsertedInstruction(Instruction *I) const { 244 return InsertedInstructions.count(I); 245 } 246 247 /// GetOrInsertCanonicalInductionVariable - This method returns the 248 /// canonical induction variable of the specified type for the specified 249 /// loop (inserts one if there is none). A canonical induction variable 250 /// starts at zero and steps by one on each iteration. 251 Value *GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty); 252 253 254 /// addInsertedValue - Remember the specified instruction as being the 255 /// canonical form for the specified SCEV. 256 void addInsertedValue(Instruction *I, SCEV *S) { 257 InsertedExpressions[S] = I; 258 InsertedInstructions.insert(I); 259 } 260 261 /// ExpandCodeFor - Insert code to directly compute the specified SCEV 262 /// expression into the program. The inserted code is inserted into the 263 /// specified block. 264 /// 265 /// If a particular value sign is required, a type may be specified for the 266 /// result. 267 Value *ExpandCodeFor(SCEVHandle SH, Instruction *InsertPt, 268 const Type *Ty = 0); 269 }; 270} 271 272#endif 273