[InstCombine] Missed fold: a non-power-of-two `sdiv exact` compare
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
### Reproducer
```llvm
define i1 @src(i64 %x) {
entry:
%q = sdiv exact i64 %x, 24
%r = icmp ugt i64 %q, 4611686018427387903
ret i1 %r
}
```
### Expected
This is equivalent to:
```llvm
define i1 @tgt(i64 %x) {
entry:
%r = icmp slt i64 %x, 0
ret i1 %r
}
```
Reason:
- `%q = sdiv exact %x, 24` implies `%x` is divisible by `24`
- `%q >u 4611686018427387903` means `%q` is negative
- for positive divisor `24`, `%q < 0` iff `%x < 0`
Alive2 verifies `src => tgt`. https://alive2.llvm.org/ce/z/TQeyKJ
### What LLVM does
With LLVM trunk:
```bash
opt -S -passes='instcombine'
```
the function is left unchanged (https://godbolt.org/z/9EWjrnhYz)
LLVM already handles power-of-two divisors like https://godbolt.org/z/qchnqf3f4:
```llvm
sdiv exact i64 %x, 8
```
### Missed case
The missed case is:
```text
icmp ugt (sdiv exact x, C), K
```
where:
- `C` is positive and not a power of two
- `K` is large enough that the comparison is true iff the quotient is negative
So the missing canonicalization is:
```llvm
icmp ugt (sdiv exact %x, C_nonpow2), K_high
-> icmp slt %x, 0
```
Contributor guide
Assessment
This issue has not been assessed yet.