[PM/LoopUnswitch] Fix PR37889, producing the correct loop nest structure

after trivial unswitching.

This PR illustrates that a fundamental analysis update was not performed
with the new loop unswitch. This update is also somewhat fundamental to
the core idea of the new loop unswitch -- we actually *update* the CFG
based on the unswitching. In order to do that, we need to update the
loop nest in addition to the domtree.

For some reason, when writing trivial unswitching, I thought that the
loop nest structure cannot be changed by the transformation. But the PR
helps illustrate that it clearly can. I've expanded this to a number of
different test cases that try to cover the different cases of this. When
we unswitch, we move an exit edge of a loop out of the loop. If this
exit edge changes which loop reached by an exit is the innermost loop,
it changes the parent of the loop. Essentially, this transformation may
hoist the inner loop up the nest. I've added the simple logic to handle
this reliably in the trivial unswitching case. This just requires
updating LoopInfo and rebuilding LCSSA on the impacted loops. In the
trivial case, we don't even need to handle dedicated exits because we're
only hoisting the one loop and we just split its preheader.

I've also ported all of these tests to non-trivial unswitching and
verified that the logic already there correctly handles the loop nest
updates necessary.

Differential Revision: https://reviews.llvm.org/D48851

llvm-svn: 336477

2 files changed, 1162 insertions, 1 deletions

diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll b/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll
index a463cb68a07..bcf9fa81678 100644
--- a/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll
+++ b/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll
@@ -9,6 +9,9 @@ declare void @d()
 declare void @sink1(i32)
 declare void @sink2(i32)
 
+declare i1 @cond()
+declare i32 @cond.i32()
+
 ; Negative test: we cannot unswitch convergent calls.
 define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) {
 ; CHECK-LABEL: @test_no_unswitch_convergent(
@@ -2961,4 +2964,621 @@ loop_exit:
   ret i32 0
 ; CHECK:       loop_exit:
 ; CHECK-NEXT:    ret i32 0
-}
\ No newline at end of file
+}
+
+; Unswitch will not actually change the loop nest from:
+;   A < B < C
+define void @hoist_inner_loop0() {
+; CHECK-LABEL: define void @hoist_inner_loop0(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
+;
+; CHECK:       [[C_HEADER_US]]:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %[[B_LATCH_SPLIT_US:.*]]
+;
+; CHECK:       [[B_LATCH_SPLIT_US]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  call void @c()
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %b.latch
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]]
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       [[B_LATCH_SPLIT]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C
+; into
+;   A < (B, C)
+define void @hoist_inner_loop1(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop1(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
+;
+; CHECK:       [[C_HEADER_US]]:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
+;
+; CHECK:       [[B_LATCH_US]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  call void @c()
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %a.exit.c
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %x.a, i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.exit.b
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
+
+a.exit.c:
+  br label %a.latch
+; CHECK:       a.exit.c
+; CHECK-NEXT:    br label %a.latch
+
+a.exit.b:
+  br label %a.latch
+; CHECK:       a.exit.b:
+; CHECK-NEXT:    br label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C
+; into
+;   (A < B), C
+define void @hoist_inner_loop2(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop2(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
+;
+; CHECK:       [[C_HEADER_US]]:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
+;
+; CHECK:       [[B_LATCH_US]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  call void @c()
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   (A < B), (C < D)
+define void @hoist_inner_loop3(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop3(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
+;
+; CHECK:       [[C_HEADER_US]]:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
+;
+; CHECK:       [[B_LATCH_US]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  call void @c()
+  br i1 %v1, label %b.latch, label %c.body
+; CHECK:       c.header:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %c.body
+
+c.body:
+  %x.c = load i32, i32* %ptr
+  br label %d.header
+; CHECK:       c.body:
+; CHECK-NEXT:    %x.c = load i32, i32* %ptr
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  store i32 %x.c, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.header, label %c.latch
+; CHECK:       d.header:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %x.c, i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
+
+c.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
+
+b.latch:
+  %v4 = call i1 @cond()
+  br i1 %v4, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v4 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; This test is designed to exercise checking multiple remaining exits from the
+; loop being unswitched.
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   A < B < (C, D)
+define void @hoist_inner_loop4() {
+; CHECK-LABEL: define void @hoist_inner_loop4(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  %v1 = call i1 @cond()
+  br label %d.header
+; CHECK:       c.header:
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[C_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
+;
+; CHECK:       [[D_HEADER_US]]:
+; CHECK-NEXT:    call void @d()
+; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
+;
+; CHECK:       [[C_LATCH_US]]:
+; CHECK-NEXT:    br label %c.latch
+;
+; CHECK:       [[C_HEADER_SPLIT]]:
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  call void @d()
+  br i1 %v1, label %c.latch, label %d.exiting1
+; CHECK:       d.header:
+; CHECK-NEXT:    call void @d()
+; CHECK-NEXT:    br label %d.exiting1
+
+d.exiting1:
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.exiting2, label %a.latch
+; CHECK:       d.exiting1:
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
+
+d.exiting2:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %d.exiting3, label %loopexit.d
+; CHECK:       d.exiting2:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
+
+d.exiting3:
+  %v4 = call i1 @cond()
+  br i1 %v4, label %d.latch, label %b.latch
+; CHECK:       d.exiting3:
+; CHECK-NEXT:    %v4 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
+
+d.latch:
+  br label %d.header
+; CHECK:       d.latch:
+; CHECK-NEXT:    br label %d.header
+
+c.latch:
+  %v5 = call i1 @cond()
+  br i1 %v5, label %c.header, label %loopexit.c
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v5 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
+
+b.latch:
+  br label %b.header
+; CHECK:       b.latch:
+; CHECK-NEXT:    br label %b.header
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+loopexit.d:
+  br label %exit
+; CHECK:       loopexit.d:
+; CHECK-NEXT:    br label %exit
+
+loopexit.c:
+  br label %exit
+; CHECK:       loopexit.c:
+; CHECK-NEXT:    br label %exit
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   A < ((B < C), D)
+define void @hoist_inner_loop5(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop5(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  %x.c = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %d.header
+; CHECK:       c.header:
+; CHECK-NEXT:    %x.c = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[C_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
+;
+; CHECK:       [[D_HEADER_US]]:
+; CHECK-NEXT:    call void @d()
+; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
+;
+; CHECK:       [[C_LATCH_US]]:
+; CHECK-NEXT:    br label %c.latch
+;
+; CHECK:       [[C_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
+; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  call void @d()
+  br i1 %v1, label %c.latch, label %d.latch
+; CHECK:       d.header:
+; CHECK-NEXT:    call void @d()
+; CHECK-NEXT:    br label %d.latch
+
+d.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  store i32 %x.c, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.header, label %a.latch
+; CHECK:       d.latch:
+; CHECK-NEXT:    store i32 %x.a, i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
+
+c.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %c.header, label %b.latch
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
+
+b.latch:
+  br label %b.header
+; CHECK:       b.latch:
+; CHECK-NEXT:    br label %b.header
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+define void @hoist_inner_loop_switch(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop_switch(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i32 @cond.i32()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i32 @cond.i32()
+; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
+; CHECK-NEXT:      i32 1, label %[[B_HEADER_SPLIT_US:.*]]
+; CHECK-NEXT:      i32 2, label %[[B_HEADER_SPLIT_US]]
+; CHECK-NEXT:      i32 3, label %[[B_HEADER_SPLIT_US]]
+; CHECK-NEXT:    ]
+;
+; CHECK:       [[B_HEADER_SPLIT_US]]:
+; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
+;
+; CHECK:       [[C_HEADER_US]]:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
+;
+; CHECK:       [[B_LATCH_US]]:
+; CHECK-NEXT:    br label %b.latch
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  call void @c()
+  switch i32 %v1, label %c.latch [
+    i32 1, label %b.latch
+    i32 2, label %b.latch
+    i32 3, label %b.latch
+  ]
+; CHECK:       c.header:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll b/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll
index 572d2b6cf83..6b36a8a5cde 100644
--- a/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll
+++ b/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll
@@ -2,6 +2,9 @@
 
 declare void @some_func() noreturn
 
+declare i1 @cond()
+declare i32 @cond.i32()
+
 ; 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.
@@ -619,3 +622,541 @@ loop_exit:
 ; CHECK-NEXT:    %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ]
 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 }
+
+; Unswitch will not actually change the loop nest from:
+;   A < B < C
+define void @hoist_inner_loop0() {
+; CHECK-LABEL: define void @hoist_inner_loop0(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[B_LATCH_SPLIT:.*]], label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %b.latch
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %b.latch
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    br label %[[B_LATCH_SPLIT]]
+;
+; CHECK:       [[B_LATCH_SPLIT]]:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C
+; into
+;   A < (B, C)
+define void @hoist_inner_loop1(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop1(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %a.exit.c
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %x.a, i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.exit.b
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
+
+a.exit.c:
+  br label %a.latch
+; CHECK:       a.exit.c
+; CHECK-NEXT:    br label %a.latch
+
+a.exit.b:
+  br label %a.latch
+; CHECK:       a.exit.b:
+; CHECK-NEXT:    br label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C
+; into
+;   (A < B), C
+define void @hoist_inner_loop2(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop2(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  br i1 %v1, label %b.latch, label %c.latch
+; CHECK:       c.header:
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   (A < B), (C < D)
+define void @hoist_inner_loop3(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop3(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  br i1 %v1, label %b.latch, label %c.body
+; CHECK:       c.header:
+; CHECK-NEXT:    br label %c.body
+
+c.body:
+  %x.c = load i32, i32* %ptr
+  br label %d.header
+; CHECK:       c.body:
+; CHECK-NEXT:    %x.c = load i32, i32* %ptr
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  store i32 %x.c, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.header, label %c.latch
+; CHECK:       d.header:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %x.c, i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
+
+c.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
+
+b.latch:
+  %v4 = call i1 @cond()
+  br i1 %v4, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v4 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; This test is designed to exercise checking multiple remaining exits from the
+; loop being unswitched.
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   A < B < (C, D)
+define void @hoist_inner_loop4() {
+; CHECK-LABEL: define void @hoist_inner_loop4(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  %v1 = call i1 @cond()
+  br label %d.header
+; CHECK:       c.header:
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT:.*]], label %c.latch
+;
+; CHECK:       [[C_HEADER_SPLIT]]:
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  br i1 %v1, label %d.exiting1, label %c.latch
+; CHECK:       d.header:
+; CHECK-NEXT:    br label %d.exiting1
+
+d.exiting1:
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.exiting2, label %a.latch
+; CHECK:       d.exiting1:
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
+
+d.exiting2:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %d.exiting3, label %loopexit.d
+; CHECK:       d.exiting2:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
+
+d.exiting3:
+  %v4 = call i1 @cond()
+  br i1 %v4, label %d.latch, label %b.latch
+; CHECK:       d.exiting3:
+; CHECK-NEXT:    %v4 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
+
+d.latch:
+  br label %d.header
+; CHECK:       d.latch:
+; CHECK-NEXT:    br label %d.header
+
+c.latch:
+  %v5 = call i1 @cond()
+  br i1 %v5, label %c.header, label %loopexit.c
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v5 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
+
+b.latch:
+  br label %b.header
+; CHECK:       b.latch:
+; CHECK-NEXT:    br label %b.header
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+loopexit.d:
+  br label %exit
+; CHECK:       loopexit.d:
+; CHECK-NEXT:    br label %exit
+
+loopexit.c:
+  br label %exit
+; CHECK:       loopexit.c:
+; CHECK-NEXT:    br label %exit
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Unswitch will transform the loop nest from:
+;   A < B < C < D
+; into
+;   A < ((B < C), D)
+define void @hoist_inner_loop5(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop5(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  %x.c = load i32, i32* %ptr
+  %v1 = call i1 @cond()
+  br label %d.header
+; CHECK:       c.header:
+; CHECK-NEXT:    %x.c = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v1, label %c.latch, label %[[C_HEADER_SPLIT:.*]]
+;
+; CHECK:       [[C_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
+; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
+; CHECK-NEXT:    br label %d.header
+
+d.header:
+  br i1 %v1, label %c.latch, label %d.latch
+; CHECK:       d.header:
+; CHECK-NEXT:    br label %d.latch
+
+d.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  store i32 %x.c, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %d.header, label %a.latch
+; CHECK:       d.latch:
+; CHECK-NEXT:    store i32 %x.a, i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
+
+c.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %c.header, label %b.latch
+; CHECK:       c.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
+
+b.latch:
+  br label %b.header
+; CHECK:       b.latch:
+; CHECK-NEXT:    br label %b.header
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}
+
+; Same as `@hoist_inner_loop2` but using a switch.
+; Unswitch will transform the loop nest from:
+;   A < B < C
+; into
+;   (A < B), C
+define void @hoist_inner_loop_switch(i32* %ptr) {
+; CHECK-LABEL: define void @hoist_inner_loop_switch(
+entry:
+  br label %a.header
+; CHECK:       entry:
+; CHECK-NEXT:    br label %a.header
+
+a.header:
+  %x.a = load i32, i32* %ptr
+  br label %b.header
+; CHECK:       a.header:
+; CHECK-NEXT:    %x.a = load i32, i32* %ptr
+; CHECK-NEXT:    br label %b.header
+
+b.header:
+  %x.b = load i32, i32* %ptr
+  %v1 = call i32 @cond.i32()
+  br label %c.header
+; CHECK:       b.header:
+; CHECK-NEXT:    %x.b = load i32, i32* %ptr
+; CHECK-NEXT:    %v1 = call i32 @cond.i32()
+; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
+; CHECK-NEXT:      i32 1, label %b.latch
+; CHECK-NEXT:      i32 2, label %b.latch
+; CHECK-NEXT:      i32 3, label %b.latch
+; CHECK-NEXT:    ]
+;
+; CHECK:       [[B_HEADER_SPLIT]]:
+; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
+; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
+; CHECK-NEXT:    br label %c.header
+
+c.header:
+  switch i32 %v1, label %c.latch [
+    i32 1, label %b.latch
+    i32 2, label %b.latch
+    i32 3, label %b.latch
+  ]
+; CHECK:       c.header:
+; CHECK-NEXT:    br label %c.latch
+
+c.latch:
+  ; Use values from other loops to check LCSSA form.
+  store i32 %x.a, i32* %ptr
+  store i32 %x.b, i32* %ptr
+  %v2 = call i1 @cond()
+  br i1 %v2, label %c.header, label %exit
+; CHECK:       c.latch:
+; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
+; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
+; CHECK-NEXT:    %v2 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
+
+b.latch:
+  %v3 = call i1 @cond()
+  br i1 %v3, label %b.header, label %a.latch
+; CHECK:       b.latch:
+; CHECK-NEXT:    %v3 = call i1 @cond()
+; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
+
+a.latch:
+  br label %a.header
+; CHECK:       a.latch:
+; CHECK-NEXT:    br label %a.header
+
+exit:
+  ret void
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+}