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-NEXT: 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-NEXT: 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-NEXT:  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-NEXT:  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-NEXT:  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-NEXT:  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-NEXT:  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 }