This is an archive of the discontinued LLVM Phabricator instance.

[ConstantRange] Add overflow check helpers
ClosedPublic

Authored by nikic on Mar 10 2019, 1:41 PM.

Details

Summary

Add functions to ConstantRange that determine whether the unsigned/signed addition/subtraction of two ConstantRanges may/always/never overflows. This will allow checking overflow conditions based on known constant ranges in addition to known bits (with D59071 in mind).

I'm implementing these methods on ConstantRange to allow them to be unit tested independently of any ValueTracking machinery.

The OverflowResult enum is redeclared on ConstantRange, because I wanted to avoid a dependency in either direction between ValueTracking.h and ConstantRange.h.

Diff Detail

Repository
rL LLVM

Event Timeline

nikic created this revision.Mar 10 2019, 1:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2019, 1:41 PM

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

nikic added a comment.Mar 10 2019, 2:00 PM

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

Maybe I can just include some exhaustive tests? I'm thinking on 4-bit numbers we have 16^2 possible ranges with less than 16^4 values contained in them in total. That's few enough to try all of them.

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

Maybe I can just include some exhaustive tests? I'm thinking on 4-bit numbers we have 16^2 possible ranges with less than 16^4 values contained in them in total. That's few enough to try all of them.

Sure, for one-time thing brute-force verification could work (how do you plan to produce the 'truth' you will be verifying against?)

Also, see @nlopes's ConstantRange section of https://llvm.org/devmtg/2013-11/slides/Lopes-SMT.pdf.
This is rather not suited for day-to-day use, but i'm not sure there are friendlier wrappers for such a rare use-case..

nikic added a comment.Mar 10 2019, 2:39 PM

@lebedev.ri I've implemented the following code for exhaustive checking on 4-bit numbers: https://gist.github.com/nikic/3d37a4742a8685c5dd101524f928fe58 The source of truth are APInt uadd_ov and friends.

Is this something I should include in the patch (possibly reduced to 3-bit testing) or is this okay as a one-off test?

@lebedev.ri I've implemented the following code for exhaustive checking on 4-bit numbers: https://gist.github.com/nikic/3d37a4742a8685c5dd101524f928fe58 The source of truth are APInt uadd_ov and friends.

Nice, not manual hardcoding, but cross-checking.

Is this something I should include in the patch (possibly reduced to 3-bit testing) or is this okay as a one-off test?

What's the runtime of the current 4-bit case?

What's the runtime of the current 4-bit case?

The run-times for the 4-bit checks I get on a debug build:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (609 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (589 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (726 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (735 ms)

For 3-bit checks:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (11 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (10 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (13 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (14 ms)

What's the runtime of the current 4-bit case?

The run-times for the 4-bit checks I get on a debug build:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (609 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (589 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (726 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (735 ms)

I was expecting something like 10 sec total, that looks like nothing to me.
Please add those tests into appropriate place :)
It's not SMT, but better than nothing i suppose.

nikic updated this revision to Diff 190048.Mar 11 2019, 1:13 AM

Add exhaustive tests for overflow checks.

Looks good, some nits.

llvm/unittests/IR/ConstantRangeTest.cpp
1315–1316 ↗(On Diff #190048)

On the first look this is confusing.
Maybe add Set/Range prefix, so it is clearer that it is over the whole set, not just some one point.

1317–1329 ↗(On Diff #190048)

Hm, so this is iterating so that N1 is every point in CR1 and N2 is every point in CR2.
Took me a moment to get that.
Can this perhaps be rewritten with for-loop somehow, more explicitly?

for(APInt N1 = CR1.getLower(), APInt N1Max = CR1.getUpper(); N1 != N1Max; N1++) {
  for(APInt N2 = CR2.getLower(), APInt N2Max = CR2.getUpper(); N2 != N2Max; N2++) {
    assert(CR1.contains(N1));
    assert(CR2.contains(N2));

    if (OverflowFn(N1, N2))
      HasOverflow = true;
    else
       HasNoOverflow = true;
  }
}
nikic updated this revision to Diff 190139.Mar 11 2019, 12:44 PM

Rename to RangeHasOverflow/RangeHasNoOverflow, add comment.

nikic marked 2 inline comments as done.Mar 11 2019, 12:47 PM
nikic added inline comments.
llvm/unittests/IR/ConstantRangeTest.cpp
1317–1329 ↗(On Diff #190048)

A simple for loop will not work for the case of a full range (as N1 != N1Max will fail immediately). That's why I'm using the current code based on the range size. I've added a comment to that effect.

lebedev.ri accepted this revision.Mar 11 2019, 12:51 PM

Okay, thanks, looks sane to me.
You may want to wait for @spatel / @craig.topper comments though.

This revision is now accepted and ready to land.Mar 11 2019, 12:51 PM
nikic added a comment.Mar 14 2019, 3:45 PM

@spatel Anything to add here?

spatel accepted this revision.Mar 14 2019, 3:53 PM

LGTM

llvm/include/llvm/IR/ConstantRange.h
331 ↗(On Diff #190139)

other -> Other ?

(hoping we can standardize to camelCase variables, but we're not there yet?)

This revision was automatically updated to reflect the committed changes.