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

    <tr>
        <th>Summary</th>
        <td>
            [LoopPredication] Miscompile due to sinking of widenable condition into loop
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    https://godbolt.org/z/8j953fhT6

Run `opt -passes=loop-predication` on the following IR:
```
define i32 @test() {
entry:
  %wc = call i1 @llvm.experimental.widenable.condition()
 br label %outer_loop

outer_backedge: ; preds = %always, %never
  call void @print()
  %cnt.next = add i32 %cnt, 1
  br label %outer_loop

outer_loop: ; preds = %outer_backedge, %entry
  %cnt = phi i32 [0, %entry], [%cnt.next, %outer_backedge]
  br i1 %wc, label %inner_loop.preheader, label %exit

inner_loop.preheader: ; preds = %outer_loop
  br label %inner_loop

inner_loop:                                       ; preds = %never, %inner_loop.preheader
  %iv = phi i32 [ %iv.next, %never ], [ 2, %inner_loop.preheader ]
  %iv.next = add nuw nsw i32 %iv, 1
  br i1 false, label %never, label %always

never: ; preds = %inner_loop
  %icmp = icmp ugt i32 %iv.next, 37
  br i1 %icmp, label %outer_backedge, label %inner_loop

exit: ; preds = %outer_loop
 %cnt.lcssa = phi i32 [%cnt, %outer_loop]
  ret i32 %cnt.lcssa

always:                                           ; preds = %inner_loop
  br label %outer_backedge
}

declare void @print()

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

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }
```

Result:
```
; ModuleID = './reduced.ll'
source_filename = "./reduced.ll"

define void @test() {
entry:
  br label %outer_loop

outer_backedge.loopexit:                          ; preds = %never
  br label %outer_backedge

outer_backedge: ; preds = %outer_backedge.loopexit, %always
  br label %outer_loop

outer_loop:                                       ; preds = %outer_backedge, %entry
  %wc = call i1 @llvm.experimental.widenable.condition()
  br i1 %wc, label %inner_loop.preheader, label %exit

inner_loop.preheader: ; preds = %outer_loop
  br label %inner_loop

inner_loop:                                       ; preds = %never, %inner_loop.preheader
  %iv = phi i32 [ %iv.next, %never ], [ 2, %inner_loop.preheader ]
  %iv.next = add nuw nsw i32 %iv, 1
  br i1 false, label %never, label %always

never: ; preds = %inner_loop
  %icmp = icmp ugt i32 %iv.next, 37
  br i1 %icmp, label %outer_backedge.loopexit, label %inner_loop

exit:                                             ; preds = %outer_loop
  ret void

always: ; preds = %inner_loop
  br label %outer_backedge
}

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

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }
```

The issue is similar to https://github.com/llvm/llvm-project/issues/60234 (but then it was in Guard Widening). We are not allowed to sink widenable conditions into loops. Here is why it is a miscompile:

The behavior of program before the transform is limited to 2 scenarios:
- If `%wc` is true, branch will always go into the inner loop, and the program will infinitely call `@print()`. Program never returns.
- If `%wc` is false, program returns `0`, and `@print()` is never called.

This allows us to optimize return value to `ret i32 0`  (IndVars actually does it, but it also eliminates some other code and breaks the example for unrelated reasons).

After the reansform, `%wc` is computed in the loop. It means that the legal scenario is that the program calls `@print()` 10 times and then exits, returning `9`. It was impossible scenario before the transform.

This code in Loop Predication is wrong: https://gitlab.azulsystems.com/dev/orca/-/blob/master/llvm/lib/Transforms/Scalar/LoopPredication.cpp#L1195

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWE1v4zgS_TX0pRBBpiw5PviQrOHdADPAYLaxcxxQUslmN0VqScqO8-sXRcryR5xdZ9HTpzYa7pgqVj0-Pr6SJJyTG424ZPkzy1cT0futsctWvD78uxdvQk9KUx-WW-87x7InxteMrzemLo3yibEbxtdvjK8fvy7yrNl-KVi6YulT_P6918CK1HQeHjrhHDqWrZQx3UNnsZaV8NJoVqRgNPgtQmOUMnupN_DyO9WKqYp0-Bd-1thIjSAzDmyWenSe8UfGF8DmzzECtbeHcToA4_m-ApatoBJKgZzSRKV2bYKvHVrZovZCJXtZoxalwqQyupYBWsg85CktKFGionym92j_pJWcLzeOlqL6hvUGWfYELHsGWqoL5RnPhdqLg2P8b_RD4w7tEWXAtjOyJnSdldpfVKf4SvtE46sPyURdRxLCOGWcHkPvRRpGb6G8WkhEG2m9QBPiu62MQPLn9CI0X4Wf-fMZ9CHgqkC-OoNO-0M7RqHjMqTWA-Cks7hFUaO9CMBX6c9XeHPCx2s9EXRJ3ynN7eSU8r7Pu8Jx9yMfN9GeqJa7a6bj6DmlIR2cSAf-X3LDGeWnTKOudL8H7fZHfcndtbzkFBqhHF5swbigcWRQ-xlzMebWPlwzHYFVbRcCwh_9xp8gjWvP5u_EQ9EXQN4L-n_scJDTXXIZxK0q58T1Lp3O5uXME_kW_dkpjlnOcQwM3q2ym0p7T-17hxi5icXnq3MUNVZKWPzYnobv7BnWva7IOuHJexuAa0PWRvlBm8YigjbuoCvQptd7qWtwHVa9Ep7MF_ZSKYu-txpabI09MP4otagqdE6WCltsKatFUe-t9DhiOIKktDU2n_d5YDxLL8j33sqy9-jCpUjn_PkHrAhOG3DZ_Ya-iq5X_qMOSdvwq6l7hS-rQQLzhPG1xbqvsE6UYnw4M870tsI_G6lQixaHaH4dzS_FEBrwUQv3dODPts6ELh-P4Gcd9V6J39uyP4IWT_W5xX2-8_6fB_qu_vw97nl-9uOf_fiv78cXZ-rOxvyZzx0aoz5Mjna7937_jvqzVf6gVvlliyCd6-kbnGylEha8gavnWem3fZlUpmV8TTwM_z101nzFyjO-Dkkc4-si5dkMGH8se09PrRqkh71wIDX8vRe2hj-INqk3jC8S-AMhUu1B0NMt1lTeSf0NRnphpJeyeAOkLJfAP9AG3PvtgYpIBwJa6SrTdlLhqf-PKy1xK3bSWDANdNZsrGihxMZYDM_X3grtGmNbSqVkK31Ew8FVqIWVxo1JH-CloYf36P1FSlO87YPFlFboaht2C-IpgY2JyKlMOB1hDRQsdB1Gj3jCLKkbqaVHdYgNigpd3lcWaQK_DVOil0ZhuORjfKMHHmsNUyguCGOAc6sazY91CBDWySW3xD1tn4PeEWWm87KVbziUgJ1QPdIFVqTHm3oqSbb5-KLrfwnrQFS-F0odoDboIPodqUiSNpwBpD3Rgk6RMy2C8VvCY2oMsEuL4psLZOKraDuF0BgLvbaoBG2lReGMdqS7c_RPjUcbplkcBBB60SV5pKqessj4MiZ0KHjx0NIk8Fvh4zhuhBoFE2RxvHSknRh0t1mepuBli-4oCw3k6OGNSGRS6g3NjAJ4GU5W25loAKe6t2T9fs8Cd1LDL8Z08NvppVM4VdboDdnJOy9QokzEW6_cwXls3eALNe4YXxtbCcbXD4yvS2VKxtetcJ4a7Wgckka_HEGRZ_yzEkpQCOE4g5FUXcd49st0usgj6km9zOpFthATXE6L-aLIFtN5OtkuRVPlaVGVzSwX-bxOq-k0E7NmjljO8rSpJ3LJU56lGZ-lBS-mafKYlmJWzHCWzmeLJhNslmIrpEqC0Ru7mQRPWxbTYp5NQvdy4S0g5xr30TXp3j9fTewyuGHZbxw1Cum8O2Xx0qvw-vBqcSxfwa-jW0Edzwc5H-2xaW7538n-Jr1V128dP-PStKj_BAAA__-NEGew">