Trailing whitespace.

[oota-llvm.git] / include / llvm / Analysis / ScalarEvolution.h

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 837ed40f50554553c82bb12b1a6aa3b399807da5..1fa94e9c311cb0df2a4e0a49384782929d7103fa 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -44,12 +44,17 @@ 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 FoldingSetNode {
+    friend struct FoldingSetTrait<SCEV>;
+
     /// FastID - A reference to an Interned FoldingSetNodeID for this node.
     /// The ScalarEvolution's BumpPtrAllocator holds the data.
     FoldingSetNodeIDRef FastID;
@@ -73,9 +78,6 @@ namespace llvm {
 
     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;
@@ -125,6 +127,21 @@ namespace llvm {
     void dump() const;
   };
 
+  // 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 raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
     S.print(OS);
     return OS;
@@ -175,6 +192,7 @@ namespace llvm {
 
     friend class SCEVCallbackVH;
     friend class SCEVExpander;
+    friend class SCEVUnknown;
 
     /// F - The function we are analyzing.
     ///
@@ -196,9 +214,14 @@ 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<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 includes an exact count and a maximum count.
@@ -263,7 +286,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);
 
@@ -343,10 +366,6 @@ 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
@@ -354,10 +373,11 @@ namespace llvm {
     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,
@@ -530,10 +550,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.
@@ -650,6 +666,15 @@ namespace llvm {
     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;
@@ -658,6 +683,11 @@ namespace llvm {
   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;
   };
 }