ScalarEvolutionExpressions.h revision 1b342583f6fc42f548912632f6aa24fc6e11986a
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) : 40 SCEV(scConstant), V(v) {} 41 public: 42 virtual void Profile(FoldingSetNodeID &ID) const; 43 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 const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, 57 const SCEV *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 const SCEV *Op; 81 const Type *Ty; 82 83 SCEVCastExpr(unsigned SCEVTy, const SCEV *op, const Type *ty); 84 85 public: 86 virtual void Profile(FoldingSetNodeID &ID) const; 87 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 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 SCEV *op, const Type *ty); 118 119 public: 120 const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, 121 const SCEV *Conc, 122 ScalarEvolution &SE) const { 123 const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 124 if (H == Op) 125 return this; 126 return SE.getTruncateExpr(H, Ty); 127 } 128 129 virtual void print(raw_ostream &OS) const; 130 131 /// Methods for support type inquiry through isa, cast, and dyn_cast: 132 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 133 static inline bool classof(const SCEV *S) { 134 return S->getSCEVType() == scTruncate; 135 } 136 }; 137 138 //===--------------------------------------------------------------------===// 139 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 140 /// integer value to a larger integer value. 141 /// 142 class SCEVZeroExtendExpr : public SCEVCastExpr { 143 friend class ScalarEvolution; 144 145 SCEVZeroExtendExpr(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 SCEV *op, const Type *ty); 174 175 public: 176 const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, 177 const SCEV *Conc, 178 ScalarEvolution &SE) const { 179 const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 180 if (H == Op) 181 return this; 182 return SE.getSignExtendExpr(H, Ty); 183 } 184 185 virtual void print(raw_ostream &OS) const; 186 187 /// Methods for support type inquiry through isa, cast, and dyn_cast: 188 static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 189 static inline bool classof(const SCEV *S) { 190 return S->getSCEVType() == scSignExtend; 191 } 192 }; 193 194 195 //===--------------------------------------------------------------------===// 196 /// SCEVNAryExpr - This node is a base class providing common 197 /// functionality for n'ary operators. 198 /// 199 class SCEVNAryExpr : public SCEV { 200 protected: 201 SmallVector<const SCEV *, 8> Operands; 202 203 SCEVNAryExpr(enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops) 204 : SCEV(T), Operands(ops.begin(), ops.end()) {} 205 206 public: 207 virtual void Profile(FoldingSetNodeID &ID) const; 208 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(enum SCEVTypes T, 265 const SmallVectorImpl<const SCEV *> &ops) 266 : SCEVNAryExpr(T, ops) {} 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 : SCEVCommutativeExpr(scAddExpr, ops) { 296 } 297 298 public: 299 virtual const char *getOperationStr() const { return " + "; } 300 301 /// Methods for support type inquiry through isa, cast, and dyn_cast: 302 static inline bool classof(const SCEVAddExpr *S) { return true; } 303 static inline bool classof(const SCEV *S) { 304 return S->getSCEVType() == scAddExpr; 305 } 306 }; 307 308 //===--------------------------------------------------------------------===// 309 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 310 /// 311 class SCEVMulExpr : public SCEVCommutativeExpr { 312 friend class ScalarEvolution; 313 314 explicit SCEVMulExpr(const SmallVectorImpl<const SCEV *> &ops) 315 : SCEVCommutativeExpr(scMulExpr, ops) { 316 } 317 318 public: 319 virtual const char *getOperationStr() const { return " * "; } 320 321 /// Methods for support type inquiry through isa, cast, and dyn_cast: 322 static inline bool classof(const SCEVMulExpr *S) { return true; } 323 static inline bool classof(const SCEV *S) { 324 return S->getSCEVType() == scMulExpr; 325 } 326 }; 327 328 329 //===--------------------------------------------------------------------===// 330 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 331 /// 332 class SCEVUDivExpr : public SCEV { 333 friend class ScalarEvolution; 334 335 const SCEV *LHS; 336 const SCEV *RHS; 337 SCEVUDivExpr(const SCEV *lhs, const SCEV *rhs) 338 : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} 339 340 public: 341 virtual void Profile(FoldingSetNodeID &ID) const; 342 343 const SCEV *getLHS() const { return LHS; } 344 const SCEV *getRHS() const { return RHS; } 345 346 virtual bool isLoopInvariant(const Loop *L) const { 347 return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 348 } 349 350 virtual bool hasComputableLoopEvolution(const Loop *L) const { 351 return LHS->hasComputableLoopEvolution(L) && 352 RHS->hasComputableLoopEvolution(L); 353 } 354 355 const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, 356 const SCEV *Conc, 357 ScalarEvolution &SE) const { 358 const SCEV *L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 359 const SCEV *R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 360 if (L == LHS && R == RHS) 361 return this; 362 else 363 return SE.getUDivExpr(L, R); 364 } 365 366 bool dominates(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 SmallVectorImpl<const SCEV *> &ops, const Loop *l) 395 : SCEVNAryExpr(scAddRecExpr, ops), L(l) { 396 for (size_t i = 0, e = Operands.size(); i != e; ++i) 397 assert(Operands[i]->isLoopInvariant(l) && 398 "Operands of AddRec must be loop-invariant!"); 399 } 400 401 public: 402 virtual void Profile(FoldingSetNodeID &ID) const; 403 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 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<const SCEV *> &ops) 479 : SCEVCommutativeExpr(scSMaxExpr, ops) { 480 } 481 482 public: 483 virtual const char *getOperationStr() const { return " smax "; } 484 485 /// Methods for support type inquiry through isa, cast, and dyn_cast: 486 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 487 static inline bool classof(const SCEV *S) { 488 return S->getSCEVType() == scSMaxExpr; 489 } 490 }; 491 492 493 //===--------------------------------------------------------------------===// 494 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 495 /// 496 class SCEVUMaxExpr : public SCEVCommutativeExpr { 497 friend class ScalarEvolution; 498 499 explicit SCEVUMaxExpr(const SmallVectorImpl<const SCEV *> &ops) 500 : SCEVCommutativeExpr(scUMaxExpr, ops) { 501 } 502 503 public: 504 virtual const char *getOperationStr() const { return " umax "; } 505 506 /// Methods for support type inquiry through isa, cast, and dyn_cast: 507 static inline bool classof(const SCEVUMaxExpr *S) { return true; } 508 static inline bool classof(const SCEV *S) { 509 return S->getSCEVType() == scUMaxExpr; 510 } 511 }; 512 513 514 //===--------------------------------------------------------------------===// 515 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 516 /// value, and only represent it as it's LLVM Value. This is the "bottom" 517 /// value for the analysis. 518 /// 519 class SCEVUnknown : public SCEV { 520 friend class ScalarEvolution; 521 522 Value *V; 523 explicit SCEVUnknown(Value *v) : 524 SCEV(scUnknown), V(v) {} 525 526 public: 527 virtual void Profile(FoldingSetNodeID &ID) const; 528 529 Value *getValue() const { return V; } 530 531 virtual bool isLoopInvariant(const Loop *L) const; 532 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 533 return false; // not computable 534 } 535 536 const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, 537 const SCEV *Conc, 538 ScalarEvolution &SE) const { 539 if (&*Sym == this) return Conc; 540 return this; 541 } 542 543 bool dominates(BasicBlock *BB, DominatorTree *DT) const; 544 545 virtual const Type *getType() const; 546 547 virtual void print(raw_ostream &OS) const; 548 549 /// Methods for support type inquiry through isa, cast, and dyn_cast: 550 static inline bool classof(const SCEVUnknown *S) { return true; } 551 static inline bool classof(const SCEV *S) { 552 return S->getSCEVType() == scUnknown; 553 } 554 }; 555 556 /// SCEVVisitor - This class defines a simple visitor class that may be used 557 /// for various SCEV analysis purposes. 558 template<typename SC, typename RetVal=void> 559 struct SCEVVisitor { 560 RetVal visit(const SCEV *S) { 561 switch (S->getSCEVType()) { 562 case scConstant: 563 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 564 case scTruncate: 565 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 566 case scZeroExtend: 567 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 568 case scSignExtend: 569 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 570 case scAddExpr: 571 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 572 case scMulExpr: 573 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 574 case scUDivExpr: 575 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 576 case scAddRecExpr: 577 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 578 case scSMaxExpr: 579 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 580 case scUMaxExpr: 581 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 582 case scUnknown: 583 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 584 case scCouldNotCompute: 585 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 586 default: 587 assert(0 && "Unknown SCEV type!"); 588 abort(); 589 } 590 } 591 592 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 593 assert(0 && "Invalid use of SCEVCouldNotCompute!"); 594 abort(); 595 return RetVal(); 596 } 597 }; 598} 599 600#endif 601