71f3551347bf5b1c5213bbb005146369421f0056
[oota-llvm.git] / test / CodeGen / WebAssembly / cfg-stackify.ll
1 ; RUN: llc < %s -asm-verbose=false -disable-block-placement -verify-machineinstrs | FileCheck %s
2 ; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck -check-prefix=OPT %s
3
4 ; Test the CFG stackifier pass.
5
6 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
7 target triple = "wasm32-unknown-unknown"
8
9 declare void @something()
10
11 ; Test that loops are made contiguous, even in the presence of split backedges.
12
13 ; CHECK-LABEL: test0:
14 ; CHECK: loop
15 ; CHECK-NOT: br
16 ; CHECK: i32.add
17 ; CHECK-NEXT: i32.ge_s
18 ; CHECK-NEXT: br_if
19 ; CHECK-NOT: br
20 ; CHECK: call
21 ; CHECK: br BB0_1{{$}}
22 ; CHECK: return{{$}}
23 ; OPT-LABEL: test0:
24 ; OPT: loop
25 ; OPT-NOT: br
26 ; OPT: i32.add
27 ; OPT-NEXT: i32.ge_s
28 ; OPT-NEXT: br_if
29 ; OPT-NOT: br
30 ; OPT: call
31 ; OPT: br BB0_1{{$}}
32 ; OPT: return{{$}}
33 define void @test0(i32 %n) {
34 entry:
35   br label %header
36
37 header:
38   %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
39   %i.next = add i32 %i, 1
40
41   %c = icmp slt i32 %i.next, %n
42   br i1 %c, label %back, label %exit
43
44 exit:
45   ret void
46
47 back:
48   call void @something()
49   br label %header
50 }
51
52 ; Same as test0, but the branch condition is reversed.
53
54 ; CHECK-LABEL: test1:
55 ; CHECK: loop
56 ; CHECK-NOT: br
57 ; CHECK: i32.add
58 ; CHECK-NEXT: i32.ge_s
59 ; CHECK-NEXT: br_if
60 ; CHECK-NOT: br
61 ; CHECK: call
62 ; CHECK: br BB1_1{{$}}
63 ; CHECK: return{{$}}
64 ; OPT-LABEL: test1:
65 ; OPT: loop
66 ; OPT-NOT: br
67 ; OPT: i32.add
68 ; OPT-NEXT: i32.ge_s
69 ; OPT-NEXT: br_if
70 ; OPT-NOT: br
71 ; OPT: call
72 ; OPT: br BB1_1{{$}}
73 ; OPT: return{{$}}
74 define void @test1(i32 %n) {
75 entry:
76   br label %header
77
78 header:
79   %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
80   %i.next = add i32 %i, 1
81
82   %c = icmp sge i32 %i.next, %n
83   br i1 %c, label %exit, label %back
84
85 exit:
86   ret void
87
88 back:
89   call void @something()
90   br label %header
91 }
92
93 ; Test that a simple loop is handled as expected.
94
95 ; CHECK-LABEL: test2:
96 ; CHECK: block BB2_2{{$}}
97 ; CHECK: br_if {{[^,]*}}, BB2_2{{$}}
98 ; CHECK: BB2_1:
99 ; CHECK: br_if ${{[0-9]+}}, BB2_1{{$}}
100 ; CHECK: BB2_2:
101 ; CHECK: return{{$}}
102 ; OPT-LABEL: test2:
103 ; OPT: block BB2_2{{$}}
104 ; OPT: br_if {{[^,]*}}, BB2_2{{$}}
105 ; OPT: BB2_1:
106 ; OPT: br_if ${{[0-9]+}}, BB2_1{{$}}
107 ; OPT: BB2_2:
108 ; OPT: return{{$}}
109 define void @test2(double* nocapture %p, i32 %n) {
110 entry:
111   %cmp.4 = icmp sgt i32 %n, 0
112   br i1 %cmp.4, label %for.body.preheader, label %for.end
113
114 for.body.preheader:
115   br label %for.body
116
117 for.body:
118   %i.05 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
119   %arrayidx = getelementptr inbounds double, double* %p, i32 %i.05
120   %0 = load double, double* %arrayidx, align 8
121   %mul = fmul double %0, 3.200000e+00
122   store double %mul, double* %arrayidx, align 8
123   %inc = add nuw nsw i32 %i.05, 1
124   %exitcond = icmp eq i32 %inc, %n
125   br i1 %exitcond, label %for.end.loopexit, label %for.body
126
127 for.end.loopexit:
128   br label %for.end
129
130 for.end:
131   ret void
132 }
133
134 ; CHECK-LABEL: doublediamond:
135 ; CHECK: block BB3_5{{$}}
136 ; CHECK: block BB3_2{{$}}
137 ; CHECK: br_if $0, BB3_2{{$}}
138 ; CHECK: block BB3_4{{$}}
139 ; CHECK: br_if $1, BB3_4{{$}}
140 ; CHECK: br BB3_5{{$}}
141 ; CHECK: BB3_4:
142 ; CHECK: BB3_5:
143 ; CHECK: return ${{[0-9]+}}{{$}}
144 ; OPT-LABEL: doublediamond:
145 ; OPT: block BB3_5{{$}}
146 ; OPT: block BB3_4{{$}}
147 ; OPT: br_if {{[^,]*}}, BB3_4{{$}}
148 ; OPT: block BB3_3{{$}}
149 ; OPT: br_if {{[^,]*}}, BB3_3{{$}}
150 ; OPT: br BB3_5{{$}}
151 ; OPT: BB3_4:
152 ; OPT: BB3_5:
153 ; OPT: return ${{[0-9]+}}{{$}}
154 define i32 @doublediamond(i32 %a, i32 %b, i32* %p) {
155 entry:
156   %c = icmp eq i32 %a, 0
157   %d = icmp eq i32 %b, 0
158   store volatile i32 0, i32* %p
159   br i1 %c, label %true, label %false
160 true:
161   store volatile i32 1, i32* %p
162   br label %exit
163 false:
164   store volatile i32 2, i32* %p
165   br i1 %d, label %ft, label %ff
166 ft:
167   store volatile i32 3, i32* %p
168   br label %exit
169 ff:
170   store volatile i32 4, i32* %p
171   br label %exit
172 exit:
173   store volatile i32 5, i32* %p
174   ret i32 0
175 }
176
177 ; CHECK-LABEL: triangle:
178 ; CHECK: block BB4_2{{$}}
179 ; CHECK: br_if $1, BB4_2{{$}}
180 ; CHECK: BB4_2:
181 ; CHECK: return ${{[0-9]+}}{{$}}
182 ; OPT-LABEL: triangle:
183 ; OPT: block BB4_2{{$}}
184 ; OPT: br_if $1, BB4_2{{$}}
185 ; OPT: BB4_2:
186 ; OPT: return ${{[0-9]+}}{{$}}
187 define i32 @triangle(i32* %p, i32 %a) {
188 entry:
189   %c = icmp eq i32 %a, 0
190   store volatile i32 0, i32* %p
191   br i1 %c, label %true, label %exit
192 true:
193   store volatile i32 1, i32* %p
194   br label %exit
195 exit:
196   store volatile i32 2, i32* %p
197   ret i32 0
198 }
199
200 ; CHECK-LABEL: diamond:
201 ; CHECK: block BB5_3{{$}}
202 ; CHECK: block BB5_2{{$}}
203 ; CHECK: br_if $1, BB5_2{{$}}
204 ; CHECK: br BB5_3{{$}}
205 ; CHECK: BB5_2:
206 ; CHECK: BB5_3:
207 ; CHECK: return ${{[0-9]+}}{{$}}
208 ; OPT-LABEL: diamond:
209 ; OPT: block BB5_3{{$}}
210 ; OPT: block BB5_2{{$}}
211 ; OPT: br_if {{[^,]*}}, BB5_2{{$}}
212 ; OPT: br BB5_3{{$}}
213 ; OPT: BB5_2:
214 ; OPT: BB5_3:
215 ; OPT: return ${{[0-9]+}}{{$}}
216 define i32 @diamond(i32* %p, i32 %a) {
217 entry:
218   %c = icmp eq i32 %a, 0
219   store volatile i32 0, i32* %p
220   br i1 %c, label %true, label %false
221 true:
222   store volatile i32 1, i32* %p
223   br label %exit
224 false:
225   store volatile i32 2, i32* %p
226   br label %exit
227 exit:
228   store volatile i32 3, i32* %p
229   ret i32 0
230 }
231
232 ; CHECK-LABEL: single_block:
233 ; CHECK-NOT: br
234 ; CHECK: return $pop{{[0-9]+}}{{$}}
235 ; OPT-LABEL: single_block:
236 ; OPT-NOT: br
237 ; OPT: return $pop{{[0-9]+}}{{$}}
238 define i32 @single_block(i32* %p) {
239 entry:
240   store volatile i32 0, i32* %p
241   ret i32 0
242 }
243
244 ; CHECK-LABEL: minimal_loop:
245 ; CHECK-NOT: br
246 ; CHECK: BB7_1:
247 ; CHECK: i32.store $discard=, 0($0), $pop{{[0-9]+}}{{$}}
248 ; CHECK: br BB7_1{{$}}
249 ; CHECK: BB7_2:
250 ; OPT-LABEL: minimal_loop:
251 ; OPT-NOT: br
252 ; OPT: BB7_1:
253 ; OPT: i32.store $discard=, 0($0), $pop{{[0-9]+}}{{$}}
254 ; OPT: br BB7_1{{$}}
255 ; OPT: BB7_2:
256 define i32 @minimal_loop(i32* %p) {
257 entry:
258   store volatile i32 0, i32* %p
259   br label %loop
260 loop:
261   store volatile i32 1, i32* %p
262   br label %loop
263 }
264
265 ; CHECK-LABEL: simple_loop:
266 ; CHECK-NOT: br
267 ; CHECK: BB8_1:
268 ; CHECK: loop BB8_2{{$}}
269 ; CHECK: br_if $pop{{[0-9]+}}, BB8_1{{$}}
270 ; CHECK: BB8_2:
271 ; CHECK: return ${{[0-9]+}}{{$}}
272 ; OPT-LABEL: simple_loop:
273 ; OPT-NOT: br
274 ; OPT: BB8_1:
275 ; OPT: loop BB8_2{{$}}
276 ; OPT: br_if {{[^,]*}}, BB8_1{{$}}
277 ; OPT: BB8_2:
278 ; OPT: return ${{[0-9]+}}{{$}}
279 define i32 @simple_loop(i32* %p, i32 %a) {
280 entry:
281   %c = icmp eq i32 %a, 0
282   store volatile i32 0, i32* %p
283   br label %loop
284 loop:
285   store volatile i32 1, i32* %p
286   br i1 %c, label %loop, label %exit
287 exit:
288   store volatile i32 2, i32* %p
289   ret i32 0
290 }
291
292 ; CHECK-LABEL: doubletriangle:
293 ; CHECK: block BB9_4{{$}}
294 ; CHECK: br_if $0, BB9_4{{$}}
295 ; CHECK: block BB9_3{{$}}
296 ; CHECK: br_if $1, BB9_3{{$}}
297 ; CHECK: BB9_3:
298 ; CHECK: BB9_4:
299 ; CHECK: return ${{[0-9]+}}{{$}}
300 ; OPT-LABEL: doubletriangle:
301 ; OPT: block BB9_4{{$}}
302 ; OPT: br_if $0, BB9_4{{$}}
303 ; OPT: block BB9_3{{$}}
304 ; OPT: br_if $1, BB9_3{{$}}
305 ; OPT: BB9_3:
306 ; OPT: BB9_4:
307 ; OPT: return ${{[0-9]+}}{{$}}
308 define i32 @doubletriangle(i32 %a, i32 %b, i32* %p) {
309 entry:
310   %c = icmp eq i32 %a, 0
311   %d = icmp eq i32 %b, 0
312   store volatile i32 0, i32* %p
313   br i1 %c, label %true, label %exit
314 true:
315   store volatile i32 2, i32* %p
316   br i1 %d, label %tt, label %tf
317 tt:
318   store volatile i32 3, i32* %p
319   br label %tf
320 tf:
321   store volatile i32 4, i32* %p
322   br label %exit
323 exit:
324   store volatile i32 5, i32* %p
325   ret i32 0
326 }
327
328 ; CHECK-LABEL: ifelse_earlyexits:
329 ; CHECK: block BB10_4{{$}}
330 ; CHECK: block BB10_2{{$}}
331 ; CHECK: br_if $0, BB10_2{{$}}
332 ; CHECK: br BB10_4{{$}}
333 ; CHECK: BB10_2:
334 ; CHECK: br_if $1, BB10_4{{$}}
335 ; CHECK: BB10_4:
336 ; CHECK: return ${{[0-9]+}}{{$}}
337 ; OPT-LABEL: ifelse_earlyexits:
338 ; OPT: block BB10_4{{$}}
339 ; OPT: block BB10_3{{$}}
340 ; OPT: br_if {{[^,]*}}, BB10_3{{$}}
341 ; OPT: br_if $1, BB10_4{{$}}
342 ; OPT: br BB10_4{{$}}
343 ; OPT: BB10_3:
344 ; OPT: BB10_4:
345 ; OPT: return ${{[0-9]+}}{{$}}
346 define i32 @ifelse_earlyexits(i32 %a, i32 %b, i32* %p) {
347 entry:
348   %c = icmp eq i32 %a, 0
349   %d = icmp eq i32 %b, 0
350   store volatile i32 0, i32* %p
351   br i1 %c, label %true, label %false
352 true:
353   store volatile i32 1, i32* %p
354   br label %exit
355 false:
356   store volatile i32 2, i32* %p
357   br i1 %d, label %ft, label %exit
358 ft:
359   store volatile i32 3, i32* %p
360   br label %exit
361 exit:
362   store volatile i32 4, i32* %p
363   ret i32 0
364 }
365
366 ; CHECK-LABEL: doublediamond_in_a_loop:
367 ; CHECK: BB11_1:
368 ; CHECK: loop            BB11_7{{$}}
369 ; CHECK: block           BB11_6{{$}}
370 ; CHECK: block           BB11_3{{$}}
371 ; CHECK: br_if           $0, BB11_3{{$}}
372 ; CHECK: br              BB11_6{{$}}
373 ; CHECK: BB11_3:
374 ; CHECK: block           BB11_5{{$}}
375 ; CHECK: br_if           $1, BB11_5{{$}}
376 ; CHECK: br              BB11_6{{$}}
377 ; CHECK: BB11_5:
378 ; CHECK: BB11_6:
379 ; CHECK: br              BB11_1{{$}}
380 ; CHECK: BB11_7:
381 ; OPT-LABEL: doublediamond_in_a_loop:
382 ; OPT: BB11_1:
383 ; OPT: loop            BB11_7{{$}}
384 ; OPT: block           BB11_6{{$}}
385 ; OPT: block           BB11_5{{$}}
386 ; OPT: br_if           {{[^,]*}}, BB11_5{{$}}
387 ; OPT: block           BB11_4{{$}}
388 ; OPT: br_if           {{[^,]*}}, BB11_4{{$}}
389 ; OPT: br              BB11_6{{$}}
390 ; OPT: BB11_4:
391 ; OPT: br              BB11_6{{$}}
392 ; OPT: BB11_5:
393 ; OPT: BB11_6:
394 ; OPT: br              BB11_1{{$}}
395 ; OPT: BB11_7:
396 define i32 @doublediamond_in_a_loop(i32 %a, i32 %b, i32* %p) {
397 entry:
398   br label %header
399 header:
400   %c = icmp eq i32 %a, 0
401   %d = icmp eq i32 %b, 0
402   store volatile i32 0, i32* %p
403   br i1 %c, label %true, label %false
404 true:
405   store volatile i32 1, i32* %p
406   br label %exit
407 false:
408   store volatile i32 2, i32* %p
409   br i1 %d, label %ft, label %ff
410 ft:
411   store volatile i32 3, i32* %p
412   br label %exit
413 ff:
414   store volatile i32 4, i32* %p
415   br label %exit
416 exit:
417   store volatile i32 5, i32* %p
418   br label %header
419 }
420
421 ; Test that nested loops are handled.
422
423 ; CHECK-LABEL: test3:
424 ; CHECK: loop
425 ; CHECK-NEXT: br_if
426 ; CHECK-NEXT: BB{{[0-9]+}}_{{[0-9]+}}:
427 ; CHECK-NEXT: loop
428 ; OPT-LABEL: test3:
429 ; OPT: loop
430 ; OPT-NEXT: br_if
431 ; OPT-NEXT: BB{{[0-9]+}}_{{[0-9]+}}:
432 ; OPT-NEXT: loop
433 declare void @bar()
434 define void @test3(i32 %w)  {
435 entry:
436   br i1 undef, label %outer.ph, label %exit
437
438 outer.ph:
439   br label %outer
440
441 outer:
442   %tobool = icmp eq i32 undef, 0
443   br i1 %tobool, label %inner, label %unreachable
444
445 unreachable:
446   unreachable
447
448 inner:
449   %c = icmp eq i32 undef, %w
450   br i1 %c, label %if.end, label %inner
451
452 exit:
453   ret void
454
455 if.end:
456   call void @bar()
457   br label %outer
458 }
459
460 ; Test switch lowering and block placement.
461
462 ; CHECK-LABEL: test4:
463 ; CHECK-NEXT: .param      i32{{$}}
464 ; CHECK:      block       BB13_8{{$}}
465 ; CHECK-NEXT: block       BB13_7{{$}}
466 ; CHECK-NEXT: block       BB13_4{{$}}
467 ; CHECK:      br_if       $pop{{[0-9]*}}, BB13_4{{$}}
468 ; CHECK-NEXT: block       BB13_3{{$}}
469 ; CHECK:      br_if       $pop{{[0-9]*}}, BB13_3{{$}}
470 ; CHECK:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
471 ; CHECK-NEXT: BB13_3:
472 ; CHECK-NEXT: return{{$}}
473 ; CHECK-NEXT: BB13_4:
474 ; CHECK:      br_if       $pop{{[0-9]*}}, BB13_8{{$}}
475 ; CHECK:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
476 ; CHECK-NEXT: return{{$}}
477 ; CHECK-NEXT: BB13_7:
478 ; CHECK-NEXT: return{{$}}
479 ; CHECK-NEXT: BB13_8:
480 ; CHECK-NEXT: return{{$}}
481 ; OPT-LABEL: test4:
482 ; OPT-NEXT: .param      i32{{$}}
483 ; OPT:      block       BB13_8{{$}}
484 ; OPT-NEXT: block       BB13_7{{$}}
485 ; OPT-NEXT: block       BB13_4{{$}}
486 ; OPT:      br_if       $pop{{[0-9]*}}, BB13_4{{$}}
487 ; OPT-NEXT: block       BB13_3{{$}}
488 ; OPT:      br_if       $pop{{[0-9]*}}, BB13_3{{$}}
489 ; OPT:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
490 ; OPT-NEXT: BB13_3:
491 ; OPT-NEXT: return{{$}}
492 ; OPT-NEXT: BB13_4:
493 ; OPT:      br_if       $pop{{[0-9]*}}, BB13_8{{$}}
494 ; OPT:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
495 ; OPT-NEXT: return{{$}}
496 ; OPT-NEXT: BB13_7:
497 ; OPT-NEXT: return{{$}}
498 ; OPT-NEXT: BB13_8:
499 ; OPT-NEXT: return{{$}}
500 define void @test4(i32 %t) {
501 entry:
502   switch i32 %t, label %default [
503     i32 0, label %bb2
504     i32 2, label %bb2
505     i32 4, label %bb1
506     i32 622, label %bb0
507   ]
508
509 bb0:
510   ret void
511
512 bb1:
513   ret void
514
515 bb2:
516   ret void
517
518 default:
519   ret void
520 }
521
522 ; Test a case where the BLOCK needs to be placed before the LOOP in the
523 ; same basic block.
524
525 ; CHECK-LABEL: test5:
526 ; CHECK:       BB14_1:
527 ; CHECK-NEXT:  block BB14_4{{$}}
528 ; CHECK-NEXT:  loop BB14_3{{$}}
529 ; CHECK:       br_if {{[^,]*}}, BB14_4{{$}}
530 ; CHECK:       br_if {{[^,]*}}, BB14_1{{$}}
531 ; CHECK-NEXT:  BB14_3:
532 ; CHECK:       return{{$}}
533 ; CHECK-NEXT:  BB14_4:
534 ; CHECK:       return{{$}}
535 ; OPT-LABEL: test5:
536 ; OPT:       BB14_1:
537 ; OPT-NEXT:  block BB14_4{{$}}
538 ; OPT-NEXT:  loop BB14_3{{$}}
539 ; OPT:       br_if {{[^,]*}}, BB14_4{{$}}
540 ; OPT:       br_if {{[^,]*}}, BB14_1{{$}}
541 ; OPT-NEXT:  BB14_3:
542 ; OPT:       return{{$}}
543 ; OPT-NEXT:  BB14_4:
544 ; OPT:       return{{$}}
545 define void @test5(i1 %p, i1 %q) {
546 entry:
547   br label %header
548
549 header:
550   store volatile i32 0, i32* null
551   br i1 %p, label %more, label %alt
552
553 more:
554   store volatile i32 1, i32* null
555   br i1 %q, label %header, label %return
556
557 alt:
558   store volatile i32 2, i32* null
559   ret void
560
561 return:
562   store volatile i32 3, i32* null
563   ret void
564 }
565
566 ; Test an interesting case of a loop with multiple exits, which
567 ; aren't to layout successors of the loop, and one of which is to a successors
568 ; which has another predecessor.
569
570 ; CHECK-LABEL: test6:
571 ; CHECK:       BB15_1:
572 ; CHECK-NEXT:  block BB15_6{{$}}
573 ; CHECK-NEXT:  block BB15_5{{$}}
574 ; CHECK-NEXT:  loop  BB15_4{{$}}
575 ; CHECK-NOT:   block
576 ; CHECK:       br_if {{[^,]*}}, BB15_6{{$}}
577 ; CHECK-NOT:   block
578 ; CHECK:       br_if {{[^,]*}}, BB15_5{{$}}
579 ; CHECK-NOT:   block
580 ; CHECK:       br_if {{[^,]*}}, BB15_1{{$}}
581 ; CHECK-NEXT:  BB15_4:
582 ; CHECK-NOT:   block
583 ; CHECK:       return{{$}}
584 ; CHECK-NEXT:  BB15_5:
585 ; CHECK-NOT:   block
586 ; CHECK:       BB15_6:
587 ; CHECK-NOT:   block
588 ; CHECK:       return{{$}}
589 ; OPT-LABEL: test6:
590 ; OPT:       BB15_1:
591 ; OPT-NEXT:  block BB15_6{{$}}
592 ; OPT-NEXT:  block BB15_5{{$}}
593 ; OPT-NEXT:  loop  BB15_4{{$}}
594 ; OPT-NOT:   block
595 ; OPT:       br_if {{[^,]*}}, BB15_6{{$}}
596 ; OPT-NOT:   block
597 ; OPT:       br_if {{[^,]*}}, BB15_5{{$}}
598 ; OPT-NOT:   block
599 ; OPT:       br_if {{[^,]*}}, BB15_1{{$}}
600 ; OPT-NEXT:  BB15_4:
601 ; OPT-NOT:   block
602 ; OPT:       return{{$}}
603 ; OPT-NEXT:  BB15_5:
604 ; OPT-NOT:   block
605 ; OPT:       BB15_6:
606 ; OPT-NOT:   block
607 ; OPT:       return{{$}}
608 define void @test6(i1 %p, i1 %q) {
609 entry:
610   br label %header
611
612 header:
613   store volatile i32 0, i32* null
614   br i1 %p, label %more, label %second
615
616 more:
617   store volatile i32 1, i32* null
618   br i1 %q, label %evenmore, label %first
619
620 evenmore:
621   store volatile i32 1, i32* null
622   br i1 %q, label %header, label %return
623
624 return:
625   store volatile i32 2, i32* null
626   ret void
627
628 first:
629   store volatile i32 3, i32* null
630   br label %second
631
632 second:
633   store volatile i32 4, i32* null
634   ret void
635 }
636
637 ; Test a case where there are multiple backedges and multiple loop exits
638 ; that end in unreachable.
639
640 ; CHECK-LABEL: test7:
641 ; CHECK:       BB16_1:
642 ; CHECK-NEXT:  loop BB16_5{{$}}
643 ; CHECK-NOT:   block
644 ; CHECK:       block BB16_4{{$}}
645 ; CHECK:       br_if {{[^,]*}}, BB16_4{{$}}
646 ; CHECK-NOT:   block
647 ; CHECK:       br_if {{[^,]*}}, BB16_1{{$}}
648 ; CHECK-NOT:   block
649 ; CHECK:       unreachable
650 ; CHECK_NEXT:  BB16_4:
651 ; CHECK-NOT:   block
652 ; CHECK:       br_if {{[^,]*}}, BB16_1{{$}}
653 ; CHECK-NEXT:  BB16_5:
654 ; CHECK-NOT:   block
655 ; CHECK:       unreachable
656 ; OPT-LABEL: test7:
657 ; OPT:       BB16_1:
658 ; OPT-NEXT:  loop BB16_5{{$}}
659 ; OPT-NOT:   block
660 ; OPT:       block BB16_4{{$}}
661 ; OPT-NOT:   block
662 ; OPT:       br_if {{[^,]*}}, BB16_4{{$}}
663 ; OPT-NOT:   block
664 ; OPT:       br_if {{[^,]*}}, BB16_1{{$}}
665 ; OPT-NOT:   block
666 ; OPT:       unreachable
667 ; OPT_NEXT:  BB16_4:
668 ; OPT-NOT:   block
669 ; OPT:       br_if {{[^,]*}}, BB16_1{{$}}
670 ; OPT-NEXT:  BB16_5:
671 ; OPT-NOT:   block
672 ; OPT:       unreachable
673 define void @test7(i1 %tobool2, i1 %tobool9) {
674 entry:
675   store volatile i32 0, i32* null
676   br label %loop
677
678 loop:
679   store volatile i32 1, i32* null
680   br i1 %tobool2, label %l1, label %l0
681
682 l0:
683   store volatile i32 2, i32* null
684   br i1 %tobool9, label %loop, label %u0
685
686 l1:
687   store volatile i32 3, i32* null
688   br i1 %tobool9, label %loop, label %u1
689
690 u0:
691   store volatile i32 4, i32* null
692   unreachable
693
694 u1:
695   store volatile i32 5, i32* null
696   unreachable
697 }
698
699 ; Test an interesting case using nested loops and switches.
700
701 ; CHECK-LABEL: test8:
702 ; CHECK:       BB17_1:
703 ; CHECK-NEXT:  loop     BB17_4{{$}}
704 ; CHECK-NEXT:  block    BB17_3{{$}}
705 ; CHECK-NOT:   block
706 ; CHECK:       br_if    {{[^,]*}}, BB17_3{{$}}
707 ; CHECK-NOT:   block
708 ; CHECK:       br_if    {{[^,]*}}, BB17_1{{$}}
709 ; CHECK-NEXT:  BB17_3:
710 ; CHECK-NEXT:  loop     BB17_4{{$}}
711 ; CHECK-NEXT:  br_if    {{[^,]*}}, BB17_3{{$}}
712 ; CHECK-NEXT:  br       BB17_1{{$}}
713 ; CHECK-NEXT:  BB17_4:
714 ; OPT-LABEL: test8:
715 ; OPT:       BB17_1:
716 ; OPT-NEXT:  loop     BB17_4{{$}}
717 ; OPT-NEXT:  block    BB17_3{{$}}
718 ; OPT-NOT:   block
719 ; OPT:       br_if    {{[^,]*}}, BB17_3{{$}}
720 ; OPT-NOT:   block
721 ; OPT:       br_if    {{[^,]*}}, BB17_1{{$}}
722 ; OPT-NEXT:  BB17_3:
723 ; OPT-NEXT:  loop     BB17_4{{$}}
724 ; OPT-NEXT:  br_if    {{[^,]*}}, BB17_3{{$}}
725 ; OPT-NEXT:  br       BB17_1{{$}}
726 ; OPT-NEXT:  BB17_4:
727 define i32 @test8() {
728 bb:
729   br label %bb1
730
731 bb1:
732   br i1 undef, label %bb2, label %bb3
733
734 bb2:
735   switch i8 undef, label %bb1 [
736     i8 44, label %bb2
737   ]
738
739 bb3:
740   switch i8 undef, label %bb1 [
741     i8 44, label %bb2
742   ]
743 }
744
745 ; Test an interesting case using nested loops that share a bottom block.
746
747 ; CHECK-LABEL: test9:
748 ; CHECK:       BB18_1:
749 ; CHECK-NEXT:  loop      BB18_5{{$}}
750 ; CHECK-NOT:   block
751 ; CHECK:       br_if     {{[^,]*}}, BB18_5{{$}}
752 ; CHECK-NEXT:  BB18_2:
753 ; CHECK-NEXT:  loop      BB18_5{{$}}
754 ; CHECK-NOT:   block
755 ; CHECK:       block     BB18_4{{$}}
756 ; CHECK-NOT:   block
757 ; CHECK:       br_if     {{[^,]*}}, BB18_4{{$}}
758 ; CHECK-NOT:   block
759 ; CHECK:       br_if     {{[^,]*}}, BB18_2{{$}}
760 ; CHECK-NEXT:  br        BB18_1{{$}}
761 ; CHECK-NEXT:  BB18_4:
762 ; CHECK-NOT:   block
763 ; CHECK:       br_if     {{[^,]*}}, BB18_2{{$}}
764 ; CHECK-NEXT:  br        BB18_1{{$}}
765 ; CHECK-NEXT:  BB18_5:
766 ; CHECK-NOT:   block
767 ; CHECK:       return{{$}}
768 ; OPT-LABEL: test9:
769 ; OPT:       BB18_1:
770 ; OPT-NEXT:  loop      BB18_5{{$}}
771 ; OPT-NOT:   block
772 ; OPT:       br_if     {{[^,]*}}, BB18_5{{$}}
773 ; OPT-NEXT:  BB18_2:
774 ; OPT-NEXT:  loop      BB18_5{{$}}
775 ; OPT-NOT:   block
776 ; OPT:       block     BB18_4{{$}}
777 ; OPT-NOT:   block
778 ; OPT:       br_if     {{[^,]*}}, BB18_4{{$}}
779 ; OPT-NOT:   block
780 ; OPT:       br_if     {{[^,]*}}, BB18_2{{$}}
781 ; OPT-NEXT:  br        BB18_1{{$}}
782 ; OPT-NEXT:  BB18_4:
783 ; OPT-NOT:   block
784 ; OPT:       br_if     {{[^,]*}}, BB18_2{{$}}
785 ; OPT-NEXT:  br        BB18_1{{$}}
786 ; OPT-NEXT:  BB18_5:
787 ; OPT-NOT:   block
788 ; OPT:       return{{$}}
789 declare i1 @a()
790 define void @test9() {
791 entry:
792   store volatile i32 0, i32* null
793   br label %header
794
795 header:
796   store volatile i32 1, i32* null
797   %call4 = call i1 @a()
798   br i1 %call4, label %header2, label %end
799
800 header2:
801   store volatile i32 2, i32* null
802   %call = call i1 @a()
803   br i1 %call, label %if.then, label %if.else
804
805 if.then:
806   store volatile i32 3, i32* null
807   %call3 = call i1 @a()
808   br i1 %call3, label %header2, label %header
809
810 if.else:
811   store volatile i32 4, i32* null
812   %call2 = call i1 @a()
813   br i1 %call2, label %header2, label %header
814
815 end:
816   store volatile i32 5, i32* null
817   ret void
818 }
819
820 ; Test an interesting case involving nested loops sharing a loop bottom,
821 ; and loop exits to a block with unreachable.
822
823 ; CHECK-LABEL: test10:
824 ; CHECK:       BB19_1:
825 ; CHECK-NEXT:  loop     BB19_7{{$}}
826 ; CHECK-NOT:   block
827 ; CHECK:       br_if    {{[^,]*}}, BB19_1{{$}}
828 ; CHECK-NEXT:  BB19_2:
829 ; CHECK-NEXT:  block    BB19_6{{$}}
830 ; CHECK-NEXT:  loop     BB19_5{{$}}
831 ; CHECK-NOT:   block
832 ; CHECK:       BB19_3:
833 ; CHECK-NEXT:  loop     BB19_5{{$}}
834 ; CHECK-NOT:   block
835 ; CHECK:       br_if    {{[^,]*}}, BB19_1{{$}}
836 ; CHECK-NOT:   block
837 ; CHECK:       tableswitch  {{[^,]*}}, BB19_3, BB19_3, BB19_5, BB19_1, BB19_2, BB19_6{{$}}
838 ; CHECK-NEXT:  BB19_5:
839 ; CHECK-NEXT:  return{{$}}
840 ; CHECK-NEXT:  BB19_6:
841 ; CHECK-NOT:   block
842 ; CHECK:       br       BB19_1{{$}}
843 ; CHECK-NEXT:  BB19_7:
844 ; OPT-LABEL: test10:
845 ; OPT:       BB19_1:
846 ; OPT-NEXT:  loop     BB19_7{{$}}
847 ; OPT-NOT:   block
848 ; OPT:       br_if    {{[^,]*}}, BB19_1{{$}}
849 ; OPT-NEXT:  BB19_2:
850 ; OPT-NEXT:  block    BB19_6{{$}}
851 ; OPT-NEXT:  loop     BB19_5{{$}}
852 ; OPT-NOT:   block
853 ; OPT:       BB19_3:
854 ; OPT-NEXT:  loop     BB19_5{{$}}
855 ; OPT-NOT:   block
856 ; OPT:       br_if    {{[^,]*}}, BB19_1{{$}}
857 ; OPT-NOT:   block
858 ; OPT:       tableswitch  {{[^,]*}}, BB19_3, BB19_3, BB19_5, BB19_1, BB19_2, BB19_6{{$}}
859 ; OPT-NEXT:  BB19_5:
860 ; OPT-NEXT:  return{{$}}
861 ; OPT-NEXT:  BB19_6:
862 ; OPT-NOT:   block
863 ; OPT:       br       BB19_1{{$}}
864 ; OPT-NEXT:  BB19_7:
865 define void @test10() {
866 bb0:
867   br label %bb1
868
869 bb1:
870   %tmp = phi i32 [ 2, %bb0 ], [ 3, %bb3 ]
871   %tmp3 = phi i32 [ undef, %bb0 ], [ %tmp11, %bb3 ]
872   %tmp4 = icmp eq i32 %tmp3, 0
873   br i1 %tmp4, label %bb4, label %bb2
874
875 bb2:
876   br label %bb3
877
878 bb3:
879   %tmp11 = phi i32 [ 1, %bb5 ], [ 0, %bb2 ]
880   br label %bb1
881
882 bb4:
883   %tmp6 = phi i32 [ %tmp9, %bb5 ], [ 4, %bb1 ]
884   %tmp7 = phi i32 [ %tmp6, %bb5 ], [ %tmp, %bb1 ]
885   br label %bb5
886
887 bb5:
888   %tmp9 = phi i32 [ %tmp6, %bb5 ], [ %tmp7, %bb4 ]
889   switch i32 %tmp9, label %bb2 [
890     i32 0, label %bb5
891     i32 1, label %bb6
892     i32 3, label %bb4
893     i32 4, label %bb3
894   ]
895
896 bb6:
897   ret void
898 }
899
900 ; Test a CFG DAG with interesting merging.
901
902 ; CHECK-LABEL: test11:
903 ; CHECK:       block        BB20_8{{$}}
904 ; CHECK-NEXT:  block        BB20_7{{$}}
905 ; CHECK-NEXT:  block        BB20_6{{$}}
906 ; CHECK-NEXT:  block        BB20_4{{$}}
907 ; CHECK-NEXT:  br_if        {{[^,]*}}, BB20_4{{$}}
908 ; CHECK-NOT:   block
909 ; CHECK:       block        BB20_3{{$}}
910 ; CHECK:       br_if        {{[^,]*}}, BB20_3{{$}}
911 ; CHECK-NOT:   block
912 ; CHECK:       br_if        {{[^,]*}}, BB20_6{{$}}
913 ; CHECK-NEXT:  BB20_3:
914 ; CHECK-NOT:   block
915 ; CHECK:       return{{$}}
916 ; CHECK-NEXT:  BB20_4:
917 ; CHECK-NOT:   block
918 ; CHECK:       br_if        {{[^,]*}}, BB20_8{{$}}
919 ; CHECK-NOT:   block
920 ; CHECK:       br_if        {{[^,]*}}, BB20_7{{$}}
921 ; CHECK-NEXT:  BB20_6:
922 ; CHECK-NOT:   block
923 ; CHECK:       return{{$}}
924 ; CHECK-NEXT:  BB20_7:
925 ; CHECK-NOT:   block
926 ; CHECK:       return{{$}}
927 ; CHECK-NEXT:  BB20_8:
928 ; CHECK-NOT:   block
929 ; CHECK:       return{{$}}
930 ; OPT-LABEL: test11:
931 ; OPT:       block        BB20_8{{$}}
932 ; OPT-NEXT:  block        BB20_4{{$}}
933 ; OPT-NEXT:  br_if        $0, BB20_4{{$}}
934 ; OPT-NOT:   block
935 ; OPT:       block        BB20_3{{$}}
936 ; OPT:       br_if        $0, BB20_3{{$}}
937 ; OPT-NOT:   block
938 ; OPT:       br_if        $0, BB20_8{{$}}
939 ; OPT-NEXT:  BB20_3:
940 ; OPT-NOT:   block
941 ; OPT:       return{{$}}
942 ; OPT-NEXT:  BB20_4:
943 ; OPT-NOT:   block
944 ; OPT:       block        BB20_6{{$}}
945 ; OPT-NOT:   block
946 ; OPT:       br_if        $pop9, BB20_6{{$}}
947 ; OPT-NOT:   block
948 ; OPT:       return{{$}}
949 ; OPT-NEXT:  BB20_6:
950 ; OPT-NOT:   block
951 ; OPT:       br_if        $0, BB20_8{{$}}
952 ; OPT-NOT:   block
953 ; OPT:       return{{$}}
954 ; OPT-NEXT:  BB20_8:
955 ; OPT-NOT:   block
956 ; OPT:       return{{$}}
957 define void @test11() {
958 bb0:
959   store volatile i32 0, i32* null
960   br i1 undef, label %bb1, label %bb4
961 bb1:
962   store volatile i32 1, i32* null
963   br i1 undef, label %bb3, label %bb2
964 bb2:
965   store volatile i32 2, i32* null
966   br i1 undef, label %bb3, label %bb7
967 bb3:
968   store volatile i32 3, i32* null
969   ret void
970 bb4:
971   store volatile i32 4, i32* null
972   br i1 undef, label %bb8, label %bb5
973 bb5:
974   store volatile i32 5, i32* null
975   br i1 undef, label %bb6, label %bb7
976 bb6:
977   store volatile i32 6, i32* null
978   ret void
979 bb7:
980   store volatile i32 7, i32* null
981   ret void
982 bb8:
983   store volatile i32 8, i32* null
984   ret void
985 }
986
987 ; CHECK-LABEL: test12:
988 ; CHECK:       BB21_1:
989 ; CHECK-NEXT:  loop        BB21_8{{$}}
990 ; CHECK-NOT:   block
991 ; CHECK:       block       BB21_7{{$}}
992 ; CHECK-NEXT:  block       BB21_6{{$}}
993 ; CHECK-NEXT:  block       BB21_4{{$}}
994 ; CHECK:       br_if       {{[^,]*}}, BB21_4{{$}}
995 ; CHECK-NOT:   block
996 ; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
997 ; CHECK-NOT:   block
998 ; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
999 ; CHECK-NEXT:  br          BB21_6{{$}}
1000 ; CHECK-NEXT:  BB21_4:
1001 ; CHECK-NOT:   block
1002 ; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
1003 ; CHECK-NOT:   block
1004 ; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
1005 ; CHECK-NEXT:  BB21_6:
1006 ; CHECK-NEXT:  return{{$}}
1007 ; CHECK-NEXT:  BB21_7:
1008 ; CHECK-NOT:   block
1009 ; CHECK:       br          BB21_1{{$}}
1010 ; CHECK-NEXT:  BB21_8:
1011 ; OPT-LABEL: test12:
1012 ; OPT:       BB21_1:
1013 ; OPT-NEXT:  loop        BB21_8{{$}}
1014 ; OPT-NOT:   block
1015 ; OPT:       block       BB21_7{{$}}
1016 ; OPT-NEXT:  block       BB21_6{{$}}
1017 ; OPT-NEXT:  block       BB21_4{{$}}
1018 ; OPT:       br_if       {{[^,]*}}, BB21_4{{$}}
1019 ; OPT-NOT:   block
1020 ; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
1021 ; OPT-NOT:   block
1022 ; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
1023 ; OPT-NEXT:  br          BB21_6{{$}}
1024 ; OPT-NEXT:  BB21_4:
1025 ; OPT-NOT:   block
1026 ; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
1027 ; OPT-NOT:   block
1028 ; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
1029 ; OPT-NEXT:  BB21_6:
1030 ; OPT-NEXT:  return{{$}}
1031 ; OPT-NEXT:  BB21_7:
1032 ; OPT-NOT:   block
1033 ; OPT:       br          BB21_1{{$}}
1034 ; OPT-NEXT:  BB21_8:
1035 define void @test12(i8* %arg) {
1036 bb:
1037   br label %bb1
1038
1039 bb1:
1040   %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb4 ]
1041   %tmp2 = getelementptr i8, i8* %arg, i32 %tmp
1042   %tmp3 = load i8, i8* %tmp2
1043   switch i8 %tmp3, label %bb7 [
1044     i8 42, label %bb4
1045     i8 76, label %bb4
1046     i8 108, label %bb4
1047     i8 104, label %bb4
1048   ]
1049
1050 bb4:
1051   %tmp5 = add i32 %tmp, 1
1052   br label %bb1
1053
1054 bb7:
1055   ret void
1056 }
1057
1058 ; A block can be "branched to" from another even if it is also reachable via
1059 ; fallthrough from the other. This would normally be optimized away, so use
1060 ; optnone to disable optimizations to test this case.
1061
1062 ; CHECK-LABEL: test13:
1063 ; CHECK-NEXT:  .local i32{{$}}
1064 ; CHECK:       block BB22_2{{$}}
1065 ; CHECK:       br_if $pop4, BB22_2{{$}}
1066 ; CHECK-NEXT:  return{{$}}
1067 ; CHECK-NEXT:  BB22_2:
1068 ; CHECK:       block BB22_4{{$}}
1069 ; CHECK-NEXT:  br_if $0, BB22_4{{$}}
1070 ; CHECK:       BB22_4:
1071 ; CHECK:       block BB22_5{{$}}
1072 ; CHECK:       br_if $pop6, BB22_5{{$}}
1073 ; CHECK-NEXT:  BB22_5:
1074 ; CHECK-NEXT:  unreachable{{$}}
1075 ; OPT-LABEL: test13:
1076 ; OPT-NEXT:  .local i32{{$}}
1077 ; OPT:       block BB22_2{{$}}
1078 ; OPT:       br_if $pop4, BB22_2{{$}}
1079 ; OPT-NEXT:  return{{$}}
1080 ; OPT-NEXT:  BB22_2:
1081 ; OPT:       block BB22_4{{$}}
1082 ; OPT-NEXT:  br_if $0, BB22_4{{$}}
1083 ; OPT:       BB22_4:
1084 ; OPT:       block BB22_5{{$}}
1085 ; OPT:       br_if $pop6, BB22_5{{$}}
1086 ; OPT-NEXT:  BB22_5:
1087 ; OPT-NEXT:  unreachable{{$}}
1088 define void @test13() noinline optnone {
1089 bb:
1090   br i1 undef, label %bb5, label %bb2
1091 bb1:
1092   unreachable
1093 bb2:
1094   br i1 undef, label %bb3, label %bb4
1095 bb3:
1096   br label %bb4
1097 bb4:
1098   %tmp = phi i1 [ false, %bb2 ], [ false, %bb3 ]
1099   br i1 %tmp, label %bb1, label %bb1
1100 bb5:
1101   ret void
1102 }