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

    <tr>
        <th>Summary</th>
        <td>
            LLVM fails to optimize BitScanForward loop to a single cttz instruction
        </td>
    </tr>

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

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

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

<pre>
    Here is a loop that LLVM fails to optimize down to a single cttz instruction:
```
define i32 @I32_BitScanFwd_1(i32) local_unnamed_addr #0 {
start:
  br label %loop
loop:
  %i = phi i32 [0, %start], [%next_i, %bit_not_found]
  %bit_mask = shl nuw i32 1, %i
  %curr_bit = and i32 %0, %bit_mask
  %curr_bit_is_zero = icmp eq i32 %curr_bit, 0
  br i1 %curr_bit_is_zero, label %bit_not_found, label %exit
bit_not_found:
  %next_i = add nsw nuw i32 %i, 1
  %done = icmp eq i32 %next_i, 32
  br i1 %done, label %exit, label %loop
exit:
  %result = phi i32 [ %i, %loop ], [ %next_i, %bit_not_found ]
  ret i32 %result
}
```

Here is the optimized version of the above op:
```
define i32 @I32_BitScanFwd_2(i32) local_unnamed_addr #0 {
  %result = call i32 @llvm.cttz.i32(i32 %0, i1 0)
  ret i32 %result
}
```

Here is a link to an Alive2 snippet of the above functions that shows that the optimization appears to be valid: https://alive2.llvm.org/ce/z/bqdZkV
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysVEGv2zYM_jXyhWgg03ESH3x4aWBsQHca0MMuhiwpsfoUyZXkpHu_fpDsJE77VmBDgSC2RfIj-ZH6mPfqZKSsSbkn5SFjY-itq7_Y3gyaheCzzoq_69-kk6A8MNDWDhB6FuDTp89_wJEp7SFYsENQZ_UmQdiriQcMvDInLYGH8AbK-OBGHpQ1pHgh9EDoC9nQ-Zc-hTwqI0EVCGRNfy-w3avwJ2emuYo2J7hTBRKsQFvOdDsaw85StEwIBwQLCmS7n4B8YC7cswB0DjTrpAaCZSx_Ok9vDyeCpQJSHGDo1VRDuacEP0bDBFge0me5J1ga-S20ajZ3KrTGhvZoRyOi2wMyms7MvyZk32sw4zWh53OsWjjz0bm2UyE5MyOmMrCkizwR7J2QVvn2TTqbQhU_DyC_3sJvPhGFLjhR-XsI0evO1nNnS4v8psKE9ezzROjE0tSOEGD89d5_ah0_Qr5wF9bI9xp4kF3gD_XHoB8rWx48Rp5MTxU66Ucdvp_7vbo5Gh6zh58OHxbTdzLcGpiyzEu_Pby7_dP_7Z6FXt5vlICLdF5ZA_aYDKyzl2j-XxcJ_8NF-p4izrS-wWp9Oa_i1V4ltN1yV1UOlGD1S5hgoJV5TYJi4EWri0TwRg2DDM98HEeT5MVP6uR7e51fF2Sy6AFsGCRzSbY6CRemVVxc6EMYfCQVG4INS7lWqU_rTgQbLgk2bwSb7qv46_VzJupCVEXFMlnn25xSLDfFJutrLvm2wpzzklc7eSxKeiw6jruqwC1dc8xUjRTXtKAVFnSbb1bYbcSayVxihYLvNmRN5Zkpfc-eKe9HWe_Wm3KTpc32SbERjbxCMhLEKOCujjEfuvHk45SUD_6BElTQsv4X4b4tiXVX5sQs9D_R8Wx0un7m7KRCP3Yrbs8Em5h1fnwYnP0ieSDYpFo9wSb18k8AAAD__8sg9G8">