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