[InstCombine] Missed optimization: fold compare-only srem(x, C) vs x to signed range checks
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
I found a missed InstCombine fold for a one-use signed remainder that is compared with its own dividend.
A reduced example is:
```llvm
define i1 @src(i64 %x) {
%rem = srem i64 %x, 250
%cmp = icmp ne i64 %rem, %x
ret i1 %cmp
}
define i1 @tgt(i64 %x) {
%offset = add i64 %x, -250
%cmp = icmp ult i64 %offset, -499
ret i1 %cmp
}
```
For a strictly positive constant `C`, the remainder is equal to the dividend exactly when the dividend is already in the signed remainder range:
```text
(srem X, C) == X iff -C < X < C
(srem X, C) != X iff X <= -C or X >= C
```
The range and its complement can each be represented by a single offset unsigned comparison. Suggested folds are:
```text
icmp eq (srem X, C), X
-> icmp ult (add X, C - 1), 2*C - 1
icmp ne (srem X, C), X
-> icmp ult (add X, -C), -(2*C - 1)
```
The arithmetic constants are interpreted at the original integer bit width. The `ne` form is equivalently expressible as `icmp uge (add X, C - 1), 2*C - 1`, and the source `icmp` operands may be swapped.
This is profitable when the `srem` has one use, because replacing the comparison also removes the remainder operation. If the `srem` has other users, it remains live and the additional range check may regress codegen. A conservative first implementation could therefore be limited to `eq`/`ne`, strictly positive constant divisors, a one-use `srem`, and a comparison with the same SSA value used as the dividend.
In the linked x86-64 comparison, `llc` emits 11 instructions for the current form and 4 for the range-check form. `llvm-mca` reports modeled block throughputs of 3.0 and 1.0, respectively.
AliveProof: https://alive2.llvm.org/ce/z/mYxhRy
Compiler Explorer sample & perf: https://compiler-explorer.com/z/hfn4do6nd
RealWorld Usage: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/faiss/optimized/test_merge.ll#L4169-L4175
Contributor guide
Research direction
Start in InstCombine with the reduced srem/icmp example and review the stated Alive2 proof and positive-divisor constraints. Use llc to compare the generated instruction sequences and llvm-mca to check the reported throughput; done means the conservative eq/ne fold is implemented without changing cases with additional srem users.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100