[LoopUnswitch] Improve loop unswitch pass to find trivial unswitch conditions more effectively

Summary:
This patch improves trivial loop unswitch. 

The current trivial loop unswitch only checks if loop header's terminator contains a trivial unswitch condition. But if the loop header only has one reachable successor (due to intentionally or unintentionally missed code simplification), we should consider the successor as part of the loop header. Therefore, instead of stopping at loop header's terminator, we should keep traversing its successors within loop until reach a *real* conditional branch or switch (whose condition can not be constant folded). This change will enable a single -loop-unswitch pass to unswitch multiple trivial conditions (unswitch one trivial condition could open opportunity to unswitch another one in the same loop), while the old implementation can unswitch only one per pass. 

Reviewers: reames, broune

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D11481

llvm-svn: 243203

2 files changed, 52 insertions, 5 deletions

diff --git a/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll b/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll
index e79d874d9ca..3d1c895edec 100644
--- a/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll
+++ b/llvm/test/Transforms/LoopUnswitch/infinite-loop.ll
@@ -9,23 +9,23 @@
 ; It can trivially unswitch on the false cas of condition %a though.
 
 ; STATS: 2 loop-unswitch - Number of branches unswitched
-; STATS: 1 loop-unswitch - Number of unswitches that are trivial
+; STATS: 2 loop-unswitch - Number of unswitches that are trivial
 
 ; CHECK-LABEL: @func_16(
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT: br i1 %a, label %entry.split, label %abort0.split
 
 ; CHECK: entry.split:
-; CHECK-NEXT: br i1 %b, label %cond.end.us, label %abort1
+; CHECK-NEXT: br i1 %b, label %cond.end, label %abort1.split
 
-; CHECK: cond.end.us:
-; CHECK-NEXT: br label %cond.end.us
+; CHECK: cond.end:
+; CHECK-NEXT: br label %cond.end
 
 ; CHECK: abort0.split:
 ; CHECK-NEXT: call void @end0() [[NOR_NUW:#[0-9]+]]
 ; CHECK-NEXT: unreachable
 
-; CHECK: abort1:
+; CHECK: abort1.split:
 ; CHECK-NEXT: call void @end1() [[NOR_NUW]]
 ; CHECK-NEXT: unreachable
 
diff --git a/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll b/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll
new file mode 100644
index 00000000000..db3328278da
--- /dev/null
+++ b/llvm/test/Transforms/LoopUnswitch/trivial-unswitch.ll
@@ -0,0 +1,47 @@
+; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -verify-loop-info -S < %s 2>&1 | FileCheck %s
+
+; This test contains two trivial unswitch condition in one loop. 
+; LoopUnswitch pass should be able to unswitch the second one 
+; after unswitching the first one.
+
+
+; CHECK:  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge
+
+; CHECK:  ..split_crit_edge:                                ; preds = %0
+; CHECK:    br label %.split
+
+; CHECK:  .split:                                           ; preds = %..split_crit_edge
+; CHECK:    br i1 %cond2, label %.split..split.split_crit_edge, label %.split.loop_exit.split1_crit_edge
+
+; CHECK:  .split..split.split_crit_edge:                    ; preds = %.split
+; CHECK:    br label %.split.split
+
+; CHECK:  .split.split:                                     ; preds = %.split..split.split_crit_edge
+; CHECK:    br label %loop_begin
+
+; CHECK:  loop_begin:                                       ; preds = %do_something, %.split.split
+; CHECK:    br i1 true, label %continue, label %loop_exit
+
+; CHECK:  continue:                                         ; preds = %loop_begin
+; CHECK:    %var_val = load i32, i32* %var
+; CHECK:    br i1 true, label %do_something, label %loop_exit
+
+define i32 @test(i32* %var, i1 %cond1, i1 %cond2) {
+  br label %loop_begin
+
+loop_begin:  
+  br i1 %cond1, label %continue, label %loop_exit	; first trivial condition
+
+continue:
+  %var_val = load i32, i32* %var
+  br i1 %cond2, label %do_something, label %loop_exit	; second trivial condition  
+
+do_something:
+  call void @some_func() noreturn nounwind
+  br label %loop_begin
+
+loop_exit:
+  ret i32 0
+}
+
+declare void @some_func() noreturn
\ No newline at end of file