Page MenuHomePhabricator

[LSR] Fix signed overflow in GenerateCrossUseConstantOffsets.
ClosedPublic

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

Details

Summary

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

Diff Detail

Repository
rL LLVM

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
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
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.
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
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
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
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
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
4142 ↗(On Diff #192202)

Are you sure this formula is right? Alive says it doesn't work correctly for signed values: https://rise4fun.com/Alive/E3V.

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.Thu, Mar 28, 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: https://rise4fun.com/Alive/Plqc

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