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