llvm / llvm/llvm-project

[InstCombine] Missed fold: a non-power-of-two `sdiv exact` compare

Open
#187,433 6 comments 0 reactions 1 assignee Claimed by @dtcxzyw View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.