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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missing algebraic fold for handwritten bitwise AND
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:instcombine,
            llvm:transforms
      </td>
    </tr>

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

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

<pre>
    There are a few missing folds opportunities when attempting to simplify a manual bitwise AND, as Clang emits suboptimal codegen for the following snippet:
```c
uint64_t and(uint64_t a, uint64_t b) {
    uint64_t c = 0;
 for (int i = 0; i < 64; i++) {
        if (((a >> i) & 1) && ((b >> i) & 1)) {
            c |= (uint64_t)1 << i;
        }
    }
    return c;
}
```
We might start from folding: `(((1 << %mask) & %a) == 0) | ((1 << %mask) & %b) == 0)) ? 0 : (1 << %mask)` into `(1 << %mask) & %a & %b`. Same may be done for `(2 << %mask)`. With these folds in place, Reassociate + GVN should be able to unleash the and between `a` and `b`.

Alive2: https://alive2.llvm.org/ce/z/ehkjGQ.
Godbolt: https://godbolt.org/z/h3TMdcxG3.

Found by @purplesyringa.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyEVEGP2zgP_TX0hWigyLE9OfjgSerBd2iBb7fYHheyzdhqZcmQ6Mlmf_1CtpsM2sGuoCCUyMf3KNFSIejeEpWQPUN2TtTMg_Olsuysdhev-4GYXdK47lZ-GcgTqvjDC11x1CFo2-PFmS6gmybnebaaNQW8DmRRMdM4cYxhh0GPk9GXGyoclZ2VwUbzVQfC6vMZ5AlVwJNRtkcaNQcMc-Mm1qMy2LqOerJ4cR55oMho3DXmDVZPEzGkFYgKcrHOFkQ1a8v54U9GZTuQT49lpLqvGpBHhOIZRIWIj_0WIT2jgHTxRF6QT9oy6rtjMU-YHxYb5PMy32aLQ18icp0KIf0I6ccYfUSQOe43I9prTPNuzK9542gRilOU86Y-kMd91BWl6U3-NqA4b6uH5Ylnb7FdI9f9-zGCqL4SjrofGAMrz3jxblzuW9se0gpj0I_q7rQgs1GF7z_0g8zUYqfn9eiWWk74n6jmJ9S6rFHgQv0uFnKB2rLblP2bpgdNLnb4uxoJR3XDhrBzltY7X5LId2l2-FXzENsx0PYJaIuTUS3FDvuNVAiu1YoJQT7jyx-fMQxuNl1kUI2h-E3M1pAKS5bYp9gQX4lsJFaxlLgHuVgkxpsRVWX0K8l4AAPzFGLjyxpkrZb9nTGv4875HmQdddR_g6xp-P7t5f8R_-K6xhn-Fd2vjg0ZQUP65VPX_vWSbry1m6O-G8JBTLOfDIWb17ZXu6Qr0-6YHlVC5b445Nk-z495MpSplJ2k7nAQmWoLlT11aZ43-zQXRAVRnuhSCpmJTOSiSPdpvpNFJ1QhsuKplSK7tHAQNCpt7mUlOoSZyn36lGciMaohE5a3S8oYAmmlbeDWjY22BFKCPD1c7JUNF-fHED3ZOfFl9Hxo5j7AQRgdODyYWLNZ3sX_2cCnLWN2xk_bq6dMT41Xul0uf2mXQdnu6jUz2bdvWzJ7U_503pqHudm1bgRZL_LWvw-Td9-oZZD1UmkAWW_FvpbynwAAAP__t7Cjwg">