This is an archive of the discontinued LLVM Phabricator instance.

[ConstantRange] add helper function addWithNoWrap
ClosedPublic

Authored by shchenz on Sep 8 2019, 8:00 PM.

Details

Summary

Currently there is only an add function for constant range without considering wrap flag. It may produce a conservative range.
For example, currently, full_set +nsw [1,3) will get full_set. But right range should be [SINT_MIN + 1, SINT_MIN)
Add a helper function to consider wrap flag, so we can get a more accurate range.

This is splitted from https://reviews.llvm.org/D64869.

Diff Detail

Repository
rL LLVM

Event Timeline

shchenz created this revision.Sep 8 2019, 8:00 PM
shchenz edited the summary of this revision. (Show Details)Sep 8 2019, 8:41 PM

It would be really good to add exaustive tests for this, see TestUnsignedBinOpExhaustive / TestSignedBinOpExhaustive / TestNoWrapRegionExhaustive / TestOverflowExhaustive.

nikic added a comment.Sep 9 2019, 1:41 PM

The implementation looks correct to me. As @lebedev.ri mentioned we usually add exhaustive tests for ConstantRange methods nowadays. I'm not totally sure what should be tested here... I guess we should test a) conservative correctness (no wrong results produced) and b) tight bounds if the input sets are non-wrapping/non-sign-wrapping.

llvm/include/llvm/IR/ConstantRange.h
338 ↗(On Diff #219286)

My preference would be to add this as an optional argument to add() instead. In the future, we'll likely want to accept NoWrapKind on more methods, and also thread it through binaryOp().

llvm/lib/IR/ConstantRange.cpp
833 ↗(On Diff #219286)

I think we should also accept OBO::NoSignedWrap|OBO::NoUnsignedWrap here. This would allow directly passing through nowrap flags in LVI.

Possibly this can be implemented by computing both the nuw and the nsw result and intersecting both?

844 ↗(On Diff #219286)

As this is a method on ConstantRange you can just write return getEmpty(); here.

The implementation looks correct to me. As @lebedev.ri mentioned we usually add exhaustive tests for ConstantRange methods nowadays.

I'm not totally sure what should be tested here... I guess we should test a) conservative correctness (no wrong results produced) and b) tight bounds if the input sets are non-wrapping/non-sign-wrapping.

That is what i was suggesting, yes; thought quick glance through code suggests that only a. can be enforced for the diff as present.

lebedev.ri requested changes to this revision.Sep 10 2019, 1:59 PM

(marking as reviewed)

This revision now requires changes to proceed.Sep 10 2019, 1:59 PM
shchenz updated this revision to Diff 220286.EditedSep 16 2019, 1:27 AM
shchenz marked 3 inline comments as done.

address @nikic @lebedev.ri comments

Sorry for the delay. Ready for further review.

llvm/include/llvm/IR/ConstantRange.h
338 ↗(On Diff #219286)

Can I do it later in another seperated patch? I want to make this patch as small as possible. Combining with current add may introduce potential issue?

llvm/lib/IR/ConstantRange.cpp
833 ↗(On Diff #219286)

I think there is no necessary for us to support OBO::NoSignedWrap|OBO::NoUnsignedWrap . We have different signed and unsigned ranges for one SCEV and we can only query one type range(Unsigned range or Signed range) for one time. Also we set nsw only based on signed range and nuw only based on unsigned range. Intersecting signed and unsigned range may get wrong result for SCEV's range if we use this intersecting range for signed/unsigned range. For example, if one ADDSCEV's signed range is [-10, 5), and its unsigned range is [10, 20), in StrengthenNoWrapFlags, we will set this SCEV with nsw and nuw. So we get Intersecting range is empty-set, if we use this range as signed range or unsigned range, we get empty-set, this should be wrong?

nikic added inline comments.Sep 21 2019, 2:18 AM
llvm/include/llvm/IR/ConstantRange.h
338 ↗(On Diff #219286)

Sure, we can do that separately.

llvm/lib/IR/ConstantRange.cpp
833 ↗(On Diff #219286)

I think there is no necessary for us to support OBO::NoSignedWrap|OBO::NoUnsignedWrap . We have different signed and unsigned ranges for one SCEV and we can only query one type range(Unsigned range or Signed range) for one time. Also we set nsw only based on signed range and nuw only based on unsigned range.

The addWithNoWrap() functionality is also useful outside of SCEV. LVI, which is used by CVP, does not distinguish between signed and unsigned ranges. It would simply pass through the nowrap flags on the (IR-level) add operation. It would be odd if analysis quality would decrease if an add had both nuw/nsw, rather than only one of them.

Intersecting signed and unsigned range may get wrong result for SCEV's range if we use this intersecting range for signed/unsigned range. For example, if one ADDSCEV's signed range is [-10, 5), and its unsigned range is [10, 20), in StrengthenNoWrapFlags, we will set this SCEV with nsw and nuw. So we get Intersecting range is empty-set, if we use this range as signed range or unsigned range, we get empty-set, this should be wrong?

Getting an empty set is correct in this case. The unsigned and signed SCEV ranges are *both* (conseratively) correct and the real range will be a subset of their intersection.

In D64869, you're using the addNoWrap() functionality by only setting nuw if both the add is nuw and the preferred range type is unsigned (and same for signed). I think this makes sense as a conservative choice that avoids regressions, but generally these are really orthogonal: The nowrap flags and the preferred signedness are independent concepts and may be mixed.

I think the ideal design here would actually be to expose both as separate arguments, nowrap using OBO flags and signedness using ConstantRange::PreferredRangeType:

ConstantRange addWithNoWrap(
    const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType);

In this case the implementation could, at a high level, look something like this:

// Normal wrapping addition as baseline.
ConstantRange Res = add(Other);
if (NoWrapKind & NUW) {
    // Intersect in NUW addition based on getUnsignedMin/Max().
    Res = Res.intersect(addNUW(Other), RangeType);
}
if (NoWrapKind == NSW) {
    // Intersect in NSW addition based on getSignedMin/Max().
    Res = Res.intersect(addNSW(Other), RangeType);
}
return Res;

I think this is both flexible in terms of how it may be used, and intuitive in how it works/behaves.

To take a specific example, consider an add nuw nsw i4 [0, 3], [5, 7]:

add: [5, 10]
addNUW: [5, 10]
addNSW: [5, 7]
intersection: [5, 7] (independent of sign preference in this case)

If this was a SCEV with an unsigned preference, then taking just the nuw flag would have given us a worse result than considering both. Even for the unsigned range, the nsw flag still provides useful information.

nikic added inline comments.Sep 21 2019, 4:00 AM
llvm/unittests/IR/ConstantRangeTest.cpp
701 ↗(On Diff #220286)

The logic here seems unnecessary complicated to me. Couldn't we do something like this?

bool IsOverflow = false;
APInt N = IntFn(IsOverflow, N1, N2);
if (!IsOverflow) {
    if (N.sle(Min))
        Min = N;
    if (N.sge(Max))
        Max = N;
}

here, and use just sadd_ov() (without sadd_sat) in IntFn? The empty set case can be checked as if (Min.sgt(Max)) EXPECT_TRUE(CR.isEmptySet()); I believe.

shchenz updated this revision to Diff 221693.Sep 25 2019, 2:39 AM

address @nikic comments

shchenz marked 3 inline comments as done.Sep 25 2019, 2:40 AM

Hi @nikic, thanks for your comments. Could you help to have another look?

llvm/unittests/IR/ConstantRangeTest.cpp
701 ↗(On Diff #220286)

Good idea.

nikic added a comment.Sep 29 2019, 6:39 AM

Two more notes, otherwise this looks good to me :) @lebedev.ri Anything to add?

llvm/lib/IR/ConstantRange.cpp
834 ↗(On Diff #221693)

You can remove the check for isWrappedSet / isSignWrappedSet now. We're going to intersect with the add() result anyway, so this is just going to intersect with itself. Even if one of the ranges is wrapped, we might still get a better result here if the other isn't. E.g. something like [10, MAX] + Wrapped will still get you [10, MAX] as the result here, which is likely better than what the wrapped calculation will provide.

llvm/unittests/IR/ConstantRangeTest.cpp
712 ↗(On Diff #221693)

Rather than skipping these entirely, you can still check that the result is correct, even if not minimal. Something like this:

ConstantRange CR = RangeFn(CR1, CR2);
//... Loop
if (!IsOverflow) {
  // ... Collect Min/Max
  EXPECT_TRUE(CR.contains(N));
}

if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) {
    // ... Do the exact check here
}
shchenz marked 2 inline comments as done.Sep 29 2019, 7:03 PM
shchenz added inline comments.
llvm/lib/IR/ConstantRange.cpp
834 ↗(On Diff #221693)

I am a little confuse about removing the check for isWrappedSet / isSignWrappedSet.
Assuming we have two unsigned ranges [10, 20), [200, 100), if we remove the check for wrap, we get [10, 20) as result.

But if we do the math, [10, 20) +nuw [200, 100) results in two disjoint ranges [10, 119) \/ [210, 0).
My previous is a little like getPreferredRange, we choose one range from above disjoint ranges based on preferred type.

If we use [10, 20), will it be too aggresive, since we use a smaller range?
If we use add result for wrap range, we get [210, 119) as result which is father range of "[10, 119) \/ [210, 0)", it is conservative but right?

nikic added inline comments.Sep 30 2019, 1:09 AM
llvm/lib/IR/ConstantRange.cpp
834 ↗(On Diff #221693)

Assuming we have two unsigned ranges [10, 20), [200, 100), if we remove the check for wrap, we get [10, 20) as result.

In this case, you should get [10, 0) as the result. The wrapped range will be treated as a full range by getUnsignedMin() and getUnsignedMax(), so this is the same as doing [10, 20) + full.

Additionally, as you say, you will get [210, 119) from the normal add. These are then intersected and you will get back either [10, 0) (if there is an unsigned preference) or [210, 119) (if there is a smallest range preference). For SCEV, getting [10, 0) back will be more useful than getting the wrapped range back.

shchenz updated this revision to Diff 222375.Sep 30 2019, 2:03 AM
shchenz marked 2 inline comments as done.

address @nikic comments

In this case, you should get [10, 0) as the result. The wrapped range will be treated as a full range by getUnsignedMin() and getUnsignedMax(), so this is the same as doing [10, 20) + full.

Ah, right, it should get [10, 0). my bad...

nikic accepted this revision.Sep 30 2019, 2:46 AM

LGTM

llvm/unittests/IR/ConstantRangeTest.cpp
767 ↗(On Diff #222375)

This should also check for EXPECT_TRUE(CR.contains(N)), if both overflow flags are false. Because N must be the same for both operations, it might make sense to not have two separate branches, that is:

bool IsSignedOverflow, IsUnsignedOverflow;
APInt N = IntFnSigned(IsSignedOverflow, N1, N2);
(void) IntFnUnsigned(IsSignedOverflow, N1, N2);
if (!IsSignedOverflow && !IsUnsignedOverflow) {
  // Compute SMin, SMax, UMin, UMax
  EXPECT_TRUE(CR.contains(N));
}
shchenz updated this revision to Diff 222393.Sep 30 2019, 5:23 AM

Thanks very much for your helpful review @nikic

This revision was not accepted when it landed; it landed in state Needs Review.Sep 30 2019, 5:58 AM
This revision was automatically updated to reflect the committed changes.
lebedev.ri added inline comments.Nov 6 2019, 11:45 AM
llvm/trunk/lib/IR/ConstantRange.cpp
834–856

@nikic @shchenz
So i'm trying to look into sub variant, and i'm missing a subtlety here.

In addWithNoSignedWrap() why those overflow checks are needed?
All tests pass without them.

In addWithNoUnsignedWrap() why is that overflow check needed?
All tests pass without it (with it replaced with uadd_sat)

nikic added inline comments.Nov 6 2019, 11:58 AM
llvm/trunk/lib/IR/ConstantRange.cpp
834–856

[i8 200, i8 200] add nuw [i8 200, i8 200] should result in empty-set rather than [i8 255, i8 255], this is what the overflow check is for.

Not sure why there is not test failure, I'd expect one of the EXPECT_TRUE(CR.isEmptySet()) checks to fail.