X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpressions.h;h=b55ba22a6342f42e38b11af518ce4a049817ff23;hb=2b762697564ca1e12e0e974e93ceeb4c3420505c;hp=db432c8173ddded42396e061e140e49712e6ab70;hpb=4ce32db913beb6ae27df2fa0a9db5d68fd4889d2;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index db432c8173d..b55ba22a634 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" @@ -42,10 +44,9 @@ namespace llvm { public: ConstantInt *getValue() const { return V; } - const Type *getType() const { return V->getType(); } + 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; } @@ -57,17 +58,16 @@ namespace llvm { class SCEVCastExpr : public SCEV { protected: const SCEV *Op; - const Type *Ty; + Type *Ty; SCEVCastExpr(const FoldingSetNodeIDRef ID, - unsigned SCEVTy, const SCEV *op, const Type *ty); + unsigned SCEVTy, const SCEV *op, Type *ty); public: const SCEV *getOperand() const { return Op; } - const Type *getType() const { return Ty; } + 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 || @@ -83,11 +83,10 @@ namespace llvm { friend class ScalarEvolution; SCEVTruncateExpr(const FoldingSetNodeIDRef ID, - const SCEV *op, const Type *ty); + 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; } @@ -101,11 +100,10 @@ namespace llvm { friend class ScalarEvolution; SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, - const SCEV *op, const Type *ty); + 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; } @@ -119,11 +117,10 @@ namespace llvm { friend class ScalarEvolution; SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, - const SCEV *op, const Type *ty); + const SCEV *op, Type *ty); public: /// 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; } @@ -155,22 +152,20 @@ namespace llvm { } 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()); + } - const Type *getType() const { return getOperand(0)->getType(); } + Type *getType() const { return getOperand(0)->getType(); } - bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } - void setHasNoUnsignedWrap(bool B) { - SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); - } - bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } - void setHasNoSignedWrap(bool B) { - SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); + NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { + return (NoWrapFlags)(SubclassData & Mask); } /// 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 || @@ -192,13 +187,17 @@ namespace llvm { 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() == scSMaxExpr || S->getSCEVType() == scUMaxExpr; } + + /// Set flags for a non-recurrence without clearing previously set flags. + void setNoWrapFlags(NoWrapFlags Flags) { + SubclassData |= Flags; + } }; @@ -214,7 +213,7 @@ namespace llvm { } public: - const Type *getType() const { + 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. @@ -222,7 +221,6 @@ namespace llvm { } /// 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; } @@ -241,7 +239,6 @@ namespace llvm { 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; } @@ -263,7 +260,7 @@ namespace llvm { const SCEV *getLHS() const { return LHS; } const SCEV *getRHS() const { return RHS; } - const Type *getType() const { + 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 @@ -273,7 +270,6 @@ namespace llvm { } /// 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; } @@ -305,28 +301,38 @@ namespace llvm { /// 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); } - /// 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; @@ -347,13 +353,11 @@ namespace llvm { } /// 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; } }; - //===--------------------------------------------------------------------===// /// SCEVSMaxExpr - This class represents a signed maximum selection. /// @@ -364,13 +368,11 @@ namespace llvm { const SCEV *const *O, size_t N) : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: /// 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; } @@ -387,13 +389,11 @@ namespace llvm { const SCEV *const *O, size_t N) : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: /// 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; } @@ -404,12 +404,12 @@ namespace llvm { /// value, and only represent it as its LLVM Value. This is the "bottom" /// value for the analysis. /// - class SCEVUnknown : public SCEV, private CallbackVH { + class SCEVUnknown final : public SCEV, private CallbackVH { friend class ScalarEvolution; // Implement CallbackVH. - virtual void deleted(); - virtual void allUsesReplacedWith(Value *New); + void deleted() override; + void allUsesReplacedWith(Value *New) override; /// SE - The parent ScalarEvolution value. This is used to update /// the parent's maps when the value associated with a SCEVUnknown @@ -433,14 +433,13 @@ namespace llvm { /// 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(const Type *&AllocTy) const; - bool isAlignOf(const Type *&AllocTy) const; - bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const; + bool isSizeOf(Type *&AllocTy) const; + bool isAlignOf(Type *&AllocTy) const; + bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; - const Type *getType() const { return getValPtr()->getType(); } + 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; } @@ -483,9 +482,227 @@ namespace llvm { RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); - return RetVal(); } }; + + /// 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); + } + + /// Recursively visits a SCEV expression and re-writes it. + template + class SCEVRewriteVisitor : public SCEVVisitor { + protected: + ScalarEvolution &SE; + public: + SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {} + + const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = ((SC*)this)->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(((SC*)this)->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(((SC*)this)->visit(Expr->getOperand(i))); + return SE.getMulExpr(Operands); + } + + const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(((SC*)this)->visit(Expr->getLHS()), + ((SC*)this)->visit(Expr->getRHS())); + } + + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + SmallVector Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(((SC*)this)->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(((SC*)this)->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(((SC*)this)->visit(Expr->getOperand(i))); + return SE.getUMaxExpr(Operands); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + return Expr; + } + + const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + }; + + typedef DenseMap ValueToValueMap; + + /// The SCEVParameterRewriter takes a scalar evolution expression and updates + /// the SCEVUnknown components following the Map (Value -> Value). + class SCEVParameterRewriter : public SCEVRewriteVisitor { + 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 &SE, ValueToValueMap &M, bool C) + : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {} + + 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; + } + + private: + ValueToValueMap ⤅ + bool InterpretConsts; + }; + + typedef DenseMap LoopToScevMapT; + + /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies + /// the Map (Loop -> SCEV) to all AddRecExprs. + class SCEVLoopAddRecRewriter + : public SCEVRewriteVisitor { + public: + static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, + ScalarEvolution &SE) { + SCEVLoopAddRecRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } + + SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M) + : SCEVRewriteVisitor(SE), Map(M) {} + + 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 = cast(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 SCEVLoopAddRecRewriter::rewrite(Scev, Map, SE); +} + } #endif