ScalarEvolution.h revision af79fb5f47b0088c6a8973a7fdbaea96973a429d
169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// The LLVM Compiler Infrastructure 469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// This file is distributed under the University of Illinois Open Source 669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// License. See LICENSE.TXT for details. 769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===----------------------------------------------------------------------===// 969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 1069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// The ScalarEvolution class is an LLVM pass which can be used to analyze and 1169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// catagorize scalar expressions in loops. It specializes in recognizing 1269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// general induction variables, representing them with the abstract and opaque 1369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// SCEV class. Given this analysis, trip counts of loops and other important 1469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// properties can be obtained. 1569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 1669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// This analysis is primarily useful for induction variable substitution and 1769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// strength reduction. 1869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 1969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===----------------------------------------------------------------------===// 2069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 2169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 2269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#define LLVM_ANALYSIS_SCALAREVOLUTION_H 2369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 2469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/Pass.h" 2569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/Analysis/LoopInfo.h" 2669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/Support/DataTypes.h" 2769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include <iosfwd> 2869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 2969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalnamespace llvm { 3069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class APInt; 3169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class ConstantInt; 3269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class Type; 3369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class SCEVHandle; 3469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class ScalarEvolution; 3569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 3669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// SCEV - This class represent an analyzed expression in the program. These 3769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// are reference counted opaque objects that the client is not allowed to 3869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// do much with directly. 3969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// 4069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class SCEV { 4169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const unsigned SCEVType; // The SCEV baseclass this node corresponds to 4269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal mutable unsigned RefCount; 4369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 4469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal friend class SCEVHandle; 4569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void addRef() const { ++RefCount; } 4669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void dropRef() const { 4769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal if (--RefCount == 0) 4869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal delete this; 4969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 5069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 5169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEV(const SCEV &); // DO NOT IMPLEMENT 5269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void operator=(const SCEV &); // DO NOT IMPLEMENT 5369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal protected: 5469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual ~SCEV(); 5569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal public: 5669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} 5769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 5869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal unsigned getSCEVType() const { return SCEVType; } 5969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 6069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 6169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the specified loop. 6269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool isLoopInvariant(const Loop *L) const = 0; 6369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 6469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 6569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// known way in the specified loop. This property being true implies that 6669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the value is variant in the loop AND that we can emit an expression to 6769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// compute the value of the expression at any particular loop iteration. 6869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 6969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 7069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// getType - Return the LLVM type of this SCEV expression. 7169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// 7269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual const Type *getType() const = 0; 7369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 7469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// isZero - Return true if the expression is a constant zero. 7569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// 7669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal bool isZero() const; 7769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 7869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 7969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the symbolic value "Sym", construct and return a new SCEV that produces 8069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the same value, but which uses the concrete value Conc instead of the 8169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// symbolic value. If this SCEV does not use the symbolic value, it 8269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// returns itself. 8369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual SCEVHandle 8469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 8569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEVHandle &Conc, 8669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal ScalarEvolution &SE) const = 0; 8769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 8869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// dominates - Return true if elements that makes up this SCEV dominates 8969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the specified basic block. 9069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 9169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 9269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// print - Print out the internal representation of this scalar to the 9369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// specified stream. This should really only be used for debugging 9469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// purposes. 9569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual void print(raw_ostream &OS) const = 0; 9669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void print(std::ostream &OS) const; 9769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void print(std::ostream *OS) const { if (OS) print(*OS); } 9869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 9969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// dump - This method is used for debugging. 10069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// 10169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void dump() const; 10269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal }; 10369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 10469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 10569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S.print(OS); 10669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return OS; 10769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 10869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 10969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 11069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S.print(OS); 11169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return OS; 11269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 11369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 11469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// SCEVCouldNotCompute - An object of this class is returned by queries that 11569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// could not be answered. For example, if you ask for the number of 11669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// iterations of a linked-list traversal loop, you will get one of these. 11769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// None of the standard SCEV operations are valid on this class, it is just a 11869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// marker. 11969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal struct SCEVCouldNotCompute : public SCEV { 12069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEVCouldNotCompute(); 12169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 12269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // None of these methods are valid for this object. 12369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool isLoopInvariant(const Loop *L) const; 12469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual const Type *getType() const; 12569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool hasComputableLoopEvolution(const Loop *L) const; 12669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual void print(raw_ostream &OS) const; 12769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual SCEVHandle 12869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 12969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEVHandle &Conc, 13069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal ScalarEvolution &SE) const; 13169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 13269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 13369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return true; 13469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 13569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 13669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Methods for support type inquiry through isa, cast, and dyn_cast: 13769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 13869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal static bool classof(const SCEV *S); 13969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal }; 14069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 14169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, 14269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// freeing the objects when the last reference is dropped. 14369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal class SCEVHandle { 14469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEV *S; 14569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEVHandle(); // DO NOT IMPLEMENT 14669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal public: 14769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) { 14869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal assert(S && "Cannot create a handle to a null SCEV!"); 14969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S->addRef(); 15069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 15169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { 15269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S->addRef(); 15369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 15469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal ~SCEVHandle() { S->dropRef(); } 15569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 15669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal operator SCEV*() const { return S; } 15769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 15869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEV &operator*() const { return *S; } 15969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal SCEV *operator->() const { return S; } 16069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 16169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal bool operator==(SCEV *RHS) const { return S == RHS; } 16269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal bool operator!=(SCEV *RHS) const { return S != RHS; } 16369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 16469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEVHandle &operator=(SCEV *RHS) { 16569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal if (S != RHS) { 16669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S->dropRef(); 16769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S = RHS; 16869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal S->addRef(); 16969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 170 return *this; 171 } 172 173 const SCEVHandle &operator=(const SCEVHandle &RHS) { 174 if (S != RHS.S) { 175 S->dropRef(); 176 S = RHS.S; 177 S->addRef(); 178 } 179 return *this; 180 } 181 }; 182 183 template<typename From> struct simplify_type; 184 template<> struct simplify_type<const SCEVHandle> { 185 typedef SCEV* SimpleType; 186 static SimpleType getSimplifiedValue(const SCEVHandle &Node) { 187 return Node; 188 } 189 }; 190 template<> struct simplify_type<SCEVHandle> 191 : public simplify_type<const SCEVHandle> {}; 192 193 /// ScalarEvolution - This class is the main scalar evolution driver. Because 194 /// client code (intentionally) can't do much with the SCEV objects directly, 195 /// they must ask this class for services. 196 /// 197 class ScalarEvolution : public FunctionPass { 198 void *Impl; // ScalarEvolution uses the pimpl pattern 199 public: 200 static char ID; // Pass identification, replacement for typeid 201 ScalarEvolution() : FunctionPass(&ID), Impl(0) {} 202 203 /// isSCEVable - Test if values of the given type are analyzable within 204 /// the SCEV framework. This primarily includes integer types, and it 205 /// can optionally include pointer types if the ScalarEvolution class 206 /// has access to target-specific information. 207 bool isSCEVable(const Type *Ty) const; 208 209 /// getTypeSizeInBits - Return the size in bits of the specified type, 210 /// for which isSCEVable must return true. 211 uint64_t getTypeSizeInBits(const Type *Ty) const; 212 213 /// getEffectiveSCEVType - Return a type with the same bitwidth as 214 /// the given type and which represents how SCEV will treat the given 215 /// type, for which isSCEVable must return true. For pointer types, 216 /// this is the pointer-sized integer type. 217 const Type *getEffectiveSCEVType(const Type *Ty) const; 218 219 /// getSCEV - Return a SCEV expression handle for the full generality of the 220 /// specified expression. 221 SCEVHandle getSCEV(Value *V) const; 222 223 SCEVHandle getConstant(ConstantInt *V); 224 SCEVHandle getConstant(const APInt& Val); 225 SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); 226 SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); 227 SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); 228 SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops); 229 SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 230 std::vector<SCEVHandle> Ops; 231 Ops.push_back(LHS); 232 Ops.push_back(RHS); 233 return getAddExpr(Ops); 234 } 235 SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, 236 const SCEVHandle &Op2) { 237 std::vector<SCEVHandle> Ops; 238 Ops.push_back(Op0); 239 Ops.push_back(Op1); 240 Ops.push_back(Op2); 241 return getAddExpr(Ops); 242 } 243 SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops); 244 SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { 245 std::vector<SCEVHandle> Ops; 246 Ops.push_back(LHS); 247 Ops.push_back(RHS); 248 return getMulExpr(Ops); 249 } 250 SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 251 SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, 252 const Loop *L); 253 SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands, 254 const Loop *L); 255 SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands, 256 const Loop *L) { 257 std::vector<SCEVHandle> NewOp(Operands); 258 return getAddRecExpr(NewOp, L); 259 } 260 SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 261 SCEVHandle getSMaxExpr(std::vector<SCEVHandle> Operands); 262 SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); 263 SCEVHandle getUMaxExpr(std::vector<SCEVHandle> Operands); 264 SCEVHandle getUnknown(Value *V); 265 SCEVHandle getCouldNotCompute(); 266 267 /// getNegativeSCEV - Return the SCEV object corresponding to -V. 268 /// 269 SCEVHandle getNegativeSCEV(const SCEVHandle &V); 270 271 /// getNotSCEV - Return the SCEV object corresponding to ~V. 272 /// 273 SCEVHandle getNotSCEV(const SCEVHandle &V); 274 275 /// getMinusSCEV - Return LHS-RHS. 276 /// 277 SCEVHandle getMinusSCEV(const SCEVHandle &LHS, 278 const SCEVHandle &RHS); 279 280 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 281 /// of the input value to the specified type. If the type must be 282 /// extended, it is zero extended. 283 SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); 284 285 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 286 /// of the input value to the specified type. If the type must be 287 /// extended, it is sign extended. 288 SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); 289 290 /// getIntegerSCEV - Given an integer or FP type, create a constant for the 291 /// specified signed integer value and return a SCEV for the constant. 292 SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 293 294 /// hasSCEV - Return true if the SCEV for this value has already been 295 /// computed. 296 bool hasSCEV(Value *V) const; 297 298 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 299 /// the specified value. 300 void setSCEV(Value *V, const SCEVHandle &H); 301 302 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 303 /// at the specified scope in the program. The L value specifies a loop 304 /// nest to evaluate the expression at, where null is the top-level or a 305 /// specified loop is immediately inside of the loop. 306 /// 307 /// This method can be used to compute the exit value for a variable defined 308 /// in a loop by querying what the value will hold in the parent loop. 309 /// 310 /// If this value is not computable at this scope, a SCEVCouldNotCompute 311 /// object is returned. 312 SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; 313 314 /// isLoopGuardedByCond - Test whether entry to the loop is protected by 315 /// a conditional between LHS and RHS. 316 bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 317 SCEV *LHS, SCEV *RHS); 318 319 /// getBackedgeTakenCount - If the specified loop has a predictable 320 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 321 /// object. The backedge-taken count is the number of times the loop header 322 /// will be branched to from within the loop. This is one less than the 323 /// trip count of the loop, since it doesn't count the first iteration, 324 /// when the header is branched to from outside the loop. 325 /// 326 /// Note that it is not valid to call this method on a loop without a 327 /// loop-invariant backedge-taken count (see 328 /// hasLoopInvariantBackedgeTakenCount). 329 /// 330 SCEVHandle getBackedgeTakenCount(const Loop *L) const; 331 332 /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 333 /// has an analyzable loop-invariant backedge-taken count. 334 bool hasLoopInvariantBackedgeTakenCount(const Loop *L) const; 335 336 /// forgetLoopBackedgeTakenCount - This method should be called by the 337 /// client when it has changed a loop in a way that may effect 338 /// ScalarEvolution's ability to compute a trip count, or if the loop 339 /// is deleted. 340 void forgetLoopBackedgeTakenCount(const Loop *L); 341 342 /// deleteValueFromRecords - This method should be called by the 343 /// client before it removes a Value from the program, to make sure 344 /// that no dangling references are left around. 345 void deleteValueFromRecords(Value *V) const; 346 347 virtual bool runOnFunction(Function &F); 348 virtual void releaseMemory(); 349 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 350 void print(raw_ostream &OS, const Module* = 0) const; 351 virtual void print(std::ostream &OS, const Module* = 0) const; 352 void print(std::ostream *OS, const Module* M = 0) const { 353 if (OS) print(*OS, M); 354 } 355 }; 356} 357 358#endif 359