X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=a62f6a80d1a715d084a35ecd389d4440b25e597c;hb=7a2bdde0a0eebcd2125055e0eacaca040f0b766c;hp=c2cfd385ce122dd14e8d6df7f7ea86902d00e92f;hpb=aadb5f5adbdb650c5cdc5ece939aaa30af91b3bc;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index c2cfd385ce1..a62f6a80d1a 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,7 +24,8 @@ #include "llvm/Pass.h" #include "llvm/Instructions.h" #include "llvm/Function.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Operator.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" @@ -46,14 +47,14 @@ namespace llvm { class Operator; class SCEVUnknown; class SCEV; - template<> class FoldingSetTrait; + template<> struct FoldingSetTrait; /// SCEV - This class represents an analyzed expression in the program. These /// are opaque objects that the client is not allowed to do much with /// directly. /// class SCEV : public FoldingSetNode { - friend class FoldingSetTrait; + friend struct FoldingSetTrait; /// FastID - A reference to an Interned FoldingSetNodeID for this node. /// The ScalarEvolution's BumpPtrAllocator holds the data. @@ -70,27 +71,39 @@ namespace llvm { private: SCEV(const SCEV &); // DO NOT IMPLEMENT void operator=(const SCEV &); // DO NOT IMPLEMENT - protected: - virtual ~SCEV(); + public: + /// NoWrapFlags are bitfield indices into SubclassData. + /// + /// Add and Mul expressions may have no-unsigned-wrap or + /// no-signed-wrap properties, which are derived from the IR + /// operator. NSW is a misnomer that we use to mean no signed overflow or + /// underflow. + /// + /// AddRec expression may have a no-self-wraparound property if the + /// result can never reach the start value. This property is independent of + /// the actual start value and step direction. Self-wraparound is defined + /// purely in terms of the recurrence's loop, step size, and + /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: + /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). + /// + /// Note that NUW and NSW are also valid properties of a recurrence, and + /// either implies NW. For convenience, NW will be set for a recurrence + /// whenever either NUW or NSW are set. + enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. + FlagNW = (1 << 0), // No self-wrap. + FlagNUW = (1 << 1), // No unsigned wrap. + FlagNSW = (1 << 2), // No signed wrap. + NoWrapMask = (1 << 3) -1 }; + explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} unsigned getSCEVType() const { return SCEVType; } - /// isLoopInvariant - Return true if the value of this SCEV is unchanging in - /// the specified loop. - virtual bool isLoopInvariant(const Loop *L) const = 0; - - /// hasComputableLoopEvolution - Return true if this SCEV changes value in a - /// known way in the specified loop. This property being true implies that - /// the value is variant in the loop AND that we can emit an expression to - /// compute the value of the expression at any particular loop iteration. - virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; - /// getType - Return the LLVM type of this SCEV expression. /// - virtual const Type *getType() const = 0; + const Type *getType() const; /// isZero - Return true if the expression is a constant zero. /// @@ -105,22 +118,10 @@ namespace llvm { /// bool isAllOnesValue() const; - /// hasOperand - Test whether this SCEV has Op as a direct or - /// indirect operand. - virtual bool hasOperand(const SCEV *Op) const = 0; - - /// dominates - Return true if elements that makes up this SCEV dominates - /// the specified basic block. - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; - - /// properlyDominates - Return true if elements that makes up this SCEV - /// properly dominate the specified basic block. - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const = 0; - /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. - virtual void print(raw_ostream &OS) const = 0; + void print(raw_ostream &OS) const; /// dump - This method is used for debugging. /// @@ -155,21 +156,6 @@ namespace llvm { struct SCEVCouldNotCompute : public SCEV { SCEVCouldNotCompute(); - // None of these methods are valid for this object. - virtual bool isLoopInvariant(const Loop *L) const; - virtual const Type *getType() const; - virtual bool hasComputableLoopEvolution(const Loop *L) const; - virtual void print(raw_ostream &OS) const; - virtual bool hasOperand(const SCEV *Op) const; - - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); @@ -180,6 +166,38 @@ namespace llvm { /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { + public: + /// LoopDisposition - An enum describing the relationship between a + /// SCEV and a loop. + enum LoopDisposition { + LoopVariant, ///< The SCEV is loop-variant (unknown). + LoopInvariant, ///< The SCEV is loop-invariant. + LoopComputable ///< The SCEV varies predictably with the loop. + }; + + /// BlockDisposition - An enum describing the relationship between a + /// SCEV and a basic block. + enum BlockDisposition { + DoesNotDominateBlock, ///< The SCEV does not dominate the block. + DominatesBlock, ///< The SCEV dominates the block. + ProperlyDominatesBlock ///< The SCEV properly dominates the block. + }; + + /// Convenient NoWrapFlags manipulation that hides enum casts and is + /// visible in the ScalarEvolution name space. + static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) { + return (SCEV::NoWrapFlags)(Flags & Mask); + } + static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, + SCEV::NoWrapFlags OnFlags) { + return (SCEV::NoWrapFlags)(Flags | OnFlags); + } + static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, + SCEV::NoWrapFlags OffFlags) { + return (SCEV::NoWrapFlags)(Flags & ~OffFlags); + } + + private: /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { @@ -214,9 +232,14 @@ namespace llvm { /// counts and things. SCEVCouldNotCompute CouldNotCompute; - /// Scalars - This is a cache of the scalars we have analyzed so far. + /// ValueExprMapType - The typedef for ValueExprMap. /// - std::map Scalars; + typedef DenseMap > + ValueExprMapType; + + /// ValueExprMap - This is a cache of the values we have analyzed so far. + /// + ValueExprMapType ValueExprMap; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently includes an exact count and a maximum count. @@ -262,6 +285,46 @@ namespace llvm { std::map > ValuesAtScopes; + /// LoopDispositions - Memoized computeLoopDisposition results. + std::map > LoopDispositions; + + /// computeLoopDisposition - Compute a LoopDisposition value. + LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); + + /// BlockDispositions - Memoized computeBlockDisposition results. + std::map > BlockDispositions; + + /// computeBlockDisposition - Compute a BlockDisposition value. + BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// UnsignedRanges - Memoized results from getUnsignedRange + DenseMap UnsignedRanges; + + /// SignedRanges - Memoized results from getSignedRange + DenseMap SignedRanges; + + /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. + const ConstantRange &setUnsignedRange(const SCEV *S, + const ConstantRange &CR) { + std::pair::iterator, bool> Pair = + UnsignedRanges.insert(std::make_pair(S, CR)); + if (!Pair.second) + Pair.first->second = CR; + return Pair.first->second; + } + + /// setUnsignedRange - Set the memoized signed range for the given SCEV. + const ConstantRange &setSignedRange(const SCEV *S, + const ConstantRange &CR) { + std::pair::iterator, bool> Pair = + SignedRanges.insert(std::make_pair(S, CR)); + if (!Pair.second) + Pair.first->second = CR; + return Pair.first->second; + } + /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. const SCEV *createSCEV(Value *V); @@ -281,7 +344,7 @@ namespace llvm { /// ForgetSymbolicValue - This looks up computed SCEV values for all /// instructions that depend on the given instruction and removes them from - /// the Scalars map if they reference SymName. This is used during PHI + /// the ValueExprMap map if they reference SymName. This is used during PHI /// resolution. void ForgetSymbolicName(Instruction *I, const SCEV *SymName); @@ -403,6 +466,9 @@ namespace llvm { bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// forgetMemoizedResults - Drop memoized information computed for S. + void forgetMemoizedResults(const SCEV *S); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -437,44 +503,41 @@ namespace llvm { const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); const SCEV *getAddExpr(SmallVectorImpl &Ops, - bool HasNUW = false, bool HasNSW = false); + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, - bool HasNUW = false, bool HasNSW = false) { + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { SmallVector Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getAddExpr(Ops, HasNUW, HasNSW); + return getAddExpr(Ops, Flags); } - const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, - const SCEV *Op2, - bool HasNUW = false, bool HasNSW = false) { + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { SmallVector Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); - return getAddExpr(Ops, HasNUW, HasNSW); + return getAddExpr(Ops, Flags); } const SCEV *getMulExpr(SmallVectorImpl &Ops, - bool HasNUW = false, bool HasNSW = false); + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, - bool HasNUW = false, bool HasNSW = false) { + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) + { SmallVector Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getMulExpr(Ops, HasNUW, HasNSW); + return getMulExpr(Ops, Flags); } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, - const Loop *L, - bool HasNUW = false, bool HasNSW = false); + const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(SmallVectorImpl &Operands, - const Loop *L, - bool HasNUW = false, bool HasNSW = false); + const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(const SmallVectorImpl &Operands, - const Loop *L, - bool HasNUW = false, bool HasNSW = false) { + const Loop *L, SCEV::NoWrapFlags Flags) { SmallVector NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L, HasNUW, HasNSW); + return getAddRecExpr(NewOp, L, Flags); } const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getSMaxExpr(SmallVectorImpl &Operands); @@ -509,10 +572,9 @@ namespace llvm { /// const SCEV *getNotSCEV(const SCEV *V); - /// getMinusSCEV - Return LHS-RHS. - /// - const SCEV *getMinusSCEV(const SCEV *LHS, - const SCEV *RHS); + /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. + const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be @@ -557,6 +619,12 @@ namespace llvm { const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + /// getPointerBase - Transitively follow the chain of pointer-type operands + /// until reaching a SCEV that does not have a single pointer operand. This + /// returns a SCEVUnknown pointer for well-formed pointer-type expressions, + /// but corner cases do exist. + const SCEV *getPointerBase(const SCEV *V); + /// getSCEVAtScope - Return a SCEV expression for the specified value /// at the specified scope in the program. The L value specifies a loop /// nest to evaluate the expression at, where null is the top-level or a @@ -670,6 +738,36 @@ namespace llvm { const SCEV *&LHS, const SCEV *&RHS); + /// getLoopDisposition - Return the "disposition" of the given SCEV with + /// respect to the given loop. + LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); + + /// isLoopInvariant - Return true if the value of the given SCEV is + /// unchanging in the specified loop. + bool isLoopInvariant(const SCEV *S, const Loop *L); + + /// hasComputableLoopEvolution - Return true if the given SCEV changes value + /// in a known way in the specified loop. This property being true implies + /// that the value is variant in the loop AND that we can emit an expression + /// to compute the value of the expression at any particular loop iteration. + bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); + + /// getLoopDisposition - Return the "disposition" of the given SCEV with + /// respect to the given block. + BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// dominates - Return true if elements that makes up the given SCEV + /// dominate the specified basic block. + bool dominates(const SCEV *S, const BasicBlock *BB); + + /// properlyDominates - Return true if elements that makes up the given SCEV + /// properly dominate the specified basic block. + bool properlyDominates(const SCEV *S, const BasicBlock *BB); + + /// hasOperand - Test whether the given SCEV has Op as a direct or + /// indirect operand. + bool hasOperand(const SCEV *S, const SCEV *Op) const; + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const;