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(ptr %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, ptr %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(ptr %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, ptr %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(ptr %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, ptr %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(ptr %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, ptr %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(ptr %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, ptr %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, ptr %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, ptr %cond2.ptr
 417   br i1 %cond2, label %if.then23, label %if.else
 418 ; CHECK:       if.then20:
 419 ; CHECK-NEXT:    %[[COND2:.*]] = load volatile i1, ptr %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(ptr %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:    [[FROZEN:%.+]] = freeze i1 %cond2
 457 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.split, label %loop_exit
 458 ;
 459 ; CHECK:       entry.split.split:
 460 ; CHECK-NEXT:    br label %loop_begin
 461
 462 loop_begin:
 463   br i1 %cond1, label %continue, label %loop_exit
 464 ; CHECK:       loop_begin:
 465 ; CHECK-NEXT:    br label %continue
 466
 467 continue:
 468   %var_val = load i32, ptr %var
 469   %var_cond = trunc i32 %var_val to i1
 470   %cond_and = and i1 %var_cond, %cond2
 471   br i1 %cond_and, label %do_something, label %loop_exit
 472 ; CHECK:       continue:
 473 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 474 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 475 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 476 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 477
 478 do_something:
 479   call void @some_func() noreturn nounwind
 480   br label %loop_begin
 481 ; CHECK:       do_something:
 482 ; CHECK-NEXT:    call
 483 ; CHECK-NEXT:    br label %loop_begin
 484
 485 loop_exit:
 486   ret i32 0
 487 ; CHECK:       loop_exit:
 488 ; CHECK-NEXT:    br label %loop_exit.split
 489 ;
 490 ; CHECK:       loop_exit.split:
 491 ; CHECK-NEXT:    ret
 492 }
 493
 494 define i32 @test_partial_condition_unswitch_and_select(ptr %var, i1 %cond1, i1 %cond2) {
 495 ; CHECK-LABEL: @test_partial_condition_unswitch_and_select(
 496 entry:
 497   br label %loop_begin
 498 ; CHECK-NEXT:  entry:
 499 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 500 ;
 501 ; CHECK:       entry.split:
 502 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond2
 503 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.split, label %loop_exit
 504 ;
 505 ; CHECK:       entry.split.split:
 506 ; CHECK-NEXT:    br label %loop_begin
 507
 508 loop_begin:
 509   br i1 %cond1, label %continue, label %loop_exit
 510 ; CHECK:       loop_begin:
 511 ; CHECK-NEXT:    br label %continue
 512
 513 continue:
 514   %var_val = load i32, ptr %var
 515   %var_cond = trunc i32 %var_val to i1
 516   %cond_and = select i1 %var_cond, i1 %cond2, i1 false
 517   br i1 %cond_and, label %do_something, label %loop_exit
 518 ; CHECK:       continue:
 519 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 520 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 521 ; CHECK-NEXT:    %[[COND_AND:.*]] = select i1 %[[VAR_COND]], i1 true, i1 false
 522 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 523
 524 do_something:
 525   call void @some_func() noreturn nounwind
 526   br label %loop_begin
 527 ; CHECK:       do_something:
 528 ; CHECK-NEXT:    call
 529 ; CHECK-NEXT:    br label %loop_begin
 530
 531 loop_exit:
 532   ret i32 0
 533 ; CHECK:       loop_exit:
 534 ; CHECK-NEXT:    br label %loop_exit.split
 535 ;
 536 ; CHECK:       loop_exit.split:
 537 ; CHECK-NEXT:    ret
 538 }
 539
 540 define i32 @test_partial_condition_unswitch_or_simple_select(ptr %var, i1 %cond1, i1 %cond2) {
 541 ; CHECK-LABEL: @test_partial_condition_unswitch_or_simple_select(
 542 entry:
 543   br label %loop_begin
 544 ; CHECK-NEXT:  entry:
 545 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 546 ;
 547 ; CHECK:       entry.split:
 548 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond2
 549 ; CHECK-NEXT:    br i1 [[FROZEN]], label %loop_exit.split1, label %entry.split.split
 550 ;
 551 ; CHECK:       entry.split.split:
 552 ; CHECK-NEXT:    br label %loop_begin
 553
 554 loop_begin:
 555   br i1 %cond1, label %continue, label %loop_exit
 556 ; CHECK:       loop_begin:
 557 ; CHECK-NEXT:    br label %continue
 558
 559 continue:
 560   %var_val = load i32, ptr %var
 561   %var_cond = trunc i32 %var_val to i1
 562   %cond_or = select i1 %var_cond, i1 true, i1 %cond2
 563   br i1 %cond_or, label %loop_exit, label %do_something
 564 ; CHECK:       continue:
 565 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 566 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 567 ; CHECK-NEXT:    %[[COND_OR:.*]] = select i1 %[[VAR_COND]], i1 true, i1 false
 568 ; CHECK-NEXT:    br i1 %[[COND_OR]], label %loop_exit, label %do_something
 569
 570 do_something:
 571   call void @some_func() noreturn nounwind
 572   br label %loop_begin
 573 ; CHECK:       do_something:
 574 ; CHECK-NEXT:    call
 575 ; CHECK-NEXT:    br label %loop_begin
 576
 577 loop_exit:
 578   ret i32 0
 579 ; CHECK:       loop_exit:
 580 ; CHECK-NEXT:    br label %loop_exit.split1
 581 ;
 582 ; CHECK:       loop_exit.split1:
 583 ; CHECK-NEXT:    br label %loop_exit.split
 584 ;
 585 ; CHECK:       loop_exit.split:
 586 ; CHECK-NEXT:    ret
 587 }
 588
 589 define i32 @test_partial_condition_unswitch_or(ptr %var, i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4, i1 %cond5, i1 %cond6) {
 590 ; CHECK-LABEL: @test_partial_condition_unswitch_or(
 591 entry:
 592   br label %loop_begin
 593 ; CHECK-NEXT:  entry:
 594 ; CHECK-NEXT:    %[[C4_FR:.+]] = freeze i1 %cond4
 595 ; CHECK-NEXT:    %[[C2_FR:.+]] = freeze i1 %cond2
 596 ; CHECK-NEXT:    %[[C3_FR:.+]] = freeze i1 %cond3
 597 ; CHECK-NEXT:    %[[C1_FR:.+]] = freeze i1 %cond1
 598 ; CHECK-NEXT:    %[[INV_OR1:.*]] = or i1 %[[C4_FR]], %[[C2_FR]]
 599 ; CHECK-NEXT:    %[[INV_OR2:.*]] = or i1 %[[INV_OR1]], %[[C3_FR]]
 600 ; CHECK-NEXT:    %[[INV_OR3:.*]] = or i1 %[[INV_OR2]], %[[C1_FR]]
 601 ; CHECK-NEXT:    br i1 %[[INV_OR3]], label %loop_exit.split, label %entry.split
 602 ;
 603 ; CHECK:       entry.split:
 604 ; CHECK-NEXT:    br label %loop_begin
 605
 606 loop_begin:
 607   %var_val = load i32, ptr %var
 608   %var_cond = trunc i32 %var_val to i1
 609   %cond_or1 = or i1 %var_cond, %cond1
 610   %cond_or2 = or i1 %cond2, %cond3
 611   %cond_or3 = or i1 %cond_or1, %cond_or2
 612   %cond_xor1 = xor i1 %cond5, %var_cond
 613   %cond_and1 = and i1 %cond6, %var_cond
 614   %cond_or4 = or i1 %cond_xor1, %cond_and1
 615   %cond_or5 = or i1 %cond_or3, %cond_or4
 616   %cond_or6 = or i1 %cond_or5, %cond4
 617   br i1 %cond_or6, label %loop_exit, label %do_something
 618 ; CHECK:       loop_begin:
 619 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 620 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 621 ; CHECK-NEXT:    %[[COND_OR1:.*]] = or i1 %[[VAR_COND]], false
 622 ; CHECK-NEXT:    %[[COND_OR2:.*]] = or i1 false, false
 623 ; CHECK-NEXT:    %[[COND_OR3:.*]] = or i1 %[[COND_OR1]], %[[COND_OR2]]
 624 ; CHECK-NEXT:    %[[COND_XOR:.*]] = xor i1 %cond5, %[[VAR_COND]]
 625 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %cond6, %[[VAR_COND]]
 626 ; CHECK-NEXT:    %[[COND_OR4:.*]] = or i1 %[[COND_XOR]], %[[COND_AND]]
 627 ; CHECK-NEXT:    %[[COND_OR5:.*]] = or i1 %[[COND_OR3]], %[[COND_OR4]]
 628 ; CHECK-NEXT:    %[[COND_OR6:.*]] = or i1 %[[COND_OR5]], false
 629 ; CHECK-NEXT:    br i1 %[[COND_OR6]], label %loop_exit, label %do_something
 630
 631 do_something:
 632   call void @some_func() noreturn nounwind
 633   br label %loop_begin
 634 ; CHECK:       do_something:
 635 ; CHECK-NEXT:    call
 636 ; CHECK-NEXT:    br label %loop_begin
 637
 638 loop_exit:
 639   ret i32 0
 640 ; CHECK:       loop_exit.split:
 641 ; CHECK-NEXT:    ret
 642 }
 643
 644 define i32 @test_partial_condition_unswitch_with_lcssa_phi1(ptr %var, i1 %cond, i32 %x) {
 645 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi1(
 646 entry:
 647   br label %loop_begin
 648 ; CHECK-NEXT:  entry:
 649 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 650 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split, label %loop_exit.split
 651 ;
 652 ; CHECK:       entry.split:
 653 ; CHECK-NEXT:    br label %loop_begin
 654
 655 loop_begin:
 656   %var_val = load i32, ptr %var
 657   %var_cond = trunc i32 %var_val to i1
 658   %cond_and = and i1 %var_cond, %cond
 659   br i1 %cond_and, label %do_something, label %loop_exit
 660 ; CHECK:       loop_begin:
 661 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 662 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 663 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 664 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 665
 666 do_something:
 667   call void @some_func() noreturn nounwind
 668   br label %loop_begin
 669 ; CHECK:       do_something:
 670 ; CHECK-NEXT:    call
 671 ; CHECK-NEXT:    br label %loop_begin
 672
 673 loop_exit:
 674   %x.lcssa = phi i32 [ %x, %loop_begin ]
 675   ret i32 %x.lcssa
 676 ; CHECK:       loop_exit:
 677 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %x, %loop_begin ]
 678 ; CHECK-NEXT:    br label %loop_exit.split
 679 ;
 680 ; CHECK:       loop_exit.split:
 681 ; CHECK-NEXT:    %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ]
 682 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 683 }
 684
 685 define i32 @test_partial_condition_unswitch_with_lcssa_phi2(ptr %var, i1 %cond, i32 %x, i32 %y) {
 686 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi2(
 687 entry:
 688   br label %loop_begin
 689 ; CHECK-NEXT:  entry:
 690 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 691 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split, label %loop_exit.split
 692 ;
 693 ; CHECK:       entry.split:
 694 ; CHECK-NEXT:    br label %loop_begin
 695
 696 loop_begin:
 697   %var_val = load i32, ptr %var
 698   %var_cond = trunc i32 %var_val to i1
 699   %cond_and = and i1 %var_cond, %cond
 700   br i1 %cond_and, label %do_something, label %loop_exit
 701 ; CHECK:       loop_begin:
 702 ; CHECK-NEXT:    %[[VAR:.*]] = load i32
 703 ; CHECK-NEXT:    %[[VAR_COND:.*]] = trunc i32 %[[VAR]] to i1
 704 ; CHECK-NEXT:    %[[COND_AND:.*]] = and i1 %[[VAR_COND]], true
 705 ; CHECK-NEXT:    br i1 %[[COND_AND]], label %do_something, label %loop_exit
 706
 707 do_something:
 708   call void @some_func() noreturn nounwind
 709   br i1 %var_cond, label %loop_begin, label %loop_exit
 710 ; CHECK:       do_something:
 711 ; CHECK-NEXT:    call
 712 ; CHECK-NEXT:    br i1 %[[VAR_COND]], label %loop_begin, label %loop_exit
 713
 714 loop_exit:
 715   %xy.lcssa = phi i32 [ %x, %loop_begin ], [ %y, %do_something ]
 716   ret i32 %xy.lcssa
 717 ; CHECK:       loop_exit:
 718 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %x, %loop_begin ], [ %y, %do_something ]
 719 ; CHECK-NEXT:    br label %loop_exit.split
 720 ;
 721 ; CHECK:       loop_exit.split:
 722 ; CHECK-NEXT:    %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ]
 723 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 724 }
 725
 726 ; Unswitch will not actually change the loop nest from:
 727 ;   A < B < C
 728 define void @hoist_inner_loop0() {
 729 ; CHECK-LABEL: define void @hoist_inner_loop0(
 730 entry:
 731   br label %a.header
 732 ; CHECK:       entry:
 733 ; CHECK-NEXT:    br label %a.header
 734
 735 a.header:
 736   br label %b.header
 737 ; CHECK:       a.header:
 738 ; CHECK-NEXT:    br label %b.header
 739
 740 b.header:
 741   %v1 = call i1 @cond()
 742   br label %c.header
 743 ; CHECK:       b.header:
 744 ; CHECK-NEXT:    %v1 = call i1 @cond()
 745 ; CHECK-NEXT:    br i1 %v1, label %[[B_LATCH_SPLIT:.*]], label %[[B_HEADER_SPLIT:.*]]
 746 ;
 747 ; CHECK:       [[B_HEADER_SPLIT]]:
 748 ; CHECK-NEXT:    br label %c.header
 749
 750 c.header:
 751   br i1 %v1, label %b.latch, label %c.latch
 752 ; CHECK:       c.header:
 753 ; CHECK-NEXT:    br label %c.latch
 754
 755 c.latch:
 756   %v2 = call i1 @cond()
 757   br i1 %v2, label %c.header, label %b.latch
 758 ; CHECK:       c.latch:
 759 ; CHECK-NEXT:    %v2 = call i1 @cond()
 760 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %b.latch
 761
 762 b.latch:
 763   %v3 = call i1 @cond()
 764   br i1 %v3, label %b.header, label %a.latch
 765 ; CHECK:       b.latch:
 766 ; CHECK-NEXT:    br label %[[B_LATCH_SPLIT]]
 767 ;
 768 ; CHECK:       [[B_LATCH_SPLIT]]:
 769 ; CHECK-NEXT:    %v3 = call i1 @cond()
 770 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
 771
 772 a.latch:
 773   br label %a.header
 774 ; CHECK:       a.latch:
 775 ; CHECK-NEXT:    br label %a.header
 776
 777 exit:
 778   ret void
 779 ; CHECK:       exit:
 780 ; CHECK-NEXT:    ret void
 781 }
 782
 783 ; Unswitch will transform the loop nest from:
 784 ;   A < B < C
 785 ; into
 786 ;   A < (B, C)
 787 define void @hoist_inner_loop1(ptr %ptr) {
 788 ; CHECK-LABEL: define void @hoist_inner_loop1(
 789 entry:
 790   br label %a.header
 791 ; CHECK:       entry:
 792 ; CHECK-NEXT:    br label %a.header
 793
 794 a.header:
 795   %x.a = load i32, ptr %ptr
 796   br label %b.header
 797 ; CHECK:       a.header:
 798 ; CHECK-NEXT:    %x.a = load i32, ptr %ptr
 799 ; CHECK-NEXT:    br label %b.header
 800
 801 b.header:
 802   %x.b = load i32, ptr %ptr
 803   %v1 = call i1 @cond()
 804   br label %c.header
 805 ; CHECK:       b.header:
 806 ; CHECK-NEXT:    %x.b = load i32, ptr %ptr
 807 ; CHECK-NEXT:    %v1 = call i1 @cond()
 808 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
 809 ;
 810 ; CHECK:       [[B_HEADER_SPLIT]]:
 811 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
 812 ; CHECK-NEXT:    br label %c.header
 813
 814 c.header:
 815   br i1 %v1, label %b.latch, label %c.latch
 816 ; CHECK:       c.header:
 817 ; CHECK-NEXT:    br label %c.latch
 818
 819 c.latch:
 820   ; Use values from other loops to check LCSSA form.
 821   store i32 %x.a, ptr %ptr
 822   store i32 %x.b, ptr %ptr
 823   %v2 = call i1 @cond()
 824   br i1 %v2, label %c.header, label %a.exit.c
 825 ; CHECK:       c.latch:
 826 ; CHECK-NEXT:    store i32 %x.a, ptr %ptr
 827 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], ptr %ptr
 828 ; CHECK-NEXT:    %v2 = call i1 @cond()
 829 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
 830
 831 b.latch:
 832   %v3 = call i1 @cond()
 833   br i1 %v3, label %b.header, label %a.exit.b
 834 ; CHECK:       b.latch:
 835 ; CHECK-NEXT:    %v3 = call i1 @cond()
 836 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
 837
 838 a.exit.c:
 839   br label %a.latch
 840 ; CHECK:       a.exit.c
 841 ; CHECK-NEXT:    br label %a.latch
 842
 843 a.exit.b:
 844   br label %a.latch
 845 ; CHECK:       a.exit.b:
 846 ; CHECK-NEXT:    br label %a.latch
 847
 848 a.latch:
 849   br label %a.header
 850 ; CHECK:       a.latch:
 851 ; CHECK-NEXT:    br label %a.header
 852
 853 exit:
 854   ret void
 855 ; CHECK:       exit:
 856 ; CHECK-NEXT:    ret void
 857 }
 858
 859 ; Unswitch will transform the loop nest from:
 860 ;   A < B < C
 861 ; into
 862 ;   (A < B), C
 863 define void @hoist_inner_loop2(ptr %ptr) {
 864 ; CHECK-LABEL: define void @hoist_inner_loop2(
 865 entry:
 866   br label %a.header
 867 ; CHECK:       entry:
 868 ; CHECK-NEXT:    br label %a.header
 869
 870 a.header:
 871   %x.a = load i32, ptr %ptr
 872   br label %b.header
 873 ; CHECK:       a.header:
 874 ; CHECK-NEXT:    %x.a = load i32, ptr %ptr
 875 ; CHECK-NEXT:    br label %b.header
 876
 877 b.header:
 878   %x.b = load i32, ptr %ptr
 879   %v1 = call i1 @cond()
 880   br label %c.header
 881 ; CHECK:       b.header:
 882 ; CHECK-NEXT:    %x.b = load i32, ptr %ptr
 883 ; CHECK-NEXT:    %v1 = call i1 @cond()
 884 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
 885 ;
 886 ; CHECK:       [[B_HEADER_SPLIT]]:
 887 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
 888 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
 889 ; CHECK-NEXT:    br label %c.header
 890
 891 c.header:
 892   br i1 %v1, label %b.latch, label %c.latch
 893 ; CHECK:       c.header:
 894 ; CHECK-NEXT:    br label %c.latch
 895
 896 c.latch:
 897   ; Use values from other loops to check LCSSA form.
 898   store i32 %x.a, ptr %ptr
 899   store i32 %x.b, ptr %ptr
 900   %v2 = call i1 @cond()
 901   br i1 %v2, label %c.header, label %exit
 902 ; CHECK:       c.latch:
 903 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], ptr %ptr
 904 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], ptr %ptr
 905 ; CHECK-NEXT:    %v2 = call i1 @cond()
 906 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
 907
 908 b.latch:
 909   %v3 = call i1 @cond()
 910   br i1 %v3, label %b.header, label %a.latch
 911 ; CHECK:       b.latch:
 912 ; CHECK-NEXT:    %v3 = call i1 @cond()
 913 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
 914
 915 a.latch:
 916   br label %a.header
 917 ; CHECK:       a.latch:
 918 ; CHECK-NEXT:    br label %a.header
 919
 920 exit:
 921   ret void
 922 ; CHECK:       exit:
 923 ; CHECK-NEXT:    ret void
 924 }
 925
 926 ; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
 927 ; Unswitch will transform the loop nest from:
 928 ;   A < B < C < D
 929 ; into
 930 ;   (A < B), (C < D)
 931 define void @hoist_inner_loop3(ptr %ptr) {
 932 ; CHECK-LABEL: define void @hoist_inner_loop3(
 933 entry:
 934   br label %a.header
 935 ; CHECK:       entry:
 936 ; CHECK-NEXT:    br label %a.header
 937
 938 a.header:
 939   %x.a = load i32, ptr %ptr
 940   br label %b.header
 941 ; CHECK:       a.header:
 942 ; CHECK-NEXT:    %x.a = load i32, ptr %ptr
 943 ; CHECK-NEXT:    br label %b.header
 944
 945 b.header:
 946   %x.b = load i32, ptr %ptr
 947   %v1 = call i1 @cond()
 948   br label %c.header
 949 ; CHECK:       b.header:
 950 ; CHECK-NEXT:    %x.b = load i32, ptr %ptr
 951 ; CHECK-NEXT:    %v1 = call i1 @cond()
 952 ; CHECK-NEXT:    br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]]
 953 ;
 954 ; CHECK:       [[B_HEADER_SPLIT]]:
 955 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
 956 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
 957 ; CHECK-NEXT:    br label %c.header
 958
 959 c.header:
 960   br i1 %v1, label %b.latch, label %c.body
 961 ; CHECK:       c.header:
 962 ; CHECK-NEXT:    br label %c.body
 963
 964 c.body:
 965   %x.c = load i32, ptr %ptr
 966   br label %d.header
 967 ; CHECK:       c.body:
 968 ; CHECK-NEXT:    %x.c = load i32, ptr %ptr
 969 ; CHECK-NEXT:    br label %d.header
 970
 971 d.header:
 972   ; Use values from other loops to check LCSSA form.
 973   store i32 %x.a, ptr %ptr
 974   store i32 %x.b, ptr %ptr
 975   store i32 %x.c, ptr %ptr
 976   %v2 = call i1 @cond()
 977   br i1 %v2, label %d.header, label %c.latch
 978 ; CHECK:       d.header:
 979 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], ptr %ptr
 980 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], ptr %ptr
 981 ; CHECK-NEXT:    store i32 %x.c, ptr %ptr
 982 ; CHECK-NEXT:    %v2 = call i1 @cond()
 983 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
 984
 985 c.latch:
 986   %v3 = call i1 @cond()
 987   br i1 %v3, label %c.header, label %exit
 988 ; CHECK:       c.latch:
 989 ; CHECK-NEXT:    %v3 = call i1 @cond()
 990 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
 991
 992 b.latch:
 993   %v4 = call i1 @cond()
 994   br i1 %v4, label %b.header, label %a.latch
 995 ; CHECK:       b.latch:
 996 ; CHECK-NEXT:    %v4 = call i1 @cond()
 997 ; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
 998
 999 a.latch:
1000   br label %a.header
1001 ; CHECK:       a.latch:
1002 ; CHECK-NEXT:    br label %a.header
1003
1004 exit:
1005   ret void
1006 ; CHECK:       exit:
1007 ; CHECK-NEXT:    ret void
1008 }
1009
1010 ; This test is designed to exercise checking multiple remaining exits from the
1011 ; loop being unswitched.
1012 ; Unswitch will transform the loop nest from:
1013 ;   A < B < C < D
1014 ; into
1015 ;   A < B < (C, D)
1016 define void @hoist_inner_loop4() {
1017 ; CHECK-LABEL: define void @hoist_inner_loop4(
1018 entry:
1019   br label %a.header
1020 ; CHECK:       entry:
1021 ; CHECK-NEXT:    br label %a.header
1022
1023 a.header:
1024   br label %b.header
1025 ; CHECK:       a.header:
1026 ; CHECK-NEXT:    br label %b.header
1027
1028 b.header:
1029   br label %c.header
1030 ; CHECK:       b.header:
1031 ; CHECK-NEXT:    br label %c.header
1032
1033 c.header:
1034   %v1 = call i1 @cond()
1035   br label %d.header
1036 ; CHECK:       c.header:
1037 ; CHECK-NEXT:    %v1 = call i1 @cond()
1038 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT:.*]], label %c.latch
1039 ;
1040 ; CHECK:       [[C_HEADER_SPLIT]]:
1041 ; CHECK-NEXT:    br label %d.header
1042
1043 d.header:
1044   br i1 %v1, label %d.exiting1, label %c.latch
1045 ; CHECK:       d.header:
1046 ; CHECK-NEXT:    br label %d.exiting1
1047
1048 d.exiting1:
1049   %v2 = call i1 @cond()
1050   br i1 %v2, label %d.exiting2, label %a.latch
1051 ; CHECK:       d.exiting1:
1052 ; CHECK-NEXT:    %v2 = call i1 @cond()
1053 ; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
1054
1055 d.exiting2:
1056   %v3 = call i1 @cond()
1057   br i1 %v3, label %d.exiting3, label %loopexit.d
1058 ; CHECK:       d.exiting2:
1059 ; CHECK-NEXT:    %v3 = call i1 @cond()
1060 ; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
1061
1062 d.exiting3:
1063   %v4 = call i1 @cond()
1064   br i1 %v4, label %d.latch, label %b.latch
1065 ; CHECK:       d.exiting3:
1066 ; CHECK-NEXT:    %v4 = call i1 @cond()
1067 ; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
1068
1069 d.latch:
1070   br label %d.header
1071 ; CHECK:       d.latch:
1072 ; CHECK-NEXT:    br label %d.header
1073
1074 c.latch:
1075   %v5 = call i1 @cond()
1076   br i1 %v5, label %c.header, label %loopexit.c
1077 ; CHECK:       c.latch:
1078 ; CHECK-NEXT:    %v5 = call i1 @cond()
1079 ; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
1080
1081 b.latch:
1082   br label %b.header
1083 ; CHECK:       b.latch:
1084 ; CHECK-NEXT:    br label %b.header
1085
1086 a.latch:
1087   br label %a.header
1088 ; CHECK:       a.latch:
1089 ; CHECK-NEXT:    br label %a.header
1090
1091 loopexit.d:
1092   br label %exit
1093 ; CHECK:       loopexit.d:
1094 ; CHECK-NEXT:    br label %exit
1095
1096 loopexit.c:
1097   br label %exit
1098 ; CHECK:       loopexit.c:
1099 ; CHECK-NEXT:    br label %exit
1100
1101 exit:
1102   ret void
1103 ; CHECK:       exit:
1104 ; CHECK-NEXT:    ret void
1105 }
1106
1107 ; Unswitch will transform the loop nest from:
1108 ;   A < B < C < D
1109 ; into
1110 ;   A < ((B < C), D)
1111 define void @hoist_inner_loop5(ptr %ptr) {
1112 ; CHECK-LABEL: define void @hoist_inner_loop5(
1113 entry:
1114   br label %a.header
1115 ; CHECK:       entry:
1116 ; CHECK-NEXT:    br label %a.header
1117
1118 a.header:
1119   %x.a = load i32, ptr %ptr
1120   br label %b.header
1121 ; CHECK:       a.header:
1122 ; CHECK-NEXT:    %x.a = load i32, ptr %ptr
1123 ; CHECK-NEXT:    br label %b.header
1124
1125 b.header:
1126   %x.b = load i32, ptr %ptr
1127   br label %c.header
1128 ; CHECK:       b.header:
1129 ; CHECK-NEXT:    %x.b = load i32, ptr %ptr
1130 ; CHECK-NEXT:    br label %c.header
1131
1132 c.header:
1133   %x.c = load i32, ptr %ptr
1134   %v1 = call i1 @cond()
1135   br label %d.header
1136 ; CHECK:       c.header:
1137 ; CHECK-NEXT:    %x.c = load i32, ptr %ptr
1138 ; CHECK-NEXT:    %v1 = call i1 @cond()
1139 ; CHECK-NEXT:    br i1 %v1, label %c.latch, label %[[C_HEADER_SPLIT:.*]]
1140 ;
1141 ; CHECK:       [[C_HEADER_SPLIT]]:
1142 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
1143 ; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
1144 ; CHECK-NEXT:    br label %d.header
1145
1146 d.header:
1147   br i1 %v1, label %c.latch, label %d.latch
1148 ; CHECK:       d.header:
1149 ; CHECK-NEXT:    br label %d.latch
1150
1151 d.latch:
1152   ; Use values from other loops to check LCSSA form.
1153   store i32 %x.a, ptr %ptr
1154   store i32 %x.b, ptr %ptr
1155   store i32 %x.c, ptr %ptr
1156   %v2 = call i1 @cond()
1157   br i1 %v2, label %d.header, label %a.latch
1158 ; CHECK:       d.latch:
1159 ; CHECK-NEXT:    store i32 %x.a, ptr %ptr
1160 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], ptr %ptr
1161 ; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], ptr %ptr
1162 ; CHECK-NEXT:    %v2 = call i1 @cond()
1163 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
1164
1165 c.latch:
1166   %v3 = call i1 @cond()
1167   br i1 %v3, label %c.header, label %b.latch
1168 ; CHECK:       c.latch:
1169 ; CHECK-NEXT:    %v3 = call i1 @cond()
1170 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
1171
1172 b.latch:
1173   br label %b.header
1174 ; CHECK:       b.latch:
1175 ; CHECK-NEXT:    br label %b.header
1176
1177 a.latch:
1178   br label %a.header
1179 ; CHECK:       a.latch:
1180 ; CHECK-NEXT:    br label %a.header
1181
1182 exit:
1183   ret void
1184 ; CHECK:       exit:
1185 ; CHECK-NEXT:    ret void
1186 }
1187
1188 ; Same as `@hoist_inner_loop2` but using a switch.
1189 ; Unswitch will transform the loop nest from:
1190 ;   A < B < C
1191 ; into
1192 ;   (A < B), C
1193 define void @hoist_inner_loop_switch(ptr %ptr) {
1194 ; CHECK-LABEL: define void @hoist_inner_loop_switch(
1195 entry:
1196   br label %a.header
1197 ; CHECK:       entry:
1198 ; CHECK-NEXT:    br label %a.header
1199
1200 a.header:
1201   %x.a = load i32, ptr %ptr
1202   br label %b.header
1203 ; CHECK:       a.header:
1204 ; CHECK-NEXT:    %x.a = load i32, ptr %ptr
1205 ; CHECK-NEXT:    br label %b.header
1206
1207 b.header:
1208   %x.b = load i32, ptr %ptr
1209   %v1 = call i32 @cond.i32()
1210   br label %c.header
1211 ; CHECK:       b.header:
1212 ; CHECK-NEXT:    %x.b = load i32, ptr %ptr
1213 ; CHECK-NEXT:    %v1 = call i32 @cond.i32()
1214 ; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
1215 ; CHECK-NEXT:      i32 1, label %b.latch
1216 ; CHECK-NEXT:      i32 2, label %b.latch
1217 ; CHECK-NEXT:      i32 3, label %b.latch
1218 ; CHECK-NEXT:    ]
1219 ;
1220 ; CHECK:       [[B_HEADER_SPLIT]]:
1221 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
1222 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
1223 ; CHECK-NEXT:    br label %c.header
1224
1225 c.header:
1226   switch i32 %v1, label %c.latch [
1227     i32 1, label %b.latch
1228     i32 2, label %b.latch
1229     i32 3, label %b.latch
1230   ]
1231 ; CHECK:       c.header:
1232 ; CHECK-NEXT:    br label %c.latch
1233
1234 c.latch:
1235   ; Use values from other loops to check LCSSA form.
1236   store i32 %x.a, ptr %ptr
1237   store i32 %x.b, ptr %ptr
1238   %v2 = call i1 @cond()
1239   br i1 %v2, label %c.header, label %exit
1240 ; CHECK:       c.latch:
1241 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], ptr %ptr
1242 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], ptr %ptr
1243 ; CHECK-NEXT:    %v2 = call i1 @cond()
1244 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
1245
1246 b.latch:
1247   %v3 = call i1 @cond()
1248   br i1 %v3, label %b.header, label %a.latch
1249 ; CHECK:       b.latch:
1250 ; CHECK-NEXT:    %v3 = call i1 @cond()
1251 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
1252
1253 a.latch:
1254   br label %a.header
1255 ; CHECK:       a.latch:
1256 ; CHECK-NEXT:    br label %a.header
1257
1258 exit:
1259   ret void
1260 ; CHECK:       exit:
1261 ; CHECK-NEXT:    ret void
1262 }
1263
1264 define void @test_unswitch_to_common_succ_with_phis(ptr %var, i32 %cond) {
1265 ; CHECK-LABEL: @test_unswitch_to_common_succ_with_phis(
1266 entry:
1267   br label %header
1268 ; CHECK-NEXT:  entry:
1269 ; CHECK-NEXT:    switch i32 %cond, label %loopexit1 [
1270 ; CHECK-NEXT:      i32 13, label %loopexit2
1271 ; CHECK-NEXT:      i32 0, label %entry.split
1272 ; CHECK-NEXT:      i32 1, label %entry.split
1273 ; CHECK-NEXT:    ]
1274 ;
1275 ; CHECK:       entry.split:
1276 ; CHECK-NEXT:    br label %header
1277
1278 header:
1279   %var_val = load i32, ptr %var
1280   switch i32 %cond, label %loopexit1 [
1281     i32 0, label %latch
1282     i32 1, label %latch
1283     i32 13, label %loopexit2
1284   ]
1285 ; CHECK:       header:
1286 ; CHECK-NEXT:    load
1287 ; CHECK-NEXT:    br label %latch
1288
1289 latch:
1290   ; No-op PHI node to exercise weird PHI update scenarios.
1291   %phi = phi i32 [ %var_val, %header ], [ %var_val, %header ]
1292   call void @sink(i32 %phi)
1293   br label %header
1294 ; CHECK:       latch:
1295 ; CHECK-NEXT:    %[[PHI:.*]] = phi i32 [ %var_val, %header ]
1296 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
1297 ; CHECK-NEXT:    br label %header
1298
1299 loopexit1:
1300   ret void
1301 ; CHECK:       loopexit1:
1302 ; CHECK-NEXT:    ret
1303
1304 loopexit2:
1305   ret void
1306 ; CHECK:       loopexit2:
1307 ; CHECK-NEXT:    ret
1308 }
1309
1310 define void @test_unswitch_to_default_common_succ_with_phis(ptr %var, i32 %cond) {
1311 ; CHECK-LABEL: @test_unswitch_to_default_common_succ_with_phis(
1312 entry:
1313   br label %header
1314 ; CHECK-NEXT:  entry:
1315 ; CHECK-NEXT:    switch i32 %cond, label %entry.split [
1316 ; CHECK-NEXT:      i32 13, label %loopexit
1317 ; CHECK-NEXT:    ]
1318 ;
1319 ; CHECK:       entry.split:
1320 ; CHECK-NEXT:    br label %header
1321
1322 header:
1323   %var_val = load i32, ptr %var
1324   switch i32 %cond, label %latch [
1325     i32 0, label %latch
1326     i32 1, label %latch
1327     i32 13, label %loopexit
1328   ]
1329 ; CHECK:       header:
1330 ; CHECK-NEXT:    load
1331 ; CHECK-NEXT:    br label %latch
1332
1333 latch:
1334   ; No-op PHI node to exercise weird PHI update scenarios.
1335   %phi = phi i32 [ %var_val, %header ], [ %var_val, %header ], [ %var_val, %header ]
1336   call void @sink(i32 %phi)
1337   br label %header
1338 ; CHECK:       latch:
1339 ; CHECK-NEXT:    %[[PHI:.*]] = phi i32 [ %var_val, %header ]
1340 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
1341 ; CHECK-NEXT:    br label %header
1342
1343 loopexit:
1344   ret void
1345 ; CHECK:       loopexit:
1346 ; CHECK-NEXT:    ret
1347 }
1348
1349 declare void @f()
1350 declare void @g()
1351 define void @test_unswitch_switch_with_nonempty_unreachable() {
1352 ; CHECK-LABEL: @test_unswitch_switch_with_nonempty_unreachable()
1353 entry:
1354   br label %loop
1355
1356 loop:
1357   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1358   br label %for.cond
1359
1360 for.cond:
1361   switch i32 %cleanup.dest.slot.0, label %NonEmptyUnreachableBlock [
1362     i32 0, label %for.cond
1363     i32 1, label %NonEmptyUnreachableBlock
1364     i32 2, label %loop.loopexit
1365   ]
1366
1367 loop.loopexit:
1368   unreachable
1369
1370 NonEmptyUnreachableBlock:
1371   call void @f()
1372   call void @g()
1373   unreachable
1374
1375 ; CHECK:loop:
1376 ; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1377 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %NonEmptyUnreachableBlock [
1378 ; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
1379 ; CHECK-NEXT:    i32 0, label %loop.split
1380 ; CHECK-NEXT:    i32 2, label %loop.split
1381 ; CHECK-NEXT:  ]
1382
1383 ; CHECK:loop.split:
1384 ; CHECK-NEXT:  br label %for.cond
1385
1386 ; CHECK:for.cond:
1387 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.loopexit [
1388 ; CHECK-NEXT:    i32 0, label %for.cond
1389 ; CHECK-NEXT:  ]
1390
1391 ; CHECK:loop.loopexit:
1392 ; CHECK-NEXT:  unreachable
1393
1394 ; CHECK:NonEmptyUnreachableBlock:
1395 ; CHECK-NEXT:  call void @f()
1396 ; CHECK-NEXT:  call void @g()
1397 ; CHECK-NEXT:  unreachable
1398 }
1399
1400 define void @test_unswitch_switch_with_nonempty_unreachable2() {
1401 ; CHECK-LABEL: @test_unswitch_switch_with_nonempty_unreachable2()
1402 entry:
1403   br label %loop
1404
1405 loop:
1406   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1407   br label %for.cond
1408
1409 for.cond:
1410   switch i32 %cleanup.dest.slot.0, label %for.cond [
1411     i32 0, label %for.cond
1412     i32 1, label %NonEmptyUnreachableBlock
1413     i32 2, label %loop.loopexit
1414   ]
1415
1416 loop.loopexit:
1417   unreachable
1418
1419 NonEmptyUnreachableBlock:
1420   call void @f()
1421   call void @g()
1422   unreachable
1423
1424 ; CHECK:loop:
1425 ; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1426 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %loop.split [
1427 ; CHECK-NEXT:    i32 1, label %NonEmptyUnreachableBlock
1428 ; CHECK-NEXT:  ]
1429
1430 ; CHECK:loop.split:
1431 ; CHECK-NEXT:  br label %for.cond
1432
1433 ; CHECK:for.cond:
1434 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %for.cond.backedge [
1435 ; CHECK-NEXT:    i32 0, label %for.cond.backedge
1436 ; CHECK-NEXT:    i32 2, label %loop.loopexit
1437 ; CHECK-NEXT:  ]
1438
1439 ; CHECK:for.cond.backedge:
1440 ; CHECK-NEXT:  br label %for.cond
1441
1442 ; CHECK:loop.loopexit:
1443 ; CHECK-NEXT:  unreachable
1444
1445 ; CHECK:NonEmptyUnreachableBlock:
1446 ; CHECK-NEXT:  call void @f()
1447 ; CHECK-NEXT:  call void @g()
1448 ; CHECK-NEXT:  unreachable
1449 }
1450
1451 ; PR45355
1452 define void @test_unswitch_switch_with_duplicate_edge() {
1453 ; CHECK-LABEL: @test_unswitch_switch_with_duplicate_edge()
1454 entry:
1455   br label %lbl1
1456
1457 lbl1:                                             ; preds = %entry
1458   %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
1459   br label %for.cond1
1460
1461 for.cond1:                                        ; preds = %for.cond1, %lbl1
1462   switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
1463     i32 0, label %for.cond1
1464     i32 5, label %UnifiedUnreachableBlock
1465     i32 2, label %lbl1.loopexit
1466   ]
1467
1468 UnifiedUnreachableBlock:                          ; preds = %for.cond1, %for.cond1
1469   unreachable
1470
1471 lbl1.loopexit:                                    ; preds = %for.cond1
1472   unreachable
1473
1474 ; CHECK: for.cond1:
1475 ; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
1476 ; CHECK-NEXT:    i32 0, label %for.cond1
1477 ; CHECK-NEXT:    i32 5, label %UnifiedUnreachableBlock
1478 ; CHECK-NEXT:    i32 2, label %lbl1.loopexit
1479 ; CHECK-NEXT:  ]
1480 }