1; RUN: opt < %s -S -loop-flatten -debug-only=loop-flatten 2>&1 | FileCheck %s
2; REQUIRES: asserts
3
4target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
5
6; Every function in this file has a reason that it can't be transformed.
7
8; CHECK-NOT: Checks all passed, doing the transformation
9
10; Outer loop does not start at zero
11define void @test_1(i32 %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
12entry:
13  %cmp25 = icmp sgt i32 %N, 0
14  br i1 %cmp25, label %for.body4.lr.ph, label %for.cond.cleanup
15
16for.body4.lr.ph:
17  %i.026 = phi i32 [ %inc10, %for.cond.cleanup3 ], [ 1, %entry ]
18  %mul = mul nsw i32 %i.026, %N
19  br label %for.body4
20
21for.body4:
22  %j.024 = phi i32 [ 0, %for.body4.lr.ph ], [ %inc, %for.body4 ]
23  %add = add nsw i32 %j.024, %mul
24  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
25  %0 = load i32, i32* %arrayidx, align 4
26  %mul5 = mul nsw i32 %0, %scale
27  %arrayidx8 = getelementptr inbounds i32, i32* %C, i32 %add
28  store i32 %mul5, i32* %arrayidx8, align 4
29  %inc = add nuw nsw i32 %j.024, 1
30  %exitcond = icmp eq i32 %inc, %N
31  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
32
33for.cond.cleanup3:
34  %inc10 = add nuw nsw i32 %i.026, 1
35  %exitcond27 = icmp eq i32 %inc10, %N
36  br i1 %exitcond27, label %for.cond.cleanup, label %for.body4.lr.ph
37
38for.cond.cleanup:
39  ret void
40}
41
42; Inner loop does not start at zero
43define void @test_2(i32 %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
44entry:
45  %cmp25 = icmp sgt i32 %N, 0
46  br i1 %cmp25, label %for.body4.lr.ph, label %for.cond.cleanup
47
48for.body4.lr.ph:
49  %i.026 = phi i32 [ %inc10, %for.cond.cleanup3 ], [ 0, %entry ]
50  %mul = mul nsw i32 %i.026, %N
51  br label %for.body4
52
53for.body4:
54  %j.024 = phi i32 [ 1, %for.body4.lr.ph ], [ %inc, %for.body4 ]
55  %add = add nsw i32 %j.024, %mul
56  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
57  %0 = load i32, i32* %arrayidx, align 4
58  %mul5 = mul nsw i32 %0, %scale
59  %arrayidx8 = getelementptr inbounds i32, i32* %C, i32 %add
60  store i32 %mul5, i32* %arrayidx8, align 4
61  %inc = add nuw nsw i32 %j.024, 1
62  %exitcond = icmp eq i32 %inc, %N
63  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
64
65for.cond.cleanup3:
66  %inc10 = add nuw nsw i32 %i.026, 1
67  %exitcond27 = icmp eq i32 %inc10, %N
68  br i1 %exitcond27, label %for.cond.cleanup, label %for.body4.lr.ph
69
70for.cond.cleanup:
71  ret void
72}
73
74; Outer IV used directly
75define hidden void @test_3(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
76entry:
77  %conv = zext i16 %N to i32
78  %cmp25 = icmp eq i16 %N, 0
79  br i1 %cmp25, label %for.cond.cleanup, label %for.body.lr.ph.split.us
80
81for.body.lr.ph.split.us:                          ; preds = %entry
82  br label %for.body.us
83
84for.body.us:                                      ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.lr.ph.split.us
85  %i.026.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.cond.cleanup6_crit_edge.us ]
86  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %i.026.us
87  %mul9.us = mul nuw nsw i32 %i.026.us, %conv
88  br label %for.body7.us
89
90for.body7.us:                                     ; preds = %for.body.us, %for.body7.us
91  %j.024.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body7.us ]
92  %0 = load i32, i32* %arrayidx.us, align 4
93  %mul.us = mul nsw i32 %0, %scale
94  %add.us = add nuw nsw i32 %j.024.us, %mul9.us
95  %arrayidx10.us = getelementptr inbounds i32, i32* %C, i32 %add.us
96  store i32 %mul.us, i32* %arrayidx10.us, align 4
97  %inc.us = add nuw nsw i32 %j.024.us, 1
98  %exitcond = icmp ne i32 %inc.us, %conv
99  br i1 %exitcond, label %for.body7.us, label %for.cond2.for.cond.cleanup6_crit_edge.us
100
101for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
102  %inc12.us = add nuw nsw i32 %i.026.us, 1
103  %exitcond27 = icmp ne i32 %inc12.us, %conv
104  br i1 %exitcond27, label %for.body.us, label %for.cond.cleanup.loopexit
105
106for.cond.cleanup.loopexit:                        ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us
107  br label %for.cond.cleanup
108
109for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
110  ret void
111}
112
113; Inner IV used directly
114define hidden void @test_4(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
115entry:
116  %conv = zext i16 %N to i32
117  %cmp25 = icmp eq i16 %N, 0
118  br i1 %cmp25, label %for.cond.cleanup, label %for.body.lr.ph.split.us
119
120for.body.lr.ph.split.us:                          ; preds = %entry
121  br label %for.body.us
122
123for.body.us:                                      ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.lr.ph.split.us
124  %i.026.us = phi i32 [ 0, %for.body.lr.ph.split.us ], [ %inc12.us, %for.cond2.for.cond.cleanup6_crit_edge.us ]
125  %mul9.us = mul nuw nsw i32 %i.026.us, %conv
126  br label %for.body7.us
127
128for.body7.us:                                     ; preds = %for.body.us, %for.body7.us
129  %j.024.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body7.us ]
130  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %j.024.us
131  %0 = load i32, i32* %arrayidx.us, align 4
132  %mul.us = mul nsw i32 %0, %scale
133  %add.us = add nuw nsw i32 %j.024.us, %mul9.us
134  %arrayidx10.us = getelementptr inbounds i32, i32* %C, i32 %add.us
135  store i32 %mul.us, i32* %arrayidx10.us, align 4
136  %inc.us = add nuw nsw i32 %j.024.us, 1
137  %exitcond = icmp ne i32 %inc.us, %conv
138  br i1 %exitcond, label %for.body7.us, label %for.cond2.for.cond.cleanup6_crit_edge.us
139
140for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
141  %inc12.us = add nuw nsw i32 %i.026.us, 1
142  %exitcond27 = icmp ne i32 %inc12.us, %conv
143  br i1 %exitcond27, label %for.body.us, label %for.cond.cleanup.loopexit
144
145for.cond.cleanup.loopexit:                        ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us
146  br label %for.cond.cleanup
147
148for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
149  ret void
150}
151
152; Inner iteration count not invariant in outer loop
153declare i32 @get_int() readonly
154define void @test_5(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
155entry:
156  %conv = zext i16 %N to i32
157  %cmp27 = icmp eq i16 %N, 0
158  br i1 %cmp27, label %for.cond.cleanup, label %for.body.lr.ph
159
160for.body.lr.ph:                                   ; preds = %entry
161  br label %for.body
162
163for.cond.cleanup.loopexit:                        ; preds = %for.cond.cleanup5
164  br label %for.cond.cleanup
165
166for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
167  ret void
168
169for.body:                                         ; preds = %for.body.lr.ph, %for.cond.cleanup5
170  %i.028 = phi i32 [ 0, %for.body.lr.ph ], [ %inc12, %for.cond.cleanup5 ]
171  %call = tail call i32 @get_int()
172  %cmp325 = icmp sgt i32 %call, 0
173  br i1 %cmp325, label %for.body6.lr.ph, label %for.cond.cleanup5
174
175for.body6.lr.ph:                                  ; preds = %for.body
176  %mul = mul nsw i32 %call, %i.028
177  br label %for.body6
178
179for.cond.cleanup5.loopexit:                       ; preds = %for.body6
180  br label %for.cond.cleanup5
181
182for.cond.cleanup5:                                ; preds = %for.cond.cleanup5.loopexit, %for.body
183  %inc12 = add nuw nsw i32 %i.028, 1
184  %exitcond29 = icmp ne i32 %inc12, %conv
185  br i1 %exitcond29, label %for.body, label %for.cond.cleanup.loopexit
186
187for.body6:                                        ; preds = %for.body6.lr.ph, %for.body6
188  %j.026 = phi i32 [ 0, %for.body6.lr.ph ], [ %inc, %for.body6 ]
189  %add = add nsw i32 %j.026, %mul
190  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
191  %0 = load i32, i32* %arrayidx, align 4
192  %mul7 = mul nsw i32 %0, %scale
193  %arrayidx10 = getelementptr inbounds i32, i32* %C, i32 %add
194  store i32 %mul7, i32* %arrayidx10, align 4
195  %inc = add nuw nsw i32 %j.026, 1
196  %exitcond = icmp ne i32 %inc, %call
197  br i1 %exitcond, label %for.body6, label %for.cond.cleanup5.loopexit
198}
199
200; Inner loop has an early exit
201define hidden void @test_6(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
202entry:
203  %conv = zext i16 %N to i32
204  %cmp39 = icmp eq i16 %N, 0
205  br i1 %cmp39, label %for.cond.cleanup, label %for.body.us.preheader
206
207for.body.us.preheader:                            ; preds = %entry
208  br label %for.body.us
209
210for.body.us:                                      ; preds = %for.body.us.preheader, %cleanup.us
211  %i.040.us = phi i32 [ %inc19.us, %cleanup.us ], [ 0, %for.body.us.preheader ]
212  %mul.us = mul nuw nsw i32 %i.040.us, %conv
213  br label %for.body7.us
214
215for.body7.us:                                     ; preds = %for.body.us, %if.end.us
216  %j.038.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %if.end.us ]
217  %add.us = add nuw nsw i32 %j.038.us, %mul.us
218  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %add.us
219  %0 = load i32, i32* %arrayidx.us, align 4
220  %tobool.us = icmp eq i32 %0, 0
221  br i1 %tobool.us, label %if.end.us, label %cleanup.us
222
223cleanup.us:                                       ; preds = %if.end.us, %for.body7.us
224  %inc19.us = add nuw nsw i32 %i.040.us, 1
225  %exitcond = icmp eq i32 %inc19.us, %conv
226  br i1 %exitcond, label %for.cond.cleanup, label %for.body.us
227
228if.end.us:                                        ; preds = %for.body7.us
229  %arrayidx17.us = getelementptr inbounds i32, i32* %C, i32 %add.us
230  store i32 0, i32* %arrayidx17.us, align 4
231  %inc.us = add nuw nsw i32 %j.038.us, 1
232  %cmp4.us = icmp ult i32 %inc.us, %conv
233  br i1 %cmp4.us, label %for.body7.us, label %cleanup.us
234
235for.cond.cleanup:                                 ; preds = %cleanup.us, %entry
236  ret void
237}
238
239define hidden void @test_7(i16 zeroext %N, i32* nocapture %C, i32* nocapture readonly %A, i32 %scale) {
240entry:
241  %conv = zext i16 %N to i32
242  %cmp30 = icmp eq i16 %N, 0
243  br i1 %cmp30, label %cleanup, label %for.body.us.preheader
244
245for.body.us.preheader:                            ; preds = %entry
246  br label %for.body.us
247
248for.body.us:                                      ; preds = %for.body.us.preheader, %for.cond2.for.cond.cleanup6_crit_edge.us
249  %i.031.us = phi i32 [ %inc15.us, %for.cond2.for.cond.cleanup6_crit_edge.us ], [ 0, %for.body.us.preheader ]
250  %call.us = tail call i32 @get_int() #2
251  %tobool.us = icmp eq i32 %call.us, 0
252  br i1 %tobool.us, label %for.body7.lr.ph.us, label %cleanup
253
254for.body7.us:                                     ; preds = %for.body7.us, %for.body7.lr.ph.us
255  %j.029.us = phi i32 [ 0, %for.body7.lr.ph.us ], [ %inc.us, %for.body7.us ]
256  %add.us = add nuw nsw i32 %j.029.us, %mul.us
257  %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %add.us
258  %0 = load i32, i32* %arrayidx.us, align 4
259  %mul9.us = mul nsw i32 %0, %scale
260  %arrayidx13.us = getelementptr inbounds i32, i32* %C, i32 %add.us
261  store i32 %mul9.us, i32* %arrayidx13.us, align 4
262  %inc.us = add nuw nsw i32 %j.029.us, 1
263  %exitcond = icmp eq i32 %inc.us, %conv
264  br i1 %exitcond, label %for.cond2.for.cond.cleanup6_crit_edge.us, label %for.body7.us
265
266for.body7.lr.ph.us:                               ; preds = %for.body.us
267  %mul.us = mul nuw nsw i32 %i.031.us, %conv
268  br label %for.body7.us
269
270for.cond2.for.cond.cleanup6_crit_edge.us:         ; preds = %for.body7.us
271  %inc15.us = add nuw nsw i32 %i.031.us, 1
272  %cmp.us = icmp ult i32 %inc15.us, %conv
273  br i1 %cmp.us, label %for.body.us, label %cleanup
274
275cleanup:                                          ; preds = %for.cond2.for.cond.cleanup6_crit_edge.us, %for.body.us, %entry
276  ret void
277}
278
279; Step is not 1
280define i32 @test_8(i32 %val, i16* nocapture %A) {
281entry:
282  br label %for.body
283
284for.body:                                         ; preds = %entry, %for.inc6
285  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
286  %mul = mul nuw nsw i32 %i.018, 20
287  br label %for.body3
288
289for.body3:                                        ; preds = %for.body, %for.body3
290  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
291  %add = add nuw nsw i32 %j.017, %mul
292  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
293  %0 = load i16, i16* %arrayidx, align 2
294  %conv16 = zext i16 %0 to i32
295  %add4 = add i32 %conv16, %val
296  %conv5 = trunc i32 %add4 to i16
297  store i16 %conv5, i16* %arrayidx, align 2
298  %inc = add nuw nsw i32 %j.017, 1
299  %exitcond = icmp ne i32 %inc, 20
300  br i1 %exitcond, label %for.body3, label %for.inc6
301
302for.inc6:                                         ; preds = %for.body3
303  %inc7 = add nuw nsw i32 %i.018, 2
304  %exitcond19 = icmp ne i32 %inc7, 10
305  br i1 %exitcond19, label %for.body, label %for.end8
306
307for.end8:                                         ; preds = %for.inc6
308  ret i32 10
309}
310
311
312; Step is not 1
313define i32 @test_9(i32 %val, i16* nocapture %A) {
314entry:
315  br label %for.body
316
317for.body:                                         ; preds = %entry, %for.inc6
318  %i.018 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
319  %mul = mul nuw nsw i32 %i.018, 20
320  br label %for.body3
321
322for.body3:                                        ; preds = %for.body, %for.body3
323  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
324  %add = add nuw nsw i32 %j.017, %mul
325  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
326  %0 = load i16, i16* %arrayidx, align 2
327  %conv16 = zext i16 %0 to i32
328  %add4 = add i32 %conv16, %val
329  %conv5 = trunc i32 %add4 to i16
330  store i16 %conv5, i16* %arrayidx, align 2
331  %inc = add nuw nsw i32 %j.017, 2
332  %exitcond = icmp ne i32 %inc, 20
333  br i1 %exitcond, label %for.body3, label %for.inc6
334
335for.inc6:                                         ; preds = %for.body3
336  %inc7 = add nuw nsw i32 %i.018, 1
337  %exitcond19 = icmp ne i32 %inc7, 10
338  br i1 %exitcond19, label %for.body, label %for.end8
339
340for.end8:                                         ; preds = %for.inc6
341  ret i32 10
342}
343
344; test_10, test_11 and test_12 are for the case when the
345; inner trip count is a constant, then the InstCombine pass
346; makes the transformation icmp ult i32 %inc, tripcount ->
347; icmp ult i32 %j, tripcount-step.
348
349; test_10: The step is not 1.
350define i32 @test_10(i32* nocapture %A) {
351entry:
352  br label %for.cond1.preheader
353
354for.cond1.preheader:
355  %i.017 = phi i32 [ 0, %entry ], [ %inc, %for.cond.cleanup3 ]
356  %mul = mul i32 %i.017, 20
357  br label %for.body4
358
359for.body4:
360  %j.016 = phi i32 [ 0, %for.cond1.preheader ], [ %add5, %for.body4 ]
361  %add = add i32 %j.016, %mul
362  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
363  store i32 30, i32* %arrayidx, align 4
364  %add5 = add nuw nsw i32 %j.016, 2
365  %cmp2 = icmp ult i32 %j.016, 18
366  br i1 %cmp2, label %for.body4, label %for.cond.cleanup3
367
368for.cond.cleanup3:
369  %inc = add i32 %i.017, 1
370  %cmp = icmp ult i32 %inc, 11
371  br i1 %cmp, label %for.cond1.preheader, label %for.cond.cleanup
372
373for.cond.cleanup:
374  %0 = load i32, i32* %A, align 4
375  ret i32 %0
376}
377
378; test_11: The inner inducation variable is used in a compare which
379; isn't the condition of the inner branch.
380define i32 @test_11(i32* nocapture %A) {
381entry:
382  br label %for.cond1.preheader
383
384for.cond1.preheader:
385  %i.020 = phi i32 [ 0, %entry ], [ %inc7, %for.cond.cleanup3 ]
386  %mul = mul i32 %i.020, 20
387  br label %for.body4
388
389for.body4:
390  %j.019 = phi i32 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ]
391  %cmp5 = icmp ult i32 %j.019, 5
392  %cond = select i1 %cmp5, i32 30, i32 15
393  %add = add i32 %j.019, %mul
394  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
395  store i32 %cond, i32* %arrayidx, align 4
396  %inc = add nuw nsw i32 %j.019, 1
397  %cmp2 = icmp ult i32 %j.019, 19
398  br i1 %cmp2, label %for.body4, label %for.cond.cleanup3
399
400for.cond.cleanup3:
401  %inc7 = add i32 %i.020, 1
402  %cmp = icmp ult i32 %inc7, 11
403  br i1 %cmp, label %for.cond1.preheader, label %for.cond.cleanup
404
405for.cond.cleanup:
406  %0 = load i32, i32* %A, align 4
407  ret i32 %0
408}
409
410; test_12: Incoming phi node value for preheader is a variable
411define i32 @test_12(i32* %A) {
412entry:
413  br label %while.cond1.preheader
414
415while.cond1.preheader:
416  %j.017 = phi i32 [ 0, %entry ], [ %j.1, %while.end ]
417  %i.016 = phi i32 [ 0, %entry ], [ %inc4, %while.end ]
418  %mul = mul i32 %i.016, 20
419  %cmp214 = icmp ult i32 %j.017, 20
420  br i1 %cmp214, label %while.body3.preheader, label %while.end
421
422while.body3.preheader:
423  br label %while.body3
424
425while.body3:
426  %j.115 = phi i32 [ %inc, %while.body3 ], [ %j.017, %while.body3.preheader ]
427  %add = add i32 %j.115, %mul
428  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %add
429  store i32 30, i32* %arrayidx, align 4
430  %inc = add nuw nsw i32 %j.115, 1
431  %cmp2 = icmp ult i32 %j.115, 19
432  br i1 %cmp2, label %while.body3, label %while.end.loopexit
433
434while.end.loopexit:
435  %inc.lcssa = phi i32 [ %inc, %while.body3 ]
436  br label %while.end
437
438while.end:
439  %j.1 = phi i32 [ %j.017, %while.cond1.preheader], [ %inc.lcssa, %while.end.loopexit ]
440  %inc4 = add i32 %i.016, 1
441  %cmp = icmp ult i32 %inc4, 11
442  br i1 %cmp, label %while.cond1.preheader, label %while.end5
443
444while.end5:
445  %0 = load i32, i32* %A, align 4
446  ret i32 %0
447}
448
449; Outer loop conditional phi
450define i32 @e() {
451entry:
452  br label %for.body
453
454for.body:                                         ; preds = %entry, %for.end16
455  %f.033 = phi i32 [ 0, %entry ], [ %inc18, %for.end16 ]
456  %g.032 = phi i32 [ undef, %entry ], [ %g.3.lcssa, %for.end16 ]
457  %.pr = add i32 10, 10
458  %tobool29 = icmp eq i32 %.pr, 0
459  br i1 %tobool29, label %for.end, label %for.body2.lr.ph
460
461for.body2.lr.ph:                                  ; preds = %for.body
462  br label %for.cond1.for.end_crit_edge
463
464for.cond1.for.end_crit_edge:                      ; preds = %for.body2.lr.ph
465  br label %for.end
466
467for.end:                                          ; preds = %for.cond1.for.end_crit_edge, %for.body
468  %g.1.lcssa = phi i32 [ 0, %for.cond1.for.end_crit_edge ], [ %g.032, %for.body ]
469  br label %for.body5
470
471for.body5:                                        ; preds = %for.end, %lor.end
472  %i.031 = phi i32 [ 0, %for.end ], [ %inc15, %lor.end ]
473  %g.230 = phi i32 [ %g.1.lcssa, %for.end ], [ %g.3, %lor.end ]
474  %0 = add i32 10, 10
475  %1 = add i32 10, 10
476  %tobool9 = icmp eq i32 %1, 0
477  br i1 %tobool9, label %lor.rhs, label %lor.end
478
479lor.rhs:                                          ; preds = %for.body5
480  %2 = add i32 10, 10
481  %call11 = add i32 10, 10
482  %tobool12 = icmp ne i32 %call11, 0
483  br label %lor.end
484
485lor.end:                                          ; preds = %for.body5, %lor.rhs
486  %g.3 = phi i32 [ %g.230, %for.body5 ], [ %call11, %lor.rhs ]
487  %3 = phi i1 [ true, %for.body5 ], [ %tobool12, %lor.rhs ]
488  %lor.ext = zext i1 %3 to i32
489  %inc15 = add nuw nsw i32 %i.031, 1
490  %exitcond = icmp ne i32 %inc15, 9
491  br i1 %exitcond, label %for.body5, label %for.end16
492
493for.end16:                                        ; preds = %lor.end
494  %g.3.lcssa = phi i32 [ %g.3, %lor.end ]
495  %inc18 = add nuw nsw i32 %f.033, 1
496  %exitcond34 = icmp ne i32 %inc18, 7
497  br i1 %exitcond34, label %for.body, label %for.end19
498
499for.end19:                                        ; preds = %for.end16
500  ret i32 undef
501}
502
503; A 3d loop corresponding to:
504;
505; for (int i = 0; i < N; ++i)
506;    for (int j = 0; j < N; ++j)
507;      for (int k = 0; k < N; ++k)
508;        f(&A[i + N * (j + N * k)]);
509;
510define void @d3_1(i32* %A, i32 %N) {
511entry:
512  %cmp35 = icmp sgt i32 %N, 0
513  br i1 %cmp35, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
514
515for.cond1.preheader.lr.ph:
516  br label %for.cond1.preheader.us
517
518for.cond1.preheader.us:
519  %i.036.us = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc15.us, %for.cond1.for.cond.cleanup3_crit_edge.us ]
520  br i1 true, label %for.cond5.preheader.us.us.preheader, label %for.cond5.preheader.us52.preheader
521
522for.cond5.preheader.us52.preheader:
523  br label %for.cond5.preheader.us52
524
525for.cond5.preheader.us.us.preheader:
526  br label %for.cond5.preheader.us.us
527
528for.cond5.preheader.us52:
529  br i1 false, label %for.cond5.preheader.us52, label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit58
530
531for.cond1.for.cond.cleanup3_crit_edge.us.loopexit:
532  br label %for.cond1.for.cond.cleanup3_crit_edge.us
533
534for.cond1.for.cond.cleanup3_crit_edge.us.loopexit58:
535  br label %for.cond1.for.cond.cleanup3_crit_edge.us
536
537for.cond1.for.cond.cleanup3_crit_edge.us:
538  %inc15.us = add nuw nsw i32 %i.036.us, 1
539  %cmp.us = icmp slt i32 %inc15.us, %N
540  br i1 %cmp.us, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit
541
542for.cond5.preheader.us.us:
543  %j.033.us.us = phi i32 [ %inc12.us.us, %for.cond5.for.cond.cleanup7_crit_edge.us.us ], [ 0, %for.cond5.preheader.us.us.preheader ]
544  br label %for.body8.us.us
545
546for.cond5.for.cond.cleanup7_crit_edge.us.us:
547  %inc12.us.us = add nuw nsw i32 %j.033.us.us, 1
548  %cmp2.us.us = icmp slt i32 %inc12.us.us, %N
549  br i1 %cmp2.us.us, label %for.cond5.preheader.us.us, label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit
550
551for.body8.us.us:
552  %k.031.us.us = phi i32 [ 0, %for.cond5.preheader.us.us ], [ %inc.us.us, %for.body8.us.us ]
553  %mul.us.us = mul nsw i32 %k.031.us.us, %N
554  %add.us.us = add nsw i32 %mul.us.us, %j.033.us.us
555  %mul9.us.us = mul nsw i32 %add.us.us, %N
556  %add10.us.us = add nsw i32 %mul9.us.us, %i.036.us
557  %idxprom.us.us = sext i32 %add10.us.us to i64
558  %arrayidx.us.us = getelementptr inbounds i32, i32* %A, i64 %idxprom.us.us
559  tail call void @f(i32* %arrayidx.us.us) #2
560  %inc.us.us = add nuw nsw i32 %k.031.us.us, 1
561  %cmp6.us.us = icmp slt i32 %inc.us.us, %N
562  br i1 %cmp6.us.us, label %for.body8.us.us, label %for.cond5.for.cond.cleanup7_crit_edge.us.us
563
564for.cond.cleanup.loopexit:
565  br label %for.cond.cleanup
566
567for.cond.cleanup:
568  ret void
569}
570
571; A 3d loop corresponding to:
572;
573;   for (int k = 0; k < N; ++k)
574;    for (int i = 0; i < N; ++i)
575;      for (int j = 0; j < M; ++j)
576;        f(&A[i*M+j]);
577;
578; This could be supported, but isn't at the moment.
579;
580define void @d3_2(i32* %A, i32 %N, i32 %M) {
581entry:
582  %cmp30 = icmp sgt i32 %N, 0
583  br i1 %cmp30, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
584
585for.cond1.preheader.lr.ph:
586  %cmp625 = icmp sgt i32 %M, 0
587  br label %for.cond1.preheader.us
588
589for.cond1.preheader.us:
590  %k.031.us = phi i32 [ 0, %for.cond1.preheader.lr.ph ], [ %inc13.us, %for.cond1.for.cond.cleanup3_crit_edge.us ]
591  br i1 %cmp625, label %for.cond5.preheader.us.us.preheader, label %for.cond5.preheader.us43.preheader
592
593for.cond5.preheader.us43.preheader:
594  br label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit50
595
596for.cond5.preheader.us.us.preheader:
597  br label %for.cond5.preheader.us.us
598
599for.cond1.for.cond.cleanup3_crit_edge.us.loopexit:
600  br label %for.cond1.for.cond.cleanup3_crit_edge.us
601
602for.cond1.for.cond.cleanup3_crit_edge.us.loopexit50:
603  br label %for.cond1.for.cond.cleanup3_crit_edge.us
604
605for.cond1.for.cond.cleanup3_crit_edge.us:
606  %inc13.us = add nuw nsw i32 %k.031.us, 1
607  %exitcond52 = icmp ne i32 %inc13.us, %N
608  br i1 %exitcond52, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit
609
610for.cond5.preheader.us.us:
611  %i.028.us.us = phi i32 [ %inc10.us.us, %for.cond5.for.cond.cleanup7_crit_edge.us.us ], [ 0, %for.cond5.preheader.us.us.preheader ]
612  %mul.us.us = mul nsw i32 %i.028.us.us, %M
613  br label %for.body8.us.us
614
615for.cond5.for.cond.cleanup7_crit_edge.us.us:
616  %inc10.us.us = add nuw nsw i32 %i.028.us.us, 1
617  %exitcond51 = icmp ne i32 %inc10.us.us, %N
618  br i1 %exitcond51, label %for.cond5.preheader.us.us, label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit
619
620for.body8.us.us:
621  %j.026.us.us = phi i32 [ 0, %for.cond5.preheader.us.us ], [ %inc.us.us, %for.body8.us.us ]
622  %add.us.us = add nsw i32 %j.026.us.us, %mul.us.us
623  %idxprom.us.us = sext i32 %add.us.us to i64
624  %arrayidx.us.us = getelementptr inbounds i32, i32* %A, i64 %idxprom.us.us
625  tail call void @f(i32* %arrayidx.us.us) #2
626  %inc.us.us = add nuw nsw i32 %j.026.us.us, 1
627  %exitcond = icmp ne i32 %inc.us.us, %M
628  br i1 %exitcond, label %for.body8.us.us, label %for.cond5.for.cond.cleanup7_crit_edge.us.us
629
630for.cond.cleanup.loopexit:
631  br label %for.cond.cleanup
632
633for.cond.cleanup:
634  ret void
635}
636
637; A 3d loop corresponding to:
638;
639;   for (int i = 0; i < N; ++i)
640;     for (int j = 0; j < M; ++j) {
641;       A[i*M+j] = 0;
642;       for (int k = 0; k < N; ++k)
643;         g();
644;     }
645;
646define void @d3_3(i32* nocapture %A, i32 %N, i32 %M) {
647entry:
648  %cmp29 = icmp sgt i32 %N, 0
649  br i1 %cmp29, label %for.cond1.preheader.lr.ph, label %for.cond.cleanup
650
651for.cond1.preheader.lr.ph:
652  %cmp227 = icmp sgt i32 %M, 0
653  br i1 %cmp227, label %for.cond1.preheader.us.preheader, label %for.cond1.preheader.preheader
654
655for.cond1.preheader.preheader:
656  br label %for.cond.cleanup.loopexit49
657
658for.cond1.preheader.us.preheader:
659  br label %for.cond1.preheader.us
660
661for.cond1.preheader.us:
662  %i.030.us = phi i32 [ %inc13.us, %for.cond1.for.cond.cleanup3_crit_edge.us ], [ 0, %for.cond1.preheader.us.preheader ]
663  %mul.us = mul nsw i32 %i.030.us, %M
664  br i1 true, label %for.body4.us.us.preheader, label %for.body4.us32.preheader
665
666for.body4.us32.preheader:
667  br label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit48
668
669for.body4.us.us.preheader:
670  br label %for.body4.us.us
671
672for.cond1.for.cond.cleanup3_crit_edge.us.loopexit:
673  br label %for.cond1.for.cond.cleanup3_crit_edge.us
674
675for.cond1.for.cond.cleanup3_crit_edge.us.loopexit48:
676  br label %for.cond1.for.cond.cleanup3_crit_edge.us
677
678for.cond1.for.cond.cleanup3_crit_edge.us:
679  %inc13.us = add nuw nsw i32 %i.030.us, 1
680  %exitcond51 = icmp ne i32 %inc13.us, %N
681  br i1 %exitcond51, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit
682
683for.body4.us.us:
684  %j.028.us.us = phi i32 [ %inc10.us.us, %for.cond5.for.cond.cleanup7_crit_edge.us.us ], [ 0, %for.body4.us.us.preheader ]
685  %add.us.us = add nsw i32 %j.028.us.us, %mul.us
686  %idxprom.us.us = sext i32 %add.us.us to i64
687  %arrayidx.us.us = getelementptr inbounds i32, i32* %A, i64 %idxprom.us.us
688  store i32 0, i32* %arrayidx.us.us, align 4
689  br label %for.body8.us.us
690
691for.cond5.for.cond.cleanup7_crit_edge.us.us:
692  %inc10.us.us = add nuw nsw i32 %j.028.us.us, 1
693  %exitcond50 = icmp ne i32 %inc10.us.us, %M
694  br i1 %exitcond50, label %for.body4.us.us, label %for.cond1.for.cond.cleanup3_crit_edge.us.loopexit
695
696for.body8.us.us:
697  %k.026.us.us = phi i32 [ 0, %for.body4.us.us ], [ %inc.us.us, %for.body8.us.us ]
698  tail call void bitcast (void (...)* @g to void ()*)() #2
699  %inc.us.us = add nuw nsw i32 %k.026.us.us, 1
700  %exitcond = icmp ne i32 %inc.us.us, %N
701  br i1 %exitcond, label %for.body8.us.us, label %for.cond5.for.cond.cleanup7_crit_edge.us.us
702
703for.cond.cleanup.loopexit:
704  br label %for.cond.cleanup
705
706for.cond.cleanup.loopexit49:
707  br label %for.cond.cleanup
708
709for.cond.cleanup:
710  ret void
711}
712
713; Backedge-taken count is not predictable.
714%struct.Limits = type { i16, i16 }
715define void @backedge_count(%struct.Limits* %lim) {
716entry:
717  %N = getelementptr inbounds %struct.Limits, %struct.Limits* %lim, i32 0, i32 0
718  %M = getelementptr inbounds %struct.Limits, %struct.Limits* %lim, i32 0, i32 1
719  %0 = load i16, i16* %N, align 2
720  %cmp20 = icmp sgt i16 %0, 0
721  br i1 %cmp20, label %for.cond2.preheader.preheader, label %for.cond.cleanup
722
723for.cond2.preheader.preheader:
724  %.pre = load i16, i16* %M, align 2
725  br label %for.cond2.preheader
726
727for.cond2.preheader:
728  %1 = phi i16 [ %3, %for.cond.cleanup6 ], [ %0, %for.cond2.preheader.preheader ]
729  %2 = phi i16 [ %4, %for.cond.cleanup6 ], [ %.pre, %for.cond2.preheader.preheader ]
730  %i.021 = phi i32 [ %inc9, %for.cond.cleanup6 ], [ 0, %for.cond2.preheader.preheader ]
731  %cmp417 = icmp sgt i16 %2, 0
732  br i1 %cmp417, label %for.body7, label %for.cond.cleanup6
733
734for.cond.cleanup:
735  ret void
736
737for.cond.cleanup6.loopexit:
738  %.pre22 = load i16, i16* %N, align 2
739  br label %for.cond.cleanup6
740
741for.cond.cleanup6:
742  %3 = phi i16 [ %.pre22, %for.cond.cleanup6.loopexit ], [ %1, %for.cond2.preheader ]
743  %4 = phi i16 [ %5, %for.cond.cleanup6.loopexit ], [ %2, %for.cond2.preheader ]
744  %inc9 = add nuw nsw i32 %i.021, 1
745  %conv = sext i16 %3 to i32
746  %cmp = icmp slt i32 %inc9, %conv
747  br i1 %cmp, label %for.cond2.preheader, label %for.cond.cleanup
748
749for.body7:
750  %j.018 = phi i32 [ %inc, %for.body7 ], [ 0, %for.cond2.preheader ]
751  tail call void bitcast (void (...)* @g to void ()*)()
752  %inc = add nuw nsw i32 %j.018, 1
753  %5 = load i16, i16* %M, align 2
754  %conv3 = sext i16 %5 to i32
755  %cmp4 = icmp slt i32 %inc, %conv3
756  br i1 %cmp4, label %for.body7, label %for.cond.cleanup6.loopexit
757}
758
759; Invalid trip count
760define void @invalid_tripCount(i8* %a, i32 %b, i32 %c, i32 %initial-mutations, i32 %statemutations) {
761entry:
762  %iszero = icmp eq i32 %b, 0
763  br i1 %iszero, label %for.empty, label %for.loopinit
764for.loopinit:
765  br label %for.loopbody.outer
766for.loopbody.outer:
767  %for.count.ph = phi i32 [ %c, %for.refetch ], [ %b, %for.loopinit ]
768  br label %for.loopbody
769for.loopbody:
770  %for.index = phi i32 [ %1, %for.notmutated ], [ 0, %for.loopbody.outer ]
771  %0 = icmp eq i32 %statemutations, %initial-mutations
772  br i1 %0, label %for.notmutated, label %for.mutated
773for.mutated:
774  call void @objc_enumerationMutation(i8* %a)
775  br label %for.notmutated
776for.notmutated:
777  %1 = add nuw i32 %for.index, 1
778  %2 = icmp ult i32 %1, %for.count.ph
779  br i1 %2, label %for.loopbody, label %for.refetch
780for.refetch:
781  %3 = icmp eq i32 %c, 0
782  br i1 %3, label %for.empty.loopexit, label %for.loopbody.outer
783for.empty.loopexit:
784  br label %for.empty
785for.empty:
786  ret void
787}
788
789; GEP doesn't dominate the loop latch so can't guarantee N*M won't overflow.
790@first = global i32 1, align 4
791@a = external global [0 x i8], align 1
792define void @overflow(i32 %lim, i8* %a) {
793entry:
794  %cmp17.not = icmp eq i32 %lim, 0
795  br i1 %cmp17.not, label %for.cond.cleanup, label %for.cond1.preheader.preheader
796
797for.cond1.preheader.preheader:
798  br label %for.cond1.preheader
799
800for.cond1.preheader:
801  %i.018 = phi i32 [ %inc6, %for.cond.cleanup3 ], [ 0, %for.cond1.preheader.preheader ]
802  %mul = mul i32 %i.018, 100000
803  br label %for.body4
804
805for.cond.cleanup.loopexit:
806  br label %for.cond.cleanup
807
808for.cond.cleanup:
809  ret void
810
811for.cond.cleanup3:
812  %inc6 = add i32 %i.018, 1
813  %cmp = icmp ult i32 %inc6, %lim
814  br i1 %cmp, label %for.cond1.preheader, label %for.cond.cleanup.loopexit
815
816for.body4:
817  %j.016 = phi i32 [ 0, %for.cond1.preheader ], [ %inc, %if.end ]
818  %add = add i32 %j.016, %mul
819  %0 = load i32, i32* @first, align 4
820  %tobool.not = icmp eq i32 %0, 0
821  br i1 %tobool.not, label %if.end, label %if.then
822
823if.then:
824  %arrayidx = getelementptr inbounds [0 x i8], [0 x i8]* @a, i32 0, i32 %add
825  %1 = load i8, i8* %arrayidx, align 1
826  tail call void asm sideeffect "", "r"(i8 %1)
827  store i32 0, i32* @first, align 4
828  br label %if.end
829
830if.end:
831  tail call void asm sideeffect "", "r"(i32 %add)
832  %inc = add nuw nsw i32 %j.016, 1
833  %cmp2 = icmp ult i32 %j.016, 99999
834  br i1 %cmp2, label %for.body4, label %for.cond.cleanup3
835}
836
837declare void @objc_enumerationMutation(i8*)
838declare dso_local void @f(i32*)
839declare dso_local void @g(...)
840