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