llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch-loop-guard.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt -passes='loop-mssa(simple-loop-unswitch),verify<loops>' -S < %s | FileCheck %s

;; Check that a loop-invariant guard branch in a perfect nest is trivially
;; unswitched.  The outer loop's header branches to the latch (skipping the
;; inner loop entirely) when N == 0, or falls through into the inner loop.
;; Because N is loop-invariant, the new code in unswitchTrivialBranch rewires
;; the latch arm to point at the outer-loop exit, making the branch look like
;; an ordinary exit branch and allowing the standard trivial-unswitch logic to
;; hoist it out of the outer loop.
;;
;; Source:
;;   void f(int M, int N, int *A, int *B) {
;;     for (int j = 0; j < M; j++) {
;;       if (N <= 0) continue;          // invariant guard branches to latch
;;       for (int i = 0; i < N; i++)
;;         A[i] = B[i] + 1;
;;     }
;;   }
;; The key CFG edge is: outer.header --[N==0]--> outer.latch (the latch),
;; outer.header --[N!=0]--> inner.preheader (inside the outer loop).

define void @perfect_nest_guard(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @perfect_nest_guard(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP_M:%.*]] = icmp sle i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_M]], label %[[EXIT:.*]], label %[[OUTER_PREHEADER:.*]]
; CHECK:       [[OUTER_PREHEADER]]:
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    br i1 [[GUARD]], label %[[EXIT_LOOPEXIT_SPLIT:.*]], label %[[OUTER_PREHEADER_SPLIT:.*]]
; CHECK:       [[OUTER_PREHEADER_SPLIT]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[OUTER_PREHEADER_SPLIT]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[J_NEXT]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_OUTER:%.*]] = icmp eq i32 [[J_NEXT]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_OUTER]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT_LOOPEXIT_SPLIT]]
; CHECK:       [[EXIT_LOOPEXIT_SPLIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp.M = icmp sle i32 %M, 0
  br i1 %cmp.M, label %exit, label %outer.preheader

outer.preheader:
  %guard = icmp sle i32 %N, 0
  br label %outer.header

outer.header:
  %j = phi i32 [ 0, %outer.preheader ], [ %j.next, %outer.latch ]
  br i1 %guard, label %outer.latch, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  %j.next = add nuw i32 %j, 1
  %exitcond.outer = icmp eq i32 %j.next, %M
  br i1 %exitcond.outer, label %exit, label %outer.header

exit:
  ret void
}

;; This loopnest is similar to @perfect_nest_guard, except that the outer loop
;; is infinite. So the trivial unswitching of the inner loop guard is not
;; legal.
;;
;; Source:
;;   void f(int N, int *A, int *B) {
;;     while (true) {
;;       if (N <= 0) continue;          // invariant guard branches to latch
;;       for (int i = 0; i < N; i++)
;;         A[i] = B[i] + 1;
;;     }
;;   }
define void @perfect_nest_guard2(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @perfect_nest_guard2(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    br label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br i1 [[GUARD]], label %[[OUTER_LATCH:.*]], label %[[INNER_PREHEADER1:.*]]
; CHECK:       [[INNER_PREHEADER1]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER1]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    br label %[[INNER_PREHEADER]]
; CHECK:       [[EXIT:.*:]]
; CHECK-NEXT:    ret void
;
entry:
  %guard = icmp sle i32 %N, 0
  br label %outer.header

outer.header:
  br i1 %guard, label %outer.latch, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  br label %outer.header

exit:
  ret void
}

;; A negative test in which trivial unswitching cannot be done because there is
;; side effect before the branch
;;
;; Source:
;;   void f(int N, int *A, int *B) {
;;     while (true) {
;;       B[0] = 1;
;;       if (N <= 0) continue;          // invariant guard branches to latch
;;       for (int i = 0; i < N; i++)
;;         A[i] = B[i] + 1;
;;     }
;;   }
define void @not_perfect_nest_guard(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @not_perfect_nest_guard(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    store i32 0, ptr [[B]], align 4
; CHECK-NEXT:    br i1 [[GUARD]], label %[[OUTER_LATCH:.*]], label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER]]
; CHECK:       [[EXIT:.*:]]
; CHECK-NEXT:    ret void
;
entry:
  %guard = icmp sle i32 %N, 0
  br label %outer.header

outer.header:
  store i32 0, ptr %B, align 4
  br i1 %guard, label %outer.latch, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  br label %outer.header

exit:
  ret void
}

;; A negative test in which trivial unswitching cannot be done because there is
;; side effect in the latch of the outer loop
;;
;; Source:
;;   void f(int N, int *A, int *B) {
;;     while (true) {
;;       if (N > 0) {         // invariant guard branches to latch
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;       B[0] = 1;
;;     }
;;   }
;;
define void @not_perfect_nest_guard2(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @not_perfect_nest_guard2(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    br i1 [[GUARD]], label %[[INNER_PREHEADER:.*]], label %[[OUTER_LATCH:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    store i32 0, ptr [[B]], align 4
; CHECK-NEXT:    br label %[[OUTER_HEADER]]
; CHECK:       [[EXIT:.*:]]
; CHECK-NEXT:    ret void
;
entry:
  %guard = icmp sgt i32 %N, 0
  br label %outer.header

outer.header:
  br i1 %guard, label %inner.preheader, label %outer.latch

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  store i32 0, ptr %B, align 4
  br label %outer.header

exit:
  ret void
}

;; A negative test in which trivial unswitching cannot be done because the
;; latch of the outer loop has multiple exit blocks.
;;
;; void bad_outer_latch(int M, int N, int *A, int *B) {
;;   while (true) {
;;     if (N > 0) {         // invariant guard branches to latch
;;       for (int i = 0; i < N; i++)
;;         A[i] = B[i] + 1;
;;     }
;;
;;     // The latch now has multiple exit edges based on B[0]
;;     switch (B[0]) {
;;       case 0:
;;         A[0] = 1;
;;         return;          // branches to %exit
;;       case 1:
;;         return;          // branches to %exit2
;;       default:
;;         break;           // loops back to %outer.header
;;     }
;;   }
;; }
;;
define void @bad_outer_latch(i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @bad_outer_latch(
; CHECK-SAME: i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    br i1 [[GUARD]], label %[[INNER_PREHEADER:.*]], label %[[OUTER_LATCH:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[M:%.*]] = load i32, ptr [[B]], align 4
; CHECK-NEXT:    switch i32 [[M]], label %[[OUTER_HEADER]] [
; CHECK-NEXT:      i32 0, label %[[EXIT:.*]]
; CHECK-NEXT:      i32 1, label %[[EXIT2:.*]]
; CHECK-NEXT:    ]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    store i32 1, ptr [[A]], align 4
; CHECK-NEXT:    br label %[[EXIT3:.*]]
; CHECK:       [[EXIT2]]:
; CHECK-NEXT:    br label %[[EXIT3]]
; CHECK:       [[EXIT3]]:
; CHECK-NEXT:    ret void
;
entry:
  %guard = icmp sgt i32 %N, 0
  br label %outer.header

outer.header:
  br i1 %guard, label %inner.preheader, label %outer.latch

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  %sw = load i32, ptr %B, align 4
  switch i32 %sw, label %outer.header [
  i32 0, label %exit
  i32 1, label %exit2
  ]

exit:
  store i32 1, ptr %A, align 4
  br label %exit2

exit2:
  ret void
}

;; A negative test in which trivial unswitching cannot be done because a value
;; calculated in the loop is used in a phi in the exit block of the loop.
;;
;; Source:
;;   int f(int M, int N, int *A, int *B) {
;;     int sum = 42;              // 1. Initialized before the outer loop
;;     while (M > 0) {
;;       sum = sum + 1;           // 2. Updated in the outer header to a new initial value
;;       if (N > 0) {             // invariant guard branches to latch
;;         for (int i = 0; i < N; i++) {
;;           A[i] = B[i] + 1;
;;           sum += A[i];         // 3. Calculated/Accumulated in the inner loop
;;         }
;;       }
;;       B[0] = 0;
;;       M--;
;;     }
;;     return sum;                // 4. Used in outer loop exit block
;;   }
;;
define i32 @exit_phi(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define i32 @exit_phi(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp sgt i32 [[M]], 0
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT:    br i1 [[OUTER_COND]], label %[[OUTER_HEADER_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[IV_M:%.*]] = phi i32 [ [[IV_M_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ [[M]], %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[SUM_OUTER:%.*]] = phi i32 [ [[SUM_LATCH:%.*]], %[[OUTER_LATCH]] ], [ 42, %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[SUM_NEW_INIT:%.*]] = add i32 [[SUM_OUTER]], 1
; CHECK-NEXT:    br i1 [[GUARD]], label %[[INNER_PREHEADER:.*]], label %[[OUTER_LATCH]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[SUM_INNER:%.*]] = phi i32 [ [[SUM_NEW_INIT]], %[[INNER_PREHEADER]] ], [ [[SUM_NEXT:%.*]], %[[INNER_LATCH]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM_INNER]], [[INC]]
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], %[[INNER_LATCH]] ]
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[SUM_LATCH]] = phi i32 [ [[SUM_NEW_INIT]], %[[OUTER_HEADER]] ], [ [[SUM_NEXT_LCSSA]], %[[OUTER_LATCH_LOOPEXIT]] ]
; CHECK-NEXT:    [[IV_M_NEXT]] = sub nsw i32 [[IV_M]], 1
; CHECK-NEXT:    [[OUTER_COND2:%.*]] = icmp sgt i32 [[IV_M_NEXT]], 0
; CHECK-NEXT:    br i1 [[OUTER_COND2]], label %[[OUTER_HEADER]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    [[SUM_OUTER_LCSSA:%.*]] = phi i32 [ [[SUM_OUTER]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[SUM_EXIT:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[SUM_OUTER_LCSSA]], %[[EXIT_LOOPEXIT]] ]
; CHECK-NEXT:    ret i32 [[SUM_EXIT]]
;
entry:
  %outer.cond = icmp sgt i32 %M, 0
  %guard = icmp sgt i32 %N, 0
  br i1 %outer.cond, label %outer.header, label %exit

outer.header:
  %iv.M = phi i32 [ %M, %entry ], [ %iv.M.next, %outer.latch ]
  ; 1. Initialized before the outer loop (starts at 42 from entry)
  %sum.outer = phi i32 [ 42, %entry ], [ %sum.latch, %outer.latch ]

  ; 2. Updated in the outer loop header to a new initial value
  %sum.new_init = add i32 %sum.outer, 1
  br i1 %guard, label %inner.preheader, label %outer.latch

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %sum.inner = phi i32 [ %sum.new_init, %inner.preheader ], [ %sum.next, %inner.latch ]

  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4

  ; 3. Calculated in the inner loop
  %sum.next = add i32 %sum.inner, %inc
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  ; Merging the bypassed inner loop value with the executed inner loop reduction
  %sum.latch = phi i32 [ %sum.new_init, %outer.header], [ %sum.next, %inner.latch ]
  %iv.M.next = sub nsw i32 %iv.M, 1
  %outer.cond2 = icmp sgt i32 %iv.M.next, 0
  br i1 %outer.cond2, label %outer.header, label %exit

exit:
  ; 4. Used in a phi node in the outer loop exit block (LCSSA form)
  %sum.exit = phi i32 [%sum.outer, %outer.latch], [0, %entry]
  ret i32 %sum.exit
}

;; A positive test that includes a phi in the exit block of the outer loop
;;
;; Source:
;;   int f(int M, int N, int *A, int *B) {
;;     int sum = 42;
;;     while (M > 0) {
;;       sum = 10;
;;       if (N > 0) {
;;         for (int i = 0; i < N; i++) {
;;           A[i] = B[i] + 1;
;;         }
;;       }
;;       B[0] = 0;
;;       M--;
;;     }
;;     return sum;
;;   }
;;
define i32 @exit_phi2(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define i32 @exit_phi2(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp sgt i32 [[M]], 0
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT:    br i1 [[OUTER_COND]], label %[[OUTER_HEADER_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER]]:
; CHECK-NEXT:    br i1 [[GUARD]], label %[[OUTER_HEADER_PREHEADER_SPLIT:.*]], label %[[EXIT_LOOPEXIT_SPLIT:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER_SPLIT]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[IV_M:%.*]] = phi i32 [ [[IV_M_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ [[M]], %[[OUTER_HEADER_PREHEADER_SPLIT]] ]
; CHECK-NEXT:    br label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[IV_M_NEXT]] = sub nsw i32 [[IV_M]], 1
; CHECK-NEXT:    [[OUTER_COND2:%.*]] = icmp sgt i32 [[IV_M_NEXT]], 0
; CHECK-NEXT:    br i1 [[OUTER_COND2]], label %[[OUTER_HEADER]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT_LOOPEXIT_SPLIT]]
; CHECK:       [[EXIT_LOOPEXIT_SPLIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[SUM_EXIT:%.*]] = phi i32 [ 42, %[[ENTRY]] ], [ 10, %[[EXIT_LOOPEXIT_SPLIT]] ]
; CHECK-NEXT:    ret i32 [[SUM_EXIT]]
;
entry:
  %outer.cond = icmp sgt i32 %M, 0
  %guard = icmp sgt i32 %N, 0
  br i1 %outer.cond, label %outer.header, label %exit

outer.header:
  %iv.M = phi i32 [ %M, %entry ], [ %iv.M.next, %outer.latch ]
  br i1 %guard, label %inner.preheader, label %outer.latch

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %outer.latch, label %inner.header

outer.latch:
  %iv.M.next = sub nsw i32 %iv.M, 1
  %outer.cond2 = icmp sgt i32 %iv.M.next, 0
  br i1 %outer.cond2, label %outer.header, label %exit

exit:
  %sum.exit = phi i32 [10, %outer.latch], [42, %entry]
  ret i32 %sum.exit
}


;; A negative test in which we have two inner loops both guarded with different
;; guard conditions. The first guard doesn't branch to loop latch so this cannot
;; be unswitched. Unswitching either of the branches will be non-trivial
;; and requires loop versioning
;;
;; Source:
;;   void f(int M, int N, int N2, int *A, int *B) {
;;     for (int j = 0; j < M; j++) {
;;       if (N > 0) {                   // invariant guard
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;
;;       if (N2 > 0) {                  // invariant guard branches to latch
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;     }
;;   }

define void @multiple_inner_loops(i32 %M, i32 %N, i32 %N2, ptr %A, ptr %B) {
; CHECK-LABEL: define void @multiple_inner_loops(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], i32 [[N2:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP_M:%.*]] = icmp sle i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_M]], label %[[EXIT:.*]], label %[[OUTER_PREHEADER:.*]]
; CHECK:       [[OUTER_PREHEADER]]:
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    [[GUARD2:%.*]] = icmp sle i32 [[N2]], 0
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[OUTER_PREHEADER]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br i1 [[GUARD]], label %[[INNER2_GUARD:.*]], label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[INNER2_GUARD_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[INNER2_GUARD_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[INNER2_GUARD]]
; CHECK:       [[INNER2_GUARD]]:
; CHECK-NEXT:    br i1 [[GUARD2]], label %[[OUTER_LATCH]], label %[[INNER2_PREHEADER:.*]]
; CHECK:       [[INNER2_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER2_HEADER:.*]]
; CHECK:       [[INNER2_HEADER]]:
; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ 0, %[[INNER2_PREHEADER]] ], [ [[I_NEXT2:%.*]], %[[INNER2_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B2:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I2]]
; CHECK-NEXT:    [[VAL2:%.*]] = load i32, ptr [[GEP_B2]], align 4
; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[VAL2]], 1
; CHECK-NEXT:    [[GEP_A2:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I2]]
; CHECK-NEXT:    store i32 [[INC2]], ptr [[GEP_A2]], align 4
; CHECK-NEXT:    br label %[[INNER2_LATCH]]
; CHECK:       [[INNER2_LATCH]]:
; CHECK-NEXT:    [[I_NEXT2]] = add nuw i32 [[I2]], 1
; CHECK-NEXT:    [[EXITCOND_INNER2:%.*]] = icmp eq i32 [[I_NEXT2]], [[N2]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER2]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER2_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[J_NEXT]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_OUTER:%.*]] = icmp eq i32 [[J_NEXT]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_OUTER]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp.M = icmp sle i32 %M, 0
  br i1 %cmp.M, label %exit, label %outer.preheader

outer.preheader:
  %guard = icmp sle i32 %N, 0
  %guard2 = icmp sle i32 %N2, 0
  br label %outer.header

outer.header:
  %j = phi i32 [ 0, %outer.preheader ], [ %j.next, %outer.latch ]
  br i1 %guard, label %inner2.guard, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %inner2.guard, label %inner.header

inner2.guard:
  br i1 %guard2, label %outer.latch, label %inner2.preheader

inner2.preheader:
  br label %inner2.header

inner2.header:
  %i2 = phi i32 [ 0, %inner2.preheader ], [ %i.next2, %inner2.latch ]
  %gep.B2 = getelementptr inbounds i32, ptr %B, i32 %i2
  %val2 = load i32, ptr %gep.B2, align 4
  %inc2 = add i32 %val2, 1
  %gep.A2 = getelementptr inbounds i32, ptr %A, i32 %i2
  store i32 %inc2, ptr %gep.A2, align 4
  br label %inner2.latch

inner2.latch:
  %i.next2 = add nuw i32 %i2, 1
  %exitcond.inner2 = icmp eq i32 %i.next2, %N2
  br i1 %exitcond.inner2, label %outer.latch, label %inner2.header

outer.latch:
  %j.next = add nuw i32 %j, 1
  %exitcond.outer = icmp eq i32 %j.next, %M
  br i1 %exitcond.outer, label %exit, label %outer.header

exit:
  ret void
}

;; A negative test in which we have two inner loops both guarded but the guards
;; have the same conditions. The first guard doesn't branch to loop latch so
;; this cannot be unswitched. If the control flow is optimized before the loop
;; unswitching, and the second branch is eliminated then this will be a case of
;; trivial unswitching.
;;
;; Source:
;;   void f(int M, int N, int *A, int *B) {
;;     for (int j = 0; j < M; j++) {
;;       if (N > 0) {                   // invariant guard
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;
;;       if (N > 0) {                   // invariant guard branches to latch
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;     }
;;   }

define void @multiple_inner_loops2(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @multiple_inner_loops2(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP_M:%.*]] = icmp sle i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_M]], label %[[EXIT:.*]], label %[[OUTER_PREHEADER:.*]]
; CHECK:       [[OUTER_PREHEADER]]:
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[OUTER_PREHEADER]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br i1 [[GUARD]], label %[[INNER2_GUARD:.*]], label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[INNER2_GUARD_LOOPEXIT:.*]], label %[[INNER_HEADER]]
; CHECK:       [[INNER2_GUARD_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[INNER2_GUARD]]
; CHECK:       [[INNER2_GUARD]]:
; CHECK-NEXT:    br i1 [[GUARD]], label %[[OUTER_LATCH]], label %[[INNER2_PREHEADER:.*]]
; CHECK:       [[INNER2_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER2_HEADER:.*]]
; CHECK:       [[INNER2_HEADER]]:
; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ 0, %[[INNER2_PREHEADER]] ], [ [[I_NEXT2:%.*]], %[[INNER2_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B2:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I2]]
; CHECK-NEXT:    [[VAL2:%.*]] = load i32, ptr [[GEP_B2]], align 4
; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[VAL2]], 1
; CHECK-NEXT:    [[GEP_A2:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I2]]
; CHECK-NEXT:    store i32 [[INC2]], ptr [[GEP_A2]], align 4
; CHECK-NEXT:    br label %[[INNER2_LATCH]]
; CHECK:       [[INNER2_LATCH]]:
; CHECK-NEXT:    [[I_NEXT2]] = add nuw i32 [[I2]], 1
; CHECK-NEXT:    [[EXITCOND_INNER2:%.*]] = icmp eq i32 [[I_NEXT2]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER2]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER2_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[J_NEXT]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_OUTER:%.*]] = icmp eq i32 [[J_NEXT]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_OUTER]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp.M = icmp sle i32 %M, 0
  br i1 %cmp.M, label %exit, label %outer.preheader

outer.preheader:
  %guard = icmp sle i32 %N, 0
  br label %outer.header

outer.header:
  %j = phi i32 [ 0, %outer.preheader ], [ %j.next, %outer.latch ]
  br i1 %guard, label %inner2.guard, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %inner2.guard, label %inner.header

inner2.guard:
  br i1 %guard, label %outer.latch, label %inner2.preheader

inner2.preheader:
  br label %inner2.header

inner2.header:
  %i2 = phi i32 [ 0, %inner2.preheader ], [ %i.next2, %inner2.latch ]
  %gep.B2 = getelementptr inbounds i32, ptr %B, i32 %i2
  %val2 = load i32, ptr %gep.B2, align 4
  %inc2 = add i32 %val2, 1
  %gep.A2 = getelementptr inbounds i32, ptr %A, i32 %i2
  store i32 %inc2, ptr %gep.A2, align 4
  br label %inner2.latch

inner2.latch:
  %i.next2 = add nuw i32 %i2, 1
  %exitcond.inner2 = icmp eq i32 %i.next2, %N
  br i1 %exitcond.inner2, label %outer.latch, label %inner2.header

outer.latch:
  %j.next = add nuw i32 %j, 1
  %exitcond.outer = icmp eq i32 %j.next, %M
  br i1 %exitcond.outer, label %exit, label %outer.header

exit:
  ret void
}

;; This is modified from the previous test, @multiple_inner_loops2. Here
;; the second branch is optimzied away. The first branch is technically not a
;; loop guard anymore, but still this is an invariant branch and both loops
;; are control flow dependent on it. This is a case of trivial unswitching again.
;;
;; Source:
;;   void f(int M, int N, int *A, int *B) {
;;     for (int j = 0; j < M; j++) {
;;       if (N > 0) {                   // invariant branch
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;
;;         for (int i = 0; i < N; i++)
;;           A[i] = B[i] + 1;
;;       }
;;     }
;;   }

define void @multiple_inner_loops3(i32 %M, i32 %N, ptr %A, ptr %B) {
; CHECK-LABEL: define void @multiple_inner_loops3(
; CHECK-SAME: i32 [[M:%.*]], i32 [[N:%.*]], ptr [[A:%.*]], ptr [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP_M:%.*]] = icmp sle i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_M]], label %[[EXIT:.*]], label %[[OUTER_PREHEADER:.*]]
; CHECK:       [[OUTER_PREHEADER]]:
; CHECK-NEXT:    [[GUARD:%.*]] = icmp sle i32 [[N]], 0
; CHECK-NEXT:    br i1 [[GUARD]], label %[[EXIT_LOOPEXIT_SPLIT:.*]], label %[[OUTER_PREHEADER_SPLIT:.*]]
; CHECK:       [[OUTER_PREHEADER_SPLIT]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[OUTER_PREHEADER_SPLIT]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I]]
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[GEP_B]], align 4
; CHECK-NEXT:    [[INC:%.*]] = add i32 [[VAL]], 1
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I]]
; CHECK-NEXT:    store i32 [[INC]], ptr [[GEP_A]], align 4
; CHECK-NEXT:    br label %[[INNER_LATCH]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[I_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[INNER2_PREHEADER:.*]], label %[[INNER_HEADER]]
; CHECK:       [[INNER2_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER2_HEADER:.*]]
; CHECK:       [[INNER2_HEADER]]:
; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ 0, %[[INNER2_PREHEADER]] ], [ [[I_NEXT2:%.*]], %[[INNER2_LATCH:.*]] ]
; CHECK-NEXT:    [[GEP_B2:%.*]] = getelementptr inbounds i32, ptr [[B]], i32 [[I2]]
; CHECK-NEXT:    [[VAL2:%.*]] = load i32, ptr [[GEP_B2]], align 4
; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[VAL2]], 1
; CHECK-NEXT:    [[GEP_A2:%.*]] = getelementptr inbounds i32, ptr [[A]], i32 [[I2]]
; CHECK-NEXT:    store i32 [[INC2]], ptr [[GEP_A2]], align 4
; CHECK-NEXT:    br label %[[INNER2_LATCH]]
; CHECK:       [[INNER2_LATCH]]:
; CHECK-NEXT:    [[I_NEXT2]] = add nuw i32 [[I2]], 1
; CHECK-NEXT:    [[EXITCOND_INNER2:%.*]] = icmp eq i32 [[I_NEXT2]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER2]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[INNER2_HEADER]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[J_NEXT]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_OUTER:%.*]] = icmp eq i32 [[J_NEXT]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_OUTER]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT_LOOPEXIT_SPLIT]]
; CHECK:       [[EXIT_LOOPEXIT_SPLIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp.M = icmp sle i32 %M, 0
  br i1 %cmp.M, label %exit, label %outer.preheader

outer.preheader:
  %guard = icmp sle i32 %N, 0
  br label %outer.header

outer.header:
  %j = phi i32 [ 0, %outer.preheader ], [ %j.next, %outer.latch ]
  br i1 %guard, label %outer.latch, label %inner.preheader

inner.preheader:
  br label %inner.header

inner.header:
  %i = phi i32 [ 0, %inner.preheader ], [ %i.next, %inner.latch ]
  %gep.B = getelementptr inbounds i32, ptr %B, i32 %i
  %val = load i32, ptr %gep.B, align 4
  %inc = add i32 %val, 1
  %gep.A = getelementptr inbounds i32, ptr %A, i32 %i
  store i32 %inc, ptr %gep.A, align 4
  br label %inner.latch

inner.latch:
  %i.next = add nuw i32 %i, 1
  %exitcond.inner = icmp eq i32 %i.next, %N
  br i1 %exitcond.inner, label %inner2.preheader, label %inner.header

inner2.preheader:
  br label %inner2.header

inner2.header:
  %i2 = phi i32 [ 0, %inner2.preheader ], [ %i.next2, %inner2.latch ]
  %gep.B2 = getelementptr inbounds i32, ptr %B, i32 %i2
  %val2 = load i32, ptr %gep.B2, align 4
  %inc2 = add i32 %val2, 1
  %gep.A2 = getelementptr inbounds i32, ptr %A, i32 %i2
  store i32 %inc2, ptr %gep.A2, align 4
  br label %inner2.latch

inner2.latch:
  %i.next2 = add nuw i32 %i2, 1
  %exitcond.inner2 = icmp eq i32 %i.next2, %N
  br i1 %exitcond.inner2, label %outer.latch, label %inner2.header

outer.latch:
  %j.next = add nuw i32 %j, 1
  %exitcond.outer = icmp eq i32 %j.next, %M
  br i1 %exitcond.outer, label %exit, label %outer.header

exit:
  ret void
}