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

@A = dso_local global [256 x [256 x float]] zeroinitializer
@B = dso_local global [256 x [256 x float]] zeroinitializer
@C = dso_local global [256 x [256 x float]] zeroinitializer
@D = global [256 x [256 x [256 x float]]] zeroinitializer
@E = global [256 x [256 x [256 x float]]] zeroinitializer

; Check that the below loops are exchanged for vectorization.
;
; for (int i = 0; i < 256; i++) {
;   for (int j = 1; j < 256; j++) {
;     A[i][j] = A[i][j-1] + B[i][j];
;     C[i][j] += 1;
;   }
; }
;

define void @interchange_necessary_for_vectorization() {
; CHECK-LABEL: define void @interchange_necessary_for_vectorization() {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[FOR_J_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_I_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[FOR_I_HEADER:.*]]
; CHECK:       [[FOR_I_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[FOR_I_INC:.*]] ], [ 1, %[[FOR_I_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[FOR_J_BODY_SPLIT1:.*]]
; CHECK:       [[FOR_J_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_J_BODY:.*]]
; CHECK:       [[FOR_J_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[FOR_J_BODY_SPLIT:.*]] ], [ 1, %[[FOR_J_BODY_PREHEADER]] ]
; CHECK-NEXT:    br label %[[FOR_I_HEADER_PREHEADER]]
; CHECK:       [[FOR_J_BODY_SPLIT1]]:
; CHECK-NEXT:    [[J_DEC:%.*]] = add nsw i64 [[J]], -1
; CHECK-NEXT:    [[A_LOAD_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J_DEC]]
; CHECK-NEXT:    [[B_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @B, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[C_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @C, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[A:%.*]] = load float, ptr [[A_LOAD_INDEX]], align 4
; CHECK-NEXT:    [[B:%.*]] = load float, ptr [[B_INDEX]], align 4
; CHECK-NEXT:    [[C:%.*]] = load float, ptr [[C_INDEX]], align 4
; CHECK-NEXT:    [[ADD_0:%.*]] = fadd float [[A]], [[B]]
; CHECK-NEXT:    [[A_STORE_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    store float [[ADD_0]], ptr [[A_STORE_INDEX]], align 4
; CHECK-NEXT:    [[ADD_1:%.*]] = fadd float [[C]], 1.000000e+00
; CHECK-NEXT:    store float [[ADD_1]], ptr [[C_INDEX]], align 4
; CHECK-NEXT:    [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[CMP_J:%.*]] = icmp eq i64 [[J_NEXT]], 256
; CHECK-NEXT:    br label %[[FOR_I_INC]]
; CHECK:       [[FOR_J_BODY_SPLIT]]:
; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 256
; CHECK-NEXT:    br i1 [[TMP1]], label %[[EXIT:.*]], label %[[FOR_J_BODY]]
; CHECK:       [[FOR_I_INC]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq i64 [[I_NEXT]], 256
; CHECK-NEXT:    br i1 [[CMP_I]], label %[[FOR_J_BODY_SPLIT]], label %[[FOR_I_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.i.header

for.i.header:
  %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]
  br label %for.j.body

for.j.body:
  %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]
  %j.dec = add nsw i64 %j, -1
  %a.load.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec
  %b.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j
  %c.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i, i64 %j
  %a = load float, ptr %a.load.index, align 4
  %b = load float, ptr %b.index, align 4
  %c = load float, ptr %c.index, align 4
  %add.0 = fadd float %a, %b
  %a.store.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j
  store float %add.0, ptr %a.store.index, align 4
  %add.1 = fadd float %c, 1.0
  store float %add.1, ptr %c.index, align 4
  %j.next = add nuw nsw i64 %j, 1
  %cmp.j = icmp eq i64 %j.next, 256
  br i1 %cmp.j, label %for.i.inc, label %for.j.body

for.i.inc:
  %i.next = add nuw nsw i64 %i, 1
  %cmp.i = icmp eq i64 %i.next, 256
  br i1 %cmp.i, label %exit, label %for.i.header

exit:
  ret void
}

; Check that the following innermost loop can be vectorized so that
; interchanging is unnecessary.
;
; for (int i = 0; i < 256; i++)
;   for (int j = 1; j < 256; j++)
;     A[i][j-1] = A[i][j] + B[i][j];
;

define void @interchange_unnecesasry_for_vectorization() {
; CHECK-LABEL: define void @interchange_unnecesasry_for_vectorization() {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[FOR_I_HEADER:.*]]
; CHECK:       [[FOR_I_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 1, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[FOR_I_INC:.*]] ]
; CHECK-NEXT:    br label %[[FOR_J_BODY:.*]]
; CHECK:       [[FOR_J_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 1, %[[FOR_I_HEADER]] ], [ [[J_NEXT:%.*]], %[[FOR_J_BODY]] ]
; CHECK-NEXT:    [[J_DEC:%.*]] = add nsw i64 [[J]], -1
; CHECK-NEXT:    [[A_LOAD_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[B_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @B, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[A:%.*]] = load float, ptr [[A_LOAD_INDEX]], align 4
; CHECK-NEXT:    [[B:%.*]] = load float, ptr [[B_INDEX]], align 4
; CHECK-NEXT:    [[ADD:%.*]] = fadd float [[A]], [[B]]
; CHECK-NEXT:    [[A_STORE_INDEX:%.*]] = getelementptr inbounds nuw [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J_DEC]]
; CHECK-NEXT:    store float [[ADD]], ptr [[A_STORE_INDEX]], align 4
; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[CMP_J:%.*]] = icmp eq i64 [[J_NEXT]], 256
; CHECK-NEXT:    br i1 [[CMP_J]], label %[[FOR_I_INC]], label %[[FOR_J_BODY]]
; CHECK:       [[FOR_I_INC]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq i64 [[I_NEXT]], 256
; CHECK-NEXT:    br i1 [[CMP_I]], label %[[EXIT:.*]], label %[[FOR_I_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.i.header

for.i.header:
  %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]
  br label %for.j.body

for.j.body:
  %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]
  %j.dec = add nsw i64 %j, -1
  %a.load.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j
  %b.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j
  %a = load float, ptr %a.load.index, align 4
  %b = load float, ptr %b.index, align 4
  %add = fadd float %a, %b
  %a.store.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec
  store float %add, ptr %a.store.index, align 4
  %j.next = add nuw nsw i64 %j, 1
  %cmp.j = icmp eq i64 %j.next, 256
  br i1 %cmp.j, label %for.i.inc, label %for.j.body

for.i.inc:
  %i.next = add nuw nsw i64 %i, 1
  %cmp.i = icmp eq i64 %i.next, 256
  br i1 %cmp.i, label %exit, label %for.i.header

exit:
  ret void
}

; Check that the below loops are exchanged to allow innermost loop
; vectorization. We cannot vectorize the j-loop because it has a lexically
; backward dependency, but the i-loop can be vectorized because all the
; loop-carried dependencies are lexically forward. LoopVectorize currently only
; vectorizes innermost loop, hence move the i-loop to that position.
;
; for (int i = 0; i < 255; i++) {
;   for (int j = 1; j < 256; j++) {
;     A[i][j] = A[i][j-1] + B[i][j];
;     C[i][j] += C[i+1][j];
;   }
; }
;

define void @interchange_necessary_for_vectorization2() {
; CHECK-LABEL: define void @interchange_necessary_for_vectorization2() {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[FOR_J_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_I_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[FOR_I_HEADER:.*]]
; CHECK:       [[FOR_I_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[FOR_I_INC:.*]] ], [ 1, %[[FOR_I_HEADER_PREHEADER]] ]
; CHECK-NEXT:    [[I_INC:%.*]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    br label %[[FOR_J_BODY_SPLIT1:.*]]
; CHECK:       [[FOR_J_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_J_BODY:.*]]
; CHECK:       [[FOR_J_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[FOR_J_BODY_SPLIT:.*]] ], [ 1, %[[FOR_J_BODY_PREHEADER]] ]
; CHECK-NEXT:    br label %[[FOR_I_HEADER_PREHEADER]]
; CHECK:       [[FOR_J_BODY_SPLIT1]]:
; CHECK-NEXT:    [[J_DEC:%.*]] = add nsw i64 [[J]], -1
; CHECK-NEXT:    [[A_LOAD_INDEX:%.*]] = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J_DEC]]
; CHECK-NEXT:    [[B_INDEX:%.*]] = getelementptr inbounds [256 x [256 x float]], ptr @B, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[C_LOAD_INDEX:%.*]] = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 [[I_INC]], i64 [[J]]
; CHECK-NEXT:    [[C_STORE_INDEX:%.*]] = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    [[A:%.*]] = load float, ptr [[A_LOAD_INDEX]], align 4
; CHECK-NEXT:    [[B:%.*]] = load float, ptr [[B_INDEX]], align 4
; CHECK-NEXT:    [[C0:%.*]] = load float, ptr [[C_LOAD_INDEX]], align 4
; CHECK-NEXT:    [[C1:%.*]] = load float, ptr [[C_STORE_INDEX]], align 4
; CHECK-NEXT:    [[ADD_0:%.*]] = fadd float [[A]], [[B]]
; CHECK-NEXT:    [[A_STORE_INDEX:%.*]] = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 [[I]], i64 [[J]]
; CHECK-NEXT:    store float [[ADD_0]], ptr [[A_STORE_INDEX]], align 4
; CHECK-NEXT:    [[ADD_1:%.*]] = fadd float [[C0]], [[C1]]
; CHECK-NEXT:    store float [[ADD_1]], ptr [[C_STORE_INDEX]], align 4
; CHECK-NEXT:    [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[CMP_J:%.*]] = icmp eq i64 [[J_NEXT]], 256
; CHECK-NEXT:    br label %[[FOR_I_INC]]
; CHECK:       [[FOR_J_BODY_SPLIT]]:
; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 256
; CHECK-NEXT:    br i1 [[TMP1]], label %[[EXIT:.*]], label %[[FOR_J_BODY]]
; CHECK:       [[FOR_I_INC]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq i64 [[I_NEXT]], 255
; CHECK-NEXT:    br i1 [[CMP_I]], label %[[FOR_J_BODY_SPLIT]], label %[[FOR_I_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.i.header

for.i.header:
  %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]
  %i.inc = add nuw nsw i64 %i, 1
  br label %for.j.body

for.j.body:
  %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]
  %j.dec = add nsw i64 %j, -1
  %a.load.index = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec
  %b.index = getelementptr inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j
  %c.load.index = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i.inc, i64 %j
  %c.store.index = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i, i64 %j
  %a = load float, ptr %a.load.index
  %b = load float, ptr %b.index
  %c0 = load float, ptr %c.load.index
  %c1 = load float, ptr %c.store.index
  %add.0 = fadd float %a, %b
  %a.store.index = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j
  store float %add.0, ptr %a.store.index
  %add.1 = fadd float %c0, %c1
  store float %add.1, ptr %c.store.index
  %j.next = add nuw nsw i64 %j, 1
  %cmp.j = icmp eq i64 %j.next, 256
  br i1 %cmp.j, label %for.i.inc, label %for.j.body

for.i.inc:
  %i.next = add nuw nsw i64 %i, 1
  %cmp.i = icmp eq i64 %i.next, 255
  br i1 %cmp.i, label %exit, label %for.i.header

exit:
  ret void
}

; Check that no interchange is performed for the following loop. Interchanging
; the j-loop and k-loop makes the innermost loop vectorizble, since the j-loop
; has only forward dependencies. However, at the moment, a loop body consisting
; of multiple BBs is handled pesimistically. Hence the j-loop isn't moved to
; the innermost place.
;
; for (int i = 0; i < 255; i++) {
;   for (int j = 0; j < 255; j++) {
;     for (int k = 0; k < 128; k++) {
;       E[i][j][k] = D[i+1][j+1][2*k];
;       if (cond)
;         D[i][j][k+1] = 1.0;
;   }
; }

define void @multiple_BBs_in_loop() {
; CHECK-LABEL: define void @multiple_BBs_in_loop() {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[FOR_I_HEADER:.*]]
; CHECK:       [[FOR_I_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_INC:%.*]], %[[FOR_I_INC:.*]] ]
; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    br label %[[FOR_J_HEADER:.*]]
; CHECK:       [[FOR_J_HEADER]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 0, %[[FOR_I_HEADER]] ], [ [[J_INC:%.*]], %[[FOR_J_INC:.*]] ]
; CHECK-NEXT:    [[J_INC]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    br label %[[FOR_K_BODY:.*]]
; CHECK:       [[FOR_K_BODY]]:
; CHECK-NEXT:    [[K:%.*]] = phi i64 [ 0, %[[FOR_J_HEADER]] ], [ [[K_INC:%.*]], %[[FOR_K_INC:.*]] ]
; CHECK-NEXT:    [[K_INC]] = add nuw nsw i64 [[K]], 1
; CHECK-NEXT:    [[K_2:%.*]] = mul nuw nsw i64 [[K]], 2
; CHECK-NEXT:    [[D_INDEX:%.*]] = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 [[I_INC]], i64 [[J_INC]], i64 [[K_2]]
; CHECK-NEXT:    [[E_INDEX:%.*]] = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @E, i64 0, i64 [[I]], i64 [[J]], i64 [[K]]
; CHECK-NEXT:    [[D_LOAD:%.*]] = load float, ptr [[D_INDEX]], align 4
; CHECK-NEXT:    store float [[D_LOAD]], ptr [[E_INDEX]], align 4
; CHECK-NEXT:    [[COND:%.*]] = freeze i1 undef
; CHECK-NEXT:    br i1 [[COND]], label %[[IF_THEN:.*]], label %[[FOR_K_INC]]
; CHECK:       [[IF_THEN]]:
; CHECK-NEXT:    [[D_INDEX2:%.*]] = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 [[I]], i64 [[J]], i64 [[K_INC]]
; CHECK-NEXT:    store float 1.000000e+00, ptr [[D_INDEX2]], align 4
; CHECK-NEXT:    br label %[[FOR_K_INC]]
; CHECK:       [[FOR_K_INC]]:
; CHECK-NEXT:    [[CMP_K:%.*]] = icmp eq i64 [[K_INC]], 128
; CHECK-NEXT:    br i1 [[CMP_K]], label %[[FOR_J_INC]], label %[[FOR_K_BODY]]
; CHECK:       [[FOR_J_INC]]:
; CHECK-NEXT:    [[CMP_J:%.*]] = icmp eq i64 [[J_INC]], 255
; CHECK-NEXT:    br i1 [[CMP_J]], label %[[FOR_I_INC]], label %[[FOR_J_HEADER]]
; CHECK:       [[FOR_I_INC]]:
; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq i64 [[I_INC]], 255
; CHECK-NEXT:    br i1 [[CMP_I]], label %[[EXIT:.*]], label %[[FOR_I_HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.i.header

for.i.header:
  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
  %i.inc = add nuw nsw i64 %i, 1
  br label %for.j.header

for.j.header:
  %j = phi i64 [ 0, %for.i.header ], [ %j.inc, %for.j.inc ]
  %j.inc = add nuw nsw i64 %j, 1
  br label %for.k.body

for.k.body:
  %k = phi i64 [ 0, %for.j.header ], [ %k.inc, %for.k.inc ]
  %k.inc = add nuw nsw i64 %k, 1
  %k.2 = mul nuw nsw i64 %k, 2
  %d.index = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 %i.inc, i64 %j.inc, i64 %k.2
  %e.index = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @E, i64 0, i64 %i, i64 %j, i64 %k
  %d.load = load float, ptr %d.index
  store float %d.load, ptr %e.index
  %cond = freeze i1 undef
  br i1 %cond, label %if.then, label %for.k.inc

if.then:
  %d.index2 = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 %i, i64 %j, i64 %k.inc
  store float 1.0, ptr %d.index2
  br label %for.k.inc

for.k.inc:
  %cmp.k = icmp eq i64 %k.inc, 128
  br i1 %cmp.k, label %for.j.inc, label %for.k.body

for.j.inc:
  %cmp.j = icmp eq i64 %j.inc, 255
  br i1 %cmp.j, label %for.i.inc, label %for.j.header

for.i.inc:
  %cmp.i = icmp eq i64 %i.inc, 255
  br i1 %cmp.i, label %exit, label %for.i.header

exit:
  ret void
}