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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missed optimization: simplify demanded bits on multi-use instructions
        </td>
    </tr>

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

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

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

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/8qHKuR

### Motivating example

```llvm
define void @src(i1 %c, i64 %a, i64 %b) #0 {
entry:
  %and1 = and i64 %a, 24 ; mask 0001 1000
  %and2 = and i64 %b, 25 ; mask 0001 1001
  %s = select i1 %c, i64 %and1, i64 %and2
 %ret1 = and i64 %s, 8    ; demanded bits: 0000 1000
  %ret2 = and i64 %s, 16   ; demanded bits: 0001 0000
  call void @use(i64 %ret1)
  call void @use(i64 %ret2)
  ret void
}
```

can be simplified to:

```llvm
define void @tgt(i1 %c, i64 %a, i64 %b) #0 {
entry:
  %s = select i1 %c, i64 %a, i64 %b
  %ret1 = and i64 %s, 8
  %ret2 = and i64 %s, 16
  call void @use(i64 %ret1)
  call void @use(i64 %ret2)
  ret void
}
```

Until now, InstCombine doesn't support simplifying multi-use instructions based on demanded bits and only computes their KnownBits. However, that's common in the scenarios like doing bitwise operations in loops.

### Real-world motivation

This snippet of IR is derived from [qemu/hw/virtio/vhost-shadow-virtqueue.c@vhost_svq_valid_features](https://github.com/qemu/qemu/blob/7425b6277f12e82952cede1f531bfc689bf77fb1/hw/virtio/vhost-shadow-virtqueue.c#L27) (after O3 pipeline).
The example above is a reduced version. If you're interested in the original suboptimal IR and optimal IR, see also:https://godbolt.org/z/6rsvv4q61

**Let me know if you can confirm that it's an optimization opportunity, thanks.**
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMVkGPozgT_TXOpZQITAhwyKF7omhaM6NPan0r7a1lcJHUtrFplyGb-fUrk6Q36Z6Z7cMeVkIJxlWPZ79XZRQz7SziWuT3It_M1BD2zq9__7Q_zmqnj-s7QyNK6L1zrcjuYB9CzyK7E3Ir5FZNswtjxm7h_E7IbYNCbr8LuS1fPn8ZHkWyEcnd-Vdmpwu-uUCjCmR3gH-qrjd4E7dKTleEPT3S2JJFGB1pEMuEfSNkSSkImTdCfgJaLeO9urqvhaxAyCwBUdyfUNAGf4zcpxFMGVanILINKKtvUOQSRHYPneJnSJIkhTRJkttE-TaxnhLz94npVSJPWYwGmwA_WILV6e1QnpOFzD2Gd2w5RpcAML1WY6esRg01hShTpJC85e4xvOM-waSrX8CkE9YFplHGvOoxMEY9TkiRpJDVhwLlVaDHMMWdTVBs3rjh2iKNslAjMHW9oZZQQ3Cvwn7URWEX_iUX_ZOmN4A3OvxEzo-J9d_Q4jcbyIB1h0jqwXL45Lo67rN2yFbIIgAPfe98uOh1jIXfDSbQfGAEshz80ARylqFWjBqcvbXgtHhnzREa1_VDQIawR_LwxbqDvafAC_jsDjiijyzCXgUhC47RnbNANoYDN2iVJ8dg6DnyizxqCgdiBNejVycOZME41_Pix93rEZWZH5w3GrpzI3P2OvT_e2JgS32PAVwLD49ADBo9jaih9a4Dkd-_YDcIud0fhNyO5AO5eLN3HOa8V9od5vHpy4ADLhqxTKapJx5fnkZlSD-1qMLgkUW-EbK87cs7CvuhXjSuE3J7ftH5rzauFnJbLGVer2RRtKnEUla5bFBj2uZZWrfNqqzqtijaOv04Q5l9lcWpXErVBvTwvwx66tGQRSGrxWVz8NL0QdVuxLg3CjzqoUENI3omZxfw0MLRDUIWPjokoEcOqC9SOk87ssoAD7XrA3XKxG2ebPI6jFZgRFCGY3d4s0VO186E87EVT6yV53FcvqzSW9nj9RUDdAjP1h2AJmIQW1DjbEu-m_wGdLKcsicG9H3yBbjJ-oOlcDxb0z7z4gQ70-tMV1mlZrhOiyTPq6Soqtl-nSdN3iyxLlcyr3QjtVZlWsm8bFpV562c0VomcpmkaZnmaZaUi6rQuWraNK8zXWKGYplgp8i8ns0zYh5wXZR5tZoZVaPh6dCX0uIBpkkhZfwG8OuYM6-HHYtlYogD_40SKJjpa-Gq0kW-gW_EU-FeLT2eG5eKf1POzv6k_meDN-tfeHlq5qe_ee_dH9gEIbcTe46ujqv7KwAA__-dEaD-">