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

; Test that loop-interchange doesn't undo its own transoformation. This is
; the case when the cost computed by CacheCost is the same for the loop of `j`
; and `k`.
;
; #define N 4
; int a[N*N][N*N][N*N];
; void f() {
;   for (int i = 0; i < N; i++)
;     for (int j = 1; j < 2*N; j++)
;       for (int k = 1; k < 2*N; k++)
;         a[i][k+1][j-1] -= a[i+N-1][k][j];
; }

@a = dso_local local_unnamed_addr global [16 x [16 x [16 x i32]]] zeroinitializer, align 4

define dso_local void @f() {
; CHECK-LABEL: define dso_local void @f() {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[FOR_COND1_PREHEADER:.*]]
; CHECK:       [[FOR_COND1_PREHEADER]]:
; CHECK-NEXT:    [[INDVARS_IV46:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[INDVARS_IV_NEXT47:%.*]], %[[FOR_COND_CLEANUP3:.*]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = add nuw nsw i64 [[INDVARS_IV46]], 3
; CHECK-NEXT:    br label %[[FOR_BODY8_PREHEADER:.*]]
; CHECK:       [[FOR_COND5_PREHEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[FOR_COND5_PREHEADER:.*]]
; CHECK:       [[FOR_COND5_PREHEADER]]:
; CHECK-NEXT:    [[INDVARS_IV41:%.*]] = phi i64 [ [[INDVARS_IV_NEXT42:%.*]], %[[FOR_COND_CLEANUP7:.*]] ], [ 1, %[[FOR_COND5_PREHEADER_PREHEADER]] ]
; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV41]], -1
; CHECK-NEXT:    br label %[[FOR_BODY8_SPLIT1:.*]]
; CHECK:       [[FOR_BODY8_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY8:.*]]
; CHECK:       [[FOR_COND_CLEANUP3]]:
; CHECK-NEXT:    [[INDVARS_IV_NEXT47]] = add nuw nsw i64 [[INDVARS_IV46]], 1
; CHECK-NEXT:    [[EXITCOND50:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT47]], 4
; CHECK-NEXT:    br i1 [[EXITCOND50]], label %[[FOR_COND1_PREHEADER]], label %[[FOR_COND_CLEANUP:.*]]
; CHECK:       [[FOR_COND_CLEANUP7]]:
; CHECK-NEXT:    [[INDVARS_IV_NEXT42]] = add nuw nsw i64 [[INDVARS_IV41]], 1
; CHECK-NEXT:    [[EXITCOND45:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT42]], 8
; CHECK-NEXT:    br i1 [[EXITCOND45]], label %[[FOR_COND5_PREHEADER]], label %[[FOR_BODY8_SPLIT:.*]]
; CHECK:       [[FOR_BODY8]]:
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP4:%.*]], %[[FOR_BODY8_SPLIT]] ], [ 1, %[[FOR_BODY8_PREHEADER]] ]
; CHECK-NEXT:    br label %[[FOR_COND5_PREHEADER_PREHEADER]]
; CHECK:       [[FOR_BODY8_SPLIT1]]:
; CHECK-NEXT:    [[ARRAYIDX12:%.*]] = getelementptr inbounds nuw [16 x [16 x [16 x i32]]], ptr @a, i64 0, i64 [[TMP0]], i64 [[INDVARS_IV]], i64 [[INDVARS_IV41]]
; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[ARRAYIDX12]], align 4
; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[ARRAYIDX20:%.*]] = getelementptr inbounds [16 x [16 x [16 x i32]]], ptr @a, i64 0, i64 [[INDVARS_IV46]], i64 [[INDVARS_IV_NEXT]], i64 [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[ARRAYIDX20]], align 4
; CHECK-NEXT:    [[SUB21:%.*]] = sub nsw i32 [[TMP3]], [[TMP2]]
; CHECK-NEXT:    store i32 [[SUB21]], ptr [[ARRAYIDX20]], align 4
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], 8
; CHECK-NEXT:    br label %[[FOR_COND_CLEANUP7]]
; CHECK:       [[FOR_BODY8_SPLIT]]:
; CHECK-NEXT:    [[TMP4]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i64 [[TMP4]], 8
; CHECK-NEXT:    br i1 [[TMP5]], label %[[FOR_BODY8]], label %[[FOR_COND_CLEANUP3]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.cond1.preheader

for.cond1.preheader:
  %indvars.iv46 = phi i64 [ 0, %entry ], [ %indvars.iv.next47, %for.cond.cleanup3 ]
  %0 = add nuw nsw i64 %indvars.iv46, 3
  br label %for.cond5.preheader

for.cond5.preheader:
  %indvars.iv41 = phi i64 [ 1, %for.cond1.preheader ], [ %indvars.iv.next42, %for.cond.cleanup7 ]
  %1 = add nsw i64 %indvars.iv41, -1
  br label %for.body8

for.cond.cleanup3:
  %indvars.iv.next47 = add nuw nsw i64 %indvars.iv46, 1
  %exitcond50 = icmp ne i64 %indvars.iv.next47, 4
  br i1 %exitcond50, label %for.cond1.preheader, label %for.cond.cleanup

for.cond.cleanup7:
  %indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1
  %exitcond45 = icmp ne i64 %indvars.iv.next42, 8
  br i1 %exitcond45, label %for.cond5.preheader, label %for.cond.cleanup3

for.body8:
  %indvars.iv = phi i64 [ 1, %for.cond5.preheader ], [ %indvars.iv.next, %for.body8 ]
  %arrayidx12 = getelementptr inbounds nuw [16 x [16 x [16 x i32]]], ptr @a, i64 0, i64 %0, i64 %indvars.iv, i64 %indvars.iv41
  %2 = load i32, ptr %arrayidx12, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %arrayidx20 = getelementptr inbounds [16 x [16 x [16 x i32]]], ptr @a, i64 0, i64 %indvars.iv46, i64 %indvars.iv.next, i64 %1
  %3 = load i32, ptr %arrayidx20, align 4
  %sub21 = sub nsw i32 %3, %2
  store i32 %sub21, ptr %arrayidx20, align 4
  %exitcond = icmp ne i64 %indvars.iv.next, 8
  br i1 %exitcond, label %for.body8, label %for.cond.cleanup7

for.cond.cleanup:
  ret void
}