ScalarEvolutionExpressions.h revision 263508
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_SCALAREVOLUTIONEXPRESSIONS_H 15#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 16 17#include "llvm/ADT/SmallPtrSet.h" 18#include "llvm/Analysis/ScalarEvolution.h" 19#include "llvm/Support/ErrorHandling.h" 20 21namespace 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 SCEV *S) { 50 return S->getSCEVType() == scConstant; 51 } 52 }; 53 54 //===--------------------------------------------------------------------===// 55 /// SCEVCastExpr - This is the base class for unary cast operator classes. 56 /// 57 class SCEVCastExpr : public SCEV { 58 protected: 59 const SCEV *Op; 60 Type *Ty; 61 62 SCEVCastExpr(const FoldingSetNodeIDRef ID, 63 unsigned SCEVTy, const SCEV *op, Type *ty); 64 65 public: 66 const SCEV *getOperand() const { return Op; } 67 Type *getType() const { return Ty; } 68 69 /// Methods for support type inquiry through isa, cast, and dyn_cast: 70 static inline bool classof(const SCEV *S) { 71 return S->getSCEVType() == scTruncate || 72 S->getSCEVType() == scZeroExtend || 73 S->getSCEVType() == scSignExtend; 74 } 75 }; 76 77 //===--------------------------------------------------------------------===// 78 /// SCEVTruncateExpr - This class represents a truncation of an integer value 79 /// to a smaller integer value. 80 /// 81 class SCEVTruncateExpr : public SCEVCastExpr { 82 friend class ScalarEvolution; 83 84 SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 85 const SCEV *op, Type *ty); 86 87 public: 88 /// Methods for support type inquiry through isa, cast, and dyn_cast: 89 static inline bool classof(const SCEV *S) { 90 return S->getSCEVType() == scTruncate; 91 } 92 }; 93 94 //===--------------------------------------------------------------------===// 95 /// SCEVZeroExtendExpr - This class represents a zero extension of a small 96 /// integer value to a larger integer value. 97 /// 98 class SCEVZeroExtendExpr : public SCEVCastExpr { 99 friend class ScalarEvolution; 100 101 SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 102 const SCEV *op, Type *ty); 103 104 public: 105 /// Methods for support type inquiry through isa, cast, and dyn_cast: 106 static inline bool classof(const SCEV *S) { 107 return S->getSCEVType() == scZeroExtend; 108 } 109 }; 110 111 //===--------------------------------------------------------------------===// 112 /// SCEVSignExtendExpr - This class represents a sign extension of a small 113 /// integer value to a larger integer value. 114 /// 115 class SCEVSignExtendExpr : public SCEVCastExpr { 116 friend class ScalarEvolution; 117 118 SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 119 const SCEV *op, Type *ty); 120 121 public: 122 /// Methods for support type inquiry through isa, cast, and dyn_cast: 123 static inline bool classof(const SCEV *S) { 124 return S->getSCEVType() == scSignExtend; 125 } 126 }; 127 128 129 //===--------------------------------------------------------------------===// 130 /// SCEVNAryExpr - This node is a base class providing common 131 /// functionality for n'ary operators. 132 /// 133 class SCEVNAryExpr : public SCEV { 134 protected: 135 // Since SCEVs are immutable, ScalarEvolution allocates operand 136 // arrays with its SCEVAllocator, so this class just needs a simple 137 // pointer rather than a more elaborate vector-like data structure. 138 // This also avoids the need for a non-trivial destructor. 139 const SCEV *const *Operands; 140 size_t NumOperands; 141 142 SCEVNAryExpr(const FoldingSetNodeIDRef ID, 143 enum SCEVTypes T, const SCEV *const *O, size_t N) 144 : SCEV(ID, T), Operands(O), NumOperands(N) {} 145 146 public: 147 size_t getNumOperands() const { return NumOperands; } 148 const SCEV *getOperand(unsigned i) const { 149 assert(i < NumOperands && "Operand index out of range!"); 150 return Operands[i]; 151 } 152 153 typedef const SCEV *const *op_iterator; 154 op_iterator op_begin() const { return Operands; } 155 op_iterator op_end() const { return Operands + NumOperands; } 156 157 Type *getType() const { return getOperand(0)->getType(); } 158 159 NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 160 return (NoWrapFlags)(SubclassData & Mask); 161 } 162 163 /// Methods for support type inquiry through isa, cast, and dyn_cast: 164 static inline bool classof(const SCEV *S) { 165 return S->getSCEVType() == scAddExpr || 166 S->getSCEVType() == scMulExpr || 167 S->getSCEVType() == scSMaxExpr || 168 S->getSCEVType() == scUMaxExpr || 169 S->getSCEVType() == scAddRecExpr; 170 } 171 }; 172 173 //===--------------------------------------------------------------------===// 174 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 175 /// operators. 176 /// 177 class SCEVCommutativeExpr : public SCEVNAryExpr { 178 protected: 179 SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 180 enum SCEVTypes T, const SCEV *const *O, size_t N) 181 : SCEVNAryExpr(ID, T, O, N) {} 182 183 public: 184 /// Methods for support type inquiry through isa, cast, and dyn_cast: 185 static inline bool classof(const SCEV *S) { 186 return S->getSCEVType() == scAddExpr || 187 S->getSCEVType() == scMulExpr || 188 S->getSCEVType() == scSMaxExpr || 189 S->getSCEVType() == scUMaxExpr; 190 } 191 192 /// Set flags for a non-recurrence without clearing previously set flags. 193 void setNoWrapFlags(NoWrapFlags Flags) { 194 SubclassData |= Flags; 195 } 196 }; 197 198 199 //===--------------------------------------------------------------------===// 200 /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 201 /// 202 class SCEVAddExpr : public SCEVCommutativeExpr { 203 friend class ScalarEvolution; 204 205 SCEVAddExpr(const FoldingSetNodeIDRef ID, 206 const SCEV *const *O, size_t N) 207 : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 208 } 209 210 public: 211 Type *getType() const { 212 // Use the type of the last operand, which is likely to be a pointer 213 // type, if there is one. This doesn't usually matter, but it can help 214 // reduce casts when the expressions are expanded. 215 return getOperand(getNumOperands() - 1)->getType(); 216 } 217 218 /// Methods for support type inquiry through isa, cast, and dyn_cast: 219 static inline bool classof(const SCEV *S) { 220 return S->getSCEVType() == scAddExpr; 221 } 222 }; 223 224 //===--------------------------------------------------------------------===// 225 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 226 /// 227 class SCEVMulExpr : public SCEVCommutativeExpr { 228 friend class ScalarEvolution; 229 230 SCEVMulExpr(const FoldingSetNodeIDRef ID, 231 const SCEV *const *O, size_t N) 232 : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 233 } 234 235 public: 236 /// Methods for support type inquiry through isa, cast, and dyn_cast: 237 static inline bool classof(const SCEV *S) { 238 return S->getSCEVType() == scMulExpr; 239 } 240 }; 241 242 243 //===--------------------------------------------------------------------===// 244 /// SCEVUDivExpr - This class represents a binary unsigned division operation. 245 /// 246 class SCEVUDivExpr : public SCEV { 247 friend class ScalarEvolution; 248 249 const SCEV *LHS; 250 const SCEV *RHS; 251 SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 252 : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 253 254 public: 255 const SCEV *getLHS() const { return LHS; } 256 const SCEV *getRHS() const { return RHS; } 257 258 Type *getType() const { 259 // In most cases the types of LHS and RHS will be the same, but in some 260 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 261 // depend on the type for correctness, but handling types carefully can 262 // avoid extra casts in the SCEVExpander. The LHS is more likely to be 263 // a pointer type than the RHS, so use the RHS' type here. 264 return getRHS()->getType(); 265 } 266 267 /// Methods for support type inquiry through isa, cast, and dyn_cast: 268 static inline bool classof(const SCEV *S) { 269 return S->getSCEVType() == scUDivExpr; 270 } 271 }; 272 273 274 //===--------------------------------------------------------------------===// 275 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 276 /// count of the specified loop. This is the primary focus of the 277 /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 278 /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 279 /// created and analyzed. 280 /// 281 /// All operands of an AddRec are required to be loop invariant. 282 /// 283 class SCEVAddRecExpr : public SCEVNAryExpr { 284 friend class ScalarEvolution; 285 286 const Loop *L; 287 288 SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 289 const SCEV *const *O, size_t N, const Loop *l) 290 : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 291 292 public: 293 const SCEV *getStart() const { return Operands[0]; } 294 const Loop *getLoop() const { return L; } 295 296 /// getStepRecurrence - This method constructs and returns the recurrence 297 /// indicating how much this expression steps by. If this is a polynomial 298 /// of degree N, it returns a chrec of degree N-1. 299 /// We cannot determine whether the step recurrence has self-wraparound. 300 const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 301 if (isAffine()) return getOperand(1); 302 return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 303 op_end()), 304 getLoop(), FlagAnyWrap); 305 } 306 307 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 308 /// an expressions A+B*x where A and B are loop invariant values. 309 bool isAffine() const { 310 // We know that the start value is invariant. This expression is thus 311 // affine iff the step is also invariant. 312 return getNumOperands() == 2; 313 } 314 315 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 316 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 317 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 318 bool isQuadratic() const { 319 return getNumOperands() == 3; 320 } 321 322 /// Set flags for a recurrence without clearing any previously set flags. 323 /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 324 /// to make it easier to propagate flags. 325 void setNoWrapFlags(NoWrapFlags Flags) { 326 if (Flags & (FlagNUW | FlagNSW)) 327 Flags = ScalarEvolution::setFlags(Flags, FlagNW); 328 SubclassData |= Flags; 329 } 330 331 /// evaluateAtIteration - Return the value of this chain of recurrences at 332 /// the specified iteration number. 333 const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 334 335 /// getNumIterationsInRange - Return the number of iterations of this loop 336 /// that produce values in the specified constant range. Another way of 337 /// looking at this is that it returns the first iteration number where the 338 /// value is not in the condition, thus computing the exit count. If the 339 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 340 /// returned. 341 const SCEV *getNumIterationsInRange(ConstantRange Range, 342 ScalarEvolution &SE) const; 343 344 /// getPostIncExpr - Return an expression representing the value of 345 /// this expression one iteration of the loop ahead. 346 const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 347 return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 348 } 349 350 /// Methods for support type inquiry through isa, cast, and dyn_cast: 351 static inline bool classof(const SCEV *S) { 352 return S->getSCEVType() == scAddRecExpr; 353 } 354 355 /// Splits the SCEV into two vectors of SCEVs representing the subscripts 356 /// and sizes of an array access. Returns the remainder of the 357 /// delinearization that is the offset start of the array. 358 const SCEV *delinearize(ScalarEvolution &SE, 359 SmallVectorImpl<const SCEV *> &Subscripts, 360 SmallVectorImpl<const SCEV *> &Sizes) const; 361 }; 362 363 //===--------------------------------------------------------------------===// 364 /// SCEVSMaxExpr - This class represents a signed maximum selection. 365 /// 366 class SCEVSMaxExpr : public SCEVCommutativeExpr { 367 friend class ScalarEvolution; 368 369 SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 370 const SCEV *const *O, size_t N) 371 : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 372 // Max never overflows. 373 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 374 } 375 376 public: 377 /// Methods for support type inquiry through isa, cast, and dyn_cast: 378 static inline bool classof(const SCEV *S) { 379 return S->getSCEVType() == scSMaxExpr; 380 } 381 }; 382 383 384 //===--------------------------------------------------------------------===// 385 /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 386 /// 387 class SCEVUMaxExpr : public SCEVCommutativeExpr { 388 friend class ScalarEvolution; 389 390 SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 391 const SCEV *const *O, size_t N) 392 : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 393 // Max never overflows. 394 setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 395 } 396 397 public: 398 /// Methods for support type inquiry through isa, cast, and dyn_cast: 399 static inline bool classof(const SCEV *S) { 400 return S->getSCEVType() == scUMaxExpr; 401 } 402 }; 403 404 //===--------------------------------------------------------------------===// 405 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 406 /// value, and only represent it as its LLVM Value. This is the "bottom" 407 /// value for the analysis. 408 /// 409 class SCEVUnknown : public SCEV, private CallbackVH { 410 friend class ScalarEvolution; 411 412 // Implement CallbackVH. 413 virtual void deleted(); 414 virtual void allUsesReplacedWith(Value *New); 415 416 /// SE - The parent ScalarEvolution value. This is used to update 417 /// the parent's maps when the value associated with a SCEVUnknown 418 /// is deleted or RAUW'd. 419 ScalarEvolution *SE; 420 421 /// Next - The next pointer in the linked list of all 422 /// SCEVUnknown instances owned by a ScalarEvolution. 423 SCEVUnknown *Next; 424 425 SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 426 ScalarEvolution *se, SCEVUnknown *next) : 427 SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 428 429 public: 430 Value *getValue() const { return getValPtr(); } 431 432 /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 433 /// constant representing a type size, alignment, or field offset in 434 /// a target-independent manner, and hasn't happened to have been 435 /// folded with other operations into something unrecognizable. This 436 /// is mainly only useful for pretty-printing and other situations 437 /// where it isn't absolutely required for these to succeed. 438 bool isSizeOf(Type *&AllocTy) const; 439 bool isAlignOf(Type *&AllocTy) const; 440 bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 441 442 Type *getType() const { return getValPtr()->getType(); } 443 444 /// Methods for support type inquiry through isa, cast, and dyn_cast: 445 static inline bool classof(const SCEV *S) { 446 return S->getSCEVType() == scUnknown; 447 } 448 }; 449 450 /// SCEVVisitor - This class defines a simple visitor class that may be used 451 /// for various SCEV analysis purposes. 452 template<typename SC, typename RetVal=void> 453 struct SCEVVisitor { 454 RetVal visit(const SCEV *S) { 455 switch (S->getSCEVType()) { 456 case scConstant: 457 return ((SC*)this)->visitConstant((const SCEVConstant*)S); 458 case scTruncate: 459 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 460 case scZeroExtend: 461 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 462 case scSignExtend: 463 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 464 case scAddExpr: 465 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 466 case scMulExpr: 467 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 468 case scUDivExpr: 469 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 470 case scAddRecExpr: 471 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 472 case scSMaxExpr: 473 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 474 case scUMaxExpr: 475 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 476 case scUnknown: 477 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 478 case scCouldNotCompute: 479 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 480 default: 481 llvm_unreachable("Unknown SCEV type!"); 482 } 483 } 484 485 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 486 llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 487 } 488 }; 489 490 /// Visit all nodes in the expression tree using worklist traversal. 491 /// 492 /// Visitor implements: 493 /// // return true to follow this node. 494 /// bool follow(const SCEV *S); 495 /// // return true to terminate the search. 496 /// bool isDone(); 497 template<typename SV> 498 class SCEVTraversal { 499 SV &Visitor; 500 SmallVector<const SCEV *, 8> Worklist; 501 SmallPtrSet<const SCEV *, 8> Visited; 502 503 void push(const SCEV *S) { 504 if (Visited.insert(S) && Visitor.follow(S)) 505 Worklist.push_back(S); 506 } 507 public: 508 SCEVTraversal(SV& V): Visitor(V) {} 509 510 void visitAll(const SCEV *Root) { 511 push(Root); 512 while (!Worklist.empty() && !Visitor.isDone()) { 513 const SCEV *S = Worklist.pop_back_val(); 514 515 switch (S->getSCEVType()) { 516 case scConstant: 517 case scUnknown: 518 break; 519 case scTruncate: 520 case scZeroExtend: 521 case scSignExtend: 522 push(cast<SCEVCastExpr>(S)->getOperand()); 523 break; 524 case scAddExpr: 525 case scMulExpr: 526 case scSMaxExpr: 527 case scUMaxExpr: 528 case scAddRecExpr: { 529 const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 530 for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 531 E = NAry->op_end(); I != E; ++I) { 532 push(*I); 533 } 534 break; 535 } 536 case scUDivExpr: { 537 const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 538 push(UDiv->getLHS()); 539 push(UDiv->getRHS()); 540 break; 541 } 542 case scCouldNotCompute: 543 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 544 default: 545 llvm_unreachable("Unknown SCEV kind!"); 546 } 547 } 548 } 549 }; 550 551 /// Use SCEVTraversal to visit all nodes in the givien expression tree. 552 template<typename SV> 553 void visitAll(const SCEV *Root, SV& Visitor) { 554 SCEVTraversal<SV> T(Visitor); 555 T.visitAll(Root); 556 } 557 558 typedef DenseMap<const Value*, Value*> ValueToValueMap; 559 560 /// The SCEVParameterRewriter takes a scalar evolution expression and updates 561 /// the SCEVUnknown components following the Map (Value -> Value). 562 struct SCEVParameterRewriter 563 : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { 564 public: 565 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 566 ValueToValueMap &Map) { 567 SCEVParameterRewriter Rewriter(SE, Map); 568 return Rewriter.visit(Scev); 569 } 570 571 SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) 572 : SE(S), Map(M) {} 573 574 const SCEV *visitConstant(const SCEVConstant *Constant) { 575 return Constant; 576 } 577 578 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 579 const SCEV *Operand = visit(Expr->getOperand()); 580 return SE.getTruncateExpr(Operand, Expr->getType()); 581 } 582 583 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 584 const SCEV *Operand = visit(Expr->getOperand()); 585 return SE.getZeroExtendExpr(Operand, Expr->getType()); 586 } 587 588 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 589 const SCEV *Operand = visit(Expr->getOperand()); 590 return SE.getSignExtendExpr(Operand, Expr->getType()); 591 } 592 593 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 594 SmallVector<const SCEV *, 2> Operands; 595 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 596 Operands.push_back(visit(Expr->getOperand(i))); 597 return SE.getAddExpr(Operands); 598 } 599 600 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 601 SmallVector<const SCEV *, 2> Operands; 602 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 603 Operands.push_back(visit(Expr->getOperand(i))); 604 return SE.getMulExpr(Operands); 605 } 606 607 const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 608 return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 609 } 610 611 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 612 SmallVector<const SCEV *, 2> Operands; 613 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 614 Operands.push_back(visit(Expr->getOperand(i))); 615 return SE.getAddRecExpr(Operands, Expr->getLoop(), 616 Expr->getNoWrapFlags()); 617 } 618 619 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 620 SmallVector<const SCEV *, 2> Operands; 621 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 622 Operands.push_back(visit(Expr->getOperand(i))); 623 return SE.getSMaxExpr(Operands); 624 } 625 626 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 627 SmallVector<const SCEV *, 2> Operands; 628 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 629 Operands.push_back(visit(Expr->getOperand(i))); 630 return SE.getUMaxExpr(Operands); 631 } 632 633 const SCEV *visitUnknown(const SCEVUnknown *Expr) { 634 Value *V = Expr->getValue(); 635 if (Map.count(V)) 636 return SE.getUnknown(Map[V]); 637 return Expr; 638 } 639 640 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 641 return Expr; 642 } 643 644 private: 645 ScalarEvolution &SE; 646 ValueToValueMap ⤅ 647 }; 648 649 typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; 650 651 /// The SCEVApplyRewriter takes a scalar evolution expression and applies 652 /// the Map (Loop -> SCEV) to all AddRecExprs. 653 struct SCEVApplyRewriter 654 : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> { 655 public: 656 static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, 657 ScalarEvolution &SE) { 658 SCEVApplyRewriter Rewriter(SE, Map); 659 return Rewriter.visit(Scev); 660 } 661 662 SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) 663 : SE(S), Map(M) {} 664 665 const SCEV *visitConstant(const SCEVConstant *Constant) { 666 return Constant; 667 } 668 669 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 670 const SCEV *Operand = visit(Expr->getOperand()); 671 return SE.getTruncateExpr(Operand, Expr->getType()); 672 } 673 674 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 675 const SCEV *Operand = visit(Expr->getOperand()); 676 return SE.getZeroExtendExpr(Operand, Expr->getType()); 677 } 678 679 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 680 const SCEV *Operand = visit(Expr->getOperand()); 681 return SE.getSignExtendExpr(Operand, Expr->getType()); 682 } 683 684 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 685 SmallVector<const SCEV *, 2> Operands; 686 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 687 Operands.push_back(visit(Expr->getOperand(i))); 688 return SE.getAddExpr(Operands); 689 } 690 691 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 692 SmallVector<const SCEV *, 2> Operands; 693 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 694 Operands.push_back(visit(Expr->getOperand(i))); 695 return SE.getMulExpr(Operands); 696 } 697 698 const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 699 return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 700 } 701 702 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 703 SmallVector<const SCEV *, 2> Operands; 704 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 705 Operands.push_back(visit(Expr->getOperand(i))); 706 707 const Loop *L = Expr->getLoop(); 708 const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); 709 710 if (0 == Map.count(L)) 711 return Res; 712 713 const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; 714 return Rec->evaluateAtIteration(Map[L], SE); 715 } 716 717 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 718 SmallVector<const SCEV *, 2> Operands; 719 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 720 Operands.push_back(visit(Expr->getOperand(i))); 721 return SE.getSMaxExpr(Operands); 722 } 723 724 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 725 SmallVector<const SCEV *, 2> Operands; 726 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 727 Operands.push_back(visit(Expr->getOperand(i))); 728 return SE.getUMaxExpr(Operands); 729 } 730 731 const SCEV *visitUnknown(const SCEVUnknown *Expr) { 732 return Expr; 733 } 734 735 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 736 return Expr; 737 } 738 739 private: 740 ScalarEvolution &SE; 741 LoopToScevMapT ⤅ 742 }; 743 744/// Applies the Map (Loop -> SCEV) to the given Scev. 745static inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, 746 ScalarEvolution &SE) { 747 return SCEVApplyRewriter::rewrite(Scev, Map, SE); 748} 749 750} 751 752#endif 753