some comment improvements.
[oota-llvm.git] / include / llvm / Analysis / ScalarEvolution.h
index 558cd011f5e5ed42bce3978b5386ee9dc0446d29..d1938061bef6958a462ab726f603680594bd62d6 100644 (file)
@@ -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.
@@ -30,7 +30,6 @@
 #include "llvm/Support/ConstantRange.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/DenseMap.h"
-#include <iosfwd>
 #include <map>
 
 namespace llvm {
@@ -45,44 +44,42 @@ namespace llvm {
   class Loop;
   class LoopInfo;
   class Operator;
+  class SCEVUnknown;
+  class SCEV;
+  template<> struct FoldingSetTrait<SCEV>;
 
   /// 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<SCEV>;
+
+    /// 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.
     ///
@@ -97,32 +94,32 @@ 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;
-
     /// 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); }
+    void print(raw_ostream &OS) const;
 
     /// dump - This method is used for debugging.
     ///
     void dump() const;
   };
 
-  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
-    S.print(OS);
-    return OS;
-  }
+  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
+  // temporary FoldingSetNodeID values.
+  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
+    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 std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
+  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
     S.print(OS);
     return OS;
   }
@@ -135,17 +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;
-    }
-
     /// 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 {
@@ -167,7 +171,8 @@ namespace llvm {
     };
 
     friend class SCEVCallbackVH;
-    friend struct SCEVExpander;
+    friend class SCEVExpander;
+    friend class SCEVUnknown;
 
     /// F - The function we are analyzing.
     ///
@@ -177,20 +182,29 @@ 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.
     SCEVCouldNotCompute CouldNotCompute;
 
-    /// Scalars - This is a cache of the scalars we have analyzed so far.
+    /// ValueExprMapType - The typedef for ValueExprMap.
     ///
-    std::map<SCEVCallbackVH, const SCEV *> Scalars;
+    typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
+      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
@@ -227,10 +241,51 @@ 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;
+
+    /// LoopDispositions - Memoized computeLoopDisposition results.
+    std::map<const SCEV *,
+             std::map<const Loop *, LoopDisposition> > LoopDispositions;
+
+    /// computeLoopDisposition - Compute a LoopDisposition value.
+    LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
+
+    /// BlockDispositions - Memoized computeBlockDisposition results.
+    std::map<const SCEV *,
+             std::map<const BasicBlock *, BlockDisposition> > BlockDispositions;
+
+    /// computeBlockDisposition - Compute a BlockDisposition value.
+    BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
+
+    /// UnsignedRanges - Memoized results from getUnsignedRange
+    DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
+
+    /// SignedRanges - Memoized results from getSignedRange
+    DenseMap<const SCEV *, ConstantRange> SignedRanges;
+
+    /// setUnsignedRange - Set the memoized unsigned range for the given SCEV.
+    const ConstantRange &setUnsignedRange(const SCEV *S,
+                                          const ConstantRange &CR) {
+      std::pair<DenseMap<const SCEV *, ConstantRange>::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<DenseMap<const SCEV *, ConstantRange>::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.
@@ -242,11 +297,16 @@ namespace llvm {
 
     /// createNodeForGEP - Provide the special handling we need to analyze GEP
     /// SCEVs.
-    const SCEV *createNodeForGEP(Operator *GEP);
+    const SCEV *createNodeForGEP(GEPOperator *GEP);
+
+    /// 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
+    /// the ValueExprMap map if they reference SymName. This is used during PHI
     /// resolution.
     void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
 
@@ -255,7 +315,8 @@ namespace llvm {
     /// CouldNotCompute if an intermediate computation overflows.
     const SCEV *getBECount(const SCEV *Start,
                            const SCEV *End,
-                           const SCEV *Step);
+                           const SCEV *Step,
+                           bool NoWrap);
 
     /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
     /// loop, lazily computing new values if the loop hasn't been analyzed
@@ -294,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,
@@ -312,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
@@ -325,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<BasicBlock *, BasicBlock *>
+    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,
@@ -362,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();
@@ -384,7 +453,7 @@ 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);
 
@@ -395,37 +464,45 @@ namespace llvm {
     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) {
+    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) {
+                           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) {
+    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 Loop *L,
+                              bool HasNUW = false, bool HasNSW = false);
     const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
-                              const Loop *L);
+                              const Loop *L,
+                              bool HasNUW = false, bool HasNSW = false);
     const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
-                              const Loop *L) {
+                              const Loop *L,
+                              bool HasNUW = false, bool HasNSW = false) {
       SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
-      return getAddRecExpr(NewOp, L);
+      return getAddRecExpr(NewOp, L, HasNUW, HasNSW);
     }
     const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
     const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
@@ -433,11 +510,25 @@ namespace llvm {
     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();
 
+    /// 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);
@@ -446,10 +537,11 @@ namespace llvm {
     ///
     const SCEV *getNotSCEV(const SCEV *V);
 
-    /// getMinusSCEV - Return LHS-RHS.
-    ///
-    const SCEV *getMinusSCEV(const SCEV *LHS,
-                             const SCEV *RHS);
+    /// getMinusSCEV - Return LHS-RHS.  Minus is represented in SCEV as A+B*-1,
+    /// and thus the HasNUW and HasNSW bits apply to the resultant add, not
+    /// whether the sub would have overflowed.
+    const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
+                             bool HasNUW = false, bool HasNSW = false);
 
     /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
     /// of the input value to the specified type.  If the type must be
@@ -482,10 +574,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(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.
@@ -498,7 +586,7 @@ namespace llvm {
     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.
@@ -514,11 +602,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
@@ -548,11 +636,15 @@ namespace llvm {
     /// 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
@@ -592,24 +684,64 @@ 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;
-    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;
     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;
   };
 }