7 files changed, 872 insertions, 0 deletions
diff --git a/test/Transforms/LoopUnroll/2011-08-08-PhiUpdate.ll b/test/Transforms/LoopUnroll/2011-08-08-PhiUpdate.ll
new file mode 100644
index 0000000..cd954c8
--- /dev/null
+++ b/test/Transforms/LoopUnroll/2011-08-08-PhiUpdate.ll
@@ -0,0 +1,103 @@
+; RUN: opt < %s -loop-unroll -S -unroll-count=4 | FileCheck %s
+; Test phi update after partial unroll.
+
+declare i1 @check() nounwind
+
+; CHECK: @test
+; CHECK: if.else:
+; CHECK: if.then.loopexit
+; CHECK: %sub5.lcssa = phi i32 [ %sub{{.*}}, %if.else{{.*}} ], [ %sub{{.*}}, %if.else{{.*}} ], [ %sub{{.*}}, %if.else{{.*}} ], [ %sub{{.*}}, %if.else{{.*}} ]
+; CHECK: if.else.3
+define void @test1(i32 %i, i32 %j) nounwind uwtable ssp {
+entry:
+  %cond1 = call zeroext i1 @check()
+  br i1 %cond1, label %if.then, label %if.else.lr.ph
+
+if.else.lr.ph:                                    ; preds = %entry
+  br label %if.else
+
+if.else:                                          ; preds = %if.else, %if.else.lr.ph
+  %sub = phi i32 [ %i, %if.else.lr.ph ], [ %sub5, %if.else ]
+  %sub5 = sub i32 %sub, %j
+  %cond2 = call zeroext i1 @check()
+  br i1 %cond2, label %if.then, label %if.else
+
+if.then:                                          ; preds = %if.else, %entry
+  %i.tr = phi i32 [ %i, %entry ], [ %sub5, %if.else ]
+  ret void
+
+}
+
+; PR7318: assertion failure after doing a simple loop unroll
+;
+; CHECK: @test2
+; CHECK: bb1.bb2_crit_edge:
+; CHECK: %.lcssa = phi i32 [ %{{[2468]}}, %bb1{{.*}} ], [ %{{[2468]}}, %bb1{{.*}} ], [ %{{[2468]}}, %bb1{{.*}} ], [ %{{[2468]}}, %bb1{{.*}} ]
+; CHECK: bb1.3:
+define i32 @test2(i32* nocapture %p, i32 %n) nounwind readonly {
+entry:
+  %0 = icmp sgt i32 %n, 0                         ; <i1> [#uses=1]
+  br i1 %0, label %bb.nph, label %bb2
+
+bb.nph:                                           ; preds = %entry
+  %tmp = zext i32 %n to i64                       ; <i64> [#uses=1]
+  br label %bb
+
+bb:                                               ; preds = %bb.nph, %bb1
+  %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %bb1 ] ; <i64> [#uses=2]
+  %s.01 = phi i32 [ 0, %bb.nph ], [ %2, %bb1 ]    ; <i32> [#uses=1]
+  %scevgep = getelementptr i32* %p, i64 %indvar   ; <i32*> [#uses=1]
+  %1 = load i32* %scevgep, align 1                ; <i32> [#uses=1]
+  %2 = add nsw i32 %1, %s.01                      ; <i32> [#uses=2]
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  %indvar.next = add i64 %indvar, 1               ; <i64> [#uses=2]
+  %exitcond = icmp ne i64 %indvar.next, %tmp      ; <i1> [#uses=1]
+  br i1 %exitcond, label %bb, label %bb1.bb2_crit_edge
+
+bb1.bb2_crit_edge:                                ; preds = %bb1
+  %.lcssa = phi i32 [ %2, %bb1 ]                  ; <i32> [#uses=1]
+  br label %bb2
+
+bb2:                                              ; preds = %bb1.bb2_crit_edge, %entry
+  %s.0.lcssa = phi i32 [ %.lcssa, %bb1.bb2_crit_edge ], [ 0, %entry ] ; <i32> [#uses=1]
+  ret i32 %s.0.lcssa
+}
+
+; Check phi update for loop with an early-exit.
+;
+; CHECK: @test3
+; CHECK: return.loopexit:
+; CHECK: %tmp7.i.lcssa = phi i32 [ %tmp7.i{{.*}}, %land.lhs.true{{.*}} ], [ %tmp7.i{{.*}}, %land.lhs.true{{.*}} ], [ %tmp7.i{{.*}}, %land.lhs.true{{.*}} ], [ %tmp7.i{{.*}}, %land.lhs.true{{.*}} ]
+; CHECK: exit.3:
+define i32 @test3() nounwind uwtable ssp align 2 {
+entry:
+  %cond1 = call zeroext i1 @check()
+  br i1 %cond1, label %return, label %if.end
+
+if.end:                                           ; preds = %entry
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %if.end
+  %cond2 = call zeroext i1 @check()
+  br i1 %cond2, label %exit, label %do.cond
+
+exit:                  ; preds = %do.body
+  %tmp7.i = load i32* undef, align 8
+  br i1 undef, label %do.cond, label %land.lhs.true
+
+land.lhs.true:                                    ; preds = %exit
+  br i1 undef, label %return, label %do.cond
+
+do.cond:                                          ; preds = %land.lhs.true, %exit, %do.body
+  %cond3 = call zeroext i1 @check()
+  br i1 %cond3, label %do.end, label %do.body
+
+do.end:                                           ; preds = %do.cond
+  br label %return
+
+return:                                           ; preds = %do.end, %land.lhs.true, %entry
+  %retval.0 = phi i32 [ 0, %do.end ], [ 0, %entry ], [ %tmp7.i, %land.lhs.true ]
+  ret i32 %retval.0
+}
diff --git a/test/Transforms/LoopUnroll/2011-08-09-IVSimplify.ll b/test/Transforms/LoopUnroll/2011-08-09-IVSimplify.ll
new file mode 100644
index 0000000..59551d5
--- /dev/null
+++ b/test/Transforms/LoopUnroll/2011-08-09-IVSimplify.ll
@@ -0,0 +1,41 @@
+; RUN: opt -S < %s -loop-unroll -unroll-count=4 -enable-iv-rewrite=false | FileCheck %s
+;
+; Test induction variable simplify after loop unrolling. It should
+; expose nice opportunities for GVN.
+;
+; CHECK-NOT: while.body also ensures that loop unrolling (with SCEV)
+; removes unrolled loop exits given that 128 is a multiple of 4.
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-f80:128:128-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
+
+; PR10534: LoopUnroll not keeping canonical induction variable...
+; CHECK: while.body:
+; CHECK-NOT: while.body.1:
+; CHECK: %shr.1 = lshr i32 %bit_addr.addr.01, 5
+; CHECK: %arrayidx.1 = getelementptr inbounds i32* %bitmap, i32 %shr.1
+; CHECK: %shr.2 = lshr i32 %bit_addr.addr.01, 5
+; CHECK: %arrayidx.2 = getelementptr inbounds i32* %bitmap, i32 %shr.2
+; CHECK: %shr.3 = lshr i32 %bit_addr.addr.01, 5
+; CHECK: %arrayidx.3 = getelementptr inbounds i32* %bitmap, i32 %shr.3
+define void @FlipBit(i32* nocapture %bitmap, i32 %bit_addr, i32 %nbits) nounwind {
+entry:
+  br label %while.body
+
+while.body:
+  %nbits.addr.02 = phi i32 [ 128, %entry ], [ %dec, %while.body ]
+  %bit_addr.addr.01 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
+  %dec = add i32 %nbits.addr.02, -1
+  %shr = lshr i32 %bit_addr.addr.01, 5
+  %rem = and i32 %bit_addr.addr.01, 31
+  %shl = shl i32 1, %rem
+  %arrayidx = getelementptr inbounds i32* %bitmap, i32 %shr
+  %tmp6 = load i32* %arrayidx, align 4
+  %xor = xor i32 %tmp6, %shl
+  store i32 %xor, i32* %arrayidx, align 4
+  %inc = add i32 %bit_addr.addr.01, 1
+  %tobool = icmp eq i32 %dec, 0
+  br i1 %tobool, label %while.end, label %while.body
+
+while.end:
+  ret void
+}
diff --git a/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll b/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll
new file mode 100644
index 0000000..c1221f5
--- /dev/null
+++ b/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll
@@ -0,0 +1,62 @@
+; RUN: opt -S < %s -instcombine -inline -jump-threading -loop-unroll -unroll-count=4 | FileCheck %s
+;
+; This is a test case that required a number of setup passes because
+; it depends on block order.
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-apple-macosx10.6.8"
+
+declare i1 @check() nounwind
+declare i32 @getval() nounwind
+
+; Check that the loop exit merges values from all the iterations. This
+; could be a tad fragile, but it's a good test.
+;
+; CHECK: @foo
+; CHECK: return:
+; CHECK: %retval.0 = phi i32 [ %tmp7.i, %land.lhs.true ], [ 0, %do.cond ], [ %tmp7.i.1, %land.lhs.true.1 ], [ 0, %do.cond.1 ], [ %tmp7.i.2, %land.lhs.true.2 ], [ 0, %do.cond.2 ], [ %tmp7.i.3, %land.lhs.true.3 ], [ 0, %do.cond.3 ]
+; CHECK-NOT: @bar
+; CHECK: bar.exit.3
+define i32 @foo() uwtable ssp align 2 {
+entry:
+  br i1 undef, label %return, label %if.end
+
+if.end:                                           ; preds = %entry
+  %call2 = call i32 @getval()
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %if.end
+  %call6 = call i32 @bar()
+  %cmp = icmp ne i32 %call6, 0
+  br i1 %cmp, label %land.lhs.true, label %do.cond
+
+land.lhs.true:                                    ; preds = %do.body
+  %call10 = call i32 @getval()
+  %cmp11 = icmp eq i32 0, %call10
+  br i1 %cmp11, label %return, label %do.cond
+
+do.cond:                                          ; preds = %land.lhs.true, %do.body
+  %cmp18 = icmp sle i32 0, %call2
+  br i1 %cmp18, label %do.body, label %return
+
+return:                                           ; preds = %do.cond, %land.lhs.true, %entry
+  %retval.0 = phi i32 [ 0, %entry ], [ %call6, %land.lhs.true ], [ 0, %do.cond ]
+  ret i32 %retval.0
+}
+
+define linkonce_odr i32 @bar() nounwind uwtable ssp align 2 {
+entry:
+  br i1 undef, label %land.lhs.true, label %cond.end
+
+land.lhs.true:                                    ; preds = %entry
+  %cmp4 = call zeroext i1 @check()
+  br i1 %cmp4, label %cond.true, label %cond.end
+
+cond.true:                                        ; preds = %land.lhs.true
+  %tmp7 = call i32 @getval()
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.true, %land.lhs.true, %entry
+  %cond = phi i32 [ %tmp7, %cond.true ], [ 0, %land.lhs.true ], [ 0, %entry ]
+  ret i32 %cond
+}
diff --git a/test/Transforms/LoopUnroll/2011-10-01-NoopTrunc.ll b/test/Transforms/LoopUnroll/2011-10-01-NoopTrunc.ll
new file mode 100644
index 0000000..7fb471e
--- /dev/null
+++ b/test/Transforms/LoopUnroll/2011-10-01-NoopTrunc.ll
@@ -0,0 +1,36 @@
+; RUN: opt < %s -S -loop-unroll -unroll-threshold=150 | FileCheck %s
+;
+; Verify that trunc i64 to i32 is considered free by loop unrolling
+; heuristics when i32 is a native type.
+; This should result in full unrolling this loop with size=7, TC=19.
+; If the trunc were not free we would have 8*19=152 > 150.
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+; Check that for.body was unrolled 19 times.
+; CHECK: @test
+; CHECK: %0 = load
+; CHECK: %conv = sext i8 %0 to i32
+; CHECK: %add.1 = add nsw i32 %conv.1, %conv
+; CHECK: %add.18 = add nsw i32 %conv.18, %add.17
+; CHECK: ret i32 %add.18
+define i32 @test(i8* %arr) nounwind uwtable readnone {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %sum.02 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i8* %arr, i64 %indvars.iv
+  %0 = load i8* %arrayidx, align 1
+  %conv = sext i8 %0 to i32
+  %add = add nsw i32 %conv, %sum.02
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv1 = trunc i64 %indvars.iv.next to i32
+  %exitcond2 = icmp eq i32 %lftr.wideiv1, 19
+  br i1 %exitcond2, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  ret i32 %add.lcssa
+}
diff --git a/test/Transforms/LoopUnroll/pr10813.ll b/test/Transforms/LoopUnroll/pr10813.ll
new file mode 100644
index 0000000..7daefc2
--- /dev/null
+++ b/test/Transforms/LoopUnroll/pr10813.ll
@@ -0,0 +1,29 @@
+; RUN: opt < %s -loop-unroll -disable-output
+
+define void @"f_fu___REFUf[]REFUf[]Uf"() nounwind {
+allocas:
+  br i1 undef, label %cif_mask_all, label %cif_mixed_test_all
+
+cif_mask_all:                                     ; preds = %allocas
+  unreachable
+
+cif_mixed_test_all:                               ; preds = %allocas
+  br label %pl_loop.i964
+
+pl_loop.i964:                                     ; preds = %pl_loopend.i973, %cif_mixed_test_all
+  %0 = phi i32 [ %pl_nextlane.i971, %pl_loopend.i973 ], [ 0, %cif_mixed_test_all ]
+  br i1 undef, label %pl_dolane.i970, label %pl_loopend.i973
+
+pl_dolane.i970:                                   ; preds = %pl_loop.i964
+  %storeval.i.i969 = extractelement <4 x i8> <i8 0, i8 1, i8 2, i8 3>, i32 %0
+  store i8 %storeval.i.i969, i8* undef, align 1
+  br label %pl_loopend.i973
+
+pl_loopend.i973:                                  ; preds = %pl_dolane.i970, %pl_loop.i964
+  %pl_nextlane.i971 = add i32 %0, 1
+  %exitcond5 = icmp ne i32 %pl_nextlane.i971, 5
+  br i1 %exitcond5, label %pl_loop.i964, label %__scatter_base_offsets_i8.exit974
+
+__scatter_base_offsets_i8.exit974:                ; preds = %pl_loopend.i973
+  unreachable
+}
diff --git a/test/Transforms/LoopUnroll/scevunroll.ll b/test/Transforms/LoopUnroll/scevunroll.ll
new file mode 100644
index 0000000..99b3a7d
--- /dev/null
+++ b/test/Transforms/LoopUnroll/scevunroll.ll
@@ -0,0 +1,172 @@
+; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s
+;
+; Unit tests for loop unrolling using ScalarEvolution to compute trip counts.
+;
+; Indvars is run first to generate an "old" SCEV result. Some unit
+; tests may check that SCEV is properly invalidated between passes.
+
+; Completely unroll loops without a canonical IV.
+;
+; CHECK: @sansCanonical
+; CHECK-NOT: phi
+; CHECK-NOT: icmp
+; CHECK: ret
+define i32 @sansCanonical(i32* %base) nounwind {
+entry:
+  br label %while.body
+
+while.body:
+  %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ]
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ]
+  %iv.next = add i64 %iv, -1
+  %adr = getelementptr inbounds i32* %base, i64 %iv.next
+  %tmp = load i32* %adr, align 8
+  %sum.next = add i32 %sum, %tmp
+  %iv.narrow = trunc i64 %iv.next to i32
+  %cmp.i65 = icmp sgt i32 %iv.narrow, 0
+  br i1 %cmp.i65, label %while.body, label %exit
+
+exit:
+  ret i32 %sum
+}
+
+; SCEV unrolling properly handles loops with multiple exits. In this
+; case, the computed trip count based on a canonical IV is *not* for a
+; latch block. Canonical unrolling incorrectly unrolls it, but SCEV
+; unrolling does not.
+;
+; CHECK: @earlyLoopTest
+; CHECK: tail:
+; CHECK-NOT: br
+; CHECK: br i1 %cmp2, label %loop, label %exit2
+define i64 @earlyLoopTest(i64* %base) nounwind {
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %inc, %tail ]
+  %s = phi i64 [ 0, %entry ], [ %s.next, %tail ]
+  %adr = getelementptr i64* %base, i64 %iv
+  %val = load i64* %adr
+  %s.next = add i64 %s, %val
+  %inc = add i64 %iv, 1
+  %cmp = icmp ne i64 %inc, 4
+  br i1 %cmp, label %tail, label %exit1
+
+tail:
+  %cmp2 = icmp ne i64 %val, 0
+  br i1 %cmp2, label %loop, label %exit2
+
+exit1:
+  ret i64 %s
+
+exit2:
+  ret i64 %s.next
+}
+
+; SCEV properly unrolls multi-exit loops.
+;
+; CHECK: @multiExit
+; CHECK: getelementptr i32* %base, i32 10
+; CHECK-NEXT: load i32*
+; CHECK: br i1 false, label %l2.10, label %exit1
+; CHECK: l2.10:
+; CHECK-NOT: br
+; CHECK: ret i32
+define i32 @multiExit(i32* %base) nounwind {
+entry:
+  br label %l1
+l1:
+  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ]
+  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ]
+  %inc1 = add i32 %iv1, 1
+  %inc2 = add i32 %iv2, 1
+  %adr = getelementptr i32* %base, i32 %iv1
+  %val = load i32* %adr
+  %cmp1 = icmp slt i32 %iv1, 5
+  br i1 %cmp1, label %l2, label %exit1
+l2:
+  %cmp2 = icmp slt i32 %iv2, 10
+  br i1 %cmp2, label %l1, label %exit2
+exit1:
+  ret i32 1
+exit2:
+  ret i32 %val
+}
+
+
+; SCEV should not unroll a multi-exit loops unless the latch block has
+; a known trip count, regardless of the early exit trip counts. The
+; LoopUnroll utility uses this assumption to optimize the latch
+; block's branch.
+;
+; CHECK: @multiExit
+; CHECK: l3:
+; CHECK-NOT: br
+; CHECK:   br i1 %cmp3, label %l1, label %exit3
+define i32 @multiExitIncomplete(i32* %base) nounwind {
+entry:
+  br label %l1
+l1:
+  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
+  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]
+  %inc1 = add i32 %iv1, 1
+  %inc2 = add i32 %iv2, 1
+  %adr = getelementptr i32* %base, i32 %iv1
+  %val = load i32* %adr
+  %cmp1 = icmp slt i32 %iv1, 5
+  br i1 %cmp1, label %l2, label %exit1
+l2:
+  %cmp2 = icmp slt i32 %iv2, 10
+  br i1 %cmp2, label %l3, label %exit2
+l3:
+  %cmp3 = icmp ne i32 %val, 0
+  br i1 %cmp3, label %l1, label %exit3
+
+exit1:
+  ret i32 1
+exit2:
+  ret i32 2
+exit3:
+  ret i32 3
+}
+
+; When loop unroll merges a loop exit with one of its parent loop's
+; exits, SCEV must forget its ExitNotTaken info.
+;
+; CHECK: @nestedUnroll
+; CHECK-NOT: br i1
+; CHECK: for.body87:
+define void @nestedUnroll() nounwind {
+entry:
+  br label %for.inc
+
+for.inc:
+  br i1 false, label %for.inc, label %for.body38.preheader
+
+for.body38.preheader:
+  br label %for.body38
+
+for.body38:
+  %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
+  %mul48 = mul nsw i32 %i.113, 6
+  br label %for.body43
+
+for.body43:
+  %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ]
+  %add49 = add nsw i32 %j.011, %mul48
+  %sh_prom50 = zext i32 %add49 to i64
+  %inc72 = add nsw i32 %j.011, 1
+  br i1 false, label %for.body43, label %for.inc74
+
+for.inc74:
+  %inc76 = add nsw i32 %i.113, 1
+  br i1 false, label %for.body38, label %for.body87.preheader
+
+for.body87.preheader:
+  br label %for.body87
+
+for.body87:
+  br label %for.body87
+}
+
diff --git a/test/Transforms/LoopUnroll/unloop.ll b/test/Transforms/LoopUnroll/unloop.ll
new file mode 100644
index 0000000..217c8ce
--- /dev/null
+++ b/test/Transforms/LoopUnroll/unloop.ll
@@ -0,0 +1,429 @@
+; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s
+;
+; Unit tests for LoopInfo::updateUnloop.
+
+declare i1 @check() nounwind
+
+; Ensure that tail->inner is removed and rely on verify-loopinfo to
+; check soundness.
+;
+; CHECK: @skiplevelexit
+; CHECK: tail:
+; CHECK-NOT: br
+; CHECK: ret void
+define void @skiplevelexit() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %inner
+
+inner:
+  %iv = phi i32 [ 0, %outer ], [ %inc, %tail ]
+  %inc = add i32 %iv, 1
+  %wbucond = call zeroext i1 @check()
+  br i1 %wbucond, label %outer.backedge, label %tail
+
+tail:
+  br i1 false, label %inner, label %exit
+
+outer.backedge:
+  br label %outer
+
+exit:
+  ret void
+}
+
+; Remove the middle loop of a triply nested loop tree.
+; Ensure that only the middle loop is removed and rely on verify-loopinfo to
+; check soundness.
+;
+; CHECK: @unloopNested
+; Outer loop control.
+; CHECK: while.body:
+; CHECK: br i1 %cmp3, label %if.then, label %if.end
+; Inner loop control.
+; CHECK: while.end14.i:
+; CHECK: br i1 %call15.i, label %if.end.i, label %exit
+; Middle loop control should no longer reach %while.cond.
+; Now it is the outer loop backedge.
+; CHECK: exit:
+; CHECK: br label %while.cond.outer
+define void @unloopNested() {
+entry:
+  br label %while.cond.outer
+
+while.cond.outer:
+  br label %while.cond
+
+while.cond:
+  %cmp = call zeroext i1 @check()
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:
+  %cmp3 = call zeroext i1 @check()
+  br i1 %cmp3, label %if.then, label %if.end
+
+if.then:
+  br label %return
+
+if.end:
+  %cmp.i48 = call zeroext i1 @check()
+  br i1 %cmp.i48, label %if.then.i, label %if.else20.i
+
+if.then.i:
+  %cmp8.i = call zeroext i1 @check()
+  br i1 %cmp8.i, label %merge, label %if.else.i
+
+if.else.i:
+  br label %merge
+
+if.else20.i:
+  %cmp25.i = call zeroext i1 @check()
+  br i1 %cmp25.i, label %merge, label %if.else28.i
+
+if.else28.i:
+  br label %merge
+
+merge:
+  br label %while.cond2.i
+
+while.cond2.i:
+  %cmp.i = call zeroext i1 @check()
+  br i1 %cmp.i, label %while.cond2.backedge.i, label %while.end.i
+
+while.cond2.backedge.i:
+  br label %while.cond2.i
+
+while.end.i:
+  %cmp1114.i = call zeroext i1 @check()
+  br i1 %cmp1114.i, label %while.body12.lr.ph.i, label %while.end14.i
+
+while.body12.lr.ph.i:
+  br label %while.end14.i
+
+while.end14.i:
+  %call15.i = call zeroext i1 @check()
+  br i1 %call15.i, label %if.end.i, label %exit
+
+if.end.i:
+  br label %while.cond2.backedge.i
+
+exit:
+  br i1 false, label %while.cond, label %if.else
+
+if.else:
+  br label %while.cond.outer
+
+while.end:
+  br label %return
+
+return:
+  ret void
+}
+
+; Remove the middle loop of a deeply nested loop tree.
+; Ensure that only the middle loop is removed and rely on verify-loopinfo to
+; check soundness.
+;
+; CHECK: @unloopDeepNested
+; Inner-inner loop control.
+; CHECK: while.cond.us.i:
+; CHECK: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
+; CHECK: if.then.us.i:
+; CHECK: br label %while.cond.us.i
+; Inner loop tail.
+; CHECK: if.else.i:
+; CHECK: br label %while.cond.outer.i
+; Middle loop control (removed).
+; CHECK: valid_data.exit:
+; CHECK-NOT: br
+; CHECK: %cmp = call zeroext i1 @check()
+; Outer loop control.
+; CHECK: copy_data.exit:
+; CHECK: br i1 %cmp38, label %if.then39, label %while.cond.outer
+; Outer-outer loop tail.
+; CHECK: while.cond.outer.outer.backedge:
+; CHECK: br label %while.cond.outer.outer
+define void @unloopDeepNested() nounwind {
+for.cond8.preheader.i:
+  %cmp113.i = call zeroext i1 @check()
+  br i1 %cmp113.i, label %make_data.exit, label %for.body13.lr.ph.i
+
+for.body13.lr.ph.i:
+  br label %make_data.exit
+
+make_data.exit:
+  br label %while.cond.outer.outer
+
+while.cond.outer.outer:
+  br label %while.cond.outer
+
+while.cond.outer:
+  br label %while.cond
+
+while.cond:
+  br label %while.cond.outer.i
+
+while.cond.outer.i:
+  %tmp192.ph.i = call zeroext i1 @check()
+  br i1 %tmp192.ph.i, label %while.cond.outer.split.us.i, label %while.body.loopexit
+
+while.cond.outer.split.us.i:
+  br label %while.cond.us.i
+
+while.cond.us.i:
+  %cmp.us.i = call zeroext i1 @check()
+  br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
+
+while.body.us.i:
+  %cmp7.us.i = call zeroext i1 @check()
+  br i1 %cmp7.us.i, label %if.then.us.i, label %if.else.i
+
+if.then.us.i:
+  br label %while.cond.us.i
+
+if.else.i:
+  br label %while.cond.outer.i
+
+next_data.exit:
+  %tmp192.ph.i.lcssa28 = call zeroext i1 @check()
+  br i1 %tmp192.ph.i.lcssa28, label %while.end, label %while.body
+
+while.body.loopexit:
+  br label %while.body
+
+while.body:
+  br label %while.cond.i
+
+while.cond.i:
+  %cmp.i = call zeroext i1 @check()
+  br i1 %cmp.i, label %valid_data.exit, label %while.body.i
+
+while.body.i:
+  %cmp7.i = call zeroext i1 @check()
+  br i1 %cmp7.i, label %valid_data.exit, label %if.end.i
+
+if.end.i:
+  br label %while.cond.i
+
+valid_data.exit:
+  br i1 true, label %if.then, label %while.cond
+
+if.then:
+  %cmp = call zeroext i1 @check()
+  br i1 %cmp, label %if.then12, label %if.end
+
+if.then12:
+  br label %if.end
+
+if.end:
+  %tobool3.i = call zeroext i1 @check()
+  br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i
+
+while.body.lr.ph.i:
+  br label %copy_data.exit
+
+copy_data.exit:
+  %cmp38 = call zeroext i1 @check()
+  br i1 %cmp38, label %if.then39, label %while.cond.outer
+
+if.then39:
+  %cmp5.i = call zeroext i1 @check()
+  br i1 %cmp5.i, label %while.cond.outer.outer.backedge, label %for.cond8.preheader.i8.thread
+
+for.cond8.preheader.i8.thread:
+  br label %while.cond.outer.outer.backedge
+
+while.cond.outer.outer.backedge:
+  br label %while.cond.outer.outer
+
+while.end:
+  ret void
+}
+
+; Remove a nested loop with irreducible control flow.
+; Ensure that only the middle loop is removed and rely on verify-loopinfo to
+; check soundness.
+;
+; CHECK: @unloopIrreducible
+; Irreducible loop.
+; CHECK: for.inc117:
+; CHECK: br label %for.cond103t
+; Nested loop (removed).
+; CHECK: for.inc159:
+; CHECK: br label %for.inc163
+define void @unloopIrreducible() nounwind {
+
+entry:
+  br label %for.body
+
+for.body:
+  %cmp2113 = call zeroext i1 @check()
+  br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163
+
+for.body22.lr.ph:
+  br label %for.body22
+
+for.body22:
+  br label %for.body33
+
+for.body33:
+  br label %for.end
+
+for.end:
+  %cmp424 = call zeroext i1 @check()
+  br i1 %cmp424, label %for.body43.lr.ph, label %for.end93
+
+for.body43.lr.ph:
+  br label %for.end93
+
+for.end93:
+  %cmp96 = call zeroext i1 @check()
+  br i1 %cmp96, label %if.then97, label %for.cond103
+
+if.then97:
+  br label %for.cond103t
+
+for.cond103t:
+  br label %for.cond103
+
+for.cond103:
+  %cmp105 = call zeroext i1 @check()
+  br i1 %cmp105, label %for.body106, label %for.end120
+
+for.body106:
+  %cmp108 = call zeroext i1 @check()
+  br i1 %cmp108, label %if.then109, label %for.inc117
+
+if.then109:
+  br label %for.inc117
+
+for.inc117:
+  br label %for.cond103t
+
+for.end120:
+  br label %for.inc159
+
+for.inc159:
+  br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge
+
+for.cond15.for.inc163_crit_edge:
+  br label %for.inc163
+
+for.inc163:
+  %cmp12 = call zeroext i1 @check()
+  br i1 %cmp12, label %for.body, label %for.end166
+
+for.end166:
+  ret void
+
+}
+
+; Remove a loop whose exit branches into a sibling loop.
+; Ensure that only the loop is removed and rely on verify-loopinfo to
+; check soundness.
+;
+; CHECK: @unloopCriticalEdge
+; CHECK: while.cond.outer.i.loopexit.split:
+; CHECK: br label %while.body
+; CHECK: while.body:
+; CHECK: br label %for.end78
+define void @unloopCriticalEdge() nounwind {
+entry:
+  br label %for.cond31
+
+for.cond31:
+  br i1 undef, label %for.body35, label %for.end94
+
+for.body35:
+  br label %while.cond.i.preheader
+
+while.cond.i.preheader:
+  br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split
+
+while.cond.i.preheader.split:
+  br label %while.cond.i
+
+while.cond.i:
+  br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit
+
+while.cond.outer.i.loopexit:
+  br label %while.cond.outer.i.loopexit.split
+
+while.cond.outer.i.loopexit.split:
+  br i1 false, label %while.cond.i.preheader, label %Func2.exit
+
+Func2.exit:
+  br label %while.body
+
+while.body:
+  br i1 false, label %while.body, label %while.end
+
+while.end:
+  br label %for.end78
+
+for.end78:
+  br i1 undef, label %Proc2.exit, label %for.cond.i.preheader
+
+for.cond.i.preheader:
+  br label %for.cond.i
+
+for.cond.i:
+  br label %for.cond.i
+
+Proc2.exit:
+  br label %for.cond31
+
+for.end94:
+  ret void
+}
+
+; Test UnloopUpdater::removeBlocksFromAncestors.
+;
+; Check that the loop backedge is removed from the middle loop 1699,
+; but not the inner loop 1676.
+; CHECK: while.body1694:
+; CHECK:   br label %while.cond1676
+; CHECK: while.end1699:
+; CHECK:   br label %sw.default1711
+define void @removeSubloopBlocks() nounwind {
+entry:
+  br label %tryagain.outer
+
+tryagain.outer:                                   ; preds = %sw.bb304, %entry
+  br label %tryagain
+
+tryagain:                                         ; preds = %while.end1699, %tryagain.outer
+  br i1 undef, label %sw.bb1669, label %sw.bb304
+
+sw.bb304:                                         ; preds = %tryagain
+  br i1 undef, label %return, label %tryagain.outer
+
+sw.bb1669:                                        ; preds = %tryagain
+  br i1 undef, label %sw.default1711, label %while.cond1676
+
+while.cond1676:                                   ; preds = %while.body1694, %sw.bb1669
+  br i1 undef, label %while.end1699, label %while.body1694
+
+while.body1694:                                   ; preds = %while.cond1676
+  br label %while.cond1676
+
+while.end1699:                                    ; preds = %while.cond1676
+  br i1 false, label %tryagain, label %sw.default1711
+
+sw.default1711:                                   ; preds = %while.end1699, %sw.bb1669, %tryagain
+  br label %defchar
+
+defchar:                                          ; preds = %sw.default1711, %sw.bb376
+  br i1 undef, label %if.end2413, label %if.then2368
+
+if.then2368:                                      ; preds = %defchar
+  unreachable
+
+if.end2413:                                       ; preds = %defchar
+  unreachable
+
+return:                                           ; preds = %sw.bb304
+  ret void
+}