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