X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpressions.h;h=eac91131ad535c53ec2fcaf42199c313abfc6ea6;hb=b075ed3b90fa2a520aeb15802fddf3460d865f91;hp=2a546c34824f9273ff4a8ed87856a9d052d9e274;hpb=60a05cc118763c680834a61280f48530482a1f86;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 2a546c34824..eac91131ad5 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -11,62 +11,66 @@ // //===----------------------------------------------------------------------===// -#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/Analysis/ScalarEvolution.h" +#include "llvm/Support/ErrorHandling.h" namespace llvm { class ConstantInt; class ConstantRange; + class DominatorTree; enum SCEVTypes { // These should be ordered in terms of increasing complexity to make the // folders simpler. - scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr, - scAddRecExpr, scUnknown, scCouldNotCompute + scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, + scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, + scUnknown, scCouldNotCompute }; //===--------------------------------------------------------------------===// /// SCEVConstant - This class represents a constant integer value. /// class SCEVConstant : public SCEV { - ConstantInt *V; - SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} + friend class ScalarEvolution; - virtual ~SCEVConstant(); + ConstantInt *V; + SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : + SCEV(ID, scConstant), V(v) {} public: - /// get method - This just gets and returns a new SCEVConstant object. - /// - static SCEVHandle get(ConstantInt *V); - ConstantInt *getValue() const { return V; } - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const; + Type *getType() const { return V->getType(); } - virtual bool isLoopInvariant(const Loop *L) const { - return true; + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scConstant; } + }; - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return false; // Not loop variant - } + //===--------------------------------------------------------------------===// + /// SCEVCastExpr - This is the base class for unary cast operator classes. + /// + class SCEVCastExpr : public SCEV { + protected: + const SCEV *Op; + Type *Ty; - virtual const Type *getType() const; + SCEVCastExpr(const FoldingSetNodeIDRef ID, + unsigned SCEVTy, const SCEV *op, Type *ty); - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - return this; - } - - virtual void print(std::ostream &OS) const; + public: + const SCEV *getOperand() const { return Op; } + Type *getType() const { return Ty; } /// 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; + return S->getSCEVType() == scTruncate || + S->getSCEVType() == scZeroExtend || + S->getSCEVType() == scSignExtend; } }; @@ -74,43 +78,14 @@ namespace llvm { /// SCEVTruncateExpr - This class represents a truncation of an integer value /// to a smaller integer value. /// - class SCEVTruncateExpr : public SCEV { - SCEVHandle Op; - const Type *Ty; - SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); - virtual ~SCEVTruncateExpr(); - public: - /// get method - This just gets and returns a new SCEVTruncate object - /// - static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); - - const SCEVHandle &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); - } - - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); - if (H == Op) - return this; - return get(H, Ty); - } + class SCEVTruncateExpr : public SCEVCastExpr { + friend class ScalarEvolution; - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const; - - virtual void print(std::ostream &OS) const; + SCEVTruncateExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); + public: /// 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; } @@ -120,110 +95,103 @@ namespace llvm { /// SCEVZeroExtendExpr - This class represents a zero extension of a small /// integer value to a larger integer value. /// - class SCEVZeroExtendExpr : public SCEV { - SCEVHandle Op; - const Type *Ty; - SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); - virtual ~SCEVZeroExtendExpr(); - public: - /// get method - This just gets and returns a new SCEVZeroExtend object - /// - static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); + class SCEVZeroExtendExpr : public SCEVCastExpr { + friend class ScalarEvolution; - const SCEVHandle &getOperand() const { return Op; } - virtual const Type *getType() const { return Ty; } + SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); - virtual bool isLoopInvariant(const Loop *L) const { - return Op->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return Op->hasComputableLoopEvolution(L); + public: + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scZeroExtend; } + }; - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const; - - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); - if (H == Op) - return this; - return get(H, Ty); - } + //===--------------------------------------------------------------------===// + /// SCEVSignExtendExpr - This class represents a sign extension of a small + /// integer value to a larger integer value. + /// + class SCEVSignExtendExpr : public SCEVCastExpr { + friend class ScalarEvolution; - virtual void print(std::ostream &OS) const; + SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); + public: /// 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; + return S->getSCEVType() == scSignExtend; } }; //===--------------------------------------------------------------------===// - /// SCEVCommutativeExpr - This node is the base class for n'ary commutative - /// operators. + /// SCEVNAryExpr - This node is a base class providing common + /// functionality for n'ary operators. /// - class SCEVCommutativeExpr : public SCEV { - std::vector Operands; - + class SCEVNAryExpr : public SCEV { protected: - SCEVCommutativeExpr(enum SCEVTypes T, const std::vector &ops) - : SCEV(T) { - Operands.reserve(ops.size()); - Operands.insert(Operands.end(), ops.begin(), ops.end()); - } - ~SCEVCommutativeExpr(); + // 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(const FoldingSetNodeIDRef ID, + enum SCEVTypes T, const SCEV *const *O, size_t N) + : SCEV(ID, T), Operands(O), NumOperands(N) {} public: - unsigned getNumOperands() const { return Operands.size(); } - const SCEVHandle &getOperand(unsigned i) const { - assert(i < Operands.size() && "Operand index out of range!"); + size_t getNumOperands() const { return NumOperands; } + const SCEV *getOperand(unsigned i) const { + assert(i < NumOperands && "Operand index out of range!"); return Operands[i]; } - const std::vector &getOperands() const { return Operands; } - typedef std::vector::const_iterator op_iterator; - op_iterator op_begin() const { return Operands.begin(); } - op_iterator op_end() const { return Operands.end(); } + typedef const SCEV *const *op_iterator; + op_iterator op_begin() const { return Operands; } + op_iterator op_end() const { return Operands + NumOperands; } + Type *getType() const { return getOperand(0)->getType(); } - 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; + NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { + return (NoWrapFlags)(SubclassData & Mask); } - // hasComputableLoopEvolution - Commutative 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; + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scAddExpr || + S->getSCEVType() == scMulExpr || + S->getSCEVType() == scSMaxExpr || + S->getSCEVType() == scUMaxExpr || + S->getSCEVType() == scAddRecExpr; } + }; - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const; - - virtual const char *getOperationStr() const = 0; - - virtual const Type *getType() const { return getOperand(0)->getType(); } - virtual void print(std::ostream &OS) const; + //===--------------------------------------------------------------------===// + /// SCEVCommutativeExpr - This node is the base class for n'ary commutative + /// operators. + /// + class SCEVCommutativeExpr : public SCEVNAryExpr { + protected: + SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, + enum SCEVTypes T, const SCEV *const *O, size_t N) + : SCEVNAryExpr(ID, T, O, N) {} + public: /// 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() == scMulExpr || + S->getSCEVType() == scSMaxExpr || + S->getSCEVType() == scUMaxExpr; + } + + /// Set flags for a non-recurrence without clearing previously set flags. + void setNoWrapFlags(NoWrapFlags Flags) { + SubclassData |= Flags; } }; @@ -232,33 +200,22 @@ namespace llvm { /// SCEVAddExpr - This node represents an addition of some number of SCEVs. /// class SCEVAddExpr : public SCEVCommutativeExpr { - SCEVAddExpr(const std::vector &ops) - : SCEVCommutativeExpr(scAddExpr, ops) { - } - - public: - static SCEVHandle get(std::vector &Ops); + friend class ScalarEvolution; - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector Ops; - Ops.push_back(LHS); - Ops.push_back(RHS); - return get(Ops); + SCEVAddExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scAddExpr, O, N) { } - static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, - const SCEVHandle &Op2) { - std::vector Ops; - Ops.push_back(Op0); - Ops.push_back(Op1); - Ops.push_back(Op2); - return get(Ops); + public: + 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(); } - virtual const char *getOperationStr() const { return " + "; } - /// 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; } @@ -268,24 +225,15 @@ namespace llvm { /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. /// class SCEVMulExpr : public SCEVCommutativeExpr { - SCEVMulExpr(const std::vector &ops) - : SCEVCommutativeExpr(scMulExpr, ops) { - } - - public: - static SCEVHandle get(std::vector &Ops); + friend class ScalarEvolution; - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector Ops; - Ops.push_back(LHS); - Ops.push_back(RHS); - return get(Ops); + SCEVMulExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scMulExpr, O, N) { } - virtual const char *getOperationStr() const { return " * "; } - + public: /// 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; } @@ -293,110 +241,69 @@ namespace llvm { //===--------------------------------------------------------------------===// - /// SCEVSDivExpr - This class represents a binary unsigned division operation. + /// SCEVUDivExpr - This class represents a binary unsigned division operation. /// - class SCEVSDivExpr : public SCEV { - SCEVHandle LHS, RHS; - SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) - : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {} - - virtual ~SCEVSDivExpr(); - public: - /// get method - This just gets and returns a new SCEVSDiv object. - /// - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); - - const SCEVHandle &getLHS() const { return LHS; } - const SCEVHandle &getRHS() const { return RHS; } + class SCEVUDivExpr : public SCEV { + friend class ScalarEvolution; - virtual bool isLoopInvariant(const Loop *L) const { - return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); - } + const SCEV *LHS; + const SCEV *RHS; + SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) + : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return LHS->hasComputableLoopEvolution(L) && - RHS->hasComputableLoopEvolution(L); - } + public: + const SCEV *getLHS() const { return LHS; } + const SCEV *getRHS() const { return RHS; } - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc); - SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc); - if (L == LHS && R == RHS) - return this; - else - return get(L, R); + 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 const Type *getType() const; - - void print(std::ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVSDivExpr *S) { return true; } static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scSDivExpr; + return S->getSCEVType() == scUDivExpr; } }; //===--------------------------------------------------------------------===// /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip - /// count of the specified loop. + /// count of the specified loop. This is the primary focus of the + /// ScalarEvolution framework; all the other SCEV subclasses are mostly just + /// supporting infrastructure to allow SCEVAddRecExpr expressions to be + /// created and analyzed. /// /// All operands of an AddRec are required to be loop invariant. /// - class SCEVAddRecExpr : public SCEV { - std::vector Operands; + class SCEVAddRecExpr : public SCEVNAryExpr { + friend class ScalarEvolution; + const Loop *L; - SCEVAddRecExpr(const std::vector &ops, const Loop *l) - : SCEV(scAddRecExpr), Operands(ops), L(l) { - for (unsigned i = 0, e = Operands.size(); i != e; ++i) - assert(Operands[i]->isLoopInvariant(l) && - "Operands of AddRec must be loop-invariant!"); - } - ~SCEVAddRecExpr(); + SCEVAddRecExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N, const Loop *l) + : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} + public: - static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, - const Loop *); - static SCEVHandle get(std::vector &Operands, - const Loop *); - static SCEVHandle get(const std::vector &Operands, - const Loop *L) { - std::vector NewOp(Operands); - return get(NewOp, L); - } - - typedef std::vector::const_iterator op_iterator; - op_iterator op_begin() const { return Operands.begin(); } - op_iterator op_end() const { return Operands.end(); } - - unsigned getNumOperands() const { return Operands.size(); } - const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } - const SCEVHandle &getStart() const { return Operands[0]; } + 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. - SCEVHandle getStepRecurrence() const { - if (getNumOperands() == 2) return getOperand(1); - return SCEVAddRecExpr::get(std::vector(op_begin()+1,op_end()), - getLoop()); - } - - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - if (L == QL) return true; - return false; + /// 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(), FlagAnyWrap); } - virtual bool isLoopInvariant(const Loop *QueryLoop) const; - - virtual const Type *getType() const { return Operands[0]->getType(); } - /// 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. bool isAffine() const { @@ -412,9 +319,18 @@ namespace llvm { 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. - SCEVHandle evaluateAtIteration(SCEVHandle It) const; + const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; /// getNumIterationsInRange - Return the number of iterations of this loop /// that produce values in the specified constant range. Another way of @@ -422,59 +338,104 @@ namespace llvm { /// value is not in the condition, thus computing the exit count. If the /// iteration count can't be computed, an instance of SCEVCouldNotCompute is /// returned. - SCEVHandle getNumIterationsInRange(ConstantRange Range) const; - - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const; + const SCEV *getNumIterationsInRange(ConstantRange Range, + ScalarEvolution &SE) const; - virtual void print(std::ostream &OS) const; + /// getPostIncExpr - Return an expression representing the value of + /// this expression one iteration of the loop ahead. + const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { + return cast(SE.getAddExpr(this, getStepRecurrence(SE))); + } /// 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; } }; + //===--------------------------------------------------------------------===// - /// 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 for the analysis. + /// SCEVSMaxExpr - This class represents a signed maximum selection. /// - class SCEVUnknown : public SCEV { - Value *V; - SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} + class SCEVSMaxExpr : public SCEVCommutativeExpr { + friend class ScalarEvolution; + + SCEVSMaxExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { + // Max never overflows. + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); + } - protected: - ~SCEVUnknown(); public: - /// get method - For SCEVUnknown, this just gets and returns a new - /// SCEVUnknown. - static SCEVHandle get(Value *V); + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scSMaxExpr; + } + }; - /// getIntegerSCEV - Given an integer or FP type, create a constant for the - /// specified signed integer value and return a SCEV for the constant. - static SCEVHandle getIntegerSCEV(int Val, const Type *Ty); - Value *getValue() const { return V; } + //===--------------------------------------------------------------------===// + /// SCEVUMaxExpr - This class represents an unsigned maximum selection. + /// + class SCEVUMaxExpr : public SCEVCommutativeExpr { + friend class ScalarEvolution; - virtual bool isLoopInvariant(const Loop *L) const; - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return false; // not computable + SCEVUMaxExpr(const FoldingSetNodeIDRef ID, + const SCEV *const *O, size_t N) + : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { + // Max never overflows. + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } - SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - if (&*Sym == this) return Conc; - return this; + public: + /// Methods for support type inquiry through isa, cast, and dyn_cast: + 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 its LLVM Value. This is the "bottom" + /// value for the analysis. + /// + class SCEVUnknown : public SCEV, private CallbackVH { + friend class ScalarEvolution; - virtual const Type *getType() const; + // Implement CallbackVH. + virtual void deleted(); + virtual void allUsesReplacedWith(Value *New); - virtual void print(std::ostream &OS) const; + /// 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; + + /// Next - The next pointer in the linked list of all + /// SCEVUnknown instances owned by a ScalarEvolution. + SCEVUnknown *Next; + + SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, + ScalarEvolution *se, SCEVUnknown *next) : + SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} + + public: + Value *getValue() const { return getValPtr(); } + + /// 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; + + 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; } @@ -484,39 +445,254 @@ namespace llvm { /// for various SCEV analysis purposes. template struct SCEVVisitor { - RetVal visit(SCEV *S) { + RetVal visit(const SCEV *S) { switch (S->getSCEVType()) { case scConstant: - return ((SC*)this)->visitConstant((SCEVConstant*)S); + return ((SC*)this)->visitConstant((const SCEVConstant*)S); case scTruncate: - return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S); + return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); case scZeroExtend: - return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S); + return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); + case scSignExtend: + return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); case scAddExpr: - return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S); + return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); case scMulExpr: - return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S); - case scSDivExpr: - return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S); + return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); + case scUDivExpr: + return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); case scAddRecExpr: - return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S); + return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); + case scSMaxExpr: + return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); + case scUMaxExpr: + return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); case scUnknown: - return ((SC*)this)->visitUnknown((SCEVUnknown*)S); + return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); case scCouldNotCompute: - return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S); + return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); default: - assert(0 && "Unknown SCEV type!"); - abort(); + llvm_unreachable("Unknown SCEV type!"); + } + } + + RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { + 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) && 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 givien expression tree. + template + void visitAll(const SCEV *Root, SV& Visitor) { + SCEVTraversal T(Visitor); + T.visitAll(Root); + } + + /// The SCEVRewriter takes a scalar evolution expression and copies all its + /// components. The result after a rewrite is an identical SCEV. + struct SCEVRewriter + : public SCEVVisitor { + public: + SCEVRewriter(ScalarEvolution &S) : SE(S) {} + + virtual ~SCEVRewriter() {} + + virtual const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + virtual const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + virtual const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getSignExtendExpr(Operand, Expr->getType()); + } + + virtual 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); + } + + virtual 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); + } + + virtual const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); + } + + virtual 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()); + } + + virtual 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); + } + + virtual 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); + } + + virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { + return Expr; + } + + virtual const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + + protected: + ScalarEvolution &SE; + }; + + typedef DenseMap ValueToValueMap; + + /// The SCEVParameterRewriter takes a scalar evolution expression and updates + /// the SCEVUnknown components following the Map (Value -> Value). + struct SCEVParameterRewriter: public SCEVRewriter { + public: + static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, + ValueToValueMap &Map) { + SCEVParameterRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } + SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) + : SCEVRewriter(S), Map(M) {} + + virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { + Value *V = Expr->getValue(); + if (Map.count(V)) + return SE.getUnknown(Map[V]); + return Expr; + } + + private: + ValueToValueMap ⤅ + }; + + typedef DenseMap LoopToScevMapT; + + /// The SCEVApplyRewriter takes a scalar evolution expression and applies + /// the Map (Loop -> SCEV) to all AddRecExprs. + struct SCEVApplyRewriter: public SCEVRewriter { + 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) + : SCEVRewriter(S), Map(M) {} + + virtual 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; - RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) { - assert(0 && "Invalid use of SCEVCouldNotCompute!"); - abort(); - return RetVal(); + const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; + return Rec->evaluateAtIteration(Map[L], SE); } + + private: + 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 +} +#endif