llvm / llvm/llvm-project

[IndVarSimplify] Stale SCEV results transforms a terminating loop into infinite loop.

Open
#222,490 0 comments 0 reactions 0 assignees View on GitHub
confirmed llvm:SCEV miscompilation
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.