diff options
Diffstat (limited to 'include/llvm/Analysis/ScalarEvolution.h')
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 354 |
1 files changed, 204 insertions, 150 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 9da5c59a5e54..ed5d18eaf981 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -22,37 +22,50 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_H #include "llvm/Pass.h" -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Instructions.h" +#include "llvm/Function.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/ConstantRange.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseMap.h" -#include <iosfwd> +#include <map> namespace llvm { class APInt; + class Constant; class ConstantInt; + class DominatorTree; class Type; class ScalarEvolution; class TargetData; + class LLVMContext; + class Loop; + class LoopInfo; + class Operator; /// 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 { - const unsigned SCEVType; // The SCEV baseclass this node corresponds to + class SCEV : public FastFoldingSetNode { + // The SCEV baseclass this node corresponds to + const unsigned short SCEVType; + protected: + /// SubclassData - This field is initialized to zero and may be used in + /// subclasses to store miscelaneous information. + unsigned short SubclassData; + + private: SCEV(const SCEV &); // DO NOT IMPLEMENT void operator=(const SCEV &); // DO NOT IMPLEMENT protected: virtual ~SCEV(); public: - explicit SCEV(unsigned SCEVTy) : - SCEVType(SCEVTy) {} - - virtual void Profile(FoldingSetNodeID &ID) const = 0; + explicit SCEV(const FoldingSetNodeID &ID, unsigned SCEVTy) : + FastFoldingSetNode(ID), SCEVType(SCEVTy), SubclassData(0) {} unsigned getSCEVType() const { return SCEVType; } @@ -83,26 +96,22 @@ namespace llvm { /// 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 const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const = 0; + /// 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(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } /// dump - This method is used for debugging. /// @@ -114,11 +123,6 @@ namespace llvm { return OS; } - inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { - S.print(OS); - return OS; - } - /// SCEVCouldNotCompute - An object of this class is returned by queries that /// could not be answered. For example, if you ask for the number of /// iterations of a linked-list traversal loop, you will get one of these. @@ -128,20 +132,20 @@ namespace llvm { 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 const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) 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); @@ -163,7 +167,7 @@ namespace llvm { }; friend class SCEVCallbackVH; - friend class SCEVExpander; + friend struct SCEVExpander; /// F - The function we are analyzing. /// @@ -183,7 +187,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map<SCEVCallbackVH, const SCEV*> Scalars; + std::map<SCEVCallbackVH, const SCEV *> Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -191,16 +195,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. - const SCEV* Exact; + const SCEV *Exact; - /// Exact - An expression indicating the least maximum backedge-taken + /// Max - An expression indicating the least maximum backedge-taken /// count of the loop that is known, or a SCEVCouldNotCompute. - const SCEV* Max; + const SCEV *Max; - /*implicit*/ BackedgeTakenInfo(const SCEV* exact) : + /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : Exact(exact), Max(exact) {} - BackedgeTakenInfo(const SCEV* exact, const SCEV* max) : + BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : Exact(exact), Max(max) {} /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any @@ -223,37 +227,42 @@ namespace llvm { /// exit value. std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; - /// ValuesAtScopes - This map contains entries for all the instructions - /// that we attempt to compute getSCEVAtScope information for without - /// using SCEV techniques, which can be expensive. - std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; + /// ValuesAtScopes - This map contains entries for all the expressions + /// that we attempt to compute getSCEVAtScope information for, which can + /// be expensive in extreme cases. + std::map<const SCEV *, + std::map<const Loop *, const SCEV *> > ValuesAtScopes; /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. - const SCEV* createSCEV(Value *V); + const SCEV *createSCEV(Value *V); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. - const SCEV* createNodeForPHI(PHINode *PN); + const SCEV *createNodeForPHI(PHINode *PN); /// createNodeForGEP - Provide the special handling we need to analyze GEP /// SCEVs. - const SCEV* createNodeForGEP(User *GEP); + const SCEV *createNodeForGEP(Operator *GEP); + + /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called + /// at most once for each SCEV+Loop pair. + /// + const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); - /// 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 SCEV* SymName, - const SCEV* NewVal); + /// 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 + /// resolution. + void ForgetSymbolicName(Instruction *I, const SCEV *SymName); /// 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); + const SCEV *getBECount(const SCEV *Start, + const SCEV *End, + const SCEV *Step, + bool NoWrap); /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed @@ -290,31 +299,32 @@ namespace llvm { BasicBlock *FBB); /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition - /// of 'icmp op load X, cst', try to see if we can compute the trip count. - const SCEV* + /// of 'icmp op load X, cst', try to see if we can compute the + /// backedge-taken count. + const SCEV * ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, const Loop *L, ICmpInst::Predicate p); - /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute + /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute /// 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 CouldNotCompute. - const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L, + /// evaluate the backedge-taken 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 /// CouldNotCompute. - const SCEV* HowFarToZero(const SCEV *V, const Loop *L); + 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 /// CouldNotCompute. - const SCEV* HowFarToNonZero(const SCEV *V, const Loop *L); + 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 @@ -332,11 +342,25 @@ 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); + /// isImpliedCond - Test whether the condition described by Pred, LHS, + /// and RHS is true whenever the given Cond value evaluates to true. + bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + bool Inverse); + + /// isImpliedCondOperands - Test whether the condition described by Pred, + /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, + /// and FoundRHS is true. + bool isImpliedCondOperands(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS); + + /// isImpliedCondOperandsHelper - Test whether the condition described by + /// Pred, LHS, and RHS is true whenever the condition desribed by Pred, + /// FoundLHS, and FoundRHS is true. + bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS); /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a @@ -345,15 +369,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 F->getContext(); } + /// 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 @@ -370,127 +391,129 @@ namespace llvm { /// this is the pointer-sized integer type. const Type *getEffectiveSCEVType(const Type *Ty) const; - /// getSCEV - Return a SCEV expression handle for the full generality of the + /// getSCEV - Return a SCEV expression for the full generality of the /// specified expression. - 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<const SCEV*> &Ops); - const SCEV* getAddExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> 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<const SCEV *> &Ops, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getAddExpr(Ops); + return getAddExpr(Ops, HasNUW, HasNSW); } - const SCEV* getAddExpr(const SCEV* Op0, const SCEV* Op1, - const SCEV* Op2) { - SmallVector<const SCEV*, 3> Ops; + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, + const SCEV *Op2, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 3> Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); - return getAddExpr(Ops); + return getAddExpr(Ops, HasNUW, HasNSW); } - const SCEV* getMulExpr(SmallVectorImpl<const SCEV*> &Ops); - const SCEV* getMulExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> Ops; + const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getMulExpr(Ops); + return getMulExpr(Ops, HasNUW, HasNSW); } - const SCEV* getUDivExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getAddRecExpr(const SCEV* Start, const SCEV* Step, - const Loop *L); - const SCEV* getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands, - const Loop *L); - const SCEV* getAddRecExpr(const SmallVectorImpl<const SCEV*> &Operands, - const Loop *L) { - SmallVector<const SCEV*, 4> NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L); + 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 SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, HasNUW, HasNSW); } - const SCEV* getSMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getSMaxExpr(SmallVectorImpl<const SCEV*> &Operands); - const SCEV* getUMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUMaxExpr(SmallVectorImpl<const SCEV*> &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(); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getFieldOffsetExpr(const StructType *STy, unsigned FieldNo); + const SCEV *getAllocSizeExpr(const Type *AllocTy); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// - const SCEV* getNegativeSCEV(const SCEV* V); + const SCEV *getNegativeSCEV(const SCEV *V); /// getNotSCEV - Return the SCEV object corresponding to ~V. /// - const SCEV* getNotSCEV(const SCEV* V); + const SCEV *getNotSCEV(const SCEV *V); /// getMinusSCEV - Return LHS-RHS. /// - const SCEV* getMinusSCEV(const SCEV* LHS, - const SCEV* 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. - const SCEV* getTruncateOrZeroExtend(const SCEV* 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. - const SCEV* getTruncateOrSignExtend(const SCEV* 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. - const SCEV* getNoopOrZeroExtend(const SCEV* 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. - const SCEV* getNoopOrSignExtend(const SCEV* 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); + 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. - const SCEV* getTruncateOrNoop(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); /// getIntegerSCEV - Given a SCEVable type, create a constant for the /// specified signed integer value and return a SCEV for the constant. - const SCEV* 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); + 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. - bool hasSCEV(Value *V) const; + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); - /// setSCEV - Insert the specified SCEV into the map of current SCEVs for - /// the specified value. - void setSCEV(Value *V, const SCEV* H); - - /// getSCEVAtScope - Return a SCEV expression handle for the specified value + /// 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 /// specified loop is immediately inside of the loop. @@ -500,18 +523,24 @@ namespace llvm { /// /// 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); + const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); /// getSCEVAtScope - This is a convenience function which does /// getSCEVAtScope(getSCEV(V), L). - const SCEV* 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 - /// expressions in loop trip counts. + /// expressions in loop trip counts, and to eliminate casts. bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is + /// protected by a conditional between LHS and RHS. This is used to + /// to eliminate casts. + bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + /// getBackedgeTakenCount - If the specified loop has a predictable /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute /// object. The backedge-taken count is the number of times the loop header @@ -523,12 +552,12 @@ namespace llvm { /// loop-invariant backedge-taken count (see /// hasLoopInvariantBackedgeTakenCount). /// - const SCEV* 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. - const SCEV* 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. @@ -545,24 +574,49 @@ namespace llvm { /// 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); + 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); + /// getUnsignedRange - Determine the unsigned range for a particular SCEV. + /// + ConstantRange getUnsignedRange(const SCEV *S); - /// GetMinSignBits - Determine the minimum number of sign bits that S is - /// guaranteed to begin with. - uint32_t GetMinSignBits(const SCEV* S); + /// getSignedRange - Determine the signed range for a particular SCEV. + /// + ConstantRange getSignedRange(const SCEV *S); + + /// isKnownNegative - Test if the given expression is known to be negative. + /// + bool isKnownNegative(const SCEV *S); + + /// isKnownPositive - Test if the given expression is known to be positive. + /// + bool isKnownPositive(const SCEV *S); + + /// isKnownNonNegative - Test if the given expression is known to be + /// non-negative. + /// + bool isKnownNonNegative(const SCEV *S); + + /// isKnownNonPositive - Test if the given expression is known to be + /// non-positive. + /// + bool isKnownNonPositive(const SCEV *S); + + /// isKnownNonZero - Test if the given expression is known to be + /// non-zero. + /// + bool isKnownNonZero(const SCEV *S); + + /// isKnownNonZero - Test if the given expression is known to satisfy + /// the condition described by Pred, LHS, and RHS. + /// + bool isKnownPredicate(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; - void print(raw_ostream &OS, const Module* = 0) const; - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } + virtual void print(raw_ostream &OS, const Module* = 0) const; private: FoldingSet<SCEV> UniqueSCEVs; |