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

    <tr>
        <th>Summary</th>
        <td>
            Move comparison before `umul.with.overflow` 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>
    When the result of a `umul.with.overflow` by a constant is only needed when it didn't overflow *and* the result passes a comparison check, that comparison can be moved *before* the checked multiplication so that it can be replaced with a normal multiplication.

Alive2 proof for an example case: <https://alive2.llvm.org/ce/z/XdagRK>
```llvm
define i64 @src(i64 noundef %x) denormal-fp-math=ieee,ieee {
%start:
  %0 = umul_overflow i64 noundef %x, 5
  %1 = extractvalue {i64, i1, i24} %0, 1
  %2 = extractvalue {i64, i1, i24} %0, 0
  %_8.i = icmp ugt i64 %2, 9223372036854775807
  %3 = or i1 %1, %_8.i
  %.0.i = select i1 %3, i64 -1, i64 %2
  ret i64 %.0.i
}
=>
define i64 @tgt(i64 noundef %x) denormal-fp-math=ieee,ieee {
%start:
  %is_bigger = icmp ugt i64 noundef %x, 1844674407370955161
  %product = mul nsw nuw i64 noundef %x, 5
  %r = select i1 %is_bigger, i64 -1, i64 %product
  ret i64 %r
}
Transformation seems to be correct!
```

This is highly advantageous as actually emitting the overflow check needs a full x86 `mul`, whereas without it a `lea` can be used, and since it collapsed the two conditions into the one check it saves the second conditional move too:
```nasm
src:                                    # @src
        mov     rax, rdi
        mov     ecx, 5
        mul     rcx
        seto    cl
        test    rax, rax
        mov     rdx, -1
        cmovs   rax, rdx
        test    cl, cl
        cmovne  rax, rdx
        ret
tgt:                                    # @tgt
        movabs  rax, 1844674407370955161
        cmp     rdi, rax
        lea     rcx, [rdi + 4*rdi]
        mov     rax, -1
        cmovbe  rax, rcx
        ret
```

---

Motivation: after https://github.com/rust-lang/rust/pull/95295, we're hitting this a bunch in Rust.  https://github.com/rust-lang/rust/pull/99174 does it manually for some cases, but it would be much nicer for LLVM to do it everywhere.

Minimized demonstration of the code pattern: <https://rust.godbolt.org/z/7KWh5j5Mz>
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy1VsGS2jgQ_RpzUUEZGdtw4DAZdi7JXFKpzd5SsiSMsrJESTIzk6_fJ9lDDEOyyVYtZbCt1uvXaqkf3Vjxsv18kIaEgyRO-l4HYveEkazK-67XiycVDgt7km6v7RMGSfMCK7fGB2YCUZ5Yo1-IkVJIQZ6iKxWIUMJktIavEUkyeseMwO-U6ci8lz75647MKW8N4QfJ_87oPeaxcGFghjSSdHAportG7q2Trx4TDAbEHNRRK86CAsjbwQ9iGvFOHjXjMVasDNTGuo7pK9wiy3dZfjf83ml1kpQcnUVmwEngSD6z7qhBy7zMijuSFfeHEI4ezxl9wMUSaKH1qVtY12KEI9aHb_j-JVj78X1W_DGSVPlwxbnDkJB7ZSRR1Ypkq9w7ntF1fDG2N7Bh9eVzRjdEyCH6-f4471g4ZMVOSQme-3gjWf1upKAltsuFGF0aINFFjqh3JO7yl_M2vWW5J-UEs0wY-Rwc4-HEdJ9YgIoT1TL90lVW7xJBfF1O0PS30fkE_WW9UMmB4t2R9G0YEgS3ceaG0qKoaV5U63JV1-U6ryfYIgGxd2qZlhERo8vJrEU-MnipJQ_j5CLFBar58vUpkY44J8-BRPyY8Xo3PhS7805fbmtow_-yrcp_aVTbSvc2V9c7u1yvVlW9WuV1UeebslxW093CgRc9shDd4JAQ45-I6f_9jLi3KTzHdDOVI9GNhLqrbH5yzPh9TM5Q3VJ2ngQb65pb50CY0eVVWU1L-dMBgoXroNoDVIuJE0SMtdL2UCFcPPRMwyA7FYIybZKWc3EkjUlSFzVr32tNntdVlEqkJzJhSVBAJ-Eqqovtk_AkMdWSRfUcRaj3UsTZkETileEyCZTVmh1hSazhyUaZFSquFEGbYIdozCh2EeLZCfoZh72Mk78joqQhcCTHno_HOSWG-VFporZAvn7hk9HiVYzGfRo-YEl3x9JBcELdtkt-eVBGK85VQsN6YfAS68WH68vxIH2Y0rHnH4Qjkn2-vDRz2P002ufb7kEL8zV5RCP9P0Tj5A4DsbZ_K60RcL0O1vgz1U8q9TW047hudTMvOH_nREftK99hJtjfEYjvXUSVu59u7K1MNpNcXG_gORc3C3E-n09fH21Qp1TTMW1sH6Bel_-nLeqpbxboB_Dieh_mmpl2fMbtiGrEbVPSTZnqEHJZO4lKfy1kFYu26Q0_oJjIR8AW5D-SbJb1igiL0kMNdswMohFbA2-7oSnwMYhmEIAn22uRepce5EZxrC5O_vDhz8eoXsLGWRIy85Lk46L7eFRGdeobVEHILrZdbtA-9CKp77FCoo8KyJi52YjE0BetFY3VYexEYhNSv_98KL-Wj9_w7zQT20Jsig2bBRW03D5G4Zh0XkOn9Yst4ax3evuTtKYuZ7jNIfxfk2Y_KO_7mLOHsiorOjtslxvKebWROeMbthf5WmwwIteiLtaUMzbTrJHab3GQM0qNxN9SdIFnHOSZ2tKc0rxeVnlVruh6QfeMs7oq9_WaL1dNiZKTHVP63KDN3DaF1PSth1ErH_x3I_pU1UL4Ex38sx7q7rae2xA63s0S9zbF_g_zJVCc">