[ConstantRange] Add sdiv() support

The implementation is conceptually simple: We separate the LHS and
RHS into positive and negative components and then also compute the
positive and negative components of the result, taking into account
that e.g. only pos/pos and neg/neg will give a positive result.

However, there's one significant complication: SignedMin / -1 is UB
for sdiv, and we can't just ignore it, because the APInt result of
SignedMin would break the sign segregation. Instead we drop SignedMin
or -1 from the corresponding ranges, taking into account some edge
cases with wrapped ranges.

Because of the sign segregation, the implementation ends up being
nearly fully precise even for wrapped ranges (the remaining
imprecision is due to ranges that are both signed and unsigned
wrapping and are divided by a trivial divisor like 1). This means
that the testing cannot just check the signed envelope as we
usually do. Instead we collect all possible results in a bitvector
and construct a better sign wrapped range (than the full envelope).

Differential Revision: https://reviews.llvm.org/D61238

llvm-svn: 362430

1 files changed, 58 insertions, 0 deletions

diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp
index eeebe2e73ae..c0166b21039 100644
--- a/llvm/unittests/IR/ConstantRangeTest.cpp
+++ b/llvm/unittests/IR/ConstantRangeTest.cpp
@@ -6,6 +6,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
@@ -844,6 +845,63 @@ TEST_F(ConstantRangeTest, UDiv) {
             ConstantRange(APInt(16, 0), APInt(16, 99)));
 }
 
+TEST_F(ConstantRangeTest, SDiv) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
+                                       const ConstantRange &CR2) {
+    // Collect possible results in a bit vector. We store the signed value plus
+    // a bias to make it unsigned.
+    int Bias = 1 << (Bits - 1);
+    BitVector Results(1 << Bits);
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        // Division by zero is UB.
+        if (N2 == 0)
+          return;
+
+        // SignedMin / -1 is UB.
+        if (N1.isMinSignedValue() && N2.isAllOnesValue())
+          return;
+
+        APInt N = N1.sdiv(N2);
+        Results.set(N.getSExtValue() + Bias);
+      });
+    });
+
+    ConstantRange CR = CR1.sdiv(CR2);
+    if (Results.none()) {
+      EXPECT_TRUE(CR.isEmptySet());
+      return;
+    }
+
+    // If there is a non-full signed envelope, that should be the result.
+    APInt SMin(Bits, Results.find_first() - Bias);
+    APInt SMax(Bits, Results.find_last() - Bias);
+    ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
+    if (!Envelope.isFullSet()) {
+      EXPECT_EQ(Envelope, CR);
+      return;
+    }
+
+    // If the signed envelope is a full set, try to find a smaller sign wrapped
+    // set that is separated in negative and positive components (or one which
+    // can also additionally contain zero).
+    int LastNeg = Results.find_last_in(0, Bias) - Bias;
+    int LastPos = Results.find_next(Bias) - Bias;
+    if (Results[Bias]) {
+      if (LastNeg == -1)
+        ++LastNeg;
+      else if (LastPos == 1)
+        --LastPos;
+    }
+
+    APInt WMax(Bits, LastNeg);
+    APInt WMin(Bits, LastPos);
+    ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
+    EXPECT_EQ(Wrapped, CR);
+  });
+}
+
 TEST_F(ConstantRangeTest, URem) {
   EXPECT_EQ(Full.urem(Empty), Empty);
   EXPECT_EQ(Empty.urem(Full), Empty);