1; RUN: opt -S -loop-fusion -debug-only=loop-fusion -disable-output < %s 2>&1 | FileCheck %s
2; REQUIRES: asserts
3
4@B = common global [1024 x i32] zeroinitializer, align 16
5
6; CHECK that the two candidates for fusion are placed into separate candidate
7; sets because they are not control flow equivalent.
8
9; CHECK: Performing Loop Fusion on function non_cfe
10; CHECK: Fusion Candidates:
11; CHECK: *** Fusion Candidate Set ***
12; CHECK: bb
13; CHECK: ****************************
14; CHECK: *** Fusion Candidate Set ***
15; CHECK: bb20.preheader
16; CHECK: ****************************
17; CHECK: Loop Fusion complete
18define void @non_cfe(i32* noalias %arg) {
19bb:
20  br label %bb5
21
22bb5:                                              ; preds = %bb14, %bb
23  %indvars.iv2 = phi i64 [ %indvars.iv.next3, %bb14 ], [ 0, %bb ]
24  %.01 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ]
25  %exitcond4 = icmp ne i64 %indvars.iv2, 100
26  br i1 %exitcond4, label %bb7, label %bb16
27
28bb7:                                              ; preds = %bb5
29  %tmp = add nsw i32 %.01, -3
30  %tmp8 = add nuw nsw i64 %indvars.iv2, 3
31  %tmp9 = trunc i64 %tmp8 to i32
32  %tmp10 = mul nsw i32 %tmp, %tmp9
33  %tmp11 = trunc i64 %indvars.iv2 to i32
34  %tmp12 = srem i32 %tmp10, %tmp11
35  %tmp13 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv2
36  store i32 %tmp12, i32* %tmp13, align 4
37  br label %bb14
38
39bb14:                                             ; preds = %bb7
40  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
41  %tmp15 = add nuw nsw i32 %.01, 1
42  br label %bb5
43
44bb16:                                             ; preds = %bb5
45  %tmp17 = load i32, i32* %arg, align 4
46  %tmp18 = icmp slt i32 %tmp17, 0
47  br i1 %tmp18, label %bb20, label %bb33
48
49bb20:                                             ; preds = %bb30, %bb16
50  %indvars.iv = phi i64 [ %indvars.iv.next, %bb30 ], [ 0, %bb16 ]
51  %.0 = phi i32 [ 0, %bb16 ], [ %tmp31, %bb30 ]
52  %exitcond = icmp ne i64 %indvars.iv, 100
53  br i1 %exitcond, label %bb22, label %bb33
54
55bb22:                                             ; preds = %bb20
56  %tmp23 = add nsw i32 %.0, -3
57  %tmp24 = add nuw nsw i64 %indvars.iv, 3
58  %tmp25 = trunc i64 %tmp24 to i32
59  %tmp26 = mul nsw i32 %tmp23, %tmp25
60  %tmp27 = trunc i64 %indvars.iv to i32
61  %tmp28 = srem i32 %tmp26, %tmp27
62  %tmp29 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv
63  store i32 %tmp28, i32* %tmp29, align 4
64  br label %bb30
65
66bb30:                                             ; preds = %bb22
67  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
68  %tmp31 = add nuw nsw i32 %.0, 1
69  br label %bb20
70
71bb33:                                             ; preds = %bb20, %bb16
72  ret void
73}
74
75; Check that fusion detects the two canddates are not adjacent (the exit block
76; of the first candidate is not the preheader of the second candidate).
77
78; CHECK: Performing Loop Fusion on function non_adjacent
79; CHECK: Fusion Candidates:
80; CHECK: *** Fusion Candidate Set ***
81; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
82; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
83; CHECK-NEXT: ****************************
84; CHECK: Attempting fusion on Candidate Set:
85; CHECK-NEXT: [[LOOP1PREHEADER]]
86; CHECK-NEXT: [[LOOP2PREHEADER]]
87; CHECK: Fusion candidates are not adjacent. Not fusing.
88; CHECK: Loop Fusion complete
89define void @non_adjacent(i32* noalias %arg) {
90bb:
91  br label %bb3
92
93bb3:                                              ; preds = %bb11, %bb
94  %.01 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
95  %exitcond2 = icmp ne i64 %.01, 100
96  br i1 %exitcond2, label %bb5, label %bb4
97
98bb4:                                              ; preds = %bb3
99  br label %bb13
100
101bb5:                                              ; preds = %bb3
102  %tmp = add nsw i64 %.01, -3
103  %tmp6 = add nuw nsw i64 %.01, 3
104  %tmp7 = mul nsw i64 %tmp, %tmp6
105  %tmp8 = srem i64 %tmp7, %.01
106  %tmp9 = trunc i64 %tmp8 to i32
107  %tmp10 = getelementptr inbounds i32, i32* %arg, i64 %.01
108  store i32 %tmp9, i32* %tmp10, align 4
109  br label %bb11
110
111bb11:                                             ; preds = %bb5
112  %tmp12 = add nuw nsw i64 %.01, 1
113  br label %bb3
114
115bb13:                                             ; preds = %bb4
116  br label %bb14
117
118bb14:                                             ; preds = %bb23, %bb13
119  %.0 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ]
120  %exitcond = icmp ne i64 %.0, 100
121  br i1 %exitcond, label %bb16, label %bb15
122
123bb15:                                             ; preds = %bb14
124  br label %bb25
125
126bb16:                                             ; preds = %bb14
127  %tmp17 = add nsw i64 %.0, -3
128  %tmp18 = add nuw nsw i64 %.0, 3
129  %tmp19 = mul nsw i64 %tmp17, %tmp18
130  %tmp20 = srem i64 %tmp19, %.0
131  %tmp21 = trunc i64 %tmp20 to i32
132  %tmp22 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %.0
133  store i32 %tmp21, i32* %tmp22, align 4
134  br label %bb23
135
136bb23:                                             ; preds = %bb16
137  %tmp24 = add nuw nsw i64 %.0, 1
138  br label %bb14
139
140bb25:                                             ; preds = %bb15
141  ret void
142}
143
144; Check that the different bounds are detected and prevent fusion.
145
146; CHECK: Performing Loop Fusion on function different_bounds
147; CHECK: Fusion Candidates:
148; CHECK: *** Fusion Candidate Set ***
149; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
150; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
151; CHECK-NEXT: ****************************
152; CHECK: Attempting fusion on Candidate Set:
153; CHECK-NEXT: [[LOOP1PREHEADER]]
154; CHECK-NEXT: [[LOOP2PREHEADER]]
155; CHECK: Fusion candidates do not have identical trip counts. Not fusing.
156; CHECK: Loop Fusion complete
157define void @different_bounds(i32* noalias %arg) {
158bb:
159  br label %bb3
160
161bb3:                                              ; preds = %bb11, %bb
162  %.01 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
163  %exitcond2 = icmp ne i64 %.01, 100
164  br i1 %exitcond2, label %bb5, label %bb4
165
166bb4:                                              ; preds = %bb3
167  br label %bb13
168
169bb5:                                              ; preds = %bb3
170  %tmp = add nsw i64 %.01, -3
171  %tmp6 = add nuw nsw i64 %.01, 3
172  %tmp7 = mul nsw i64 %tmp, %tmp6
173  %tmp8 = srem i64 %tmp7, %.01
174  %tmp9 = trunc i64 %tmp8 to i32
175  %tmp10 = getelementptr inbounds i32, i32* %arg, i64 %.01
176  store i32 %tmp9, i32* %tmp10, align 4
177  br label %bb11
178
179bb11:                                             ; preds = %bb5
180  %tmp12 = add nuw nsw i64 %.01, 1
181  br label %bb3
182
183bb13:                                             ; preds = %bb4
184  br label %bb14
185
186bb14:                                             ; preds = %bb23, %bb13
187  %.0 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ]
188  %exitcond = icmp ne i64 %.0, 200
189  br i1 %exitcond, label %bb16, label %bb15
190
191bb15:                                             ; preds = %bb14
192  br label %bb25
193
194bb16:                                             ; preds = %bb14
195  %tmp17 = add nsw i64 %.0, -3
196  %tmp18 = add nuw nsw i64 %.0, 3
197  %tmp19 = mul nsw i64 %tmp17, %tmp18
198  %tmp20 = srem i64 %tmp19, %.0
199  %tmp21 = trunc i64 %tmp20 to i32
200  %tmp22 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %.0
201  store i32 %tmp21, i32* %tmp22, align 4
202  br label %bb23
203
204bb23:                                             ; preds = %bb16
205  %tmp24 = add nuw nsw i64 %.0, 1
206  br label %bb14
207
208bb25:                                             ; preds = %bb15
209  ret void
210}
211
212; Check that the negative dependence between the two candidates is identified
213; and prevents fusion.
214
215; CHECK: Performing Loop Fusion on function negative_dependence
216; CHECK: Fusion Candidates:
217; CHECK: *** Fusion Candidate Set ***
218; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
219; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
220; CHECK-NEXT: ****************************
221; CHECK: Attempting fusion on Candidate Set:
222; CHECK-NEXT: [[LOOP1PREHEADER]]
223; CHECK-NEXT: [[LOOP2PREHEADER]]
224; CHECK: Memory dependencies do not allow fusion!
225; CHECK: Loop Fusion complete
226define void @negative_dependence(i32* noalias %arg) {
227bb:
228  br label %bb5
229
230bb5:                                              ; preds = %bb9, %bb
231  %indvars.iv2 = phi i64 [ %indvars.iv.next3, %bb9 ], [ 0, %bb ]
232  %exitcond4 = icmp ne i64 %indvars.iv2, 100
233  br i1 %exitcond4, label %bb7, label %bb11
234
235bb7:                                              ; preds = %bb5
236  %tmp = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv2
237  %tmp8 = trunc i64 %indvars.iv2 to i32
238  store i32 %tmp8, i32* %tmp, align 4
239  br label %bb9
240
241bb9:                                              ; preds = %bb7
242  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
243  br label %bb5
244
245bb11:                                             ; preds = %bb18, %bb5
246  %indvars.iv = phi i64 [ %indvars.iv.next, %bb18 ], [ 0, %bb5 ]
247  %exitcond = icmp ne i64 %indvars.iv, 100
248  br i1 %exitcond, label %bb13, label %bb19
249
250bb13:                                             ; preds = %bb11
251  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
252  %tmp14 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv.next
253  %tmp15 = load i32, i32* %tmp14, align 4
254  %tmp16 = shl nsw i32 %tmp15, 1
255  %tmp17 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv
256  store i32 %tmp16, i32* %tmp17, align 4
257  br label %bb18
258
259bb18:                                             ; preds = %bb13
260  br label %bb11
261
262bb19:                                             ; preds = %bb11
263  ret void
264}
265
266; Check for values defined in Loop 0 and used in Loop 1.
267; It is not safe to fuse in this case, because the second loop has
268; a use of %.01.lcssa which is defined in the body of loop 0. The
269; first loop must execute completely in order to compute the correct
270; value of %.01.lcssa to be used in the second loop.
271
272; CHECK: Performing Loop Fusion on function sumTest
273; CHECK: Fusion Candidates:
274; CHECK: *** Fusion Candidate Set ***
275; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
276; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
277; CHECK-NEXT: ****************************
278; CHECK: Attempting fusion on Candidate Set:
279; CHECK-NEXT: [[LOOP1PREHEADER]]
280; CHECK-NEXT: [[LOOP2PREHEADER]]
281; CHECK: Memory dependencies do not allow fusion!
282; CHECK: Loop Fusion complete
283define i32 @sumTest(i32* noalias %arg) {
284bb:
285  br label %bb6
286
287bb6:                                              ; preds = %bb9, %bb
288  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %bb9 ], [ 0, %bb ]
289  %.01 = phi i32 [ 0, %bb ], [ %tmp11, %bb9 ]
290  %exitcond5 = icmp ne i64 %indvars.iv3, 100
291  br i1 %exitcond5, label %bb9, label %bb13
292
293bb9:                                              ; preds = %bb6
294  %tmp = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv3
295  %tmp10 = load i32, i32* %tmp, align 4
296  %tmp11 = add nsw i32 %.01, %tmp10
297  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
298  br label %bb6
299
300bb13:                                             ; preds = %bb20, %bb6
301  %.01.lcssa = phi i32 [ %.01, %bb6 ], [ %.01.lcssa, %bb20 ]
302  %indvars.iv = phi i64 [ %indvars.iv.next, %bb20 ], [ 0, %bb6 ]
303  %exitcond = icmp ne i64 %indvars.iv, 100
304  br i1 %exitcond, label %bb15, label %bb14
305
306bb14:                                             ; preds = %bb13
307  br label %bb21
308
309bb15:                                             ; preds = %bb13
310  %tmp16 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv
311  %tmp17 = load i32, i32* %tmp16, align 4
312  %tmp18 = sdiv i32 %tmp17, %.01.lcssa
313  %tmp19 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv
314  store i32 %tmp18, i32* %tmp19, align 4
315  br label %bb20
316
317bb20:                                             ; preds = %bb15
318  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
319  br label %bb13
320
321bb21:                                             ; preds = %bb14
322  ret i32 %.01.lcssa
323}
324
325; Similar to sumTest above. The first loop computes %add and must
326; complete before it is used in the second loop. Thus, these two loops
327; also cannot be fused.
328
329; CHECK: Performing Loop Fusion on function test
330; CHECK: Fusion Candidates:
331; CHECK: *** Fusion Candidate Set ***
332; CHECK-NEXT: [[LOOP1PREHEADER:for.body[0-9]*.preheader]]
333; CHECK-NEXT: [[LOOP2PREHEADER:for.body[0-9]*.preheader]]
334; CHECK-NEXT: ****************************
335; CHECK: Attempting fusion on Candidate Set:
336; CHECK-NEXT: [[LOOP1PREHEADER]]
337; CHECK-NEXT: [[LOOP2PREHEADER]]
338; CHECK: Memory dependencies do not allow fusion!
339; CHECK: Loop Fusion complete
340define float @test(float* nocapture %a, i32 %n) {
341entry:
342  %conv = zext i32 %n to i64
343  %cmp32 = icmp eq i32 %n, 0
344  br i1 %cmp32, label %for.cond.cleanup7, label %for.body
345
346for.body:                                         ; preds = %for.body, %entry
347  %i.034 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
348  %sum1.033 = phi float [ %add, %for.body ], [ 0.000000e+00, %entry ]
349  %idxprom = trunc i64 %i.034 to i32
350  %arrayidx = getelementptr inbounds float, float* %a, i32 %idxprom
351  %0 = load float, float* %arrayidx, align 4
352  %add = fadd float %sum1.033, %0
353  %inc = add nuw nsw i64 %i.034, 1
354  %cmp = icmp ult i64 %inc, %conv
355  br i1 %cmp, label %for.body, label %for.body8
356
357for.body8:                                        ; preds = %for.body, %for.body8
358  %i2.031 = phi i64 [ %inc14, %for.body8 ], [ 0, %for.body ]
359  %idxprom9 = trunc i64 %i2.031 to i32
360  %arrayidx10 = getelementptr inbounds float, float* %a, i32 %idxprom9
361  %1 = load float, float* %arrayidx10, align 4
362  %div = fdiv float %1, %add
363  store float %div, float* %arrayidx10, align 4
364  %inc14 = add nuw nsw i64 %i2.031, 1
365  %cmp5 = icmp ult i64 %inc14, %conv
366  br i1 %cmp5, label %for.body8, label %for.cond.cleanup7
367
368for.cond.cleanup7:                                ; preds = %for.body8, %entry
369  %sum1.0.lcssa36 = phi float [ 0.000000e+00, %entry ], [ %add, %for.body8 ]
370  ret float %sum1.0.lcssa36
371}
372