1193323Sed//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the classes used to represent and build scalar expressions. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14249423Sdim#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 15249423Sdim#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H 16193323Sed 17249423Sdim#include "llvm/ADT/SmallPtrSet.h" 18193323Sed#include "llvm/Analysis/ScalarEvolution.h" 19198090Srdivacky#include "llvm/Support/ErrorHandling.h" 20193323Sed 21193323Sednamespace llvm { 22193323Sed class ConstantInt; 23193323Sed class ConstantRange; 24193323Sed class DominatorTree; 25193323Sed 26193323Sed enum SCEVTypes { 27193323Sed // These should be ordered in terms of increasing complexity to make the 28193323Sed // folders simpler. 29193323Sed scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 30198090Srdivacky scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 31203954Srdivacky scUnknown, scCouldNotCompute 32193323Sed }; 33193323Sed 34193323Sed //===--------------------------------------------------------------------===// 35193323Sed /// SCEVConstant - This class represents a constant integer value. 36193323Sed /// 37193323Sed class SCEVConstant : public SCEV { 38193323Sed friend class ScalarEvolution; 39193323Sed 40193323Sed ConstantInt *V; 41205407Srdivacky SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 42198090Srdivacky SCEV(ID, scConstant), V(v) {} 43193323Sed public: 44193323Sed ConstantInt *getValue() const { return V; } 45193323Sed 46226633Sdim Type *getType() const { return V->getType(); } 47193323Sed 48193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 49193323Sed static inline bool classof(const SCEV *S) { 50193323Sed return S->getSCEVType() == scConstant; 51193323Sed } 52193323Sed }; 53193323Sed 54193323Sed //===--------------------------------------------------------------------===// 55193323Sed /// SCEVCastExpr - This is the base class for unary cast operator classes. 56193323Sed /// 57193323Sed class SCEVCastExpr : public SCEV { 58193323Sed protected: 59198090Srdivacky const SCEV *Op; 60226633Sdim Type *Ty; 61193323Sed 62205407Srdivacky SCEVCastExpr(const FoldingSetNodeIDRef ID, 63226633Sdim unsigned SCEVTy, const SCEV *op, Type *ty); 64193323Sed 65193323Sed public: 66198090Srdivacky const SCEV *getOperand() const { return Op; } 67226633Sdim Type *getType() const { return Ty; } 68193323Sed 69193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 70193323Sed static inline bool classof(const SCEV *S) { 71193323Sed return S->getSCEVType() == scTruncate || 72193323Sed S->getSCEVType() == scZeroExtend || 73193323Sed S->getSCEVType() == scSignExtend; 74193323Sed } 75193323Sed }; 76193323Sed 77193323Sed //===--------------------------------------------------------------------===// 78193323Sed /// SCEVTruncateExpr - This class represents a truncation of an integer value 79193323Sed /// to a smaller integer value. 80193323Sed /// 81193323Sed class SCEVTruncateExpr : public SCEVCastExpr { 82193323Sed friend class ScalarEvolution; 83193323Sed 84205407Srdivacky SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 85226633Sdim const SCEV *op, Type *ty); 86193323Sed 87193323Sed public: 88193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 89193323Sed static inline bool classof(const SCEV *S) { 90193323Sed return S->getSCEVType() == scTruncate; 91193323Sed } 92193323Sed }; 93193323Sed 94193323Sed //===--------------------------------------------------------------------===// 95193323Sed /// SCEVZeroExtendExpr - This class represents a zero extension of a small 96193323Sed /// integer value to a larger integer value. 97193323Sed /// 98193323Sed class SCEVZeroExtendExpr : public SCEVCastExpr { 99193323Sed friend class ScalarEvolution; 100193323Sed 101205407Srdivacky SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 102226633Sdim const SCEV *op, Type *ty); 103193323Sed 104193323Sed public: 105193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 106193323Sed static inline bool classof(const SCEV *S) { 107193323Sed return S->getSCEVType() == scZeroExtend; 108193323Sed } 109193323Sed }; 110193323Sed 111193323Sed //===--------------------------------------------------------------------===// 112193323Sed /// SCEVSignExtendExpr - This class represents a sign extension of a small 113193323Sed /// integer value to a larger integer value. 114193323Sed /// 115193323Sed class SCEVSignExtendExpr : public SCEVCastExpr { 116193323Sed friend class ScalarEvolution; 117193323Sed 118205407Srdivacky SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 119226633Sdim const SCEV *op, Type *ty); 120193323Sed 121193323Sed public: 122193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 123193323Sed static inline bool classof(const SCEV *S) { 124193323Sed return S->getSCEVType() == scSignExtend; 125193323Sed } 126193323Sed }; 127193323Sed 128193323Sed 129193323Sed //===--------------------------------------------------------------------===// 130193323Sed /// SCEVNAryExpr - This node is a base class providing common 131193323Sed /// functionality for n'ary operators. 132193323Sed /// 133193323Sed class SCEVNAryExpr : public SCEV { 134193323Sed protected: 135205407Srdivacky // Since SCEVs are immutable, ScalarEvolution allocates operand 136205407Srdivacky // arrays with its SCEVAllocator, so this class just needs a simple 137205407Srdivacky // pointer rather than a more elaborate vector-like data structure. 138205407Srdivacky // This also avoids the need for a non-trivial destructor. 139205407Srdivacky const SCEV *const *Operands; 140205407Srdivacky size_t NumOperands; 141193323Sed 142205407Srdivacky SCEVNAryExpr(const FoldingSetNodeIDRef ID, 143205407Srdivacky enum SCEVTypes T, const SCEV *const *O, size_t N) 144205407Srdivacky : SCEV(ID, T), Operands(O), NumOperands(N) {} 145193323Sed 146193323Sed public: 147205407Srdivacky size_t getNumOperands() const { return NumOperands; } 148198090Srdivacky const SCEV *getOperand(unsigned i) const { 149205407Srdivacky assert(i < NumOperands && "Operand index out of range!"); 150193323Sed return Operands[i]; 151193323Sed } 152193323Sed 153205407Srdivacky typedef const SCEV *const *op_iterator; 154205407Srdivacky op_iterator op_begin() const { return Operands; } 155205407Srdivacky op_iterator op_end() const { return Operands + NumOperands; } 156193323Sed 157226633Sdim Type *getType() const { return getOperand(0)->getType(); } 158193323Sed 159221345Sdim NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { 160221345Sdim return (NoWrapFlags)(SubclassData & Mask); 161198090Srdivacky } 162198090Srdivacky 163193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 164193323Sed static inline bool classof(const SCEV *S) { 165193323Sed return S->getSCEVType() == scAddExpr || 166193323Sed S->getSCEVType() == scMulExpr || 167193323Sed S->getSCEVType() == scSMaxExpr || 168193323Sed S->getSCEVType() == scUMaxExpr || 169193323Sed S->getSCEVType() == scAddRecExpr; 170193323Sed } 171193323Sed }; 172193323Sed 173193323Sed //===--------------------------------------------------------------------===// 174193323Sed /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 175193323Sed /// operators. 176193323Sed /// 177193323Sed class SCEVCommutativeExpr : public SCEVNAryExpr { 178193323Sed protected: 179205407Srdivacky SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 180205407Srdivacky enum SCEVTypes T, const SCEV *const *O, size_t N) 181205407Srdivacky : SCEVNAryExpr(ID, T, O, N) {} 182193323Sed 183193323Sed public: 184193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 185193323Sed static inline bool classof(const SCEV *S) { 186193323Sed return S->getSCEVType() == scAddExpr || 187193323Sed S->getSCEVType() == scMulExpr || 188193323Sed S->getSCEVType() == scSMaxExpr || 189193323Sed S->getSCEVType() == scUMaxExpr; 190193323Sed } 191221345Sdim 192221345Sdim /// Set flags for a non-recurrence without clearing previously set flags. 193221345Sdim void setNoWrapFlags(NoWrapFlags Flags) { 194221345Sdim SubclassData |= Flags; 195221345Sdim } 196193323Sed }; 197193323Sed 198193323Sed 199193323Sed //===--------------------------------------------------------------------===// 200193323Sed /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 201193323Sed /// 202193323Sed class SCEVAddExpr : public SCEVCommutativeExpr { 203193323Sed friend class ScalarEvolution; 204193323Sed 205205407Srdivacky SCEVAddExpr(const FoldingSetNodeIDRef ID, 206205407Srdivacky const SCEV *const *O, size_t N) 207205407Srdivacky : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 208193323Sed } 209193323Sed 210193323Sed public: 211226633Sdim Type *getType() const { 212202878Srdivacky // Use the type of the last operand, which is likely to be a pointer 213202878Srdivacky // type, if there is one. This doesn't usually matter, but it can help 214202878Srdivacky // reduce casts when the expressions are expanded. 215202878Srdivacky return getOperand(getNumOperands() - 1)->getType(); 216202878Srdivacky } 217202878Srdivacky 218193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 219193323Sed static inline bool classof(const SCEV *S) { 220193323Sed return S->getSCEVType() == scAddExpr; 221193323Sed } 222193323Sed }; 223193323Sed 224193323Sed //===--------------------------------------------------------------------===// 225193323Sed /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 226193323Sed /// 227193323Sed class SCEVMulExpr : public SCEVCommutativeExpr { 228193323Sed friend class ScalarEvolution; 229193323Sed 230205407Srdivacky SCEVMulExpr(const FoldingSetNodeIDRef ID, 231205407Srdivacky const SCEV *const *O, size_t N) 232205407Srdivacky : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 233193323Sed } 234193323Sed 235193323Sed public: 236193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 237193323Sed static inline bool classof(const SCEV *S) { 238193323Sed return S->getSCEVType() == scMulExpr; 239193323Sed } 240193323Sed }; 241193323Sed 242193323Sed 243193323Sed //===--------------------------------------------------------------------===// 244193323Sed /// SCEVUDivExpr - This class represents a binary unsigned division operation. 245193323Sed /// 246193323Sed class SCEVUDivExpr : public SCEV { 247193323Sed friend class ScalarEvolution; 248193323Sed 249198090Srdivacky const SCEV *LHS; 250198090Srdivacky const SCEV *RHS; 251205407Srdivacky SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 252198090Srdivacky : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 253193323Sed 254193323Sed public: 255198090Srdivacky const SCEV *getLHS() const { return LHS; } 256198090Srdivacky const SCEV *getRHS() const { return RHS; } 257195340Sed 258226633Sdim Type *getType() const { 259218893Sdim // In most cases the types of LHS and RHS will be the same, but in some 260218893Sdim // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 261218893Sdim // depend on the type for correctness, but handling types carefully can 262218893Sdim // avoid extra casts in the SCEVExpander. The LHS is more likely to be 263218893Sdim // a pointer type than the RHS, so use the RHS' type here. 264218893Sdim return getRHS()->getType(); 265193323Sed } 266193323Sed 267193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 268193323Sed static inline bool classof(const SCEV *S) { 269193323Sed return S->getSCEVType() == scUDivExpr; 270193323Sed } 271193323Sed }; 272193323Sed 273193323Sed 274193323Sed //===--------------------------------------------------------------------===// 275193323Sed /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 276193323Sed /// count of the specified loop. This is the primary focus of the 277193323Sed /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 278193323Sed /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 279193323Sed /// created and analyzed. 280193323Sed /// 281193323Sed /// All operands of an AddRec are required to be loop invariant. 282193323Sed /// 283193323Sed class SCEVAddRecExpr : public SCEVNAryExpr { 284193323Sed friend class ScalarEvolution; 285193323Sed 286193323Sed const Loop *L; 287193323Sed 288205407Srdivacky SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 289205407Srdivacky const SCEV *const *O, size_t N, const Loop *l) 290218893Sdim : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} 291193323Sed 292193323Sed public: 293198090Srdivacky const SCEV *getStart() const { return Operands[0]; } 294193323Sed const Loop *getLoop() const { return L; } 295193323Sed 296193323Sed /// getStepRecurrence - This method constructs and returns the recurrence 297193323Sed /// indicating how much this expression steps by. If this is a polynomial 298193323Sed /// of degree N, it returns a chrec of degree N-1. 299221345Sdim /// We cannot determine whether the step recurrence has self-wraparound. 300198090Srdivacky const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 301193323Sed if (isAffine()) return getOperand(1); 302198090Srdivacky return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 303198090Srdivacky op_end()), 304221345Sdim getLoop(), FlagAnyWrap); 305193323Sed } 306193323Sed 307193323Sed /// isAffine - Return true if this is an affine AddRec (i.e., it represents 308193323Sed /// an expressions A+B*x where A and B are loop invariant values. 309193323Sed bool isAffine() const { 310193323Sed // We know that the start value is invariant. This expression is thus 311193323Sed // affine iff the step is also invariant. 312193323Sed return getNumOperands() == 2; 313193323Sed } 314193323Sed 315193323Sed /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 316193323Sed /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 317193323Sed /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 318193323Sed bool isQuadratic() const { 319193323Sed return getNumOperands() == 3; 320193323Sed } 321193323Sed 322221345Sdim /// Set flags for a recurrence without clearing any previously set flags. 323221345Sdim /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here 324221345Sdim /// to make it easier to propagate flags. 325221345Sdim void setNoWrapFlags(NoWrapFlags Flags) { 326221345Sdim if (Flags & (FlagNUW | FlagNSW)) 327221345Sdim Flags = ScalarEvolution::setFlags(Flags, FlagNW); 328221345Sdim SubclassData |= Flags; 329221345Sdim } 330221345Sdim 331193323Sed /// evaluateAtIteration - Return the value of this chain of recurrences at 332193323Sed /// the specified iteration number. 333198090Srdivacky const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 334193323Sed 335193323Sed /// getNumIterationsInRange - Return the number of iterations of this loop 336193323Sed /// that produce values in the specified constant range. Another way of 337193323Sed /// looking at this is that it returns the first iteration number where the 338193323Sed /// value is not in the condition, thus computing the exit count. If the 339193323Sed /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 340193323Sed /// returned. 341198090Srdivacky const SCEV *getNumIterationsInRange(ConstantRange Range, 342193323Sed ScalarEvolution &SE) const; 343193323Sed 344198090Srdivacky /// getPostIncExpr - Return an expression representing the value of 345198090Srdivacky /// this expression one iteration of the loop ahead. 346198090Srdivacky const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 347198090Srdivacky return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 348198090Srdivacky } 349193323Sed 350193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 351193323Sed static inline bool classof(const SCEV *S) { 352193323Sed return S->getSCEVType() == scAddRecExpr; 353193323Sed } 354263508Sdim 355263508Sdim /// Splits the SCEV into two vectors of SCEVs representing the subscripts 356263508Sdim /// and sizes of an array access. Returns the remainder of the 357263508Sdim /// delinearization that is the offset start of the array. 358263508Sdim const SCEV *delinearize(ScalarEvolution &SE, 359263508Sdim SmallVectorImpl<const SCEV *> &Subscripts, 360263508Sdim SmallVectorImpl<const SCEV *> &Sizes) const; 361193323Sed }; 362193323Sed 363193323Sed //===--------------------------------------------------------------------===// 364193323Sed /// SCEVSMaxExpr - This class represents a signed maximum selection. 365193323Sed /// 366193323Sed class SCEVSMaxExpr : public SCEVCommutativeExpr { 367193323Sed friend class ScalarEvolution; 368193323Sed 369205407Srdivacky SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 370205407Srdivacky const SCEV *const *O, size_t N) 371205407Srdivacky : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 372198090Srdivacky // Max never overflows. 373221345Sdim setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 374193323Sed } 375193323Sed 376193323Sed public: 377193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 378193323Sed static inline bool classof(const SCEV *S) { 379193323Sed return S->getSCEVType() == scSMaxExpr; 380193323Sed } 381193323Sed }; 382193323Sed 383193323Sed 384193323Sed //===--------------------------------------------------------------------===// 385193323Sed /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 386193323Sed /// 387193323Sed class SCEVUMaxExpr : public SCEVCommutativeExpr { 388193323Sed friend class ScalarEvolution; 389193323Sed 390205407Srdivacky SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 391205407Srdivacky const SCEV *const *O, size_t N) 392205407Srdivacky : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 393198090Srdivacky // Max never overflows. 394221345Sdim setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); 395193323Sed } 396193323Sed 397193323Sed public: 398193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 399193323Sed static inline bool classof(const SCEV *S) { 400193323Sed return S->getSCEVType() == scUMaxExpr; 401193323Sed } 402193323Sed }; 403193323Sed 404198090Srdivacky //===--------------------------------------------------------------------===// 405193323Sed /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 406198090Srdivacky /// value, and only represent it as its LLVM Value. This is the "bottom" 407193323Sed /// value for the analysis. 408193323Sed /// 409212904Sdim class SCEVUnknown : public SCEV, private CallbackVH { 410193323Sed friend class ScalarEvolution; 411193323Sed 412212904Sdim // Implement CallbackVH. 413212904Sdim virtual void deleted(); 414212904Sdim virtual void allUsesReplacedWith(Value *New); 415198090Srdivacky 416212904Sdim /// SE - The parent ScalarEvolution value. This is used to update 417212904Sdim /// the parent's maps when the value associated with a SCEVUnknown 418212904Sdim /// is deleted or RAUW'd. 419212904Sdim ScalarEvolution *SE; 420212904Sdim 421212904Sdim /// Next - The next pointer in the linked list of all 422212904Sdim /// SCEVUnknown instances owned by a ScalarEvolution. 423212904Sdim SCEVUnknown *Next; 424212904Sdim 425212904Sdim SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 426212904Sdim ScalarEvolution *se, SCEVUnknown *next) : 427212904Sdim SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 428212904Sdim 429193323Sed public: 430212904Sdim Value *getValue() const { return getValPtr(); } 431193323Sed 432203954Srdivacky /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 433203954Srdivacky /// constant representing a type size, alignment, or field offset in 434203954Srdivacky /// a target-independent manner, and hasn't happened to have been 435203954Srdivacky /// folded with other operations into something unrecognizable. This 436203954Srdivacky /// is mainly only useful for pretty-printing and other situations 437203954Srdivacky /// where it isn't absolutely required for these to succeed. 438226633Sdim bool isSizeOf(Type *&AllocTy) const; 439226633Sdim bool isAlignOf(Type *&AllocTy) const; 440226633Sdim bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; 441203954Srdivacky 442226633Sdim Type *getType() const { return getValPtr()->getType(); } 443193323Sed 444193323Sed /// Methods for support type inquiry through isa, cast, and dyn_cast: 445193323Sed static inline bool classof(const SCEV *S) { 446193323Sed return S->getSCEVType() == scUnknown; 447193323Sed } 448193323Sed }; 449193323Sed 450193323Sed /// SCEVVisitor - This class defines a simple visitor class that may be used 451193323Sed /// for various SCEV analysis purposes. 452193323Sed template<typename SC, typename RetVal=void> 453193323Sed struct SCEVVisitor { 454193323Sed RetVal visit(const SCEV *S) { 455193323Sed switch (S->getSCEVType()) { 456193323Sed case scConstant: 457193323Sed return ((SC*)this)->visitConstant((const SCEVConstant*)S); 458193323Sed case scTruncate: 459193323Sed return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 460193323Sed case scZeroExtend: 461193323Sed return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 462193323Sed case scSignExtend: 463193323Sed return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 464193323Sed case scAddExpr: 465193323Sed return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 466193323Sed case scMulExpr: 467193323Sed return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 468193323Sed case scUDivExpr: 469193323Sed return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 470193323Sed case scAddRecExpr: 471193323Sed return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 472193323Sed case scSMaxExpr: 473193323Sed return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 474193323Sed case scUMaxExpr: 475193323Sed return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 476193323Sed case scUnknown: 477193323Sed return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 478193323Sed case scCouldNotCompute: 479193323Sed return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 480193323Sed default: 481198090Srdivacky llvm_unreachable("Unknown SCEV type!"); 482193323Sed } 483193323Sed } 484193323Sed 485193323Sed RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 486198090Srdivacky llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 487193323Sed } 488193323Sed }; 489239462Sdim 490239462Sdim /// Visit all nodes in the expression tree using worklist traversal. 491239462Sdim /// 492239462Sdim /// Visitor implements: 493239462Sdim /// // return true to follow this node. 494239462Sdim /// bool follow(const SCEV *S); 495239462Sdim /// // return true to terminate the search. 496239462Sdim /// bool isDone(); 497239462Sdim template<typename SV> 498239462Sdim class SCEVTraversal { 499239462Sdim SV &Visitor; 500239462Sdim SmallVector<const SCEV *, 8> Worklist; 501239462Sdim SmallPtrSet<const SCEV *, 8> Visited; 502239462Sdim 503239462Sdim void push(const SCEV *S) { 504239462Sdim if (Visited.insert(S) && Visitor.follow(S)) 505239462Sdim Worklist.push_back(S); 506239462Sdim } 507239462Sdim public: 508239462Sdim SCEVTraversal(SV& V): Visitor(V) {} 509239462Sdim 510239462Sdim void visitAll(const SCEV *Root) { 511239462Sdim push(Root); 512239462Sdim while (!Worklist.empty() && !Visitor.isDone()) { 513239462Sdim const SCEV *S = Worklist.pop_back_val(); 514239462Sdim 515239462Sdim switch (S->getSCEVType()) { 516239462Sdim case scConstant: 517239462Sdim case scUnknown: 518239462Sdim break; 519239462Sdim case scTruncate: 520239462Sdim case scZeroExtend: 521239462Sdim case scSignExtend: 522239462Sdim push(cast<SCEVCastExpr>(S)->getOperand()); 523239462Sdim break; 524239462Sdim case scAddExpr: 525239462Sdim case scMulExpr: 526239462Sdim case scSMaxExpr: 527239462Sdim case scUMaxExpr: 528239462Sdim case scAddRecExpr: { 529239462Sdim const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); 530239462Sdim for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), 531239462Sdim E = NAry->op_end(); I != E; ++I) { 532239462Sdim push(*I); 533239462Sdim } 534239462Sdim break; 535239462Sdim } 536239462Sdim case scUDivExpr: { 537239462Sdim const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S); 538239462Sdim push(UDiv->getLHS()); 539239462Sdim push(UDiv->getRHS()); 540239462Sdim break; 541239462Sdim } 542239462Sdim case scCouldNotCompute: 543239462Sdim llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 544239462Sdim default: 545239462Sdim llvm_unreachable("Unknown SCEV kind!"); 546239462Sdim } 547239462Sdim } 548239462Sdim } 549239462Sdim }; 550239462Sdim 551239462Sdim /// Use SCEVTraversal to visit all nodes in the givien expression tree. 552239462Sdim template<typename SV> 553239462Sdim void visitAll(const SCEV *Root, SV& Visitor) { 554239462Sdim SCEVTraversal<SV> T(Visitor); 555239462Sdim T.visitAll(Root); 556239462Sdim } 557249423Sdim 558263508Sdim typedef DenseMap<const Value*, Value*> ValueToValueMap; 559263508Sdim 560263508Sdim /// The SCEVParameterRewriter takes a scalar evolution expression and updates 561263508Sdim /// the SCEVUnknown components following the Map (Value -> Value). 562263508Sdim struct SCEVParameterRewriter 563263508Sdim : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { 564249423Sdim public: 565263508Sdim static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, 566263508Sdim ValueToValueMap &Map) { 567263508Sdim SCEVParameterRewriter Rewriter(SE, Map); 568263508Sdim return Rewriter.visit(Scev); 569263508Sdim } 570249423Sdim 571263508Sdim SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) 572263508Sdim : SE(S), Map(M) {} 573249423Sdim 574263508Sdim const SCEV *visitConstant(const SCEVConstant *Constant) { 575249423Sdim return Constant; 576249423Sdim } 577249423Sdim 578263508Sdim const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 579249423Sdim const SCEV *Operand = visit(Expr->getOperand()); 580249423Sdim return SE.getTruncateExpr(Operand, Expr->getType()); 581249423Sdim } 582249423Sdim 583263508Sdim const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 584249423Sdim const SCEV *Operand = visit(Expr->getOperand()); 585249423Sdim return SE.getZeroExtendExpr(Operand, Expr->getType()); 586249423Sdim } 587249423Sdim 588263508Sdim const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 589249423Sdim const SCEV *Operand = visit(Expr->getOperand()); 590249423Sdim return SE.getSignExtendExpr(Operand, Expr->getType()); 591249423Sdim } 592249423Sdim 593263508Sdim const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 594249423Sdim SmallVector<const SCEV *, 2> Operands; 595249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 596249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 597249423Sdim return SE.getAddExpr(Operands); 598249423Sdim } 599249423Sdim 600263508Sdim const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 601249423Sdim SmallVector<const SCEV *, 2> Operands; 602249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 603249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 604249423Sdim return SE.getMulExpr(Operands); 605249423Sdim } 606249423Sdim 607263508Sdim const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 608249423Sdim return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 609249423Sdim } 610249423Sdim 611263508Sdim const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 612249423Sdim SmallVector<const SCEV *, 2> Operands; 613249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 614249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 615249423Sdim return SE.getAddRecExpr(Operands, Expr->getLoop(), 616249423Sdim Expr->getNoWrapFlags()); 617249423Sdim } 618249423Sdim 619263508Sdim const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 620249423Sdim SmallVector<const SCEV *, 2> Operands; 621249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 622249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 623249423Sdim return SE.getSMaxExpr(Operands); 624249423Sdim } 625249423Sdim 626263508Sdim const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 627249423Sdim SmallVector<const SCEV *, 2> Operands; 628249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 629249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 630249423Sdim return SE.getUMaxExpr(Operands); 631249423Sdim } 632249423Sdim 633263508Sdim const SCEV *visitUnknown(const SCEVUnknown *Expr) { 634263508Sdim Value *V = Expr->getValue(); 635263508Sdim if (Map.count(V)) 636263508Sdim return SE.getUnknown(Map[V]); 637249423Sdim return Expr; 638249423Sdim } 639249423Sdim 640263508Sdim const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 641249423Sdim return Expr; 642249423Sdim } 643249423Sdim 644263508Sdim private: 645249423Sdim ScalarEvolution &SE; 646249423Sdim ValueToValueMap ⤅ 647249423Sdim }; 648249423Sdim 649249423Sdim typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; 650249423Sdim 651249423Sdim /// The SCEVApplyRewriter takes a scalar evolution expression and applies 652249423Sdim /// the Map (Loop -> SCEV) to all AddRecExprs. 653263508Sdim struct SCEVApplyRewriter 654263508Sdim : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> { 655249423Sdim public: 656249423Sdim static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, 657249423Sdim ScalarEvolution &SE) { 658249423Sdim SCEVApplyRewriter Rewriter(SE, Map); 659249423Sdim return Rewriter.visit(Scev); 660249423Sdim } 661263508Sdim 662249423Sdim SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) 663263508Sdim : SE(S), Map(M) {} 664249423Sdim 665263508Sdim const SCEV *visitConstant(const SCEVConstant *Constant) { 666263508Sdim return Constant; 667263508Sdim } 668263508Sdim 669263508Sdim const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { 670263508Sdim const SCEV *Operand = visit(Expr->getOperand()); 671263508Sdim return SE.getTruncateExpr(Operand, Expr->getType()); 672263508Sdim } 673263508Sdim 674263508Sdim const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 675263508Sdim const SCEV *Operand = visit(Expr->getOperand()); 676263508Sdim return SE.getZeroExtendExpr(Operand, Expr->getType()); 677263508Sdim } 678263508Sdim 679263508Sdim const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 680263508Sdim const SCEV *Operand = visit(Expr->getOperand()); 681263508Sdim return SE.getSignExtendExpr(Operand, Expr->getType()); 682263508Sdim } 683263508Sdim 684263508Sdim const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { 685249423Sdim SmallVector<const SCEV *, 2> Operands; 686249423Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 687249423Sdim Operands.push_back(visit(Expr->getOperand(i))); 688263508Sdim return SE.getAddExpr(Operands); 689263508Sdim } 690249423Sdim 691263508Sdim const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { 692263508Sdim SmallVector<const SCEV *, 2> Operands; 693263508Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 694263508Sdim Operands.push_back(visit(Expr->getOperand(i))); 695263508Sdim return SE.getMulExpr(Operands); 696263508Sdim } 697263508Sdim 698263508Sdim const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { 699263508Sdim return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); 700263508Sdim } 701263508Sdim 702263508Sdim const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 703263508Sdim SmallVector<const SCEV *, 2> Operands; 704263508Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 705263508Sdim Operands.push_back(visit(Expr->getOperand(i))); 706263508Sdim 707249423Sdim const Loop *L = Expr->getLoop(); 708249423Sdim const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); 709249423Sdim 710249423Sdim if (0 == Map.count(L)) 711249423Sdim return Res; 712249423Sdim 713249423Sdim const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; 714249423Sdim return Rec->evaluateAtIteration(Map[L], SE); 715249423Sdim } 716249423Sdim 717263508Sdim const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { 718263508Sdim SmallVector<const SCEV *, 2> Operands; 719263508Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 720263508Sdim Operands.push_back(visit(Expr->getOperand(i))); 721263508Sdim return SE.getSMaxExpr(Operands); 722263508Sdim } 723263508Sdim 724263508Sdim const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { 725263508Sdim SmallVector<const SCEV *, 2> Operands; 726263508Sdim for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) 727263508Sdim Operands.push_back(visit(Expr->getOperand(i))); 728263508Sdim return SE.getUMaxExpr(Operands); 729263508Sdim } 730263508Sdim 731263508Sdim const SCEV *visitUnknown(const SCEVUnknown *Expr) { 732263508Sdim return Expr; 733263508Sdim } 734263508Sdim 735263508Sdim const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { 736263508Sdim return Expr; 737263508Sdim } 738263508Sdim 739249423Sdim private: 740263508Sdim ScalarEvolution &SE; 741249423Sdim LoopToScevMapT ⤅ 742249423Sdim }; 743249423Sdim 744249423Sdim/// Applies the Map (Loop -> SCEV) to the given Scev. 745249423Sdimstatic inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, 746249423Sdim ScalarEvolution &SE) { 747249423Sdim return SCEVApplyRewriter::rewrite(Scev, Map, SE); 748193323Sed} 749193323Sed 750249423Sdim} 751249423Sdim 752193323Sed#endif 753