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

    <tr>
        <th>Summary</th>
        <td>
            [SCCP][ConstantRange] Missed optimization due to approximation of `xor` operation on ConstantRange
        </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/7h2WSQ

### Description

```llvm
define i1 @src(i64 %a) {
entry:
  %cmp = icmp ugt i64 %a, 8192
  br i1 %cmp, label %then, label %else
then:
 %ctlz = call i64 @llvm.ctlz.i64(i64 %a, i1 true) ;[0, 50]
  %conv = xor i64 %ctlz, 63                        ;[13, 63]
  %cmp1 = icmp ult i64 %conv, 13
  ret i1 %cmp1
else:
  call void @dummy()
  ret i1 0
}
```

can be folded to:

```llvm
define i1 @tgt(i64 %a) {
entry:
  %cmp = icmp ugt i64 %a, 8192
  br i1 %cmp, label %then, label %else
then:
  ret i1 0
else:
  call void @dummy()
  ret i1 0
}
```

As `opt -debug --passes=ipsccp` outputs, the constant range of `%ctlz` is [0, 50], which is precise, but that of `%conv` is [0, 63] but not [13, 63], which is imprecise. After looking into `ConstantRange::binaryXor`, I found that we reuse KnownBit's xor operation here, but as this example shows, it's an over-approximation.

### Real-world motivation

This snippet of IR is derived from [jemalloc/src/large.c@large_palloc](https://github.com/jemalloc/jemalloc/blob/f96010b7fa8ce5f83802144bdebf2bb7a6679649/src/large.c#L21) (after inline and 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/511rf89EK

**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/eJzMVk2P4zYM_TXKhUhgy44_DjlkkgZY7BZtdwt0b4Vs0bF2ZcmQ5GQyv76gnJlJ0g_0UqADY2JJ1CP59EhZeK-OBnHD1k9svV-IKfTWbb7u-suisfKy2Wp1Qg6js7Zj2Rb6EEbPsi3jB8YPIq6utD4NK-uOjB9aZPzwwvih7PlvX35hyZ4l2-t_ns0P7NG3To1BWXNnUCTzQ3jzlMROGQSVAssT71rGK1XkwPhaMF4DK59mOzTBXSisOAIyaIcRWLYHRS_TMcD7xh1Uac1fbRsX8eMOWtOiQU3j0KO5m0Dtcd4Vl97c0d6gX6K7Vmg9u8pjHitaWakivwt9Ry6DmzBmkT2x9VNCs-uErfe3SVhzirDP1r0mQIBkW2TwN38zYJrNVg-Iw5je8KLfeCFXtCHNXq0dhndm0ivRRME7zzHbk1WS0pXTMFwYrxivHyCS6wGX-4eTvj3-VhhoEDqrJUoI9s3Nv1NHOIb_pzoeSPgPGdx6YEVixwBLic10hOVyFN6jZ9lejb5tR1YkYKcwTsFT7KFHaK3xQZgATpgjgu0I41VmRQLKw706-Q7OvWp7WhkdtsojzTVTgNCLcINAirpHiGqMpsYGeBDpLbAartAr2HYBHWhrvytzBGWCJfzdNezPFDXxmW0bZYS7fLUuut_BB-jsZOQc1RnB4eQRPhp7Nk8qMF76WFZ2RCeoF0GP7i0V4SH0ygM-i2HUCL6358jZdacwYE_olmIcnX1WQ0RY_XW_-4xCL8_WaQmDDeokHjvfr-TJGzWOGPn78Jk4kOjUCSV0zg7E1TcchNa2ZfwQW-FBC3fEVUudht5-H-dlorK6b9RHFfqpWbV2YPxwg3Pz2mjbMH7o6iJJk6bsRNXiuquyKuFpnjcSm443TSmKoqyLvP5TEDz7xNNYdrwS8ciU0VSewkj4KYNRjUhjxuvVa9b4Rq9o7AkpaQEO5dSihBM6T5zChw4udmK8dEjHjw59QAnKRP1ap47KCA1-auwY1CA08Ude34d0cB4RhPbUVx7IsbKxOlxvMLq81mnquqr-4eP9edLzCQMMCN-NPYOKgQE1rtaaTrlh1tqNRCgC9TLLy46jdWEyKlzm4hPmu1_NsAu5yWSd1WKBm7RMiqzkFc8X_abFkudVK5K8zdIiFbKWTSuFxCRt2qpqFmrDE54nKS_TgpdJvkKZlbhO23qddnm17lie4CCUfrumF8r7CTdlXdTFIrYvH-9_zg2eIS4yzulzwG1oz7KZjp5Epnzw7yhBBR0_HL7sdj-T6NZP90W53sOPynuU9zTICSFYuCuca9N4jrV7U5HWwB3mYnJ68w_SjnfD_LMcnf2GbWD8EFPy9FFCKf8RAAD__xfrpyE">