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

    <tr>
        <th>Summary</th>
        <td>
            Missed optimization when known bits would permit transforming an `and` into subtruction
        </td>
    </tr>

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

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

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

<pre>
    Rust in which we spotted this originally: https://godbolt.org/z/8xM3P9xP5

Take this IR:
```llvm
define noundef i8 @f(i8 noundef %0) unnamed_addr {
  ; check if two highest bits are set
  %2 = lshr i8 %0, 6
  %3 = icmp eq i8 %2, 3
  br i1 %3, label %4, label %7

4:                                                ; preds = %1
  ; if so, get the value of the lower 6 bits + 1
  %5 = and i8 %0, 63
  %6 = add i8 %5, 1
  br label %8

7:                                                ; preds = %1
  br label %8

8:                                                ; preds = %7, %4
  %9 = phi i8 [ %6, %4 ], [ -1, %7 ]
  ret i8 %9
}
```
Today `--passes=instcombine` turns it into

```llvm
define noundef i8 @f(i8 noundef %0) unnamed_addr {
  %2 = icmp ugt i8 %0, -65
  br i1 %2, label %3, label %6

3:
  %4 = and i8 %0, 63 ; 😢
  %5 = add nuw nsw i8 %4, 1
  br label %7

6:
  br label %7

7:
  %8 = phi i8 [ %5, %3 ], [ -1, %6 ]
  ret i8 %8
}
```

However the `and` and `add` could be combined too -- they are used in the branch where `%0 > -65` (two highest bits in `%0` are set), which means that `and i8 %0, 63` (`& 0b111111`) could be replaced with `add i8, %0, -192` (`- 0b11000000`) and then trivially folded with the other `add`. That is, the resulting IR should look like this (https://alive2.llvm.org/ce/z/Go8nxD):

```llvm
define noundef i8 @tgt(i8 noundef %0) unnamed_addr {
  %2 = icmp ugt i8 %0, -65
  br i1 %2, label %3, label %6

3:
  %5 = add nuw nsw i8 %0, -191 ; 🌸
  br label %7

6:
  br label %7

7:
  %8 = phi i8 [ %5, %3 ], [ -1, %6 ]
  ret i8 %8
}
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzMVk9v47YT_TT0ZeCAoqx_Bx3s9c-_LtAFFosFeiwocWSxoUmVpKxkP31BSkri1AVaIIcVAsTkkI_zZt4MyZ2TZ41Yk-xAsuOGj743tv6Nd53CX_nwKPWmMeK5_jY6D1LD1Mu2hwnBDcZ7FOB76cBYeZaaK_VM0j303g-OpHvCToSdzkY0RvkHY8-EnX4QdiqfvqRfq6evGaF7Qvff-SPOMJ-_hV10T3I6_yl1vRC6F9hJjaDNqAV2IEsgO9oRVsryZZKwjBJWwag1v6D4nQthgRQHQvcAJD1A22P7CLIDPxno5blH56GR3gG3CA79vJJlDEh6BOV6G0-KuJ8gX81pNMv2MgD-uaxgYUUaVzQWZBLXhTnFG1RhtLsZFTPzXYjWf_wClcGicNENwrLkhaHswJlwzhk9-B7hytWIYLo4UGZCC_lMmbADJCujLEJxLW74pqs5n81iNWfBnKxkXziVM6fi4zjdQS8_Ar0IBGJOFoZVtAy9jAyzQ2S9LgKSHePv7ADbZJkt4mzYbtEvcamCi8XxrX6Duo3gz0Byut0O3Dl0JD1K7XxrLo3USHIKfrTagQz15c3M8-MrYNV1FO549m9zvc2zW-2yG7XeKjmfPUznUoUlRvcEFCNPTpRUJ1KVZM_eCU4I0OME2k3Lvt19ZS3Vkq8n3rEVb7wp72QzW_KW3s1mfieb5d1sErr_xUx4RRtriuSUaxFyGMiHkYij1oxKQIOwZFmANwa227DpOfab0aEI_TSgNJbr0FR7tBEyRBBI-r-Yl5wCYeXfepbU68p4-tLBWBUYzT36glw78D33i5vvqnsGjiA50CaJXxxWr_5bHBRvUcAkfb8QBFkucZvFk1TsFWwboWj8FrBwtO9Rg7fyKsMlAZ1RYgUNETC-R_savwf4HtyWLuAHu0U3Ki_1GT5_A9dH75Qxj6DkencQVt7eO1zJK7KHUEDL3dPicgH935T66RiiNV83_7Le_Nn_LBX3TxW0ZiR5W3vlJ3Iof9qq2og6FVVa8Q3WSZElNN1labrp666t2mzXllna0i4rRVclBUeWiVKIrm26jawZZRnNWZHsWJmxh7JjeV7QrmtpnjQ7JDuKFy7Viwg20rkR62SX07LYRLouPn0Y0zhBtBLGwkvI1mHTthnPjuyoks67VxgvvcL6i3Shis3g5UX-4F6a8D5CDY_aTHqu0ylqdUB7kR685dp1xl6Ckrl-0z5C5wc3Nt6ObcDZjFbV795R0vdj89CaC2GnKNP533aw5g9sPWGn6L8j7LQQvNbsrwAAAP__Qd6p6A">