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