X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpressions.h;h=b74cb3328567595a105bac26a5f461056622c020;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=2e4fd7e2106c77ec35b3a81826facee279436f8c;hpb=78db186d2dbaf4745f7e4beab4029db40856b54b;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 2e4fd7e2106..b74cb332856 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -14,6 +14,7 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" @@ -37,37 +38,14 @@ namespace llvm { friend class ScalarEvolution; ConstantInt *V; - SCEVConstant(const FoldingSetNodeIDRef ID, unsigned Num, ConstantInt *v) - : SCEV(ID, Num, scConstant), V(v) {} + SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : + SCEV(ID, scConstant), V(v) {} public: 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; - - virtual bool hasOperand(const SCEV *) const { - return false; - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - bool properlyDominates(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,33 +57,16 @@ namespace llvm { class SCEVCastExpr : public SCEV { protected: const SCEV *Op; - const Type *Ty; + Type *Ty; - SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned Num, - unsigned SCEVTy, const SCEV *op, const Type *ty); + SCEVCastExpr(const FoldingSetNodeIDRef ID, + unsigned SCEVTy, const SCEV *op, Type *ty); public: 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 hasOperand(const SCEV *O) const { - return Op == O || Op->hasOperand(O); - } - - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual bool properlyDominates(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 || @@ -120,14 +81,11 @@ namespace llvm { class SCEVTruncateExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVTruncateExpr(const FoldingSetNodeIDRef ID, unsigned Num, - const SCEV *op, const Type *ty); + SCEVTruncateExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - 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; } @@ -140,14 +98,11 @@ namespace llvm { class SCEVZeroExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num, - const SCEV *op, const Type *ty); + SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - 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; } @@ -160,14 +115,11 @@ namespace llvm { class SCEVSignExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, unsigned Num, - const SCEV *op, const Type *ty); + SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, + const SCEV *op, Type *ty); public: - 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; } @@ -187,9 +139,9 @@ namespace llvm { const SCEV *const *Operands; size_t NumOperands; - SCEVNAryExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N) - : SCEV(ID, Num, T), Operands(O), NumOperands(N) {} + : SCEV(ID, T), Operands(O), NumOperands(N) {} public: size_t getNumOperands() const { return NumOperands; } @@ -202,51 +154,13 @@ namespace llvm { op_iterator op_begin() const { return Operands; } op_iterator op_end() const { return Operands + NumOperands; } - 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; - } - - // 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; - } + Type *getType() const { return getOperand(0)->getType(); } - virtual bool hasOperand(const SCEV *O) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (O == getOperand(i) || getOperand(i)->hasOperand(O)) - return true; - return false; - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const 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 || @@ -262,23 +176,23 @@ namespace llvm { /// class SCEVCommutativeExpr : public SCEVNAryExpr { protected: - SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N) - : SCEVNAryExpr(ID, Num, T, O, N) {} + : SCEVNAryExpr(ID, T, O, N) {} public: - 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; + } }; @@ -288,15 +202,13 @@ namespace llvm { class SCEVAddExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - SCEVAddExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVAddExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N) - : SCEVCommutativeExpr(ID, Num, scAddExpr, O, N) { + : SCEVCommutativeExpr(ID, scAddExpr, O, N) { } public: - virtual const char *getOperationStr() const { return " + "; } - - virtual 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. @@ -304,7 +216,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; } @@ -316,16 +227,13 @@ namespace llvm { class SCEVMulExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - SCEVMulExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVMulExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N) - : SCEVCommutativeExpr(ID, Num, scMulExpr, O, 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; } @@ -340,37 +248,23 @@ namespace llvm { const SCEV *LHS; const SCEV *RHS; - SCEVUDivExpr(const FoldingSetNodeIDRef ID, unsigned Num, - const SCEV *lhs, const SCEV *rhs) - : SCEV(ID, Num, scUDivExpr), LHS(lhs), RHS(rhs) {} + SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) + : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} public: 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); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return LHS->hasComputableLoopEvolution(L) && - RHS->hasComputableLoopEvolution(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 hasOperand(const SCEV *O) const { - return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(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; } @@ -391,13 +285,9 @@ namespace llvm { const Loop *L; - SCEVAddRecExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVAddRecExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N, const Loop *l) - : SCEVNAryExpr(ID, Num, scAddRecExpr, O, N), L(l) { - for (size_t i = 0, e = NumOperands; i != e; ++i) - assert(Operands[i]->isLoopInvariant(l) && - "Operands of AddRec must be loop-invariant!"); - } + : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} public: const SCEV *getStart() const { return Operands[0]; } @@ -406,23 +296,14 @@ 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); } - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return L == QL; - } - - virtual bool isLoopInvariant(const Loop *QueryLoop) const; - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) 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. bool isAffine() const { @@ -438,6 +319,15 @@ 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. const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; @@ -457,10 +347,7 @@ namespace llvm { 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; } @@ -473,19 +360,15 @@ namespace llvm { class SCEVSMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - SCEVSMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N) - : SCEVCommutativeExpr(ID, Num, scSMaxExpr, O, N) { + : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + 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; } @@ -498,19 +381,15 @@ namespace llvm { class SCEVUMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - SCEVUMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num, + SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N) - : SCEVCommutativeExpr(ID, Num, scUMaxExpr, O, N) { + : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + 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; } @@ -521,15 +400,28 @@ namespace llvm { /// 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; - SCEVUnknown(const FoldingSetNodeIDRef ID, unsigned Num, Value *v) - : SCEV(ID, Num, scUnknown), V(v) {} + // Implement CallbackVH. + virtual void deleted(); + virtual void allUsesReplacedWith(Value *New); + + /// 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 V; } + Value *getValue() const { return getValPtr(); } /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special /// constant representing a type size, alignment, or field offset in @@ -537,29 +429,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; - - virtual bool isLoopInvariant(const Loop *L) const; - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return false; // not computable - } - - virtual bool hasOperand(const SCEV *) const { - return false; - } + bool isSizeOf(Type *&AllocTy) const; + bool isAlignOf(Type *&AllocTy) const; + bool isOffsetOf(Type *&STy, Constant *&FieldNo) const; - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() 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; } @@ -602,9 +478,76 @@ 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) && 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); + } } #endif