1; RUN: opt -S -loop-fusion < %s | FileCheck %s
2
3@B = common global [1024 x i32] zeroinitializer, align 16
4
5; CHECK: void @dep_free
6; CHECK-NEXT: bb:
7; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]*]]
8; CHECK: [[LOOP1HEADER]]
9; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
10; CHECK: [[LOOP2HEADER]]
11; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
12; CHECK: [[LOOP2LATCH]]
13; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
14; CHECK: ret void
15define void @dep_free(i32* noalias %arg) {
16bb:
17  br label %bb7
18
19bb7:                                              ; preds = %bb, %bb14
20  %.014 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ]
21  %indvars.iv23 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb14 ]
22  %tmp = add nsw i32 %.014, -3
23  %tmp8 = add nuw nsw i64 %indvars.iv23, 3
24  %tmp9 = trunc i64 %tmp8 to i32
25  %tmp10 = mul nsw i32 %tmp, %tmp9
26  %tmp11 = trunc i64 %indvars.iv23 to i32
27  %tmp12 = srem i32 %tmp10, %tmp11
28  %tmp13 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv23
29  store i32 %tmp12, i32* %tmp13, align 4
30  br label %bb14
31
32bb14:                                             ; preds = %bb7
33  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv23, 1
34  %tmp15 = add nuw nsw i32 %.014, 1
35  %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
36  br i1 %exitcond4, label %bb7, label %bb17.preheader
37
38bb17.preheader:                                   ; preds = %bb14
39  br label %bb19
40
41bb19:                                             ; preds = %bb17.preheader, %bb27
42  %.02 = phi i32 [ 0, %bb17.preheader ], [ %tmp28, %bb27 ]
43  %indvars.iv1 = phi i64 [ 0, %bb17.preheader ], [ %indvars.iv.next, %bb27 ]
44  %tmp20 = add nsw i32 %.02, -3
45  %tmp21 = add nuw nsw i64 %indvars.iv1, 3
46  %tmp22 = trunc i64 %tmp21 to i32
47  %tmp23 = mul nsw i32 %tmp20, %tmp22
48  %tmp24 = trunc i64 %indvars.iv1 to i32
49  %tmp25 = srem i32 %tmp23, %tmp24
50  %tmp26 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1
51  store i32 %tmp25, i32* %tmp26, align 4
52  br label %bb27
53
54bb27:                                             ; preds = %bb19
55  %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
56  %tmp28 = add nuw nsw i32 %.02, 1
57  %exitcond = icmp ne i64 %indvars.iv.next, 100
58  br i1 %exitcond, label %bb19, label %bb18
59
60bb18:                                             ; preds = %bb27
61  br label %bb29
62
63bb29:                                             ; preds = %bb18
64  ret void
65}
66
67; CHECK: void @dep_free_parametric
68; CHECK-NEXT: bb:
69; CHECK: br i1 %{{.*}}, label %[[LOOP1PREHEADER:bb[0-9.a-z]*]], label %[[EXITBLOCK:bb[0-9]*]]
70; CHECK: [[LOOP1PREHEADER]]
71; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
72; CHECK: [[LOOP1HEADER]]
73; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
74; CHECK: [[LOOP2HEADER]]
75; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
76; CHECK: [[LOOP2LATCH]]
77; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[EXITBLOCK]]
78; CHECK: ret void
79define void @dep_free_parametric(i32* noalias %arg, i64 %arg2) {
80bb:
81  %tmp3 = icmp slt i64 0, %arg2
82  br i1 %tmp3, label %bb5, label %bb15.preheader
83
84bb5:                                              ; preds = %bb5, %bb12
85  %.014 = phi i64 [ 0, %bb ], [ %tmp13, %bb12 ]
86  %tmp6 = add nsw i64 %.014, -3
87  %tmp7 = add nuw nsw i64 %.014, 3
88  %tmp8 = mul nsw i64 %tmp6, %tmp7
89  %tmp9 = srem i64 %tmp8, %.014
90  %tmp10 = trunc i64 %tmp9 to i32
91  %tmp11 = getelementptr inbounds i32, i32* %arg, i64 %.014
92  store i32 %tmp10, i32* %tmp11, align 4
93  br label %bb12
94
95bb12:                                             ; preds = %bb5
96  %tmp13 = add nuw nsw i64 %.014, 1
97  %tmp = icmp slt i64 %tmp13, %arg2
98  br i1 %tmp, label %bb5, label %bb15.preheader
99
100bb15.preheader:                                   ; preds = %bb12, %bb
101  %tmp161 = icmp slt i64 0, %arg2
102  br i1 %tmp161, label %bb18, label %bb27
103
104bb18:                                             ; preds = %bb15.preheader, %bb25
105  %.02 = phi i64 [ 0, %bb15.preheader ], [ %tmp26, %bb25 ]
106  %tmp19 = add nsw i64 %.02, -3
107  %tmp20 = add nuw nsw i64 %.02, 3
108  %tmp21 = mul nsw i64 %tmp19, %tmp20
109  %tmp22 = srem i64 %tmp21, %.02
110  %tmp23 = trunc i64 %tmp22 to i32
111  %tmp24 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %.02
112  store i32 %tmp23, i32* %tmp24, align 4
113  br label %bb25
114
115bb25:                                             ; preds = %bb18
116  %tmp26 = add nuw nsw i64 %.02, 1
117  %tmp16 = icmp slt i64 %tmp26, %arg2
118  br i1 %tmp16, label %bb18, label %bb27
119
120bb27:                                             ; preds = %bb17
121  ret void
122}
123
124; CHECK: void @raw_only
125; CHECK-NEXT: bb:
126; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]*]]
127; CHECK: [[LOOP1HEADER]]
128; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
129; CHECK: [[LOOP2HEADER]]
130; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
131; CHECK: [[LOOP2LATCH]]
132; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
133; CHECK: ret void
134define void @raw_only(i32* noalias %arg) {
135bb:
136  br label %bb7
137
138bb11.preheader:                                   ; preds = %bb9
139  br label %bb13
140
141bb7:                                              ; preds = %bb, %bb9
142  %indvars.iv22 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb9 ]
143  %tmp = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv22
144  %tmp8 = trunc i64 %indvars.iv22 to i32
145  store i32 %tmp8, i32* %tmp, align 4
146  br label %bb9
147
148bb9:                                              ; preds = %bb7
149  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv22, 1
150  %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
151  br i1 %exitcond4, label %bb7, label %bb11.preheader
152
153bb13:                                             ; preds = %bb11.preheader, %bb18
154  %indvars.iv1 = phi i64 [ 0, %bb11.preheader ], [ %indvars.iv.next, %bb18 ]
155  %tmp14 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv1
156  %tmp15 = load i32, i32* %tmp14, align 4
157  %tmp16 = shl nsw i32 %tmp15, 1
158  %tmp17 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1
159  store i32 %tmp16, i32* %tmp17, align 4
160  br label %bb18
161
162bb18:                                             ; preds = %bb13
163  %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
164  %exitcond = icmp ne i64 %indvars.iv.next, 100 br i1 %exitcond, label %bb13, label %bb19
165
166bb19:                                             ; preds = %bb18
167  ret void
168}
169
170; CHECK: void @raw_only_parametric
171; CHECK-NEXT: bb:
172; CHECK: br i1 %{{.*}}, label %[[LOOP1PREHEADER:bb[0-9.a-z]*]], label %[[EXITBLOCK:bb[0-9]*]]
173; CHECK: [[LOOP1PREHEADER]]
174; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
175; CHECK: [[LOOP1HEADER]]
176; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[EXITBLOCK]]
177; CHECK: ret void
178define void @raw_only_parametric(i32* noalias %arg, i32 %arg4) {
179bb:
180  %tmp = sext i32 %arg4 to i64
181  %tmp64 = icmp sgt i32 %arg4, 0
182  br i1 %tmp64, label %bb8, label %bb23
183
184bb8:                                              ; preds = %bb, %bb8
185  %indvars.iv25 = phi i64 [ %indvars.iv.next3, %bb8 ], [ 0, %bb ]
186  %tmp9 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv25
187  %tmp10 = trunc i64 %indvars.iv25 to i32
188  store i32 %tmp10, i32* %tmp9, align 4
189  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv25, 1
190  %tmp6 = icmp slt i64 %indvars.iv.next3, %tmp
191  br i1 %tmp6, label %bb8, label %bb17
192
193bb17:                                             ; preds = %bb8, %bb17
194  %indvars.iv3 = phi i64 [ %indvars.iv.next, %bb17 ], [ 0, %bb8 ]
195  %tmp18 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv3
196  %tmp19 = load i32, i32* %tmp18, align 4
197  %tmp20 = shl nsw i32 %tmp19, 1
198  %tmp21 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv3
199  store i32 %tmp20, i32* %tmp21, align 4
200  %indvars.iv.next = add nuw nsw i64 %indvars.iv3, 1
201  %tmp15 = icmp slt i64 %indvars.iv.next, %tmp
202  br i1 %tmp15, label %bb17, label %bb23
203
204bb23:                                             ; preds = %bb17, %bb
205  ret void
206}
207
208; CHECK: void @forward_dep
209; CHECK-NEXT: bb:
210; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
211; CHECK: [[LOOP1HEADER]]
212; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
213; CHECK: [[LOOP2HEADER]]
214; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
215; CHECK: [[LOOP2LATCH]]
216; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
217; CHECK: ret void
218define void @forward_dep(i32* noalias %arg) {
219bb:
220  br label %bb7
221
222bb7:                                              ; preds = %bb, %bb14
223  %.013 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ]
224  %indvars.iv22 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb14 ]
225  %tmp = add nsw i32 %.013, -3
226  %tmp8 = add nuw nsw i64 %indvars.iv22, 3
227  %tmp9 = trunc i64 %tmp8 to i32
228  %tmp10 = mul nsw i32 %tmp, %tmp9
229  %tmp11 = trunc i64 %indvars.iv22 to i32
230  %tmp12 = srem i32 %tmp10, %tmp11
231  %tmp13 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv22
232  store i32 %tmp12, i32* %tmp13, align 4
233  br label %bb14
234
235bb14:                                             ; preds = %bb7
236  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv22, 1
237  %tmp15 = add nuw nsw i32 %.013, 1
238  %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
239  br i1 %exitcond4, label %bb7, label %bb19
240
241bb19:                                             ; preds = %bb14, %bb25
242  %indvars.iv1 = phi i64 [ 0, %bb14 ], [ %indvars.iv.next, %bb25 ]
243  %tmp20 = add nsw i64 %indvars.iv1, -3
244  %tmp21 = getelementptr inbounds i32, i32* %arg, i64 %tmp20
245  %tmp22 = load i32, i32* %tmp21, align 4
246  %tmp23 = mul nsw i32 %tmp22, 3
247  %tmp24 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv1
248  store i32 %tmp23, i32* %tmp24, align 4
249  br label %bb25
250
251bb25:                                             ; preds = %bb19
252  %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
253  %exitcond = icmp ne i64 %indvars.iv.next, 100
254  br i1 %exitcond, label %bb19, label %bb26
255
256bb26:                                             ; preds = %bb25
257  ret void
258}
259
260; Test that instructions in loop 1 latch are moved to the beginning of loop 2
261; latch iff it is proven safe. %inc.first and %cmp.first are moved, but
262; `store i32 0, i32* %Ai.first` is not.
263
264; CHECK: void @flow_dep
265; CHECK-LABEL: entry:
266; CHECK-NEXT: br label %for.first
267; CHECK-LABEL: for.first:
268; CHECK: store i32 0, i32* %Ai.first
269; CHECK: %Ai.second =
270; CHECK: br label %for.second.latch
271; CHECK-LABEL: for.second.latch:
272; CHECK-NEXT: %inc.first = add nsw i64 %i.first, 1
273; CHECK-NEXT: %cmp.first = icmp slt i64 %inc.first, 100
274; CHECK: br i1 %cmp.second, label %for.first, label %for.end
275; CHECK-LABEL: for.end:
276; CHECK-NEXT: ret void
277
278define void @flow_dep(i32* noalias %A, i32* noalias %B) {
279entry:
280  br label %for.first
281
282for.first:
283  %i.first = phi i64 [ 0, %entry ], [ %inc.first, %for.first ]
284  %Ai.first = getelementptr inbounds i32, i32* %A, i64 %i.first
285  store i32 0, i32* %Ai.first, align 4
286  %inc.first = add nsw i64 %i.first, 1
287  %cmp.first = icmp slt i64 %inc.first, 100
288  br i1 %cmp.first, label %for.first, label %for.second.preheader
289
290for.second.preheader:
291  br label %for.second
292
293for.second:
294  %i.second = phi i64 [ %inc.second, %for.second.latch ], [ 0, %for.second.preheader ]
295  %Ai.second = getelementptr inbounds i32, i32* %A, i64 %i.second
296  %0 = load i32, i32* %Ai.second, align 4
297  %Bi = getelementptr inbounds i32, i32* %B, i64 %i.second
298  store i32 %0, i32* %Bi, align 4
299  br label %for.second.latch
300
301for.second.latch:
302  %inc.second = add nsw i64 %i.second, 1
303  %cmp.second = icmp slt i64 %inc.second, 100
304  br i1 %cmp.second, label %for.second, label %for.end
305
306for.end:
307  ret void
308}
309
310; Test that `%add` is moved in basic block entry, and the two loops for.first
311; and for.second are fused.
312
313; CHECK: i32 @moveinsts_preheader
314; CHECK-LABEL: entry:
315; CHECK-NEXT: %add = add nsw i32 %x, 1
316; CHECK-NEXT: br label %for.first
317; CHECK-LABEL: for.first:
318; CHECK: br i1 %cmp.j, label %for.first, label %for.second.exit
319; CHECK-LABEL: for.second.exit:
320; CHECK-NEXT: ret i32 %add
321
322define i32 @moveinsts_preheader(i32* %A, i32 %x) {
323entry:
324  br label %for.first
325
326for.first:
327  %i = phi i64 [ 0, %entry ], [ %inc.i, %for.first ]
328  %Ai = getelementptr inbounds i32, i32* %A, i64 %i
329  store i32 0, i32* %Ai, align 4
330  %inc.i = add nsw i64 %i, 1
331  %cmp.i = icmp slt i64 %inc.i, 100
332  br i1 %cmp.i, label %for.first, label %for.first.exit
333
334for.first.exit:
335  %add = add nsw i32 %x, 1
336  br label %for.second
337
338for.second:
339  %j = phi i64 [ 0, %for.first.exit ], [ %inc.j, %for.second ]
340  %Aj = getelementptr inbounds i32, i32* %A, i64 %j
341  store i32 2, i32* %Aj, align 4
342  %inc.j = add nsw i64 %j, 1
343  %cmp.j = icmp slt i64 %inc.j, 100
344  br i1 %cmp.j, label %for.second, label %for.second.exit
345
346for.second.exit:
347  ret i32 %add
348}
349
350; Test that `%add` cannot be moved to basic block entry, as it uses %i, which
351; defined after basic block entry. And the two loops for.first and for.second
352; are not fused.
353
354; CHECK: i64 @unsafe_preheader
355; CHECK-LABEL: entry:
356; CHECK-NEXT: br label %for.first
357; CHECK-LABEL: for.first:
358; CHECK: br i1 %cmp.i, label %for.first, label %for.first.exit
359; CHECK-LABEL: for.first.exit:
360; CHECK-NEXT: %add = add nsw i64 %x, %i
361; CHECK-NEXT: br label %for.second
362; CHECK-LABEL: for.second:
363; CHECK: br i1 %cmp.j, label %for.second, label %for.second.exit
364; CHECK-LABEL: for.second.exit:
365; CHECK-NEXT: ret i64 %add
366
367define i64 @unsafe_preheader(i32* %A, i64 %x) {
368entry:
369  br label %for.first
370
371for.first:
372  %i = phi i64 [ 0, %entry ], [ %inc.i, %for.first ]
373  %Ai = getelementptr inbounds i32, i32* %A, i64 %i
374  store i32 0, i32* %Ai, align 4
375  %inc.i = add nsw i64 %i, 1
376  %cmp.i = icmp slt i64 %inc.i, 100
377  br i1 %cmp.i, label %for.first, label %for.first.exit
378
379for.first.exit:
380  %add = add nsw i64 %x, %i
381  br label %for.second
382
383for.second:
384  %j = phi i64 [ 0, %for.first.exit ], [ %inc.j, %for.second ]
385  %Aj = getelementptr inbounds i32, i32* %A, i64 %j
386  store i32 2, i32* %Aj, align 4
387  %inc.j = add nsw i64 %j, 1
388  %cmp.j = icmp slt i64 %inc.j, 100
389  br i1 %cmp.j, label %for.second, label %for.second.exit
390
391for.second.exit:
392  ret i64 %add
393}
394