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