[opt] Missed optimization: `loop-deletion` preserving ScalarEvolution leaves a stale, less precise SCEV; then `loop-reduce` missed its optimization
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`loop-deletion` preserves ScalarEvolution analysis. However the ScalarEvolution analysis that it preserves is less precise than what it could be (i.e., compared to fresh recomputation). The following reproducer shows the missed optimization case (after and `loop-reduce`), comparing the analysis to a freshly recomputed one.
test.ll
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
declare void @sideeffect(i32)
define void @pr27570(i32 %val, i1 %c1) {
entry:
br label %for.cond
for.cond: ; preds = %for.inc11, %entry
%f.0 = phi i32 [ 20, %entry ], [ 0, %for.inc11 ]
br label %for.body6
for.body6: ; preds = %for.body6, %for.cond
%h.039 = phi i32 [ 1, %for.cond ], [ %inc, %for.body6 ]
%g.138 = phi i32 [ 0, %for.cond ], [ %and, %for.body6 ]
%cmp = icmp eq i32 %val, -1
%conv7 = zext i1 %cmp to i32
%add.i = add nsw i32 %conv7, %h.039
%sext = shl i32 %add.i, 24
%conv8 = ashr exact i32 %sext, 24
%cmp9 = icmp eq i32 %conv8, %f.0
%conv10 = zext i1 %cmp9 to i32
%and = add i32 %conv10, %g.138
%inc = add i32 %h.039, 1
%exitcond = icmp eq i32 %inc, 20000
br i1 %exitcond, label %for.inc11, label %for.body6
for.inc11: ; preds = %for.body6
%and.lcssa = phi i32 [ %and, %for.body6 ]
call void @sideeffect(i32 %and.lcssa)
br i1 %c1, label %for.cond, label %done
done: ; preds = %for.inc11
ret void
}
```
Reproduce:
```
opt -passes="function(loop(indvars)),function(loop(loop-deletion)),function(loop(loop-reduce))" test.ll -S -o \
stale.ll
opt -passes="function(loop(indvars)),function(loop(loop-deletion)),function(invalidate),function(loop(loop-reduce))" test.ll -S -o \
fresh.ll
diff fresh.ll stale.ll
```
```diff
16,17d15
< %0 = shl nuw nsw i32 %conv7, 24
< %1 = add nuw nsw i32 %0, 16777216
21d18
< %lsr.iv1 = phi i32 [ %lsr.iv.next2, %for.body6 ], [ %1, %for.cond ]
22a20
> %h.039 = phi i32 [ 1, %for.cond ], [ %inc, %for.body6 ]
24c22,24
< %conv8 = ashr exact i32 %lsr.iv1, 24
---
> %0 = add i32 %conv7, %h.039
> %sext = shl i32 %0, 24
> %conv8 = ashr exact i32 %sext, 24
27a28
> %inc = add nuw nsw i32 %h.039, 1
29d29
< %lsr.iv.next2 = add i32 %lsr.iv1, 16777216
```
Note that `indvars` in the pipeline is needed for reproduction to first *warm* the ScalarEvolution analysis before `loop-deletion` left it to be less precise. Replacing `indvars` with simply `require` also reproduces the issue.
Contributor guide
Research direction
Start with the test.ll reproducer and run the two opt pipelines shown, comparing stale.ll with fresh.ll. Trace how loop-deletion preserves ScalarEvolution before loop-reduce consumes it; done means the stale analysis no longer causes the missed optimization, as verified by the comparison.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100