X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpressions.h;h=b55ba22a6342f42e38b11af518ce4a049817ff23;hb=2b762697564ca1e12e0e974e93ceeb4c3420505c;hp=5e06c0a43bd1d7dc5964b1918837df29b325d502;hpb=7e2c793a2b5c746344652b6579e958ee42fafdcc;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 5e06c0a43bd..b55ba22a634 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -11,11 +11,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -46,7 +47,6 @@ namespace llvm { 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; } @@ -68,7 +68,6 @@ namespace llvm { 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 || @@ -88,7 +87,6 @@ namespace llvm { 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; } @@ -106,7 +104,6 @@ namespace llvm { 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; } @@ -124,7 +121,6 @@ namespace llvm { 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; } @@ -156,8 +152,12 @@ 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()); + } Type *getType() const { return getOperand(0)->getType(); } @@ -166,7 +166,6 @@ namespace llvm { } /// 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 || @@ -188,7 +187,6 @@ 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 || @@ -223,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; } @@ -242,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; } @@ -274,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; } @@ -314,17 +309,17 @@ namespace llvm { 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 if the step is also invariant. + // 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; } @@ -358,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. /// @@ -380,7 +373,6 @@ namespace llvm { 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; } @@ -402,7 +394,6 @@ namespace llvm { 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; } @@ -413,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 @@ -449,7 +440,6 @@ namespace llvm { 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; } @@ -509,7 +499,7 @@ namespace llvm { SmallPtrSet Visited; void push(const SCEV *S) { - if (Visited.insert(S) && Visitor.follow(S)) + if (Visited.insert(S).second && Visitor.follow(S)) Worklist.push_back(S); } public: @@ -556,12 +546,163 @@ namespace llvm { } }; - /// Use SCEVTraversal to visit all nodes in the givien expression tree. + /// 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