1; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s
2; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop-unroll,verify<loops>' | FileCheck %s
3;
4; Unit tests for LoopInfo::markAsRemoved.
5
6declare i1 @check() nounwind
7
8; Ensure that tail->inner is removed and rely on verify-loopinfo to
9; check soundness.
10;
11; CHECK-LABEL: @skiplevelexit(
12; CHECK: tail:
13; CHECK-NOT: br
14; CHECK: ret void
15define void @skiplevelexit() nounwind {
16entry:
17  br label %outer
18
19outer:
20  br label %inner
21
22inner:
23  %iv = phi i32 [ 0, %outer ], [ %inc, %tail ]
24  %inc = add i32 %iv, 1
25  call zeroext i1 @check()
26  br i1 true, label %outer.backedge, label %tail
27
28tail:
29  br i1 false, label %inner, label %exit
30
31outer.backedge:
32  br label %outer
33
34exit:
35  ret void
36}
37
38; Remove the middle loop of a triply nested loop tree.
39; Ensure that only the middle loop is removed and rely on verify-loopinfo to
40; check soundness.
41;
42; CHECK-LABEL: @unloopNested(
43; Outer loop control.
44; CHECK: while.body:
45; CHECK: br i1 %cmp3, label %if.then, label %if.end
46; Inner loop control.
47; CHECK: while.end14.i:
48; CHECK: br i1 %call15.i, label %if.end.i, label %exit
49; Middle loop control should no longer reach %while.cond.
50; Now it is the outer loop backedge.
51; CHECK: exit:
52; CHECK: br label %while.cond.outer
53define void @unloopNested() {
54entry:
55  br label %while.cond.outer
56
57while.cond.outer:
58  br label %while.cond
59
60while.cond:
61  %cmp = call zeroext i1 @check()
62  br i1 %cmp, label %while.body, label %while.end
63
64while.body:
65  %cmp3 = call zeroext i1 @check()
66  br i1 %cmp3, label %if.then, label %if.end
67
68if.then:
69  br label %return
70
71if.end:
72  %cmp.i48 = call zeroext i1 @check()
73  br i1 %cmp.i48, label %if.then.i, label %if.else20.i
74
75if.then.i:
76  %cmp8.i = call zeroext i1 @check()
77  br i1 %cmp8.i, label %merge, label %if.else.i
78
79if.else.i:
80  br label %merge
81
82if.else20.i:
83  %cmp25.i = call zeroext i1 @check()
84  br i1 %cmp25.i, label %merge, label %if.else28.i
85
86if.else28.i:
87  br label %merge
88
89merge:
90  br label %while.cond2.i
91
92while.cond2.i:
93  %cmp.i = call zeroext i1 @check()
94  br i1 %cmp.i, label %while.cond2.backedge.i, label %while.end.i
95
96while.cond2.backedge.i:
97  br label %while.cond2.i
98
99while.end.i:
100  %cmp1114.i = call zeroext i1 @check()
101  br i1 %cmp1114.i, label %while.body12.lr.ph.i, label %while.end14.i
102
103while.body12.lr.ph.i:
104  br label %while.end14.i
105
106while.end14.i:
107  %call15.i = call zeroext i1 @check()
108  br i1 %call15.i, label %if.end.i, label %exit
109
110if.end.i:
111  br label %while.cond2.backedge.i
112
113exit:
114  br i1 false, label %while.cond, label %if.else
115
116if.else:
117  br label %while.cond.outer
118
119while.end:
120  br label %return
121
122return:
123  ret void
124}
125
126; Remove the middle loop of a deeply nested loop tree.
127; Ensure that only the middle loop is removed and rely on verify-loopinfo to
128; check soundness.
129;
130; This test must be disabled until trip count computation can be optimized...
131; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
132; CHECKFIXME-LABEL: @unloopDeepNested(
133; Inner-inner loop control.
134; CHECKFIXME: while.cond.us.i:
135; CHECKFIXME: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
136; CHECKFIXME: if.then.us.i:
137; CHECKFIXME: br label %while.cond.us.i
138; Inner loop tail.
139; CHECKFIXME: if.else.i:
140; CHECKFIXME: br label %while.cond.outer.i
141; Middle loop control (removed).
142; CHECKFIXME: valid_data.exit:
143; CHECKFIXME-NOT: br
144; CHECKFIXME: %cmp = call zeroext i1 @check()
145; Outer loop control.
146; CHECKFIXME: copy_data.exit:
147; CHECKFIXME: br i1 %cmp38, label %if.then39, label %while.cond.outer
148; Outer-outer loop tail.
149; CHECKFIXME: while.cond.outer.outer.backedge:
150; CHECKFIXME: br label %while.cond.outer.outer
151define void @unloopDeepNested() nounwind {
152for.cond8.preheader.i:
153  %cmp113.i = call zeroext i1 @check()
154  br i1 %cmp113.i, label %make_data.exit, label %for.body13.lr.ph.i
155
156for.body13.lr.ph.i:
157  br label %make_data.exit
158
159make_data.exit:
160  br label %while.cond.outer.outer
161
162while.cond.outer.outer:
163  br label %while.cond.outer
164
165while.cond.outer:
166  br label %while.cond
167
168while.cond:
169  br label %while.cond.outer.i
170
171while.cond.outer.i:
172  %tmp192.ph.i = call zeroext i1 @check()
173  br i1 %tmp192.ph.i, label %while.cond.outer.split.us.i, label %while.body.loopexit
174
175while.cond.outer.split.us.i:
176  br label %while.cond.us.i
177
178while.cond.us.i:
179  %cmp.us.i = call zeroext i1 @check()
180  br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
181
182while.body.us.i:
183  %cmp7.us.i = call zeroext i1 @check()
184  br i1 %cmp7.us.i, label %if.then.us.i, label %if.else.i
185
186if.then.us.i:
187  br label %while.cond.us.i
188
189if.else.i:
190  br label %while.cond.outer.i
191
192next_data.exit:
193  %tmp192.ph.i.lcssa28 = call zeroext i1 @check()
194  br i1 %tmp192.ph.i.lcssa28, label %while.end, label %while.body
195
196while.body.loopexit:
197  br label %while.body
198
199while.body:
200  br label %while.cond.i
201
202while.cond.i:
203  %cmp.i = call zeroext i1 @check()
204  br i1 %cmp.i, label %valid_data.exit, label %while.body.i
205
206while.body.i:
207  %cmp7.i = call zeroext i1 @check()
208  br i1 %cmp7.i, label %valid_data.exit, label %if.end.i
209
210if.end.i:
211  br label %while.cond.i
212
213valid_data.exit:
214  br i1 true, label %if.then, label %while.cond
215
216if.then:
217  %cmp = call zeroext i1 @check()
218  br i1 %cmp, label %if.then12, label %if.end
219
220if.then12:
221  br label %if.end
222
223if.end:
224  %tobool3.i = call zeroext i1 @check()
225  br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i
226
227while.body.lr.ph.i:
228  br label %copy_data.exit
229
230copy_data.exit:
231  %cmp38 = call zeroext i1 @check()
232  br i1 %cmp38, label %if.then39, label %while.cond.outer
233
234if.then39:
235  %cmp5.i = call zeroext i1 @check()
236  br i1 %cmp5.i, label %while.cond.outer.outer.backedge, label %for.cond8.preheader.i8.thread
237
238for.cond8.preheader.i8.thread:
239  br label %while.cond.outer.outer.backedge
240
241while.cond.outer.outer.backedge:
242  br label %while.cond.outer.outer
243
244while.end:
245  ret void
246}
247
248; Remove a nested loop with irreducible control flow.
249; Ensure that only the middle loop is removed and rely on verify-loopinfo to
250; check soundness.
251;
252; CHECK-LABEL: @unloopIrreducible(
253; Irreducible loop.
254; CHECK: for.inc117:
255; CHECK: br label %for.cond103t
256; Nested loop (removed).
257; CHECK: for.inc159:
258; CHECK: br label %for.inc163
259define void @unloopIrreducible() nounwind {
260
261entry:
262  br label %for.body
263
264for.body:
265  %cmp2113 = call zeroext i1 @check()
266  br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163
267
268for.body22.lr.ph:
269  br label %for.body22
270
271for.body22:
272  br label %for.body33
273
274for.body33:
275  br label %for.end
276
277for.end:
278  %cmp424 = call zeroext i1 @check()
279  br i1 %cmp424, label %for.body43.lr.ph, label %for.end93
280
281for.body43.lr.ph:
282  br label %for.end93
283
284for.end93:
285  %cmp96 = call zeroext i1 @check()
286  br i1 %cmp96, label %if.then97, label %for.cond103
287
288if.then97:
289  br label %for.cond103t
290
291for.cond103t:
292  br label %for.cond103
293
294for.cond103:
295  %cmp105 = call zeroext i1 @check()
296  br i1 %cmp105, label %for.body106, label %for.end120
297
298for.body106:
299  %cmp108 = call zeroext i1 @check()
300  br i1 %cmp108, label %if.then109, label %for.inc117
301
302if.then109:
303  br label %for.inc117
304
305for.inc117:
306  br label %for.cond103t
307
308for.end120:
309  br label %for.inc159
310
311for.inc159:
312  br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge
313
314for.cond15.for.inc163_crit_edge:
315  br label %for.inc163
316
317for.inc163:
318  %cmp12 = call zeroext i1 @check()
319  br i1 %cmp12, label %for.body, label %for.end166
320
321for.end166:
322  ret void
323
324}
325
326; Remove a loop whose exit branches into a sibling loop.
327; Ensure that only the loop is removed and rely on verify-loopinfo to
328; check soundness.
329;
330; CHECK-LABEL: @unloopCriticalEdge(
331; CHECK: while.cond.outer.i.loopexit.split:
332; CHECK: br label %while.body
333; CHECK: while.body:
334; CHECK: br label %for.end78
335define void @unloopCriticalEdge() nounwind {
336entry:
337  br label %for.cond31
338
339for.cond31:
340  br i1 undef, label %for.body35, label %for.end94
341
342for.body35:
343  br label %while.cond.i.preheader
344
345while.cond.i.preheader:
346  br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split
347
348while.cond.i.preheader.split:
349  br label %while.cond.i
350
351while.cond.i:
352  br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit
353
354while.cond.outer.i.loopexit:
355  br label %while.cond.outer.i.loopexit.split
356
357while.cond.outer.i.loopexit.split:
358  br i1 false, label %while.cond.i.preheader, label %Func2.exit
359
360Func2.exit:
361  br label %while.body
362
363while.body:
364  br i1 false, label %while.body, label %while.end
365
366while.end:
367  br label %for.end78
368
369for.end78:
370  br i1 undef, label %Proc2.exit, label %for.cond.i.preheader
371
372for.cond.i.preheader:
373  br label %for.cond.i
374
375for.cond.i:
376  br label %for.cond.i
377
378Proc2.exit:
379  br label %for.cond31
380
381for.end94:
382  ret void
383}
384
385; Test UnloopUpdater::removeBlocksFromAncestors.
386;
387; Check that the loop backedge is removed from the middle loop 1699,
388; but not the inner loop 1676.
389; CHECK: while.body1694:
390; CHECK:   unreachable
391; CHECK: while.end1699:
392; CHECK:   br label %sw.default1711
393define void @removeSubloopBlocks() nounwind {
394entry:
395  br label %tryagain.outer
396
397tryagain.outer:                                   ; preds = %sw.bb304, %entry
398  br label %tryagain
399
400tryagain:                                         ; preds = %while.end1699, %tryagain.outer
401  br i1 undef, label %sw.bb1669, label %sw.bb304
402
403sw.bb304:                                         ; preds = %tryagain
404  br i1 undef, label %return, label %tryagain.outer
405
406sw.bb1669:                                        ; preds = %tryagain
407  br i1 undef, label %sw.default1711, label %while.cond1676
408
409while.cond1676:                                   ; preds = %while.body1694, %sw.bb1669
410  br i1 undef, label %while.end1699, label %while.body1694
411
412while.body1694:                                   ; preds = %while.cond1676
413  br label %while.cond1676
414
415while.end1699:                                    ; preds = %while.cond1676
416  br i1 false, label %tryagain, label %sw.default1711
417
418sw.default1711:                                   ; preds = %while.end1699, %sw.bb1669, %tryagain
419  br label %defchar
420
421defchar:                                          ; preds = %sw.default1711, %sw.bb376
422  br i1 undef, label %if.end2413, label %if.then2368
423
424if.then2368:                                      ; preds = %defchar
425  unreachable
426
427if.end2413:                                       ; preds = %defchar
428  unreachable
429
430return:                                           ; preds = %sw.bb304
431  ret void
432}
433
434; PR11335: the most deeply nested block should be removed from the outer loop.
435; CHECK-LABEL: @removeSubloopBlocks2(
436; CHECK: for.cond3:
437; CHECK-NOT: br
438; CHECK: ret void
439define void @removeSubloopBlocks2() nounwind {
440entry:
441  %tobool.i = icmp ne i32 undef, 0
442  br label %lbl_616
443
444lbl_616.loopexit:                                 ; preds = %for.cond
445  br label %lbl_616
446
447lbl_616:                                          ; preds = %lbl_616.loopexit, %entry
448  br label %for.cond
449
450for.cond:                                         ; preds = %for.cond3, %lbl_616
451  br i1 false, label %for.cond1.preheader, label %lbl_616.loopexit
452
453for.cond1.preheader:                              ; preds = %for.cond
454  br label %for.cond1
455
456for.cond1.loopexit:                               ; preds = %for.cond.i
457  br label %for.cond1
458
459for.cond1:                                        ; preds = %for.cond1.loopexit, %for.cond1.preheader
460  br i1 false, label %for.body2, label %for.cond3
461
462for.body2:                                        ; preds = %for.cond1
463  br label %for.cond.i
464
465for.cond.i:                                       ; preds = %for.cond.i, %for.body2
466  br i1 %tobool.i, label %for.cond.i, label %for.cond1.loopexit
467
468for.cond3:                                        ; preds = %for.cond1
469  br i1 false, label %for.cond, label %if.end
470
471if.end:                                           ; preds = %for.cond3
472  ret void
473}
474