[SCEV] Make isImpliedCond smarter.

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

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 8381b8670846883df594a4dbdd14ade8d22e8ab2..4360414e85624ade2c1588f097ae7cc3febbfeae 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -71,8 +71,8 @@ namespace llvm {
     unsigned short SubclassData;
 
   private:
-    SCEV(const SCEV &) LLVM_DELETED_FUNCTION;
-    void operator=(const SCEV &) LLVM_DELETED_FUNCTION;
+    SCEV(const SCEV &) = delete;
+    void operator=(const SCEV &) = delete;
 
   public:
     /// NoWrapFlags are bitfield indices into SubclassData.
@@ -87,7 +87,8 @@ namespace llvm {
     /// unsigned-max(bitwidth).  This means that the recurrence will never reach
     /// its start value if the step is non-zero.  Computing the same value on
     /// each iteration is not considered wrapping, and recurrences with step = 0
-    /// are trivially <NW>.
+    /// are trivially <NW>.  <NW> is independent of the sign of step and the
+    /// value the add recurrence starts with.
     ///
     /// Note that NUW and NSW are also valid properties of a recurrence, and
     /// either implies NW. For convenience, NW will be set for a recurrence
@@ -231,10 +232,6 @@ namespace llvm {
     ///
     LoopInfo *LI;
 
-    /// The DataLayout information for the target we are targeting.
-    ///
-    const DataLayout *DL;
-
     /// TLI - The target library information for the target we are targeting.
     ///
     TargetLibraryInfo *TLI;
@@ -387,32 +384,31 @@ namespace llvm {
     /// computeBlockDisposition - Compute a BlockDisposition value.
     BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
 
-    /// UnsignedRanges - Memoized results from getUnsignedRange
+    /// UnsignedRanges - Memoized results from getRange
     DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
 
-    /// SignedRanges - Memoized results from getSignedRange
+    /// SignedRanges - Memoized results from getRange
     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;
-    }
+    /// RangeSignHint - Used to parameterize getRange
+    enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
+
+    /// setRange - Set the memoized range for the given SCEV.
+    const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
+                                  const ConstantRange &CR) {
+      DenseMap<const SCEV *, ConstantRange> &Cache =
+          Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
 
-    /// 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));
+          Cache.insert(std::make_pair(S, CR));
       if (!Pair.second)
         Pair.first->second = CR;
       return Pair.first->second;
     }
 
+    /// getRange - Determine the range for a particular SCEV.
+    ConstantRange getRange(const SCEV *S, RangeSignHint Hint);
+
     /// createSCEV - We know that there is no SCEV for the specified value.
     /// Analyze the expression.
     const SCEV *createSCEV(Value *V);
@@ -539,6 +535,15 @@ namespace llvm {
                                      const SCEV *FoundLHS,
                                      const SCEV *FoundRHS);
 
+    /// isImpliedCondOperandsViaRanges - Test whether the condition described by
+    /// Pred, LHS, and RHS is true whenever the condition described by Pred,
+    /// FoundLHS, and FoundRHS is true.  Utility function used by
+    /// isImpliedCondOperands.
+    bool isImpliedCondOperandsViaRanges(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
     /// constant number of times, and the PHI node is just a recurrence
@@ -560,6 +565,15 @@ namespace llvm {
     /// pointer.
     bool checkValidity(const SCEV *S) const;
 
+    // Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be equal
+    // to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is equivalent to
+    // proving no signed (resp. unsigned) wrap in {`Start`,+,`Step`} if
+    // `ExtendOpTy` is `SCEVSignExtendExpr` (resp. `SCEVZeroExtendExpr`).
+    //
+    template<typename ExtendOpTy>
+    bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
+                                   const Loop *L);
+
   public:
     static char ID; // Pass identification, replacement for typeid
     ScalarEvolution();
@@ -833,11 +847,15 @@ namespace llvm {
 
     /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
     ///
-    ConstantRange getUnsignedRange(const SCEV *S);
+    ConstantRange getUnsignedRange(const SCEV *S) {
+      return getRange(S, HINT_RANGE_UNSIGNED);
+    }
 
     /// getSignedRange - Determine the signed range for a particular SCEV.
     ///
-    ConstantRange getSignedRange(const SCEV *S);
+    ConstantRange getSignedRange(const SCEV *S) {
+      return getRange(S, HINT_RANGE_SIGNED);
+    }
 
     /// isKnownNegative - Test if the given expression is known to be negative.
     ///