[SimplifyCFG] Defer folding unconditional branches to LateSimplifyCFG if it can destroy canonical loop structure.
Summary:
When simplifying unconditional branches from empty blocks, we pre-test if the
BB belongs to a set of loop headers and keep the block to prevent passes from
destroying canonical loop structure. However, the current algorithm fails if
the destination of the branch is a loop header. Especially when such a loop's
latch block is folded into loop header it results in additional backedges and
LoopSimplify turns it into a nested loop which prevent later optimizations
from being applied (e.g., loop unrolling and loop interleaving).
This patch augments the existing algorithm by further checking if the
destination of the branch belongs to a set of loop headers and defer
eliminating it if yes to LateSimplifyCFG.
Fixes PR33605: https://bugs.llvm.org/show_bug.cgi?id=33605
Reviewers: efriedma, mcrosier, pacxx, hsung, davidxl
Reviewed By: efriedma
Subscribers: ashutosh.nema, gberry, javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D35411
llvm-svn: 308422
diff --git a/llvm/test/Transforms/JumpThreading/pr33605.ll b/llvm/test/Transforms/JumpThreading/pr33605.ll
new file mode 100644
index 0000000..eb8cab9
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/pr33605.ll
@@ -0,0 +1,64 @@
+; RUN: opt < %s -jump-threading -S | FileCheck %s
+
+; Skip simplifying unconditional branches from empty blocks in simplifyCFG,
+; when it can destroy canonical loop structure.
+
+; void foo();
+; bool test(int a, int b, int *c) {
+; bool changed = false;
+; for (unsigned int i = 2; i--;) {
+; int r = a | b;
+; if ( r != c[i]) {
+; c[i] = r;
+; foo();
+; changed = true;
+; }
+; }
+; return changed;
+; }
+
+; CHECK-LABEL: @test(
+; CHECK: for.cond:
+; CHECK-NEXT: %i.0 = phi i32 [ 2, %entry ], [ %dec, %if.end ]
+; CHECK: for.body:
+; CHECK: br i1 %cmp, label %if.end, label %if.then
+; CHECK-NOT: br i1 %cmp, label %for.cond, label %if.then
+; CHECK: if.then:
+; CHECK: br label %if.end
+; CHECK-NOT: br label %for.cond
+; CHECK: if.end:
+; CHECK br label %for.cond
+define i1 @test(i32 %a, i32 %b, i32* %c) {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %if.end, %entry
+ %i.0 = phi i32 [ 2, %entry ], [ %dec, %if.end ]
+ %changed.0.off0 = phi i1 [ false, %entry ], [ %changed.1.off0, %if.end ]
+ %dec = add nsw i32 %i.0, -1
+ %tobool = icmp eq i32 %i.0, 0
+ br i1 %tobool, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup: ; preds = %for.cond
+ %changed.0.off0.lcssa = phi i1 [ %changed.0.off0, %for.cond ]
+ ret i1 %changed.0.off0.lcssa
+
+for.body: ; preds = %for.cond
+ %or = or i32 %a, %b
+ %idxprom = sext i32 %dec to i64
+ %arrayidx = getelementptr inbounds i32, i32* %c, i64 %idxprom
+ %0 = load i32, i32* %arrayidx, align 4
+ %cmp = icmp eq i32 %or, %0
+ br i1 %cmp, label %if.end, label %if.then
+
+if.then: ; preds = %for.body
+ store i32 %or, i32* %arrayidx, align 4
+ call void @foo()
+ br label %if.end
+
+if.end: ; preds = %for.body, %if.then
+ %changed.1.off0 = phi i1 [ true, %if.then ], [ %changed.0.off0, %for.body ]
+ br label %for.cond
+}
+
+declare void @foo()
diff --git a/llvm/test/Transforms/JumpThreading/static-profile.ll b/llvm/test/Transforms/JumpThreading/static-profile.ll
index d634a60..505e849 100644
--- a/llvm/test/Transforms/JumpThreading/static-profile.ll
+++ b/llvm/test/Transforms/JumpThreading/static-profile.ll
@@ -86,7 +86,7 @@
; Verify the new backedge:
; CHECK: check_2.thread:
; CHECK-NEXT: call void @bar()
-; CHECK-NEXT: br label %check_1
+; CHECK-NEXT: br label %check_3.thread
check_2:
%cond2 = icmp eq i32 %v, 2
@@ -100,7 +100,7 @@
; Verify the new backedge:
; CHECK: eq_2:
; CHECK-NEXT: call void @bar()
-; CHECK-NEXT: br label %check_1
+; CHECK-NEXT: br label %check_3.thread
check_3:
%condE = icmp eq i32 %v, 3