Page MenuHomePhabricator

[ConstantRange] Shl of ConstantRanges considers full-set shifting to last bit position
ClosedPublic

Authored by kariddi on Feb 8 2019, 3:32 PM.

Details

Summary

Hello, I'm not sure here what I did is correct , but I noticed that if we do SHL of two 16-bit ranges like [0, 30000) with [1,2) we get "full-set" instead of what I would have expected [0, 60000) which is still in the 16-bit unsigned range.

In the ConstantRange SHL code I noticed that we compare if we are shifting out of the range with "uge" which considers "0x7FFFU << 1" out of range even if the result "0xFFFE" would still be in range.

Now, maybe this is done for being conservative with respect to signed ranges? Is that the reason? With this question I posted this patch with a possible fix if that is not the case.

Diff Detail

Repository
rL LLVM

Event Timeline

kariddi created this revision.Feb 8 2019, 3:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 8 2019, 3:32 PM
nlopes requested changes to this revision.Mar 3 2019, 8:13 AM

This patch is not correct for this input:
lhs = FullSet
rhs = [0, 1)

should output FullSet
but this patch gives EmptySet

Here's a Z3 model if you want to play further with this patch: https://rise4fun.com/Z3/akYEt

This revision now requires changes to proceed.Mar 3 2019, 8:13 AM
kariddi updated this revision to Diff 192784.Mar 29 2019, 1:36 AM

Thanks Nuno,

I updated my patch and tried the concept on the Z3 model.

I noticed that there might have been a bug

I think

(define-fun contains ((n Integer) (I Interval)) Bool

(ite
  (= (L I) (H I))
  (isFullSet I)
  (ite
    (not (isWrappedSet I))
    (and (bvule (L I) n) (bvult n (H I)))
    (or (bvule (L I) n) (bvult n (H I)))
  )
)

)

should have been

(define-fun contains ((n Integer) (I Interval)) Bool

(ite
  (= (L I) (H I))
  (isFullSet I)
  (ite
    (not (isWrappedSet I))
    (and (bvuge (L I) n) (bvult n (H I)))
    (or (bvuge (L I) n) (bvult n (H I)))
  )
)

)

right?

I believe the contains function I wrote is correct. It says that an integer n belongs to interval I iff n >= lower(I) and n < upper(I) is there's no wrapping.
BTW, function isWrappedSet() just changed recently, so that needs tweaking in the Z3 model I sent (https://github.com/llvm-mirror/llvm/blob/master/lib/IR/ConstantRange.cpp#L347)

Can you please send a rise4fun.com permalink with your code changes?

Sorry, you are right, I didn't notice the operands were flipped. I'm not familiar with Z3 syntax and I got confused :)

Here a link with the changes. As I said I'm not familiar with Z3 so let me know if there's something wrong

https://rise4fun.com/Z3/LoTq

Here the one with your isWrappedSet changes

https://rise4fun.com/Z3/2haZ

nlopes accepted this revision.Mar 30 2019, 3:04 AM

LGTM.
Minor: you have a typo in the comment: "return return"

This revision is now accepted and ready to land.Mar 30 2019, 3:04 AM

Please always upload patches with full context (-U99999)
You have changed code, but there were no test changes as far as i can tell?

nikic added inline comments.Mar 30 2019, 8:19 AM
lib/IR/ConstantRange.cpp
1011 ↗(On Diff #192784)

The !isWrappedSet() doesn't really make sense to me here. Other_umax (which is the inclusive unsigned maximum) for a wrapped set will always be MaxValue, so this check seems redundant.

unittests/IR/ConstantRangeTest.cpp
57 ↗(On Diff #192784)

I'd suggest moving this into the shl test, as it is only used there.

kariddi updated this revision to Diff 193827.Apr 4 2019, 7:20 PM

Hi Nikita, thanks for the review. I updated the patch based on your comment.

Let me know if that's ok for you now.

lebedev.ri requested changes to this revision.Apr 4 2019, 11:17 PM

You have changed code, but there were no test changes as far as i can tell?

Please improve test coverage.

This revision now requires changes to proceed.Apr 4 2019, 11:17 PM
kariddi updated this revision to Diff 193892.Apr 5 2019, 8:48 AM

Update coverage

lebedev.ri resigned from this revision.Apr 5 2019, 9:13 AM
This revision is now accepted and ready to land.Apr 5 2019, 9:13 AM
nikic accepted this revision.Apr 5 2019, 9:21 AM

Looks good, thanks for the update.

This revision was automatically updated to reflect the committed changes.