[opt] Missed optimization in `constraint-elimination`: Preserving ScalarEvolution leaves a stale, less precise SCEV; `indvars` then fails to fold a guard
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`ConstraintElimination` 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, 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 = "amdgcn-amd-amdhsa"
define void @multiple_pow2(i64 %count) {
entry:
%end = shl i64 %count, 2
br label %loop
loop: ; preds = %loop.latch, %entry
%iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %entry ]
%cmp.i.not = icmp eq i64 %iv, %end
br i1 %cmp.i.not, label %exit, label %loop.latch
loop.latch: ; preds = %loop
%iv.next = add i64 %iv, 4
%cmp2.i.i = icmp ult i64 %iv, %end
br i1 %cmp2.i.i, label %loop, label %exit
exit: ; preds = %loop.latch, %loop
ret void
}
```
Reproduce:
```
opt -passes="function(constraint-elimination),function(loop(indvars))" test.ll -S -o \
stale.ll
opt -passes="function(constraint-elimination),function(invalidate),function(loop(indvars))" test.ll -S -o \
fresh.ll
diff fresh.ll stale.ll
```
```diff
7a8,13
> %end = shl i64 %count, 2
> %0 = lshr i64 %end, 2
> %1 = add nuw nsw i64 %end, 3
> %2 = lshr i64 %1, 2
> %umin = call i64 @llvm.umin.i64(i64 %0, i64 %2)
> %3 = icmp eq i64 %0, %umin
11c17
< br i1 true, label %exit, label %loop.latch
---
> br i1 %3, label %exit, label %loop.latch
18a25,29
>
> declare i64 @llvm.umin.i64(i64, i64) #0
```
With SCEV invalidated, `indvars` proves the guard is always true and emits `br i1 true`. With the preserved SCEV it cannot, and leaves six instructions, a `llvm.umin` call and a conditional branch in the loop preheader (causing the missed optimization).
Contributor guide
Research direction
Start with the test.ll reproducer and run the two opt pipelines shown, then compare stale.ll with fresh.ll. Read the ConstraintElimination, ScalarEvolution, and indvars pass interactions to determine why the preserved analysis prevents the guard from folding; done means the missed optimization is removed without requiring explicit invalidation in the pipeline.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100