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/ADT/SmallPtrSet.h" 19 #include "llvm/Support/ErrorHandling.h" 20 21 namespace llvm { 22 class ConstantInt; 23 class ConstantRange; 24 class DominatorTree; 25 26 enum SCEVTypes { 27 // These should be ordered in terms of increasing complexity to make the 28 // folders simpler. 29 scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 30 scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 31 scUnknown, scCouldNotCompute 32 }; 33 34 //===--------------------------------------------------------------------===// 35 /// SCEVConstant - This class represents a constant integer value. 36 /// 37 class SCEVConstant : public SCEV { 38 friend class ScalarEvolution; 39 40 ConstantInt *V; 41 SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 42 SCEV(ID, scConstant), V(v) {} 43 public: 44 ConstantInt *getValue() const { return V; } 45 46 Type *getType() const { return V->getType(); } 47 48 /// Methods for support type inquiry through isa, cast, and dyn_cast: 49 static inline bool classof(const SCEVConstant *S) { return true; } 50 static inline bool classof(const SCEV *S) { 51 return S->getSCEVType() == scConstant; 52 } 53 }; 54 55 //===--------------------------------------------------------------------===// 56 /// SCEVCastExpr - This is the base class for unary cast operator classes. 57 /// 58 class SCEVCastExpr : public SCEV { 59 protected: 60 const SCEV *Op; 61 Type *Ty; 62 63 SCEVCastExpr(const FoldingSetNodeIDRef ID, 64 unsigned SCEVTy, const SCEV *op, Type *ty); 65 66 public: 67 const SCEV *getOperand() const { return Op; } 68 Type *getType() const { return Ty; } 69 70 /// Methods for support type inquiry through isa, cast, and dyn_cast: 71 static inline bool classof(const SCEVCastExpr *S) { return true; } 72 static inline bool classof(const SCEV *S) { 73 return S->getSCEVType() == scTruncate || 74 S->getSCEVType() == scZeroExtend || 75 S->getSCEVType() == scSignExtend; 76 } 77 }; 78 79 //===--------------------------------------------------------------------===// 80 /// SCEVTruncateExpr - This class represents a truncation of an integer value 81 /// to a smaller integer value. 82 /// 83 class SCEVTruncateExpr : public SCEVCastExpr { 84 friend class ScalarEvolution; 85 86 SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 87 const SCEV *op, Type *ty); 88 89 public: 90 /// Methods for support type inquiry through isa, cast, and dyn_cast: 91 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 92 static inline bool classof(const SCEV *S) { 93 return S->getSCEVType() == scTruncate; 94 } 95 }; 96 97 //===--------------------------------------------------------------------===// 98 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 99 /// integer value to a larger integer value. 100 /// 101 class SCEVZeroExtendExpr : public SCEVCastExpr { 102 friend class ScalarEvolution; 103 104 SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 105 const SCEV *op, Type *ty); 106 107 public: 108 /// Methods for support type inquiry through isa, cast, and dyn_cast: 109 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 110 static inline bool classof(const SCEV *S) { 111 return S->getSCEVType() == scZeroExtend; 112 } 113 }; 114 115 //===--------------------------------------------------------------------===// 116 /// SCEVSignExtendExpr - This class represents a sign extension of a small 117 /// integer value to a larger integer value. 118 /// 119 class SCEVSignExtendExpr : public SCEVCastExpr { 120 friend class ScalarEvolution; 121 122 SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 123 const SCEV *op, Type *ty); 124 125 public: 126 /// Methods for support type inquiry through isa, cast, and dyn_cast: 127 static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 128 static inline bool classof(const SCEV *S) { 129 return S->getSCEVType() == scSignExtend; 130 } 131 }; 132 133 134 //===--------------------------------------------------------------------===// 135 /// SCEVNAryExpr - This node is a base class providing common 136 /// functionality for n'ary operators. 137 /// 138 class SCEVNAryExpr : public SCEV { 139 protected: 140 // Since SCEVs are immutable, ScalarEvolution allocates operand 141 // arrays with its SCEVAllocator, so this class just needs a simple 142 // pointer rather than a more elaborate vector-like data structure. 143 // This also avoids the need for a non-trivial destructor. 144 const SCEV *const *Operands; 145 size_t NumOperands; 146 147 SCEVNAryExpr(const FoldingSetNodeIDRef ID, 148 enum SCEVTypes T, const SCEV *const *O, size_t N) 149 : SCEV(ID, T), Operands(O), NumOperands(N) {} 150 151 public: 152 size_t getNumOperands() const { return NumOperands; } 153 const SCEV *getOperand(unsigned i) const { 154 assert(i < NumOperands && "Operand index out of range!"); 155 return Operands[i]; 156 } 157 158 typedef const SCEV *const *op_iterator; 159 op_iterator op_begin() const { return Operands; } 160 op_iterator op_end() const { return Operands + NumOperands; } 161 162 Type *getType() const { return getOperand(0)->getType(); } 163 164 NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 165 return (NoWrapFlags)(SubclassData & Mask); 166 } 167 168 /// Methods for support type inquiry through isa, cast, and dyn_cast: 169 static inline bool classof(const SCEVNAryExpr *S) { return true; } 170 static inline bool classof(const SCEV *S) { 171 return S->getSCEVType() == scAddExpr || 172 S->getSCEVType() == scMulExpr || 173 S->getSCEVType() == scSMaxExpr || 174 S->getSCEVType() == scUMaxExpr || 175 S->getSCEVType() == scAddRecExpr; 176 } 177 }; 178 179 //===--------------------------------------------------------------------===// 180 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 181 /// operators. 182 /// 183 class SCEVCommutativeExpr : public SCEVNAryExpr { 184 protected: 185 SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 186 enum SCEVTypes T, const SCEV *const *O, size_t N) 187 : SCEVNAryExpr(ID, T, O, N) {} 188 189 public: 190 /// Methods for support type inquiry through isa, cast, and dyn_cast: 191 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 192 static inline bool classof(const SCEV *S) { 193 return S->getSCEVType() == scAddExpr || 194 S->getSCEVType() == scMulExpr || 195 S->getSCEVType() == scSMaxExpr || 196 S->getSCEVType() == scUMaxExpr; 197 } 198 199 /// Set flags for a non-recurrence without clearing previously set flags. 200 void setNoWrapFlags(NoWrapFlags Flags) { 201 SubclassData |= Flags; 202 } 203 }; 204 205 206 //===--------------------------------------------------------------------===// 207 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 208 /// 209 class SCEVAddExpr : public SCEVCommutativeExpr { 210 friend class ScalarEvolution; 211 212 SCEVAddExpr(const FoldingSetNodeIDRef ID, 213 const SCEV *const *O, size_t N) 214 : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 215 } 216 217 public: 218 Type *getType() const { 219 // Use the type of the last operand, which is likely to be a pointer 220 // type, if there is one. This doesn't usually matter, but it can help 221 // reduce casts when the expressions are expanded. 222 return getOperand(getNumOperands() - 1)->getType(); 223 } 224 225 /// Methods for support type inquiry through isa, cast, and dyn_cast: 226 static inline bool classof(const SCEVAddExpr *S) { return true; } 227 static inline bool classof(const SCEV *S) { 228 return S->getSCEVType() == scAddExpr; 229 } 230 }; 231 232 //===--------------------------------------------------------------------===// 233 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 234 /// 235 class SCEVMulExpr : public SCEVCommutativeExpr { 236 friend class ScalarEvolution; 237 238 SCEVMulExpr(const FoldingSetNodeIDRef ID, 239 const SCEV *const *O, size_t N) 240 : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 241 } 242 243 public: 244 /// Methods for support type inquiry through isa, cast, and dyn_cast: 245 static inline bool classof(const SCEVMulExpr *S) { return true; } 246 static inline bool classof(const SCEV *S) { 247 return S->getSCEVType() == scMulExpr; 248 } 249 }; 250 251 252 //===--------------------------------------------------------------------===// 253 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 254 /// 255 class SCEVUDivExpr : public SCEV { 256 friend class ScalarEvolution; 257 258 const SCEV *LHS; 259 const SCEV *RHS; 260 SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 261 : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 262 263 public: 264 const SCEV *getLHS() const { return LHS; } 265 const SCEV *getRHS() const { return RHS; } 266 267 Type *getType() const { 268 // In most cases the types of LHS and RHS will be the same, but in some 269 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 270 // depend on the type for correctness, but handling types carefully can 271 // avoid extra casts in the SCEVExpander. The LHS is more likely to be 272 // a pointer type than the RHS, so use the RHS' type here. 273 return getRHS()->getType(); 274 } 275 276 /// Methods for support type inquiry through isa, cast, and dyn_cast: 277 static inline bool classof(const SCEVUDivExpr *S) { return true; } 278 static inline bool classof(const SCEV *S) { 279 return S->getSCEVType() == scUDivExpr; 280 } 281 }; 282 283 284 //===--------------------------------------------------------------------===// 285 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 286 /// count of the specified loop. This is the primary focus of the 287 /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 288 /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 289 /// created and analyzed. 290 /// 291 /// All operands of an AddRec are required to be loop invariant. 292 /// 293 class SCEVAddRecExpr : public SCEVNAryExpr { 294 friend class ScalarEvolution; 295 296 const Loop *L; 297 298 SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 299 const SCEV *const *O, size_t N, const Loop *l) 300 : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 301 302 public: 303 const SCEV *getStart() const { return Operands[0]; } 304 const Loop *getLoop() const { return L; } 305 306 /// getStepRecurrence - This method constructs and returns the recurrence 307 /// indicating how much this expression steps by. If this is a polynomial 308 /// of degree N, it returns a chrec of degree N-1. 309 /// We cannot determine whether the step recurrence has self-wraparound. 310 const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 311 if (isAffine()) return getOperand(1); 312 return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 313 op_end()), 314 getLoop(), FlagAnyWrap); 315 } 316 317 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 318 /// an expressions A+B*x where A and B are loop invariant values. 319 bool isAffine() const { 320 // We know that the start value is invariant. This expression is thus 321 // affine iff the step is also invariant. 322 return getNumOperands() == 2; 323 } 324 325 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 326 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 327 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 328 bool isQuadratic() const { 329 return getNumOperands() == 3; 330 } 331 332 /// Set flags for a recurrence without clearing any previously set flags. 333 /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 334 /// to make it easier to propagate flags. 335 void setNoWrapFlags(NoWrapFlags Flags) { 336 if (Flags & (FlagNUW | FlagNSW)) 337 Flags = ScalarEvolution::setFlags(Flags, FlagNW); 338 SubclassData |= Flags; 339 } 340 341 /// evaluateAtIteration - Return the value of this chain of recurrences at 342 /// the specified iteration number. 343 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 344 345 /// getNumIterationsInRange - Return the number of iterations of this loop 346 /// that produce values in the specified constant range. Another way of 347 /// looking at this is that it returns the first iteration number where the 348 /// value is not in the condition, thus computing the exit count. If the 349 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 350 /// returned. 351 const SCEV *getNumIterationsInRange(ConstantRange Range, 352 ScalarEvolution &SE) const; 353 354 /// getPostIncExpr - Return an expression representing the value of 355 /// this expression one iteration of the loop ahead. 356 const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 357 return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 358 } 359 360 /// Methods for support type inquiry through isa, cast, and dyn_cast: 361 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 362 static inline bool classof(const SCEV *S) { 363 return S->getSCEVType() == scAddRecExpr; 364 } 365 }; 366 367 368 //===--------------------------------------------------------------------===// 369 /// SCEVSMaxExpr - This class represents a signed maximum selection. 370 /// 371 class SCEVSMaxExpr : public SCEVCommutativeExpr { 372 friend class ScalarEvolution; 373 374 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 375 const SCEV *const *O, size_t N) 376 : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 377 // Max never overflows. 378 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 379 } 380 381 public: 382 /// Methods for support type inquiry through isa, cast, and dyn_cast: 383 static inline bool classof(const SCEVSMaxExpr *S) { return true; } 384 static inline bool classof(const SCEV *S) { 385 return S->getSCEVType() == scSMaxExpr; 386 } 387 }; 388 389 390 //===--------------------------------------------------------------------===// 391 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 392 /// 393 class SCEVUMaxExpr : public SCEVCommutativeExpr { 394 friend class ScalarEvolution; 395 396 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 397 const SCEV *const *O, size_t N) 398 : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 399 // Max never overflows. 400 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 401 } 402 403 public: 404 /// Methods for support type inquiry through isa, cast, and dyn_cast: 405 static inline bool classof(const SCEVUMaxExpr *S) { return true; } 406 static inline bool classof(const SCEV *S) { 407 return S->getSCEVType() == scUMaxExpr; 408 } 409 }; 410 411 //===--------------------------------------------------------------------===// 412 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 413 /// value, and only represent it as its LLVM Value. This is the "bottom" 414 /// value for the analysis. 415 /// 416 class SCEVUnknown : public SCEV, private CallbackVH { 417 friend class ScalarEvolution; 418 419 // Implement CallbackVH. 420 virtual void deleted(); 421 virtual void allUsesReplacedWith(Value *New); 422 423 /// SE - The parent ScalarEvolution value. This is used to update 424 /// the parent's maps when the value associated with a SCEVUnknown 425 /// is deleted or RAUW'd. 426 ScalarEvolution *SE; 427 428 /// Next - The next pointer in the linked list of all 429 /// SCEVUnknown instances owned by a ScalarEvolution. 430 SCEVUnknown *Next; 431 432 SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 433 ScalarEvolution *se, SCEVUnknown *next) : 434 SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 435 436 public: 437 Value *getValue() const { return getValPtr(); } 438 439 /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 440 /// constant representing a type size, alignment, or field offset in 441 /// a target-independent manner, and hasn't happened to have been 442 /// folded with other operations into something unrecognizable. This 443 /// is mainly only useful for pretty-printing and other situations 444 /// where it isn't absolutely required for these to succeed. 445 bool isSizeOf(Type *&AllocTy) const; 446 bool isAlignOf(Type *&AllocTy) const; 447 bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 448 449 Type *getType() const { return getValPtr()->getType(); } 450 451 /// Methods for support type inquiry through isa, cast, and dyn_cast: 452 static inline bool classof(const SCEVUnknown *S) { return true; } 453 static inline bool classof(const SCEV *S) { 454 return S->getSCEVType() == scUnknown; 455 } 456 }; 457 458 /// SCEVVisitor - This class defines a simple visitor class that may be used 459 /// for various SCEV analysis purposes. 460 template<typename SC, typename RetVal=void> 461 struct SCEVVisitor { 462 RetVal visit(const SCEV *S) { 463 switch (S->getSCEVType()) { 464 case scConstant: 465 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 466 case scTruncate: 467 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 468 case scZeroExtend: 469 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 470 case scSignExtend: 471 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 472 case scAddExpr: 473 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 474 case scMulExpr: 475 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 476 case scUDivExpr: 477 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 478 case scAddRecExpr: 479 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 480 case scSMaxExpr: 481 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 482 case scUMaxExpr: 483 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 484 case scUnknown: 485 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 486 case scCouldNotCompute: 487 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 488 default: 489 llvm_unreachable("Unknown SCEV type!"); 490 } 491 } 492 493 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 494 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 495 } 496 }; 497 498 /// Visit all nodes in the expression tree using worklist traversal. 499 /// 500 /// Visitor implements: 501 /// // return true to follow this node. 502 /// bool follow(const SCEV *S); 503 /// // return true to terminate the search. 504 /// bool isDone(); 505 template<typename SV> 506 class SCEVTraversal { 507 SV &Visitor; 508 SmallVector<const SCEV *, 8> Worklist; 509 SmallPtrSet<const SCEV *, 8> Visited; 510 511 void push(const SCEV *S) { 512 if (Visited.insert(S) && Visitor.follow(S)) 513 Worklist.push_back(S); 514 } 515 public: 516 SCEVTraversal(SV& V): Visitor(V) {} 517 518 void visitAll(const SCEV *Root) { 519 push(Root); 520 while (!Worklist.empty() && !Visitor.isDone()) { 521 const SCEV *S = Worklist.pop_back_val(); 522 523 switch (S->getSCEVType()) { 524 case scConstant: 525 case scUnknown: 526 break; 527 case scTruncate: 528 case scZeroExtend: 529 case scSignExtend: 530 push(cast<SCEVCastExpr>(S)->getOperand()); 531 break; 532 case scAddExpr: 533 case scMulExpr: 534 case scSMaxExpr: 535 case scUMaxExpr: 536 case scAddRecExpr: { 537 const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 538 for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 539 E = NAry->op_end(); I != E; ++I) { 540 push(*I); 541 } 542 break; 543 } 544 case scUDivExpr: { 545 const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 546 push(UDiv->getLHS()); 547 push(UDiv->getRHS()); 548 break; 549 } 550 case scCouldNotCompute: 551 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 552 default: 553 llvm_unreachable("Unknown SCEV kind!"); 554 } 555 } 556 } 557 }; 558 559 /// Use SCEVTraversal to visit all nodes in the givien expression tree. 560 template<typename SV> 561 void visitAll(const SCEV *Root, SV& Visitor) { 562 SCEVTraversal<SV> T(Visitor); 563 T.visitAll(Root); 564 } 565 } 566 567 #endif 568