; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info -S 2>&1 | FileCheck %s

@a = common global i32 0, align 4
@d = common dso_local local_unnamed_addr global [1 x [6 x i32]] zeroinitializer, align 4

; After interchanging the innermost and the middle loop, we should not continue
; doing interchange for the (new) middle loop and the outermost loop, because of
; values defined in the new innermost loop not available in the exiting block of
; the entire loop nest.
;
define void @innermost_latch_uses_values_in_middle_header() {
; CHECK-LABEL: define void @innermost_latch_uses_values_in_middle_header() {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr @a, align 4
; CHECK-NEXT:    [[B:%.*]] = add i32 80, 1
; CHECK-NEXT:    br label %[[OUTERMOST_HEADER:.*]]
; CHECK:       [[OUTERMOST_HEADER]]:
; CHECK-NEXT:    [[INDVAR_OUTERMOST:%.*]] = phi i32 [ 10, %[[ENTRY]] ], [ [[INDVAR_OUTERMOST_NEXT:%.*]], %[[OUTERMOST_LATCH:.*]] ]
; CHECK-NEXT:    [[TOBOOL71_I:%.*]] = icmp eq i32 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[TOBOOL71_I]], label %[[INNERMOST_HEADER_PREHEADER:.*]], label %[[OUTERMOST_LATCH]]
; CHECK:       [[MIDDLE_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[MIDDLE_HEADER:.*]]
; CHECK:       [[MIDDLE_HEADER]]:
; CHECK-NEXT:    [[INDVAR_MIDDLE:%.*]] = phi i64 [ [[INDVAR_MIDDLE_NEXT:%.*]], %[[MIDDLE_LATCH:.*]] ], [ 4, %[[MIDDLE_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[INDVAR_MIDDLE_WIDE:%.*]] = zext i32 [[B]] to i64
; CHECK-NEXT:    br label %[[INNERMOST_BODY:.*]]
; CHECK:       [[INNERMOST_HEADER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNERMOST_HEADER:.*]]
; CHECK:       [[INNERMOST_HEADER]]:
; CHECK-NEXT:    [[INDVAR_INNERMOST:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNERMOST_LATCH_SPLIT:.*]] ], [ 4, %[[INNERMOST_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[MIDDLE_HEADER_PREHEADER]]
; CHECK:       [[INNERMOST_BODY]]:
; CHECK-NEXT:    [[ARRAYIDX9_I:%.*]] = getelementptr inbounds [1 x [6 x i32]], ptr @d, i64 0, i64 [[INDVAR_INNERMOST]], i64 [[INDVAR_MIDDLE]]
; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX9_I]], align 4
; CHECK-NEXT:    br label %[[INNERMOST_LATCH:.*]]
; CHECK:       [[INNERMOST_LATCH]]:
; CHECK-NEXT:    [[INDVAR_INNERMOST_NEXT:%.*]] = add nsw i64 [[INDVAR_INNERMOST]], 1
; CHECK-NEXT:    [[TOBOOL5_I:%.*]] = icmp eq i64 [[INDVAR_INNERMOST_NEXT]], [[INDVAR_MIDDLE_WIDE]]
; CHECK-NEXT:    br label %[[MIDDLE_LATCH]]
; CHECK:       [[INNERMOST_LATCH_SPLIT]]:
; CHECK-NEXT:    [[INDVAR_MIDDLE_WIDE_LCSSA:%.*]] = phi i64 [ [[INDVAR_MIDDLE_WIDE]], %[[MIDDLE_LATCH]] ]
; CHECK-NEXT:    [[TMP1]] = add nsw i64 [[INDVAR_INNERMOST]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], [[INDVAR_MIDDLE_WIDE_LCSSA]]
; CHECK-NEXT:    br i1 [[TMP2]], label %[[OUTERMOST_LATCH_LOOPEXIT:.*]], label %[[INNERMOST_HEADER]]
; CHECK:       [[MIDDLE_LATCH]]:
; CHECK-NEXT:    [[INDVAR_MIDDLE_NEXT]] = add nsw i64 [[INDVAR_MIDDLE]], -1
; CHECK-NEXT:    [[TOBOOL2_I:%.*]] = icmp eq i64 [[INDVAR_MIDDLE_NEXT]], 0
; CHECK-NEXT:    br i1 [[TOBOOL2_I]], label %[[INNERMOST_LATCH_SPLIT]], label %[[MIDDLE_HEADER]]
; CHECK:       [[OUTERMOST_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTERMOST_LATCH]]
; CHECK:       [[OUTERMOST_LATCH]]:
; CHECK-NEXT:    [[INDVAR_OUTERMOST_NEXT]] = add nsw i32 [[INDVAR_OUTERMOST]], -5
; CHECK-NEXT:    [[TOBOOL_I:%.*]] = icmp eq i32 [[INDVAR_OUTERMOST_NEXT]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_I]], label %[[OUTERMOST_EXIT:.*]], label %[[OUTERMOST_HEADER]]
; CHECK:       [[OUTERMOST_EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %0 = load i32, ptr @a, align 4
  %b = add i32 80, 1
  br label %outermost.header

outermost.header:                      ; preds = %outermost.latch, %entry
  %indvar.outermost = phi i32 [ 10, %entry ], [ %indvar.outermost.next, %outermost.latch ]
  %tobool71.i = icmp eq i32 %0, 0
  br i1 %tobool71.i, label %middle.header, label %outermost.latch

middle.header:                            ; preds = %middle.latch, %outermost.header
  %indvar.middle = phi i64 [ 4, %outermost.header ], [ %indvar.middle.next, %middle.latch ]
  %indvar.middle.wide = zext i32 %b to i64 ; a def in the middle header
  br label %innermost.header

innermost.header:                                         ; preds = %middle.header, %innermost.latch
  %indvar.innermost = phi i64 [ %indvar.innermost.next, %innermost.latch ], [ 4, %middle.header ]
  br label %innermost.body

innermost.body:                                      ; preds = %innermost.header
  %arrayidx9.i = getelementptr inbounds [1 x [6 x i32]], ptr @d, i64 0, i64 %indvar.innermost, i64 %indvar.middle
  store i32 0, ptr %arrayidx9.i, align 4
  br label %innermost.latch

innermost.latch:                             ; preds = %innermost.body
  %indvar.innermost.next = add nsw i64 %indvar.innermost, 1
  %tobool5.i = icmp eq i64 %indvar.innermost.next, %indvar.middle.wide ; corresponding use in the innermost latch
  br i1 %tobool5.i, label %middle.latch, label %innermost.header

middle.latch:                                      ; preds = %innermost.latch
  %indvar.middle.next = add nsw i64 %indvar.middle, -1
  %tobool2.i = icmp eq i64 %indvar.middle.next, 0
  br i1 %tobool2.i, label %outermost.latch, label %middle.header

outermost.latch:                                      ; preds = %middle.latch, %outermost.header
  %indvar.outermost.next = add nsw i32 %indvar.outermost, -5
  %tobool.i = icmp eq i32 %indvar.outermost.next, 0
  br i1 %tobool.i, label %outermost.exit, label %outermost.header

outermost.exit:                                           ; preds = %outermost.latch
  ret void
}