X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=38c50d1fbed556d071eb6b1c0f1672d371378940;hb=1f6efa3996dd1929fbc129203ce5009b620e6969;hp=af5d10e6b7849d7711ece22b6699fb12075acb57;hpb=aa11defd1c66dbde0c757c99791c4ae4d740fc3e;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index af5d10e6b78..38c50d1fbed 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. @@ -24,7 +24,7 @@ #include "llvm/Pass.h" #include "llvm/Instructions.h" #include "llvm/Function.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" @@ -44,44 +44,42 @@ namespace llvm { class Loop; class LoopInfo; class Operator; + class SCEVUnknown; + class SCEV; + 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 FastFoldingSetNode { + class SCEV : public FoldingSetNode { + friend struct FoldingSetTrait; + + /// 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 miscelaneous information. + /// 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(const FoldingSetNodeID &ID, unsigned SCEVTy) : - FastFoldingSetNode(ID), SCEVType(SCEVTy), SubclassData(0) {} + 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. /// @@ -96,28 +94,31 @@ 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. /// void dump() const; }; + // Specialize FoldingSetTrait for SCEV to avoid needing to compute + // temporary FoldingSetNodeID values. + template<> struct FoldingSetTrait : DefaultFoldingSetTrait { + static void Profile(const SCEV &X, FoldingSetNodeID& ID) { + ID = X.FastID; + } + static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, + FoldingSetNodeID &TempID) { + return ID == X.FastID; + } + static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { + return X.FastID.ComputeHash(); + } + }; + inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { S.print(OS); return OS; @@ -131,21 +132,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); @@ -156,6 +142,24 @@ 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. + }; + + private: /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { @@ -168,6 +172,7 @@ namespace llvm { friend class SCEVCallbackVH; friend class SCEVExpander; + friend class SCEVUnknown; /// F - The function we are analyzing. /// @@ -177,7 +182,7 @@ 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; @@ -189,12 +194,17 @@ 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 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 @@ -237,6 +247,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); @@ -256,7 +306,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); @@ -305,7 +355,7 @@ namespace llvm { /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the /// backedge-taken count. - const SCEV * + BackedgeTakenInfo ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, const Loop *L, @@ -323,12 +373,12 @@ namespace llvm { /// 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 @@ -336,31 +386,29 @@ 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, + /// isImpliedCond - Test whether the condition described by Pred, LHS, and + /// RHS is true whenever the given FoundCondValue value evaluates to true. + bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, + Value *FoundCondValue, bool Inverse); /// isImpliedCondOperands - Test whether the condition described by Pred, - /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, + /// 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 desribed by Pred, + /// 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, @@ -373,6 +421,16 @@ namespace llvm { Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 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); + + /// forgetMemoizedResults - Drop memoized information computed for S. + void forgetMemoizedResults(const SCEV *S); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -515,10 +573,6 @@ namespace llvm { /// widening. 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(int64_t 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. @@ -547,11 +601,11 @@ namespace llvm { /// getSCEVAtScope(getSCEV(V), 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 + /// 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 isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); + 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 @@ -629,12 +683,51 @@ namespace llvm { /// bool isKnownNonZero(const SCEV *S); - /// isKnownNonZero - Test if the given expression is known to satisfy + /// 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); + + /// 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; @@ -643,6 +736,11 @@ namespace llvm { private: FoldingSet UniqueSCEVs; BumpPtrAllocator SCEVAllocator; + + /// FirstUnknown - The head of a linked list of all SCEVUnknown + /// values that have been allocated. This is used by releaseMemory + /// to locate them all and call their destructors. + SCEVUnknown *FirstUnknown; }; }