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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missed optimisation for checking divisibiliy of square numbers by power of 2
        </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>
    $x^2 \mid 2^k \Leftrightarrow x \mid 2^{ \lceil k/2 \rceil }$

```c
#include <stdbool.h>
#include <stdint.h>

#define u32 uint32_t

bool src(u32 x, u32 y) { return (x * x) % (1 << y) == 0; }
bool tgt(u32 x, u32 y) { return x % (1 << ((y + 1) / 2)) == 0; }
```

[godbolt,](https://godbolt.org/z/WK1oW6Mor), [alive](https://alive2.llvm.org/ce/z/q9eGMx)
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyEk1tvqzoQhX_N8GI1gjHm8sBDEsrRUU-f-3jExYTZMTi1TZv012-ZsNPsS7WlKGhYa77xLKC2lg6TlAWIHYgyqGc3aFM8jbI-0hQ0ursUgPEZxCMyEPuROoYgHo---E_2ztBhcLUx-p2d7w2Q7nypWkmKHQGrpd0sJaQlYAxhCeF2_U_C669da-Q0tWruJAO-t65rtFabAfjjFzpN7l7-YepkT5NkM0c20-Q4_u_uHZ7KrGkBM285A-4X7wUwZ34DI91sJgaYnRng1jtyBij8nciPBr5f3bwEXrIQ-G7Z75PvDu5v_PNvTMAMMLswwB2LrkMrhoD5l7NuEf4UgdgddNdo5QD3IErAbHDuZIFvASvAalU32hwAqw_A6uUp0i_JszbLsD0DsasVvck_dS8CbpR6G1dCK1fMay7_efZxBV3Bu5zndSCLKA15EqdCxMFQiFyGeV-HGfZZmnRNgl3UZKKPuUh42-cBFRgijxDTkKMQ8aaXaVPnsgvTLMUk4hCHcqxJ3Q4QkLWzLNIkxihQdSOVXV5sRO8AvtUnRyN91I70ZAHRp3ITabKu1WNDk7xJI1kru4f7Pq-JMjCFb3to5oOFOFRknf08hyOnlm_q38m6_coUJXtecOyKswuO9dqwdpDtkaYD6-iNLDWk6MJ0z-zrXBvJpnlspLGsubCTfpfGSxjMRhW_PE1yw9xsWj0CVstW18vDyehvsnWA1ZKQBayWkL4HAAD__9iMKS8">