[ConstantRange] Make binaryNot() more precise

[nikic]

Summary

@lebedev.ri This is what I had in mind. The code is correct and more precise without the check for wrapping sets, we just need a different testing function that can deal with wrapping ranges.

[lebedev.ri]

Guess i'll just have to do it myself then.

[lebedev.ri]

Rebase please

[nikic]

In D88178#2293723, @lebedev.ri wrote:

Guess i'll just have to do it myself then.

I feel like I'm missing context here. Did I overlook review feedback somewhere?

[lebedev.ri]

In D88178#2293838, @nikic wrote:

In D88178#2293723, @lebedev.ri wrote:

Guess i'll just have to do it myself then.

I feel like I'm missing context here. Did I overlook review feedback somewhere?

This is fixing something for which we essentially lack test coverage. Test coverage i complained we lack.

[nikic]

Looks like I reimplemented this in https://github.com/llvm/llvm-project/commit/b6088f7465a9a6691d5d237e9c0eb002734da3bf.

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
 
   // LHS range crosses zero.
   APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
   APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
   return ConstantRange(std::move(Lower), std::move(Upper));
 }
 
 ConstantRange ConstantRange::binaryNot() const {
-  if (isEmptySet())
-    return getEmpty();
-
-  if (isWrappedSet())
-    return getFull();
-
   return ConstantRange(APInt::getAllOnesValue(getBitWidth())).sub(*this);
 }
 
 ConstantRange
 ConstantRange::binaryAnd(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 

llvm/unittests/IR/ConstantRangeTest.cpp

static void TestUnsignedUnaryOpExhaustive(
   unsigned Bits = 4;
   EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
     APInt Min = APInt::getMaxValue(Bits);
     APInt Max = APInt::getMinValue(Bits);
     ForeachNumInConstantRange(CR, [&](const APInt &N) {
       if (SkipSignedIntMin && N.isMinSignedValue())
         return;
 
-      APInt AbsN = IntFn(N);
-      if (AbsN.ult(Min))
-        Min = AbsN;
-      if (AbsN.ugt(Max))
-        Max = AbsN;
+      APInt ResultN = IntFn(N);
+      if (ResultN.ult(Min))
+        Min = ResultN;
+      if (ResultN.ugt(Max))
+        Max = ResultN;
     });
 
     ConstantRange ResultCR = RangeFn(CR);
     if (Min.ugt(Max)) {
       EXPECT_TRUE(ResultCR.isEmptySet());
       return;
     }
 
     ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
     EXPECT_EQ(Exact, ResultCR);
   });
 }
 
+// Test unary operator without a sign preference. This checks that the
+// computed range is exact, rather than being exact up to the unsigned/signed
+// envelope.
+template<typename Fn1, typename Fn2>
+static void TestSignlessUnaryOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    bool Empty = true;
+    APInt Min, Max;
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      APInt ResultN = IntFn(N);
+      if (Empty) {
+        Empty = false;
+        Min = Max = ResultN;
+        return;
+      }
+
+      APInt DistFromMin = ResultN - Min;
+      if (DistFromMin.ult(Max - Min))
+        return; // Already in the range.
+
+      APInt DistFromMax = ResultN - Max;
+      if (DistFromMax.ult(-DistFromMin))
+        Max = ResultN;
+      else
+        Min = ResultN;
+    });
+
+    ConstantRange ResultCR = RangeFn(CR);
+    if (Empty) {
+      EXPECT_TRUE(ResultCR.isEmptySet());
+      return;
+    }
+
+    ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
+    EXPECT_EQ(Exact, ResultCR);
+  });
+}
+
 template<typename Fn1, typename Fn2>
 static void TestUnsignedBinOpExhaustive(
     Fn1 RangeFn, Fn2 IntFn,
     bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     APInt Min = APInt::getMaxValue(Bits);
TEST_F(ConstantRangeTest, binaryXor) {
   ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
   ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
   EXPECT_TRUE(R16_35.binaryXor(R16_35).isFullSet());
   EXPECT_TRUE(R16_35.binaryXor(R0_99).isFullSet());
   EXPECT_TRUE(R0_99.binaryXor(R16_35).isFullSet());
 }
 
 TEST_F(ConstantRangeTest, binaryNot) {
-  TestUnsignedUnaryOpExhaustive(
+  TestSignlessUnaryOpExhaustive(
       [](const ConstantRange &CR) { return CR.binaryNot(); },
       [](const APInt &N) { return ~N; });
-  TestUnsignedUnaryOpExhaustive(
+  TestSignlessUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return CR.binaryXor(
             ConstantRange(APInt::getAllOnesValue(CR.getBitWidth())));
       },
       [](const APInt &N) { return ~N; });
-  TestUnsignedUnaryOpExhaustive(
+  TestSignlessUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return ConstantRange(APInt::getAllOnesValue(CR.getBitWidth()))
             .binaryXor(CR);
       },
       [](const APInt &N) { return ~N; });
 }
 
 }  // anonymous namespace