llvm/test/Transforms/LoopInterchange/inner-only-reductions.ll

; 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 -S | FileCheck %s

; Both tests should be rejected as interchange candidates. For now, they are
; rejected for dependence analysis reasons, but that's because support for 'S'
; scalar dependencies was removed. When that is properly, the inner loop only
; reductions should still not be supported currently, see discussion at D53027
; for more information on the required checks.

@A = common global [500 x [500 x i32]] zeroinitializer
@X = common global i32 0
@B = common global [500 x [500 x i32]] zeroinitializer
@Y = common global i32 0

;; global X

;;  for( int i=1;i<N;i++)
;;    for( int j=1;j<N;j++)
;;      X+=A[j][i];

define void @reduction_01(i32 %N) {
; CHECK-LABEL: define void @reduction_01(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP16:%.*]] = icmp sgt i32 [[N]], 1
; CHECK-NEXT:    br i1 [[CMP16]], label %[[FOR_BODY3_LR_PH_PREHEADER:.*]], label %[[FOR_END8:.*]]
; CHECK:       [[FOR_BODY3_LR_PH_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY3_LR_PH:.*]]
; CHECK:       [[FOR_BODY3_LR_PH]]:
; CHECK-NEXT:    [[INDVARS_IV18:%.*]] = phi i64 [ [[INDVARS_IV_NEXT19:%.*]], %[[FOR_COND1_FOR_INC6_CRIT_EDGE:.*]] ], [ 1, %[[FOR_BODY3_LR_PH_PREHEADER]] ]
; CHECK-NEXT:    [[X_PROMOTED:%.*]] = load i32, ptr @X, align 4
; CHECK-NEXT:    br label %[[FOR_BODY3:.*]]
; CHECK:       [[FOR_BODY3]]:
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, %[[FOR_BODY3_LR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ]
; CHECK-NEXT:    [[ADD15:%.*]] = phi i32 [ [[X_PROMOTED]], %[[FOR_BODY3_LR_PH]] ], [ [[ADD:%.*]], %[[FOR_BODY3]] ]
; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV18]]
; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[ADD15]], [[TMP0]]
; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR_COND1_FOR_INC6_CRIT_EDGE]], label %[[FOR_BODY3]]
; CHECK:       [[FOR_COND1_FOR_INC6_CRIT_EDGE]]:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], %[[FOR_BODY3]] ]
; CHECK-NEXT:    store i32 [[ADD_LCSSA]], ptr @X, align 4
; CHECK-NEXT:    [[INDVARS_IV_NEXT19]] = add nuw nsw i64 [[INDVARS_IV18]], 1
; CHECK-NEXT:    [[LFTR_WIDEIV20:%.*]] = trunc i64 [[INDVARS_IV_NEXT19]] to i32
; CHECK-NEXT:    [[EXITCOND21:%.*]] = icmp eq i32 [[LFTR_WIDEIV20]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND21]], label %[[FOR_END8_LOOPEXIT:.*]], label %[[FOR_BODY3_LR_PH]]
; CHECK:       [[FOR_END8_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[FOR_END8]]
; CHECK:       [[FOR_END8]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp16 = icmp sgt i32 %N, 1
  br i1 %cmp16, label %for.body3.lr.ph, label %for.end8

for.body3.lr.ph:                                  ; preds = %for.cond1.for.inc6_crit_edge, %entry
  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
  %X.promoted = load i32, ptr @X
  br label %for.body3

for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
  %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
  %add15 = phi i32 [ %X.promoted, %for.body3.lr.ph ], [ %add, %for.body3 ]
  %arrayidx5 = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18
  %0 = load i32, ptr %arrayidx5
  %add = add nsw i32 %add15, %0
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  %exitcond = icmp eq i32 %lftr.wideiv, %N
  br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body3

for.cond1.for.inc6_crit_edge:                     ; preds = %for.body3
  %add.lcssa = phi i32 [ %add, %for.body3 ]
  store i32 %add.lcssa, ptr @X
  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
  %lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32
  %exitcond21 = icmp eq i32 %lftr.wideiv20, %N
  br i1 %exitcond21, label %for.end8, label %for.body3.lr.ph

for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
  ret void
}

;; Not tightly nested. Do not interchange.
;;  for( int i=1;i<N;i++)
;;    for( int j=1;j<N;j++) {
;;      for( int k=1;k<N;k++) {
;;        X+=A[k][j];
;;      }
;;      Y+=B[j][i];
;;    }

;; Not tightly nested. Do not interchange.
;; Not interchanged hence the phi's in the inner loop will not be split.

define void @reduction_03(i32 %N) {
; CHECK-LABEL: define void @reduction_03(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP35:%.*]] = icmp sgt i32 [[N]], 1
; CHECK-NEXT:    br i1 [[CMP35]], label %[[FOR_COND4_PREHEADER_LR_PH_PREHEADER:.*]], label %[[FOR_END19:.*]]
; CHECK:       [[FOR_COND4_PREHEADER_LR_PH_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_COND4_PREHEADER_LR_PH:.*]]
; CHECK:       [[FOR_COND4_PREHEADER_LR_PH]]:
; CHECK-NEXT:    [[INDVARS_IV41:%.*]] = phi i64 [ [[INDVARS_IV_NEXT42:%.*]], %[[FOR_COND1_FOR_INC17_CRIT_EDGE:.*]] ], [ 1, %[[FOR_COND4_PREHEADER_LR_PH_PREHEADER]] ]
; CHECK-NEXT:    [[Y_PROMOTED:%.*]] = load i32, ptr @Y, align 4
; CHECK-NEXT:    br label %[[FOR_BODY6_LR_PH:.*]]
; CHECK:       [[FOR_BODY6_LR_PH]]:
; CHECK-NEXT:    [[INDVARS_IV37:%.*]] = phi i64 [ 1, %[[FOR_COND4_PREHEADER_LR_PH]] ], [ [[INDVARS_IV_NEXT38:%.*]], %[[FOR_COND4_FOR_END_CRIT_EDGE:.*]] ]
; CHECK-NEXT:    [[ADD1334:%.*]] = phi i32 [ [[Y_PROMOTED]], %[[FOR_COND4_PREHEADER_LR_PH]] ], [ [[ADD13:%.*]], %[[FOR_COND4_FOR_END_CRIT_EDGE]] ]
; CHECK-NEXT:    [[X_PROMOTED:%.*]] = load i32, ptr @X, align 4
; CHECK-NEXT:    br label %[[FOR_BODY6:.*]]
; CHECK:       [[FOR_BODY6]]:
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, %[[FOR_BODY6_LR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY6]] ]
; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV37]]
; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX8]], align 4
; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR_COND4_FOR_END_CRIT_EDGE]], label %[[FOR_BODY6]]
; CHECK:       [[FOR_COND4_FOR_END_CRIT_EDGE]]:
; CHECK-NEXT:    [[ARRAYIDX12:%.*]] = getelementptr inbounds [500 x [500 x i32]], ptr @B, i64 0, i64 [[INDVARS_IV37]], i64 [[INDVARS_IV41]]
; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX12]], align 4
; CHECK-NEXT:    [[ADD13]] = add nsw i32 [[ADD1334]], [[TMP1]]
; CHECK-NEXT:    [[INDVARS_IV_NEXT38]] = add nuw nsw i64 [[INDVARS_IV37]], 1
; CHECK-NEXT:    [[LFTR_WIDEIV39:%.*]] = trunc i64 [[INDVARS_IV_NEXT38]] to i32
; CHECK-NEXT:    [[EXITCOND40:%.*]] = icmp eq i32 [[LFTR_WIDEIV39]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND40]], label %[[FOR_COND1_FOR_INC17_CRIT_EDGE]], label %[[FOR_BODY6_LR_PH]]
; CHECK:       [[FOR_COND1_FOR_INC17_CRIT_EDGE]]:
; CHECK-NEXT:    [[ADD13_LCSSA:%.*]] = phi i32 [ [[ADD13]], %[[FOR_COND4_FOR_END_CRIT_EDGE]] ]
; CHECK-NEXT:    store i32 [[ADD13_LCSSA]], ptr @Y, align 4
; CHECK-NEXT:    [[INDVARS_IV_NEXT42]] = add nuw nsw i64 [[INDVARS_IV41]], 1
; CHECK-NEXT:    [[LFTR_WIDEIV43:%.*]] = trunc i64 [[INDVARS_IV_NEXT42]] to i32
; CHECK-NEXT:    [[EXITCOND44:%.*]] = icmp eq i32 [[LFTR_WIDEIV43]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND44]], label %[[FOR_END19_LOOPEXIT:.*]], label %[[FOR_COND4_PREHEADER_LR_PH]]
; CHECK:       [[FOR_END19_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[FOR_END19]]
; CHECK:       [[FOR_END19]]:
; CHECK-NEXT:    ret void
;
entry:
  %cmp35 = icmp sgt i32 %N, 1
  br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19

for.cond4.preheader.lr.ph:                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
  %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]
  %Y.promoted = load i32, ptr @Y
  br label %for.body6.lr.ph

for.body6.lr.ph:                                  ; preds = %for.cond4.for.end_crit_edge, %for.cond4.preheader.lr.ph
  %indvars.iv37 = phi i64 [ 1, %for.cond4.preheader.lr.ph ], [ %indvars.iv.next38, %for.cond4.for.end_crit_edge ]
  %add1334 = phi i32 [ %Y.promoted, %for.cond4.preheader.lr.ph ], [ %add13, %for.cond4.for.end_crit_edge ]
  %X.promoted = load i32, ptr @X
  br label %for.body6

for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
  %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
  %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 %indvars.iv, i64 %indvars.iv37
  %0 = load i32, ptr %arrayidx8
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  %exitcond = icmp eq i32 %lftr.wideiv, %N
  br i1 %exitcond, label %for.cond4.for.end_crit_edge, label %for.body6

for.cond4.for.end_crit_edge:                      ; preds = %for.body6
  %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], ptr @B, i64 0, i64 %indvars.iv37, i64 %indvars.iv41
  %1 = load i32, ptr %arrayidx12
  %add13 = add nsw i32 %add1334, %1
  %indvars.iv.next38 = add nuw nsw i64 %indvars.iv37, 1
  %lftr.wideiv39 = trunc i64 %indvars.iv.next38 to i32
  %exitcond40 = icmp eq i32 %lftr.wideiv39, %N
  br i1 %exitcond40, label %for.cond1.for.inc17_crit_edge, label %for.body6.lr.ph

for.cond1.for.inc17_crit_edge:                    ; preds = %for.cond4.for.end_crit_edge
  %add13.lcssa = phi i32 [ %add13, %for.cond4.for.end_crit_edge ]
  store i32 %add13.lcssa, ptr @Y
  %indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1
  %lftr.wideiv43 = trunc i64 %indvars.iv.next42 to i32
  %exitcond44 = icmp eq i32 %lftr.wideiv43, %N
  br i1 %exitcond44, label %for.end19, label %for.cond4.preheader.lr.ph

for.end19:                                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
  ret void
}