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

    <tr>
        <th>Summary</th>
        <td>
            Compile `urem N` to `SUB`+`CMOVB` instead of `IMUL` when the input is < 2N
        </td>
    </tr>

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

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

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

<pre>
    Link for opt trunk: <https://llvm.godbolt.org/z/b5bqv6zzq>
General Alive proof for divisor small enough to avoid addition overflow: <https://alive2.llvm.org/ce/z/ntmx2a>

Given an input like
```llvm
  %_4 = urem i32 %x, 13
  %_6 = urem i32 %y, 13
  %_3 = add i32 %_6, %_4
  %_9 = urem i32 %_3, 13
```
then `%_3` is in [0, 26), and thus to avoid needing a full `IMUL`
```nasm
        imul    rcx, rax, 1321528399
        shr     rcx, 34
        lea     edx, [rcx + 2*rcx]
        lea     ecx, [rcx + 4*rdx]
        sub     eax, ecx
```
the last `urem` can be simplified.

Either to `icmp`+`sub nuw`+`select` (Alive proof: <https://alive2.llvm.org/ce/z/BaHRwz>)
```llvm
  %_8 = icmp uge i16 %_3, 13
  %_7 = sub nuw i16 %_3, 13
  %_9 = select i1 %_8, i16 %_7, i16 %_3
```
which compiles to
```nasm
        cmp     cx, 13
        lea     eax, [rsi + rdi - 13]
        cmovb   eax, ecx
```
or — maybe slightly better? — to `usub_with_overflow`+`select` (Alive proof: <https://alive2.llvm.org/ce/z/RPGqCb>)
```llvm
  %0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %_3, i32 13)
  %over = extractvalue { i32, i1 } %0, 1
  %small = extractvalue { i32, i1 } %0, 0
  %_9 = select i1 %over, i32 %_3, i32 %small
```
which compiles to
```nasm
        mov     eax, ecx
        sub     eax, 13
        cmovb   eax, ecx
```

---

Rust experiment that inspired me to open this: <https://rust.godbolt.org/z/fjaba8fdP>

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJytVl1zmzoQ_TX4RWMPlsCGBx5sJ-m9M21vJ53eV49AwqgRiEjCTvLr70rY-DM37UwzjkFwdvdodXbXuWKv2WfRPKFSaaRai6zumqeALFBAVpW1rYH7AD_AR8ptPdkolitpJ0pv4NEb_Odx_rydvb09B-Q-CO-CcPGJN1xTiRZSbDlqtVKld8_EVhi4mppKiXijuk2FrEJ0qwRDlDFhhWqQ2nJdSrW7SYI6n3jiufQcCr4n0tj6BdOBxZ4LwBtEGySatrNIiie-fz0L-49z1T9CKMDxOoKgd6jTvEaCYPfoJcArNCWnoNkV6PUaRDwI9nXArGcO5IOc4tIrZ2ty6m2g2i9tBTtyK4-bhUgY2B0K4mXorDAESd0NbRiyVWeOKW44Z6LZIIrKDk4AbP_-8uPz4HiI01AzpKT_E3Un3VUXPhma7nOCpzFOSJqeo02l0QmaROevJaf-ypl_DcQBCNteIhzghTOK796xKC4tImfBri1Ml_cWPVNn-E4ukaTGuly4A3DpLEAtOUdG1K0UpeBsciqoewE22uUUsKKoW38SS_h2IZtud1xzyQvrPAY4OamF39X1kv71uHtzusbpB9pNvJIcK9RtOBLT2bWaeuTcI_eU_w_Yi7PfC-D6MA52sJmfLm4rdleJokKFqlshudPjh3pzO_DXi9q7kAMd5GCEl4NmAo0d_lIPRa22-cd6UDpY4WARBvc4SMIgjVBNX50YpNhUVr6CMKzlOiAP6AjptdBBMtc7UMd6aGB_WgmP3z49r_JfUULoT81SIUHOrtTnS9db-qOC1R0KIm8zcbQnjvbkQHvigclZK3ILyCpOT2I4vA_DX6ymhd1S2fFbkYCOP8UT234E_IZx-IEmHZkD0TPWh2B_SJggo5t95Z2-c6ncX5Rh_z0ej0-Xjx30Kf7Sci1q3sCkrijsvjGt0JyhmjsdqhZmg62EuSktDR5uTPDyJ81pUrJvw-wc8Ww6m8Uknibz-YhlhKUkpSMrrOTZqk_XoWWir07YfQ18_7EcRL_68s-_Sz-eGmM5ZQh-BRwnDtpVninfD2aYYUAX4a-jTsvsnPYG1AkihWPa_wrZX8ZQRD9dYeEHYUzHDdzECY7JqMqKknIacTZlpJiHaUJDjuMkTgjBJcVRMpI059Jk0DsCjBsOPdC5gHtoHSOR4RDjaRimeBpFZD7JSVTGrAQPhJVRUkL18BqqayjTkc48pbzbGFdawlhzfEmNERuYvj4c-KedrZTOTKGsrYt65GNnnvt_R4yh1g">