1; RUN: opt < %s -S -loop-flatten -debug-only=loop-flatten 2>&1 | FileCheck %s
2; REQUIRES: asserts
3
4; Every function in this file has a reason that it can't be transformed.
5
6; CHECK-NOT: Checks all passed, doing the transformation
7
8; Outer loop does not start at zero
9define void @test_1(i32 %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
10entry:
11  %cmp25 = icmp sgt i32 %N, 0
12  br i1 %cmp25, label %for.body4.lr.ph, label %for.cond.cleanup
13
14for.body4.lr.ph:
15  %i.026 = phi i32 [ %inc10, %for.cond.cleanup3 ], [ 1, %entry ]
16  %mul = mul nsw i32 %i.026, %N
17  br label %for.body4
18
19for.body4:
20  %j.024 = phi i32 [ 0, %for.body4.lr.ph ], [ %inc, %for.body4 ]
21  %add = add nsw i32 %j.024, %mul
22  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
23  %0 = load i32, i32* %arrayidx, align 4
24  %mul5 = mul nsw i32 %0, %scale
25  %arrayidx8 = getelementptr inbounds i32, i32* %C, i32 %add
26  store i32 %mul5, i32* %arrayidx8, align 4
27  %inc = add nuw nsw i32 %j.024, 1
28  %exitcond = icmp eq i32 %inc, %N
29  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
30
31for.cond.cleanup3:
32  %inc10 = add nuw nsw i32 %i.026, 1
33  %exitcond27 = icmp eq i32 %inc10, %N
34  br i1 %exitcond27, label %for.cond.cleanup, label %for.body4.lr.ph
35
36for.cond.cleanup:
37  ret void
38}
39
40; Inner loop does not start at zero
41define void @test_2(i32 %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
42entry:
43  %cmp25 = icmp sgt i32 %N, 0
44  br i1 %cmp25, label %for.body4.lr.ph, label %for.cond.cleanup
45
46for.body4.lr.ph:
47  %i.026 = phi i32 [ %inc10, %for.cond.cleanup3 ], [ 0, %entry ]
48  %mul = mul nsw i32 %i.026, %N
49  br label %for.body4
50
51for.body4:
52  %j.024 = phi i32 [ 1, %for.body4.lr.ph ], [ %inc, %for.body4 ]
53  %add = add nsw i32 %j.024, %mul
54  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
55  %0 = load i32, i32* %arrayidx, align 4
56  %mul5 = mul nsw i32 %0, %scale
57  %arrayidx8 = getelementptr inbounds i32, i32* %C, i32 %add
58  store i32 %mul5, i32* %arrayidx8, align 4
59  %inc = add nuw nsw i32 %j.024, 1
60  %exitcond = icmp eq i32 %inc, %N
61  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
62
63for.cond.cleanup3:
64  %inc10 = add nuw nsw i32 %i.026, 1
65  %exitcond27 = icmp eq i32 %inc10, %N
66  br i1 %exitcond27, label %for.cond.cleanup, label %for.body4.lr.ph
67
68for.cond.cleanup:
69  ret void
70}
71
72; Outer IV used directly
73define hidden void @test_3(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
74entry:
75  %conv = zext i16 %N to i32
76  %cmp25 = icmp eq i16 %N, 0
77  br i1 %cmp25, label %for.cond.cleanup, label %for.body.lr.ph.split.us
78
79for.body.lr.ph.split.us:                          ; preds = %entry
80  br label %for.body.us
81
82for.body.us:                                      ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.lr.ph.split.us
83  %i.026.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.cond.cleanup6_crit_edge.us ]
84  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %i.026.us
85  %mul9.us = mul nuw nsw i32 %i.026.us, %conv
86  br label %for.body7.us
87
88for.body7.us:                                     ; preds = %for.body.us, %for.body7.us
89  %j.024.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body7.us ]
90  %0 = load i32, i32* %arrayidx.us, align 4
91  %mul.us = mul nsw i32 %0, %scale
92  %add.us = add nuw nsw i32 %j.024.us, %mul9.us
93  %arrayidx10.us = getelementptr inbounds i32, i32* %C, i32 %add.us
94  store i32 %mul.us, i32* %arrayidx10.us, align 4
95  %inc.us = add nuw nsw i32 %j.024.us, 1
96  %exitcond = icmp ne i32 %inc.us, %conv
97  br i1 %exitcond, label %for.body7.us, label %for.cond2.for.cond.cleanup6_crit_edge.us
98
99for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
100  %inc12.us = add nuw nsw i32 %i.026.us, 1
101  %exitcond27 = icmp ne i32 %inc12.us, %conv
102  br i1 %exitcond27, label %for.body.us, label %for.cond.cleanup.loopexit
103
104for.cond.cleanup.loopexit:                        ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us
105  br label %for.cond.cleanup
106
107for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
108  ret void
109}
110
111; Inner IV used directly
112define hidden void @test_4(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
113entry:
114  %conv = zext i16 %N to i32
115  %cmp25 = icmp eq i16 %N, 0
116  br i1 %cmp25, label %for.cond.cleanup, label %for.body.lr.ph.split.us
117
118for.body.lr.ph.split.us:                          ; preds = %entry
119  br label %for.body.us
120
121for.body.us:                                      ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.lr.ph.split.us
122  %i.026.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.cond.cleanup6_crit_edge.us ]
123  %mul9.us = mul nuw nsw i32 %i.026.us, %conv
124  br label %for.body7.us
125
126for.body7.us:                                     ; preds = %for.body.us, %for.body7.us
127  %j.024.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body7.us ]
128  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %j.024.us
129  %0 = load i32, i32* %arrayidx.us, align 4
130  %mul.us = mul nsw i32 %0, %scale
131  %add.us = add nuw nsw i32 %j.024.us, %mul9.us
132  %arrayidx10.us = getelementptr inbounds i32, i32* %C, i32 %add.us
133  store i32 %mul.us, i32* %arrayidx10.us, align 4
134  %inc.us = add nuw nsw i32 %j.024.us, 1
135  %exitcond = icmp ne i32 %inc.us, %conv
136  br i1 %exitcond, label %for.body7.us, label %for.cond2.for.cond.cleanup6_crit_edge.us
137
138for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
139  %inc12.us = add nuw nsw i32 %i.026.us, 1
140  %exitcond27 = icmp ne i32 %inc12.us, %conv
141  br i1 %exitcond27, label %for.body.us, label %for.cond.cleanup.loopexit
142
143for.cond.cleanup.loopexit:                        ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us
144  br label %for.cond.cleanup
145
146for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
147  ret void
148}
149
150; Inner iteration count not invariant in outer loop
151declare i32 @get_int() readonly
152define void @test_5(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
153entry:
154  %conv = zext i16 %N to i32
155  %cmp27 = icmp eq i16 %N, 0
156  br i1 %cmp27, label %for.cond.cleanup, label %for.body.lr.ph
157
158for.body.lr.ph:                                   ; preds = %entry
159  br label %for.body
160
161for.cond.cleanup.loopexit:                        ; preds = %for.cond.cleanup5
162  br label %for.cond.cleanup
163
164for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
165  ret void
166
167for.body:                                         ; preds = %for.body.lr.ph, %for.cond.cleanup5
168  %i.028 = phi i32 [ 0, %for.body.lr.ph ], [ %inc12, %for.cond.cleanup5 ]
169  %call = tail call i32 @get_int()
170  %cmp325 = icmp sgt i32 %call, 0
171  br i1 %cmp325, label %for.body6.lr.ph, label %for.cond.cleanup5
172
173for.body6.lr.ph:                                  ; preds = %for.body
174  %mul = mul nsw i32 %call, %i.028
175  br label %for.body6
176
177for.cond.cleanup5.loopexit:                       ; preds = %for.body6
178  br label %for.cond.cleanup5
179
180for.cond.cleanup5:                                ; preds = %for.cond.cleanup5.loopexit, %for.body
181  %inc12 = add nuw nsw i32 %i.028, 1
182  %exitcond29 = icmp ne i32 %inc12, %conv
183  br i1 %exitcond29, label %for.body, label %for.cond.cleanup.loopexit
184
185for.body6:                                        ; preds = %for.body6.lr.ph, %for.body6
186  %j.026 = phi i32 [ 0, %for.body6.lr.ph ], [ %inc, %for.body6 ]
187  %add = add nsw i32 %j.026, %mul
188  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
189  %0 = load i32, i32* %arrayidx, align 4
190  %mul7 = mul nsw i32 %0, %scale
191  %arrayidx10 = getelementptr inbounds i32, i32* %C, i32 %add
192  store i32 %mul7, i32* %arrayidx10, align 4
193  %inc = add nuw nsw i32 %j.026, 1
194  %exitcond = icmp ne i32 %inc, %call
195  br i1 %exitcond, label %for.body6, label %for.cond.cleanup5.loopexit
196}
197
198; Inner loop has an early exit
199define hidden void @test_6(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
200entry:
201  %conv = zext i16 %N to i32
202  %cmp39 = icmp eq i16 %N, 0
203  br i1 %cmp39, label %for.cond.cleanup, label %for.body.us.preheader
204
205for.body.us.preheader:                            ; preds = %entry
206  br label %for.body.us
207
208for.body.us:                                      ; preds = %for.body.us.preheader, %cleanup.us
209  %i.040.us = phi i32 [ %inc19.us, %cleanup.us ], [ 0, %for.body.us.preheader ]
210  %mul.us = mul nuw nsw i32 %i.040.us, %conv
211  br label %for.body7.us
212
213for.body7.us:                                     ; preds = %for.body.us, %if.end.us
214  %j.038.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %if.end.us ]
215  %add.us = add nuw nsw i32 %j.038.us, %mul.us
216  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %add.us
217  %0 = load i32, i32* %arrayidx.us, align 4
218  %tobool.us = icmp eq i32 %0, 0
219  br i1 %tobool.us, label %if.end.us, label %cleanup.us
220
221cleanup.us:                                       ; preds = %if.end.us, %for.body7.us
222  %inc19.us = add nuw nsw i32 %i.040.us, 1
223  %exitcond = icmp eq i32 %inc19.us, %conv
224  br i1 %exitcond, label %for.cond.cleanup, label %for.body.us
225
226if.end.us:                                        ; preds = %for.body7.us
227  %arrayidx17.us = getelementptr inbounds i32, i32* %C, i32 %add.us
228  store i32 0, i32* %arrayidx17.us, align 4
229  %inc.us = add nuw nsw i32 %j.038.us, 1
230  %cmp4.us = icmp ult i32 %inc.us, %conv
231  br i1 %cmp4.us, label %for.body7.us, label %cleanup.us
232
233for.cond.cleanup:                                 ; preds = %cleanup.us, %entry
234  ret void
235}
236
237define hidden void @test_7(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
238entry:
239  %conv = zext i16 %N to i32
240  %cmp30 = icmp eq i16 %N, 0
241  br i1 %cmp30, label %cleanup, label %for.body.us.preheader
242
243for.body.us.preheader:                            ; preds = %entry
244  br label %for.body.us
245
246for.body.us:                                      ; preds = %for.body.us.preheader, %for.cond2.for.cond.cleanup6_crit_edge.us
247  %i.031.us = phi i32 [ %inc15.us, %for.cond2.for.cond.cleanup6_crit_edge.us ], [ 0, %for.body.us.preheader ]
248  %call.us = tail call i32 @get_int() #2
249  %tobool.us = icmp eq i32 %call.us, 0
250  br i1 %tobool.us, label %for.body7.lr.ph.us, label %cleanup
251
252for.body7.us:                                     ; preds = %for.body7.us, %for.body7.lr.ph.us
253  %j.029.us = phi i32 [ 0, %for.body7.lr.ph.us ], [ %inc.us, %for.body7.us ]
254  %add.us = add nuw nsw i32 %j.029.us, %mul.us
255  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %add.us
256  %0 = load i32, i32* %arrayidx.us, align 4
257  %mul9.us = mul nsw i32 %0, %scale
258  %arrayidx13.us = getelementptr inbounds i32, i32* %C, i32 %add.us
259  store i32 %mul9.us, i32* %arrayidx13.us, align 4
260  %inc.us = add nuw nsw i32 %j.029.us, 1
261  %exitcond = icmp eq i32 %inc.us, %conv
262  br i1 %exitcond, label %for.cond2.for.cond.cleanup6_crit_edge.us, label %for.body7.us
263
264for.body7.lr.ph.us:                               ; preds = %for.body.us
265  %mul.us = mul nuw nsw i32 %i.031.us, %conv
266  br label %for.body7.us
267
268for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
269  %inc15.us = add nuw nsw i32 %i.031.us, 1
270  %cmp.us = icmp ult i32 %inc15.us, %conv
271  br i1 %cmp.us, label %for.body.us, label %cleanup
272
273cleanup:                                          ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.us, %entry
274  ret void
275}
276
277; Step is not 1
278define i32 @test_8(i32 %val, i16* nocapture %A) {
279entry:
280  br label %for.body
281
282for.body:                                         ; preds = %entry, %for.inc6
283  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
284  %mul = mul nuw nsw i32 %i.018, 20
285  br label %for.body3
286
287for.body3:                                        ; preds = %for.body, %for.body3
288  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
289  %add = add nuw nsw i32 %j.017, %mul
290  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
291  %0 = load i16, i16* %arrayidx, align 2
292  %conv16 = zext i16 %0 to i32
293  %add4 = add i32 %conv16, %val
294  %conv5 = trunc i32 %add4 to i16
295  store i16 %conv5, i16* %arrayidx, align 2
296  %inc = add nuw nsw i32 %j.017, 1
297  %exitcond = icmp ne i32 %inc, 20
298  br i1 %exitcond, label %for.body3, label %for.inc6
299
300for.inc6:                                         ; preds = %for.body3
301  %inc7 = add nuw nsw i32 %i.018, 2
302  %exitcond19 = icmp ne i32 %inc7, 10
303  br i1 %exitcond19, label %for.body, label %for.end8
304
305for.end8:                                         ; preds = %for.inc6
306  ret i32 10
307}
308
309
310; Step is not 1
311define i32 @test_9(i32 %val, i16* nocapture %A) {
312entry:
313  br label %for.body
314
315for.body:                                         ; preds = %entry, %for.inc6
316  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
317  %mul = mul nuw nsw i32 %i.018, 20
318  br label %for.body3
319
320for.body3:                                        ; preds = %for.body, %for.body3
321  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
322  %add = add nuw nsw i32 %j.017, %mul
323  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
324  %0 = load i16, i16* %arrayidx, align 2
325  %conv16 = zext i16 %0 to i32
326  %add4 = add i32 %conv16, %val
327  %conv5 = trunc i32 %add4 to i16
328  store i16 %conv5, i16* %arrayidx, align 2
329  %inc = add nuw nsw i32 %j.017, 2
330  %exitcond = icmp ne i32 %inc, 20
331  br i1 %exitcond, label %for.body3, label %for.inc6
332
333for.inc6:                                         ; preds = %for.body3
334  %inc7 = add nuw nsw i32 %i.018, 1
335  %exitcond19 = icmp ne i32 %inc7, 10
336  br i1 %exitcond19, label %for.body, label %for.end8
337
338for.end8:                                         ; preds = %for.inc6
339  ret i32 10
340}
341
342
343; Outer loop conditional phi
344define i32 @e() {
345entry:
346  br label %for.body
347
348for.body:                                         ; preds = %entry, %for.end16
349  %f.033 = phi i32 [ 0, %entry ], [ %inc18, %for.end16 ]
350  %g.032 = phi i32 [ undef, %entry ], [ %g.3.lcssa, %for.end16 ]
351  %.pr = add i32 10, 10
352  %tobool29 = icmp eq i32 %.pr, 0
353  br i1 %tobool29, label %for.end, label %for.body2.lr.ph
354
355for.body2.lr.ph:                                  ; preds = %for.body
356  br label %for.cond1.for.end_crit_edge
357
358for.cond1.for.end_crit_edge:                      ; preds = %for.body2.lr.ph
359  br label %for.end
360
361for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
362  %g.1.lcssa = phi i32 [ 0, %for.cond1.for.end_crit_edge ], [ %g.032, %for.body ]
363  br label %for.body5
364
365for.body5:                                        ; preds = %for.end, %lor.end
366  %i.031 = phi i32 [ 0, %for.end ], [ %inc15, %lor.end ]
367  %g.230 = phi i32 [ %g.1.lcssa, %for.end ], [ %g.3, %lor.end ]
368  %0 = add i32 10, 10
369  %1 = add i32 10, 10
370  %tobool9 = icmp eq i32 %1, 0
371  br i1 %tobool9, label %lor.rhs, label %lor.end
372
373lor.rhs:                                          ; preds = %for.body5
374  %2 = add i32 10, 10
375  %call11 = add i32 10, 10
376  %tobool12 = icmp ne i32 %call11, 0
377  br label %lor.end
378
379lor.end:                                          ; preds = %for.body5, %lor.rhs
380  %g.3 = phi i32 [ %g.230, %for.body5 ], [ %call11, %lor.rhs ]
381  %3 = phi i1 [ true, %for.body5 ], [ %tobool12, %lor.rhs ]
382  %lor.ext = zext i1 %3 to i32
383  %inc15 = add nuw nsw i32 %i.031, 1
384  %exitcond = icmp ne i32 %inc15, 9
385  br i1 %exitcond, label %for.body5, label %for.end16
386
387for.end16:                                        ; preds = %lor.end
388  %g.3.lcssa = phi i32 [ %g.3, %lor.end ]
389  %inc18 = add nuw nsw i32 %f.033, 1
390  %exitcond34 = icmp ne i32 %inc18, 7
391  br i1 %exitcond34, label %for.body, label %for.end19
392
393for.end19:                                        ; preds = %for.end16
394  ret i32 undef
395}
396