llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

   1 ; RUN: opt -passes='loop(simple-loop-unswitch),verify<loops>' -S < %s | FileCheck %s
   2 ; RUN: opt -verify-memoryssa -passes='loop-mssa(simple-loop-unswitch),verify<loops>' -S < %s | FileCheck %s
   3
   4 declare void @some_func() noreturn
   5 declare void @sink(i32)
   6
   7 declare i1 @cond()
   8 declare i32 @cond.i32()
   9
  10 ; This test contains two trivial unswitch condition in one loop.
  11 ; LoopUnswitch pass should be able to unswitch the second one
  12 ; after unswitching the first one.
  13 define i32 @test1(i32* %var, i1 %cond1, i1 %cond2) {
  14 ; CHECK-LABEL: @test1(
  15 entry:
  16   br label %loop_begin
  17 ; CHECK-NEXT:  entry:
  18 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split, label %loop_exit.split
  19 ;
  20 ; CHECK:       entry.split:
  21 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split.split, label %loop_exit
  22 ;
  23 ; CHECK:       entry.split.split:
  24 ; CHECK-NEXT:    br label %loop_begin
  25
  26 loop_begin:
  27   br i1 %cond1, label %continue, label %loop_exit       ; first trivial condition
  28 ; CHECK:       loop_begin:
  29 ; CHECK-NEXT:    br label %continue
  30
  31 continue:
  32   %var_val = load i32, i32* %var
  33   br i1 %cond2, label %do_something, label %loop_exit   ; second trivial condition
  34 ; CHECK:       continue:
  35 ; CHECK-NEXT:    load
  36 ; CHECK-NEXT:    br label %do_something
  37
  38 do_something:
  39   call void @some_func() noreturn nounwind
  40   br label %loop_begin
  41 ; CHECK:       do_something:
  42 ; CHECK-NEXT:    call
  43 ; CHECK-NEXT:    br label %loop_begin
  44
  45 loop_exit:
  46   ret i32 0
  47 ; CHECK:       loop_exit:
  48 ; CHECK-NEXT:    br label %loop_exit.split
  49 ;
  50 ; CHECK:       loop_exit.split:
  51 ; CHECK-NEXT:    ret
  52 }
  53
  54 ; Test for two trivially unswitchable switches.
  55 define i32 @test3(i32* %var, i32 %cond1, i32 %cond2) {
  56 ; CHECK-LABEL: @test3(
  57 entry:
  58   br label %loop_begin
  59 ; CHECK-NEXT:  entry:
  60 ; CHECK-NEXT:    switch i32 %cond1, label %entry.split [
  61 ; CHECK-NEXT:      i32 0, label %loop_exit1
  62 ; CHECK-NEXT:    ]
  63 ;
  64 ; CHECK:       entry.split:
  65 ; CHECK-NEXT:    switch i32 %cond2, label %loop_exit2 [
  66 ; CHECK-NEXT:      i32 42, label %loop_exit2
  67 ; CHECK-NEXT:      i32 0, label %entry.split.split
  68 ; CHECK-NEXT:    ]
  69 ;
  70 ; CHECK:       entry.split.split:
  71 ; CHECK-NEXT:    br label %loop_begin
  72
  73 loop_begin:
  74   switch i32 %cond1, label %continue [
  75     i32 0, label %loop_exit1
  76   ]
  77 ; CHECK:       loop_begin:
  78 ; CHECK-NEXT:    br label %continue
  79
  80 continue:
  81   %var_val = load i32, i32* %var
  82   switch i32 %cond2, label %loop_exit2 [
  83     i32 0, label %do_something
  84     i32 42, label %loop_exit2
  85   ]
  86 ; CHECK:       continue:
  87 ; CHECK-NEXT:    load
  88 ; CHECK-NEXT:    br label %do_something
  89
  90 do_something:
  91   call void @some_func() noreturn nounwind
  92   br label %loop_begin
  93 ; CHECK:       do_something:
  94 ; CHECK-NEXT:    call
  95 ; CHECK-NEXT:    br label %loop_begin
  96
  97 loop_exit1:
  98   ret i32 0
  99 ; CHECK:       loop_exit1:
 100 ; CHECK-NEXT:    ret
 101
 102 loop_exit2:
 103   ret i32 0
 104 ; CHECK:       loop_exit2:
 105 ; CHECK-NEXT:    ret
 106 ;
 107 ; We shouldn't have any unreachable blocks here because the unswitched switches
 108 ; turn into branches instead.
 109 ; CHECK-NOT:     unreachable
 110 }
 111
 112 ; Test for a trivially unswitchable switch with multiple exiting cases and
 113 ; multiple looping cases.
 114 define i32 @test4(i32* %var, i32 %cond1, i32 %cond2) {
 115 ; CHECK-LABEL: @test4(
 116 entry:
 117   br label %loop_begin
 118 ; CHECK-NEXT:  entry:
 119 ; CHECK-NEXT:    switch i32 %cond2, label %loop_exit2 [
 120 ; CHECK-NEXT:      i32 13, label %loop_exit1
 121 ; CHECK-NEXT:      i32 42, label %loop_exit3
 122 ; CHECK-NEXT:      i32 0, label %entry.split
 123 ; CHECK-NEXT:      i32 1, label %entry.split
 124 ; CHECK-NEXT:      i32 2, label %entry.split
 125 ; CHECK-NEXT:    ]
 126 ;
 127 ; CHECK:       entry.split:
 128 ; CHECK-NEXT:    br label %loop_begin
 129
 130 loop_begin:
 131   %var_val = load i32, i32* %var
 132   switch i32 %cond2, label %loop_exit2 [
 133     i32 0, label %loop0
 134     i32 1, label %loop1
 135     i32 13, label %loop_exit1
 136     i32 2, label %loop2
 137     i32 42, label %loop_exit3
 138   ]
 139 ; CHECK:       loop_begin:
 140 ; CHECK-NEXT:    load
 141 ; CHECK-NEXT:    switch i32 %cond2, label %loop2 [
 142 ; CHECK-NEXT:      i32 0, label %loop0
 143 ; CHECK-NEXT:      i32 1, label %loop1
 144 ; CHECK-NEXT:    ]
 145
 146 loop0:
 147   call void @some_func() noreturn nounwind
 148   br label %loop_latch
 149 ; CHECK:       loop0:
 150 ; CHECK-NEXT:    call
 151 ; CHECK-NEXT:    br label %loop_latch
 152
 153 loop1:
 154   call void @some_func() noreturn nounwind
 155   br label %loop_latch
 156 ; CHECK:       loop1:
 157 ; CHECK-NEXT:    call
 158 ; CHECK-NEXT:    br label %loop_latch
 159
 160 loop2:
 161   call void @some_func() noreturn nounwind
 162   br label %loop_latch
 163 ; CHECK:       loop2:
 164 ; CHECK-NEXT:    call
 165 ; CHECK-NEXT:    br label %loop_latch
 166
 167 loop_latch:
 168   br label %loop_begin
 169 ; CHECK:       loop_latch:
 170 ; CHECK-NEXT:    br label %loop_begin
 171
 172 loop_exit1:
 173   ret i32 0
 174 ; CHECK:       loop_exit1:
 175 ; CHECK-NEXT:    ret
 176
 177 loop_exit2:
 178   ret i32 0
 179 ; CHECK:       loop_exit2:
 180 ; CHECK-NEXT:    ret
 181
 182 loop_exit3:
 183   ret i32 0
 184 ; CHECK:       loop_exit3:
 185 ; CHECK-NEXT:    ret
 186 }
 187
 188 ; This test contains a trivially unswitchable branch with an LCSSA phi node in
 189 ; a loop exit block.
 190 define i32 @test5(i1 %cond1, i32 %x, i32 %y) {
 191 ; CHECK-LABEL: @test5(
 192 entry:
 193   br label %loop_begin
 194 ; CHECK-NEXT:  entry:
 195 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split, label %loop_exit
 196 ;
 197 ; CHECK:       entry.split:
 198 ; CHECK-NEXT:    br label %loop_begin
 199
 200 loop_begin:
 201   br i1 %cond1, label %latch, label %loop_exit
 202 ; CHECK:       loop_begin:
 203 ; CHECK-NEXT:    br label %latch
 204
 205 latch:
 206   call void @some_func() noreturn nounwind
 207   br label %loop_begin
 208 ; CHECK:       latch:
 209 ; CHECK-NEXT:    call
 210 ; CHECK-NEXT:    br label %loop_begin
 211
 212 loop_exit:
 213   %result1 = phi i32 [ %x, %loop_begin ]
 214   %result2 = phi i32 [ %y, %loop_begin ]
 215   %result = add i32 %result1, %result2
 216   ret i32 %result
 217 ; CHECK:       loop_exit:
 218 ; CHECK-NEXT:    %[[R1:.*]] = phi i32 [ %x, %entry ]
 219 ; CHECK-NEXT:    %[[R2:.*]] = phi i32 [ %y, %entry ]
 220 ; CHECK-NEXT:    %[[R:.*]] = add i32 %[[R1]], %[[R2]]
 221 ; CHECK-NEXT:    ret i32 %[[R]]
 222 }
 223
 224 ; This test contains a trivially unswitchable branch with a real phi node in LCSSA
 225 ; position in a shared exit block where a different path through the loop
 226 ; produces a non-invariant input to the PHI node.
 227 define i32 @test6(i32* %var, i1 %cond1, i1 %cond2, i32 %x, i32 %y) {
 228 ; CHECK-LABEL: @test6(
 229 entry:
 230   br label %loop_begin
 231 ; CHECK-NEXT:  entry:
 232 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split, label %loop_exit.split
 233 ;
 234 ; CHECK:       entry.split:
 235 ; CHECK-NEXT:    br label %loop_begin
 236
 237 loop_begin:
 238   br i1 %cond1, label %continue, label %loop_exit
 239 ; CHECK:       loop_begin:
 240 ; CHECK-NEXT:    br label %continue
 241
 242 continue:
 243   %var_val = load i32, i32* %var
 244   br i1 %cond2, label %latch, label %loop_exit
 245 ; CHECK:       continue:
 246 ; CHECK-NEXT:    load
 247 ; CHECK-NEXT:    br i1 %cond2, label %latch, label %loop_exit
 248
 249 latch:
 250   call void @some_func() noreturn nounwind
 251   br label %loop_begin
 252 ; CHECK:       latch:
 253 ; CHECK-NEXT:    call
 254 ; CHECK-NEXT:    br label %loop_begin
 255
 256 loop_exit:
 257   %result1 = phi i32 [ %x, %loop_begin ], [ %var_val, %continue ]
 258   %result2 = phi i32 [ %var_val, %continue ], [ %y, %loop_begin ]
 259   %result = add i32 %result1, %result2
 260   ret i32 %result
 261 ; CHECK:       loop_exit:
 262 ; CHECK-NEXT:    %[[R1:.*]] = phi i32 [ %var_val, %continue ]
 263 ; CHECK-NEXT:    %[[R2:.*]] = phi i32 [ %var_val, %continue ]
 264 ; CHECK-NEXT:    br label %loop_exit.split
 265 ;
 266 ; CHECK:       loop_exit.split:
 267 ; CHECK-NEXT:    %[[R1S:.*]] = phi i32 [ %x, %entry ], [ %[[R1]], %loop_exit ]
 268 ; CHECK-NEXT:    %[[R2S:.*]] = phi i32 [ %y, %entry ], [ %[[R2]], %loop_exit ]
 269 ; CHECK-NEXT:    %[[R:.*]] = add i32 %[[R1S]], %[[R2S]]
 270 ; CHECK-NEXT:    ret i32 %[[R]]
 271 }
 272
 273 ; This test contains a trivially unswitchable switch with an LCSSA phi node in
 274 ; a loop exit block.
 275 define i32 @test7(i32 %cond1, i32 %x, i32 %y) {
 276 ; CHECK-LABEL: @test7(
 277 entry:
 278   br label %loop_begin
 279 ; CHECK-NEXT:  entry:
 280 ; CHECK-NEXT:    switch i32 %cond1, label %entry.split [
 281 ; CHECK-NEXT:      i32 0, label %loop_exit
 282 ; CHECK-NEXT:      i32 1, label %loop_exit
 283 ; CHECK-NEXT:    ]
 284 ;
 285 ; CHECK:       entry.split:
 286 ; CHECK-NEXT:    br label %loop_begin
 287
 288 loop_begin:
 289   switch i32 %cond1, label %latch [
 290     i32 0, label %loop_exit
 291     i32 1, label %loop_exit
 292   ]
 293 ; CHECK:       loop_begin:
 294 ; CHECK-NEXT:    br label %latch
 295
 296 latch:
 297   call void @some_func() noreturn nounwind
 298   br label %loop_begin
 299 ; CHECK:       latch:
 300 ; CHECK-NEXT:    call
 301 ; CHECK-NEXT:    br label %loop_begin
 302
 303 loop_exit:
 304   %result1 = phi i32 [ %x, %loop_begin ], [ %x, %loop_begin ]
 305   %result2 = phi i32 [ %y, %loop_begin ], [ %y, %loop_begin ]
 306   %result = add i32 %result1, %result2
 307   ret i32 %result
 308 ; CHECK:       loop_exit:
 309 ; CHECK-NEXT:    %[[R1:.*]] = phi i32 [ %x, %entry ], [ %x, %entry ]
 310 ; CHECK-NEXT:    %[[R2:.*]] = phi i32 [ %y, %entry ], [ %y, %entry ]
 311 ; CHECK-NEXT:    %[[R:.*]] = add i32 %[[R1]], %[[R2]]
 312 ; CHECK-NEXT:    ret i32 %[[R]]
 313 }
 314
 315 ; This test contains a trivially unswitchable switch with a real phi node in
 316 ; LCSSA position in a shared exit block where a different path through the loop
 317 ; produces a non-invariant input to the PHI node.
 318 define i32 @test8(i32* %var, i32 %cond1, i32 %cond2, i32 %x, i32 %y) {
 319 ; CHECK-LABEL: @test8(
 320 entry:
 321   br label %loop_begin
 322 ; CHECK-NEXT:  entry:
 323 ; CHECK-NEXT:    switch i32 %cond1, label %entry.split [
 324 ; CHECK-NEXT:      i32 0, label %loop_exit.split
 325 ; CHECK-NEXT:      i32 1, label %loop_exit2
 326 ; CHECK-NEXT:      i32 2, label %loop_exit.split
 327 ; CHECK-NEXT:    ]
 328 ;
 329 ; CHECK:       entry.split:
 330 ; CHECK-NEXT:    br label %loop_begin
 331
 332 loop_begin:
 333   switch i32 %cond1, label %continue [
 334     i32 0, label %loop_exit
 335     i32 1, label %loop_exit2
 336     i32 2, label %loop_exit
 337   ]
 338 ; CHECK:       loop_begin:
 339 ; CHECK-NEXT:    br label %continue
 340
 341 continue:
 342   %var_val = load i32, i32* %var
 343   switch i32 %cond2, label %latch [
 344     i32 0, label %loop_exit
 345   ]
 346 ; CHECK:       continue:
 347 ; CHECK-NEXT:    load
 348 ; CHECK-NEXT:    switch i32 %cond2, label %latch [
 349 ; CHECK-NEXT:      i32 0, label %loop_exit
 350 ; CHECK-NEXT:    ]
 351
 352 latch:
 353   call void @some_func() noreturn nounwind
 354   br label %loop_begin
 355 ; CHECK:       latch:
 356 ; CHECK-NEXT:    call
 357 ; CHECK-NEXT:    br label %loop_begin
 358
 359 loop_exit:
 360   %result1.1 = phi i32 [ %x, %loop_begin ], [ %x, %loop_begin ], [ %var_val, %continue ]
 361   %result1.2 = phi i32 [ %var_val, %continue ], [ %y, %loop_begin ], [ %y, %loop_begin ]
 362   %result1 = add i32 %result1.1, %result1.2
 363   ret i32 %result1
 364 ; CHECK:       loop_exit:
 365 ; CHECK-NEXT:    %[[R1:.*]] = phi i32 [ %var_val, %continue ]
 366 ; CHECK-NEXT:    %[[R2:.*]] = phi i32 [ %var_val, %continue ]
 367 ; CHECK-NEXT:    br label %loop_exit.split
 368 ;
 369 ; CHECK:       loop_exit.split:
 370 ; CHECK-NEXT:    %[[R1S:.*]] = phi i32 [ %x, %entry ], [ %x, %entry ], [ %[[R1]], %loop_exit ]
 371 ; CHECK-NEXT:    %[[R2S:.*]] = phi i32 [ %y, %entry ], [ %y, %entry ], [ %[[R2]], %loop_exit ]
 372 ; CHECK-NEXT:    %[[R:.*]] = add i32 %[[R1S]], %[[R2S]]
 373 ; CHECK-NEXT:    ret i32 %[[R]]
 374
 375 loop_exit2:
 376   %result2.1 = phi i32 [ %x, %loop_begin ]
 377   %result2.2 = phi i32 [ %y, %loop_begin ]
 378   %result2 = add i32 %result2.1, %result2.2
 379   ret i32 %result2
 380 ; CHECK:       loop_exit2:
 381 ; CHECK-NEXT:    %[[R1:.*]] = phi i32 [ %x, %entry ]
 382 ; CHECK-NEXT:    %[[R2:.*]] = phi i32 [ %y, %entry ]
 383 ; CHECK-NEXT:    %[[R:.*]] = add i32 %[[R1]], %[[R2]]
 384 ; CHECK-NEXT:    ret i32 %[[R]]
 385 }
 386
 387 ; This test, extracted from the LLVM test suite, has an interesting dominator
 388 ; tree to update as there are edges to sibling domtree nodes within child
 389 ; domtree nodes of the unswitched node.
 390 define void @xgets(i1 %cond1, i1* %cond2.ptr) {
 391 ; CHECK-LABEL: @xgets(
 392 entry:
 393   br label %for.cond.preheader
 394 ; CHECK:       entry:
 395 ; CHECK-NEXT:    br label %for.cond.preheader
 396
 397 for.cond.preheader:
 398   br label %for.cond
 399 ; CHECK:       for.cond.preheader:
 400 ; CHECK-NEXT:    br i1 %cond1, label %for.cond.preheader.split, label %if.end17.thread.loopexit
 401 ;
 402 ; CHECK:       for.cond.preheader.split:
 403 ; CHECK-NEXT:    br label %for.cond
 404
 405 for.cond:
 406   br i1 %cond1, label %land.lhs.true, label %if.end17.thread.loopexit
 407 ; CHECK:       for.cond:
 408 ; CHECK-NEXT:    br label %land.lhs.true
 409
 410 land.lhs.true:
 411   br label %if.then20
 412 ; CHECK:       land.lhs.true:
 413 ; CHECK-NEXT:    br label %if.then20
 414
 415 if.then20:
 416   %cond2 = load volatile i1, i1* %cond2.ptr
 417   br i1 %cond2, label %if.then23, label %if.else
 418 ; CHECK:       if.then20:
 419 ; CHECK-NEXT:    %[[COND2:.*]] = load volatile i1, i1* %cond2.ptr
 420 ; CHECK-NEXT:    br i1 %[[COND2]], label %if.then23, label %if.else
 421
 422 if.else:
 423   br label %for.cond
 424 ; CHECK:       if.else:
 425 ; CHECK-NEXT:    br label %for.cond
 426
 427 if.end17.thread.loopexit:
 428   br label %if.end17.thread
 429 ; CHECK:       if.end17.thread.loopexit:
 430 ; CHECK-NEXT:    br label %if.end17.thread
 431
 432 if.end17.thread:
 433   br label %cleanup
 434 ; CHECK:       if.end17.thread:
 435 ; CHECK-NEXT:    br label %cleanup
 436
 437 if.then23:
 438   br label %cleanup
 439 ; CHECK:       if.then23:
 440 ; CHECK-NEXT:    br label %cleanup
 441
 442 cleanup:
 443   ret void
 444 ; CHECK:       cleanup:
 445 ; CHECK-NEXT:    ret void
 446 }
 447
 448 define i32 @test_partial_condition_unswitch_and(i32* %var, i1 %cond1, i1 %cond2) {
 449 ; CHECK-LABEL: @test_partial_condition_unswitch_and(
 450 entry:
 451   br label %loop_begin
 452 ; CHECK-NEXT:  entry:
 453 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 454 ;
 455 ; CHECK:       entry.split:
 456 ; CHECK-NEXT:    br i1 %cond2, label %entry.split.split, label %loop_exit
 457 ;
 458 ; CHECK:       entry.split.split:
 459 ; CHECK-NEXT:    br label %loop_begin
 460
 461 loop_begin:
 462   br i1 %cond1, label %continue, label %loop_exit
 463 ; CHECK:       loop_begin:
 464 ; CHECK-NEXT:    br label %continue
 465
 466 continue:
 467   %var_val = load i32, i32* %var
 468   %var_cond = trunc i32 %var_val to i1
 469   %cond_and = and i1 %var_cond, %cond2
 470   br i1 %cond_and, label %do_something, label %loop_exit
 471 ; CHECK:       continue:
 472 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 473 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 474 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 475 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 476
 477 do_something:
 478   call void @some_func() noreturn nounwind
 479   br label %loop_begin
 480 ; CHECK:       do_something:
 481 ; CHECK-NEXT:    call
 482 ; CHECK-NEXT:    br label %loop_begin
 483
 484 loop_exit:
 485   ret i32 0
 486 ; CHECK:       loop_exit:
 487 ; CHECK-NEXT:    br label %loop_exit.split
 488 ;
 489 ; CHECK:       loop_exit.split:
 490 ; CHECK-NEXT:    ret
 491 }
 492
 493 define i32 @test_partial_condition_unswitch_and_select(i32* %var, i1 %cond1, i1 %cond2) {
 494 ; CHECK-LABEL: @test_partial_condition_unswitch_and_select(
 495 entry:
 496   br label %loop_begin
 497 ; CHECK-NEXT:  entry:
 498 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 499 ;
 500 ; CHECK:       entry.split:
 501 ; CHECK-NEXT:    br i1 %cond2, label %entry.split.split, label %loop_exit
 502 ;
 503 ; CHECK:       entry.split.split:
 504 ; CHECK-NEXT:    br label %loop_begin
 505
 506 loop_begin:
 507   br i1 %cond1, label %continue, label %loop_exit
 508 ; CHECK:       loop_begin:
 509 ; CHECK-NEXT:    br label %continue
 510
 511 continue:
 512   %var_val = load i32, i32* %var
 513   %var_cond = trunc i32 %var_val to i1
 514   %cond_and = select i1 %var_cond, i1 %cond2, i1 false
 515   br i1 %cond_and, label %do_something, label %loop_exit
 516 ; CHECK:       continue:
 517 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 518 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 519 ; CHECK-NEXT:    %[[COND_AND:.*]] = select i1 %[[VAR_COND]], i1 true, i1 false
 520 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 521
 522 do_something:
 523   call void @some_func() noreturn nounwind
 524   br label %loop_begin
 525 ; CHECK:       do_something:
 526 ; CHECK-NEXT:    call
 527 ; CHECK-NEXT:    br label %loop_begin
 528
 529 loop_exit:
 530   ret i32 0
 531 ; CHECK:       loop_exit:
 532 ; CHECK-NEXT:    br label %loop_exit.split
 533 ;
 534 ; CHECK:       loop_exit.split:
 535 ; CHECK-NEXT:    ret
 536 }
 537
 538 define i32 @test_partial_condition_unswitch_or_simple_select(i32* %var, i1 %cond1, i1 %cond2) {
 539 ; CHECK-LABEL: @test_partial_condition_unswitch_or_simple_select(
 540 entry:
 541   br label %loop_begin
 542 ; CHECK-NEXT:  entry:
 543 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 544 ;
 545 ; CHECK:       entry.split:
 546 ; CHECK-NEXT:    br i1 %cond2, label %loop_exit.split1, label %entry.split.split
 547 ;
 548 ; CHECK:       entry.split.split:
 549 ; CHECK-NEXT:    br label %loop_begin
 550
 551 loop_begin:
 552   br i1 %cond1, label %continue, label %loop_exit
 553 ; CHECK:       loop_begin:
 554 ; CHECK-NEXT:    br label %continue
 555
 556 continue:
 557   %var_val = load i32, i32* %var
 558   %var_cond = trunc i32 %var_val to i1
 559   %cond_or = select i1 %var_cond, i1 true, i1 %cond2
 560   br i1 %cond_or, label %loop_exit, label %do_something
 561 ; CHECK:       continue:
 562 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 563 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 564 ; CHECK-NEXT:    %[[COND_OR:.*]] = select i1 %[[VAR_COND]], i1 true, i1 false
 565 ; CHECK-NEXT:    br i1 %[[COND_OR]], label %loop_exit, label %do_something
 566
 567 do_something:
 568   call void @some_func() noreturn nounwind
 569   br label %loop_begin
 570 ; CHECK:       do_something:
 571 ; CHECK-NEXT:    call
 572 ; CHECK-NEXT:    br label %loop_begin
 573
 574 loop_exit:
 575   ret i32 0
 576 ; CHECK:       loop_exit:
 577 ; CHECK-NEXT:    br label %loop_exit.split1
 578 ;
 579 ; CHECK:       loop_exit.split1:
 580 ; CHECK-NEXT:    br label %loop_exit.split
 581 ;
 582 ; CHECK:       loop_exit.split:
 583 ; CHECK-NEXT:    ret
 584 }
 585
 586 define i32 @test_partial_condition_unswitch_or(i32* %var, i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4, i1 %cond5, i1 %cond6) {
 587 ; CHECK-LABEL: @test_partial_condition_unswitch_or(
 588 entry:
 589   br label %loop_begin
 590 ; CHECK-NEXT:  entry:
 591 ; CHECK-NEXT:    %[[INV_OR1:.*]] = or i1 %cond4, %cond2
 592 ; CHECK-NEXT:    %[[INV_OR2:.*]] = or i1 %[[INV_OR1]], %cond3
 593 ; CHECK-NEXT:    %[[INV_OR3:.*]] = or i1 %[[INV_OR2]], %cond1
 594 ; CHECK-NEXT:    br i1 %[[INV_OR3]], label %loop_exit.split, label %entry.split
 595 ;
 596 ; CHECK:       entry.split:
 597 ; CHECK-NEXT:    br label %loop_begin
 598
 599 loop_begin:
 600   %var_val = load i32, i32* %var
 601   %var_cond = trunc i32 %var_val to i1
 602   %cond_or1 = or i1 %var_cond, %cond1
 603   %cond_or2 = or i1 %cond2, %cond3
 604   %cond_or3 = or i1 %cond_or1, %cond_or2
 605   %cond_xor1 = xor i1 %cond5, %var_cond
 606   %cond_and1 = and i1 %cond6, %var_cond
 607   %cond_or4 = or i1 %cond_xor1, %cond_and1
 608   %cond_or5 = or i1 %cond_or3, %cond_or4
 609   %cond_or6 = or i1 %cond_or5, %cond4
 610   br i1 %cond_or6, label %loop_exit, label %do_something
 611 ; CHECK:       loop_begin:
 612 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 613 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 614 ; CHECK-NEXT:    %[[COND_OR1:.*]] = or i1 %[[VAR_COND]], false
 615 ; CHECK-NEXT:    %[[COND_OR2:.*]] = or i1 false, false
 616 ; CHECK-NEXT:    %[[COND_OR3:.*]] = or i1 %[[COND_OR1]], %[[COND_OR2]]
 617 ; CHECK-NEXT:    %[[COND_XOR:.*]] = xor i1 %cond5, %[[VAR_COND]]
 618 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %cond6, %[[VAR_COND]]
 619 ; CHECK-NEXT:    %[[COND_OR4:.*]] = or i1 %[[COND_XOR]], %[[COND_AND]]
 620 ; CHECK-NEXT:    %[[COND_OR5:.*]] = or i1 %[[COND_OR3]], %[[COND_OR4]]
 621 ; CHECK-NEXT:    %[[COND_OR6:.*]] = or i1 %[[COND_OR5]], false
 622 ; CHECK-NEXT:    br i1 %[[COND_OR6]], label %loop_exit, label %do_something
 623
 624 do_something:
 625   call void @some_func() noreturn nounwind
 626   br label %loop_begin
 627 ; CHECK:       do_something:
 628 ; CHECK-NEXT:    call
 629 ; CHECK-NEXT:    br label %loop_begin
 630
 631 loop_exit:
 632   ret i32 0
 633 ; CHECK:       loop_exit.split:
 634 ; CHECK-NEXT:    ret
 635 }
 636
 637 ; Check that loop unswitch looks through a combination of or and select instructions.
 638 ; Note that cond6 can be unswitched because `select i1 %cond_or5, i1 true, i1 false` is
 639 ; both logical-or and logical-and.
 640 define i32 @test_partial_condition_unswitch_or_select(i32* %var, i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4, i1 %cond5, i1 %cond6) {
 641 ; CHECK-LABEL: @test_partial_condition_unswitch_or_select(
 642 entry:
 643   br label %loop_begin
 644 ; CHECK-NEXT:  entry:
 645 ; CHECK-NEXT:    %[[INV_OR1:.*]] = or i1 %cond4, %cond2
 646 ; CHECK-NEXT:    %[[INV_OR2:.*]] = or i1 %[[INV_OR1]], %cond3
 647 ; CHECK-NEXT:    %[[INV_OR3:.*]] = or i1 %[[INV_OR2]], %cond1
 648 ; CHECK-NEXT:    br i1 %[[INV_OR3]], label %loop_exit.split, label %entry.split
 649 ;
 650 ; CHECK:       entry.split:
 651 ; CHECK-NEXT:    br i1 %cond6, label %loop_exit.split1, label %entry.split.split
 652 ;
 653 ; CHECK:       entry.split.split:
 654 ; CHECK-NEXT:    br label %loop_begin
 655
 656 loop_begin:
 657   %var_val = load i32, i32* %var
 658   %var_cond = trunc i32 %var_val to i1
 659   %cond_or1 = or i1 %var_cond, %cond1
 660   %cond_or2 = or i1 %cond2, %cond3
 661   %cond_or3 = or i1 %cond_or1, %cond_or2
 662   %cond_xor1 = xor i1 %cond5, %var_cond
 663   %cond_and1 = and i1 %cond6, %var_cond
 664   %cond_or4 = or i1 %cond_xor1, %cond_and1
 665   %cond_or5 = select i1 %cond_or3, i1 true, i1 %cond_or4
 666   %cond_or6 = select i1 %cond_or5, i1 true, i1 %cond4
 667   br i1 %cond_or6, label %loop_exit, label %do_something
 668 ; CHECK:       loop_begin:
 669 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 670 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 671 ; CHECK-NEXT:    %[[COND_OR1:.*]] = or i1 %[[VAR_COND]], false
 672 ; CHECK-NEXT:    %[[COND_OR2:.*]] = or i1 false, false
 673 ; CHECK-NEXT:    %[[COND_OR3:.*]] = or i1 %[[COND_OR1]], %[[COND_OR2]]
 674 ; CHECK-NEXT:    %[[COND_XOR:.*]] = xor i1 %cond5, %[[VAR_COND]]
 675 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 false, %[[VAR_COND]]
 676 ; CHECK-NEXT:    %[[COND_OR4:.*]] = or i1 %[[COND_XOR]], %[[COND_AND]]
 677 ; CHECK-NEXT:    %[[COND_OR5:.*]] = select i1 %[[COND_OR3]], i1 true, i1 %[[COND_OR4]]
 678 ; CHECK-NEXT:    %[[COND_OR6:.*]] = select i1 %[[COND_OR5]], i1 true, i1 false
 679 ; CHECK-NEXT:    br i1 %[[COND_OR6]], label %loop_exit, label %do_something
 680
 681 do_something:
 682   call void @some_func() noreturn nounwind
 683   br label %loop_begin
 684 ; CHECK:       do_something:
 685 ; CHECK-NEXT:    call
 686 ; CHECK-NEXT:    br label %loop_begin
 687
 688 loop_exit:
 689   ret i32 0
 690 ; CHECK:       loop_exit.split:
 691 ; CHECK-NEXT:    ret
 692 }
 693
 694 define i32 @test_partial_condition_unswitch_with_lcssa_phi1(i32* %var, i1 %cond, i32 %x) {
 695 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi1(
 696 entry:
 697   br label %loop_begin
 698 ; CHECK-NEXT:  entry:
 699 ; CHECK-NEXT:    br i1 %cond, label %entry.split, label %loop_exit.split
 700 ;
 701 ; CHECK:       entry.split:
 702 ; CHECK-NEXT:    br label %loop_begin
 703
 704 loop_begin:
 705   %var_val = load i32, i32* %var
 706   %var_cond = trunc i32 %var_val to i1
 707   %cond_and = and i1 %var_cond, %cond
 708   br i1 %cond_and, label %do_something, label %loop_exit
 709 ; CHECK:       loop_begin:
 710 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 711 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 712 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 713 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 714
 715 do_something:
 716   call void @some_func() noreturn nounwind
 717   br label %loop_begin
 718 ; CHECK:       do_something:
 719 ; CHECK-NEXT:    call
 720 ; CHECK-NEXT:    br label %loop_begin
 721
 722 loop_exit:
 723   %x.lcssa = phi i32 [ %x, %loop_begin ]
 724   ret i32 %x.lcssa
 725 ; CHECK:       loop_exit:
 726 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %x, %loop_begin ]
 727 ; CHECK-NEXT:    br label %loop_exit.split
 728 ;
 729 ; CHECK:       loop_exit.split:
 730 ; CHECK-NEXT:    %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ]
 731 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 732 }
 733
 734 define i32 @test_partial_condition_unswitch_with_lcssa_phi2(i32* %var, i1 %cond, i32 %x, i32 %y) {
 735 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi2(
 736 entry:
 737   br label %loop_begin
 738 ; CHECK-NEXT:  entry:
 739 ; CHECK-NEXT:    br i1 %cond, label %entry.split, label %loop_exit.split
 740 ;
 741 ; CHECK:       entry.split:
 742 ; CHECK-NEXT:    br label %loop_begin
 743
 744 loop_begin:
 745   %var_val = load i32, i32* %var
 746   %var_cond = trunc i32 %var_val to i1
 747   %cond_and = and i1 %var_cond, %cond
 748   br i1 %cond_and, label %do_something, label %loop_exit
 749 ; CHECK:       loop_begin:
 750 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 751 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 752 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 753 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 754
 755 do_something:
 756   call void @some_func() noreturn nounwind
 757   br i1 %var_cond, label %loop_begin, label %loop_exit
 758 ; CHECK:       do_something:
 759 ; CHECK-NEXT:    call
 760 ; CHECK-NEXT:    br i1 %[[VAR_COND]], label %loop_begin, label %loop_exit
 761
 762 loop_exit:
 763   %xy.lcssa = phi i32 [ %x, %loop_begin ], [ %y, %do_something ]
 764   ret i32 %xy.lcssa
 765 ; CHECK:       loop_exit:
 766 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %x, %loop_begin ], [ %y, %do_something ]
 767 ; CHECK-NEXT:    br label %loop_exit.split
 768 ;
 769 ; CHECK:       loop_exit.split:
 770 ; CHECK-NEXT:    %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ]
 771 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 772 }
 773
 774 ; Unswitch will not actually change the loop nest from:
 775 ;   A < B < C
 776 define void @hoist_inner_loop0() {
 777 ; CHECK-LABEL: define void @hoist_inner_loop0(
 778 entry:
 779   br label %a.header
 780 ; CHECK:       entry:
 781 ; CHECK-NEXT:    br label %a.header
 782
 783 a.header:
 784   br label %b.header
 785 ; CHECK:       a.header:
 786 ; CHECK-NEXT:    br label %b.header
 787
 788 b.header:
 789   %v1 = call i1 @cond()
 790   br label %c.header
 791 ; CHECK:       b.header:
 792 ; CHECK-NEXT:    %v1 = call i1 @cond()
 793 ; CHECK-NEXT:    br i1 %v1, label %[[B_LATCH_SPLIT:.*]], label %[[B_HEADER_SPLIT:.*]]
 794 ;
 795 ; CHECK:       [[B_HEADER_SPLIT]]:
 796 ; CHECK-NEXT:    br label %c.header
 797
 798 c.header:
 799   br i1 %v1, label %b.latch, label %c.latch
 800 ; CHECK:       c.header:
 801 ; CHECK-NEXT:    br label %c.latch
 802
 803 c.latch:
 804   %v2 = call i1 @cond()
 805   br i1 %v2, label %c.header, label %b.latch
 806 ; CHECK:       c.latch:
 807 ; CHECK-NEXT:    %v2 = call i1 @cond()
 808 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %b.latch
 809
 810 b.latch:
 811   %v3 = call i1 @cond()
 812   br i1 %v3, label %b.header, label %a.latch
 813 ; CHECK:       b.latch:
 814 ; CHECK-NEXT:    br label %[[B_LATCH_SPLIT]]
 815 ;
 816 ; CHECK:       [[B_LATCH_SPLIT]]:
 817 ; CHECK-NEXT:    %v3 = call i1 @cond()
 818 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
 819
 820 a.latch:
 821   br label %a.header
 822 ; CHECK:       a.latch:
 823 ; CHECK-NEXT:    br label %a.header
 824
 825 exit:
 826   ret void
 827 ; CHECK:       exit:
 828 ; CHECK-NEXT:    ret void
 829 }
 830
 831 ; Unswitch will transform the loop nest from:
 832 ;   A < B < C
 833 ; into
 834 ;   A < (B, C)
 835 define void @hoist_inner_loop1(i32* %ptr) {
 836 ; CHECK-LABEL: define void @hoist_inner_loop1(
 837 entry:
 838   br label %a.header
 839 ; CHECK:       entry:
 840 ; CHECK-NEXT:    br label %a.header
 841
 842 a.header:
 843   %x.a = load i32, i32* %ptr
 844   br label %b.header
 845 ; CHECK:       a.header:
 846 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
 847 ; CHECK-NEXT:    br label %b.header
 848
 849 b.header:
 850   %x.b = load i32, i32* %ptr
 851   %v1 = call i1 @cond()
 852   br label %c.header
 853 ; CHECK:       b.header:
 854 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 855 ; CHECK-NEXT:    %v1 = call i1 @cond()
 856 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
 857 ;
 858 ; CHECK:       [[B_HEADER_SPLIT]]:
 859 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
 860 ; CHECK-NEXT:    br label %c.header
 861
 862 c.header:
 863   br i1 %v1, label %b.latch, label %c.latch
 864 ; CHECK:       c.header:
 865 ; CHECK-NEXT:    br label %c.latch
 866
 867 c.latch:
 868   ; Use values from other loops to check LCSSA form.
 869   store i32 %x.a, i32* %ptr
 870   store i32 %x.b, i32* %ptr
 871   %v2 = call i1 @cond()
 872   br i1 %v2, label %c.header, label %a.exit.c
 873 ; CHECK:       c.latch:
 874 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
 875 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
 876 ; CHECK-NEXT:    %v2 = call i1 @cond()
 877 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
 878
 879 b.latch:
 880   %v3 = call i1 @cond()
 881   br i1 %v3, label %b.header, label %a.exit.b
 882 ; CHECK:       b.latch:
 883 ; CHECK-NEXT:    %v3 = call i1 @cond()
 884 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
 885
 886 a.exit.c:
 887   br label %a.latch
 888 ; CHECK:       a.exit.c
 889 ; CHECK-NEXT:    br label %a.latch
 890
 891 a.exit.b:
 892   br label %a.latch
 893 ; CHECK:       a.exit.b:
 894 ; CHECK-NEXT:    br label %a.latch
 895
 896 a.latch:
 897   br label %a.header
 898 ; CHECK:       a.latch:
 899 ; CHECK-NEXT:    br label %a.header
 900
 901 exit:
 902   ret void
 903 ; CHECK:       exit:
 904 ; CHECK-NEXT:    ret void
 905 }
 906
 907 ; Unswitch will transform the loop nest from:
 908 ;   A < B < C
 909 ; into
 910 ;   (A < B), C
 911 define void @hoist_inner_loop2(i32* %ptr) {
 912 ; CHECK-LABEL: define void @hoist_inner_loop2(
 913 entry:
 914   br label %a.header
 915 ; CHECK:       entry:
 916 ; CHECK-NEXT:    br label %a.header
 917
 918 a.header:
 919   %x.a = load i32, i32* %ptr
 920   br label %b.header
 921 ; CHECK:       a.header:
 922 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
 923 ; CHECK-NEXT:    br label %b.header
 924
 925 b.header:
 926   %x.b = load i32, i32* %ptr
 927   %v1 = call i1 @cond()
 928   br label %c.header
 929 ; CHECK:       b.header:
 930 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 931 ; CHECK-NEXT:    %v1 = call i1 @cond()
 932 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
 933 ;
 934 ; CHECK:       [[B_HEADER_SPLIT]]:
 935 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
 936 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
 937 ; CHECK-NEXT:    br label %c.header
 938
 939 c.header:
 940   br i1 %v1, label %b.latch, label %c.latch
 941 ; CHECK:       c.header:
 942 ; CHECK-NEXT:    br label %c.latch
 943
 944 c.latch:
 945   ; Use values from other loops to check LCSSA form.
 946   store i32 %x.a, i32* %ptr
 947   store i32 %x.b, i32* %ptr
 948   %v2 = call i1 @cond()
 949   br i1 %v2, label %c.header, label %exit
 950 ; CHECK:       c.latch:
 951 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
 952 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
 953 ; CHECK-NEXT:    %v2 = call i1 @cond()
 954 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
 955
 956 b.latch:
 957   %v3 = call i1 @cond()
 958   br i1 %v3, label %b.header, label %a.latch
 959 ; CHECK:       b.latch:
 960 ; CHECK-NEXT:    %v3 = call i1 @cond()
 961 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
 962
 963 a.latch:
 964   br label %a.header
 965 ; CHECK:       a.latch:
 966 ; CHECK-NEXT:    br label %a.header
 967
 968 exit:
 969   ret void
 970 ; CHECK:       exit:
 971 ; CHECK-NEXT:    ret void
 972 }
 973
 974 ; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
 975 ; Unswitch will transform the loop nest from:
 976 ;   A < B < C < D
 977 ; into
 978 ;   (A < B), (C < D)
 979 define void @hoist_inner_loop3(i32* %ptr) {
 980 ; CHECK-LABEL: define void @hoist_inner_loop3(
 981 entry:
 982   br label %a.header
 983 ; CHECK:       entry:
 984 ; CHECK-NEXT:    br label %a.header
 985
 986 a.header:
 987   %x.a = load i32, i32* %ptr
 988   br label %b.header
 989 ; CHECK:       a.header:
 990 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
 991 ; CHECK-NEXT:    br label %b.header
 992
 993 b.header:
 994   %x.b = load i32, i32* %ptr
 995   %v1 = call i1 @cond()
 996   br label %c.header
 997 ; CHECK:       b.header:
 998 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
 999 ; CHECK-NEXT:    %v1 = call i1 @cond()
1000 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
1001 ;
1002 ; CHECK:       [[B_HEADER_SPLIT]]:
1003 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
1004 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
1005 ; CHECK-NEXT:    br label %c.header
1006
1007 c.header:
1008   br i1 %v1, label %b.latch, label %c.body
1009 ; CHECK:       c.header:
1010 ; CHECK-NEXT:    br label %c.body
1011
1012 c.body:
1013   %x.c = load i32, i32* %ptr
1014   br label %d.header
1015 ; CHECK:       c.body:
1016 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
1017 ; CHECK-NEXT:    br label %d.header
1018
1019 d.header:
1020   ; Use values from other loops to check LCSSA form.
1021   store i32 %x.a, i32* %ptr
1022   store i32 %x.b, i32* %ptr
1023   store i32 %x.c, i32* %ptr
1024   %v2 = call i1 @cond()
1025   br i1 %v2, label %d.header, label %c.latch
1026 ; CHECK:       d.header:
1027 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
1028 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
1029 ; CHECK-NEXT:    store i32 %x.c, i32* %ptr
1030 ; CHECK-NEXT:    %v2 = call i1 @cond()
1031 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
1032
1033 c.latch:
1034   %v3 = call i1 @cond()
1035   br i1 %v3, label %c.header, label %exit
1036 ; CHECK:       c.latch:
1037 ; CHECK-NEXT:    %v3 = call i1 @cond()
1038 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
1039
1040 b.latch:
1041   %v4 = call i1 @cond()
1042   br i1 %v4, label %b.header, label %a.latch
1043 ; CHECK:       b.latch:
1044 ; CHECK-NEXT:    %v4 = call i1 @cond()
1045 ; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
1046
1047 a.latch:
1048   br label %a.header
1049 ; CHECK:       a.latch:
1050 ; CHECK-NEXT:    br label %a.header
1051
1052 exit:
1053   ret void
1054 ; CHECK:       exit:
1055 ; CHECK-NEXT:    ret void
1056 }
1057
1058 ; This test is designed to exercise checking multiple remaining exits from the
1059 ; loop being unswitched.
1060 ; Unswitch will transform the loop nest from:
1061 ;   A < B < C < D
1062 ; into
1063 ;   A < B < (C, D)
1064 define void @hoist_inner_loop4() {
1065 ; CHECK-LABEL: define void @hoist_inner_loop4(
1066 entry:
1067   br label %a.header
1068 ; CHECK:       entry:
1069 ; CHECK-NEXT:    br label %a.header
1070
1071 a.header:
1072   br label %b.header
1073 ; CHECK:       a.header:
1074 ; CHECK-NEXT:    br label %b.header
1075
1076 b.header:
1077   br label %c.header
1078 ; CHECK:       b.header:
1079 ; CHECK-NEXT:    br label %c.header
1080
1081 c.header:
1082   %v1 = call i1 @cond()
1083   br label %d.header
1084 ; CHECK:       c.header:
1085 ; CHECK-NEXT:    %v1 = call i1 @cond()
1086 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT:.*]], label %c.latch
1087 ;
1088 ; CHECK:       [[C_HEADER_SPLIT]]:
1089 ; CHECK-NEXT:    br label %d.header
1090
1091 d.header:
1092   br i1 %v1, label %d.exiting1, label %c.latch
1093 ; CHECK:       d.header:
1094 ; CHECK-NEXT:    br label %d.exiting1
1095
1096 d.exiting1:
1097   %v2 = call i1 @cond()
1098   br i1 %v2, label %d.exiting2, label %a.latch
1099 ; CHECK:       d.exiting1:
1100 ; CHECK-NEXT:    %v2 = call i1 @cond()
1101 ; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
1102
1103 d.exiting2:
1104   %v3 = call i1 @cond()
1105   br i1 %v3, label %d.exiting3, label %loopexit.d
1106 ; CHECK:       d.exiting2:
1107 ; CHECK-NEXT:    %v3 = call i1 @cond()
1108 ; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
1109
1110 d.exiting3:
1111   %v4 = call i1 @cond()
1112   br i1 %v4, label %d.latch, label %b.latch
1113 ; CHECK:       d.exiting3:
1114 ; CHECK-NEXT:    %v4 = call i1 @cond()
1115 ; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
1116
1117 d.latch:
1118   br label %d.header
1119 ; CHECK:       d.latch:
1120 ; CHECK-NEXT:    br label %d.header
1121
1122 c.latch:
1123   %v5 = call i1 @cond()
1124   br i1 %v5, label %c.header, label %loopexit.c
1125 ; CHECK:       c.latch:
1126 ; CHECK-NEXT:    %v5 = call i1 @cond()
1127 ; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
1128
1129 b.latch:
1130   br label %b.header
1131 ; CHECK:       b.latch:
1132 ; CHECK-NEXT:    br label %b.header
1133
1134 a.latch:
1135   br label %a.header
1136 ; CHECK:       a.latch:
1137 ; CHECK-NEXT:    br label %a.header
1138
1139 loopexit.d:
1140   br label %exit
1141 ; CHECK:       loopexit.d:
1142 ; CHECK-NEXT:    br label %exit
1143
1144 loopexit.c:
1145   br label %exit
1146 ; CHECK:       loopexit.c:
1147 ; CHECK-NEXT:    br label %exit
1148
1149 exit:
1150   ret void
1151 ; CHECK:       exit:
1152 ; CHECK-NEXT:    ret void
1153 }
1154
1155 ; Unswitch will transform the loop nest from:
1156 ;   A < B < C < D
1157 ; into
1158 ;   A < ((B < C), D)
1159 define void @hoist_inner_loop5(i32* %ptr) {
1160 ; CHECK-LABEL: define void @hoist_inner_loop5(
1161 entry:
1162   br label %a.header
1163 ; CHECK:       entry:
1164 ; CHECK-NEXT:    br label %a.header
1165
1166 a.header:
1167   %x.a = load i32, i32* %ptr
1168   br label %b.header
1169 ; CHECK:       a.header:
1170 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
1171 ; CHECK-NEXT:    br label %b.header
1172
1173 b.header:
1174   %x.b = load i32, i32* %ptr
1175   br label %c.header
1176 ; CHECK:       b.header:
1177 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
1178 ; CHECK-NEXT:    br label %c.header
1179
1180 c.header:
1181   %x.c = load i32, i32* %ptr
1182   %v1 = call i1 @cond()
1183   br label %d.header
1184 ; CHECK:       c.header:
1185 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
1186 ; CHECK-NEXT:    %v1 = call i1 @cond()
1187 ; CHECK-NEXT:    br i1 %v1, label %c.latch, label %[[C_HEADER_SPLIT:.*]]
1188 ;
1189 ; CHECK:       [[C_HEADER_SPLIT]]:
1190 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
1191 ; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
1192 ; CHECK-NEXT:    br label %d.header
1193
1194 d.header:
1195   br i1 %v1, label %c.latch, label %d.latch
1196 ; CHECK:       d.header:
1197 ; CHECK-NEXT:    br label %d.latch
1198
1199 d.latch:
1200   ; Use values from other loops to check LCSSA form.
1201   store i32 %x.a, i32* %ptr
1202   store i32 %x.b, i32* %ptr
1203   store i32 %x.c, i32* %ptr
1204   %v2 = call i1 @cond()
1205   br i1 %v2, label %d.header, label %a.latch
1206 ; CHECK:       d.latch:
1207 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
1208 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
1209 ; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
1210 ; CHECK-NEXT:    %v2 = call i1 @cond()
1211 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
1212
1213 c.latch:
1214   %v3 = call i1 @cond()
1215   br i1 %v3, label %c.header, label %b.latch
1216 ; CHECK:       c.latch:
1217 ; CHECK-NEXT:    %v3 = call i1 @cond()
1218 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
1219
1220 b.latch:
1221   br label %b.header
1222 ; CHECK:       b.latch:
1223 ; CHECK-NEXT:    br label %b.header
1224
1225 a.latch:
1226   br label %a.header
1227 ; CHECK:       a.latch:
1228 ; CHECK-NEXT:    br label %a.header
1229
1230 exit:
1231   ret void
1232 ; CHECK:       exit:
1233 ; CHECK-NEXT:    ret void
1234 }
1235
1236 ; Same as `@hoist_inner_loop2` but using a switch.
1237 ; Unswitch will transform the loop nest from:
1238 ;   A < B < C
1239 ; into
1240 ;   (A < B), C
1241 define void @hoist_inner_loop_switch(i32* %ptr) {
1242 ; CHECK-LABEL: define void @hoist_inner_loop_switch(
1243 entry:
1244   br label %a.header
1245 ; CHECK:       entry:
1246 ; CHECK-NEXT:    br label %a.header
1247
1248 a.header:
1249   %x.a = load i32, i32* %ptr
1250   br label %b.header
1251 ; CHECK:       a.header:
1252 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
1253 ; CHECK-NEXT:    br label %b.header
1254
1255 b.header:
1256   %x.b = load i32, i32* %ptr
1257   %v1 = call i32 @cond.i32()
1258   br label %c.header
1259 ; CHECK:       b.header:
1260 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
1261 ; CHECK-NEXT:    %v1 = call i32 @cond.i32()
1262 ; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
1263 ; CHECK-NEXT:      i32 1, label %b.latch
1264 ; CHECK-NEXT:      i32 2, label %b.latch
1265 ; CHECK-NEXT:      i32 3, label %b.latch
1266 ; CHECK-NEXT:    ]
1267 ;
1268 ; CHECK:       [[B_HEADER_SPLIT]]:
1269 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
1270 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
1271 ; CHECK-NEXT:    br label %c.header
1272
1273 c.header:
1274   switch i32 %v1, label %c.latch [
1275     i32 1, label %b.latch
1276     i32 2, label %b.latch
1277     i32 3, label %b.latch
1278   ]
1279 ; CHECK:       c.header:
1280 ; CHECK-NEXT:    br label %c.latch
1281
1282 c.latch:
1283   ; Use values from other loops to check LCSSA form.
1284   store i32 %x.a, i32* %ptr
1285   store i32 %x.b, i32* %ptr
1286   %v2 = call i1 @cond()
1287   br i1 %v2, label %c.header, label %exit
1288 ; CHECK:       c.latch:
1289 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
1290 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
1291 ; CHECK-NEXT:    %v2 = call i1 @cond()
1292 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
1293
1294 b.latch:
1295   %v3 = call i1 @cond()
1296   br i1 %v3, label %b.header, label %a.latch
1297 ; CHECK:       b.latch:
1298 ; CHECK-NEXT:    %v3 = call i1 @cond()
1299 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
1300
1301 a.latch:
1302   br label %a.header
1303 ; CHECK:       a.latch:
1304 ; CHECK-NEXT:    br label %a.header
1305
1306 exit:
1307   ret void
1308 ; CHECK:       exit:
1309 ; CHECK-NEXT:    ret void
1310 }
1311
1312 define void @test_unswitch_to_common_succ_with_phis(i32* %var, i32 %cond) {
1313 ; CHECK-LABEL: @test_unswitch_to_common_succ_with_phis(
1314 entry:
1315   br label %header
1316 ; CHECK-NEXT:  entry:
1317 ; CHECK-NEXT:    switch i32 %cond, label %loopexit1 [
1318 ; CHECK-NEXT:      i32 13, label %loopexit2
1319 ; CHECK-NEXT:      i32 0, label %entry.split
1320 ; CHECK-NEXT:      i32 1, label %entry.split
1321 ; CHECK-NEXT:    ]
1322 ;
1323 ; CHECK:       entry.split:
1324 ; CHECK-NEXT:    br label %header
1325
1326 header:
1327   %var_val = load i32, i32* %var
1328   switch i32 %cond, label %loopexit1 [
1329     i32 0, label %latch
1330     i32 1, label %latch
1331     i32 13, label %loopexit2
1332   ]
1333 ; CHECK:       header:
1334 ; CHECK-NEXT:    load
1335 ; CHECK-NEXT:    br label %latch
1336
1337 latch:
1338   ; No-op PHI node to exercise weird PHI update scenarios.
1339   %phi = phi i32 [ %var_val, %header ], [ %var_val, %header ]
1340   call void @sink(i32 %phi)
1341   br label %header
1342 ; CHECK:       latch:
1343 ; CHECK-NEXT:    %[[PHI:.*]] = phi i32 [ %var_val, %header ]
1344 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
1345 ; CHECK-NEXT:    br label %header
1346
1347 loopexit1:
1348   ret void
1349 ; CHECK:       loopexit1:
1350 ; CHECK-NEXT:    ret
1351
1352 loopexit2:
1353   ret void
1354 ; CHECK:       loopexit2:
1355 ; CHECK-NEXT:    ret
1356 }
1357
1358 define void @test_unswitch_to_default_common_succ_with_phis(i32* %var, i32 %cond) {
1359 ; CHECK-LABEL: @test_unswitch_to_default_common_succ_with_phis(
1360 entry:
1361   br label %header
1362 ; CHECK-NEXT:  entry:
1363 ; CHECK-NEXT:    switch i32 %cond, label %entry.split [
1364 ; CHECK-NEXT:      i32 13, label %loopexit
1365 ; CHECK-NEXT:    ]
1366 ;
1367 ; CHECK:       entry.split:
1368 ; CHECK-NEXT:    br label %header
1369
1370 header:
1371   %var_val = load i32, i32* %var
1372   switch i32 %cond, label %latch [
1373     i32 0, label %latch
1374     i32 1, label %latch
1375     i32 13, label %loopexit
1376   ]
1377 ; CHECK:       header:
1378 ; CHECK-NEXT:    load
1379 ; CHECK-NEXT:    br label %latch
1380
1381 latch:
1382   ; No-op PHI node to exercise weird PHI update scenarios.
1383   %phi = phi i32 [ %var_val, %header ], [ %var_val, %header ], [ %var_val, %header ]
1384   call void @sink(i32 %phi)
1385   br label %header
1386 ; CHECK:       latch:
1387 ; CHECK-NEXT:    %[[PHI:.*]] = phi i32 [ %var_val, %header ]
1388 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
1389 ; CHECK-NEXT:    br label %header
1390
1391 loopexit:
1392   ret void
1393 ; CHECK:       loopexit:
1394 ; CHECK-NEXT:    ret
1395 }
1396
1397 declare void @f()
1398 declare void @g()
1399 define void @test_unswitch_switch_with_nonempty_unreachable() {
1400 ; CHECK-LABEL: @test_unswitch_switch_with_nonempty_unreachable()
1401 entry:
1402   br label %loop
1403
1404 loop:
1405   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1406   br label %for.cond
1407
1408 for.cond:
1409   switch i32 %cleanup.dest.slot.0, label %NonEmptyUnreachableBlock [
1410     i32 0, label %for.cond
1411     i32 1, label %NonEmptyUnreachableBlock
1412     i32 2, label %loop.loopexit
1413   ]
1414
1415 loop.loopexit:
1416   unreachable
1417
1418 NonEmptyUnreachableBlock:
1419   call void @f()
1420   call void @g()
1421   unreachable
1422
1423 ; CHECK:loop:
1424 ; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1425 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %NonEmptyUnreachableBlock [
1426 ; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
1427 ; CHECK-NEXT:    i32 0, label %loop.split
1428 ; CHECK-NEXT:    i32 2, label %loop.split
1429 ; CHECK-NEXT:  ]
1430
1431 ; CHECK:loop.split:
1432 ; CHECK-NEXT:  br label %for.cond
1433
1434 ; CHECK:for.cond:
1435 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.loopexit [
1436 ; CHECK-NEXT:    i32 0, label %for.cond
1437 ; CHECK-NEXT:  ]
1438
1439 ; CHECK:loop.loopexit:
1440 ; CHECK-NEXT:  unreachable
1441
1442 ; CHECK:NonEmptyUnreachableBlock:
1443 ; CHECK-NEXT:  call void @f()
1444 ; CHECK-NEXT:  call void @g()
1445 ; CHECK-NEXT:  unreachable
1446 }
1447
1448 define void @test_unswitch_switch_with_nonempty_unreachable2() {
1449 ; CHECK-LABEL: @test_unswitch_switch_with_nonempty_unreachable2()
1450 entry:
1451   br label %loop
1452
1453 loop:
1454   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1455   br label %for.cond
1456
1457 for.cond:
1458   switch i32 %cleanup.dest.slot.0, label %for.cond [
1459     i32 0, label %for.cond
1460     i32 1, label %NonEmptyUnreachableBlock
1461     i32 2, label %loop.loopexit
1462   ]
1463
1464 loop.loopexit:
1465   unreachable
1466
1467 NonEmptyUnreachableBlock:
1468   call void @f()
1469   call void @g()
1470   unreachable
1471
1472 ; CHECK:loop:
1473 ; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1474 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.split [
1475 ; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
1476 ; CHECK-NEXT:  ]
1477
1478 ; CHECK:loop.split:
1479 ; CHECK-NEXT:  br label %for.cond
1480
1481 ; CHECK:for.cond:
1482 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %for.cond.backedge [
1483 ; CHECK-NEXT:    i32 0, label %for.cond.backedge
1484 ; CHECK-NEXT:    i32 2, label %loop.loopexit
1485 ; CHECK-NEXT:  ]
1486
1487 ; CHECK:for.cond.backedge:
1488 ; CHECK-NEXT:  br label %for.cond
1489
1490 ; CHECK:loop.loopexit:
1491 ; CHECK-NEXT:  unreachable
1492
1493 ; CHECK:NonEmptyUnreachableBlock:
1494 ; CHECK-NEXT:  call void @f()
1495 ; CHECK-NEXT:  call void @g()
1496 ; CHECK-NEXT:  unreachable
1497 }
1498
1499 ; PR45355
1500 define void @test_unswitch_switch_with_duplicate_edge() {
1501 ; CHECK-LABEL: @test_unswitch_switch_with_duplicate_edge()
1502 entry:
1503   br label %lbl1
1504
1505 lbl1:                                             ; preds = %entry
1506   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1507   br label %for.cond1
1508
1509 for.cond1:                                        ; preds = %for.cond1, %lbl1
1510   switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
1511     i32 0, label %for.cond1
1512     i32 5, label %UnifiedUnreachableBlock
1513     i32 2, label %lbl1.loopexit
1514   ]
1515
1516 UnifiedUnreachableBlock:                          ; preds = %for.cond1, %for.cond1
1517   unreachable
1518
1519 lbl1.loopexit:                                    ; preds = %for.cond1
1520   unreachable
1521
1522 ; CHECK: for.cond1:
1523 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
1524 ; CHECK-NEXT:    i32 0, label %for.cond1
1525 ; CHECK-NEXT:    i32 5, label %UnifiedUnreachableBlock
1526 ; CHECK-NEXT:    i32 2, label %lbl1.loopexit
1527 ; CHECK-NEXT:  ]
1528 }