[IndVars] Miscompile: UB introduced to a simple program by indvars

[xortator]

https://godbolt.org/z/xdce1e8P4

Run opt -passes=indvars on the following IR:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

define void @test(i32 %tmp) {
bb:
  br label %bb2

bb1:                                              ; preds = %bb12
  br label %bb2

bb2:                                              ; preds = %bb1, %bb
  %tmp3 = phi i32 [ %tmp, %bb ], [ %tmp7, %bb1 ]
  %tmp4 = zext i32 %tmp3 to i64
  %tmp5 = getelementptr inbounds i64, i64 addrspace(1)* undef, i64 %tmp4
  br label %bb6

bb6:                                              ; preds = %bb2
  %tmp7 = add i32 %tmp3, -1
  %tmp8 = icmp slt i32 %tmp7, 11
  br i1 %tmp8, label %bb9, label %bb11

bb9:                                              ; preds = %bb6
  %tmp10 = phi i32 [ %tmp7, %bb6 ]
  ret void

bb11:                                             ; preds = %bb6
  br label %bb12

bb12:                                             ; preds = %bb12, %bb11
  br i1 false, label %bb1, label %bb12
}

Output:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

define void @test(i32 %tmp) {
bb:
  %0 = zext i32 %tmp to i64
  br label %bb2

bb1:                                              ; preds = %bb12
  br label %bb2

bb2:                                              ; preds = %bb1, %bb
  %indvars.iv = phi i64 [ %indvars.iv.next, %bb1 ], [ %0, %bb ]
  br label %bb6

bb6:                                              ; preds = %bb2
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, -1
  %indvars = trunc i64 %indvars.iv.next to i32
  %tmp8 = icmp slt i32 %indvars, 11
  br i1 %tmp8, label %bb9, label %bb11

bb9:                                              ; preds = %bb6
  %tmp10 = phi i32 [ %indvars, %bb6 ]
  ret void

bb11:                                             ; preds = %bb6
  br label %bb12

bb12:                                             ; preds = %bb12, %bb11
  br i1 false, label %bb1, label %bb12
}

The original program is well-defined. The new program will have poison in %indvars.iv.next for any other input than zero, and then branch by poisoned condition.

The issue appeared with

commit 34ae308c73e4d76dbdab25a6206d3fbc5ebafdf5
Author: Max Kazantsev <[email protected]>
Date:   Wed Aug 3 13:10:56 2022 +0700

    [SCEV] Use context to strengthen flags of BinOps

    Sometimes SCEV cannot infer nuw/nsw from something as simple as
    ```
      len in [0, MAX_INT]
    ...
      iv = phi(0, iv.next)
      guard(iv <s len)
      guard(iv <u len)
      iv.next = iv + 1
    ```
    just because flag strenthening only relies on definition and does not use local facts.
    This patch adds support for the simplest case: inference of flags of `add(x, constant)`
    if we can contextually prove that `x <= max_int - constant`.

    In case if it has negative CT impact, we can add an option to switch it off. I woudln't
    expect that though.

    Differential Revision: https://reviews.llvm.org/D129643
    Reviewed By: apilipenko

but this patch only exposed the issue, not caused it. Note that in the original program loop lever goes on 2nd iteration, and this patch managed to infer nuw for IV increment in (never executed) backedge. But then the another part of IndVars has moved this increment out of dead block and introduced uses to it.

[xortator]

Please don't revert this patch, it's not guilty. I'll prepare a proper fix.

[xortator]

The problematic instruction was hoisted from backedge to inside the loop by

NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts, TTI);

Guess this thing just doesn't take poison into account.

[xortator]

On review: https://reviews.llvm.org/D132022

[xortator]

commit 86d5586d78d813a6921d786f7ddb1a41c6fb56e0 (HEAD -> main, origin/main, origin/HEAD)
Author: Max Kazantsev <[email protected]>
Date:   Tue Sep 13 12:31:07 2022 +0700

    [SCEVExpander] Recompute poison-generating flags on hoisting. PR57187

    Instruction being hoisted could have nuw/nsw flags inferred from the old
    context, and we cannot simply move it to the new location keeping them
    because we are going to introduce new uses to them that didn't exist before.

    Example in https://github.com/llvm/llvm-project/issues/57187 shows how
    this can produce branch by poison from initially well-defined program.

    This patch forcefully recomputes poison-generating flag in the new context.

    Differential Revision: https://reviews.llvm.org/D132022
    Reviewed By: fhahn, nikic