X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=eec7ec8de1a8a0fa0dbea41743ced381586714bb;hb=59ae6b99872953761dfda5984801d23a66692673;hp=d43d2449ebe2baec413d0c33a89baf7062157b6f;hpb=859b4824eeb2d88c441e855afe3dd7827dfd62a4;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index d43d2449ebe..eec7ec8de1a 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -25,37 +25,35 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseMap.h" #include namespace llvm { class APInt; class ConstantInt; class Type; - class SCEVHandle; class ScalarEvolution; class TargetData; + class LLVMContext; - /// SCEV - This class represent an analyzed expression in the program. These - /// are reference counted opaque objects that the client is not allowed to - /// do much with directly. + /// 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 { + class SCEV : public FoldingSetNode { const unsigned SCEVType; // The SCEV baseclass this node corresponds to - mutable unsigned RefCount; - - friend class SCEVHandle; - void addRef() const { ++RefCount; } - void dropRef() const { - if (--RefCount == 0) - delete this; - } SCEV(const SCEV &); // DO NOT IMPLEMENT void operator=(const SCEV &); // DO NOT IMPLEMENT protected: virtual ~SCEV(); public: - explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} + explicit SCEV(unsigned SCEVTy) : + SCEVType(SCEVTy) {} + + virtual void Profile(FoldingSetNodeID &ID) const = 0; unsigned getSCEVType() const { return SCEVType; } @@ -81,14 +79,19 @@ namespace llvm { /// bool isOne() const; + /// isAllOnesValue - Return true if the expression is a constant + /// all-ones value. + /// + bool isAllOnesValue() const; + /// replaceSymbolicValuesWithConcrete - If this SCEV internally references /// the symbolic value "Sym", construct and return a new SCEV that produces /// the same value, but which uses the concrete value Conc instead of the /// symbolic value. If this SCEV does not use the symbolic value, it /// returns itself. - virtual SCEVHandle - replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc, + virtual const SCEV * + replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const = 0; /// dominates - Return true if elements that makes up this SCEV dominates @@ -124,16 +127,16 @@ namespace llvm { /// marker. struct SCEVCouldNotCompute : public SCEV { SCEVCouldNotCompute(); - ~SCEVCouldNotCompute(); // None of these methods are valid for this object. + virtual void Profile(FoldingSetNodeID &ID) const; 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 SCEVHandle - replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc, + virtual const SCEV * + replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const; virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { @@ -145,74 +148,23 @@ namespace llvm { static bool classof(const SCEV *S); }; - /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be - /// notified whenever a Value is deleted. - class SCEVCallbackVH : public CallbackVH { - ScalarEvolution *SE; - virtual void deleted(); - virtual void allUsesReplacedWith(Value *New); - public: - SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); - }; - - /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, - /// freeing the objects when the last reference is dropped. - class SCEVHandle { - const SCEV *S; - SCEVHandle(); // DO NOT IMPLEMENT - public: - SCEVHandle(const SCEV *s) : S(s) { - assert(S && "Cannot create a handle to a null SCEV!"); - S->addRef(); - } - SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) { - S->addRef(); - } - ~SCEVHandle() { S->dropRef(); } - - operator const SCEV*() const { return S; } - - const SCEV &operator*() const { return *S; } - const SCEV *operator->() const { return S; } - - bool operator==(const SCEV *RHS) const { return S == RHS; } - bool operator!=(const SCEV *RHS) const { return S != RHS; } - - const SCEVHandle &operator=(SCEV *RHS) { - if (S != RHS) { - S->dropRef(); - S = RHS; - S->addRef(); - } - return *this; - } - - const SCEVHandle &operator=(const SCEVHandle &RHS) { - if (S != RHS.S) { - S->dropRef(); - S = RHS.S; - S->addRef(); - } - return *this; - } - }; - - template struct simplify_type; - template<> struct simplify_type { - typedef const SCEV* SimpleType; - static SimpleType getSimplifiedValue(const SCEVHandle &Node) { - return Node; - } - }; - template<> struct simplify_type - : public simplify_type {}; - /// ScalarEvolution - This class is the main scalar evolution driver. Because /// client code (intentionally) can't do much with the SCEV objects directly, /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { + /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be + /// notified whenever a Value is deleted. + class SCEVCallbackVH : public CallbackVH { + ScalarEvolution *SE; + virtual void deleted(); + virtual void allUsesReplacedWith(Value *New); + public: + SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); + }; + friend class SCEVCallbackVH; + friend class SCEVExpander; /// F - The function we are analyzing. /// @@ -226,13 +178,13 @@ namespace llvm { /// TargetData *TD; - /// UnknownValue - This SCEV is used to represent unknown trip counts and - /// things. - SCEVHandle UnknownValue; + /// CouldNotCompute - This SCEV is used to represent unknown trip + /// counts and things. + SCEVCouldNotCompute CouldNotCompute; /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map Scalars; + std::map Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -240,19 +192,16 @@ namespace llvm { struct BackedgeTakenInfo { /// Exact - An expression indicating the exact backedge-taken count of /// the loop if it is known, or a SCEVCouldNotCompute otherwise. - SCEVHandle Exact; + const SCEV *Exact; /// Exact - An expression indicating the least maximum backedge-taken /// count of the loop that is known, or a SCEVCouldNotCompute. - SCEVHandle Max; - - /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : - Exact(exact), Max(exact) {} + const SCEV *Max; /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : Exact(exact), Max(exact) {} - BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : + BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : Exact(exact), Max(max) {} /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any @@ -282,23 +231,30 @@ namespace llvm { /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. - SCEVHandle createSCEV(Value *V); + const SCEV *createSCEV(Value *V); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. - SCEVHandle createNodeForPHI(PHINode *PN); + const SCEV *createNodeForPHI(PHINode *PN); /// createNodeForGEP - Provide the special handling we need to analyze GEP /// SCEVs. - SCEVHandle createNodeForGEP(User *GEP); + const SCEV *createNodeForGEP(User *GEP); /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value /// for the specified instruction and replaces any references to the /// symbolic value SymName with the specified value. This is used during /// PHI resolution. void ReplaceSymbolicValueWithConcrete(Instruction *I, - const SCEVHandle &SymName, - const SCEVHandle &NewVal); + const SCEV *SymName, + const SCEV *NewVal); + + /// getBECount - Subtract the end and start values and divide by the step, + /// rounding up, to get the number of times the backedge is executed. Return + /// CouldNotCompute if an intermediate computation overflows. + const SCEV *getBECount(const SCEV *Start, + const SCEV *End, + const SCEV *Step); /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed @@ -309,9 +265,34 @@ namespace llvm { /// loop will iterate. BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); + /// ComputeBackedgeTakenCountFromExit - Compute the number of times the + /// backedge of the specified loop will execute if it exits via the + /// specified block. + BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, + BasicBlock *ExitingBlock); + + /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the + /// backedge of the specified loop will execute if its exit condition + /// were a conditional branch of ExitCond, TBB, and FBB. + BackedgeTakenInfo + ComputeBackedgeTakenCountFromExitCond(const Loop *L, + Value *ExitCond, + BasicBlock *TBB, + BasicBlock *FBB); + + /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of + /// times the backedge of the specified loop will execute if its exit + /// condition were a conditional branch of the ICmpInst ExitCond, TBB, + /// and FBB. + BackedgeTakenInfo + ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, + ICmpInst *ExitCond, + BasicBlock *TBB, + BasicBlock *FBB); + /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the trip count. - SCEVHandle + const SCEV * ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, const Loop *L, @@ -321,23 +302,24 @@ namespace llvm { /// a constant number of times (the condition evolves only from constants), /// try to evaluate a few iterations of the loop until we get the exit /// condition gets a value of ExitWhen (true or false). If we cannot - /// evaluate the trip count of the loop, return UnknownValue. - SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, - bool ExitWhen); + /// evaluate the trip count of the loop, return CouldNotCompute. + const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, + Value *Cond, + bool ExitWhen); /// HowFarToZero - Return the number of times a backedge comparing the /// specified value to zero will execute. If not computable, return - /// UnknownValue. - SCEVHandle HowFarToZero(const SCEV *V, const Loop *L); + /// CouldNotCompute. + const SCEV *HowFarToZero(const SCEV *V, const Loop *L); /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return - /// UnknownValue. - SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L); + /// CouldNotCompute. + const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return - /// UnknownValue. isSigned specifies whether the less-than is signed. + /// CouldNotCompute. isSigned specifies whether the less-than is signed. BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, bool isSigned); @@ -351,6 +333,12 @@ namespace llvm { /// found. BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + /// isNecessaryCond - Test whether the given CondValue value is a condition + /// which is at least as strict as the one described by Pred, LHS, and RHS. + bool isNecessaryCond(Value *Cond, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + bool Inverse); + /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence @@ -358,15 +346,12 @@ namespace llvm { Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L); - /// forgetLoopPHIs - Delete the memoized SCEVs associated with the - /// PHI nodes in the given loop. This is used when the trip count of - /// the loop may have changed. - void forgetLoopPHIs(const Loop *L); - public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); + LLVMContext *getContext() const { return Context; } + /// isSCEVable - Test if values of the given type are analyzable within /// the SCEV framework. This primarily includes integer types, and it /// can optionally include pointer types if the ScalarEvolution class @@ -385,93 +370,115 @@ namespace llvm { /// getSCEV - Return a SCEV expression handle for the full generality of the /// specified expression. - SCEVHandle getSCEV(Value *V); - - SCEVHandle getConstant(ConstantInt *V); - SCEVHandle getConstant(const APInt& Val); - SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); - SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); - SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); - SCEVHandle getAddExpr(std::vector &Ops); - SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector Ops; + const SCEV *getSCEV(Value *V); + + const SCEV *getConstant(ConstantInt *V); + const SCEV *getConstant(const APInt& Val); + const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); + const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); + const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAddExpr(SmallVectorImpl &Ops); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector Ops; Ops.push_back(LHS); Ops.push_back(RHS); return getAddExpr(Ops); } - SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, - const SCEVHandle &Op2) { - std::vector Ops; + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, + const SCEV *Op2) { + SmallVector Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); return getAddExpr(Ops); } - SCEVHandle getMulExpr(std::vector &Ops); - SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector Ops; + const SCEV *getMulExpr(SmallVectorImpl &Ops); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector Ops; Ops.push_back(LHS); Ops.push_back(RHS); return getMulExpr(Ops); } - SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); - SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, + const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L); - SCEVHandle getAddRecExpr(std::vector &Operands, + const SCEV *getAddRecExpr(SmallVectorImpl &Operands, const Loop *L); - SCEVHandle getAddRecExpr(const std::vector &Operands, + const SCEV *getAddRecExpr(const SmallVectorImpl &Operands, const Loop *L) { - std::vector NewOp(Operands); + SmallVector NewOp(Operands.begin(), Operands.end()); return getAddRecExpr(NewOp, L); } - SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); - SCEVHandle getSMaxExpr(std::vector Operands); - SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); - SCEVHandle getUMaxExpr(std::vector Operands); - SCEVHandle getUnknown(Value *V); - SCEVHandle getCouldNotCompute(); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// - SCEVHandle getNegativeSCEV(const SCEVHandle &V); + const SCEV *getNegativeSCEV(const SCEV *V); /// getNotSCEV - Return the SCEV object corresponding to ~V. /// - SCEVHandle getNotSCEV(const SCEVHandle &V); + const SCEV *getNotSCEV(const SCEV *V); /// getMinusSCEV - Return LHS-RHS. /// - SCEVHandle getMinusSCEV(const SCEVHandle &LHS, - const SCEVHandle &RHS); + const SCEV *getMinusSCEV(const SCEV *LHS, + const SCEV *RHS); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is zero extended. - SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); + const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is sign extended. - SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); + const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is zero extended. The conversion must not be narrowing. - SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty); + const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is sign extended. The conversion must not be narrowing. - SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty); + const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); + + /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of + /// the input value to the specified type. If the type must be extended, + /// it is extended with unspecified bits. The conversion must not be + /// narrowing. + const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the /// input value to the specified type. The conversion must not be /// widening. - SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty); + const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); - /// getIntegerSCEV - Given an integer or FP type, create a constant for the + /// getIntegerSCEV - Given a SCEVable type, create a constant for the /// specified signed integer value and return a SCEV for the constant. - SCEVHandle getIntegerSCEV(int Val, const Type *Ty); + const SCEV *getIntegerSCEV(int Val, const Type *Ty); + + /// getUMaxFromMismatchedTypes - Promote the operands to the wider of + /// the types using zero-extension, and then perform a umax operation + /// with them. + const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); + + /// getUMinFromMismatchedTypes - Promote the operands to the wider of + /// the types using zero-extension, and then perform a umin operation + /// with them. + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); /// hasSCEV - Return true if the SCEV for this value has already been /// computed. @@ -479,7 +486,7 @@ namespace llvm { /// setSCEV - Insert the specified SCEV into the map of current SCEVs for /// the specified value. - void setSCEV(Value *V, const SCEVHandle &H); + void setSCEV(Value *V, const SCEV *H); /// getSCEVAtScope - Return a SCEV expression handle for the specified value /// at the specified scope in the program. The L value specifies a loop @@ -489,13 +496,13 @@ namespace llvm { /// This method can be used to compute the exit value for a variable defined /// in a loop by querying what the value will hold in the parent loop. /// - /// If this value is not computable at this scope, a SCEVCouldNotCompute - /// object is returned. - SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L); + /// In the case that a relevant loop exit value cannot be computed, the + /// original value V is returned. + const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); /// getSCEVAtScope - This is a convenience function which does /// getSCEVAtScope(getSCEV(V), L). - SCEVHandle getSCEVAtScope(Value *V, const Loop *L); + const SCEV *getSCEVAtScope(Value *V, const Loop *L); /// isLoopGuardedByCond - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. This is used to help avoid max @@ -514,12 +521,12 @@ namespace llvm { /// loop-invariant backedge-taken count (see /// hasLoopInvariantBackedgeTakenCount). /// - SCEVHandle getBackedgeTakenCount(const Loop *L); + const SCEV *getBackedgeTakenCount(const Loop *L); /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except /// return the least SCEV value that is known never to be less than the /// actual backedge taken count. - SCEVHandle getMaxBackedgeTakenCount(const Loop *L); + const SCEV *getMaxBackedgeTakenCount(const Loop *L); /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop /// has an analyzable loop-invariant backedge-taken count. @@ -531,6 +538,21 @@ namespace llvm { /// is deleted. void forgetLoopBackedgeTakenCount(const Loop *L); + /// GetMinTrailingZeros - Determine the minimum number of zero bits that S + /// is guaranteed to end in (at every loop iteration). It is, at the same + /// time, the minimum number of times S is divisible by 2. For example, + /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the + /// bitwidth of S. + uint32_t GetMinTrailingZeros(const SCEV *S); + + /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is + /// guaranteed to begin with (at every loop iteration). + uint32_t GetMinLeadingZeros(const SCEV *S); + + /// GetMinSignBits - Determine the minimum number of sign bits that S is + /// guaranteed to begin with. + uint32_t GetMinSignBits(const SCEV *S); + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -539,6 +561,10 @@ namespace llvm { void print(std::ostream *OS, const Module* M = 0) const { if (OS) print(*OS, M); } + + private: + FoldingSet UniqueSCEVs; + BumpPtrAllocator SCEVAllocator; }; }