This is an archive of the discontinued LLVM Phabricator instance.

[IndVarSimplify] Widen loop compares for unsigned IVs that have a uniform step of one.
ClosedPublic

Authored by mcrosier on Sep 29 2014, 9:48 AM.

Details

Summary

This patch extends r217953 to handle unsigned comparison, which requires special handling due to unsigned wrapping.

I believe this is safe, but kicking off full correctness runs now..

Chad

Diff Detail

Event Timeline

mcrosier updated this revision to Diff 14172.Sep 29 2014, 9:48 AM
mcrosier retitled this revision from to [IndVarSimplify] Widen loop compares for unsigned IVs that have a uniform step of one..
mcrosier updated this object.
mcrosier edited the test plan for this revision. (Show Details)
mcrosier added reviewers: atrick, jmolloy.
mcrosier added subscribers: Unknown Object (MLST), njw45.
atrick edited edge metadata.Sep 29 2014, 10:20 AM

That looks safe. Why do you need to check unit stride in the unsigned case but not in the signed case? Can you think of an example where this would break?

apazos added a subscriber: apazos.Sep 29 2014, 3:57 PM

Hi Andy,

I think we are concerned about changing program behavior that somehow might depend/work fine with the wrapping.

Signed arithmetic operations in C standard do not wrap while unsigned arithmetic operations wrap.

So if you have unsigned char a,b and try to add them:
a=255; b = 1;
a+b = 0; // (produces 0 because 256-256=0 and the higher bit is ignored, overflow occurred)

while if you have char a, b when you add them:
a= 127 (0x7F); b= 1;
a+b = -128; // (produces -128 because 128-256=-128, higher bit is not ignored and flips the sign, overflow occurred)

If we promote an unsigned IV to 64-bit, we believe it has to be done so that it does not change the program behavior.

Example:
for (; i < max_range_for_the_type; i+=d)

use(i)

In this example what are the safe conditions to promote i to a larger size so that we do not change the program behavior?
Increment/Decrement i by 1 is the only case since it is guaranteed to wrap only when it hits max_range_for_the_type,
while other increment/decrement amounts might skip over the limit and wrap.

So we decided to use SCEV analysis step info to allow widening the unsigned IV only when we are sure we do not change the program behavior.

What do you think?

FWIW, my commit that reverted unsigned comparison widening (r217962) was speculative and just so happened to appease the buildbots. I suspect the real issue was addressed in r218539.

At the LLVM IR level, there is no assumption about signed or unsigned arithmetic wrapping. Either SCEV must prove a value does not wrap based on loop conditions, or it must be inferred from the add operation's nsw or nuw attributes. By the time WidenLoopCompare has been called, SCEV has proven that the IV recurrence does not wrap in the signed or unsigned sense (depending on IsSigned).

Maybe it helps to think about it this way: You could have safely implemented compare widening by first transforming the IR as follows:

Loop:
%i0 = phi i8 [%i1, %Loop, ...]
%i1 = add nuw i8 %i0, 2
%exti = zext i8 %i to i64
cmp i64 %exti, zext(k)

Then indvars would come along and widen the IV:

Loop:
%i0 = phi i64 [%i1, %Loop, ...]
%i1 = add nuw i64 %i0, 2
cmp i64 %i1, zext(k)

But you're widening the compare after WidenIV has already proven that this zero extend would be unnecessary:
%exti = zext i8 %i to i64

So you just need to extend the constant.

mcrosier accepted this revision.Sep 29 2014, 8:28 PM
mcrosier added a reviewer: mcrosier.

Thanks for the clarification, Andy.

Committed r218659.

This revision is now accepted and ready to land.Sep 29 2014, 8:28 PM
mcrosier closed this revision.Sep 29 2014, 8:28 PM