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

    <tr>
        <th>Summary</th>
        <td>
            Move `icmp ult` before wide `mul nuw` by a constant
        </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>
    Overview: When the multiplication is `nuw` and `B` & `C` are constants, transform
- `x * B < C` → `a < ⌊C / B⌋`
- `x * B ≤ C` → `a ≤ ⌈C / B⌉`

Validity proof for a specific example, as a demonstration: <https://alive2.llvm.org/ce/z/WXEWZr>
```llvm
define i64 @src(i64 %x) denormal-fp-math=ieee,ieee {
%start:
  %_4.i = zext i64 %x to i128
  %p.i = mul nuw i128 %_4.i, 5
  %_8.i = icmp ult i128 %p.i, 9223372036854775808
  %0 = trunc i128 %p.i to i64
  %.0.i = select i1 %_8.i, i64 %0, i64 -1
  ret i64 %.0.i
}
=>
define i64 @tgt(i64 %x) denormal-fp-math=ieee,ieee {
%start:
  %_8.i = icmp ult i64 %x, 1844674407370955162
  %_4.i = zext i64 %x to i128
  %p.i = mul nuw i128 %_4.i, 5
  %0 = trunc i128 %p.i to i64
  %.0.i = select i1 %_8.i, i64 %0, i64 -1
  ret i64 %.0.i
}
Transformation seems to be correct!
```

This is particularly worth doing in that example, since other existing transformations can then remove the `zext`+`trunc`:
```llvm
define i64 @tgt(i64 %x) unnamed_addr #0 {
  %_8.i = icmp ult i64 %x, 1844674407370955162
  %p.i = mul i64 %x, 5
  %.0.i = select i1 %_8.i, i64 %p.i, i64 -1
  ret i64 %.0.i
}
```

And that means much tidier output overall:
```nasm
src:                                    # @src
        mov     rax, rdi
        mov     ecx, 5
        mul     rcx
        movabs  rcx, -9223372036854775808
        cmp     rax, rcx
        sbb     rdx, 0
        mov     rcx, -1
        cmovae  rax, rcx
        ret
tgt:                                    # @tgt
        movabs  rax, 1844674407370955162
        cmp     rdi, rax
        lea     rcx, [rdi + 4*rdi]
        mov     rax, -1
        cmovb   rax, rcx
        ret
```

(This is a sibling issue to #56562, which discusses a similar thing for `umul.with.overflow`)

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzFVktv2zgQ_jXyhbAhUe-DDn4kt8Veis1iLwVFjS0W1AMkFSf99TukJEd23LRFd1FDtkgO5_XN8DPLrnot_nwG9Szg7IVb8lRDS0wNpBmkEb0UnBnRtURo4iV-O5zxl7C2srOdHXs0seO9W1dAeNdqw1qjPbonRrFWHzvVeP7B87dru_MFVbZkR7xwT5yW90C9LPFyaqXMrbulvZdtcUgfyW6eW4_3TFlx7m2j-wYv0tlMdmM2v5gdf_9iUlTCvJJedd2RYAKEEd0DF0fBCbywppdg82MaBRU0NmflgLIYYga1Mb3GMbrBB809A91I-dxsOnXCFY7qj1_x-_T3w9M_ygsfJv8YiHvs3nGpgqNogYgE4498rbhHMzeh8YtHc3TfIsBMro_9umGm9sKDALDh2Rfx0t1kmsZYGGVsVG6BWBOfo43AgA_kK7wYMtslpiMioNliYz_tw74g2AZOPBuwUMRLo9m0WfCmJ9hIl939uDmnNAxT6odJFkdpGmf-0pXvdI0aWr5UdEEl0WLjxp_8aJDArZfZu3UyJePP43Uwqyq4pGpNTPikh2kQHi71uAbfnMx_C_57nC629yTIoihJo8hPw9TP4zhI6P9duN-M_KeZLkbO0QCNtr5LSytKoSOPBjcHZXluP9VIU_j0iLTgg2RKvpJzp0xNqk60JyIstzGzPMJatBxIh5SncFloY_eZq0A04cyRYovxN90zOIJE3xZ6GwK1vORQs7O5xN89y-_baWhb1kD1mVWVwsXQf-ugX26YZR8steKfLWv_NvvhI3WvWlv8F3HVaADRxrh4TQzyLhaiG0w_GIJQKyble0RbpidELR8i5f7AB-GcCXSKefxgQd1bMQeHqsR9OfBruCYpoum0UXqrxko9ClBt_QHljR9b0WUctwZ1WY7yysn9b2QxuQtujWM48G3jWL5xwfbkT-FpFe4nzr7XlDd5V66trNqVXAJbZubFO9yJ3nckwn9_qxUfPqzoPSzKD4C-YHG3a_HEzjSDdwJRSscrWg9gmQpBiZMYU0TD51pgR1dC80FrGLc3AkkJu94q2WsFGh-whTZnYeqNbfej7M6OUvLR3aoqwioPc7Yywkgo_rD0gxtmArD3nRLQFJCzqJxoInoneUWv841sNShZXF9MTuh2KDe8a3DiaGp8rfHi88XR7aNLDS9zjzavcFUXPEp4ntIy4n4W8zQAOEYM8qysWMryMFxJVoLUBRbKo7SF84gOjrFQK1FQn1I_DRJsiCj0NylDmqsYDYJjADGNsKWgYUJebksrVbiQyuGkUSiRovWbkGktTi2Ac4f22WDqThWad8Y0vFk534WL_V-wcex8">