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

    <tr>
        <th>Summary</th>
        <td>
            Reassociate pass serializes vector comparison results
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:optimizations
      </td>
    </tr>

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

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

<pre>
    https://godbolt.org/z/Kh7667Yxo

Pulled out of Issue #63946

While the scalar code for an accumulative or chain of comparison results stays as a binary tree:
```ll
define i1 @scalar(i32 %a, i32 %b0, i32 %b1, i32 %b2, i32 %b3, i32 %b4, i32 %b5, i32 %b6, i32 %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq i32 %b0, %a
  %cmp1 = icmp eq i32 %b1, %a
  %cmp2 = icmp eq i32 %b2, %a
 %cmp3 = icmp eq i32 %b3, %a
  %cmp4 = icmp eq i32 %b4, %a
  %cmp5 = icmp eq i32 %b5, %a
  %cmp6 = icmp eq i32 %b6, %a
  %cmp7 = icmp eq i32 %b7, %a
  %or01 = or i1 %cmp0, %cmp1
  %or23 = or i1 %cmp2, %cmp3
 %or45 = or i1 %cmp4, %cmp5
  %or67 = or i1 %cmp6, %cmp7
  %or0123 = or i1 %or01, %or23
  %or4567 = or i1 %or45, %or67
  %or01234567 = or i1 %or0123, %or4567
  ret i1 %or01234567
}
```

The vector code equivalent gets linearised, resulting a much deeper serial chain, affecting IPC and makes it more likely we will hit value tracking recursion depth limits:
```ll
define <8 x i1> @vector(<8 x i32> %a, <8 x i32> %b0, <8 x i32> %b1, <8 x i32> %b2, <8 x i32> %b3, <8 x i32> %b4, <8 x i32> %b5, <8 x i32> %b6, <8 x i32> %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq <8 x i32> %b0, %a
  %cmp1 = icmp eq <8 x i32> %b1, %a
  %cmp2 = icmp eq <8 x i32> %b2, %a
  %cmp3 = icmp eq <8 x i32> %b3, %a
  %cmp4 = icmp eq <8 x i32> %b4, %a
  %cmp5 = icmp eq <8 x i32> %b5, %a
  %cmp6 = icmp eq <8 x i32> %b6, %a
  %cmp7 = icmp eq <8 x i32> %b7, %a
  %or01 = or <8 x i1> %cmp0, %cmp1
  %or23 = or <8 x i1> %cmp2, %cmp3
  %or45 = or <8 x i1> %cmp4, %cmp5
  %or67 = or <8 x i1> %cmp6, %cmp7
  %or0123 = or <8 x i1> %or01, %or23
  %or4567 = or <8 x i1> %or45, %or67
  %or01234567 = or <8 x i1> %or0123, %or4567
  ret <8 x i1> %or01234567
}
```
->
```ll
define <8 x i1> @vector(<8 x i32> %a, <8 x i32> %b0, <8 x i32> %b1, <8 x i32> %b2, <8 x i32> %b3, <8 x i32> %b4, <8 x i32> %b5, <8 x i32> %b6, <8 x i32> %b7) local_unnamed_addr {
 %cmp0 = icmp eq <8 x i32> %b0, %a
  %cmp1 = icmp eq <8 x i32> %b1, %a
 %cmp2 = icmp eq <8 x i32> %b2, %a
  %cmp3 = icmp eq <8 x i32> %b3, %a
 %cmp4 = icmp eq <8 x i32> %b4, %a
  %cmp5 = icmp eq <8 x i32> %b5, %a
 %cmp6 = icmp eq <8 x i32> %b6, %a
  %cmp7 = icmp eq <8 x i32> %b7, %a
 %or67 = or <8 x i1> %cmp1, %cmp0
  %or45 = or <8 x i1> %or67, %cmp2
 %or4567 = or <8 x i1> %or45, %cmp3
  %or23 = or <8 x i1> %or4567, %cmp4
  %or01 = or <8 x i1> %or23, %cmp5
  %or0123 = or <8 x i1> %or01, %cmp6
  %or01234567 = or <8 x i1> %or0123, %cmp7
  ret <8 x i1> %or01234567
}
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsl8Fu2zgQQL-GvgwSSCRF2Qcd0qQGil6K7gKLPRU0Nba4oUSXpNImX7-Q5MayTUdCschpgSAJR2-oIaV5EKX3etcgFiT7QLKHhWxDZV3x9fMfurbNYmPL56IKYe8JuyN0Teh6Z8uNNeHWuh2h6xdC15-rXIj875-WJA8kuRt-f2mNwRJsG8Bu4ZP3LQKhTLAVF2Pur0obhFAheCWNdKBsibC1DmQDUqm2bo0M-gnBOlCV1E03n7L1XjrtbQMOfWuCBx_kswfpQcJGN9I9Q3CIXdnD3UQy_BgzBErc6gZBp0B4Mtyb0KVmFAjNJKH3cPh_k4wH6XhAxwM2HvDxIBsPxHiQE7oCY5U039qmkTWW32RZOiD5h6FKbIJ7fl0EdEmq3idA2ANoVe8Bv5_W2Rd_AqdROI3DNArTM3hgWZRl8Yl5FOZxOIvCWRwWUVjE4TwK5xHYumTYOev6l2TY-APYbesJS9kFS48sO-6bdTy7QPkRzU6mFfkFK45sflbueRFd7EB3FZ7QPDufu4u90uJy7lhGF3_N6YBfWQ7DCXS8RvKHs44c6-DPCuEJVbAHEeD3Vj9Jg02AHQYPRjfYNT6W3W2H3tfNDiTUraqgRNyjA49OSzPoouPkdouq5z59uQfZlFDLR_SgA9TWIRj9iOYZfiD80MZApQM8SdMiBCfVY5fnULXOa9tAiftQgdG1Dn7SLoTdL-En6JSwj51nhqURuvx1gdH-ysE4F9FDT1-E03iYxsMsHubxcBYPi3j4PzHYtXVPuOzavkxY7dq-XaSxibRZqru27xPSu_ZcJvR37blNiDD6XN9U4umbPVeOkayIJs89GcmaYcxI1ix3nufNtehl3nyfxu75hlnj-LRjbwj7-L-wJoT1voZ6V0G9q5_eVU_TvZ8eez-Z6Zm-bV-z6OlH3KzGv5DaW5rp-_c1j88Ub--kKzKcqbXejL-tp7FMf09Oi7Jg5Yqt5AKLVKxoxgXlYlEVS5oKViY823KpEpkykas8Z3micuSUrxa6oAllyZImacZ5Im5XJfKULjOGG6FEmROeYC21uTXmqe7OrAvdHUULwZc8WRi5QeP7sy-lHUHYnd0HXesXGbRtPKG0OxW7ort4s2l3nvDEaB_8ccKgg8HiK0rvrdIyIOyl94dvUP2C_vhBe35oXbTOnB-vdajaza2yNaHrvqThz83e2X9QBULX_Qo8oet-Ef8GAAD__z-7EC8">