[SCEV] Missed fold for descending loop IV range check `n - 1 - i >= 0`
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
This is a reduced probe for a source pattern seen in SPEC CPU2017 `538.imagick_r`, `magick/quantize.c:FloydSteinbergDither`. The original code scans a row with `0 <= x < image->columns`; on odd serpentine rows it computes `u = image->columns - 1 - x` and uses `u` as a row-local index. The reduced test below turns the scalar range fact into an explicit check so that the missed optimization is observable.
```c
int descending_iv_bound(long n, long *out) {
int bad = 0;
for (long i = 0; i < n; i++) {
long u = n - 1 - i;
if (u < 0 || u >= n)
bad = 1;
// preserved for side effect
out[i] = u;
}
return bad;
}
```
For every executed iteration, `0 <= i < n`, so `u = n - 1 - i` is in [0, n). The function should therefore return 0.
Current behavior (https://godbolt.org/z/GMsb7GfaP):
`opt -passes=indvars` keeps the lower-bound comparison and bad-flag select, which could be optimized away:
```llvm ir
%cmp = icmp sgt i64 %u, -1
%bad.next = select i1 %cmp, i32 %bad, i32 1
ret i32 %bad.lcssa
```
But SCEV already has enough structural information to derive the endpoint range:
```shell
# opt -disable-output -passes='print'
# variable i
%i.012 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
--> {0,+,1}<%for.body> U: [0,9223372036854775807) S: [0,9223372036854775807) Exits: (-1 + %n) LoopDispositions: { %for.body: Computable }
# variable u
%sub1 = add nsw i64 %n, %0
--> {(-1 + %n),+,-1}<%for.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %for.body: Computable }
Loop %for.body: backedge-taken count is (-1 + %n)
```
It also explicitly reports the exit value of `%u` as 0. This should be enough for optimizing the `u < 0` check away and making the return a constant 0.
Contributor guide
Research direction
Start by compiling the reduced C probe and comparing opt -passes=indvars output with the scalar-evolution report shown in the issue. Trace the SCEV handling of the descending induction variable and its loop exit value; done means the lower-bound check and bad-flag select are removed and the function returns constant 0.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100