Page MenuHomePhabricator

[LSR] Fix signed overflow in GenerateCrossUseConstantOffsets.

Authored by fhahn on Mar 11 2019, 9:37 AM.



For the attached test case, unchecked addition of immediate starts and
ends overflows, as they can be arbitrary i64 constants.

Diff Detail


Event Timeline

fhahn created this revision.Mar 11 2019, 9:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 11 2019, 9:37 AM
fhahn updated this revision to Diff 190143.Mar 11 2019, 1:02 PM

Use wrapping arithmetic

Another case similar to D59211

Ping. This applies the same solution as D59211 to a different case.

efriedma added inline comments.Mar 22 2019, 4:10 PM
4152 ↗(On Diff #190143)

This code is trying to compute (x+y)/2. Mathematically, this can't overflow, so this shouldn't require a bitwidth to produce a meaningful result.

fhahn marked an inline comment as done.Mar 25 2019, 5:04 AM
fhahn added inline comments.
4152 ↗(On Diff #190143)

Unless I am missing something, the cast addresses a potential overflow for the x + y part of the expression. Running the attached test with opt+ubsan crashes here.

efriedma added inline comments.Mar 25 2019, 12:13 PM
4152 ↗(On Diff #190143)

Sorry, I guess I wasn't clear.

By "mathematically, this can't overflow", I meant that if x and y are in the range [INT_MIN, INT_MAX], (x+y)/2 is also in the range [INT_MIN, INT_MAX]. If you try to compute the result by just writing "(x+y)/2" in C, sure, it'll overflow, but you can rewrite the formula some other way. (Not sure what the most efficient way to write that in C is, off the top of my head.)

fhahn updated this revision to Diff 192202.Mar 25 2019, 2:22 PM

Thanks Eli, I did not realize that there are quite efficient ways to compute the
expressions other than splitting it up and dealing with the even/uneven cases
with modulo.

I did some digging online and updated the patch with an approach that should be
quite efficient.

efriedma added inline comments.Mar 25 2019, 2:44 PM
4142 ↗(On Diff #192202)

Are you sure this formula is right? Alive says it doesn't work correctly for signed values:

fhahn planned changes to this revision.Mar 26 2019, 6:26 AM

Modeling round-to-zero behavior correctly for all inputs is a bit tricky. I'll revisit it when I have more time

fhahn updated this revision to Diff 192696.Mar 28 2019, 12:07 PM

Fix calculation: use signed right shift to divide by 2 with round to -inf and
add 1 for negative results where one value is odd and the other even to get
round to 0 behavior. Proof:

This revision is now accepted and ready to land.Mar 28 2019, 12:16 PM
This revision was automatically updated to reflect the committed changes.