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

[mcrosier]

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

[atrick]

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]

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?

[mcrosier]

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.

[atrick]

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]

Thanks for the clarification, Andy.

Committed r218659.

lib/Transforms/Scalar/IndVarSimplify.cpp

   if (!Cmp)
     return false;
 
-  // Must be a signed compare.
-  if (!CmpInst::isSigned(Cmp->getPredicate()))
+  // Sign of IV user and compare must match.
+  if (IsSigned != CmpInst::isSigned(Cmp->getPredicate()))
     return false;
 
-  // Must be a signed IV user.
-  if (!IsSigned)
-    return false;
+  // IV of unsigned compare must be uniform step by one.
+  if (!IsSigned) {
+    const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowDef);
+    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(NarrowExpr);
+    if (!AR)
+      return false;
+    const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
+    if (!Step || !Step->isOne())
+      return false;
+  }
 
   Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
   unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());

test/Transforms/IndVarSimplify/widen-loop-comp.ll

 for.end:
   ret i32 0
 }
+
+; CHECK-LABEL: @test5
+; CHECK: zext i32 %b
+; CHECK: for.cond:
+; CHECK: phi i64
+; CHECK: icmp ule i64
+
+define i32 @test5(i32* %a, i32 %b) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp ule i32 %i.0, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32* %a, i64 %idxprom
+  %0 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret i32 %sum.0
+}