[ConstantRange] Add `mulWithNoWrap()` method

[lebedev.ri]

Summary

I'm not fully happy about this.

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

However mulWithNoWrap does pass conservatively correctness test.
Though it is less constrained than the brute-force approach.
I don't think it needs a different testing approach though?

Here we don't get EXPECT_EQ(CR.isEmptySet(), AllOverflow);
postcondition for free in any of the cases, so it needs to be
manually enforced. I wonder, shouldn't we be using
unsigned*?MayOverflow() == OverflowResult::AlwaysOverflowsHigh*
for that, everywhere? Should be more readable than manual inlined checks..

[lebedev.ri]

Bump

[nikic]

llvm/lib/IR/ConstantRange.cpp

1027

Why do these fetch the unsigned min/max for the signed multiplication case?

1046

Why do we need to specially handle the nuw+nsw combination here?

[lebedev.ri]

Fix OBO::NoSignedWrap modelling - what we are trying to check there is
whether multiplication of smallest values of two ranges do/don't multiply.
So we need to actually see what values are the smallest in this range.
And by smallest we mean closest to 0.

llvm/lib/IR/ConstantRange.cpp

1027

Right, this makes little sense.
I just ad-hoc-ked it because that is what worked, and it was likely wrong from precision standpoint.
I think this is more obvious now? (Did i horrendously over-engineer this and overlooking existing infra?)

1046

Even after fixing OBO::NoSignedWrap check this remains.
Here in OBO::NoUnsignedWrap we did check that
getUnsignedMin() * Other.getUnsignedMin()
does not exhibit *unsigned* overflow,
but we did not do any such check in OBO::NoSignedWrap.

There, even if UnsignedMin happens to be one of the values closest to 0,
since we check that all values overflow, unless said range only contains
a single UnsignedMin, we wouldn't discard such range as always-overflowing.

So i think this is correct.
At least until precision tests say otherwise.

[lebedev.ri]

typos

[lebedev.ri]

Let me know if my explanation makes sense.

llvm/lib/IR/ConstantRange.cpp

1046

Example:
Bits 4 CR1 [2,0) CR2 [4,0) CR [-8,0)

This doesn't always overflow in unsigned domain - i4 2 * i4 4 == i4 -8 (signed overflow)
This doesn't always overflow in signed domain - both ranges contain -1 value - i4 -1 * i4 -1 == i4 1 (unsigned overflow)

But there is no such value pair that exhibits both no signed overflow and no unsigned overflow at the same time.

Alive proof: https://rise4fun.com/Alive/1aK

[nikic]

@lebedev.ri Haven't looked too closely at the implementation yet, but my general feeling is that trying this hard to be precise about the empty set case is a bad tradeoff in terms of utility vs compilation time. Note in particular that a) we don't actually make use of empty sets in CVP (I believe they map to overdefined rather than undefined) and b) all the remaining calculations are only precise for non-wrapping sets (and the tests only check that).

I think it would make more sense to move the AllOverflow check in the to !isWrappedSet branches in the tests, which should make it possible to use a more naive, but for practical purposes probably equally good, implementation.

[lebedev.ri]

Streamline getClosestToZero(), reshuffle mulWithNoWrap() to do cheap checks first.

[lebedev.ri]

In D70043#1756686, @nikic wrote:

@lebedev.ri Haven't looked too closely at the implementation yet, but
my general feeling is that trying this hard to be precise about the
empty set case is a bad tradeoff in terms of utility vs compilation time.

Note in particular that a) we don't actually make use of empty sets in CVP
(I believe they map to overdefined rather than undefined)
and b) all the remaining calculations are only precise for non-wrapping sets
(and the tests only check that).

Aha, indeed. https://godbolt.org/z/N3KggA Interesting.

To not lose all that "mul is guaranteed to wrap" logic,
should i move it into signedMulMayOverflow() instead of just completely dropping?

I think it would make more sense to move the AllOverflow check in the
to !isWrappedSet branches in the tests, which should make it possible
to use a more naive, but for practical purposes probably equally good, implementation.

[lebedev.ri]

Bump. Posted https://lists.llvm.org/pipermail/llvm-dev/2019-December/137327.html

In D70043#1756686, @nikic wrote:

@lebedev.ri Haven't looked too closely at the implementation yet, but my general feeling is that trying this hard to be precise about the empty set case is a bad tradeoff in terms of utility vs compilation time. Note in particular that a) we don't actually make use of empty sets in CVP (I believe they map to overdefined rather than undefined) and b) all the remaining calculations are only precise for non-wrapping sets (and the tests only check that).

I think it would make more sense to move the AllOverflow check in the to !isWrappedSet branches in the tests, which should make it possible to use a more naive, but for practical purposes probably equally good, implementation.

Can anyone else familiar with LVI (and other ConstantRange users) chime in
and comment whether we indeed should not be doing such modelling?

[lebedev.ri]

Split ConstantRange::getClosestToZero() into it's own review.
Added ConstantRange::shlWithNoWrap() support in a follow-up patch.

[lebedev.ri]

Rebased, NFC.

[nikic]

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect, just that this testing function is a bit overly aggressive in CorrectnessOnly mode. It expects the result to be a superset of the minimal unsigned bounding range. We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Looking a bit into what causes the failures for mulWithNoWrap when testing not only correctness for the unsigned case. I think there are two main causes:

• Something like [0, 1] * [-8, -5] produces [-8, 0], while the testing code expects [0, -5]. This actual result is consistent with the "smallest range" preferred range mode, so this is just a testing deficiency.
• Something like [0, 2] * [-8, -5] produces full-set, while the testing code expects [0, -5]. The reason here is that the result can be in the ranges [0, 0], [-8, -5] or [2 * -8, 2 * -5], where the last range is unsigned (and signed) wrapping, so the result could actually be the same as for the previous case. However, we don't recognize that the 2 * [-8, -5] case is fully excluded.

So I guess it would be pretty hard to make this work non-approximately...

[lebedev.ri]

In D70043#1771089, @nikic wrote:

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect, just that this testing function is a bit overly aggressive in CorrectnessOnly mode. It expects the result to be a superset of the minimal unsigned bounding range.

Sure, of course, otherwise the EXPECT_TRUE(CR.contains(N)); would complain.

We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Note that we already do that check, otherwise we wouldn't know that the result is at least conservatively correct.

Looking a bit into what causes the failures for mulWithNoWrap when testing not only correctness for the unsigned case. I think there are two main causes:

• Something like [0, 1] * [-8, -5] produces [-8, 0], while the testing code expects [0, -5]. This actual result is consistent with the "smallest range" preferred range mode, so this is just a testing deficiency.
• Something like [0, 2] * [-8, -5] produces full-set, while the testing code expects [0, -5]. The reason here is that the result can be in the ranges [0, 0], [-8, -5] or [2 * -8, 2 * -5], where the last range is unsigned (and signed) wrapping, so the result could actually be the same as for the previous case. However, we don't recognize that the 2 * [-8, -5] case is fully excluded.

So I guess it would be pretty hard to make this work non-approximately...

[lebedev.ri]

In D70043#1771734, @lebedev.ri wrote:

In D70043#1771089, @nikic wrote:

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect,
just that this testing function is a bit overly aggressive in CorrectnessOnly mode.
It expects the result to be a superset of the minimal unsigned bounding range.

Sure, of course, otherwise the EXPECT_TRUE(CR.contains(N)); would complain.

We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Note that we already do that check, otherwise we wouldn't know that the result is at least conservatively correct.

...

So I guess it would be pretty hard to make this work non-approximately...

As i have previously said, what's *really* missing is QoI testing:
just measure how constrained is the ConstantRange-returned result,
as compared to the ideal result, with <1 being not conservatively correct,
=1 ideal, and >1 non-optimal. That can totally replace
the existing EXPECT_EQ(Exact, CR); check,
and be that much more informative.

@reames @nikic But in the end, any suggestions on how to get *these* patches moving?
The replies to the maillist post are non-conclusive.
Anyone else have an opinion?

[nikic]

But in the end, any suggestions on how to get *these* patches moving?

My opinion here hasn't really changed ... I still think that if we want to handle wrapping ranges more accurately, we need to do so in a more principled fashion that does not special case empty sets only. Specifically I would expect this to entail:

• Changing the getClosestToZero() helper to instead return two ranges, the positive and the negative one.
• Changing the signed part of the multiply() code to use those split ranges, instead of simple smin/smax.
• Possibly better, make the implementation of mulWithNoWrap() proper perform operations in the double bitwidth and then intersect with the legal part of the range. That way the empty set result should come about naturally as well.

It may well make sense to do this, but if we want to land something here more quickly, I would recommend:

• Remove the EXPECT_EQ(CR.isEmptySet(), AllOverflow) assertions and the code necessary to satisfy them. We already check that empty sets are correctly computed for non-wrapping sets in a separate assertion.
• Add some hand-written test coverage for mulWithNoWrap(). As the exhaustive tests are correctness-only, we should also check that we actually compute some reasonable ranges for a couple of inputs.

llvm/include/llvm/IR/ConstantRange.h

ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
                               PreferredRangeType RangeType = Smallest) const;
 
   /// Return a new range representing the possible values resulting
   /// from a multiplication of a value in this range and a value in \p Other,
   /// treating both this and \p Other as unsigned ranges.
   ConstantRange multiply(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
+  /// from an multiplication with wrap type \p NoWrapKind of a value in this
+  /// range and a value in \p Other.
+  /// If the result range is disjoint, the preferred range is determined by the
+  /// \p PreferredRangeType.
+  ConstantRange mulWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
+                              PreferredRangeType RangeType = Smallest) const;
+
+  /// Return a new range representing the possible values resulting
   /// from a signed maximum of a value in this range and a value in \p Other.
   ConstantRange smax(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from an unsigned maximum of a value in this range and a value in \p Other.
   ConstantRange umax(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting

llvm/lib/IR/ConstantRange.cpp

auto L = {this_min * Other_min, this_min * Other_max,
             this_max * Other_min, this_max * Other_max};
   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
   ConstantRange SR = Result_sext.truncate(getBitWidth());
 
   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
 }
 
+ConstantRange ConstantRange::mulWithNoWrap(const ConstantRange &Other,
+                                           unsigned NoWrapKind,
+                                           PreferredRangeType RangeType) const {
+  // Calculate the range for "X * Y" which is guaranteed not to wrap(overflow).
+  // (X is from this, and Y is from Other)
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+  if (isFullSet() && Other.isFullSet())
+    return getFull();
+
+  using OBO = OverflowingBinaryOperator;
+  ConstantRange Result = multiply(Other);
+
+  if (NoWrapKind & OBO::NoUnsignedWrap) {
+    bool Overflow;
+
+    (void)getUnsignedMin().umul_ov(Other.getUnsignedMin(), Overflow);
+    if (Overflow)
+      return getEmpty(); // Always overflows.
+
+    if (NoWrapKind & OBO::NoSignedWrap) {
+      (void)getUnsignedMin().smul_ov(Other.getUnsignedMin(), Overflow);
+      if (Overflow)
+        return getEmpty(); // Always overflows.
+    }
+
+    Result = Result.intersectWith(umul_sat(Other), RangeType);
+  }
+
+  if (NoWrapKind & OBO::NoSignedWrap) {
+    bool AllOverflow = true;
+    SmallVector<APInt, 2> ClosestToZero = getClosestToZero();
+    SmallVector<APInt, 2> OtherClosestToZero = Other.getClosestToZero();
+    for (const APInt &L : ClosestToZero) {
+      for (const APInt &R : OtherClosestToZero) {
+        bool Overflow;
+        (void)L.smul_ov(R, Overflow);
+        AllOverflow &= Overflow;
+        if (!AllOverflow)
+          break;
+      }
+      if (!AllOverflow)
+        break;
+    }
+    if (AllOverflow)
+      return getEmpty(); // Always overflows.
+
+    Result = Result.intersectWith(smul_sat(Other), RangeType);
+  }
+
+  return Result;
+}
+
 ConstantRange
 ConstantRange::smax(const ConstantRange &Other) const {
   // X smax Y is: range(smax(X_smin, Y_smin),
   //                    smax(X_smax, Y_smax))
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;

llvm/unittests/IR/ConstantRangeTest.cpp

EXPECT_EQ(Some.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
   EXPECT_EQ(Wrap.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
   EXPECT_EQ(One.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe)));
 }
 
 template <typename Fn1, typename Fn2>
-static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
+static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn,
+                                              bool CorrectnessOnly = false) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     ConstantRange CR = RangeFn(CR1, CR2);
     APInt Min = APInt::getSignedMaxValue(Bits);
     APInt Max = APInt::getSignedMinValue(Bits);
     bool AllOverflow = true;
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
         bool IsOverflow = false;
         APInt N = IntFn(IsOverflow, N1, N2);
         if (!IsOverflow) {
           AllOverflow = false;
           if (N.slt(Min))
             Min = N;
           if (N.sgt(Max))
             Max = N;
           EXPECT_TRUE(CR.contains(N));
         }
       });
     });
 
     EXPECT_EQ(CR.isEmptySet(), AllOverflow);
 
-    if (!CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
+    if (!CorrectnessOnly && !CR1.isSignWrappedSet() &&
+        !CR2.isSignWrappedSet()) {
       if (Min.sgt(Max)) {
         EXPECT_TRUE(CR.isEmptySet());
         return;
       }
 
       ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
       EXPECT_EQ(Exact, CR);
     }
   });
 }
 
 template <typename Fn1, typename Fn2>
-static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
+static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn,
+                                                bool CorrectnessOnly = false) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     ConstantRange CR = RangeFn(CR1, CR2);
     APInt Min = APInt::getMaxValue(Bits);
     APInt Max = APInt::getMinValue(Bits);
     bool AllOverflow = true;
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
         bool IsOverflow = false;
         APInt N = IntFn(IsOverflow, N1, N2);
         if (!IsOverflow) {
           AllOverflow = false;
           if (N.ult(Min))
             Min = N;
           if (N.ugt(Max))
             Max = N;
           EXPECT_TRUE(CR.contains(N));
         }
       });
     });
 
     EXPECT_EQ(CR.isEmptySet(), AllOverflow);
 
-    if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) {
+    if (!CorrectnessOnly && !CR1.isWrappedSet() && !CR2.isWrappedSet()) {
       if (Min.ugt(Max)) {
         EXPECT_TRUE(CR.isEmptySet());
         return;
       }
 
       ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
       EXPECT_EQ(Exact, CR);
     }
   });
 }
 
 template <typename Fn1, typename Fn2, typename Fn3>
-static void TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn,
-                                                      Fn2 IntFnSigned,
-                                                      Fn3 IntFnUnsigned) {
+static void
+TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFnSigned,
+                                          Fn3 IntFnUnsigned,
+                                          bool CorrectnessOnly = false) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(
       Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
         ConstantRange CR = RangeFn(CR1, CR2);
         APInt UMin = APInt::getMaxValue(Bits);
         APInt UMax = APInt::getMinValue(Bits);
         APInt SMin = APInt::getSignedMaxValue(Bits);
         APInt SMax = APInt::getSignedMinValue(Bits);
EnumerateTwoConstantRanges(
                 UMax = N;
               EXPECT_TRUE(CR.contains(N));
             }
           });
         });
 
         EXPECT_EQ(CR.isEmptySet(), AllOverflow);
 
-        if (!CR1.isWrappedSet() && !CR2.isWrappedSet() &&
+        if (!CorrectnessOnly && !CR1.isWrappedSet() && !CR2.isWrappedSet() &&
             !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
           if (UMin.ugt(UMax) || SMin.sgt(SMax)) {
             EXPECT_TRUE(CR.isEmptySet());
             return;
           }
 
           ConstantRange Exact =
               ConstantRange::getNonEmpty(SMin, SMax + 1)
EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
             ConstantRange(APInt(8, 250), APInt(8, 253)));
 
   // TODO: This should be return [-2, 0]
   EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
               ConstantRange(APInt(8, 0), APInt(8, 2))),
             ConstantRange(APInt(8, -2), APInt(8, 1)));
 }
 
+TEST_F(ConstantRangeTest, MulWithNoWrap) {
+  typedef OverflowingBinaryOperator OBO;
+
+  TestAddWithNoSignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.mulWithNoWrap(CR2, OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.smul_ov(N2, IsOverflow);
+      },
+      /*CorrectnessOnly=*/true);
+
+  TestAddWithNoUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.mulWithNoWrap(CR2, OBO::NoUnsignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.umul_ov(N2, IsOverflow);
+      },
+      /*CorrectnessOnly=*/true);
+
+  TestAddWithNoSignedUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.mulWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.smul_ov(N2, IsOverflow);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.umul_ov(N2, IsOverflow);
+      },
+      /*CorrectnessOnly=*/true);
+}
+
 TEST_F(ConstantRangeTest, UMax) {
   EXPECT_EQ(Full.umax(Full), Full);
   EXPECT_EQ(Full.umax(Empty), Empty);
   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
   EXPECT_EQ(Full.umax(Wrap), Full);
   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
   EXPECT_EQ(Empty.umax(Empty), Empty);
   EXPECT_EQ(Empty.umax(Some), Empty);