X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpressions.h;h=ff82db19b9e7ed881d7284deff3a712d350373de;hp=fc03e9fe78ea003679ca6b1a865fe14259c42237;hb=cd52a7a381a73c53ec4ef517ad87f19808cb1a28;hpb=c25e7581b9b8088910da31702d4ca21c4734c6d7 diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index fc03e9fe78e..ff82db19b9e 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -11,9 +11,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" @@ -26,8 +28,8 @@ namespace llvm { // These should be ordered in terms of increasing complexity to make the // folders simpler. scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, - scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown, - scCouldNotCompute + scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, + scUnknown, scCouldNotCompute }; //===--------------------------------------------------------------------===// @@ -37,37 +39,14 @@ namespace llvm { friend class ScalarEvolution; ConstantInt *V; - explicit SCEVConstant(ConstantInt *v) : - SCEV(scConstant), V(v) {} + SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : + SCEV(ID, scConstant), V(v) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - ConstantInt *getValue() const { return V; } - virtual bool isLoopInvariant(const Loop *L) const { - return true; - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return false; // Not loop variant - } - - virtual const Type *getType() const; - - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - return this; - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - virtual void print(raw_ostream &OS) const; + Type *getType() const { return V->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVConstant *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; } @@ -79,28 +58,16 @@ namespace llvm { class SCEVCastExpr : public SCEV { protected: const SCEV *Op; - const Type *Ty; + Type *Ty; - SCEVCastExpr(unsigned SCEVTy, const SCEV *op, const Type *ty); + SCEVCastExpr(const FoldingSetNodeIDRef ID, + unsigned SCEVTy, const SCEV *op, Type *ty); public: - virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV *getOperand() const { return Op; } - virtual const Type *getType() const { return Ty; } - - virtual bool isLoopInvariant(const Loop *L) const { - return Op->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return Op->hasComputableLoopEvolution(L); - } - - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; + Type *getType() const { return Ty; } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCastExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate || S->getSCEVType() == scZeroExtend || @@ -115,22 +82,11 @@ namespace llvm { class SCEVTruncateExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVTruncateExpr(const SCEV *op, const Type *ty); + SCEVTruncateExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getTruncateExpr(H, Ty); - } - - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVTruncateExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate; } @@ -143,22 +99,11 @@ namespace llvm { class SCEVZeroExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVZeroExtendExpr(const SCEV *op, const Type *ty); + SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getZeroExtendExpr(H, Ty); - } - - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scZeroExtend; } @@ -171,22 +116,11 @@ namespace llvm { class SCEVSignExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVSignExtendExpr(const SCEV *op, const Type *ty); + SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getSignExtendExpr(H, Ty); - } - - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVSignExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scSignExtend; } @@ -199,54 +133,39 @@ namespace llvm { /// class SCEVNAryExpr : public SCEV { protected: - SmallVector Operands; + // Since SCEVs are immutable, ScalarEvolution allocates operand + // arrays with its SCEVAllocator, so this class just needs a simple + // pointer rather than a more elaborate vector-like data structure. + // This also avoids the need for a non-trivial destructor. + const SCEV *const *Operands; + size_t NumOperands; - SCEVNAryExpr(enum SCEVTypes T, const SmallVectorImpl &ops) - : SCEV(T), Operands(ops.begin(), ops.end()) {} + SCEVNAryExpr(const FoldingSetNodeIDRef ID, + enum SCEVTypes T, const SCEV *const *O, size_t N) + : SCEV(ID, T), Operands(O), NumOperands(N) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - - unsigned getNumOperands() const { return (unsigned)Operands.size(); } + size_t getNumOperands() const { return NumOperands; } const SCEV *getOperand(unsigned i) const { - assert(i < Operands.size() && "Operand index out of range!"); + assert(i < NumOperands && "Operand index out of range!"); return Operands[i]; } - const SmallVectorImpl &getOperands() const { - return Operands; + typedef const SCEV *const *op_iterator; + typedef iterator_range op_range; + op_iterator op_begin() const { return Operands; } + op_iterator op_end() const { return Operands + NumOperands; } + op_range operands() const { + return make_range(op_begin(), op_end()); } - typedef SmallVectorImpl::const_iterator op_iterator; - op_iterator op_begin() const { return Operands.begin(); } - op_iterator op_end() const { return Operands.end(); } - virtual bool isLoopInvariant(const Loop *L) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (!getOperand(i)->isLoopInvariant(L)) return false; - return true; - } + Type *getType() const { return getOperand(0)->getType(); } - // hasComputableLoopEvolution - N-ary expressions have computable loop - // evolutions iff they have at least one operand that varies with the loop, - // but that all varying operands are computable. - virtual bool hasComputableLoopEvolution(const Loop *L) const { - bool HasVarying = false; - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (!getOperand(i)->isLoopInvariant(L)) { - if (getOperand(i)->hasComputableLoopEvolution(L)) - HasVarying = true; - else - return false; - } - return HasVarying; + NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { + return (NoWrapFlags)(SubclassData & Mask); } - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() const { return getOperand(0)->getType(); } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVNAryExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr || @@ -262,27 +181,23 @@ namespace llvm { /// class SCEVCommutativeExpr : public SCEVNAryExpr { protected: - SCEVCommutativeExpr(enum SCEVTypes T, - const SmallVectorImpl &ops) - : SCEVNAryExpr(T, ops) {} + SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, + enum SCEVTypes T, const SCEV *const *O, size_t N) + : SCEVNAryExpr(ID, T, O, N) {} public: - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const; - - virtual const char *getOperationStr() const = 0; - - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCommutativeExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr || S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr; } + + /// Set flags for a non-recurrence without clearing previously set flags. + void setNoWrapFlags(NoWrapFlags Flags) { + SubclassData |= Flags; + } }; @@ -292,15 +207,20 @@ namespace llvm { class SCEVAddExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVAddExpr(const SmallVectorImpl &ops) - : SCEVCommutativeExpr(scAddExpr, ops) { + SCEVAddExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scAddExpr, O, N) { } public: - virtual const char *getOperationStr() const { return " + "; } + Type *getType() const { + // Use the type of the last operand, which is likely to be a pointer + // type, if there is one. This doesn't usually matter, but it can help + // reduce casts when the expressions are expanded. + return getOperand(getNumOperands() - 1)->getType(); + } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr; } @@ -312,15 +232,13 @@ namespace llvm { class SCEVMulExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVMulExpr(const SmallVectorImpl &ops) - : SCEVCommutativeExpr(scMulExpr, ops) { + SCEVMulExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scMulExpr, O, N) { } public: - virtual const char *getOperationStr() const { return " * "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVMulExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scMulExpr; } @@ -335,43 +253,23 @@ namespace llvm { const SCEV *LHS; const SCEV *RHS; - SCEVUDivExpr(const SCEV *lhs, const SCEV *rhs) - : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} + SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) + : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV *getLHS() const { return LHS; } const SCEV *getRHS() const { return RHS; } - virtual bool isLoopInvariant(const Loop *L) const { - return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); + Type *getType() const { + // In most cases the types of LHS and RHS will be the same, but in some + // crazy cases one or the other may be a pointer. ScalarEvolution doesn't + // depend on the type for correctness, but handling types carefully can + // avoid extra casts in the SCEVExpander. The LHS is more likely to be + // a pointer type than the RHS, so use the RHS' type here. + return getRHS()->getType(); } - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return LHS->hasComputableLoopEvolution(L) && - RHS->hasComputableLoopEvolution(L); - } - - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - const SCEV *L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - const SCEV *R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (L == LHS && R == RHS) - return this; - else - return SE.getUDivExpr(L, R); - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() const; - - void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUDivExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUDivExpr; } @@ -392,51 +290,49 @@ namespace llvm { const Loop *L; - SCEVAddRecExpr(const SmallVectorImpl &ops, const Loop *l) - : SCEVNAryExpr(scAddRecExpr, ops), L(l) { - for (size_t i = 0, e = Operands.size(); i != e; ++i) - assert(Operands[i]->isLoopInvariant(l) && - "Operands of AddRec must be loop-invariant!"); - } + SCEVAddRecExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N, const Loop *l) + : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV *getStart() const { return Operands[0]; } const Loop *getLoop() const { return L; } /// getStepRecurrence - This method constructs and returns the recurrence /// indicating how much this expression steps by. If this is a polynomial /// of degree N, it returns a chrec of degree N-1. + /// We cannot determine whether the step recurrence has self-wraparound. const SCEV *getStepRecurrence(ScalarEvolution &SE) const { if (isAffine()) return getOperand(1); return SE.getAddRecExpr(SmallVector(op_begin()+1, op_end()), - getLoop()); + getLoop(), FlagAnyWrap); } - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - if (L == QL) return true; - return false; - } - - virtual bool isLoopInvariant(const Loop *QueryLoop) const; - - /// isAffine - Return true if this is an affine AddRec (i.e., it represents - /// an expressions A+B*x where A and B are loop invariant values. + /// isAffine - Return true if this represents an expression + /// A + B*x where A and B are loop invariant values. bool isAffine() const { // We know that the start value is invariant. This expression is thus // affine iff the step is also invariant. return getNumOperands() == 2; } - /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it - /// represents an expressions A+B*x+C*x^2 where A, B and C are loop - /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} + /// isQuadratic - Return true if this represents an expression + /// A + B*x + C*x^2 where A, B and C are loop invariant values. + /// This corresponds to an addrec of the form {L,+,M,+,N} bool isQuadratic() const { return getNumOperands() == 3; } + /// Set flags for a recurrence without clearing any previously set flags. + /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here + /// to make it easier to propagate flags. + void setNoWrapFlags(NoWrapFlags Flags) { + if (Flags & (FlagNUW | FlagNSW)) + Flags = ScalarEvolution::setFlags(Flags, FlagNW); + SubclassData |= Flags; + } + /// evaluateAtIteration - Return the value of this chain of recurrences at /// the specified iteration number. const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; @@ -450,25 +346,95 @@ namespace llvm { const SCEV *getNumIterationsInRange(ConstantRange Range, ScalarEvolution &SE) const; - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const; - /// getPostIncExpr - Return an expression representing the value of /// this expression one iteration of the loop ahead. - const SCEV *getPostIncExpr(ScalarEvolution &SE) const { - return SE.getAddExpr(this, getStepRecurrence(SE)); + const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { + return cast(SE.getAddExpr(this, getStepRecurrence(SE))); } - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddRecExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddRecExpr; } - }; + /// Collect parametric terms occurring in step expressions. + void collectParametricTerms(ScalarEvolution &SE, + SmallVectorImpl &Terms) const; + + /// Return in Subscripts the access functions for each dimension in Sizes. + void computeAccessFunctions(ScalarEvolution &SE, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes) const; + + /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the + /// subscripts and sizes of an array access. + /// + /// The delinearization is a 3 step process: the first two steps compute the + /// sizes of each subscript and the third step computes the access functions + /// for the delinearized array: + /// + /// 1. Find the terms in the step functions + /// 2. Compute the array size + /// 3. Compute the access function: divide the SCEV by the array size + /// starting with the innermost dimensions found in step 2. The Quotient + /// is the SCEV to be divided in the next step of the recursion. The + /// Remainder is the subscript of the innermost dimension. Loop over all + /// array dimensions computed in step 2. + /// + /// To compute a uniform array size for several memory accesses to the same + /// object, one can collect in step 1 all the step terms for all the memory + /// accesses, and compute in step 2 a unique array shape. This guarantees + /// that the array shape will be the same across all memory accesses. + /// + /// FIXME: We could derive the result of steps 1 and 2 from a description of + /// the array shape given in metadata. + /// + /// Example: + /// + /// A[][n][m] + /// + /// for i + /// for j + /// for k + /// A[j+k][2i][5i] = + /// + /// The initial SCEV: + /// + /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] + /// + /// 1. Find the different terms in the step functions: + /// -> [2*m, 5, n*m, n*m] + /// + /// 2. Compute the array size: sort and unique them + /// -> [n*m, 2*m, 5] + /// find the GCD of all the terms = 1 + /// divide by the GCD and erase constant terms + /// -> [n*m, 2*m] + /// GCD = m + /// divide by GCD -> [n, 2] + /// remove constant terms + /// -> [n] + /// size of the array is A[unknown][n][m] + /// + /// 3. Compute the access function + /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m + /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k + /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k + /// The remainder is the subscript of the innermost array dimension: [5i]. + /// + /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n + /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k + /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k + /// The Remainder is the subscript of the next array dimension: [2i]. + /// + /// The subscript of the outermost dimension is the Quotient: [j+k]. + /// + /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. + void delinearize(ScalarEvolution &SE, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes, + const SCEV *ElementSize) const; + }; //===--------------------------------------------------------------------===// /// SCEVSMaxExpr - This class represents a signed maximum selection. @@ -476,15 +442,15 @@ namespace llvm { class SCEVSMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVSMaxExpr(const SmallVectorImpl &ops) - : SCEVCommutativeExpr(scSMaxExpr, ops) { + SCEVSMaxExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { + // Max never overflows. + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: - virtual const char *getOperationStr() const { return " smax "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVSMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scSMaxExpr; } @@ -497,58 +463,61 @@ namespace llvm { class SCEVUMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVUMaxExpr(const SmallVectorImpl &ops) - : SCEVCommutativeExpr(scUMaxExpr, ops) { + SCEVUMaxExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { + // Max never overflows. + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: - virtual const char *getOperationStr() const { return " umax "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUMaxExpr; } }; - //===--------------------------------------------------------------------===// /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV - /// value, and only represent it as it's LLVM Value. This is the "bottom" + /// value, and only represent it as its LLVM Value. This is the "bottom" /// value for the analysis. /// - class SCEVUnknown : public SCEV { + class SCEVUnknown : public SCEV, private CallbackVH { friend class ScalarEvolution; - Value *V; - explicit SCEVUnknown(Value *v) : - SCEV(scUnknown), V(v) {} - - public: - virtual void Profile(FoldingSetNodeID &ID) const; + // Implement CallbackVH. + void deleted() override; + void allUsesReplacedWith(Value *New) override; - Value *getValue() const { return V; } + /// SE - The parent ScalarEvolution value. This is used to update + /// the parent's maps when the value associated with a SCEVUnknown + /// is deleted or RAUW'd. + ScalarEvolution *SE; - virtual bool isLoopInvariant(const Loop *L) const; - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return false; // not computable - } + /// Next - The next pointer in the linked list of all + /// SCEVUnknown instances owned by a ScalarEvolution. + SCEVUnknown *Next; - const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, - const SCEV *Conc, - ScalarEvolution &SE) const { - if (&*Sym == this) return Conc; - return this; - } + SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, + ScalarEvolution *se, SCEVUnknown *next) : + SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} - bool dominates(BasicBlock *BB, DominatorTree *DT) const; + public: + Value *getValue() const { return getValPtr(); } - virtual const Type *getType() const; + /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special + /// constant representing a type size, alignment, or field offset in + /// a target-independent manner, and hasn't happened to have been + /// folded with other operations into something unrecognizable. This + /// is mainly only useful for pretty-printing and other situations + /// where it isn't absolutely required for these to succeed. + bool isSizeOf(Type *&AllocTy) const; + bool isAlignOf(Type *&AllocTy) const; + bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; - virtual void print(raw_ostream &OS) const; + Type *getType() const { return getValPtr()->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUnknown *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; } @@ -585,15 +554,281 @@ namespace llvm { case scCouldNotCompute: return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); default: - LLVM_UNREACHABLE("Unknown SCEV type!"); + llvm_unreachable("Unknown SCEV type!"); } } RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { - LLVM_UNREACHABLE("Invalid use of SCEVCouldNotCompute!"); - return RetVal(); + llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); } }; + + /// Visit all nodes in the expression tree using worklist traversal. + /// + /// Visitor implements: + /// // return true to follow this node. + /// bool follow(const SCEV *S); + /// // return true to terminate the search. + /// bool isDone(); + template + class SCEVTraversal { + SV &Visitor; + SmallVector Worklist; + SmallPtrSet Visited; + + void push(const SCEV *S) { + if (Visited.insert(S).second && Visitor.follow(S)) + Worklist.push_back(S); + } + public: + SCEVTraversal(SV& V): Visitor(V) {} + + void visitAll(const SCEV *Root) { + push(Root); + while (!Worklist.empty() && !Visitor.isDone()) { + const SCEV *S = Worklist.pop_back_val(); + + switch (S->getSCEVType()) { + case scConstant: + case scUnknown: + break; + case scTruncate: + case scZeroExtend: + case scSignExtend: + push(cast(S)->getOperand()); + break; + case scAddExpr: + case scMulExpr: + case scSMaxExpr: + case scUMaxExpr: + case scAddRecExpr: { + const SCEVNAryExpr *NAry = cast(S); + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), + E = NAry->op_end(); I != E; ++I) { + push(*I); + } + break; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + push(UDiv->getLHS()); + push(UDiv->getRHS()); + break; + } + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + default: + llvm_unreachable("Unknown SCEV kind!"); + } + } + } + }; + + /// Use SCEVTraversal to visit all nodes in the given expression tree. + template + void visitAll(const SCEV *Root, SV& Visitor) { + SCEVTraversal T(Visitor); + T.visitAll(Root); + } + + typedef DenseMap ValueToValueMap; + + /// The SCEVParameterRewriter takes a scalar evolution expression and updates + /// the SCEVUnknown components following the Map (Value -> Value). + struct SCEVParameterRewriter + : public SCEVVisitor { + public: + static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, + ValueToValueMap &Map, + bool InterpretConsts = false) { + SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts); + return Rewriter.visit(Scev); + } + + SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C) + : SE(S), Map(M), InterpretConsts(C) {} + + const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getSignExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddExpr(Operands); + } + + const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getMulExpr(Operands); + } + + const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); + } + + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddRecExpr(Operands, Expr->getLoop(), + Expr->getNoWrapFlags()); + } + + const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getSMaxExpr(Operands); + } + + const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getUMaxExpr(Operands); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + Value *V = Expr->getValue(); + if (Map.count(V)) { + Value *NV = Map[V]; + if (InterpretConsts && isa(NV)) + return SE.getConstant(cast(NV)); + return SE.getUnknown(NV); + } + return Expr; + } + + const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + + private: + ScalarEvolution &SE; + ValueToValueMap ⤅ + bool InterpretConsts; + }; + + typedef DenseMap LoopToScevMapT; + + /// The SCEVApplyRewriter takes a scalar evolution expression and applies + /// the Map (Loop -> SCEV) to all AddRecExprs. + struct SCEVApplyRewriter + : public SCEVVisitor { + public: + static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, + ScalarEvolution &SE) { + SCEVApplyRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } + + SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) + : SE(S), Map(M) {} + + const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getSignExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddExpr(Operands); + } + + const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getMulExpr(Operands); + } + + const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); + } + + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + + const Loop *L = Expr->getLoop(); + const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); + + if (0 == Map.count(L)) + return Res; + + const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; + return Rec->evaluateAtIteration(Map[L], SE); + } + + const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getSMaxExpr(Operands); + } + + const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getUMaxExpr(Operands); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + return Expr; + } + + const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + + private: + ScalarEvolution &SE; + LoopToScevMapT ⤅ + }; + +/// Applies the Map (Loop -> SCEV) to the given Scev. +static inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, + ScalarEvolution &SE) { + return SCEVApplyRewriter::rewrite(Scev, Map, SE); +} + } #endif