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