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