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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missing fold for nested selects
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:instcombine,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    I hit this in https://github.com/dtcxzyw/llvm-opt-benchmark/pull/455#discussion_r1560862569, but I don't have any idea how to generalize this. Perhaps we need a binary decision tree for nested selects.

```
define i8 @src(i1 %c1, i1 %c2, i8 %a, i8 %b, i8 %c) {
   %not..i.i = xor i1 %c1, true
   %1814 = and i1 %c2, %not..i.i
   %brmerge.i.i = or i1 %c2, %c1
   %.mux.i.i = select i1 %1814, i8 %a, i8 %b
   %1815 = select i1 %brmerge.i.i, i8 %.mux.i.i, i8 %c
   ret i8 %1815
}

define i8 @tgt(i1 %c1, i1 %c2, i8 %a, i8 %b, i8 %c) {
   %.mux.i.i = select i1 %c2, i8 %a, i8 %c
 %1815 = select i1 %c1, i8 %b, i8 %.mux.i.i
   ret i8 %1815
}

; a: c2 && !c1
; b: c1
; c: !c2 && !c1
```

Alive2: https://alive2.llvm.org/ce/z/FzQfru

cc @nikic @goldsteinn @XChy

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysVE-PuzYQ_TTDZfRDMPwJOXDIboS0h0rtrbfK2BNwf2Ai2-xu8ukrs2RD2t1KlSpFaBjevHmeiZ9wTneGuYbiCYpjJGbfT7ZWXr5fL29RO6lL_YK99uh77VAb7L0_O8gOQA1Q02nfz20spxGoWauAmmF4HX9MZ_-jZSP7UdifQM15HgagJi8KoExpJ2fn9GT-sGlRJlVJRbkHesZ29viCajJAO4-9eGUU5oJascB-ekM_YceGrRj0lRdZMf7Kthdnh2-MhlmhwFYbYS-oWOrQBL1lxtNk0bDzrNDxwNK7GJIjJIf1WSbrb3lVfNKGUVcIeeKsBKp0ikCFTIPONaYlrkIs7mF7DyXQHmH39EGKGHJm8nGsY42QHfF9srgl9nbmLTit0nwBCqMeum6ItvjWjmw7_uS_09-qZLrFx-P8_gn-mMtaEDp_c7xHfcU_azcq7nW3Vtvp3Jgs-zUXCNeN7I7bBT1sxHf-f9zI90P4hu8m_NsBrJr-3vxzBP_h3JA9oYDsgJIQqAQqESi9bTF8bZevm4QMiQD6suLxj_7xPAz6lSmUPV5xseTjcKXjyXZAjWSg5grUNNffTnbekkgZVmP0T70E3TQo51kbE95-f-4vH7BI1ZnaZ3sRcZ3uUtonuywror6u9mVOp7xMs3xPqt3vKsWqTVWbJxWXQkS6poTyJE8p2WVFVsRZIsqsrLJdJapcigryhEehh0_BkXZu5rqq8iqNBtHy4Ba3IwoIyA7aOC-nsdWGgcKygWjUzrEKFqZHfRVeBzui4JC2XsytnTsHeTJo5929ldd-WLz0xTj_vHIWR_xFO6dNh6dpUF-4UDTbof4XY12Erq56ttOfLD1Qs5zLATXL0f4KAAD__wIOnEs">