Page MenuHomePhabricator

[LSR] Fix Shadow IV in case of integer overflow
ClosedPublic

Authored by mkazantsev on Aug 28 2017, 4:20 AM.

Details

Summary

When LSR processes code like

int accumulator = 0;
for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++)
    accumulator += i * j;
  use((double) sum);
}

It may decide to replace integer accumulator with a double Shadow IV to get rid
of casts. The problem with that is that the accumulator's value may overflow.
Starting from this moment, the behavior of integer and double accumulators
will differ.

This patch strenghtens up the conditions of Shadow IV mechanism applicability.
We only allow it for IVs that are proved to be AddRecs with nw flag.

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev created this revision.Aug 28 2017, 4:20 AM
reames requested changes to this revision.Aug 28 2017, 9:31 AM
reames added inline comments.
lib/Transforms/Scalar/LoopStrengthReduce.cpp
2034 ↗(On Diff #112878)

I don't think this is the correct check. Specifically, this check allows overflow as long as we can guarantee that the value never reaches it's starting value. I think you actually want hasNoUnsignedWrap() && hasNoSignedWrap()

Consider:
unsigned i = 1
do {

i += INT_MAX; 
d += i;

} while ( (signed int)i > 0)

test/Transforms/LoopStrengthReduce/dont_turn_int_overflow_to_fp.ll
10 ↗(On Diff #112878)

Can't you greatly reduce this example?

Doesn't a simple sum of squares in the 32 bit domain trigger this?

This revision now requires changes to proceed.Aug 28 2017, 9:31 AM
evstupac edited edge metadata.Aug 28 2017, 9:31 AM

Hi Max,

I believe, C and C++ standards say that signed integers overflow has undefined behavior.
So in your example we can safely change program behavior in case of overflow.

"If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined. [...]"
Unsigned case is more complicated.

Thanks,
Evgeny

Hi Max,

I believe, C and C++ standards say that signed integers overflow has undefined behavior.
So in your example we can safely change program behavior in case of overflow.

"If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined. [...]"
Unsigned case is more complicated.

Thanks,
Evgeny

Evgeny, what the C and C++ standards say is irrelevant to the semantics of LLVM IR and do not come into the discussion at all. It does not effect the legality of the transform in any way.

In this particular example, Clang would mark the add as being nsw when generating the IR. That encodes the semantics you're concerned about.

Further comments.

lib/Transforms/Scalar/LoopStrengthReduce.cpp
2034 ↗(On Diff #112878)

Giving a bit more detail, signed wrap is definitely a problem which needs prevented because double looses precision for maximum bitwidth and produces a different answer for smaller bit widths. consider signed_max<src_type> + 1. This should equal signed_min<src_type>, but may not with double arithmetic.

Unsigned wrap is less clear to me. I don't have a counter example yet, but I'm suspicious that there is one. If we allowed negative steps, we'd clearly have the corresponding underflow problem to the signed wrap one just mentioned, but with the restriction to positive steps, I'm not finding one.

Actually, here's an obvious one.
for (unsigned int16_t = UINT16_MAX; i != UINT_MAX-1; i++) { (double)i };

UINT16_MAX + 1 should be 0. Since that fits within the signed domain of a double, we'd get (int)UINT16_MAX)+1.

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll
1 ↗(On Diff #112878)

Please convert this test to use filecheck (the automatic check lines should be fine), check that in, and then rebase please.

66 ↗(On Diff #112878)

Is this even valid IR? I don't see a value being assigned here? Unless this is just wrapping really weirdly?

mkazantsev added inline comments.Aug 28 2017, 8:39 PM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
2034 ↗(On Diff #112878)

Thanks for pointing it out, it should indeed be nuw/nsw wraps.

As for unsigned, the situation is basically the same as with signed even without negative steps. Double is able to store values that are greater than UINT_MAX, and on conversion from double to int they will be rounded to nearest (UINT_MAX, apparently) while in int they will be overflown values that are less than it.

mkazantsev added inline comments.Aug 28 2017, 9:44 PM
test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll
66 ↗(On Diff #112878)

Guess that the unnamed variables are called %1, %2 etc.

mkazantsev added inline comments.Aug 28 2017, 10:23 PM
test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll
66 ↗(On Diff #112878)

Refactored the test as https://reviews.llvm.org/rL311980

mkazantsev edited edge metadata.
mkazantsev marked 4 inline comments as done.

Rebased, moved tests to existing test file, fixed the wrap check,

reames accepted this revision.Aug 29 2017, 12:17 AM

LGTM

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll
141 ↗(On Diff #113029)

this -> thus

188 ↗(On Diff #113029)

this -> thus

This revision is now accepted and ready to land.Aug 29 2017, 12:17 AM
This revision was automatically updated to reflect the committed changes.