[InstCombine] Wrong value truncation due to incorrect analysis of iv known bits

[aleks-tmb]

define void @src(i32 %0, ptr %p, i1 %cnd) {
entry:
  br i1 %cnd, label %header, label %exit

header:                                           ; preds = %latch, %entry
  %iv = phi i32 [ %iv.next, %latch ], [ 256, %entry ]
  %iv.trunc = trunc i32 %iv to i16
  %div = udiv i16 11, %iv.trunc
  br i1 %cnd, label %loop1, label %loop0

loop0:                                            ; preds = %header
  %load = load i32, ptr %p, align 4
  br label %loop1

loop1:                                            ; preds = %loop0, %header
  %v = phi i32 [ %load, %loop0 ], [ 0, %header ]
  store i32 %v, ptr %p, align 4
  %guard = icmp ugt i32 %iv, 10
  br i1 %guard, label %latch, label %loop2

loop2:                                            ; preds = %loop1
  %div.trunc = trunc i16 %div to i8
  store i8 %div.trunc, ptr %p, align 1
  br label %latch

latch:                                            ; preds = %loop2, %loop1
  %iv.next = add nuw nsw i32 %iv, 1
  %exitcond = icmp ugt i32 %iv, 300
  br i1 %exitcond, label %exit, label %header

exit:                                             ; preds = %latch
  ret void
}

If we run instcombine pass on this example, it will convert trunc i32 %iv to i16 into trunc i32 %iv to i8 to avoid cast:
https://godbolt.org/z/ze4E45ThT

But this transformation is wrong, because on the first iteration %iv is equal to 256, and the 8 bits trunc makes it equal to 0. This give us a division by zero on the next instruction: %div = udiv i16 11, %iv.trunc.

It seems that the problematic patch is #73662

@nikic Could you please take a look?

[antoniofrighetto]

May be false positive in Alive2 as well?

[dtcxzyw]

May be false positive in Alive2 as well?

You need -src-unroll and -tgt-unroll for loops :)
https://alive2.llvm.org/ce/z/Vh4zAU

[antoniofrighetto]

Just out of curiosity, did you fine-tune the iterations in a particular way, or some trial-and-error? (I had tried a few ones before and didn’t manage to have the UB triggered)

[dtcxzyw]

Just out of curiosity, did you fine-tune the iterations in a particular way, or some trial-and-error? (I had tried a few ones before and didn’t manage to have the UB triggered)

I just full unrolled the loop :)

%iv.next = add nuw nsw i32 %iv, 1
%exitcond = icmp ugt i32 %iv, 300

[antoniofrighetto]

I just full unrolled the loop :)

Definitely makes sense, thanks!

[nikic]

Reduced test case:

define void @src(i32 %x) {
  %x.trunc = trunc i32 %x to i16
  %div = udiv i16 11, %x.trunc
  %cmp = icmp ult i32 %x, 256
  br i1 %cmp, label %loop, label %exit

loop:
  %trunc = trunc i16 %div to i8
  call void @use(i8 %trunc)
  br label %loop

exit:
  ret void
}

declare void @use(i8)

The issue is that canEvaluateTruncated() preserves context instruction across non-speculatable operations.