llvm / llvm/llvm-project

[InstCombine] Missed optimization: fold compare-only srem(x, C) vs x to signed range checks

Open
#215,060 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.