[IndVarSimplify] Stale SCEV results transforms a terminating loop into infinite loop.
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
```llvm
; test.ll
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
define i32 @pre_inc_i8(ptr %ptr, i1 %always_false) {
entry:
br label %for.cond
for.cond:
%iv = phi i8 [ -128, %entry ], [ %iv.inc, %always_taken ]
%iv2 = phi i8 [ 0, %entry ], [ %iv2.inc, %always_taken ]
store i8 %iv, ptr %ptr ; poison store
%cmp = icmp slt i8 %iv, 20
br i1 %cmp, label %for.body, label %for.end
for.body:
br i1 false, label %never_taken, label %always_taken
never_taken:
store i8 %iv2, ptr %ptr
br label %always_taken
always_taken:
%iv.inc = add nsw i8 %iv, 1 ; poison here
%iv2.inc = add nuw nsw i8 %iv2, 1 ; poison here
br label %for.cond
for.end:
ret i32 0
}
```
The loop runs `%iv` from `-128` to `20`, i.e. 148 iterations, and terminates. %iv and %iv2 do become poison in the iteration but they are only ever used as stores.
With the following pipeline, an infinite loop is introduced.
```
$ opt -S -passes='function(loop(indvars),loop(indvars))' test.ll
```
Reproducer: https://godbolt.org/z/6P11zffz9
```llvm
define i32 @pre_inc_i8(ptr %ptr, i1 %always_false) {
entry:
br label %for.cond
for.cond:
%iv = phi i8 [ -128, %entry ], [ %iv.inc, %always_taken ]
%iv2 = phi i8 [ 0, %entry ], [ %iv2.inc, %always_taken ]
store i8 %iv, ptr %ptr, align 1
br i1 true, label %for.body, label %for.end
for.body:
br i1 false, label %never_taken, label %always_taken
never_taken:
store i8 %iv2, ptr %ptr, align 1
br label %always_taken
always_taken:
%iv.inc = add nsw i8 %iv, 1
%iv2.inc = add nuw i8 %iv2, 1
br label %for.cond ; infinite loop
for.end:
ret i32 0
}
```
The issue seem to have come from stale SCEV as invalidating it fixes the infinite loop.
```
$ opt -S -passes='function(loop(indvars),loop(indvars))' test.ll
$ opt -S -passes='function(loop(indvars),invalidate,loop(indvars))' test.ll
```
```diff
for.cond:
%iv = phi i8 [ -128, %entry ], [ %iv.inc, %always_taken ]
%iv2 = phi i8 [ 0, %entry ], [ %iv2.inc, %always_taken ]
store i8 %iv, ptr %ptr, align 1
- ; with a fresh ScalarEvolution:
- %exitcond = icmp ne i8 %iv2, -108
- br i1 %exitcond, label %for.body, label %for.end
+ ; with the preserved ScalarEvolution:
+ br i1 true, label %for.body, label %for.end
```
Contributor guide
Research direction
Start with the test.ll reproducer and run the two opt pipelines containing repeated loop(indvars), with and without invalidate. Trace how the preserved ScalarEvolution result changes the second pass; done means the repeated pipeline no longer turns the terminating loop into an infinite loop and retains the correct exit condition.
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