<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/60234>60234</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [GuardWidening] Miscompile due to widening into loop-invariant WC
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          max-quazan
      </td>
    </tr>
</table>

<pre>
    Alive2 repro: https://godbolt.org/z/P7fb4P9ab

The bug is in guard widening. However, to demonstrate why it is a bug, I will also run indvars. Consider case:
```

declare i32 @llvm.experimental.deoptimize.i32(...)

define i32 @test(i32 %start) {
entry:
  %wc1 = call i1 @llvm.experimental.widenable.condition()
 br label %loop

loop:
  %iv = phi i32 [ %start, %entry ], [ %iv.next, %backedge ]
  br i1 %wc1, label %guard_block, label %exit_by_wc

exit_by_wc:
  %rval1 = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv) ]
  ret i32 %rval1

guard_block:
  %start_plus_1 = add i32 %start, 1
  %cond = icmp ne i32 %start_plus_1, %iv
  %wc2 = call i1 @llvm.experimental.widenable.condition()
  %guard = and i1 %cond, %wc2
 br i1 %guard, label %backedge, label %failure

backedge:
  call void @side_effect()
  %iv.next = add i32 %iv, 1
  br label %loop

exit:
  ret i32 -1

failure:
  %rval2 = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv) ]
  ret i32 %rval2
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite)
declare i1 @llvm.experimental.widenable.condition()

declare void @side_effect()

```
Let `start = 0`. The possible scenarios here are the following:
1. `wc1 = false`. In this case, `@side_effect` is never called, we deopt with `iv = 0`.
2. `wc1 = true, wc2 = false` (on 1st iteration). In this case, `@side_effect` is never called, we deopt with `iv = 0`.
3. `wc1 = true, wc2 = true` (on 1st iteration). In this case, `@side_effect` will be call once. Deopt after `loop` will not happen (because `wc1 = true `  and is loop-invariant), however `cond` will be `false` on 1st iteration (`iv` will be equal to `start + 1`). So regardless on `wc2`, we will then deopt with `iv = 1`.

As you can see, in all cases the number of calls of `@side_effect` matches the value we deoptimize with. We can expect that this fact stays true, as long as we do the right things.

Now, indvars comes. Invars notices that branch by `wc1` is loop-invariant. Therefore, deopt there can only happen on 1st iteration or never. It means it is safe to replace the `iv` in deopt value with `start`. Result: https://godbolt.org/z/Wq7EMT58M
```
declare i32 @llvm.experimental.deoptimize.i32(...)

define i32 @test(i32 %start) {
entry:
  %wc1 = call i1 @llvm.experimental.widenable.condition()
 br label %loop

loop:                                             ; preds = %backedge, %entry
  %iv = phi i32 [ %start, %entry ], [ %iv.next, %backedge ]
  br i1 %wc1, label %guard_block, label %exit_by_wc

exit_by_wc:                                       ; preds = %loop
  %iv.lcssa = phi i32 [ %start, %loop ]
  %rval1 = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv.lcssa) ]
 ret i32 %rval1

guard_block:                                      ; preds = %loop
  %start_plus_1 = add i32 %start, 1
  %cond = icmp ne i32 %start_plus_1, %iv
  %wc2 = call i1 @llvm.experimental.widenable.condition()
  %guard = and i1 %cond, %wc2
 br i1 %guard, label %backedge, label %failure

backedge: ; preds = %guard_block
  call void @side_effect()
  %iv.next = add i32 %iv, 1
  br label %loop

 ret i32 -1

failure:                                          ; preds = %guard_block
  %iv.lcssa1 = phi i32 [ %iv, %guard_block ]
  %rval2 = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv.lcssa1) ]
  ret i32 %rval2
}

declare i1 @llvm.experimental.widenable.condition() #0

declare void @side_effect()

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }
```
Note that this transform is completely legal and corresponds to LangRef for widenable condition, saying:
```
While this may appear similar in semantics to undef, it is very different in that an invocation produces a particular, singular value. It is also intended to be lowered late, and remain available for specific optimizations and transforms that can benefit from its special properties
```
(when it was written, there is no such thing as `freeze`, but you can think that widenable condition outside the loop behaves exactly like `freeze(undef)` outside the loop, so it's a loop invariant).

And now how the bug happens. Let's run guard-widening on top of it: https://godbolt.org/z/P7fb4P9ab
```
declare i32 @llvm.experimental.deoptimize.i32(...)

define i32 @test(i32 %start) {
entry:
  %wc1 = call i1 @llvm.experimental.widenable.condition()
 br label %loop

loop:                                             ; preds = %backedge, %entry
  %iv = phi i32 [ %start, %entry ], [ %iv.next, %backedge ]
  %start_plus_1 = add i32 %start, 1
  %cond = icmp ne i32 %start_plus_1, %iv
  %wide.chk = and i1 true, %cond
  %0 = and i1 %wide.chk, %wc1
  br i1 %0, label %guard_block, label %exit_by_wc

exit_by_wc:                                       ; preds = %loop
  %iv.lcssa = phi i32 [ %start, %loop ]
  %rval1 = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv.lcssa) ]
 ret i32 %rval1

guard_block:                                      ; preds = %loop
  %wc2 = call i1 @llvm.experimental.widenable.condition()
  %guard = and i1 %cond, %wc2
 br i1 true, label %backedge, label %failure

backedge: ; preds = %guard_block
  call void @side_effect()
  %iv.next = add i32 %iv, 1
  br label %loop

 ret i32 -1

failure:                                          ; preds = %guard_block
  %iv.lcssa1 = phi i32 [ %iv, %guard_block ]
  %rval2 = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %iv.lcssa1) ]
  ret i32 %rval2
}

declare i1 @llvm.experimental.widenable.condition() #0

declare void @side_effect()

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }
```
Now imagine that `wc1 = true` and `wc2 = true`. On the first iteration, `wide_check` is true (because` iv = 0` and `start + 1 = 1`). So we will reach guard block and then backedge, calling `@side_effect` once. Then, on the 2nd iteration, `cond = false` and therefore `wide.chk = false`. It means that we must deoptimize in block `exit_by_wc` with `lv.lcssa = 0`.

So now we've called side effect once, but after deopt, we think that `iv = 0`. If it was used to re-execute the loop in interpreter, it will make one extra iteration.

My working theory is that widening into loop-invariant WCs is just wrong.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWl9v27jy_TTKyyCCTMeO_ZCH_Pnldwu0exe7BfoYUNLI4oYiVZKy4376ixlKsuwa29x2b4vFtihiSyI5Z-YMycORpfdqYxBvksVdsni4kF2orbtp5Mvlx05-kuYit-X-5larLQpw2DqbzG-hDqH1yfw2EY-JeNzYMrc6pNZtEvH4KRGPv15X-dWva5kn2UOS3ca_72uEvNuA8qAMbDrpStipEo0ymxT-ZXe4RZeIewgWSmys8cHJgLCr96ACdZPUn1q8gZ3SGqT2FlxnQJlyK51P4d4ar0p0UEiPBDDaX2b9_wmcEgstHYKaC0iuMq23TYovLTrVoAlSpyXaNqhGfcJUzUUiVmmaJmJ9PEalzDhEQB8SseIrsfBBupCINSTXd7E1muD2IyigRrtiBsn8AQqpNajZeSAcJJlrTAtrShWUNYlYjVAgd6BljpoG1Na2U4R8fWRSbdliW6uIe3E3QXtP3xknJIsHvo7P1TY1-DK0yGXxjOUGuVE_dO7YAfaJmo2QmOmnXNvi-eg-vqjwlO-fdsUU8OTuEWy3lXoaqwkjr6SPW7I3gp8lQhzYUtv4eHTHYYD-GZueYpx6dASSo_jU6s4_RayyLOE4H-5hNulAhHJDVTQtDKl0PFAfc7U9yhvx7XkzkhOhmrInkFr3RneFOCRZfMo9jogcsuHoZiWV7hxOwza2O8SM8W-tKskDmrlPWFVYhM9w9vl3GlSibRLRP5sJlFgTywO_l0fMDqg_Sz3x41KvZyC5fpgiTeZ38NiZgliF2xAcrcdgLEGkQIOxlUMEY_3eFGBsZ3bKlOBbLDotA-UFr6IOQ-cMNNhYtydURhYFeq9yjQ02NKpDWe6cCjhyMi6eX5d6x4N8gf-za_hbDJAsM54nTA09SoH2mNZG8OALNNIp66FGh0CmQo1QWa3tTpnNyPIspbGGtbiS2iOP9sZAqJWPmwlNiGV2AnOZ0b5kaOfi5ECeGTsEphl2KtTUq19zGWM0KY5MBtexgWFaDxAgEStrYOYDqIBOxjiu_6fI5n-KjK-_FRhv3jnG6WRNgSk8MCpZBXTUhyfv0NLYALVsWzRkNsdCdh5PQdI1xEXMA3W_VGYrnZKGNmGCUkeFQQ15hZsASZbZGPJTt8gmB2raAT92UpNQOeSguIMZeUtR-N2Cw410pUbvaUQGK_gxk8DjhBrNeTpmBzri31sPe9tBIQ145MAqAxQ9irPntDZdk6MDW3FYPX05G_xGhqLu-2yl7nBMCl6xGEoKH5CN0aQuAoRahshrJYsAPsi9H1NDUrzNhj5pJMsjO7WpuYvZ-CNPfrG7CJ8VGxS2QU9pw1fGBlUwNhkgd9IUNeT7nuo-pY-55SnvsLKOscRoBp7vhN8avR9y5zNirYvzI4U3ARqUxvc608sKiVyHrZZFXDXGFFADZ33weubi9k6rxm_oOx1eI5M_fLz-v3fvF6t3Z5e4f5RAhf_mH-19rcPSM7QTBTII2L-p5P3aEBziOuglXXgvv-Q4dZu6dFZpw1-sdyK0Y9Xzer391wTop1R_pVT_PJJTOr6_jv-icv-GdeSMZ5OEnZ2bTBH5cd8zE0p8hwk1-5pzxFcreUjE_GxB5VVyXobgVN4F9DxOJOD67jscYOAQgOP99hcbcKJ0gpPGV9Y1pAgK27QaA-o9aNxIzVOwsM6hb60pPamFt9JsfsMKKutgjBpMonYPXu6n544TAB9qpTEab-QeSLVIB141SktHusNjI01QBZvrTIkVSynWLFt0eyhVVaFDE6g1uyINKLO1RVQ8rbNlRwJLQitdUBRILrl5ZTb0PYoaFkTKx_qaMgFNiSXZzBG03aHDErQMUf2ZEhw2kvToVirNTlMIiCdVqQL6VGYEntuPoe2VHim1HA1WKkDlbAMq-NhfasLcogsK_flinljtSEerADtSoE6FgBzsqALpEGTBd0Ud1SjJVJL7DvET9oI878Ior6nRc4R1hkSwXaC8ZknIe2eOtdyiB3yRRaD0UM84MSBWPU9rPluc9ObQW1AhEddECo84PbccHwJMCcbu6CDDI-Tdpte2PoW3GAdxXV9bvRxqqyR8g23pQKBeJUtPq7c_ZelXbic_SJZ-V3WjSkyL-nmqS4aD4aBPDq2zE_ky9B4lzOwzaZ39FNZ_L2H9o_TukHU_te7raPupdf_RWncHqpEb2oVZ65yWfJcZz7pYt5zeTuHfJpbRlTuu_nKxl0L4VNRYPPflulibHcu2fPdQcx6MTGqoYwF0qKQO5VKHsqj798Yx9VhLkvibTnWKKames8XPWGx-X0eFaKMngpaXEz_G_XCsC_fGYq1xcHXc-iYvDYZaYtSQCE3nw7TAqkwPP1lmkx2Kq8uxlqine0x2Wgv-3bIK3GEirrfYF_eBdWV0lL0cdG0sqfcTiWvPE4V78gIA3lSDju58VPwOL_EFiy5MJK8yfChwrcMQ39hTJ6Kokc8I1iDgS3DyENQj_O_2sLPumTgKNVq35zQZBTfdVybYk0IvfLj31PAPiubOWbNJL8qbebmer-UF3syW11dXy_VczC_qm7m4zvJ8vZbz69VsLpfXy0qUWb6SYjlfrRb5hboRmZhnMzGfZUJk83ReLBYiXy3WuchmuFokVxmdaXTKi4R1mwvlfYc3y0zMry54vfbDbybcDTW6zLuNp1VF-eAP3YIKmn9d8f-Utx96B5PFA7xTnk6VdOQrOy43f8H9i87pmxPtrkLd5Wlhm0Q8ks3-47J19g9eix4Zt0_EI0P_TwAAAP__DUQkqg">