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