ScalarEvolutionExpressions.h revision 372b46cad9f745859f542f9d2216991585ae83f4
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 public: 42 ConstantInt *getValue() const { return V; } 43 44 virtual bool isLoopInvariant(const Loop *L) const { 45 return true; 46 } 47 48 virtual bool hasComputableLoopEvolution(const Loop *L) const { 49 return false; // Not loop variant 50 } 51 52 virtual const Type *getType() const; 53 54 const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, 55 const SCEV* Conc, 56 ScalarEvolution &SE) const { 57 return this; 58 } 59 60 bool dominates(BasicBlock *BB, DominatorTree *DT) const { 61 return true; 62 } 63 64 virtual void print(raw_ostream &OS) const; 65 66 /// Methods for support type inquiry through isa, cast, and dyn_cast: 67 static inline bool classof(const SCEVConstant *S) { return true; } 68 static inline bool classof(const SCEV *S) { 69 return S->getSCEVType() == scConstant; 70 } 71 }; 72 73 //===--------------------------------------------------------------------===// 74 /// SCEVCastExpr - This is the base class for unary cast operator classes. 75 /// 76 class SCEVCastExpr : public SCEV { 77 protected: 78 const SCEV* Op; 79 const Type *Ty; 80 81 SCEVCastExpr(unsigned SCEVTy, const SCEV* op, const Type *ty, 82 const ScalarEvolution* p); 83 virtual ~SCEVCastExpr(); 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 SCEV* op, const Type *ty, 116 const ScalarEvolution* p); 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 SCEV* op, const Type *ty, 145 const ScalarEvolution* p); 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 SCEV* op, const Type *ty, 174 const ScalarEvolution* p); 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(enum SCEVTypes T, const SmallVectorImpl<const SCEV*> &ops, 205 const ScalarEvolution* p) 206 : SCEV(T, p), Operands(ops.begin(), ops.end()) {} 207 virtual ~SCEVNAryExpr() {} 208 209 public: 210 unsigned getNumOperands() const { return (unsigned)Operands.size(); } 211 const SCEV* getOperand(unsigned i) const { 212 assert(i < Operands.size() && "Operand index out of range!"); 213 return Operands[i]; 214 } 215 216 const SmallVectorImpl<const SCEV*> &getOperands() const { return Operands; } 217 typedef SmallVectorImpl<const SCEV*>::const_iterator op_iterator; 218 op_iterator op_begin() const { return Operands.begin(); } 219 op_iterator op_end() const { return Operands.end(); } 220 221 virtual bool isLoopInvariant(const Loop *L) const { 222 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 223 if (!getOperand(i)->isLoopInvariant(L)) return false; 224 return true; 225 } 226 227 // hasComputableLoopEvolution - N-ary expressions have computable loop 228 // evolutions iff they have at least one operand that varies with the loop, 229 // but that all varying operands are computable. 230 virtual bool hasComputableLoopEvolution(const Loop *L) const { 231 bool HasVarying = false; 232 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 233 if (!getOperand(i)->isLoopInvariant(L)) { 234 if (getOperand(i)->hasComputableLoopEvolution(L)) 235 HasVarying = true; 236 else 237 return false; 238 } 239 return HasVarying; 240 } 241 242 bool dominates(BasicBlock *BB, DominatorTree *DT) const; 243 244 virtual const Type *getType() const { return getOperand(0)->getType(); } 245 246 /// Methods for support type inquiry through isa, cast, and dyn_cast: 247 static inline bool classof(const SCEVNAryExpr *S) { return true; } 248 static inline bool classof(const SCEV *S) { 249 return S->getSCEVType() == scAddExpr || 250 S->getSCEVType() == scMulExpr || 251 S->getSCEVType() == scSMaxExpr || 252 S->getSCEVType() == scUMaxExpr || 253 S->getSCEVType() == scAddRecExpr; 254 } 255 }; 256 257 //===--------------------------------------------------------------------===// 258 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 259 /// operators. 260 /// 261 class SCEVCommutativeExpr : public SCEVNAryExpr { 262 protected: 263 SCEVCommutativeExpr(enum SCEVTypes T, 264 const SmallVectorImpl<const SCEV*> &ops, 265 const ScalarEvolution* p) 266 : SCEVNAryExpr(T, ops, p) {} 267 268 public: 269 const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, 270 const SCEV* Conc, 271 ScalarEvolution &SE) const; 272 273 virtual const char *getOperationStr() const = 0; 274 275 virtual void print(raw_ostream &OS) const; 276 277 /// Methods for support type inquiry through isa, cast, and dyn_cast: 278 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 279 static inline bool classof(const SCEV *S) { 280 return S->getSCEVType() == scAddExpr || 281 S->getSCEVType() == scMulExpr || 282 S->getSCEVType() == scSMaxExpr || 283 S->getSCEVType() == scUMaxExpr; 284 } 285 }; 286 287 288 //===--------------------------------------------------------------------===// 289 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 290 /// 291 class SCEVAddExpr : public SCEVCommutativeExpr { 292 friend class ScalarEvolution; 293 294 explicit SCEVAddExpr(const SmallVectorImpl<const SCEV*> &ops, 295 const ScalarEvolution* p) 296 : SCEVCommutativeExpr(scAddExpr, ops, p) { 297 } 298 299 public: 300 virtual const char *getOperationStr() const { return " + "; } 301 302 /// Methods for support type inquiry through isa, cast, and dyn_cast: 303 static inline bool classof(const SCEVAddExpr *S) { return true; } 304 static inline bool classof(const SCEV *S) { 305 return S->getSCEVType() == scAddExpr; 306 } 307 }; 308 309 //===--------------------------------------------------------------------===// 310 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 311 /// 312 class SCEVMulExpr : public SCEVCommutativeExpr { 313 friend class ScalarEvolution; 314 315 explicit SCEVMulExpr(const SmallVectorImpl<const SCEV*> &ops, 316 const ScalarEvolution* p) 317 : SCEVCommutativeExpr(scMulExpr, ops, p) { 318 } 319 320 public: 321 virtual const char *getOperationStr() const { return " * "; } 322 323 /// Methods for support type inquiry through isa, cast, and dyn_cast: 324 static inline bool classof(const SCEVMulExpr *S) { return true; } 325 static inline bool classof(const SCEV *S) { 326 return S->getSCEVType() == scMulExpr; 327 } 328 }; 329 330 331 //===--------------------------------------------------------------------===// 332 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 333 /// 334 class SCEVUDivExpr : public SCEV { 335 friend class ScalarEvolution; 336 337 const SCEV* LHS; 338 const SCEV* RHS; 339 SCEVUDivExpr(const SCEV* lhs, const SCEV* rhs, 340 const ScalarEvolution* p) 341 : SCEV(scUDivExpr, p), 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 SmallVectorImpl<const SCEV*> &ops, const Loop *l, 396 const ScalarEvolution* p) 397 : SCEVNAryExpr(scAddRecExpr, ops, p), 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,op_end()), 413 getLoop()); 414 } 415 416 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 417 if (L == QL) return true; 418 return false; 419 } 420 421 virtual bool isLoopInvariant(const Loop *QueryLoop) const; 422 423 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 424 /// an expressions A+B*x where A and B are loop invariant values. 425 bool isAffine() const { 426 // We know that the start value is invariant. This expression is thus 427 // affine iff the step is also invariant. 428 return getNumOperands() == 2; 429 } 430 431 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 432 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 433 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 434 bool isQuadratic() const { 435 return getNumOperands() == 3; 436 } 437 438 /// evaluateAtIteration - Return the value of this chain of recurrences at 439 /// the specified iteration number. 440 const SCEV* evaluateAtIteration(const SCEV* It, ScalarEvolution &SE) const; 441 442 /// getNumIterationsInRange - Return the number of iterations of this loop 443 /// that produce values in the specified constant range. Another way of 444 /// looking at this is that it returns the first iteration number where the 445 /// value is not in the condition, thus computing the exit count. If the 446 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 447 /// returned. 448 const SCEV* getNumIterationsInRange(ConstantRange Range, 449 ScalarEvolution &SE) const; 450 451 const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, 452 const SCEV* Conc, 453 ScalarEvolution &SE) const; 454 455 virtual void print(raw_ostream &OS) const; 456 457 /// Methods for support type inquiry through isa, cast, and dyn_cast: 458 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 459 static inline bool classof(const SCEV *S) { 460 return S->getSCEVType() == scAddRecExpr; 461 } 462 }; 463 464 465 //===--------------------------------------------------------------------===// 466 /// SCEVSMaxExpr - This class represents a signed maximum selection. 467 /// 468 class SCEVSMaxExpr : public SCEVCommutativeExpr { 469 friend class ScalarEvolution; 470 471 explicit SCEVSMaxExpr(const SmallVectorImpl<const SCEV*> &ops, 472 const ScalarEvolution* p) 473 : SCEVCommutativeExpr(scSMaxExpr, ops, p) { 474 } 475 476 public: 477 virtual const char *getOperationStr() const { return " smax "; } 478 479 /// Methods for support type inquiry through isa, cast, and dyn_cast: 480 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 481 static inline bool classof(const SCEV *S) { 482 return S->getSCEVType() == scSMaxExpr; 483 } 484 }; 485 486 487 //===--------------------------------------------------------------------===// 488 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 489 /// 490 class SCEVUMaxExpr : public SCEVCommutativeExpr { 491 friend class ScalarEvolution; 492 493 explicit SCEVUMaxExpr(const SmallVectorImpl<const SCEV*> &ops, 494 const ScalarEvolution* p) 495 : SCEVCommutativeExpr(scUMaxExpr, ops, p) { 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, const ScalarEvolution* p) : 519 SCEV(scUnknown, p), V(v) {} 520 521 public: 522 Value *getValue() const { return V; } 523 524 virtual bool isLoopInvariant(const Loop *L) const; 525 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 526 return false; // not computable 527 } 528 529 const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, 530 const SCEV* Conc, 531 ScalarEvolution &SE) const { 532 if (&*Sym == this) return Conc; 533 return this; 534 } 535 536 bool dominates(BasicBlock *BB, DominatorTree *DT) const; 537 538 virtual const Type *getType() const; 539 540 virtual void print(raw_ostream &OS) const; 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(const SCEV *S) { 554 switch (S->getSCEVType()) { 555 case scConstant: 556 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 557 case scTruncate: 558 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 559 case scZeroExtend: 560 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 561 case scSignExtend: 562 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 563 case scAddExpr: 564 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 565 case scMulExpr: 566 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 567 case scUDivExpr: 568 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 569 case scAddRecExpr: 570 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 571 case scSMaxExpr: 572 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 573 case scUMaxExpr: 574 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 575 case scUnknown: 576 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 577 case scCouldNotCompute: 578 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 579 default: 580 assert(0 && "Unknown SCEV type!"); 581 abort(); 582 } 583 } 584 585 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 586 assert(0 && "Invalid use of SCEVCouldNotCompute!"); 587 abort(); 588 return RetVal(); 589 } 590 }; 591} 592 593#endif 594