ScalarEvolutionExpressions.h revision 4ce32db913beb6ae27df2fa0a9db5d68fd4889d2
1//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the classes used to represent and build scalar expressions. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 15#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 16 17#include "llvm/Analysis/ScalarEvolution.h" 18#include "llvm/Support/ErrorHandling.h" 19 20namespace llvm { 21 class ConstantInt; 22 class ConstantRange; 23 class DominatorTree; 24 25 enum SCEVTypes { 26 // These should be ordered in terms of increasing complexity to make the 27 // folders simpler. 28 scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 29 scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 30 scUnknown, scCouldNotCompute 31 }; 32 33 //===--------------------------------------------------------------------===// 34 /// SCEVConstant - This class represents a constant integer value. 35 /// 36 class SCEVConstant : public SCEV { 37 friend class ScalarEvolution; 38 39 ConstantInt *V; 40 SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 41 SCEV(ID, scConstant), V(v) {} 42 public: 43 ConstantInt *getValue() const { return V; } 44 45 const Type *getType() const { return V->getType(); } 46 47 /// Methods for support type inquiry through isa, cast, and dyn_cast: 48 static inline bool classof(const SCEVConstant *S) { return true; } 49 static inline bool classof(const SCEV *S) { 50 return S->getSCEVType() == scConstant; 51 } 52 }; 53 54 //===--------------------------------------------------------------------===// 55 /// SCEVCastExpr - This is the base class for unary cast operator classes. 56 /// 57 class SCEVCastExpr : public SCEV { 58 protected: 59 const SCEV *Op; 60 const Type *Ty; 61 62 SCEVCastExpr(const FoldingSetNodeIDRef ID, 63 unsigned SCEVTy, const SCEV *op, const Type *ty); 64 65 public: 66 const SCEV *getOperand() const { return Op; } 67 const Type *getType() const { return Ty; } 68 69 /// Methods for support type inquiry through isa, cast, and dyn_cast: 70 static inline bool classof(const SCEVCastExpr *S) { return true; } 71 static inline bool classof(const SCEV *S) { 72 return S->getSCEVType() == scTruncate || 73 S->getSCEVType() == scZeroExtend || 74 S->getSCEVType() == scSignExtend; 75 } 76 }; 77 78 //===--------------------------------------------------------------------===// 79 /// SCEVTruncateExpr - This class represents a truncation of an integer value 80 /// to a smaller integer value. 81 /// 82 class SCEVTruncateExpr : public SCEVCastExpr { 83 friend class ScalarEvolution; 84 85 SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 86 const SCEV *op, const Type *ty); 87 88 public: 89 /// Methods for support type inquiry through isa, cast, and dyn_cast: 90 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 91 static inline bool classof(const SCEV *S) { 92 return S->getSCEVType() == scTruncate; 93 } 94 }; 95 96 //===--------------------------------------------------------------------===// 97 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 98 /// integer value to a larger integer value. 99 /// 100 class SCEVZeroExtendExpr : public SCEVCastExpr { 101 friend class ScalarEvolution; 102 103 SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 104 const SCEV *op, const Type *ty); 105 106 public: 107 /// Methods for support type inquiry through isa, cast, and dyn_cast: 108 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 109 static inline bool classof(const SCEV *S) { 110 return S->getSCEVType() == scZeroExtend; 111 } 112 }; 113 114 //===--------------------------------------------------------------------===// 115 /// SCEVSignExtendExpr - This class represents a sign extension of a small 116 /// integer value to a larger integer value. 117 /// 118 class SCEVSignExtendExpr : public SCEVCastExpr { 119 friend class ScalarEvolution; 120 121 SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 122 const SCEV *op, const Type *ty); 123 124 public: 125 /// Methods for support type inquiry through isa, cast, and dyn_cast: 126 static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 127 static inline bool classof(const SCEV *S) { 128 return S->getSCEVType() == scSignExtend; 129 } 130 }; 131 132 133 //===--------------------------------------------------------------------===// 134 /// SCEVNAryExpr - This node is a base class providing common 135 /// functionality for n'ary operators. 136 /// 137 class SCEVNAryExpr : public SCEV { 138 protected: 139 // Since SCEVs are immutable, ScalarEvolution allocates operand 140 // arrays with its SCEVAllocator, so this class just needs a simple 141 // pointer rather than a more elaborate vector-like data structure. 142 // This also avoids the need for a non-trivial destructor. 143 const SCEV *const *Operands; 144 size_t NumOperands; 145 146 SCEVNAryExpr(const FoldingSetNodeIDRef ID, 147 enum SCEVTypes T, const SCEV *const *O, size_t N) 148 : SCEV(ID, T), Operands(O), NumOperands(N) {} 149 150 public: 151 size_t getNumOperands() const { return NumOperands; } 152 const SCEV *getOperand(unsigned i) const { 153 assert(i < NumOperands && "Operand index out of range!"); 154 return Operands[i]; 155 } 156 157 typedef const SCEV *const *op_iterator; 158 op_iterator op_begin() const { return Operands; } 159 op_iterator op_end() const { return Operands + NumOperands; } 160 161 const Type *getType() const { return getOperand(0)->getType(); } 162 163 bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } 164 void setHasNoUnsignedWrap(bool B) { 165 SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); 166 } 167 bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } 168 void setHasNoSignedWrap(bool B) { 169 SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); 170 } 171 172 /// Methods for support type inquiry through isa, cast, and dyn_cast: 173 static inline bool classof(const SCEVNAryExpr *S) { return true; } 174 static inline bool classof(const SCEV *S) { 175 return S->getSCEVType() == scAddExpr || 176 S->getSCEVType() == scMulExpr || 177 S->getSCEVType() == scSMaxExpr || 178 S->getSCEVType() == scUMaxExpr || 179 S->getSCEVType() == scAddRecExpr; 180 } 181 }; 182 183 //===--------------------------------------------------------------------===// 184 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 185 /// operators. 186 /// 187 class SCEVCommutativeExpr : public SCEVNAryExpr { 188 protected: 189 SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 190 enum SCEVTypes T, const SCEV *const *O, size_t N) 191 : SCEVNAryExpr(ID, T, O, N) {} 192 193 public: 194 /// Methods for support type inquiry through isa, cast, and dyn_cast: 195 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 196 static inline bool classof(const SCEV *S) { 197 return S->getSCEVType() == scAddExpr || 198 S->getSCEVType() == scMulExpr || 199 S->getSCEVType() == scSMaxExpr || 200 S->getSCEVType() == scUMaxExpr; 201 } 202 }; 203 204 205 //===--------------------------------------------------------------------===// 206 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 207 /// 208 class SCEVAddExpr : public SCEVCommutativeExpr { 209 friend class ScalarEvolution; 210 211 SCEVAddExpr(const FoldingSetNodeIDRef ID, 212 const SCEV *const *O, size_t N) 213 : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 214 } 215 216 public: 217 const Type *getType() const { 218 // Use the type of the last operand, which is likely to be a pointer 219 // type, if there is one. This doesn't usually matter, but it can help 220 // reduce casts when the expressions are expanded. 221 return getOperand(getNumOperands() - 1)->getType(); 222 } 223 224 /// Methods for support type inquiry through isa, cast, and dyn_cast: 225 static inline bool classof(const SCEVAddExpr *S) { return true; } 226 static inline bool classof(const SCEV *S) { 227 return S->getSCEVType() == scAddExpr; 228 } 229 }; 230 231 //===--------------------------------------------------------------------===// 232 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 233 /// 234 class SCEVMulExpr : public SCEVCommutativeExpr { 235 friend class ScalarEvolution; 236 237 SCEVMulExpr(const FoldingSetNodeIDRef ID, 238 const SCEV *const *O, size_t N) 239 : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 240 } 241 242 public: 243 /// Methods for support type inquiry through isa, cast, and dyn_cast: 244 static inline bool classof(const SCEVMulExpr *S) { return true; } 245 static inline bool classof(const SCEV *S) { 246 return S->getSCEVType() == scMulExpr; 247 } 248 }; 249 250 251 //===--------------------------------------------------------------------===// 252 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 253 /// 254 class SCEVUDivExpr : public SCEV { 255 friend class ScalarEvolution; 256 257 const SCEV *LHS; 258 const SCEV *RHS; 259 SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 260 : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 261 262 public: 263 const SCEV *getLHS() const { return LHS; } 264 const SCEV *getRHS() const { return RHS; } 265 266 const Type *getType() const { 267 // In most cases the types of LHS and RHS will be the same, but in some 268 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 269 // depend on the type for correctness, but handling types carefully can 270 // avoid extra casts in the SCEVExpander. The LHS is more likely to be 271 // a pointer type than the RHS, so use the RHS' type here. 272 return getRHS()->getType(); 273 } 274 275 /// Methods for support type inquiry through isa, cast, and dyn_cast: 276 static inline bool classof(const SCEVUDivExpr *S) { return true; } 277 static inline bool classof(const SCEV *S) { 278 return S->getSCEVType() == scUDivExpr; 279 } 280 }; 281 282 283 //===--------------------------------------------------------------------===// 284 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 285 /// count of the specified loop. This is the primary focus of the 286 /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 287 /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 288 /// created and analyzed. 289 /// 290 /// All operands of an AddRec are required to be loop invariant. 291 /// 292 class SCEVAddRecExpr : public SCEVNAryExpr { 293 friend class ScalarEvolution; 294 295 const Loop *L; 296 297 SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 298 const SCEV *const *O, size_t N, const Loop *l) 299 : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 300 301 public: 302 const SCEV *getStart() const { return Operands[0]; } 303 const Loop *getLoop() const { return L; } 304 305 /// getStepRecurrence - This method constructs and returns the recurrence 306 /// indicating how much this expression steps by. If this is a polynomial 307 /// of degree N, it returns a chrec of degree N-1. 308 const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 309 if (isAffine()) return getOperand(1); 310 return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 311 op_end()), 312 getLoop()); 313 } 314 315 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 316 /// an expressions A+B*x where A and B are loop invariant values. 317 bool isAffine() const { 318 // We know that the start value is invariant. This expression is thus 319 // affine iff the step is also invariant. 320 return getNumOperands() == 2; 321 } 322 323 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 324 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 325 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 326 bool isQuadratic() const { 327 return getNumOperands() == 3; 328 } 329 330 /// evaluateAtIteration - Return the value of this chain of recurrences at 331 /// the specified iteration number. 332 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 333 334 /// getNumIterationsInRange - Return the number of iterations of this loop 335 /// that produce values in the specified constant range. Another way of 336 /// looking at this is that it returns the first iteration number where the 337 /// value is not in the condition, thus computing the exit count. If the 338 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 339 /// returned. 340 const SCEV *getNumIterationsInRange(ConstantRange Range, 341 ScalarEvolution &SE) const; 342 343 /// getPostIncExpr - Return an expression representing the value of 344 /// this expression one iteration of the loop ahead. 345 const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 346 return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 347 } 348 349 /// Methods for support type inquiry through isa, cast, and dyn_cast: 350 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 351 static inline bool classof(const SCEV *S) { 352 return S->getSCEVType() == scAddRecExpr; 353 } 354 }; 355 356 357 //===--------------------------------------------------------------------===// 358 /// SCEVSMaxExpr - This class represents a signed maximum selection. 359 /// 360 class SCEVSMaxExpr : public SCEVCommutativeExpr { 361 friend class ScalarEvolution; 362 363 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 364 const SCEV *const *O, size_t N) 365 : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 366 // Max never overflows. 367 setHasNoUnsignedWrap(true); 368 setHasNoSignedWrap(true); 369 } 370 371 public: 372 /// Methods for support type inquiry through isa, cast, and dyn_cast: 373 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 374 static inline bool classof(const SCEV *S) { 375 return S->getSCEVType() == scSMaxExpr; 376 } 377 }; 378 379 380 //===--------------------------------------------------------------------===// 381 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 382 /// 383 class SCEVUMaxExpr : public SCEVCommutativeExpr { 384 friend class ScalarEvolution; 385 386 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 387 const SCEV *const *O, size_t N) 388 : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 389 // Max never overflows. 390 setHasNoUnsignedWrap(true); 391 setHasNoSignedWrap(true); 392 } 393 394 public: 395 /// Methods for support type inquiry through isa, cast, and dyn_cast: 396 static inline bool classof(const SCEVUMaxExpr *S) { return true; } 397 static inline bool classof(const SCEV *S) { 398 return S->getSCEVType() == scUMaxExpr; 399 } 400 }; 401 402 //===--------------------------------------------------------------------===// 403 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 404 /// value, and only represent it as its LLVM Value. This is the "bottom" 405 /// value for the analysis. 406 /// 407 class SCEVUnknown : public SCEV, private CallbackVH { 408 friend class ScalarEvolution; 409 410 // Implement CallbackVH. 411 virtual void deleted(); 412 virtual void allUsesReplacedWith(Value *New); 413 414 /// SE - The parent ScalarEvolution value. This is used to update 415 /// the parent's maps when the value associated with a SCEVUnknown 416 /// is deleted or RAUW'd. 417 ScalarEvolution *SE; 418 419 /// Next - The next pointer in the linked list of all 420 /// SCEVUnknown instances owned by a ScalarEvolution. 421 SCEVUnknown *Next; 422 423 SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 424 ScalarEvolution *se, SCEVUnknown *next) : 425 SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 426 427 public: 428 Value *getValue() const { return getValPtr(); } 429 430 /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 431 /// constant representing a type size, alignment, or field offset in 432 /// a target-independent manner, and hasn't happened to have been 433 /// folded with other operations into something unrecognizable. This 434 /// is mainly only useful for pretty-printing and other situations 435 /// where it isn't absolutely required for these to succeed. 436 bool isSizeOf(const Type *&AllocTy) const; 437 bool isAlignOf(const Type *&AllocTy) const; 438 bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const; 439 440 const Type *getType() const { return getValPtr()->getType(); } 441 442 /// Methods for support type inquiry through isa, cast, and dyn_cast: 443 static inline bool classof(const SCEVUnknown *S) { return true; } 444 static inline bool classof(const SCEV *S) { 445 return S->getSCEVType() == scUnknown; 446 } 447 }; 448 449 /// SCEVVisitor - This class defines a simple visitor class that may be used 450 /// for various SCEV analysis purposes. 451 template<typename SC, typename RetVal=void> 452 struct SCEVVisitor { 453 RetVal visit(const SCEV *S) { 454 switch (S->getSCEVType()) { 455 case scConstant: 456 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 457 case scTruncate: 458 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 459 case scZeroExtend: 460 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 461 case scSignExtend: 462 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 463 case scAddExpr: 464 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 465 case scMulExpr: 466 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 467 case scUDivExpr: 468 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 469 case scAddRecExpr: 470 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 471 case scSMaxExpr: 472 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 473 case scUMaxExpr: 474 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 475 case scUnknown: 476 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 477 case scCouldNotCompute: 478 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 479 default: 480 llvm_unreachable("Unknown SCEV type!"); 481 } 482 } 483 484 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 485 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 486 return RetVal(); 487 } 488 }; 489} 490 491#endif 492