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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missed optimization for icmp ult <power-of-2> & mask check
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    ```llvm
define i1 @src(i32 %arg) {
  %a = icmp ult i32 %arg, C1
  %b = and i32 %arg, C2
  %c = icmp ne i32 %b, C2
  %r = and i1 %a, %c
  ret i1 %r
}
```
is equivalent to:
```llvm
define i1 @tgt(i32 %arg) {
  %r = icmp ult i32, %arg, C2
  ret i1 %r
}
```
where C1 is a power of 2, and C2 is a contiguous mask of bits starting 1 bit "below" C1.

For example:
```
If C1 is       00100000

then C2 can be 00010000
            or 00011000
            or 00011100, etc.

and can not be 00010100
            or 00111000, etc.
```

This is already optimized if C2 is also a power of 2, but not if it has more than one set bit: https://godbolt.org/z/3a6WbKabr

Alive2 proof: https://alive2.llvm.org/ce/z/3Se4bm
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyNU01zmzAU_DXiookHBPjjwCGx65lMp6d2pmdJPECJQK4k4ia_vk8Cx3Y8actgQLz1vt3VQ5j6tSLLdDq1fulJuiPpfQ2NGoCqjJIidVYStlY5o4SV3LaEbShZPUxIGl9Sku-okv2BjtrTS-iWbrMLpIhIPtQfQewCJM90QcQEFDcwe-bKIlVAhL-fMBb8XLLTK7LazQ8ny9NSOQq_RvXCNQyeekPy-w-4T6Lxrf9HNPYmmlnljfH_VnvswALGSlE2pwdzBEtNQyNxSGPLpoo0g1ftaEZHe-6eA0Yo76jz3Ho1tDQLa2zIBGhzxDuSLuaW8bo3lsJv3h803EYyLR-bWcl0pGmWhuOSxXcwBFGSD1QAQibMyff5wG6hmP21iNVgFLy8khqMhwaD8e9Nsk95sqnJNc-1sen6o0NrIU1tgdev1By86tUb4Mw1p6C1Mzf7IEYfpSAKI-44boHBTfMdSjQ4Pg43G8PHVGnn_cGFeNkez9bUwmi_MGE89m_4y_nyp_jKhb3Uda_VCzB6sMY0tyQ8VhdhaGciCSe271CIPqmrvN7kG5545TVUpHx4HJzfml7gcJNyR78p59Dl7Jd7ZQbaYHbvk0zybbR8Z5o7RvIvOEfLac5kB_I5Ga2uPlhTvhvFQpoeF_GDmm536OIJJH5Je2w6gsOHsliXy6SrJCtqxpZ5IZu0YMtSllktynXBhCibdVkkmuPwumAA53eAI40U-IwmElWxlLG0yBjOwiZlC9Egg1hlnPO8SFeAnzD0XOn3qBJbRUlibB0WtXLenYvcOdUOEPMK_Hz0nbEVWPVcg3vitlaDS6KCKjr4A5xxgKU">