Page MenuHomePhabricator

[CR][WIP] Add `subWithNoWrap()` method
ClosedPublic

Authored by lebedev.ri on Wed, Nov 6, 12:29 PM.

Details

Summary

Much like D67339, adds ConstantRange handling for
when we know no-wrap behavior of the sub.

This is WIP, just barely working enough to post.

As noted in https://reviews.llvm.org/D67339#inline-629306,
there is something wrong with the exhaustive tests,
Those overflow checks in addWithNoWrap() aren't needed,
as per test coverage.

Even if i add a check `if every permutation
of ForeachNumInConstantRange()*ForeachNumInConstantRange()` says
there's overflow, then ConstantRange::*WithNoWrap() should
have returned Empty set, those overflow checks
are still not needed for add. One check is needed for sub though.

So, what is the missing check?

Diff Detail

Event Timeline

lebedev.ri created this revision.Wed, Nov 6, 12:29 PM
nikic added a comment.Wed, Nov 6, 12:48 PM

@lebedev.ri I suspect this is due to the intersection with the raw add() range. Maybe it happens that the intersection between add() and [MAX, MAX] is always empty in the case where the overflow check triggers? Can you try removing that intersection and see what happens?

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

@lebedev.ri I suspect this is due to the intersection with the raw add() range. Maybe it happens that the intersection between add() and [MAX, MAX] is always empty in the case where the overflow check triggers? Can you try removing that intersection and see what happens?

Ah, that appears to be the case:

diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index 21a93b723b7..6e0c388aaa9 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -882,8 +882,16 @@ ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
 
   if (NoWrapKind & OBO::NoSignedWrap)
     Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
-  if (NoWrapKind & OBO::NoUnsignedWrap)
+  if (NoWrapKind & OBO::NoUnsignedWrap) {
     Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
+
+    APInt LMin = getUnsignedMin(), LMax = getUnsignedMax();
+    APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax();
+    bool Overflow;
+    APInt NewMin = LMin.uadd_ov(RMin, Overflow);
+    if(Overflow)
+      assert(Result.isEmptySet());
+  }
   return Result;
 }

Didn't check signed case.

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

nikic added a comment.Wed, Nov 6, 1:14 PM

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

I guess it's okay, please add a comment to the implementation that we're relying on this lucky accident though. You might also want to piggy-back on the existing CR.uadd_sat and CR.sadd_sat implementations, now that the code is essentially the same.

lebedev.ri updated this revision to Diff 228132.Wed, Nov 6, 1:36 PM

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

I guess it's okay, please add a comment to the implementation that we're relying on this lucky accident though.

You might also want to piggy-back on the existing CR.uadd_sat and CR.sadd_sat implementations, now that the code is essentially the same.

D'oh! So *that's* why all that code looked weird to me. Now this is much better i think :)

nikic accepted this revision.Wed, Nov 6, 1:54 PM

LGTM. addWithNoWrap() has some more tests for specific inputs, but I don't think we really need them here.

llvm/lib/IR/ConstantRange.cpp
869

interception -> intersection

I'd may write "that intersection of add() with uadd_sat()/sadd_sat() results in an empty set", as it's not necessary the MAX bound.

This revision is now accepted and ready to land.Wed, Nov 6, 1:54 PM
nikic added inline comments.Wed, Nov 6, 1:56 PM
llvm/lib/IR/ConstantRange.cpp
925

As we're not using the NewMax result here (doesn't this warn?) you might want to write this as if (getUnsignedMax().ult(Other.getUnsignedMin())), as the overflow condition for usub is trivial...

lebedev.ri updated this revision to Diff 228140.Wed, Nov 6, 2:09 PM
lebedev.ri marked 2 inline comments as done.

LGTM. addWithNoWrap() has some more tests for specific inputs, but I don't think we really need them here.

Well, okay then.
Thank you for the review!

(will follow up with LVI later; not sure about SCEV)

This revision was automatically updated to reflect the committed changes.