; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt < %s -passes=loop-interchange -loop-interchange-profitabilities=ignore -S | FileCheck %s

; sum = 0;
; for (i = 0, sum_i = sum; i < 2; i++)
;   for (j = 0; j < 2; j++) {
;     sum += A[j][i];
;     B[j][i] = sum_i;
;   }
;
; Interchanging the loops will become as follows:
;
; sum = 0;
; for (j = 0, sum_j = sum; j < 2; j++)
;   for (i = 0; i < 2; i++) {
;     sum += A[j][i];
;     B[j][i] = sum_j;
;   }
;
; This is invalid transformation. Consider the case when `A` is as follows:
;
;  A = {{ 0, 0 }, { 1, 1 }}
;
; In this case, `sum_i` evolves 0 -> 1, while `sum_j` evolves 0 -> 0.
;
define i8 @extra_reduction_use_in_inner0(ptr noalias %A, ptr noalias %B) {
; CHECK-LABEL: define i8 @extra_reduction_use_in_inner0(
; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) {
; CHECK-NEXT:  [[INNER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[INNER:.*]]
; CHECK:       [[INNER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, %[[INNER_PREHEADER]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    [[SUM_OUTER:%.*]] = phi i8 [ 0, %[[INNER_PREHEADER]] ], [ [[SUM_LCSSA:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    br label %[[OUTER_HEADER_PREHEADER:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 0, %[[INNER]] ], [ [[TMP0:%.*]], %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[SUM_INNER:%.*]] = phi i8 [ [[SUM_OUTER]], %[[INNER]] ], [ [[SUM_INNER_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr [2 x i8], ptr [[A]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    [[A:%.*]] = load i8, ptr [[GEP_A]], align 1
; CHECK-NEXT:    [[SUM_INNER_NEXT]] = add i8 [[SUM_INNER]], [[A]]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr [2 x i8], ptr [[B]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    store i8 [[SUM_OUTER]], ptr [[GEP_B]], align 1
; CHECK-NEXT:    [[TMP0]] = add i64 [[J]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 2
; CHECK-NEXT:    br i1 [[TMP1]], label %[[OUTER_LATCH]], label %[[OUTER_HEADER_PREHEADER]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[SUM_LCSSA]] = phi i8 [ [[SUM_INNER_NEXT]], %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT:    [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2
; CHECK-NEXT:    br i1 [[EC_I]], label %[[EXIT:.*]], label %[[INNER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ [[SUM_LCSSA]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    ret i8 [[RES]]
;
entry:
  br label %outer.header

outer.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
  %sum.outer = phi i8 [ 0, %entry ], [ %sum.lcssa, %outer.latch ]
  br label %inner

inner:
  %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner ]
  %sum.inner = phi i8 [ %sum.outer, %outer.header ], [ %sum.inner.next, %inner ]
  %gep.A = getelementptr [2 x i8], ptr %A, i64 %j, i64 %i
  %a = load i8, ptr %gep.A
  %sum.inner.next = add i8 %sum.inner, %a
  %gep.B = getelementptr [2 x i8], ptr %B, i64 %j, i64 %i
  store i8 %sum.outer, ptr %gep.B
  %j.next = add i64 %j, 1
  %ec.j = icmp eq i64 %j.next, 2
  br i1 %ec.j, label %outer.latch, label %inner

outer.latch:
  %sum.lcssa = phi i8 [ %sum.inner.next, %inner ]
  %i.next = add i64 %i, 1
  %ec.i = icmp eq i64 %i.next, 2
  br i1 %ec.i, label %exit, label %outer.header

exit:
  %res = phi i8 [ %sum.lcssa, %outer.latch ]
  ret i8 %res
}

; sum = 0;
; for (i = 0; i < 2; i++)
;   for (j = 0; j < 2; j++) {
;     sum += A[j][i];
;     B[j][i] = sum;
;   }
;
; Interchanging the loops will become as follows:
;
; sum = 0;
; for (j = 0; j < 2; j++)
;   for (i = 0; i < 2; i++) {
;     sum += A[j][i];
;     B[j][i] = sum;
;   }
;
; This is invalid transformation. Consider the case when `A` is as follows:
;
;  A = {{ 0, 1 }, { 0, 0 }}
;
; In this case, in the original loops, `sum` evolves 0 -> 0 -> 1 -> 1, while in
; the interchanged loops, `sum` evolves 0 -> 1 -> 1 -> 1
;
define i8 @extra_reduction_use_in_inner1(ptr noalias %A, ptr noalias %B) {
; CHECK-LABEL: define i8 @extra_reduction_use_in_inner1(
; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    [[SUM_OUTER:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ [[SUM_LCSSA:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    br label %[[INNER:.*]]
; CHECK:       [[INNER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 0, %[[OUTER_HEADER]] ], [ [[J_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT:    [[SUM_INNER:%.*]] = phi i8 [ [[SUM_OUTER]], %[[OUTER_HEADER]] ], [ [[SUM_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr [2 x i8], ptr [[A]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    [[A:%.*]] = load i8, ptr [[GEP_A]], align 1
; CHECK-NEXT:    [[SUM_NEXT]] = add i8 [[SUM_INNER]], [[A]]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr [2 x i8], ptr [[B]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    store i8 [[SUM_NEXT]], ptr [[GEP_B]], align 1
; CHECK-NEXT:    [[J_NEXT]] = add i64 [[J]], 1
; CHECK-NEXT:    [[EC_J:%.*]] = icmp eq i64 [[J_NEXT]], 2
; CHECK-NEXT:    br i1 [[EC_J]], label %[[OUTER_LATCH]], label %[[INNER]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[SUM_LCSSA]] = phi i8 [ [[SUM_NEXT]], %[[INNER]] ]
; CHECK-NEXT:    [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT:    [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2
; CHECK-NEXT:    br i1 [[EC_I]], label %[[EXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ [[SUM_LCSSA]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    ret i8 [[RES]]
;
entry:
  br label %outer.header

outer.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
  %sum.outer = phi i8 [ 0, %entry ], [ %sum.lcssa, %outer.latch ]
  br label %inner

inner:
  %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner ]
  %sum.inner = phi i8 [ %sum.outer, %outer.header ], [ %sum.inner.next, %inner ]
  %gep.A = getelementptr [2 x i8], ptr %A, i64 %j, i64 %i
  %a = load i8, ptr %gep.A
  %sum.inner.next = add i8 %sum.inner, %a
  %gep.B = getelementptr [2 x i8], ptr %B, i64 %j, i64 %i
  store i8 %sum.inner.next, ptr %gep.B
  %j.next = add i64 %j, 1
  %ec.j = icmp eq i64 %j.next, 2
  br i1 %ec.j, label %outer.latch, label %inner

outer.latch:
  %sum.lcssa = phi i8 [ %sum.inner.next, %inner ]
  %i.next = add i64 %i, 1
  %ec.i = icmp eq i64 %i.next, 2
  br i1 %ec.i, label %exit, label %outer.header

exit:
  %res = phi i8 [ %sum.lcssa, %outer.latch ]
  ret i8 %res
}

; sum = 0;
; for (i = 0, sum_i = sum; i < 2; i++)
;   for (j = 0; j < 2; j++)
;     for (k = 0; k < 2; k++) {
;       sum += A[j][i];
;       B[j][i] = sum_i;
;     }
;
; In this case, interchanging the j-loop and the k-loop is legal.
;
define i8 @extra_reduction_use_in_inner2(ptr noalias %A, ptr noalias %B) {
; CHECK-LABEL: define i8 @extra_reduction_use_in_inner2(
; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    [[SUM_OUTER:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ [[SUM_OUTER_LCSSA:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    br label %[[MIDDLE_HEADER_PREHEADER:.*]]
; CHECK:       [[MIDDLE_HEADER_PREHEADER]]:
; CHECK-NEXT:    br label %[[MIDDLE_HEADER:.*]]
; CHECK:       [[MIDDLE_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[TMP2:%.*]], %[[MIDDLE_LATCH_SPLIT:.*]] ], [ 0, %[[MIDDLE_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[SUM_MIDDLE:%.*]] = phi i8 [ [[SUM_MIDDLE_LCSSA:%.*]], %[[MIDDLE_LATCH_SPLIT]] ], [ [[SUM_OUTER]], %[[MIDDLE_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[INNER_PREHEADER:.*]]
; CHECK:       [[INNER_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER:.*]]
; CHECK:       [[INNER]]:
; CHECK-NEXT:    [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[INNER_PREHEADER]] ]
; CHECK-NEXT:    [[SUM_INNER:%.*]] = phi i8 [ [[SUM_INNER_NEXT:%.*]], %[[INNER_SPLIT]] ], [ [[SUM_MIDDLE]], %[[INNER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[INNER_SPLIT1:.*]]
; CHECK:       [[INNER_SPLIT1]]:
; CHECK-NEXT:    [[GEP_A:%.*]] = getelementptr [2 x [2 x i8]], ptr [[A]], i64 [[K]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    [[A:%.*]] = load i8, ptr [[GEP_A]], align 1
; CHECK-NEXT:    [[SUM_INNER_NEXT]] = add i8 [[SUM_INNER]], [[A]]
; CHECK-NEXT:    [[GEP_B:%.*]] = getelementptr [2 x [2 x i8]], ptr [[B]], i64 [[K]], i64 [[J]], i64 [[I]]
; CHECK-NEXT:    store i8 [[SUM_OUTER]], ptr [[GEP_B]], align 1
; CHECK-NEXT:    [[K_NEXT:%.*]] = add i64 [[K]], 1
; CHECK-NEXT:    [[EC_K:%.*]] = icmp eq i64 [[K_NEXT]], 2
; CHECK-NEXT:    br label %[[MIDDLE_LATCH:.*]]
; CHECK:       [[INNER_SPLIT]]:
; CHECK-NEXT:    [[TMP0]] = add i64 [[K]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 2
; CHECK-NEXT:    br i1 [[TMP1]], label %[[MIDDLE_LATCH_SPLIT]], label %[[INNER]]
; CHECK:       [[MIDDLE_LATCH]]:
; CHECK-NEXT:    [[J_NEXT:%.*]] = add i64 [[J]], 1
; CHECK-NEXT:    [[EC_J:%.*]] = icmp eq i64 [[J_NEXT]], 2
; CHECK-NEXT:    br label %[[INNER_SPLIT]]
; CHECK:       [[MIDDLE_LATCH_SPLIT]]:
; CHECK-NEXT:    [[SUM_MIDDLE_LCSSA]] = phi i8 [ [[SUM_INNER_NEXT]], %[[INNER_SPLIT]] ]
; CHECK-NEXT:    [[TMP2]] = add i64 [[J]], 1
; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 2
; CHECK-NEXT:    br i1 [[TMP3]], label %[[OUTER_LATCH]], label %[[MIDDLE_HEADER]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[SUM_OUTER_LCSSA]] = phi i8 [ [[SUM_MIDDLE_LCSSA]], %[[MIDDLE_LATCH_SPLIT]] ]
; CHECK-NEXT:    [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT:    [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 2
; CHECK-NEXT:    br i1 [[EC_I]], label %[[EXIT:.*]], label %[[OUTER_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ [[SUM_OUTER_LCSSA]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    ret i8 [[RES]]
;
entry:
  br label %outer.header

outer.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
  %sum.outer = phi i8 [ 0, %entry ], [ %sum.outer.lcssa, %outer.latch ]
  br label %middle.header

middle.header:
  %j = phi i64 [ 0, %outer.header ], [ %j.next, %middle.latch ]
  %sum.middle = phi i8 [ %sum.outer, %outer.header ], [ %sum.middle.lcssa, %middle.latch ]
  br label %inner

inner:
  %k = phi i64 [ 0, %middle.header ], [ %k.next, %inner ]
  %sum.inner = phi i8 [ %sum.middle, %middle.header ], [ %sum.inner.next, %inner ]
  %gep.A = getelementptr [2 x [2 x i8]], ptr %A, i64 %k, i64 %j, i64 %i
  %a = load i8, ptr %gep.A
  %sum.inner.next = add i8 %sum.inner, %a
  %gep.B = getelementptr [2 x [2 x i8]], ptr %B, i64 %k, i64 %j, i64 %i
  store i8 %sum.outer, ptr %gep.B
  %k.next = add i64 %k, 1
  %ec.k = icmp eq i64 %k.next, 2
  br i1 %ec.k, label %middle.latch, label %inner

middle.latch:
  %sum.middle.lcssa = phi i8 [ %sum.inner.next, %inner ]
  %j.next = add i64 %j, 1
  %ec.j = icmp eq i64 %j.next, 2
  br i1 %ec.j, label %outer.latch, label %middle.header

outer.latch:
  %sum.outer.lcssa = phi i8 [ %sum.middle.lcssa, %middle.latch ]
  %i.next = add i64 %i, 1
  %ec.i = icmp eq i64 %i.next, 2
  br i1 %ec.i, label %exit, label %outer.header

exit:
  %res = phi i8 [ %sum.outer.lcssa, %outer.latch ]
  ret i8 %res
}