llvm / llvm/llvm-project

[opt] Missed optimization in `constraint-elimination`: Preserving ScalarEvolution leaves a stale, less precise SCEV; `indvars` then fails to fold a guard

Open
#213,872 1 comment 0 reactions 0 assignees View on GitHub
llvm:SCEV missed-optimization
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.