Replace intersectWith with maximalIntersectWith. The latter guarantees that

all values belonging to the intersection will belong to the resulting range.
The former was inconsistent about that point (either way is fine, just pick
one.) This is part of PR4545.

llvm-svn: 76289

5 files changed, 29 insertions, 85 deletions

diff --git a/llvm/include/llvm/Support/ConstantRange.h b/llvm/include/llvm/Support/ConstantRange.h
index cbf3f87a354..3b72b0430fb 100644
--- a/llvm/include/llvm/Support/ConstantRange.h
+++ b/llvm/include/llvm/Support/ConstantRange.h
@@ -153,21 +153,13 @@ public:
   ConstantRange subtract(const APInt &CI) const;
 
   /// intersectWith - Return the range that results from the intersection of
-  /// this range with another range.  The resultant range is pruned as much as
-  /// possible, but there may be cases where elements are included that are in
-  /// one of the sets but not the other.  For example: [100, 8) intersect [3,
-  /// 120) yields [3, 120)
-  ///
-  ConstantRange intersectWith(const ConstantRange &CR) const;
-
-  /// maximalIntersectWith - Return the range that results from the intersection
-  /// of this range with another range.  The resultant range is guaranteed to
+  /// this range with another range.  The resultant range is guaranteed to
   /// include all elements contained in both input ranges, and to have the
   /// smallest possible set size that does so.  Because there may be two
-  /// intersections with the same set size, A.maximalIntersectWith(B) might not
-  /// be equal to B.maximalIntersectWith(A).
+  /// intersections with the same set size, A.intersectWith(B) might not
+  /// be equal to B.intersectWith(A).
   ///
-  ConstantRange maximalIntersectWith(const ConstantRange &CR) const;
+  ConstantRange intersectWith(const ConstantRange &CR) const;
 
   /// unionWith - Return the range that results from the union of this range
   /// with another range.  The resultant range is guaranteed to include the
diff --git a/llvm/lib/Analysis/LoopVR.cpp b/llvm/lib/Analysis/LoopVR.cpp
index 6854e950ef8..e4dac8f1f9b 100644
--- a/llvm/lib/Analysis/LoopVR.cpp
+++ b/llvm/lib/Analysis/LoopVR.cpp
@@ -142,14 +142,13 @@ ConstantRange LoopVR::getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE
 
     if (R.getUnsignedMin() == 0) {
       // Just because it contains zero, doesn't mean it will also contain one.
-      // Use maximalIntersectWith to get the right behaviour.
       ConstantRange NotZero(APInt(L.getBitWidth(), 1),
                             APInt::getNullValue(L.getBitWidth()));
-      R = R.maximalIntersectWith(NotZero);
+      R = R.intersectWith(NotZero);
     }
  
-    // But, the maximal intersection might still include zero. If it does, then
-    // we know it also included one.
+    // But, the intersection might still include zero. If it does, then we know
+    // it also included one.
     if (R.contains(APInt::getNullValue(L.getBitWidth())))
       Upper = L.getUnsignedMax();
     else
@@ -295,5 +294,5 @@ void LoopVR::narrow(Value *V, const ConstantRange &CR) {
   if (I == Map.end())
     Map[V] = new ConstantRange(CR);
   else
-    Map[V] = new ConstantRange(Map[V]->maximalIntersectWith(CR));
+    Map[V] = new ConstantRange(Map[V]->intersectWith(CR));
 }
diff --git a/llvm/lib/Support/ConstantRange.cpp b/llvm/lib/Support/ConstantRange.cpp
index 4cb54bde1bd..5f3d6f8db24 100644
--- a/llvm/lib/Support/ConstantRange.cpp
+++ b/llvm/lib/Support/ConstantRange.cpp
@@ -275,58 +275,20 @@ ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
 }
 
 /// intersectWith - Return the range that results from the intersection of this
-/// range with another range.
-///
+/// range with another range.  The resultant range is guaranteed to include all
+/// elements contained in both input ranges, and to have the smallest possible
+/// set size that does so.  Because there may be two intersections with the
+/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
   assert(getBitWidth() == CR.getBitWidth() && 
          "ConstantRange types don't agree!");
-  // Handle common special cases
-  if (isEmptySet() || CR.isFullSet())  
-    return *this;
-  if (isFullSet()  || CR.isEmptySet()) 
-    return CR;
-
-  if (!isWrappedSet()) {
-    if (!CR.isWrappedSet()) {
-      APInt L = APIntOps::umax(Lower, CR.Lower);
-      APInt U = APIntOps::umin(Upper, CR.Upper);
-
-      if (L.ult(U)) // If range isn't empty...
-        return ConstantRange(L, U);
-      else
-        return ConstantRange(getBitWidth(), false);// Otherwise, empty set
-    } else
-      return intersect1Wrapped(CR, *this);
-  } else {   // We know "this" is wrapped...
-    if (!CR.isWrappedSet())
-      return intersect1Wrapped(*this, CR);
-    else {
-      // Both ranges are wrapped...
-      APInt L = APIntOps::umax(Lower, CR.Lower);
-      APInt U = APIntOps::umin(Upper, CR.Upper);
-      return ConstantRange(L, U);
-    }
-  }
-  return *this;
-}
-
-/// maximalIntersectWith - Return the range that results from the intersection
-/// of this range with another range.  The resultant range is guaranteed to
-/// include all elements contained in both input ranges, and to have the
-/// smallest possible set size that does so.  Because there may be two
-/// intersections with the same set size, A.maximalIntersectWith(B) might not
-/// be equal to B.maximalIntersect(A).
-ConstantRange
-ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
-  assert(getBitWidth() == CR.getBitWidth() && 
-         "ConstantRange types don't agree!");
 
   // Handle common cases.
   if (   isEmptySet() || CR.isFullSet()) return *this;
   if (CR.isEmptySet() ||    isFullSet()) return CR;
 
   if (!isWrappedSet() && CR.isWrappedSet())
-    return CR.maximalIntersectWith(*this);
+    return CR.intersectWith(*this);
 
   if (!isWrappedSet() && !CR.isWrappedSet()) {
     if (Lower.ult(CR.Lower)) {
diff --git a/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp b/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp
index 51de4f7c050..9845f5fc80d 100644
--- a/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp
+++ b/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp
@@ -968,7 +968,7 @@ namespace {
             std::lower_bound(begin(), E, std::make_pair(Subtree, empty), swo);
 
         if (I != end() && I->first == Subtree) {
-          ConstantRange CR2 = I->second.maximalIntersectWith(CR);
+          ConstantRange CR2 = I->second.intersectWith(CR);
           assert(!CR2.isEmptySet() && !CR2.isSingleElement() &&
                  "Invalid union of ranges.");
           I->second = CR2;
@@ -1000,18 +1000,18 @@ namespace {
       ConstantRange Range(CR.getBitWidth());
 
       if (LV_s == SGT_BIT) {
-        Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+        Range = Range.intersectWith(ConstantRange::makeICmpRegion(
                     hasEQ ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SGT, CR));
       } else if (LV_s == SLT_BIT) {
-        Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+        Range = Range.intersectWith(ConstantRange::makeICmpRegion(
                     hasEQ ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SLT, CR));
       }
 
       if (LV_u == UGT_BIT) {
-        Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+        Range = Range.intersectWith(ConstantRange::makeICmpRegion(
                     hasEQ ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_UGT, CR));
       } else if (LV_u == ULT_BIT) {
-        Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+        Range = Range.intersectWith(ConstantRange::makeICmpRegion(
                     hasEQ ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT, CR));
       }
 
@@ -1083,7 +1083,7 @@ namespace {
       switch (LV) {
       default: assert(!"Impossible lattice value!");
       case NE:
-        return CR1.maximalIntersectWith(CR2).isEmptySet();
+        return CR1.intersectWith(CR2).isEmptySet();
       case ULT:
         return CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
       case ULE:
@@ -1149,7 +1149,7 @@ namespace {
         unsigned i = VN.valueNumber(*I, Subtree);
         ConstantRange CR_Kill = i ? range(i, Subtree) : range(*I);
         if (CR_Kill.isFullSet()) continue;
-        Merged = Merged.maximalIntersectWith(CR_Kill);
+        Merged = Merged.intersectWith(CR_Kill);
       }
 
       if (Merged.isFullSet() || Merged == CR_New) return;
@@ -1159,7 +1159,7 @@ namespace {
 
     void applyRange(unsigned n, const ConstantRange &CR,
                     DomTreeDFS::Node *Subtree, VRPSolver *VRP) {
-      ConstantRange Merged = CR.maximalIntersectWith(range(n, Subtree));
+      ConstantRange Merged = CR.intersectWith(range(n, Subtree));
       if (Merged.isEmptySet()) {
         markBlock(VRP);
         return;
@@ -1249,13 +1249,13 @@ namespace {
       ConstantRange CR2 = range(n2, Subtree);
 
       if (!CR1.isSingleElement()) {
-        ConstantRange NewCR1 = CR1.maximalIntersectWith(create(LV, CR2));
+        ConstantRange NewCR1 = CR1.intersectWith(create(LV, CR2));
         if (NewCR1 != CR1)
           applyRange(n1, NewCR1, Subtree, VRP);
       }
 
       if (!CR2.isSingleElement()) {
-        ConstantRange NewCR2 = CR2.maximalIntersectWith(
+        ConstantRange NewCR2 = CR2.intersectWith(
                                        create(reversePredicate(LV), CR1));
         if (NewCR2 != CR2)
           applyRange(n2, NewCR2, Subtree, VRP);
diff --git a/llvm/unittests/Support/ConstantRangeTest.cpp b/llvm/unittests/Support/ConstantRangeTest.cpp
index 3ebb92967fd..b77ac6aece0 100644
--- a/llvm/unittests/Support/ConstantRangeTest.cpp
+++ b/llvm/unittests/Support/ConstantRangeTest.cpp
@@ -203,22 +203,13 @@ TEST_F(ConstantRangeTest, IntersectWith) {
   EXPECT_TRUE(Some.intersectWith(Wrap).isEmptySet());
   EXPECT_TRUE(One.intersectWith(Wrap).isEmptySet());
   EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
-}
 
-TEST_F(ConstantRangeTest, MaximalIntersectWith) {
-  EXPECT_TRUE(Empty.maximalIntersectWith(Full).isEmptySet());
-  EXPECT_TRUE(Empty.maximalIntersectWith(Empty).isEmptySet());
-  EXPECT_TRUE(Empty.maximalIntersectWith(One).isEmptySet());
-  EXPECT_TRUE(Empty.maximalIntersectWith(Some).isEmptySet());
-  EXPECT_TRUE(Empty.maximalIntersectWith(Wrap).isEmptySet());
-  EXPECT_TRUE(Full.maximalIntersectWith(Full).isFullSet());
-  EXPECT_TRUE(Some.maximalIntersectWith(Some) == Some);
-  EXPECT_TRUE(Some.maximalIntersectWith(One) == One);
-  EXPECT_TRUE(Full.maximalIntersectWith(One) == One);
-  EXPECT_TRUE(Full.maximalIntersectWith(Some) == Some);
-  EXPECT_TRUE(Some.maximalIntersectWith(Wrap).isEmptySet());
-  EXPECT_TRUE(One.maximalIntersectWith(Wrap).isEmptySet());
-  EXPECT_EQ(One.maximalIntersectWith(Wrap), Wrap.maximalIntersectWith(One));
+  // Klee generated testcase from PR4545.
+  // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
+  // 01..4.6789ABCDEF where the dots represent values not in the intersection.
+  ConstantRange LHS(APInt(16, 4), APInt(16, 2));
+  ConstantRange RHS(APInt(16, 6), APInt(16, 5));
+  EXPECT_EQ(LHS.intersectWith(RHS), LHS);
 }
 
 TEST_F(ConstantRangeTest, UnionWith) {