X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=b052a82232479bd5a2f68cd930f2ba5601863c17;hb=c6743207e20904008d2de016adfa6b0a9355c0e7;hp=1c1298a9a15a9de27772428c9aa3d1ee1afd4e15;hpb=753ad615f96c3d56d6f17983bdba88012e88677c;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 1c1298a9a15..b052a822324 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // The ScalarEvolution class is an LLVM pass which can be used to analyze and -// catagorize scalar expressions in loops. It specializes in recognizing +// categorize scalar expressions in loops. It specializes in recognizing // general induction variables, representing them with the abstract and opaque // SCEV class. Given this analysis, trip counts of loops and other important // properties can be obtained. @@ -22,44 +22,61 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_H #include "llvm/Pass.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Support/DataTypes.h" +#include "llvm/Instructions.h" +#include "llvm/Function.h" +#include "llvm/System/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 +#include namespace llvm { class APInt; + class Constant; class ConstantInt; + class DominatorTree; class Type; class ScalarEvolution; class TargetData; - class SCEVConstant; - class SCEVTruncateExpr; - class SCEVZeroExtendExpr; - class SCEVCommutativeExpr; - class SCEVUDivExpr; - class SCEVSignExtendExpr; - class SCEVAddRecExpr; + class LLVMContext; + class Loop; + class LoopInfo; + class Operator; class SCEVUnknown; /// SCEV - This class represents an analyzed expression in the program. These - /// are reference-counted opaque objects that the client is not allowed to - /// do much with directly. + /// are opaque objects that the client is not allowed to do much with + /// directly. /// - class SCEV { - const unsigned SCEVType; // The SCEV baseclass this node corresponds to + class SCEV : public FoldingSetNode { + /// FastID - A reference to an Interned FoldingSetNodeID for this node. + /// The ScalarEvolution's BumpPtrAllocator holds the data. + FoldingSetNodeIDRef FastID; + // 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 miscellaneous 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) {} + explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : + FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} unsigned getSCEVType() const { return SCEVType; } + /// Profile - FoldingSet support. + void Profile(FoldingSetNodeID& ID) { ID = FastID; } + /// isLoopInvariant - Return true if the value of this SCEV is unchanging in /// the specified loop. virtual bool isLoopInvariant(const Loop *L) const = 0; @@ -82,26 +99,27 @@ namespace llvm { /// bool isOne() 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; + /// isAllOnesValue - Return true if the expression is a constant + /// all-ones value. + /// + 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(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } /// dump - This method is used for debugging. /// @@ -113,11 +131,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. @@ -131,15 +144,16 @@ namespace llvm { 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); @@ -162,6 +176,7 @@ namespace llvm { friend class SCEVCallbackVH; friend class SCEVExpander; + friend class SCEVUnknown; /// F - The function we are analyzing. /// @@ -171,34 +186,38 @@ namespace llvm { /// LoopInfo *LI; - /// TD - The target data information for the target we are targetting. + /// TD - The target data information for the target we are targeting. /// TargetData *TD; + /// DT - The dominator tree. + /// + DominatorTree *DT; + /// CouldNotCompute - This SCEV is used to represent unknown trip /// counts and things. - const SCEV* CouldNotCompute; + 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. + /// of a loop. This currently includes an exact count and a maximum count. /// 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 @@ -221,37 +240,42 @@ namespace llvm { /// exit value. std::map 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 > 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 > 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(GEPOperator *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 SCEV* SymName, - const SCEV* NewVal); + /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called + /// at most once for each SCEV+Loop pair. + /// + const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); + + /// 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 @@ -288,30 +312,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. + BackedgeTakenInfo 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, Value *Cond, - bool ExitWhen); + /// 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); + BackedgeTakenInfo 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); + BackedgeTakenInfo 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 @@ -319,15 +345,32 @@ namespace llvm { BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, bool isSigned); - /// getLoopPredecessor - If the given loop's header has exactly one unique - /// predecessor outside the loop, return it. Otherwise return null. - BasicBlock *getLoopPredecessor(const Loop *L); - /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one /// successor from which BB is reachable, or null if no such block is /// found. - BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + std::pair + getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + + /// 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 described 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 described 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 @@ -336,15 +379,24 @@ 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); + /// isKnownPredicateWithRanges - Test if the given expression is known to + /// satisfy the condition described by Pred and the known constant ranges + /// of LHS and RHS. + /// + bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// forgetSCEVUnknown - V is being deleted or RAUW'd; remove the + /// SCEVUnknown for it from the uniquing map, and optionally + /// clear its contents to point to a replacement value. + void forgetSCEVUnknown(Value *V, Value *NewV); 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 @@ -361,127 +413,139 @@ 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 &Ops); - const SCEV* getAddExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector 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, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector 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 Ops; + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, + const SCEV *Op2, + bool HasNUW = false, bool HasNSW = false) { + SmallVector 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 &Ops); - const SCEV* getMulExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector Ops; + const SCEV *getMulExpr(SmallVectorImpl &Ops, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector 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 &Operands, - const Loop *L); - const SCEV* getAddRecExpr(const SmallVectorImpl &Operands, - const Loop *L) { - SmallVector 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 &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddRecExpr(const SmallVectorImpl &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false) { + SmallVector NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, HasNUW, HasNSW); } - 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(); + 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(); + + /// getSizeOfExpr - Return an expression for sizeof on the given type. + /// + const SCEV *getSizeOfExpr(const Type *AllocTy); + + /// getAlignOfExpr - Return an expression for alignof on the given type. + /// + const SCEV *getAlignOfExpr(const Type *AllocTy); + + /// getOffsetOfExpr - Return an expression for offsetof on the given field. + /// + const SCEV *getOffsetOfExpr(const StructType *STy, unsigned FieldNo); + + /// getOffsetOfExpr - Return an expression for offsetof on the given field. + /// + const SCEV *getOffsetOfExpr(const Type *CTy, Constant *FieldNo); /// 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); - - /// getIntegerSCEV - Given an integer or FP 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 *getTruncateOrNoop(const SCEV *V, 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; - - /// setSCEV - Insert the specified SCEV into the map of current SCEVs for - /// the specified value. - void setSCEV(Value *V, const SCEV* H); + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); - /// 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. @@ -491,17 +555,23 @@ 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. - bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); + /// isLoopEntryGuardedByCond - 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, and to eliminate casts. + bool isLoopEntryGuardedByCond(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 @@ -514,62 +584,88 @@ 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. bool hasLoopInvariantBackedgeTakenCount(const Loop *L); - /// forgetLoopBackedgeTakenCount - This method should be called by the - /// client when it has changed a loop in a way that may effect - /// ScalarEvolution's ability to compute a trip count, or if the loop - /// is deleted. - void forgetLoopBackedgeTakenCount(const Loop *L); + /// forgetLoop - This method should be called by the client when it has + /// changed a loop in a way that may effect ScalarEvolution's ability to + /// compute a trip count, or if the loop is deleted. + void forgetLoop(const Loop *L); + + /// forgetValue - This method should be called by the client when it has + /// changed a value in a way that may effect its value, or which may + /// disconnect it from a def-use chain linking it to a loop. + void forgetValue(Value *V); - /// 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); + /// 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); + /// 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); + + /// isKnownPredicate - 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); + + /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with + /// predicate Pred. Return true iff any changes were made. If the + /// operands are provably equal or inequal, LHS and RHS are set to + /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. + /// + bool SimplifyICmpOperands(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: - // Uniquing tables. - std::map SCEVConstants; - std::map, - SCEVTruncateExpr*> SCEVTruncates; - std::map, - SCEVZeroExtendExpr*> SCEVZeroExtends; - std::map >, - SCEVCommutativeExpr*> SCEVCommExprs; - std::map, - SCEVUDivExpr*> SCEVUDivs; - std::map, - SCEVSignExtendExpr*> SCEVSignExtends; - std::map >, - SCEVAddRecExpr*> SCEVAddRecExprs; - std::map SCEVUnknowns; + FoldingSet UniqueSCEVs; + BumpPtrAllocator SCEVAllocator; }; }