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

    <tr>
        <th>Summary</th>
        <td>
            Remove common `add`s when `icmp eq`ing two `select`s [InstCombine]
        </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>
    Take the following IR, extracted from part of how Rust generates `==` on enums:

```llvm
define noundef i64 @get_discr(i8 noundef %x) unnamed_addr {
start:
  %_4 = icmp ule i8 %x, 1
 %small = select i1 %_4, i8 3, i8 %x
  %_5 = sub i8 %small, 2
  %_0 = zext i8 %_5 to i64
  ret i64 %_0
}

define noundef zeroext i1 @discr_eq(i8 noundef %a, i8 noundef %b) unnamed_addr {
start:
  %_3 = call noundef i64 @get_discr(i8 noundef %a)
  %_4 = call noundef i64 @get_discr(i8 noundef %b)
  %_0 = icmp eq i64 %_3, %_4
  ret i1 %_0
}
```

Today, when optimizing `get_discr` InstCombine will change the <https://llvm.godbolt.org/z/6Eq87h6h7>
```c
(x <= 1 ? 3 : x) - 2
```
to
```c
(x <= 1 ? 1 : x - 2)
```
which is reasonable on its own.

The problem, though, is that that makes things worse later in `discr_eq`.

It's unable to undo that transformation after the inlining, and thus ends up as <https://llvm.godbolt.org/z/31MdEhfcv>
```llvm
define noundef zeroext i1 @discr_eq(i8 noundef %a, i8 noundef %b) unnamed_addr #0 {
  %0 = add i8 %a, -2
  %_4.inv.i = icmp ugt i8 %a, 1
  %_5.i = select i1 %_4.inv.i, i8 %0, i8 1
  %1 = add i8 %b, -2
  %_4.inv.i1 = icmp ugt i8 %b, 1
  %_5.i2 = select i1 %_4.inv.i1, i8 %1, i8 1
  %_0 = icmp eq i8 %_5.i, %_5.i2
  ret i1 %_0
}
```

But there's no reason to do those `add`s any more -- they could be pulled outside the `select`s where they'd cancel out.

Phrased as C, it's doing
```c
(x <= 1 ? 1 : x - 2) == (y <= 1 ? 1 : y - 2)
```
when instead it could be doing
```c
(x <= 1 ? 3 : x) == (y <= 1 ? 3 : y)
```

So InstCombine should be able to detect this case, and rewrite it back to
```llvm
define noundef zeroext i1 @discr_eq(i8 noundef %a, i8 noundef %b) unnamed_addr #0 {
  %_4.inv.i = icmp ugt i8 %a, 1
 %_5.i = select i1 %_4.inv.i, i8 %a, i8 3
  %_4.inv.i1 = icmp ugt i8 %b, 1
 %_5.i2 = select i1 %_4.inv.i1, i8 %b, i8 3
  %_0 = icmp eq i8 %_5.i, %_5.i2
  ret i1 %_0
}
```
Alive2 proof of correctness for that: <https://alive2.llvm.org/ce/z/AWCmDs>


</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8Vl1v4ygU_TXk5aoRxo7jPOQhbSfSPKy0mh1pHysM1zY7GDKAm6a_fgV2PiZttak0Wslqkvrey-FwzrG596o1iGuyuCeLxxkfQmfd2gsbQi_6WW3lYf2d_0AIHUJjtbZ7ZVr4-o2wB8CX4LgIKKFxtocddwFsA53dw7fBB2jRoOMBPZCSkvwxXiUFawDN0HuSbwhNV0nHS-vnntCNxEYZBGMHI7EBVRZACtpieJLKC0dYparTXcIWL4StYDCG9yifuJQOyPKe0I0P3IVxFYh1TwWQ_BGU6HcwaARVTd0PkMUawha-51qnKo8aRQCVjZ2xSFWQT5-p7zh2MTYM9XQnDYmF7FRCU8krvoSp5mkBwcatpRKHYdxmLI2MLB9Haq6oeEVn04wsMpLYeMKfbwjhE8qLf9W3cpQnpCLScPMBcMJWVyR_bkB9OYCeTwl_nmhJzI9HcWIsuybsKKSRvO9W8kNs23dowO6C6tVrlC8pL7CUFL4aHx5sX0eq90prEB037Sh6kj90IeySWtmWsG0U6by1srY6zK1rCdu-ErYtv_ysll3ZLUn-5RKKiD9Y9RIHxX1lQPItRJY3kIR7l2RyCT3Y_x6QjQNSd-LucsC-U6ID5cEh99bwWmN0nQoe7N7MJ3Y6hJ2ztcY-chQ6O7RdEo6H0PEw_un5D4y_lWk97K3zCJoHdKBMpPEkwZJOY78GwpYehnHVYGEw0k4DHTe-sa7nQVkDvIlzIsfKaGWUaePq3EgI3eABjfQw7ID7m88gz_6QX7pGPF-dwfu58lvNxHI6OSqJeNQwl3Kyexpyd86DYq7M81xd5FEbLkuzc7hMVVd5NPaf04hOX0-N2RWC-n0E2XsQ6jcQ2McYsjOI7BrEtZer47yjmePom_18P0RRosOkMGMneUeRJYlZj1GTXEpSUg_cHKC3DuHuLrYdQNhBS6gRdoPWKMEOwSs52byk4-5S6z6ukpoIW0oQ3AjUsX4S-Z-d4x5l1OZD2vMoemmjiD_pXRifjEBYdXiv7vCRx9GAMj4gl6DCeXM3grhIoA8BjDWHt4sTuvnL_hKbvjuuf_S9xBDFEjrlQXCPR3M73DsVMGKuufgBv6bd_2_V27z4CSvy07vC57z2KavVbxb5fVbbaPWMLD4cbBNf6IR1DkUw6D001qUwj8J4E8s8Nc5TOo-pLHCK5s3fD_2jn3KZbmZynctVvuIzXGfLIl-URVVUs27NK2SCIRVY8Jo3slhJulrmq6KoeFPl2UytGWULWlBG87ygyzlfiZItm0aygjZyuSAFxZ4rfYIxU94PuM7ygrJipnmN2qcXXsYM7iHdJYzF91-3jk139dB6UlCtfPDnMUEFjetv2NtnBGH73prLuEmGJCWdTiB-My2Evb3KFrK4vzBOXHVwev0rka0K3VDPhe2nh930cbdz9p84iG0TbE_YdtrX85r9GwAA__-z22L_">