ScalarEvolutionExpressions.h revision 34cd4a484e532cc463fd5a4bf59b88d13c5467c1
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 19namespace llvm { 20 class ConstantInt; 21 class ConstantRange; 22 class APInt; 23 24 enum SCEVTypes { 25 // These should be ordered in terms of increasing complexity to make the 26 // folders simpler. 27 scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 28 scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown, 29 scCouldNotCompute 30 }; 31 32 //===--------------------------------------------------------------------===// 33 /// SCEVConstant - This class represents a constant integer value. 34 /// 35 class SCEVConstant : public SCEV { 36 friend class ScalarEvolution; 37 38 ConstantInt *V; 39 explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 40 41 virtual ~SCEVConstant(); 42 public: 43 ConstantInt *getValue() const { return V; } 44 45 /// getValueRange - Return the tightest constant bounds that this value is 46 /// known to have. This method is only valid on integer SCEV objects. 47 virtual ConstantRange getValueRange() const; 48 49 virtual bool isLoopInvariant(const Loop *L) const { 50 return true; 51 } 52 53 virtual bool hasComputableLoopEvolution(const Loop *L) const { 54 return false; // Not loop variant 55 } 56 57 virtual const Type *getType() const; 58 59 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 60 const SCEVHandle &Conc, 61 ScalarEvolution &SE) const { 62 return this; 63 } 64 65 virtual void print(std::ostream &OS) const; 66 void print(std::ostream *OS) const { if (OS) print(*OS); } 67 68 /// Methods for support type inquiry through isa, cast, and dyn_cast: 69 static inline bool classof(const SCEVConstant *S) { return true; } 70 static inline bool classof(const SCEV *S) { 71 return S->getSCEVType() == scConstant; 72 } 73 }; 74 75 //===--------------------------------------------------------------------===// 76 /// SCEVTruncateExpr - This class represents a truncation of an integer value 77 /// to a smaller integer value. 78 /// 79 class SCEVTruncateExpr : public SCEV { 80 friend class ScalarEvolution; 81 82 SCEVHandle Op; 83 const Type *Ty; 84 SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 85 virtual ~SCEVTruncateExpr(); 86 public: 87 const SCEVHandle &getOperand() const { return Op; } 88 virtual const Type *getType() const { return Ty; } 89 90 virtual bool isLoopInvariant(const Loop *L) const { 91 return Op->isLoopInvariant(L); 92 } 93 94 virtual bool hasComputableLoopEvolution(const Loop *L) const { 95 return Op->hasComputableLoopEvolution(L); 96 } 97 98 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 99 const SCEVHandle &Conc, 100 ScalarEvolution &SE) const { 101 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 102 if (H == Op) 103 return this; 104 return SE.getTruncateExpr(H, Ty); 105 } 106 107 /// getValueRange - Return the tightest constant bounds that this value is 108 /// known to have. This method is only valid on integer SCEV objects. 109 virtual ConstantRange getValueRange() const; 110 111 virtual void print(std::ostream &OS) const; 112 void print(std::ostream *OS) const { if (OS) print(*OS); } 113 114 /// Methods for support type inquiry through isa, cast, and dyn_cast: 115 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 116 static inline bool classof(const SCEV *S) { 117 return S->getSCEVType() == scTruncate; 118 } 119 }; 120 121 //===--------------------------------------------------------------------===// 122 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 123 /// integer value to a larger integer value. 124 /// 125 class SCEVZeroExtendExpr : public SCEV { 126 friend class ScalarEvolution; 127 128 SCEVHandle Op; 129 const Type *Ty; 130 SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); 131 virtual ~SCEVZeroExtendExpr(); 132 public: 133 const SCEVHandle &getOperand() const { return Op; } 134 virtual const Type *getType() const { return Ty; } 135 136 virtual bool isLoopInvariant(const Loop *L) const { 137 return Op->isLoopInvariant(L); 138 } 139 140 virtual bool hasComputableLoopEvolution(const Loop *L) const { 141 return Op->hasComputableLoopEvolution(L); 142 } 143 144 /// getValueRange - Return the tightest constant bounds that this value is 145 /// known to have. This method is only valid on integer SCEV objects. 146 virtual ConstantRange getValueRange() const; 147 148 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 149 const SCEVHandle &Conc, 150 ScalarEvolution &SE) const { 151 SCEVHandle 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(std::ostream &OS) const; 158 void print(std::ostream *OS) const { if (OS) print(*OS); } 159 160 /// Methods for support type inquiry through isa, cast, and dyn_cast: 161 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 162 static inline bool classof(const SCEV *S) { 163 return S->getSCEVType() == scZeroExtend; 164 } 165 }; 166 167 //===--------------------------------------------------------------------===// 168 /// SCEVSignExtendExpr - This class represents a sign extension of a small 169 /// integer value to a larger integer value. 170 /// 171 class SCEVSignExtendExpr : public SCEV { 172 friend class ScalarEvolution; 173 174 SCEVHandle Op; 175 const Type *Ty; 176 SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty); 177 virtual ~SCEVSignExtendExpr(); 178 public: 179 const SCEVHandle &getOperand() const { return Op; } 180 virtual const Type *getType() const { return Ty; } 181 182 virtual bool isLoopInvariant(const Loop *L) const { 183 return Op->isLoopInvariant(L); 184 } 185 186 virtual bool hasComputableLoopEvolution(const Loop *L) const { 187 return Op->hasComputableLoopEvolution(L); 188 } 189 190 /// getValueRange - Return the tightest constant bounds that this value is 191 /// known to have. This method is only valid on integer SCEV objects. 192 virtual ConstantRange getValueRange() const; 193 194 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 195 const SCEVHandle &Conc, 196 ScalarEvolution &SE) const { 197 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 198 if (H == Op) 199 return this; 200 return SE.getSignExtendExpr(H, Ty); 201 } 202 203 virtual void print(std::ostream &OS) const; 204 void print(std::ostream *OS) const { if (OS) print(*OS); } 205 206 /// Methods for support type inquiry through isa, cast, and dyn_cast: 207 static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 208 static inline bool classof(const SCEV *S) { 209 return S->getSCEVType() == scSignExtend; 210 } 211 }; 212 213 214 //===--------------------------------------------------------------------===// 215 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 216 /// operators. 217 /// 218 class SCEVCommutativeExpr : public SCEV { 219 friend class ScalarEvolution; 220 221 std::vector<SCEVHandle> Operands; 222 223 protected: 224 SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 225 : SCEV(T) { 226 Operands.reserve(ops.size()); 227 Operands.insert(Operands.end(), ops.begin(), ops.end()); 228 } 229 ~SCEVCommutativeExpr(); 230 231 public: 232 unsigned getNumOperands() const { return (unsigned)Operands.size(); } 233 const SCEVHandle &getOperand(unsigned i) const { 234 assert(i < Operands.size() && "Operand index out of range!"); 235 return Operands[i]; 236 } 237 238 const std::vector<SCEVHandle> &getOperands() const { return Operands; } 239 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 240 op_iterator op_begin() const { return Operands.begin(); } 241 op_iterator op_end() const { return Operands.end(); } 242 243 244 virtual bool isLoopInvariant(const Loop *L) const { 245 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 246 if (!getOperand(i)->isLoopInvariant(L)) return false; 247 return true; 248 } 249 250 // hasComputableLoopEvolution - Commutative expressions have computable loop 251 // evolutions iff they have at least one operand that varies with the loop, 252 // but that all varying operands are computable. 253 virtual bool hasComputableLoopEvolution(const Loop *L) const { 254 bool HasVarying = false; 255 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 256 if (!getOperand(i)->isLoopInvariant(L)) { 257 if (getOperand(i)->hasComputableLoopEvolution(L)) 258 HasVarying = true; 259 else 260 return false; 261 } 262 return HasVarying; 263 } 264 265 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 266 const SCEVHandle &Conc, 267 ScalarEvolution &SE) const; 268 269 virtual const char *getOperationStr() const = 0; 270 271 virtual const Type *getType() const { return getOperand(0)->getType(); } 272 virtual void print(std::ostream &OS) const; 273 void print(std::ostream *OS) const { if (OS) print(*OS); } 274 275 /// Methods for support type inquiry through isa, cast, and dyn_cast: 276 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 277 static inline bool classof(const SCEV *S) { 278 return S->getSCEVType() == scAddExpr || 279 S->getSCEVType() == scMulExpr || 280 S->getSCEVType() == scSMaxExpr || 281 S->getSCEVType() == scUMaxExpr; 282 } 283 }; 284 285 286 //===--------------------------------------------------------------------===// 287 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 288 /// 289 class SCEVAddExpr : public SCEVCommutativeExpr { 290 friend class ScalarEvolution; 291 292 explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops) 293 : SCEVCommutativeExpr(scAddExpr, ops) { 294 } 295 296 public: 297 virtual const char *getOperationStr() const { return " + "; } 298 299 /// Methods for support type inquiry through isa, cast, and dyn_cast: 300 static inline bool classof(const SCEVAddExpr *S) { return true; } 301 static inline bool classof(const SCEV *S) { 302 return S->getSCEVType() == scAddExpr; 303 } 304 }; 305 306 //===--------------------------------------------------------------------===// 307 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 308 /// 309 class SCEVMulExpr : public SCEVCommutativeExpr { 310 friend class ScalarEvolution; 311 312 explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops) 313 : SCEVCommutativeExpr(scMulExpr, ops) { 314 } 315 316 public: 317 virtual const char *getOperationStr() const { return " * "; } 318 319 /// Methods for support type inquiry through isa, cast, and dyn_cast: 320 static inline bool classof(const SCEVMulExpr *S) { return true; } 321 static inline bool classof(const SCEV *S) { 322 return S->getSCEVType() == scMulExpr; 323 } 324 }; 325 326 327 //===--------------------------------------------------------------------===// 328 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 329 /// 330 class SCEVUDivExpr : public SCEV { 331 friend class ScalarEvolution; 332 333 SCEVHandle LHS, RHS; 334 SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 335 : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} 336 337 virtual ~SCEVUDivExpr(); 338 public: 339 const SCEVHandle &getLHS() const { return LHS; } 340 const SCEVHandle &getRHS() const { return RHS; } 341 342 virtual bool isLoopInvariant(const Loop *L) const { 343 return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 344 } 345 346 virtual bool hasComputableLoopEvolution(const Loop *L) const { 347 return LHS->hasComputableLoopEvolution(L) && 348 RHS->hasComputableLoopEvolution(L); 349 } 350 351 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 352 const SCEVHandle &Conc, 353 ScalarEvolution &SE) const { 354 SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 355 SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 356 if (L == LHS && R == RHS) 357 return this; 358 else 359 return SE.getUDivExpr(L, R); 360 } 361 362 363 virtual const Type *getType() const; 364 365 void print(std::ostream &OS) const; 366 void print(std::ostream *OS) const { if (OS) print(*OS); } 367 368 /// Methods for support type inquiry through isa, cast, and dyn_cast: 369 static inline bool classof(const SCEVUDivExpr *S) { return true; } 370 static inline bool classof(const SCEV *S) { 371 return S->getSCEVType() == scUDivExpr; 372 } 373 }; 374 375 376 //===--------------------------------------------------------------------===// 377 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 378 /// count of the specified loop. 379 /// 380 /// All operands of an AddRec are required to be loop invariant. 381 /// 382 class SCEVAddRecExpr : public SCEV { 383 friend class ScalarEvolution; 384 385 std::vector<SCEVHandle> Operands; 386 const Loop *L; 387 388 SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 389 : SCEV(scAddRecExpr), Operands(ops), L(l) { 390 for (size_t i = 0, e = Operands.size(); i != e; ++i) 391 assert(Operands[i]->isLoopInvariant(l) && 392 "Operands of AddRec must be loop-invariant!"); 393 } 394 ~SCEVAddRecExpr(); 395 public: 396 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 397 op_iterator op_begin() const { return Operands.begin(); } 398 op_iterator op_end() const { return Operands.end(); } 399 400 unsigned getNumOperands() const { return (unsigned)Operands.size(); } 401 const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 402 const SCEVHandle &getStart() const { return Operands[0]; } 403 const Loop *getLoop() const { return L; } 404 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 SCEVHandle getStepRecurrence(ScalarEvolution &SE) const { 410 if (getNumOperands() == 2) return getOperand(1); 411 return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()), 412 getLoop()); 413 } 414 415 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 416 if (L == QL) return true; 417 return false; 418 } 419 420 virtual bool isLoopInvariant(const Loop *QueryLoop) const; 421 422 virtual const Type *getType() const { return Operands[0]->getType(); } 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 SCEVHandle evaluateAtIteration(SCEVHandle 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 SCEVHandle getNumIterationsInRange(ConstantRange Range, 450 ScalarEvolution &SE) const; 451 452 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 453 const SCEVHandle &Conc, 454 ScalarEvolution &SE) const; 455 456 virtual void print(std::ostream &OS) const; 457 void print(std::ostream *OS) const { if (OS) print(*OS); } 458 459 /// Methods for support type inquiry through isa, cast, and dyn_cast: 460 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 461 static inline bool classof(const SCEV *S) { 462 return S->getSCEVType() == scAddRecExpr; 463 } 464 }; 465 466 467 //===--------------------------------------------------------------------===// 468 /// SCEVSMaxExpr - This class represents a signed maximum selection. 469 /// 470 class SCEVSMaxExpr : public SCEVCommutativeExpr { 471 friend class ScalarEvolution; 472 473 explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops) 474 : SCEVCommutativeExpr(scSMaxExpr, ops) { 475 } 476 477 public: 478 virtual const char *getOperationStr() const { return " smax "; } 479 480 /// Methods for support type inquiry through isa, cast, and dyn_cast: 481 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 482 static inline bool classof(const SCEV *S) { 483 return S->getSCEVType() == scSMaxExpr; 484 } 485 }; 486 487 488 //===--------------------------------------------------------------------===// 489 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 490 /// 491 class SCEVUMaxExpr : public SCEVCommutativeExpr { 492 friend class ScalarEvolution; 493 494 explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops) 495 : SCEVCommutativeExpr(scUMaxExpr, ops) { 496 } 497 498 public: 499 virtual const char *getOperationStr() const { return " umax "; } 500 501 /// Methods for support type inquiry through isa, cast, and dyn_cast: 502 static inline bool classof(const SCEVUMaxExpr *S) { return true; } 503 static inline bool classof(const SCEV *S) { 504 return S->getSCEVType() == scUMaxExpr; 505 } 506 }; 507 508 509 //===--------------------------------------------------------------------===// 510 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 511 /// value, and only represent it as it's LLVM Value. This is the "bottom" 512 /// value for the analysis. 513 /// 514 class SCEVUnknown : public SCEV { 515 friend class ScalarEvolution; 516 517 Value *V; 518 explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 519 520 protected: 521 ~SCEVUnknown(); 522 public: 523 Value *getValue() const { return V; } 524 525 virtual bool isLoopInvariant(const Loop *L) const; 526 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 527 return false; // not computable 528 } 529 530 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 531 const SCEVHandle &Conc, 532 ScalarEvolution &SE) const { 533 if (&*Sym == this) return Conc; 534 return this; 535 } 536 537 virtual const Type *getType() const; 538 539 virtual void print(std::ostream &OS) const; 540 void print(std::ostream *OS) const { if (OS) print(*OS); } 541 542 /// Methods for support type inquiry through isa, cast, and dyn_cast: 543 static inline bool classof(const SCEVUnknown *S) { return true; } 544 static inline bool classof(const SCEV *S) { 545 return S->getSCEVType() == scUnknown; 546 } 547 }; 548 549 /// SCEVVisitor - This class defines a simple visitor class that may be used 550 /// for various SCEV analysis purposes. 551 template<typename SC, typename RetVal=void> 552 struct SCEVVisitor { 553 RetVal visit(SCEV *S) { 554 switch (S->getSCEVType()) { 555 case scConstant: 556 return ((SC*)this)->visitConstant((SCEVConstant*)S); 557 case scTruncate: 558 return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S); 559 case scZeroExtend: 560 return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S); 561 case scSignExtend: 562 return ((SC*)this)->visitSignExtendExpr((SCEVSignExtendExpr*)S); 563 case scAddExpr: 564 return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S); 565 case scMulExpr: 566 return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S); 567 case scUDivExpr: 568 return ((SC*)this)->visitUDivExpr((SCEVUDivExpr*)S); 569 case scAddRecExpr: 570 return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S); 571 case scSMaxExpr: 572 return ((SC*)this)->visitSMaxExpr((SCEVSMaxExpr*)S); 573 case scUMaxExpr: 574 return ((SC*)this)->visitUMaxExpr((SCEVUMaxExpr*)S); 575 case scUnknown: 576 return ((SC*)this)->visitUnknown((SCEVUnknown*)S); 577 case scCouldNotCompute: 578 return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S); 579 default: 580 assert(0 && "Unknown SCEV type!"); 581 abort(); 582 } 583 } 584 585 RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) { 586 assert(0 && "Invalid use of SCEVCouldNotCompute!"); 587 abort(); 588 return RetVal(); 589 } 590 }; 591} 592 593#endif 594