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

    <tr>
        <th>Summary</th>
        <td>
            [LoopIdiomRecognize] Miscompilation on bitmask loop can trigger UB
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          ericliuu
      </td>
    </tr>
</table>

<pre>
    The following IR is miscompiled by the LoopIdiomRecognize pass:
```llvm
define i32 @src(i1 %a, i32 %b) {
 %z = zext i1 %a to i32
  %bitmask.i = shl i32 1, %z
  br label %loop.i

loop.i:                                           ; preds = %loop.i, %0
  %curr.i = phi i32 [ %b, %0 ], [ %next.i, %loop.i ]
 %curr.bitmasked.i = and i32 %curr.i, %bitmask.i
  %curr.isbitunset.i = icmp eq i32 %curr.bitmasked.i, 0
  %next.i = shl i32 %curr.i, 1
  br i1 %curr.isbitunset.i, label %loop.i, label %p2_different_liveout.SM.exit

p2_different_liveout.SM.exit: ; preds = %loop.i
  ret i32 %next.i
}
```
When optimized with `-passes="loop-idiom"`, the output IR is:
```llvm
define i32 @tgt(i1 %a, i32 %b) {
  %z = zext i1 %a to i32
  %bitmask.i = shl i32 1, %z
  %z.lowbitmask = add i32 %bitmask.i, -1
  %z.mask = or i32 %z.lowbitmask, %bitmask.i
  %b.masked = and i32 %b, %z.mask
 %b.masked.numleadingzeros = call i32 @llvm.ctlz.i32(i32 %b.masked, i1 true)
  %b.masked.numactivebits = sub nuw nsw i32 32, %b.masked.numleadingzeros
  %b.masked.leadingonepos = add nsw i32 %b.masked.numactivebits, -1
  %loop.i.backedgetakencount = sub nuw nsw i32 %z, %b.masked.leadingonepos
  %loop.i.tripcount = add nuw nsw i32 %loop.i.backedgetakencount, 1
  %curr.i = shl i32 %b, %loop.i.backedgetakencount
  %next.i = shl i32 %curr.i, 1
  br label %loop.i

loop.i:                                           ; preds = %loop.i, %0
  %loop.i.iv = phi i32 [ 0, %0 ], [ %loop.i.iv.next, %loop.i ]
  %1 = phi i32 [ %b, %0 ], [ %2, %loop.i ]
  %curr.bitmasked.i = and i32 %1, %bitmask.i
  %curr.isbitunset.i = icmp eq i32 %curr.bitmasked.i, 0
  %2 = shl i32 %1, 1
  %loop.i.iv.next = add nuw nsw i32 %loop.i.iv, 1
  %loop.i.ivcheck = icmp eq i32 %loop.i.iv.next, %loop.i.tripcount
 br i1 %loop.i.ivcheck, label %p2_different_liveout.SM.exit, label %loop.i

p2_different_liveout.SM.exit:                     ; preds = %loop.i
  %next.i.lcssa = phi i32 [ %next.i, %loop.i ]
  ret i32 %next.i.lcssa
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.ctlz.i32(i32, i1 immarg) #0
```
This optimized code can result in UB on the final branch to basic block `p2_different_liveout.SM.exit`. Here is Alive2 output that provides example input which triggers this error: https://alive2.llvm.org/ce/z/GcsFEn
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEV1tv4zYT_TX0yyCCREW5PPghjj9_XaD7st1FHxcUNbamoUiVpOLEv74gJV_k22aLFg0Cx6GGZw7P3CjhHK004pQVM1bMJ6LztbFTtCQVdd2kNNX79GuNsDRKmTXpFXz6AuSgISdN05LCCsp38DXCr8a0nyoyzReUZqVpg9AK51j-xNI5S5_YXdr_KvXa9EsVLkkjUM6B3abOSsYfKAPGC8H4c7_Oi5LxR2D3s35PWNkAy-ewwTcPgzl4E8wHk7iLfCPcS0LR1tUqwmUBNyBsLUsLSpSowqIypk1oYBs_h5X8CT7-w_IZtBYrFx3vYXvH6QFF2Vk78Gtr6o9bzIYj99bAinn83q9rfPM7qB43WuyUiZDD0bEawIWutlr2LgeAnUQnnFxJvtMO_YBAsmkB_xyhHHgJeIcH62mOhB_5zg7U7wN44jaYHQfmcKnl3ytaLtGi9t8VvaLpfPLb5wTfyB9G8Kpd_nQxWgNBi35Lf9C-x76fHyV1_-_vNWowraeGNljBmnwN7C69CYWAjuVzxnlwcEOhUBjnYSd_jvVjOt92vq-vjxeNX_mPFM0_XDXhe6LMejDvs6zaZdk-sfgz3GSjXTt7Y7fmh1BXUrNM-nw7zultsfTY-1rY2ie6axSKivRqg9b0kZZCqa2GQdtEerVJghj8YYs77I-qZuBth4w_niEUHAjp6RVL8j2860rQ3Rq0W0cvAff5GqlzsMNzo7EdWAeNt5AXCZyI3qd0Ugr5gtUKvXhBLU2n_VmqMc5HZEdMTpG9pXYPGEmOAS8yGHWDcUs86BzlqOOdg_l7vec_6_zDQej1pPmnFzr_bkcSDnhpAoTF7GcGCr-G9KNhkv3bc4QfhzE7zpexLD9IP3q9uF3WKF_OUbyi-z7tB8TdNBvDfnxunZl5PzHKfiYlj-slUdI5cS5zrl85Tgdkj3Q8JvvPfAaLTktPRsOT9zbMOdAm9OJQ06DN0iKCNu5dS9Cm02vSFbgWZaeEF6VCWJNSFn1nNTTYGPvO-IM2et-aK5RKWLzS3IeGTk0j7CrOSZ6nZ-f515rcwTyXpkKQQoNF1ykPpOHbDIyO83tJWigordCyDoO1FI4klMqExLpLr0bvLk3gFwykHTyFh3x7HfC18NBa80oVOsA30bQKgXR4tq4puLK0WqF14ANZtNbYIGvtfRvvEXzB-EJE0CSKYcKhFxIZX2wYX_xfusX_9KSa5tVj_igmOM3uHm7vH9MszSf1NEcsi4dclnmaVbKUeVHcFzwti_scRf7IJzTlKc_TgnOeZUWaJ7d8maa8qgqOEm9Fym5TbASpnfcJOdfh9I4_3OeTmPAuvoBwrnEN8WG4GhXziZ2GPTdlt3IhlOS826N48iq-uZy-ebBiDp-3rygi5pvRsL2thCyOYRykg2-zSWfVdCzZinzdlYkM97RFvH71f25aa_5A6RlfRKqO8UU8yl8BAAD__zr-6f4">