test/CodeGen/WebAssembly/cfg-stackify.ll

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