Page MenuHomePhabricator

[IR] Fix bug in `ConstantRange::intersectWith`
AbandonedPublic

Authored by sanjoy on Oct 12 2015, 3:02 PM.

Details

Reviewers
nlewycky
Summary
NOTE: this is still failing tests, so it isn't yet ready to go in and is a WIP. The failing tests will have to be audited manually before checking this in.
NOTE: all of the fixes in ConstantRangeTest.cpp were bugs to begin with, AFAICT.

This "fixes" a bug in intersectWith by rewriting it. The idea is that
we can extend the bitwidth of a constant range by a bit and use that to
simplify the logic around checking for wrapped ranges.

Roughly, if this is our number line with a wrapped range

|---)----[-------|

we map the wrapped range to

|--------[-------|---)------------|  .. (A)

and if this is the number line with an not-wrapped range

|---[----)-------|

we map it to

|---[----)-------|----------------|  .. (B)

or

|----------------|---[----)-------|  .. (C)

When intersecting a wrapped range with an unwrapped one (the "hard"
case), we intersect (A) with (B) and (A) with (C); and pick the larger
of the two.

We can do the same thing for unions.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 37186.Oct 12 2015, 3:02 PM
sanjoy retitled this revision from to [IR] Fix bug in `ConstantRange::intersectWith`.
sanjoy updated this object.
sanjoy added a reviewer: nlewycky.
sanjoy added a subscriber: llvm-commits.

Note: the only reason I introduced UnwrappedLimit instead of using APInt is that I wanted to avoid an allocation if we were working with a word-wide range. If you think that that's an acceptable overhead, I can switch this to use APInt instead.

nlewycky added inline comments.Oct 12 2015, 5:06 PM
lib/IR/ConstantRange.cpp
318–319

clang-format?

338–339

Please comment what this produces. A reader may wonder why HighBitPref is ignored on the wrapped set case; why doesn't it control whether the 'gap' is in the high or low half?

unittests/IR/ConstantRangeTest.cpp
285

Remove this newline?

sanjoy abandoned this revision.Oct 12 2015, 6:22 PM

This change is unnecessary and buggy. I was working under the assumption that everything in X.intersectWith(Y) has to belong to both X and Y; whereas X.intersectWith(Y) is allowed to return a superset of the actual mathematical intersection of X and Y. This change is buggy today because it will sometimes return a proper subset of the mathematical intersection of X and Y.