ScalarEvolutionExpressions.h revision c23197a26f34f559ea9797de51e187087c039c42
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 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 SCEVSMaxExpr(const FoldingSetNodeID &ID, 479 const SmallVectorImpl<const SCEV *> &ops) 480 : SCEVCommutativeExpr(ID, scSMaxExpr, ops) { 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 SCEVUMaxExpr(const FoldingSetNodeID &ID, 501 const SmallVectorImpl<const SCEV *> &ops) 502 : SCEVCommutativeExpr(ID, scUMaxExpr, ops) { 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 SCEVUnknown(const FoldingSetNodeID &ID, Value *v) : 526 SCEV(ID, scUnknown), V(v) {} 527 528 public: 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 llvm_unreachable("Unknown SCEV type!"); 588 } 589 } 590 591 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 592 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 593 return RetVal(); 594 } 595 }; 596} 597 598#endif 599