| 1 |
; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t -S \ |
| 2 |
; RUN: -verify-dom-info -verify-loop-info -verify-loop-lcssa 2>&1 | FileCheck -check-prefix=IR %s |
| 3 |
; RUN: FileCheck --input-file=%t %s |
| 4 |
|
| 5 |
; Both tests should be rejected as interchange candidates. For now, they are |
| 6 |
; rejected for dependence analysis reasons, but that's because support for 'S' |
| 7 |
; scalar dependencies was removed. When that is properly, the inner loop only |
| 8 |
; reductions should still not be supported currently, see discussion at D53027 |
| 9 |
; for more information on the required checks. |
| 10 |
|
| 11 |
@A = common global [500 x [500 x i32]] zeroinitializer |
| 12 |
@X = common global i32 0 |
| 13 |
@B = common global [500 x [500 x i32]] zeroinitializer |
| 14 |
@Y = common global i32 0 |
| 15 |
|
| 16 |
;; global X |
| 17 |
|
| 18 |
;; for( int i=1;i<N;i++) |
| 19 |
;; for( int j=1;j<N;j++) |
| 20 |
;; X+=A[j][i]; |
| 21 |
|
| 22 |
; CHECK: --- !Missed |
| 23 |
; CHECK-NEXT: Pass: loop-interchange |
| 24 |
; CHECK-NEXT: Name: Dependence |
| 25 |
; CHECK-NEXT: Function: reduction_01 |
| 26 |
|
| 27 |
; IR-LABEL: @reduction_01( |
| 28 |
; IR-NOT: split |
| 29 |
|
| 30 |
define void @reduction_01(i32 %N) { |
| 31 |
entry: |
| 32 |
%cmp16 = icmp sgt i32 %N, 1 |
| 33 |
br i1 %cmp16, label %for.body3.lr.ph, label %for.end8 |
| 34 |
|
| 35 |
for.body3.lr.ph: ; preds = %for.cond1.for.inc6_crit_edge, %entry |
| 36 |
%indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ] |
| 37 |
%X.promoted = load i32, ptr @X |
| 38 |
br label %for.body3 |
| 39 |
|
| 40 |
for.body3: ; preds = %for.body3, %for.body3.lr.ph |
| 41 |
%indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ] |
| 42 |
%add15 = phi i32 [ %X.promoted, %for.body3.lr.ph ], [ %add, %for.body3 ] |
| 43 |
%arrayidx5 = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18 |
| 44 |
%0 = load i32, ptr %arrayidx5 |
| 45 |
%add = add nsw i32 %add15, %0 |
| 46 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 47 |
%lftr.wideiv = trunc i64 %indvars.iv.next to i32 |
| 48 |
%exitcond = icmp eq i32 %lftr.wideiv, %N |
| 49 |
br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body3 |
| 50 |
|
| 51 |
for.cond1.for.inc6_crit_edge: ; preds = %for.body3 |
| 52 |
%add.lcssa = phi i32 [ %add, %for.body3 ] |
| 53 |
store i32 %add.lcssa, ptr @X |
| 54 |
%indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1 |
| 55 |
%lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32 |
| 56 |
%exitcond21 = icmp eq i32 %lftr.wideiv20, %N |
| 57 |
br i1 %exitcond21, label %for.end8, label %for.body3.lr.ph |
| 58 |
|
| 59 |
for.end8: ; preds = %for.cond1.for.inc6_crit_edge, %entry |
| 60 |
ret void |
| 61 |
} |
| 62 |
|
| 63 |
;; Not tightly nested. Do not interchange. |
| 64 |
;; for( int i=1;i<N;i++) |
| 65 |
;; for( int j=1;j<N;j++) { |
| 66 |
;; for( int k=1;k<N;k++) { |
| 67 |
;; X+=A[k][j]; |
| 68 |
;; } |
| 69 |
;; Y+=B[j][i]; |
| 70 |
;; } |
| 71 |
|
| 72 |
;; Not tightly nested. Do not interchange. |
| 73 |
;; Not interchanged hence the phi's in the inner loop will not be split. |
| 74 |
|
| 75 |
; CHECK: --- !Missed |
| 76 |
; CHECK-NEXT: Pass: loop-interchange |
| 77 |
; CHECK-NEXT: Name: UnsupportedPHIOuter |
| 78 |
; CHECK-NEXT: Function: reduction_03 |
| 79 |
|
| 80 |
; IR-LABEL: @reduction_03( |
| 81 |
; IR-NOT: split |
| 82 |
|
| 83 |
define void @reduction_03(i32 %N) { |
| 84 |
entry: |
| 85 |
%cmp35 = icmp sgt i32 %N, 1 |
| 86 |
br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19 |
| 87 |
|
| 88 |
for.cond4.preheader.lr.ph: ; preds = %for.cond1.for.inc17_crit_edge, %entry |
| 89 |
%indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ] |
| 90 |
%Y.promoted = load i32, ptr @Y |
| 91 |
br label %for.body6.lr.ph |
| 92 |
|
| 93 |
for.body6.lr.ph: ; preds = %for.cond4.for.end_crit_edge, %for.cond4.preheader.lr.ph |
| 94 |
%indvars.iv37 = phi i64 [ 1, %for.cond4.preheader.lr.ph ], [ %indvars.iv.next38, %for.cond4.for.end_crit_edge ] |
| 95 |
%add1334 = phi i32 [ %Y.promoted, %for.cond4.preheader.lr.ph ], [ %add13, %for.cond4.for.end_crit_edge ] |
| 96 |
%X.promoted = load i32, ptr @X |
| 97 |
br label %for.body6 |
| 98 |
|
| 99 |
for.body6: ; preds = %for.body6, %for.body6.lr.ph |
| 100 |
%indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ] |
| 101 |
%arrayidx8 = getelementptr inbounds [500 x [500 x i32]], ptr @A, i64 0, i64 %indvars.iv, i64 %indvars.iv37 |
| 102 |
%0 = load i32, ptr %arrayidx8 |
| 103 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 104 |
%lftr.wideiv = trunc i64 %indvars.iv.next to i32 |
| 105 |
%exitcond = icmp eq i32 %lftr.wideiv, %N |
| 106 |
br i1 %exitcond, label %for.cond4.for.end_crit_edge, label %for.body6 |
| 107 |
|
| 108 |
for.cond4.for.end_crit_edge: ; preds = %for.body6 |
| 109 |
%arrayidx12 = getelementptr inbounds [500 x [500 x i32]], ptr @B, i64 0, i64 %indvars.iv37, i64 %indvars.iv41 |
| 110 |
%1 = load i32, ptr %arrayidx12 |
| 111 |
%add13 = add nsw i32 %add1334, %1 |
| 112 |
%indvars.iv.next38 = add nuw nsw i64 %indvars.iv37, 1 |
| 113 |
%lftr.wideiv39 = trunc i64 %indvars.iv.next38 to i32 |
| 114 |
%exitcond40 = icmp eq i32 %lftr.wideiv39, %N |
| 115 |
br i1 %exitcond40, label %for.cond1.for.inc17_crit_edge, label %for.body6.lr.ph |
| 116 |
|
| 117 |
for.cond1.for.inc17_crit_edge: ; preds = %for.cond4.for.end_crit_edge |
| 118 |
%add13.lcssa = phi i32 [ %add13, %for.cond4.for.end_crit_edge ] |
| 119 |
store i32 %add13.lcssa, ptr @Y |
| 120 |
%indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1 |
| 121 |
%lftr.wideiv43 = trunc i64 %indvars.iv.next42 to i32 |
| 122 |
%exitcond44 = icmp eq i32 %lftr.wideiv43, %N |
| 123 |
br i1 %exitcond44, label %for.end19, label %for.cond4.preheader.lr.ph |
| 124 |
|
| 125 |
for.end19: ; preds = %for.cond1.for.inc17_crit_edge, %entry |
| 126 |
ret void |
| 127 |
} |