This is an archive of the discontinued LLVM Phabricator instance.

[ConstantRange] Add sdiv() support
ClosedPublic

Authored by nikic on Apr 28 2019, 3:41 AM.

Details

Summary

Add the last missing binary op to ConstantRange: sdiv. This was a real struggle, both in terms of implementation and testing.

The implementation is conceptually simple: We separate the LHS and RHS into positive and negative components and then also compute the positive and negative components of the result, taking into account that e.g. only pos/pos and neg/neg will give a positive result.

However, there's one complication: SignedMin / -1 is UB for sdiv, and we can't just ignore it, because the APInt result of SignedMin would break the sign segregation. Instead we drop SignedMin or -1 from the corresponding ranges, taking into account some edge cases with wrapped ranges.

Because of the sign segregation, the implementation ends up being nearly fully precise even for wrapped ranges (the remaining imprecision is due to ranges that are both signed and unsigned wrapping and are divided by a trivial divisor like 1). This means that the testing cannot just check the signed envelope as we usually do. Instead we collect all possible results in a bitvector and construct a better sign wrapped range (than the full envelope).

Diff Detail

Event Timeline

nikic created this revision.Apr 28 2019, 3:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 28 2019, 3:41 AM
fhahn added a subscriber: fhahn.Apr 28 2019, 12:47 PM
nikic added a comment.May 11 2019, 1:38 AM

Add the last missing binary op to ConstantRange: sdiv.

Turned out to be not quite true: We're also missing xor. But I don't think that one is really worthwhile to deal with in terms of ranges...

jdoerfert added inline comments.
llvm/lib/IR/ConstantRange.cpp
987

I'm confused, isn't -3 / -3 = 1 ?

999

Is it worth the hassle? Ignoring the special case and taking the APInt behavior seems like a much easier solution. Do we have evidence we don't want that? (I did not try to understand this special case yet!)

nikic marked 2 inline comments as done.Jun 2 2019, 11:57 AM
nikic added inline comments.
llvm/lib/IR/ConstantRange.cpp
987

Right, this should read neg / neg = pos.

999

Not handling this case would muddy the waters with regards to signs -- a negative number divided by a negative number should have a guaranteed positive result, and I would consider it important that we realize this.

The second motivation (and the reason why I'm going out of the way here to also treat wrapped ranges correctly), is that it allows us to exhaustively test the sdiv implementation for both conservative correctness and optimality, and thus give us full confidence in the implementation. Otherwise we would have to settle for conservative correctness only.

jdoerfert added inline comments.Jun 2 2019, 12:55 PM
llvm/lib/IR/ConstantRange.cpp
999

Agreed.

I think I understand the code below but it is hard to follow the logic and map it back to the comment above. Could you explain what is going on so it is easier to read, e.g.,

// Filter the singleton set [-1,0) as it does not make a defined contribution to the result.
if (!NegR.Lower.isAllOnesValue()) {
nikic updated this revision to Diff 202624.Jun 2 2019, 2:51 PM

Update comments so they are closer to the relevant branches in the implementation.

jdoerfert accepted this revision.Jun 2 2019, 3:11 PM

Thanks for improving the comments. LGTM now.

This revision is now accepted and ready to land.Jun 2 2019, 3:11 PM
This revision was automatically updated to reflect the committed changes.