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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Combine `x + (x | -x)` into `x & (x - 1)`
        </td>
    </tr>

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

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

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

<pre>
    This is listed in [Synthesizing an instruction selection rule library from semantic specifications](https://www.semanticscholar.org/paper/Synthesizing-an-instruction-selection-rule-library-Buchwald-Fried/bfc3571288304129df7978d9ebb09704e017bc6c) as an example of patterns that were synthesized by an SMT solved but were missing from both GCC and LLVM. This transformation may be particularly useful on x86-64, because `x & (x - 1)` can be performed by a single `blsr` instruction. 

32-bit example: ([godbolt](https://godbolt.org/z/qqTzfznhb), [alive](https://alive2.llvm.org/ce/z/NJU9vK))
```c
uint32_t src(uint32_t x, uint32_t y) { return x + (x | -x); }

uint32_t tgt(uint32_t x, uint32_t y) { return x & (x - 1); }
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyVVE1z2yAQ_TXShZEHoe-DDrE96bRJemnaawcQsmiRUADFH7--iyy7TpseOoMkYHef3r5dYLo51s-dtAiGktaJBskBBdn6y3FwnbDyJIcdogPsWmcm7qQekBVKnGdmUgLimKHmiFqje7D1dHCSIzsKLlvJqXe0QbYNSNk5N9oguQvIPYz9fr-6uFveaUXNSpsdWEY6CgPfWxIRHaIbEtGVRORJRAuJaD3xbk9VE90bKRrAYC1PsiImZZngNCZV0xZVUTaVYAxXBU4FjgvGcx6QClHrUxUH2o-Ql27RSJ0TZrDIddShvTAC2QsnkIodvf-Xp2dktXr1G9Pi1UtrvXKzJky7Dn3YbMC5QY-P355WaNbcGTrYVpt-1gj19IiYgH8aEGQCNdQRTVa0k0JgPZR5lKcB2YAPp7CPghwfUEByeMoDilAMKcAe4sDJ4wjjsReayNNRcxBT1ni_GzVXKMDbAN-d3wmJmHQXHaBe_g_QEzvdMK3ce7VcTEv9TvC8vDyf2tPQMc8KWEM8VfJVvBc9G8hKqdd-QeBigfn86Wv1-jBjVAvHHJ8HP68nObiEfHfIGihieV0e_F-vq6Ovb1CskRFuMiAn5LQ-KxcUGxQdPH4CO8X2VoprvNu5_wN_W5Y3yJcEQlHHeU7iFEYVNnXSVElFQyedEjXo9REKtNE9k4NXDS3TS93_Yj-X1Ol_9UU4GVX_UTXpuomtuO5h4dVfPtFo9A84XbCEPp6EhUlWZEkcdnXGypKnmOWJiJuibXNMG1xlKc_SltM8CRVlQlnPPyBkBk3u9OhkL0_LXUDI3BBXq29EvuR5tfkTJJroNtIbs20oa4IJwRUmcQnvapXSihYJxm3MeVXENEgxXCtSXRsqNPWcFpt2Foz-orO_jRSO6m4Qs-Qen06u06Z-6AX9KYdwVqCe0_8F9h2gVg">