LLVM API Documentation
00001 //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- 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 the classes used to represent and build scalar expressions. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 00015 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 00016 00017 #include "llvm/Analysis/ScalarEvolution.h" 00018 00019 namespace llvm { 00020 class ConstantInt; 00021 class ConstantRange; 00022 00023 enum SCEVTypes { 00024 // These should be ordered in terms of increasing complexity to make the 00025 // folders simpler. 00026 scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr, 00027 scAddRecExpr, scUnknown, scCouldNotCompute 00028 }; 00029 00030 //===--------------------------------------------------------------------===// 00031 /// SCEVConstant - This class represents a constant integer value. 00032 /// 00033 class SCEVConstant : public SCEV { 00034 ConstantInt *V; 00035 SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 00036 00037 virtual ~SCEVConstant(); 00038 public: 00039 /// get method - This just gets and returns a new SCEVConstant object. 00040 /// 00041 static SCEVHandle get(ConstantInt *V); 00042 00043 ConstantInt *getValue() const { return V; } 00044 00045 /// getValueRange - Return the tightest constant bounds that this value is 00046 /// known to have. This method is only valid on integer SCEV objects. 00047 virtual ConstantRange getValueRange() const; 00048 00049 virtual bool isLoopInvariant(const Loop *L) const { 00050 return true; 00051 } 00052 00053 virtual bool hasComputableLoopEvolution(const Loop *L) const { 00054 return false; // Not loop variant 00055 } 00056 00057 virtual const Type *getType() const; 00058 00059 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00060 const SCEVHandle &Conc) const { 00061 return this; 00062 } 00063 00064 virtual void print(std::ostream &OS) const; 00065 00066 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00067 static inline bool classof(const SCEVConstant *S) { return true; } 00068 static inline bool classof(const SCEV *S) { 00069 return S->getSCEVType() == scConstant; 00070 } 00071 }; 00072 00073 //===--------------------------------------------------------------------===// 00074 /// SCEVTruncateExpr - This class represents a truncation of an integer value 00075 /// to a smaller integer value. 00076 /// 00077 class SCEVTruncateExpr : public SCEV { 00078 SCEVHandle Op; 00079 const Type *Ty; 00080 SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 00081 virtual ~SCEVTruncateExpr(); 00082 public: 00083 /// get method - This just gets and returns a new SCEVTruncate object 00084 /// 00085 static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 00086 00087 const SCEVHandle &getOperand() const { return Op; } 00088 virtual const Type *getType() const { return Ty; } 00089 00090 virtual bool isLoopInvariant(const Loop *L) const { 00091 return Op->isLoopInvariant(L); 00092 } 00093 00094 virtual bool hasComputableLoopEvolution(const Loop *L) const { 00095 return Op->hasComputableLoopEvolution(L); 00096 } 00097 00098 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00099 const SCEVHandle &Conc) const { 00100 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 00101 if (H == Op) 00102 return this; 00103 return get(H, Ty); 00104 } 00105 00106 /// getValueRange - Return the tightest constant bounds that this value is 00107 /// known to have. This method is only valid on integer SCEV objects. 00108 virtual ConstantRange getValueRange() const; 00109 00110 virtual void print(std::ostream &OS) const; 00111 00112 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00113 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 00114 static inline bool classof(const SCEV *S) { 00115 return S->getSCEVType() == scTruncate; 00116 } 00117 }; 00118 00119 //===--------------------------------------------------------------------===// 00120 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 00121 /// integer value to a larger integer value. 00122 /// 00123 class SCEVZeroExtendExpr : public SCEV { 00124 SCEVHandle Op; 00125 const Type *Ty; 00126 SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); 00127 virtual ~SCEVZeroExtendExpr(); 00128 public: 00129 /// get method - This just gets and returns a new SCEVZeroExtend object 00130 /// 00131 static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 00132 00133 const SCEVHandle &getOperand() const { return Op; } 00134 virtual const Type *getType() const { return Ty; } 00135 00136 virtual bool isLoopInvariant(const Loop *L) const { 00137 return Op->isLoopInvariant(L); 00138 } 00139 00140 virtual bool hasComputableLoopEvolution(const Loop *L) const { 00141 return Op->hasComputableLoopEvolution(L); 00142 } 00143 00144 /// getValueRange - Return the tightest constant bounds that this value is 00145 /// known to have. This method is only valid on integer SCEV objects. 00146 virtual ConstantRange getValueRange() const; 00147 00148 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00149 const SCEVHandle &Conc) const { 00150 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 00151 if (H == Op) 00152 return this; 00153 return get(H, Ty); 00154 } 00155 00156 virtual void print(std::ostream &OS) const; 00157 00158 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00159 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 00160 static inline bool classof(const SCEV *S) { 00161 return S->getSCEVType() == scZeroExtend; 00162 } 00163 }; 00164 00165 00166 //===--------------------------------------------------------------------===// 00167 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 00168 /// operators. 00169 /// 00170 class SCEVCommutativeExpr : public SCEV { 00171 std::vector<SCEVHandle> Operands; 00172 00173 protected: 00174 SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 00175 : SCEV(T) { 00176 Operands.reserve(ops.size()); 00177 Operands.insert(Operands.end(), ops.begin(), ops.end()); 00178 } 00179 ~SCEVCommutativeExpr(); 00180 00181 public: 00182 unsigned getNumOperands() const { return Operands.size(); } 00183 const SCEVHandle &getOperand(unsigned i) const { 00184 assert(i < Operands.size() && "Operand index out of range!"); 00185 return Operands[i]; 00186 } 00187 00188 const std::vector<SCEVHandle> &getOperands() const { return Operands; } 00189 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 00190 op_iterator op_begin() const { return Operands.begin(); } 00191 op_iterator op_end() const { return Operands.end(); } 00192 00193 00194 virtual bool isLoopInvariant(const Loop *L) const { 00195 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 00196 if (!getOperand(i)->isLoopInvariant(L)) return false; 00197 return true; 00198 } 00199 00200 // hasComputableLoopEvolution - Commutative expressions have computable loop 00201 // evolutions iff they have at least one operand that varies with the loop, 00202 // but that all varying operands are computable. 00203 virtual bool hasComputableLoopEvolution(const Loop *L) const { 00204 bool HasVarying = false; 00205 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 00206 if (!getOperand(i)->isLoopInvariant(L)) 00207 if (getOperand(i)->hasComputableLoopEvolution(L)) 00208 HasVarying = true; 00209 else 00210 return false; 00211 return HasVarying; 00212 } 00213 00214 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00215 const SCEVHandle &Conc) const; 00216 00217 virtual const char *getOperationStr() const = 0; 00218 00219 virtual const Type *getType() const { return getOperand(0)->getType(); } 00220 virtual void print(std::ostream &OS) const; 00221 00222 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00223 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 00224 static inline bool classof(const SCEV *S) { 00225 return S->getSCEVType() == scAddExpr || 00226 S->getSCEVType() == scMulExpr; 00227 } 00228 }; 00229 00230 00231 //===--------------------------------------------------------------------===// 00232 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 00233 /// 00234 class SCEVAddExpr : public SCEVCommutativeExpr { 00235 SCEVAddExpr(const std::vector<SCEVHandle> &ops) 00236 : SCEVCommutativeExpr(scAddExpr, ops) { 00237 } 00238 00239 public: 00240 static SCEVHandle get(std::vector<SCEVHandle> &Ops); 00241 00242 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 00243 std::vector<SCEVHandle> Ops; 00244 Ops.push_back(LHS); 00245 Ops.push_back(RHS); 00246 return get(Ops); 00247 } 00248 00249 static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, 00250 const SCEVHandle &Op2) { 00251 std::vector<SCEVHandle> Ops; 00252 Ops.push_back(Op0); 00253 Ops.push_back(Op1); 00254 Ops.push_back(Op2); 00255 return get(Ops); 00256 } 00257 00258 virtual const char *getOperationStr() const { return " + "; } 00259 00260 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00261 static inline bool classof(const SCEVAddExpr *S) { return true; } 00262 static inline bool classof(const SCEV *S) { 00263 return S->getSCEVType() == scAddExpr; 00264 } 00265 }; 00266 00267 //===--------------------------------------------------------------------===// 00268 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 00269 /// 00270 class SCEVMulExpr : public SCEVCommutativeExpr { 00271 SCEVMulExpr(const std::vector<SCEVHandle> &ops) 00272 : SCEVCommutativeExpr(scMulExpr, ops) { 00273 } 00274 00275 public: 00276 static SCEVHandle get(std::vector<SCEVHandle> &Ops); 00277 00278 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 00279 std::vector<SCEVHandle> Ops; 00280 Ops.push_back(LHS); 00281 Ops.push_back(RHS); 00282 return get(Ops); 00283 } 00284 00285 virtual const char *getOperationStr() const { return " * "; } 00286 00287 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00288 static inline bool classof(const SCEVMulExpr *S) { return true; } 00289 static inline bool classof(const SCEV *S) { 00290 return S->getSCEVType() == scMulExpr; 00291 } 00292 }; 00293 00294 00295 //===--------------------------------------------------------------------===// 00296 /// SCEVSDivExpr - This class represents a binary unsigned division operation. 00297 /// 00298 class SCEVSDivExpr : public SCEV { 00299 SCEVHandle LHS, RHS; 00300 SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 00301 : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {} 00302 00303 virtual ~SCEVSDivExpr(); 00304 public: 00305 /// get method - This just gets and returns a new SCEVSDiv object. 00306 /// 00307 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); 00308 00309 const SCEVHandle &getLHS() const { return LHS; } 00310 const SCEVHandle &getRHS() const { return RHS; } 00311 00312 virtual bool isLoopInvariant(const Loop *L) const { 00313 return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 00314 } 00315 00316 virtual bool hasComputableLoopEvolution(const Loop *L) const { 00317 return LHS->hasComputableLoopEvolution(L) && 00318 RHS->hasComputableLoopEvolution(L); 00319 } 00320 00321 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00322 const SCEVHandle &Conc) const { 00323 SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 00324 SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 00325 if (L == LHS && R == RHS) 00326 return this; 00327 else 00328 return get(L, R); 00329 } 00330 00331 00332 virtual const Type *getType() const; 00333 00334 void print(std::ostream &OS) const; 00335 00336 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00337 static inline bool classof(const SCEVSDivExpr *S) { return true; } 00338 static inline bool classof(const SCEV *S) { 00339 return S->getSCEVType() == scSDivExpr; 00340 } 00341 }; 00342 00343 00344 //===--------------------------------------------------------------------===// 00345 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 00346 /// count of the specified loop. 00347 /// 00348 /// All operands of an AddRec are required to be loop invariant. 00349 /// 00350 class SCEVAddRecExpr : public SCEV { 00351 std::vector<SCEVHandle> Operands; 00352 const Loop *L; 00353 00354 SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 00355 : SCEV(scAddRecExpr), Operands(ops), L(l) { 00356 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 00357 assert(Operands[i]->isLoopInvariant(l) && 00358 "Operands of AddRec must be loop-invariant!"); 00359 } 00360 ~SCEVAddRecExpr(); 00361 public: 00362 static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, 00363 const Loop *); 00364 static SCEVHandle get(std::vector<SCEVHandle> &Operands, 00365 const Loop *); 00366 static SCEVHandle get(const std::vector<SCEVHandle> &Operands, 00367 const Loop *L) { 00368 std::vector<SCEVHandle> NewOp(Operands); 00369 return get(NewOp, L); 00370 } 00371 00372 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 00373 op_iterator op_begin() const { return Operands.begin(); } 00374 op_iterator op_end() const { return Operands.end(); } 00375 00376 unsigned getNumOperands() const { return Operands.size(); } 00377 const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 00378 const SCEVHandle &getStart() const { return Operands[0]; } 00379 const Loop *getLoop() const { return L; } 00380 00381 00382 /// getStepRecurrence - This method constructs and returns the recurrence 00383 /// indicating how much this expression steps by. If this is a polynomial 00384 /// of degree N, it returns a chrec of degree N-1. 00385 SCEVHandle getStepRecurrence() const { 00386 if (getNumOperands() == 2) return getOperand(1); 00387 return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), 00388 getLoop()); 00389 } 00390 00391 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 00392 if (L == QL) return true; 00393 return false; 00394 } 00395 00396 virtual bool isLoopInvariant(const Loop *QueryLoop) const; 00397 00398 virtual const Type *getType() const { return Operands[0]->getType(); } 00399 00400 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 00401 /// an expressions A+B*x where A and B are loop invariant values. 00402 bool isAffine() const { 00403 // We know that the start value is invariant. This expression is thus 00404 // affine iff the step is also invariant. 00405 return getNumOperands() == 2; 00406 } 00407 00408 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 00409 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 00410 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 00411 bool isQuadratic() const { 00412 return getNumOperands() == 3; 00413 } 00414 00415 /// evaluateAtIteration - Return the value of this chain of recurrences at 00416 /// the specified iteration number. 00417 SCEVHandle evaluateAtIteration(SCEVHandle It) const; 00418 00419 /// getNumIterationsInRange - Return the number of iterations of this loop 00420 /// that produce values in the specified constant range. Another way of 00421 /// looking at this is that it returns the first iteration number where the 00422 /// value is not in the condition, thus computing the exit count. If the 00423 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 00424 /// returned. 00425 SCEVHandle getNumIterationsInRange(ConstantRange Range) const; 00426 00427 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00428 const SCEVHandle &Conc) const; 00429 00430 virtual void print(std::ostream &OS) const; 00431 00432 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00433 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 00434 static inline bool classof(const SCEV *S) { 00435 return S->getSCEVType() == scAddRecExpr; 00436 } 00437 }; 00438 00439 //===--------------------------------------------------------------------===// 00440 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 00441 /// value, and only represent it as it's LLVM Value. This is the "bottom" 00442 /// value for the analysis. 00443 /// 00444 class SCEVUnknown : public SCEV { 00445 Value *V; 00446 SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 00447 00448 protected: 00449 ~SCEVUnknown(); 00450 public: 00451 /// get method - For SCEVUnknown, this just gets and returns a new 00452 /// SCEVUnknown. 00453 static SCEVHandle get(Value *V); 00454 00455 /// getIntegerSCEV - Given an integer or FP type, create a constant for the 00456 /// specified signed integer value and return a SCEV for the constant. 00457 static SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 00458 00459 Value *getValue() const { return V; } 00460 00461 virtual bool isLoopInvariant(const Loop *L) const; 00462 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 00463 return false; // not computable 00464 } 00465 00466 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 00467 const SCEVHandle &Conc) const { 00468 if (&*Sym == this) return Conc; 00469 return this; 00470 } 00471 00472 virtual const Type *getType() const; 00473 00474 virtual void print(std::ostream &OS) const; 00475 00476 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00477 static inline bool classof(const SCEVUnknown *S) { return true; } 00478 static inline bool classof(const SCEV *S) { 00479 return S->getSCEVType() == scUnknown; 00480 } 00481 }; 00482 00483 /// SCEVVisitor - This class defines a simple visitor class that may be used 00484 /// for various SCEV analysis purposes. 00485 template<typename SC, typename RetVal=void> 00486 struct SCEVVisitor { 00487 RetVal visit(SCEV *S) { 00488 switch (S->getSCEVType()) { 00489 case scConstant: 00490 return ((SC*)this)->visitConstant((SCEVConstant*)S); 00491 case scTruncate: 00492 return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S); 00493 case scZeroExtend: 00494 return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S); 00495 case scAddExpr: 00496 return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S); 00497 case scMulExpr: 00498 return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S); 00499 case scSDivExpr: 00500 return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S); 00501 case scAddRecExpr: 00502 return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S); 00503 case scUnknown: 00504 return ((SC*)this)->visitUnknown((SCEVUnknown*)S); 00505 case scCouldNotCompute: 00506 return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S); 00507 default: 00508 assert(0 && "Unknown SCEV type!"); 00509 abort(); 00510 } 00511 } 00512 00513 RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) { 00514 assert(0 && "Invalid use of SCEVCouldNotCompute!"); 00515 abort(); 00516 return RetVal(); 00517 } 00518 }; 00519 } 00520 00521 #endif 00522