Implement udiv for ConstantRanges.

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

2 files changed, 35 insertions, 17 deletions

diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index 7fe1568..04a1b68 100644
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -592,10 +592,32 @@ ConstantRange::umax(const ConstantRange &Other) const {
 }
 
 ConstantRange
-ConstantRange::udiv(const ConstantRange &Other) const {
-  // TODO: Implement udiv.
-  return ConstantRange(getBitWidth(),
-                       !(isEmptySet() || Other.isEmptySet()));
+ConstantRange::udiv(const ConstantRange &RHS) const {
+  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+  if (RHS.isFullSet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
+
+  APInt RHS_umin = RHS.getUnsignedMin();
+  if (RHS_umin == 0) {
+    // We want the lowest value in RHS excluding zero. Usually that would be 1
+    // except for a range in the form of [X, 1) in which case it would be X.
+    if (RHS.getUpper() == 1)
+      RHS_umin = RHS.getLower();
+    else
+      RHS_umin = APInt(getBitWidth(), 1);
+  }
+
+  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
+
+  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
+  // this could occur.
+  if (Lower == Upper)
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+  return ConstantRange(Lower, Upper);
 }
 
 /// print - Print out the bounds to a stream...
diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp
index d11d776..891c209 100644
--- a/unittests/Support/ConstantRangeTest.cpp
+++ b/unittests/Support/ConstantRangeTest.cpp
@@ -319,24 +319,20 @@ TEST_F(ConstantRangeTest, SMax) {
 TEST_F(ConstantRangeTest, UDiv) {
   EXPECT_EQ(Full.udiv(Full), Full);
   EXPECT_EQ(Full.udiv(Empty), Empty);
-  EXPECT_EQ(Full.udiv(One), Full);
-  EXPECT_EQ(Full.udiv(Some), Full);
+  EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
+                                          APInt(16, 0xffff / 0xa + 1)));
+  EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
+                                           APInt(16, 0xffff / 0xa + 1)));
   EXPECT_EQ(Full.udiv(Wrap), Full);
   EXPECT_EQ(Empty.udiv(Empty), Empty);
   EXPECT_EQ(Empty.udiv(One), Empty);
   EXPECT_EQ(Empty.udiv(Some), Empty);
   EXPECT_EQ(Empty.udiv(Wrap), Empty);
-  // TODO: ConstantRange is currently over-conservative here.
-  EXPECT_EQ(One.udiv(One), Full);
-  // TODO: ConstantRange is currently over-conservative here.
-  EXPECT_EQ(One.udiv(Some), Full);
-  // TODO: ConstantRange is currently over-conservative here.
-  EXPECT_EQ(One.udiv(Wrap), Full);
-  // TODO: ConstantRange is currently over-conservative here.
-  EXPECT_EQ(Some.udiv(Some), Full);
-  // TODO: ConstantRange is currently over-conservative here.
-  EXPECT_EQ(Some.udiv(Wrap), Full);
-  // TODO: ConstantRange is currently over-conservative here.
+  EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
+  EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
+  EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+  EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
+  EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
   EXPECT_EQ(Wrap.udiv(Wrap), Full);
 }