| Issue |
151144
|
| Summary |
SimplifyCFG breaks canonical loops even if --keep-loops is requested
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
ArneStenkrona2
|
SimplifyCFG can perform jump-threading on loop headers, which may break the dominance of the loop. SimplifyCFG has had a similar issue with breaking canonical loops, documented here https://bugs.llvm.org/show_bug.cgi?id=33605. Since that instance was treated as a bug I think it is appropriate to do the same in this instance.
To reproduce the error, this lit test can be added and run:
```
; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck --check-prefix=NO-THREADING %s
; Checks that we do not thread the control flow through the loop header bb1 as
; that will introduce a non-canonical loop
; NO-THREADING-LABEL: define void @__start
; NO-THREADING: bb3:
; NO-THREADING-NEXT: br i1 %cond, label %bb1, label %bb5
; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 --keep-loops="false" -S | FileCheck --check-prefix=THREADING %s
; Checks that we thread the control flow through the loop header bb1 since we
; do not request --keep-loops
; THREADING-LABEL: define void @__start
; THREADING: bb3:
; THREADING-NEXT: br i1 %cond, label %bb4, label %bb5
define void @__start(i1 %cond) {
entry:
br label %bb1
bb1: ; preds = %bb3, %entry
br i1 %cond, label %bb4, label %bb2
bb2: ; preds = %bb1
%_0_ = add i16 0, 0
br label %bb3
bb3: ; preds = %bb4, %bb2
br i1 %cond, label %bb1, label %bb5
bb4: ; preds = %bb1
%_1_ = add i32 0, 1
br label %bb3
bb5: ; preds = %bb3
ret void
}
```
Prior to SimplifyCFG, the loop, consisting of bb1, bb2, bb3, and bb4, is dominated by bb1. The pass will rewrite the branch in bb3, replacing the bb1 destination with bb4. The resulting cfg contains a cycle of just bb3 and bb4. Both bb3 and bb4 can be entered from outside the cycle, from bb2 and entry, respectively. Because of this, the cycle doesn't have a dominating header. I've attached a renderered CFG of both before and after for illustration.
<img width="499" height="517" alt="Image" src="" />
<img width="601" height="628" alt="Image" src="" />
It should reproduce on a current main. For reference, I was able to reproduce it now on `4745637e44bc1aaac342bd78d1f13a92caa59fde`.
I've opened a pull request for a suggested fix here https://github.com/llvm/llvm-project/pull/151142. It constrains the optimizations quite a bit, avoiding threading entirely when it involves a loop header. This prevents threading even in cases where it would not break canonical loops. which is unfortunate. The alternative would require analysis of some kind. If there is analysis at a reasonable cost that can be used to make this fix less restrictive I'm happy to amend the patch.
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
