Debian Codegraph @

llvm/test/Transforms/LoopInterchange/reductions-across-inner-and-outer-loop.ll

raw
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 -stats 2>&1 | FileCheck %s
3 ; RUN: FileCheck --input-file=%t --check-prefix=REMARKS %s
4
5
6 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
7
8 ; REMARKS: --- !Analysis
9 ; REMARKS-NEXT: Pass: loop-interchange
10 ; REMARKS-NEXT: Name: Dependence
11 ; REMARKS-NEXT: Function: test1
12 ; REMARKS-NEXT: Args:
13 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
14 ; REMARKS-NEXT: ...
15
16 ; REMARKS: --- !Passed
17 ; REMARKS-NEXT: Pass: loop-interchange
18 ; REMARKS-NEXT: Name: Interchanged
19 ; REMARKS-NEXT: Function: test1
20
21 define i64 @test1(ptr %Arr) {
22 ; CHECK-LABEL: @test1(
23 ; CHECK-NEXT: entry:
24 ; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]]
25 ; CHECK: for1.header.preheader:
26 ; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]
27 ; CHECK: for1.header:
28 ; CHECK-NEXT: [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_NEXT24:%.*]], [[FOR1_INC:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
29 ; CHECK-NEXT: [[SUM_INNER:%.*]] = phi i64 [ [[SUM_INC:%.*]], [[FOR1_INC]] ], [ [[SUM_OUTER:%.*]], [[FOR1_HEADER_PREHEADER]] ]
30 ; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]]
31 ; CHECK: for2.preheader:
32 ; CHECK-NEXT: br label [[FOR2:%.*]]
33 ; CHECK: for2:
34 ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_3:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ]
35 ; CHECK-NEXT: [[SUM_OUTER]] = phi i64 [ [[SUM_INC_LCSSA:%.*]], [[FOR2_SPLIT]] ], [ 0, [[FOR2_PREHEADER]] ]
36 ; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]
37 ; CHECK: for2.split1:
38 ; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr [[ARR:%.*]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]]
39 ; CHECK-NEXT: [[LV:%.*]] = load i64, ptr [[ARRAYIDX]], align 4
40 ; CHECK-NEXT: [[SUM_INC]] = add i64 [[SUM_INNER]], [[LV]]
41 ; CHECK-NEXT: [[IV_ORIGINAL:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1
42 ; CHECK-NEXT: [[EXIT1_ORIGINAL:%.*]] = icmp eq i64 [[IV_ORIGINAL]], 100
43 ; CHECK-NEXT: br label [[FOR1_INC]]
44 ; CHECK: for2.split:
45 ; CHECK-NEXT: [[SUM_INC_LCSSA]] = phi i64 [ [[SUM_INC]], %for1.inc ]
46 ; CHECK-NEXT: [[INDVARS_IV_NEXT_3]] = add nuw nsw i64 [[INDVARS_IV]], 1
47 ; CHECK-NEXT: [[EXIT1:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_3]], 100
48 ; CHECK-NEXT: br i1 [[EXIT1]], label [[FOR1_LOOPEXIT:%.*]], label [[FOR2]]
49 ; CHECK: for1.inc:
50 ; CHECK-NEXT: [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 1
51 ; CHECK-NEXT: [[EXIT2:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT24]], 100
52 ; CHECK-NEXT: br i1 [[EXIT2]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]
53 ; CHECK: for1.loopexit:
54 ; CHECK-NEXT: [[SUM_INC_LCSSA2:%.*]] = phi i64 [ [[SUM_INC_LCSSA]], [[FOR2_SPLIT]] ]
55 ; CHECK-NEXT: ret i64 [[SUM_INC_LCSSA2]]
56 ;
57 entry:
58 br label %for1.header
59
60 for1.header: ; preds = %for1.inc, %entry
61 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
62 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
63 br label %for2
64
65 for2: ; preds = %for2, %for1.header
66 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
67 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
68 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
69 %lv = load i64, ptr %arrayidx, align 4
70 %sum.inc = add i64 %sum.inner, %lv
71 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
72 %exit1 = icmp eq i64 %indvars.iv.next.3, 100
73 br i1 %exit1, label %for1.inc, label %for2
74
75 for1.inc: ; preds = %for2
76 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
77 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
78 %exit2 = icmp eq i64 %indvars.iv.next24, 100
79 br i1 %exit2, label %for1.loopexit, label %for1.header
80
81 for1.loopexit: ; preds = %for1.inc
82 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
83 ret i64 %sum.inc.lcssa2
84 }
85
86 ; In this test case, the inner reduction PHI %inner does not involve the outer
87 ; reduction PHI %sum.outer, do not interchange.
88 ; REMARKS: --- !Analysis
89 ; REMARKS-NEXT: Pass: loop-interchange
90 ; REMARKS-NEXT: Name: Dependence
91 ; REMARKS-NEXT: Function: test2
92 ; REMARKS-NEXT: Args:
93 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
94 ; REMARKS-NEXT: ...
95
96 ; REMARKS: --- !Missed
97 ; REMARKS-NEXT: Pass: loop-interchange
98 ; REMARKS-NEXT: Name: UnsupportedPHIOuter
99 ; REMARKS-NEXT: Function: test2
100
101 define i64 @test2(ptr %Arr) {
102 entry:
103 br label %for1.header
104
105 for1.header: ; preds = %for1.inc, %entry
106 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
107 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
108 br label %for2
109
110 for2: ; preds = %for2, %for1.header
111 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
112 %inner = phi i64 [ %indvars.iv23, %for1.header ], [ %sum.inc, %for2 ]
113 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
114 %lv = load i64, ptr %arrayidx, align 4
115 %sum.inc = add i64 %inner, %lv
116 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
117 %exit1 = icmp eq i64 %indvars.iv.next.3, 100
118 br i1 %exit1, label %for1.inc, label %for2
119
120 for1.inc: ; preds = %for2
121 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
122 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
123 %exit2 = icmp eq i64 %indvars.iv.next24, 100
124 br i1 %exit2, label %for1.loopexit, label %for1.header
125
126 for1.loopexit: ; preds = %for1.inc
127 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
128 ret i64 %sum.inc.lcssa2
129 }
130
131 ; Check that we do not interchange if there is an additional instruction
132 ; between the outer and inner reduction PHIs.
133 ; REMARKS: --- !Analysis
134 ; REMARKS-NEXT: Pass: loop-interchange
135 ; REMARKS-NEXT: Name: Dependence
136 ; REMARKS-NEXT: Function: test3
137 ; REMARKS-NEXT: Args:
138 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
139 ; REMARKS-NEXT: ...
140
141 ; REMARKS: --- !Missed
142 ; REMARKS-NEXT: Pass: loop-interchange
143 ; REMARKS-NEXT: Name: UnsupportedPHIOuter
144 ; REMARKS-NEXT: Function: test3
145
146 define i64 @test3(ptr %Arr) {
147 entry:
148 br label %for1.header
149
150 for1.header: ; preds = %for1.inc, %entry
151 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
152 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
153 %so = add i64 %sum.outer, 10
154 br label %for2
155
156 for2: ; preds = %for2, %for1.header
157 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
158 %sum.inner = phi i64 [ %so, %for1.header ], [ %sum.inc, %for2 ]
159 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
160 %lv = load i64, ptr %arrayidx, align 4
161 %sum.inc = add i64 %sum.inner, %lv
162 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
163 %exit1 = icmp eq i64 %indvars.iv.next.3, 100
164 br i1 %exit1, label %for1.inc, label %for2
165
166 for1.inc: ; preds = %for2
167 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
168 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
169 %exit2 = icmp eq i64 %indvars.iv.next24, 100
170 br i1 %exit2, label %for1.loopexit, label %for1.header
171
172 for1.loopexit: ; preds = %for1.inc
173 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
174 ret i64 %sum.inc.lcssa2
175 }
176
177 ; Check that we do not interchange if reduction is stored in an invariant address inside inner loop
178 ; REMARKS: --- !Analysis
179 ; REMARKS-NEXT: Pass: loop-interchange
180 ; REMARKS-NEXT: Name: Dependence
181 ; REMARKS-NEXT: Function: test4
182 ; REMARKS-NEXT: Args:
183 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
184 ; REMARKS-NEXT: ...
185
186 ; REMARKS: --- !Missed
187 ; REMARKS-NEXT: Pass: loop-interchange
188 ; REMARKS-NEXT: Name: Dependence
189 ; REMARKS-NEXT: Function: test4
190
191 define i64 @test4(ptr %Arr, ptr %dst) {
192 entry:
193 %gep.dst = getelementptr inbounds i64, ptr %dst, i64 42
194 br label %for1.header
195
196 for1.header: ; preds = %for1.inc, %entry
197 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
198 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
199 br label %for2
200
201 for2: ; preds = %for2, %for1.header
202 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
203 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
204 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
205 %lv = load i64, ptr %arrayidx, align 4
206 %sum.inc = add i64 %sum.inner, %lv
207 store i64 %sum.inc, ptr %gep.dst, align 4
208 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
209 %exit1 = icmp eq i64 %indvars.iv.next.3, 100
210 br i1 %exit1, label %for1.inc, label %for2
211
212 for1.inc: ; preds = %for2
213 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
214 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
215 %exit2 = icmp eq i64 %indvars.iv.next24, 100
216 br i1 %exit2, label %for1.loopexit, label %for1.header
217
218 for1.loopexit: ; preds = %for1.inc
219 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
220 ret i64 %sum.inc.lcssa2
221 }
222
223 ; Check that we do not interchange or crash if the PHI in the outer loop gets a
224 ; constant from the inner loop.
225 ; REMARKS: --- !Analysis
226 ; REMARKS-NEXT: Pass: loop-interchange
227 ; REMARKS-NEXT: Name: Dependence
228 ; REMARKS-NEXT: Function: test_constant_inner_loop_res
229 ; REMARKS-NEXT: Args:
230 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
231 ; REMARKS-NEXT: ...
232
233 ; REMARKS: --- !Missed
234 ; REMARKS-NEXT: Pass: loop-interchange
235 ; REMARKS-NEXT: Name: UnsupportedPHIOuter
236 ; REMARKS-NEXT: Function: test_constant_inner_loop_res
237
238 define i64 @test_constant_inner_loop_res(ptr %Arr) {
239 entry:
240 br label %for1.header
241
242 for1.header: ; preds = %for1.inc, %entry
243 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
244 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.amend, %for1.inc ]
245 br label %for2
246
247 for2: ; preds = %for2, %for1.header
248 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
249 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
250 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
251 %lv = load i64, ptr %arrayidx, align 4
252 %sum.inc = add i64 %sum.inner, %lv
253 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
254 %exit1 = icmp eq i64 %indvars.iv.next.3, 100
255 br i1 %exit1, label %for1.inc, label %for2
256
257 for1.inc: ; preds = %for2
258 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
259 %const.lcssa = phi i64 [ 0, %for2 ]
260 %sum.inc.amend = add i64 %const.lcssa, %sum.inc.lcssa
261 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
262 %exit2 = icmp eq i64 %indvars.iv.next24, 100
263 br i1 %exit2, label %for1.loopexit, label %for1.header
264
265 for1.loopexit: ; preds = %for1.inc
266 %il.res.lcssa2 = phi i64 [ %sum.inc.amend, %for1.inc ]
267 ret i64 %il.res.lcssa2
268 }
269
270 ; Floating point reductions are interchanged if all the fp instructions
271 ; involved allow reassociation.
272 ; REMARKS: --- !Analysis
273 ; REMARKS-NEXT: Pass: loop-interchange
274 ; REMARKS-NEXT: Name: Dependence
275 ; REMARKS-NEXT: Function: test5
276 ; REMARKS-NEXT: Args:
277 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
278 ; REMARKS-NEXT: ...
279
280 ; REMARKS: --- !Passed
281 ; REMARKS-NEXT: Pass: loop-interchange
282 ; REMARKS-NEXT: Name: Interchanged
283 ; REMARKS-NEXT: Function: test5
284
285 define float @test5(ptr %Arr, ptr %Arr2) {
286 entry:
287 br label %outer.header
288
289 outer.header: ; preds = %outer.inc, %entry
290 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
291 %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.inner.lcssa, %outer.inc ]
292 br label %for.body3
293
294 for.body3: ; preds = %for.body3, %outer.header
295 %float.inner = phi float [ %float.outer , %outer.header ], [ %float.inner.inc.inc, %for.body3 ]
296 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
297 %arrayidx5 = getelementptr inbounds [100 x [100 x float]], ptr %Arr, i64 0, i64 %iv.inner, i64 %iv.outer
298 %vA = load float, ptr %arrayidx5
299 %float.inner.inc = fadd fast float %float.inner, %vA
300 %arrayidx6 = getelementptr inbounds [100 x [100 x float]], ptr %Arr2, i64 0, i64 %iv.inner, i64 %iv.outer
301 %vB = load float, ptr %arrayidx6
302 %float.inner.inc.inc = fadd fast float %float.inner.inc, %vB
303 %iv.inner.next = add nuw nsw i64 %iv.inner, 1
304 %exitcond = icmp slt i64 %iv.inner.next, 100
305 br i1 %exitcond, label %for.body3, label %outer.inc
306
307 outer.inc: ; preds = %for.body3
308 %float.inner.lcssa = phi float [ %float.inner.inc.inc, %for.body3 ]
309 %iv.outer.next = add nsw i64 %iv.outer, 1
310 %cmp = icmp slt i64 %iv.outer.next, 100
311 br i1 %cmp, label %outer.header, label %for.exit
312
313 for.exit: ; preds = %outer.inc
314 %float.outer.lcssa = phi float [ %float.inner.lcssa, %outer.inc ]
315 ret float %float.outer.lcssa
316 }
317
318 ; Floating point reductions are not interchanged if not all the fp instructions
319 ; involved allow reassociation.
320 ; REMARKS: --- !Analysis
321 ; REMARKS-NEXT: Pass: loop-interchange
322 ; REMARKS-NEXT: Name: Dependence
323 ; REMARKS-NEXT: Function: test6
324 ; REMARKS-NEXT: Args:
325 ; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.
326 ; REMARKS-NEXT: ...
327
328 ; REMARKS: --- !Missed
329 ; REMARKS-NEXT: Pass: loop-interchange
330 ; REMARKS-NEXT: Name: UnsupportedPHIOuter
331 ; REMARKS-NEXT: Function: test6
332
333 define float @test6(ptr %Arr, ptr %Arr2) {
334 entry:
335 br label %outer.header
336
337 outer.header: ; preds = %outer.inc, %entry
338 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
339 %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.inner.lcssa, %outer.inc ]
340 br label %for.body3
341
342 for.body3: ; preds = %for.body3, %outer.header
343 %float.inner = phi float [ %float.outer , %outer.header ], [ %float.inner.inc.inc, %for.body3 ]
344 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
345 %arrayidx5 = getelementptr inbounds [100 x [100 x float]], ptr %Arr, i64 0, i64 %iv.inner, i64 %iv.outer
346 %vA = load float, ptr %arrayidx5
347 %float.inner.inc = fadd float %float.inner, %vA ; do not allow reassociation
348 %arrayidx6 = getelementptr inbounds [100 x [100 x float]], ptr %Arr2, i64 0, i64 %iv.inner, i64 %iv.outer
349 %vB = load float, ptr %arrayidx6
350 %float.inner.inc.inc = fadd fast float %float.inner.inc, %vB
351 %iv.inner.next = add nuw nsw i64 %iv.inner, 1
352 %exitcond = icmp eq i64 %iv.inner.next, 100
353 br i1 %exitcond, label %outer.inc, label %for.body3
354
355 outer.inc: ; preds = %for.body3
356 %float.inner.lcssa = phi float [ %float.inner.inc.inc, %for.body3 ]
357 %iv.outer.next = add nsw i64 %iv.outer, 1
358 %cmp = icmp eq i64 %iv.outer.next, 100
359 br i1 %cmp, label %outer.header, label %for.exit
360
361 for.exit: ; preds = %outer.inc
362 %float.outer.lcssa = phi float [ %float.inner.lcssa, %outer.inc ]
363 ret float %float.outer.lcssa
364 }