Clean up ConstantRange a bit:

 - remove ashr which never worked.
 - fix lshr and shl and add tests.
 - remove dead function "intersect1Wrapped".
 - add a new sub method to subtract ranges, with test.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110861 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 127 insertions, 98 deletions

diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h
index e324261..29086b2 100644
--- a/include/llvm/Support/ConstantRange.h
+++ b/include/llvm/Support/ConstantRange.h
@@ -41,8 +41,6 @@ namespace llvm {
 ///
 class ConstantRange {
   APInt Lower, Upper;
-  static ConstantRange intersect1Wrapped(const ConstantRange &LHS,
-                                         const ConstantRange &RHS);
 
 public:
   /// Initialize a full (the default) or empty set for the specified bit width.
@@ -196,40 +194,43 @@ public:
   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
 
   /// add - Return a new range representing the possible values resulting
-  /// from an addition of a value in this range and a value in Other.
+  /// from an addition of a value in this range and a value in \p Other.
   ConstantRange add(const ConstantRange &Other) const;
 
+  /// sub - Return a new range representing the possible values resulting
+  /// from a subtraction of a value in this range and a value in \p Other.
+  ConstantRange sub(const ConstantRange &Other) const;
+
   /// multiply - Return a new range representing the possible values resulting
-  /// from a multiplication of a value in this range and a value in Other.
+  /// from a multiplication of a value in this range and a value in \p Other.
   /// TODO: This isn't fully implemented yet.
   ConstantRange multiply(const ConstantRange &Other) const;
 
   /// smax - Return a new range representing the possible values resulting
-  /// from a signed maximum of a value in this range and a value in Other.
+  /// from a signed maximum of a value in this range and a value in \p Other.
   ConstantRange smax(const ConstantRange &Other) const;
 
   /// umax - Return a new range representing the possible values resulting
-  /// from an unsigned maximum of a value in this range and a value in Other.
+  /// from an unsigned maximum of a value in this range and a value in \p Other.
   ConstantRange umax(const ConstantRange &Other) const;
 
   /// udiv - Return a new range representing the possible values resulting
-  /// from an unsigned division of a value in this range and a value in Other.
-  /// TODO: This isn't fully implemented yet.
+  /// from an unsigned division of a value in this range and a value in
+  /// \p Other.
   ConstantRange udiv(const ConstantRange &Other) const;
 
   /// shl - Return a new range representing the possible values resulting
-  /// from a left shift of a value in this range by the Amount value.
-  ConstantRange shl(const ConstantRange &Amount) const;
-
-  /// ashr - Return a new range representing the possible values resulting from
-  /// an arithmetic right shift of a value in this range by the Amount value.
-  ConstantRange ashr(const ConstantRange &Amount) const;
+  /// from a left shift of a value in this range by a value in \p Other.
+  /// TODO: This isn't fully implemented yet.
+  ConstantRange shl(const ConstantRange &Other) const;
 
-  /// shr - Return a new range representing the possible values resulting
-  /// from a logical right shift of a value in this range by the Amount value.
-  ConstantRange lshr(const ConstantRange &Amount) const;
+  /// lshr - Return a new range representing the possible values resulting
+  /// from a logical right shift of a value in this range and a value in
+  /// \p Other.
+  ConstantRange lshr(const ConstantRange &Other) const;
 
   /// inverse - Return a new range that is the logical not of the current set.
+  ///
   ConstantRange inverse() const;
   
   /// print - Print out the bounds to a stream...
diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index d4e91a9..8ef3785 100644
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -39,7 +39,7 @@ ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
 
 /// Initialize a range to hold the single specified value.
 ///
-ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {}
+ConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {}
 
 ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
   Lower(L), Upper(U) {
@@ -203,14 +203,12 @@ bool ConstantRange::contains(const APInt &V) const {
 }
 
 /// contains - Return true if the argument is a subset of this range.
-/// Two equal set contain each other. The empty set is considered to be
-/// contained by all other sets.
+/// Two equal sets contain each other. The empty set contained by all other
+/// sets.
 ///
 bool ConstantRange::contains(const ConstantRange &Other) const {
-  if (isFullSet()) return true;
-  if (Other.isFullSet()) return false;
-  if (Other.isEmptySet()) return true;
-  if (isEmptySet()) return false;
+  if (isFullSet() || Other.isEmptySet()) return true;
+  if (isEmptySet() || Other.isFullSet()) return false;
 
   if (!isWrappedSet()) {
     if (Other.isWrappedSet())
@@ -236,46 +234,6 @@ ConstantRange ConstantRange::subtract(const APInt &Val) const {
   return ConstantRange(Lower - Val, Upper - Val);
 }
 
-
-// intersect1Wrapped - This helper function is used to intersect two ranges when
-// it is known that LHS is wrapped and RHS isn't.
-//
-ConstantRange 
-ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
-                                 const ConstantRange &RHS) {
-  assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
-
-  // Check to see if we overlap on the Left side of RHS...
-  //
-  if (RHS.Lower.ult(LHS.Upper)) {
-    // We do overlap on the left side of RHS, see if we overlap on the right of
-    // RHS...
-    if (RHS.Upper.ugt(LHS.Lower)) {
-      // Ok, the result overlaps on both the left and right sides.  See if the
-      // resultant interval will be smaller if we wrap or not...
-      //
-      if (LHS.getSetSize().ult(RHS.getSetSize()))
-        return LHS;
-      else
-        return RHS;
-
-    } else {
-      // No overlap on the right, just on the left.
-      return ConstantRange(RHS.Lower, LHS.Upper);
-    }
-  } else {
-    // We don't overlap on the left side of RHS, see if we overlap on the right
-    // of RHS...
-    if (RHS.Upper.ugt(LHS.Lower)) {
-      // Simple overlap...
-      return ConstantRange(LHS.Lower, RHS.Upper);
-    } else {
-      // No overlap...
-      return ConstantRange(LHS.getBitWidth(), false);
-    }
-  }
-}
-
 /// intersectWith - 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
@@ -487,7 +445,7 @@ ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
   assert(SrcTySize > DstTySize && "Not a value truncation");
   APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
   if (isFullSet() || getSetSize().ugt(Size))
-    return ConstantRange(DstTySize);
+    return ConstantRange(DstTySize, /*isFullSet=*/true);
 
   APInt L = Lower; L.trunc(DstTySize);
   APInt U = Upper; U.trunc(DstTySize);
@@ -540,6 +498,27 @@ ConstantRange::add(const ConstantRange &Other) const {
 }
 
 ConstantRange
+ConstantRange::sub(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+  if (isFullSet() || Other.isFullSet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
+  APInt NewLower = getLower() - Other.getLower();
+  APInt NewUpper = getUpper() - Other.getUpper() + 1;
+  if (NewLower == NewUpper)
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  ConstantRange X = ConstantRange(NewLower, NewUpper);
+  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
+    // We've wrapped, therefore, full set.
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  return X;
+}
+
+ConstantRange
 ConstantRange::multiply(const ConstantRange &Other) const {
   // TODO: If either operand is a single element and the multiply is known to
   // be non-wrapping, round the result min and max value to the appropriate
@@ -617,49 +596,40 @@ ConstantRange::udiv(const ConstantRange &RHS) const {
 }
 
 ConstantRange
-ConstantRange::shl(const ConstantRange &Amount) const {
-  if (isEmptySet())
-    return *this;
+ConstantRange::shl(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 
-  APInt min = getUnsignedMin() << Amount.getUnsignedMin();
-  APInt max = getUnsignedMax() << Amount.getUnsignedMax();
+  APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
+  APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
 
   // there's no overflow!
   APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
-  if (Zeros.uge(Amount.getUnsignedMax()))
-    return ConstantRange(min, max);
+  if (Zeros.ugt(Other.getUnsignedMax()))
+    return ConstantRange(min, max + 1);
 
   // FIXME: implement the other tricky cases
-  return ConstantRange(getBitWidth());
+  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 }
 
 ConstantRange
-ConstantRange::ashr(const ConstantRange &Amount) const {
-  if (isEmptySet())
-    return *this;
-
-  APInt min = getUnsignedMax().ashr(Amount.getUnsignedMin());
-  APInt max = getUnsignedMin().ashr(Amount.getUnsignedMax());
-  return ConstantRange(min, max);
-}
-
-ConstantRange
-ConstantRange::lshr(const ConstantRange &Amount) const {
-  if (isEmptySet())
-    return *this;
+ConstantRange::lshr(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
   
-  APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin());
-  APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax());
-  return ConstantRange(min, max);
+  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
+  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
+  if (min == max + 1)
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  return ConstantRange(min, max + 1);
 }
 
 ConstantRange ConstantRange::inverse() const {
   if (isFullSet()) {
-    return ConstantRange(APInt::getNullValue(Lower.getBitWidth()),
-      APInt::getNullValue(Lower.getBitWidth()));
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
   } else if (isEmptySet()) {
-    return ConstantRange(APInt::getAllOnesValue(Lower.getBitWidth()),
-      APInt::getAllOnesValue(Lower.getBitWidth()));
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
   }
   return ConstantRange(Upper, Lower);
 }
@@ -680,5 +650,3 @@ void ConstantRange::print(raw_ostream &OS) const {
 void ConstantRange::dump() const {
   print(dbgs());
 }
-
-
diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp
index fc1f5b8..091ecd4 100644
--- a/unittests/Support/ConstantRangeTest.cpp
+++ b/unittests/Support/ConstantRangeTest.cpp
@@ -259,11 +259,31 @@ TEST_F(ConstantRangeTest, Add) {
   EXPECT_EQ(Empty.add(Wrap), Empty);
   EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
   EXPECT_EQ(Some.add(APInt(16, 4)),
-              ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
+            ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
   EXPECT_EQ(Wrap.add(APInt(16, 4)),
-              ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
+            ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
   EXPECT_EQ(One.add(APInt(16, 4)),
-              ConstantRange(APInt(16, 0xe)));
+            ConstantRange(APInt(16, 0xe)));
+}
+
+TEST_F(ConstantRangeTest, Sub) {
+  EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
+  EXPECT_EQ(Full.sub(Full), Full);
+  EXPECT_EQ(Full.sub(Empty), Empty);
+  EXPECT_EQ(Full.sub(One), Full);
+  EXPECT_EQ(Full.sub(Some), Full);
+  EXPECT_EQ(Full.sub(Wrap), Full);
+  EXPECT_EQ(Empty.sub(Empty), Empty);
+  EXPECT_EQ(Empty.sub(One), Empty);
+  EXPECT_EQ(Empty.sub(Some), Empty);
+  EXPECT_EQ(Empty.sub(Wrap), Empty);
+  EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
+  EXPECT_EQ(Some.sub(APInt(16, 4)),
+            ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
+  EXPECT_EQ(Wrap.sub(APInt(16, 4)),
+            ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
+  EXPECT_EQ(One.sub(APInt(16, 4)),
+            ConstantRange(APInt(16, 0x6)));
 }
 
 TEST_F(ConstantRangeTest, Multiply) {
@@ -351,4 +371,44 @@ TEST_F(ConstantRangeTest, UDiv) {
   EXPECT_EQ(Wrap.udiv(Wrap), Full);
 }
 
+TEST_F(ConstantRangeTest, Shl) {
+  EXPECT_EQ(Full.shl(Full), Full);
+  EXPECT_EQ(Full.shl(Empty), Empty);
+  EXPECT_EQ(Full.shl(One), Full);    // TODO: [0, (-1 << 0xa) + 1)
+  EXPECT_EQ(Full.shl(Some), Full);   // TODO: [0, (-1 << 0xa) + 1)
+  EXPECT_EQ(Full.shl(Wrap), Full);
+  EXPECT_EQ(Empty.shl(Empty), Empty);
+  EXPECT_EQ(Empty.shl(One), Empty);
+  EXPECT_EQ(Empty.shl(Some), Empty);
+  EXPECT_EQ(Empty.shl(Wrap), Empty);
+  EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
+                                        APInt(16, (0xa << 0xa) + 1)));
+  EXPECT_EQ(One.shl(Some), Full);    // TODO: [0xa << 0xa, 0)
+  EXPECT_EQ(One.shl(Wrap), Full);    // TODO: [0xa, 0xa << 14 + 1)
+  EXPECT_EQ(Some.shl(Some), Full);   // TODO: [0xa << 0xa, 0xfc01)
+  EXPECT_EQ(Some.shl(Wrap), Full);   // TODO: [0xa, 0x7ff << 0x5 + 1)
+  EXPECT_EQ(Wrap.shl(Wrap), Full);
+}
+
+TEST_F(ConstantRangeTest, Lshr) {
+  EXPECT_EQ(Full.lshr(Full), Full);
+  EXPECT_EQ(Full.lshr(Empty), Empty);
+  EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
+                                          APInt(16, (0xffff >> 0xa) + 1)));
+  EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
+                                           APInt(16, (0xffff >> 0xa) + 1)));
+  EXPECT_EQ(Full.lshr(Wrap), Full);
+  EXPECT_EQ(Empty.lshr(Empty), Empty);
+  EXPECT_EQ(Empty.lshr(One), Empty);
+  EXPECT_EQ(Empty.lshr(Some), Empty);
+  EXPECT_EQ(Empty.lshr(Wrap), Empty);
+  EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
+  EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
+  EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+  EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
+                                           APInt(16, (0xaaa >> 0xa) + 1)));
+  EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
+  EXPECT_EQ(Wrap.lshr(Wrap), Full);
+}
+
 }  // anonymous namespace