[LSR] Fix Shadow IV in case of integer overflow

[mkazantsev]

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.

[reames]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

2034

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

Can't you greatly reduce this example?

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

[evstupac]

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

[reames]

In D37209#854175, @evstupac wrote:

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.

[reames]

Further comments.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

2034

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

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

66

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

[mkazantsev]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

2034

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]

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll

66

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

[mkazantsev]

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll

66

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

[mkazantsev]

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

[reames]

LGTM

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll

122

this -> thus

169

this -> thus

lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (IVUsers::const_iterator UI = IU.begin(), E = IU.end();
     // If target does not support DestTy natively then do not apply
     // this transformation.
     if (!TTI.isTypeLegal(DestTy)) continue;
 
     PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0));
     if (!PH) continue;
     if (PH->getNumIncomingValues() != 2) continue;
 
+    // If the calculation in integers overflows, the result in FP type will
+    // differ. So we only can do this transformation if we are guaranteed to not
+    // deal with overflowing values.
+    const SCEVAddRecExpr *PS = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PH));
+    if (!PS || !PS->hasNoSelfWrap()) continue;
+
     Type *SrcTy = PH->getType();
     int Mantissa = DestTy->getFPMantissaWidth();
     if (Mantissa == -1) continue;
     if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa)
       continue;
 
     unsigned Entry, Latch;
     if (PH->getIncomingBlock(0) == L->getLoopPreheader()) {

test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll

 ; RUN: opt < %s -loop-reduce -S -mtriple=x86_64-unknown-unknown | grep "phi double" | count 1
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 
 define void @foobar(i32 %n) nounwind {
 entry:
   icmp eq i32 %n, 0   ; <i1>:0 [#uses=2]
   br i1 %0, label %return, label %bb.nph
 
 bb.nph:   ; preds = %entry
   %umax = select i1 %0, i32 1, i32 %n    ; <i32> [#uses=1]
   br label %bb
 
 bb:   ; preds = %bb, %bb.nph
   %i.03 = phi i32 [ 0, %bb.nph ], [ %indvar.next, %bb ]    ; <i32> [#uses=3]
   tail call void @bar( i32 %i.03 ) nounwind
   uitofp i32 %i.03 to double    ; <double>:1 [#uses=1]
   tail call void @foo( double %1 ) nounwind
-  %indvar.next = add i32 %i.03, 1   ; <i32> [#uses=2]
+  %indvar.next = add nuw i32 %i.03, 1    ; <i32> [#uses=2]
   %exitcond = icmp eq i32 %indvar.next, %umax    ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:   ; preds = %bb, %entry
   ret void
 }
 
 ; Unable to eliminate cast because the mantissa bits for double are not enough
 ; to hold all of i64 IV bits.
 define void @foobar2(i64 %n) nounwind {
 entry:
   icmp eq i64 %n, 0   ; <i1>:0 [#uses=2]
   br i1 %0, label %return, label %bb.nph
 
 bb.nph:   ; preds = %entry
   %umax = select i1 %0, i64 1, i64 %n    ; <i64> [#uses=1]
   br label %bb
 
 bb:   ; preds = %bb, %bb.nph
   %i.03 = phi i64 [ 0, %bb.nph ], [ %indvar.next, %bb ]    ; <i64> [#uses=3]
   trunc i64 %i.03 to i32    ; <i32>:1 [#uses=1]
   tail call void @bar( i32 %1 ) nounwind
   uitofp i64 %i.03 to double    ; <double>:2 [#uses=1]
   tail call void @foo( double %2 ) nounwind
-  %indvar.next = add i64 %i.03, 1   ; <i64> [#uses=2]
+  %indvar.next = add nuw i64 %i.03, 1    ; <i64> [#uses=2]
   %exitcond = icmp eq i64 %indvar.next, %umax    ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:   ; preds = %bb, %entry
   ret void
 }
 
 ; Unable to eliminate cast due to potentional overflow.
 define void @foobar3() nounwind {
 entry:
   tail call i32 (...) @nn( ) nounwind    ; <i32>:0 [#uses=1]
   icmp eq i32 %0, 0   ; <i1>:1 [#uses=1]
   br i1 %1, label %return, label %bb
 
 bb:   ; preds = %bb, %entry
   %i.03 = phi i32 [ 0, %entry ], [ %3, %bb ]    ; <i32> [#uses=3]
   tail call void @bar( i32 %i.03 ) nounwind
   uitofp i32 %i.03 to double    ; <double>:2 [#uses=1]
   tail call void @foo( double %2 ) nounwind
   add i32 %i.03, 1    ; <i32>:3 [#uses=2]
   tail call i32 (...) @nn( ) nounwind    ; <i32>:4 [#uses=1]
   icmp ugt i32 %4, %3   ; <i1>:5 [#uses=1]
   br i1 %5, label %bb, label %return
 
 return:   ; preds = %bb, %entry
   ret void
 }
 
return:   ; preds = %bb, %entry
   ret void
 }
 
 declare void @bar(i32)
 
 declare void @foo(double)
 
 declare i32 @nn(...)
 

test/Transforms/LoopStrengthReduce/dont_turn_int_overflow_to_fp.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; This test checks that we don't try to replace integer calculations with
+; double calculations if we cannot prove that integer calculations will not
+; overflow.
+
+define i32 @test_01() {
+; CHECK-LABEL:  test_01(
+; CHECK:          outer_header:
+; CHECK-NOT:      phi double
+; CHECK-NOT:      phi float
+entry:
+  br label %outer_header
+
+outer_header:                                           ; preds = %outer_backedge, %entry
+  %local_3_ = phi i32 [ -4, %entry ], [ %tmp10, %outer_backedge ]
+  %local_4_ = phi i32 [ -3220, %entry ], [ %tmp5, %outer_backedge ]
+  %local_6_ = phi i32 [ 12, %entry ], [ %tmp6, %outer_backedge ]
+  %tmp1 = sitofp i32 %local_4_ to double
+  %tmp2 = fsub double 0.000000e+00, %tmp1
+  %arg.v.i.peel = insertelement <2 x double> undef, double %tmp2, i32 0
+  %res.i.peel = call i32 @llvm.x86.sse2.cvttsd2si(<2 x double> %arg.v.i.peel)
+  %tmp3 = add i32 %local_4_, 1
+  %tmp4 = add i32 %res.i.peel, %local_3_
+  br label %inner_loop
+
+inner_loop:                                           ; preds = %inner_loop, %outer_header
+  %local_3_11 = phi i32 [ %tmp4, %outer_header ], [ %tmp10, %inner_loop ]
+  %local_4_12 = phi i32 [ %tmp3, %outer_header ], [ %tmp12, %inner_loop ]
+  %local_7_ = phi i32 [ 2, %outer_header ], [ %tmp13, %inner_loop ]
+  %tmp8 = sitofp i32 %local_4_12 to double
+  %tmp9 = fsub double 0.000000e+00, %tmp8
+  %arg.v.i = insertelement <2 x double> undef, double %tmp9, i32 0
+  %res.i = call i32 @llvm.x86.sse2.cvttsd2si(<2 x double> %arg.v.i) #1
+  %tmp10 = add i32 %res.i, %local_3_11
+  %tmp11 = mul i32 %local_7_, %local_7_
+  %tmp12 = add i32 %tmp11, %local_4_12
+  %tmp13 = add nuw nsw i32 %local_7_, 1
+  %tmp14 = icmp ugt i32 %local_7_, 305
+  br i1 %tmp14, label %outer_backedge, label %inner_loop
+
+outer_backedge:                                           ; preds = %inner_loop
+  %tmp5 = add i32 %local_4_, 9597741
+  %tmp6 = add nuw nsw i32 %local_6_, 1
+  %tmp7 = icmp ugt i32 %local_6_, 235
+  br i1 %tmp7, label %exit, label %outer_header
+
+exit:                                           ; preds = %outer_backedge
+  ret i32 %tmp10
+}
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.x86.sse2.cvttsd2si(<2 x double>) #0
+
+attributes #0 = { nounwind readnone }
+attributes #1 = { nounwind }