1; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
2;; We test profitability model in these test cases.
3
4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
5target triple = "x86_64-unknown-linux-gnu"
6
7@A = common global [100 x [100 x i32]] zeroinitializer
8@B = common global [100 x [100 x i32]] zeroinitializer
9
10;;---------------------------------------Test case 01---------------------------------
11;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
12;;   for(int i=1;i<N;i++)
13;;     for(int j=1;j<N;j++)
14;;       A[j][i] = A[j - 1][i] + B[j][i];
15
16define void @interchange_01(i32 %N) {
17entry:
18  %cmp27 = icmp sgt i32 %N, 1
19  br i1 %cmp27, label %for.cond1.preheader.lr.ph, label %for.end16
20
21for.cond1.preheader.lr.ph:
22  %0 = add i32 %N, -1
23  br label %for.body3.preheader
24
25for.body3.preheader:
26  %indvars.iv30 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next31, %for.inc14 ]
27  br label %for.body3
28
29for.body3:
30  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ]
31  %1 = add nsw i64 %indvars.iv, -1
32  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %indvars.iv30
33  %2 = load i32, i32* %arrayidx5
34  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv, i64 %indvars.iv30
35  %3 = load i32, i32* %arrayidx9
36  %add = add nsw i32 %3, %2
37  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv30
38  store i32 %add, i32* %arrayidx13
39  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
40  %lftr.wideiv = trunc i64 %indvars.iv to i32
41  %exitcond = icmp eq i32 %lftr.wideiv, %0
42  br i1 %exitcond, label %for.inc14, label %for.body3
43
44for.inc14:
45  %indvars.iv.next31 = add nuw nsw i64 %indvars.iv30, 1
46  %lftr.wideiv32 = trunc i64 %indvars.iv30 to i32
47  %exitcond33 = icmp eq i32 %lftr.wideiv32, %0
48  br i1 %exitcond33, label %for.end16, label %for.body3.preheader
49
50for.end16:
51  ret void
52}
53;; Here we are checking partial .ll to check if loop are interchanged.
54; CHECK-LABEL: @interchange_01
55; CHECK:  for.body3.preheader:                              ; preds = %for.inc14, %for.cond1.preheader.lr.ph
56; CHECK:    %indvars.iv30 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next31, %for.inc14 ]
57; CHECK:    br label %for.body3.split2
58
59; CHECK:  for.body3.preheader1:                             ; preds = %entry
60; CHECK:    br label %for.body3
61
62; CHECK:  for.body3:                                        ; preds = %for.body3.preheader1, %for.body3.split
63; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3.split ], [ 1, %for.body3.preheader1 ]
64; CHECK:    br label %for.cond1.preheader.lr.ph
65
66; CHECK:  for.body3.split2:                                 ; preds = %for.body3.preheader
67; CHECK:    %1 = add nsw i64 %indvars.iv, -1
68; CHECK:    %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %indvars.iv30
69; CHECK:    %2 = load i32, i32* %arrayidx5
70; CHECK:    %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv, i64 %indvars.iv30
71; CHECK:    %3 = load i32, i32* %arrayidx9
72; CHECK:    %add = add nsw i32 %3, %2
73; CHECK:    %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv30
74; CHECK:    store i32 %add, i32* %arrayidx13
75; CHECK:    br label %for.inc14
76
77
78;; ---------------------------------------Test case 02---------------------------------
79;; Check loop interchange profitability model.
80;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some
81;; arithmetic operation on them.
82;;   for(int i=1;i<N;i++)
83;;    for(int j=1;j<N;j++)
84;;       A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];
85
86define void @interchange_02(i32 %N) {
87entry:
88  %cmp32 = icmp sgt i32 %N, 1
89  br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end21
90
91for.cond1.preheader.lr.ph:
92  %0 = add i32 %N, -1
93  br label %for.body3.lr.ph
94
95for.body3.lr.ph:
96  %indvars.iv35 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next36, %for.inc19 ]
97  %1 = add nsw i64 %indvars.iv35, -1
98  br label %for.body3
99
100for.body3:
101  %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
102  %2 = add nsw i64 %indvars.iv, -1
103  %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %2, i64 %1
104  %3 = load i32, i32* %arrayidx6
105  %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %2, i64 %1
106  %4 = load i32, i32* %arrayidx12
107  %add = add nsw i32 %4, %3
108  store i32 %add, i32* %arrayidx6
109  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
110  %lftr.wideiv = trunc i64 %indvars.iv to i32
111  %exitcond = icmp eq i32 %lftr.wideiv, %0
112  br i1 %exitcond, label %for.inc19, label %for.body3
113
114for.inc19:
115  %indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 1
116  %lftr.wideiv38 = trunc i64 %indvars.iv35 to i32
117  %exitcond39 = icmp eq i32 %lftr.wideiv38, %0
118  br i1 %exitcond39, label %for.end21, label %for.body3.lr.ph
119
120for.end21:
121  ret void
122}
123; CHECK-LABEL: @interchange_02
124; CHECK:  for.body3.lr.ph:                                  ; preds = %for.inc19, %for.cond1.preheader.lr.ph
125; CHECK:    %indvars.iv35 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next36, %for.inc19 ]
126; CHECK:    %0 = add nsw i64 %indvars.iv35, -1
127; CHECK:    br label %for.body3.split1
128
129; CHECK:  for.body3.preheader:                              ; preds = %entry
130; CHECK:    %1 = add i32 %N, -1
131; CHECK:    br label %for.body3
132
133; CHECK:  for.body3:                                        ; preds = %for.body3.preheader, %for.body3.split
134; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3.split ], [ 1, %for.body3.preheader ]
135; CHECK:    br label %for.cond1.preheader.lr.ph
136
137; CHECK:  for.body3.split1:                                 ; preds = %for.body3.lr.ph
138; CHECK:    %2 = add nsw i64 %indvars.iv, -1
139; CHECK:    %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %2, i64 %0
140; CHECK:    %3 = load i32, i32* %arrayidx6
141; CHECK:    %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %2, i64 %0
142; CHECK:    %4 = load i32, i32* %arrayidx12
143; CHECK:    %add = add nsw i32 %4, %3
144; CHECK:    store i32 %add, i32* %arrayidx6
145; CHECK:    br label %for.inc19
146
147
148;;---------------------------------------Test case 03---------------------------------
149;; Loops interchange is not profitable.
150;;   for(int i=1;i<N;i++)
151;;     for(int j=1;j<N;j++)
152;;       A[i-1][j-1] = A[i - 1][j-1] + B[i][j];
153
154define void @interchange_03(i32 %N){
155entry:
156  %cmp31 = icmp sgt i32 %N, 1
157  br i1 %cmp31, label %for.cond1.preheader.lr.ph, label %for.end19
158
159for.cond1.preheader.lr.ph:
160  %0 = add i32 %N, -1
161  br label %for.body3.lr.ph
162
163for.body3.lr.ph:
164  %indvars.iv34 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next35, %for.inc17 ]
165  %1 = add nsw i64 %indvars.iv34, -1
166  br label %for.body3
167
168for.body3:
169  %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
170  %2 = add nsw i64 %indvars.iv, -1
171  %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %2
172  %3 = load i32, i32* %arrayidx6
173  %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv34, i64 %indvars.iv
174  %4 = load i32, i32* %arrayidx10
175  %add = add nsw i32 %4, %3
176  store i32 %add, i32* %arrayidx6
177  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
178  %lftr.wideiv = trunc i64 %indvars.iv to i32
179  %exitcond = icmp eq i32 %lftr.wideiv, %0
180  br i1 %exitcond, label %for.inc17, label %for.body3
181
182for.inc17:
183  %indvars.iv.next35 = add nuw nsw i64 %indvars.iv34, 1
184  %lftr.wideiv37 = trunc i64 %indvars.iv34 to i32
185  %exitcond38 = icmp eq i32 %lftr.wideiv37, %0
186  br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph
187
188for.end19:
189  ret void
190}
191
192; CHECK-LABEL: @interchange_03
193; CHECK:  for.body3.lr.ph:
194; CHECK:    %indvars.iv34 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next35, %for.inc17 ]
195; CHECK:    %1 = add nsw i64 %indvars.iv34, -1
196; CHECK:    br label %for.body3.preheader
197; CHECK:  for.body3.preheader:
198; CHECK:    br label %for.body3
199; CHECK:  for.body3:
200; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ]
201; CHECK:    %2 = add nsw i64 %indvars.iv, -1
202; CHECK:    %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %2
203; CHECK:    %3 = load i32, i32* %arrayidx6
204; CHECK:    %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv34, i64 %indvars.iv
205; CHECK:    %4 = load i32, i32* %arrayidx10
206