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