llvm / llvm/llvm-project

[LoopInterchange] Stale ScalarEvolution loop dispositions survive loop-interchange; verify<scalar-evolution> fails and loop-unroll<runtime> then crashes

Open
#221,571 0 comments 0 reactions 0 assignees View on GitHub
confirmed crash-on-valid loopoptim
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```llvm
define void @test(ptr %A) {
entry:
br label %outer.header

outer.header:
%i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
%bound = srem i64 500, -200
br label %inner

inner:
%j = phi i64 [ 0, %outer.header ], [ %j.next, %inner ]
%gep = getelementptr inbounds [100 x [100 x i32]], ptr %A, i64 0, i64 %j, i64 %i
%v = load i32, ptr %gep, align 4
%add = add i32 %v, 1
store i32 %add, ptr %gep, align 4
%j.next = add nuw nsw i64 %j, 1
%inner.exitcond = icmp eq i64 %j.next, %bound
br i1 %inner.exitcond, label %outer.latch, label %inner

outer.latch:
%i.next = add nuw nsw i64 %i, 1
%outer.exitcond = icmp eq i64 %i.next, 100
br i1 %outer.exitcond, label %exit, label %outer.header

exit:
ret void
}
```

https://godbolt.org/z/fTz73qzrb

```
opt -disable-output -passes='loop(loop-interchange),loop-unroll' test.ll
```
```
opt: llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp:250: void ConnectEpilog(...):
Assertion `PN.hasOneUse() && "The phi should have 1 use"' failed.
2. Running pass "loop-unroll" on function "test"
```

https://godbolt.org/z/P355he1nb

```
opt -disable-output -passes='loop(loop-interchange),verify' test.ll
```
```
Cached disposition of (1 + (-1 * %bound)) for loop Loop at depth 1 containing: %inner,%inner.split,%inner.split1,%outer.header,%outer.latch,%outer.header.preheader
Loop at depth 2 containing: %outer.header,%outer.latch,%inner.split1
is incorrect: cached Invariant, actual Variant
```

Contributor guide

Open the contributing guide

Research direction

Start by running the two provided opt commands with the reproducer and inspect llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp around ConnectEpilog. Then trace the loop-interchange and ScalarEvolution handling involved in the stale disposition. Done means the ScalarEvolution verifier no longer reports an incorrect cached disposition and loop-unroll no longer hits the PHI assertion.

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
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.