test/Transforms/LoopDistribute/doubly-nested.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt -aa-pipeline=basic-aa -passes=loop-distribute -enable-loop-distribute -verify-loop-info -verify-dom-info -S \
; RUN:   < %s | FileCheck %s

; Doubly nested loop with two statements in the innermost loop.
; Statement S2 can be put into a separate loop because there is no dependence between S1 and S2.
;
;   for (int i = 0; i < N; i++) {
;     for (int j = 0; j < M; j++) {
;       S1: A[i][j+1] = A[i][j] + B[i][j] + C[i][j] // Statement S1
;       ================================
;       S2: D[i][j] = E[i][j] * F[i][j];      // Statement 2
;     }
;   }

define void @doubly_nested_distributable(ptr noalias %A, ptr noalias %B, ptr noalias %C,
                                         ptr noalias %D, ptr noalias %E, ptr noalias %F,
                                         i64 %N, i64 %M) {
; CHECK-LABEL: define void @doubly_nested_distributable(
; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]], ptr noalias [[C:%.*]], ptr noalias [[D:%.*]], ptr noalias [[E:%.*]], ptr noalias [[F:%.*]], i64 [[N:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[FOR_I_HEADER:.*]]
; CHECK:       [[FOR_I_HEADER]]:
; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[FOR_I_INC:.*]] ]
; CHECK-NEXT:    [[I_CMP:%.*]] = icmp slt i64 [[I]], [[N]]
; CHECK-NEXT:    br i1 [[I_CMP]], label %[[FOR_J_PREHEADER_LDIST1:.*]], label %[[FOR_END:.*]]
; CHECK:       [[FOR_J_PREHEADER_LDIST1]]:
; CHECK-NEXT:    br label %[[FOR_J_BODY_LDIST1:.*]]
; CHECK:       [[FOR_J_BODY_LDIST1]]:
; CHECK-NEXT:    [[J_LDIST1:%.*]] = phi i64 [ 0, %[[FOR_J_PREHEADER_LDIST1]] ], [ [[J_NEXT_LDIST1:%.*]], %[[FOR_J_BODY_LDIST1]] ]
; CHECK-NEXT:    [[IDX_I_LDIST1:%.*]] = mul i64 [[I]], [[M]]
; CHECK-NEXT:    [[IDX_LDIST1:%.*]] = add i64 [[IDX_I_LDIST1]], [[J_LDIST1]]
; CHECK-NEXT:    [[ARRAYIDXA_LDIST1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDX_LDIST1]]
; CHECK-NEXT:    [[LOADA_LDIST1:%.*]] = load i32, ptr [[ARRAYIDXA_LDIST1]], align 4
; CHECK-NEXT:    [[ARRAYIDXB_LDIST1:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[IDX_LDIST1]]
; CHECK-NEXT:    [[LOADB_LDIST1:%.*]] = load i32, ptr [[ARRAYIDXB_LDIST1]], align 4
; CHECK-NEXT:    [[ARRAYIDXC_LDIST1:%.*]] = getelementptr inbounds i32, ptr [[C]], i64 [[IDX_LDIST1]]
; CHECK-NEXT:    [[LOADC_LDIST1:%.*]] = load i32, ptr [[ARRAYIDXC_LDIST1]], align 4
; CHECK-NEXT:    [[ADDS1_LDIST1:%.*]] = add i32 [[LOADB_LDIST1]], [[LOADC_LDIST1]]
; CHECK-NEXT:    [[ADDWITHDEP_LDIST1:%.*]] = add i32 [[ADDS1_LDIST1]], [[LOADA_LDIST1]]
; CHECK-NEXT:    [[J_NEXT_LDIST1]] = add nuw nsw i64 [[J_LDIST1]], 1
; CHECK-NEXT:    [[IDX_NEXT_LDIST1:%.*]] = add i64 [[IDX_LDIST1]], 1
; CHECK-NEXT:    [[ARRAYIDXA_NEXT_LDIST1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDX_NEXT_LDIST1]]
; CHECK-NEXT:    store i32 [[ADDWITHDEP_LDIST1]], ptr [[ARRAYIDXA_NEXT_LDIST1]], align 4
; CHECK-NEXT:    [[EXITCOND_J_LDIST1:%.*]] = icmp eq i64 [[J_NEXT_LDIST1]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_J_LDIST1]], label %[[FOR_J_PREHEADER:.*]], label %[[FOR_J_BODY_LDIST1]]
; CHECK:       [[FOR_J_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_J_BODY:.*]]
; CHECK:       [[FOR_J_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 0, %[[FOR_J_PREHEADER]] ], [ [[J_NEXT:%.*]], %[[FOR_J_BODY]] ]
; CHECK-NEXT:    [[IDX_I:%.*]] = mul i64 [[I]], [[M]]
; CHECK-NEXT:    [[IDX:%.*]] = add i64 [[IDX_I]], [[J]]
; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i64 [[J]], 1
; CHECK-NEXT:    [[ARRAYIDXD:%.*]] = getelementptr inbounds i32, ptr [[D]], i64 [[IDX]]
; CHECK-NEXT:    [[ARRAYIDXE:%.*]] = getelementptr inbounds i32, ptr [[E]], i64 [[IDX]]
; CHECK-NEXT:    [[LOADE:%.*]] = load i32, ptr [[ARRAYIDXE]], align 4
; CHECK-NEXT:    [[ARRAYIDXF:%.*]] = getelementptr inbounds i32, ptr [[F]], i64 [[IDX]]
; CHECK-NEXT:    [[LOADF:%.*]] = load i32, ptr [[ARRAYIDXF]], align 4
; CHECK-NEXT:    [[MULS2:%.*]] = mul i32 [[LOADE]], [[LOADF]]
; CHECK-NEXT:    store i32 [[MULS2]], ptr [[ARRAYIDXD]], align 4
; CHECK-NEXT:    [[EXITCOND_J:%.*]] = icmp eq i64 [[J_NEXT]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_J]], label %[[FOR_J_END:.*]], label %[[FOR_J_BODY]]
; CHECK:       [[FOR_J_END]]:
; CHECK-NEXT:    br label %[[FOR_I_INC]]
; CHECK:       [[FOR_I_INC]]:
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
; CHECK-NEXT:    br label %[[FOR_I_HEADER]]
; CHECK:       [[FOR_END]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %for.i.header

for.i.header:                                     ; preds = %for.i.inc, %entry
  %i = phi i64 [ 0, %entry ], [ %i.next, %for.i.inc ]
  %i.cmp = icmp slt i64 %i, %N
  br i1 %i.cmp, label %for.j.preheader, label %for.end

for.j.preheader:                                  ; preds = %for.i.header
  br label %for.j.body

for.j.body:                                       ; preds = %for.j.body, %for.j.preheader
  %j = phi i64 [ 0, %for.j.preheader ], [ %j.next, %for.j.body ]

  %idx.i = mul i64 %i, %M
  %idx = add i64 %idx.i, %j

  ; Statement 1: A[i][j+1] = A[i][j] + B[i][j] + C[i][j]
  %arrayidxA = getelementptr inbounds i32, ptr %A, i64 %idx
  %loadA = load i32, ptr %arrayidxA, align 4

  %arrayidxB = getelementptr inbounds i32, ptr %B, i64 %idx
  %loadB = load i32, ptr %arrayidxB, align 4

  %arrayidxC = getelementptr inbounds i32, ptr %C, i64 %idx
  %loadC = load i32, ptr %arrayidxC, align 4

  %addS1 = add i32 %loadB, %loadC
  %addWithDep = add i32 %addS1, %loadA

  %j.next = add nuw nsw i64 %j, 1
  %idx.next = add i64 %idx, 1
  %arrayidxA_next = getelementptr inbounds i32, ptr %A, i64 %idx.next
  store i32 %addWithDep, ptr %arrayidxA_next, align 4

  ; Statement 2: D[i][j] = E[i][j] * F[i][j]
  %arrayidxD = getelementptr inbounds i32, ptr %D, i64 %idx
  %arrayidxE = getelementptr inbounds i32, ptr %E, i64 %idx
  %loadE = load i32, ptr %arrayidxE, align 4

  %arrayidxF = getelementptr inbounds i32, ptr %F, i64 %idx
  %loadF = load i32, ptr %arrayidxF, align 4

  %mulS2 = mul i32 %loadE, %loadF
  store i32 %mulS2, ptr %arrayidxD, align 4

  %exitcond.j = icmp eq i64 %j.next, %M
  br i1 %exitcond.j, label %for.j.end, label %for.j.body

for.j.end:                                        ; preds = %for.j.body
  br label %for.i.inc

for.i.inc:                                        ; preds = %for.j.end
  %i.next = add nuw nsw i64 %i, 1
  br label %for.i.header

for.end:                                          ; preds = %for.i.header
  ret void
}