1; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
2; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
3; RUN: FileCheck -input-file %t %s
4
5; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
6; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange \
7; RUN:     -da-disable-delinearization-checks
8; RUN: FileCheck --check-prefix=DELIN -input-file %t %s
9
10;; We test profitability model in these test cases.
11
12target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
13target triple = "x86_64-unknown-linux-gnu"
14
15@A = common global [100 x [100 x i32]] zeroinitializer
16@B = common global [100 x [100 x i32]] zeroinitializer
17
18;;---------------------------------------Test case 01---------------------------------
19;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
20;;   for(int i=1;i<100;i++)
21;;     for(int j=1;j<100;j++)
22;;       A[j][i] = A[j - 1][i] + B[j][i];
23
24; CHECK:      Name:            Dependence
25; CHECK-NEXT: Function:        interchange_01
26
27; DELIN:      Name:            Interchanged
28; DELIN-NEXT: Function:        interchange_01
29
30define void @interchange_01() {
31entry:
32  br label %for2.preheader
33
34for2.preheader:
35  %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
36  br label %for2
37
38for2:
39  %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
40  %j.prev = add nsw i64 %j,  -1
41  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i30
42  %lv1 = load i32, i32* %arrayidx5
43  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j,  i64 %i30
44  %lv2 = load i32, i32* %arrayidx9
45  %add = add nsw i32 %lv1, %lv2
46  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j,  i64 %i30
47  store i32 %add, i32* %arrayidx13
48  %i.next = add nuw nsw i64 %j,  1
49  %exitcond = icmp eq i64 %j,  99
50  br i1 %exitcond, label %for1.inc14, label %for2
51
52for1.inc14:
53  %i.next31 = add nuw nsw i64 %i30, 1
54  %exitcond33 = icmp eq i64 %i30, 99
55  br i1 %exitcond33, label %for.end16, label %for2.preheader
56
57for.end16:
58  ret void
59}
60
61;; ---------------------------------------Test case 02---------------------------------
62;; Check loop interchange profitability model.
63;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some
64;; arithmetic operation on them.
65;;   for(int i=1;i<N;i++)
66;;    for(int j=1;j<N;j++)
67;;       A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];
68
69; CHECK:      Name:            Interchanged
70; CHECK-NEXT: Function:        interchange_02
71define void @interchange_02() {
72entry:
73  br label %for1.header
74
75for1.header:
76  %i35 = phi i64 [ 1, %entry ], [ %i.next36, %for1.inc19 ]
77  %i.prev = add nsw i64 %i35, -1
78  br label %for2
79
80for2:
81  %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
82  %j.prev = add nsw i64 %j,  -1
83  %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i.prev
84  %lv1 = load i32, i32* %arrayidx6
85  %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j.prev, i64 %i.prev
86  %lv2 = load i32, i32* %arrayidx12
87  %add = add nsw i32 %lv1, %lv2
88  store i32 %add, i32* %arrayidx6
89  %i.next = add nuw nsw i64 %j,  1
90  %exitcond = icmp eq i64 %j,  99
91  br i1 %exitcond, label %for1.inc19, label %for2
92
93for1.inc19:
94  %i.next36 = add nuw nsw i64 %i35, 1
95  %exitcond39 = icmp eq i64 %i35, 99
96  br i1 %exitcond39, label %for.end21, label %for1.header
97
98for.end21:
99  ret void
100}
101
102;;---------------------------------------Test case 03---------------------------------
103;; Loops interchange is not profitable.
104;;   for(int i=1;i<100;i++)
105;;     for(int j=1;j<100;j++)
106;;       A[i-1][j-1] = A[i - 1][j-1] + B[i][j];
107
108; CHECK:      Name:            InterchangeNotProfitable
109; CHECK-NEXT: Function:        interchange_03
110define void @interchange_03(){
111entry:
112  br label %for1.header
113
114for1.header:
115  %i34 = phi i64 [ 1, %entry ], [ %i.next35, %for1.inc17 ]
116  %i.prev = add nsw i64 %i34, -1
117  br label %for2
118
119for2:
120  %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
121  %j.prev = add nsw i64 %j, -1
122  %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %i.prev, i64 %j.prev
123  %lv1 = load i32, i32* %arrayidx6
124  %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %i34, i64 %j
125  %lv2 = load i32, i32* %arrayidx10
126  %add = add nsw i32 %lv1, %lv2
127  store i32 %add, i32* %arrayidx6
128  %i.next = add nuw nsw i64 %j,  1
129  %exitcond = icmp eq i64 %j,  99
130  br i1 %exitcond, label %for1.inc17, label %for2
131
132for1.inc17:
133  %i.next35 = add nuw nsw i64 %i34, 1
134  %exitcond38 = icmp eq i64 %i34, 99
135  br i1 %exitcond38, label %for.end19, label %for1.header
136
137for.end19:
138  ret void
139}
140
141;; Loops should not be interchanged in this case as it is not profitable.
142;;  for(int i=0;i<100;i++)
143;;    for(int j=0;j<100;j++)
144;;      A[i][j] = A[i][j]+k;
145
146; CHECK:      Name:            InterchangeNotProfitable
147; CHECK-NEXT: Function:        interchange_04
148define void @interchange_04(i32 %k) {
149entry:
150  br label %for.cond1.preheader
151
152for.cond1.preheader:
153  %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]
154  br label %for.body3
155
156for.body3:
157  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
158  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv
159  %0 = load i32, i32* %arrayidx5
160  %add = add nsw i32 %0, %k
161  store i32 %add, i32* %arrayidx5
162  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
163  %exitcond = icmp eq i64 %indvars.iv.next, 100
164  br i1 %exitcond, label %for.inc10, label %for.body3
165
166for.inc10:
167  %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
168  %exitcond23 = icmp eq i64 %indvars.iv.next22, 100
169  br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
170
171for.end12:
172  ret void
173}
174