test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll

   1 ; RUN: opt -passes='loop(unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
   2 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -S < %s | FileCheck %s
   3 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
   4
   5 declare i32 @a()
   6 declare i32 @b()
   7 declare i32 @c()
   8 declare i32 @d()
   9
  10 declare void @sink1(i32)
  11 declare void @sink2(i32)
  12
  13 declare i1 @cond()
  14 declare i32 @cond.i32()
  15
  16 ; Negative test: we cannot unswitch convergent calls.
  17 define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) {
  18 ; CHECK-LABEL: @test_no_unswitch_convergent(
  19 entry:
  20   br label %loop_begin
  21 ; CHECK-NEXT:  entry:
  22 ; CHECK-NEXT:    br label %loop_begin
  23 ;
  24 ; We shouldn't have unswitched into any other block either.
  25 ; CHECK-NOT:     br i1 %cond
  26
  27 loop_begin:
  28   br i1 %cond, label %loop_a, label %loop_b
  29 ; CHECK:       loop_begin:
  30 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
  31
  32 loop_a:
  33   call i32 @a() convergent
  34   br label %loop_latch
  35
  36 loop_b:
  37   call i32 @b()
  38   br label %loop_latch
  39
  40 loop_latch:
  41   %v = load i1, i1* %ptr
  42   br i1 %v, label %loop_begin, label %loop_exit
  43
  44 loop_exit:
  45   ret void
  46 }
  47
  48 ; Negative test: we cannot unswitch noduplicate calls.
  49 define void @test_no_unswitch_noduplicate(i1* %ptr, i1 %cond) {
  50 ; CHECK-LABEL: @test_no_unswitch_noduplicate(
  51 entry:
  52   br label %loop_begin
  53 ; CHECK-NEXT:  entry:
  54 ; CHECK-NEXT:    br label %loop_begin
  55 ;
  56 ; We shouldn't have unswitched into any other block either.
  57 ; CHECK-NOT:     br i1 %cond
  58
  59 loop_begin:
  60   br i1 %cond, label %loop_a, label %loop_b
  61 ; CHECK:       loop_begin:
  62 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
  63
  64 loop_a:
  65   call i32 @a() noduplicate
  66   br label %loop_latch
  67
  68 loop_b:
  69   call i32 @b()
  70   br label %loop_latch
  71
  72 loop_latch:
  73   %v = load i1, i1* %ptr
  74   br i1 %v, label %loop_begin, label %loop_exit
  75
  76 loop_exit:
  77   ret void
  78 }
  79
  80 declare i32 @__CxxFrameHandler3(...)
  81
  82 ; Negative test: we cannot unswitch when tokens are used across blocks as we
  83 ; might introduce PHIs.
  84 define void @test_no_unswitch_cross_block_token(i1* %ptr, i1 %cond) nounwind personality i32 (...)* @__CxxFrameHandler3 {
  85 ; CHECK-LABEL: @test_no_unswitch_cross_block_token(
  86 entry:
  87   br label %loop_begin
  88 ; CHECK-NEXT:  entry:
  89 ; CHECK-NEXT:    br label %loop_begin
  90 ;
  91 ; We shouldn't have unswitched into any other block either.
  92 ; CHECK-NOT:     br i1 %cond
  93
  94 loop_begin:
  95   br i1 %cond, label %loop_a, label %loop_b
  96 ; CHECK:       loop_begin:
  97 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
  98
  99 loop_a:
 100   call i32 @a()
 101   br label %loop_cont
 102
 103 loop_b:
 104   call i32 @b()
 105   br label %loop_cont
 106
 107 loop_cont:
 108   invoke i32 @a()
 109           to label %loop_latch unwind label %loop_catch
 110
 111 loop_latch:
 112   br label %loop_begin
 113
 114 loop_catch:
 115   %catch = catchswitch within none [label %loop_catch_latch, label %loop_exit] unwind to caller
 116
 117 loop_catch_latch:
 118   %catchpad_latch = catchpad within %catch []
 119   catchret from %catchpad_latch to label %loop_begin
 120
 121 loop_exit:
 122   %catchpad_exit = catchpad within %catch []
 123   catchret from %catchpad_exit to label %exit
 124
 125 exit:
 126   ret void
 127 }
 128
 129
 130 ; Non-trivial loop unswitching where there are two distinct trivial conditions
 131 ; to unswitch within the loop.
 132 define i32 @test1(i1* %ptr, i1 %cond1, i1 %cond2) {
 133 ; CHECK-LABEL: @test1(
 134 entry:
 135   br label %loop_begin
 136 ; CHECK-NEXT:  entry:
 137 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 138
 139 loop_begin:
 140   br i1 %cond1, label %loop_a, label %loop_b
 141
 142 loop_a:
 143   call i32 @a()
 144   br label %latch
 145 ; The 'loop_a' unswitched loop.
 146 ;
 147 ; CHECK:       entry.split.us:
 148 ; CHECK-NEXT:    br label %loop_begin.us
 149 ;
 150 ; CHECK:       loop_begin.us:
 151 ; CHECK-NEXT:    br label %loop_a.us
 152 ;
 153 ; CHECK:       loop_a.us:
 154 ; CHECK-NEXT:    call i32 @a()
 155 ; CHECK-NEXT:    br label %latch.us
 156 ;
 157 ; CHECK:       latch.us:
 158 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 159 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 160 ;
 161 ; CHECK:       loop_exit.split.us:
 162 ; CHECK-NEXT:    br label %loop_exit
 163
 164 loop_b:
 165   br i1 %cond2, label %loop_b_a, label %loop_b_b
 166 ; The second unswitched condition.
 167 ;
 168 ; CHECK:       entry.split:
 169 ; CHECK-NEXT:    br i1 %cond2, label %entry.split.split.us, label %entry.split.split
 170
 171 loop_b_a:
 172   call i32 @b()
 173   br label %latch
 174 ; The 'loop_b_a' unswitched loop.
 175 ;
 176 ; CHECK:       entry.split.split.us:
 177 ; CHECK-NEXT:    br label %loop_begin.us1
 178 ;
 179 ; CHECK:       loop_begin.us1:
 180 ; CHECK-NEXT:    br label %loop_b.us
 181 ;
 182 ; CHECK:       loop_b.us:
 183 ; CHECK-NEXT:    br label %loop_b_a.us
 184 ;
 185 ; CHECK:       loop_b_a.us:
 186 ; CHECK-NEXT:    call i32 @b()
 187 ; CHECK-NEXT:    br label %latch.us2
 188 ;
 189 ; CHECK:       latch.us2:
 190 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 191 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us1, label %loop_exit.split.split.us
 192 ;
 193 ; CHECK:       loop_exit.split.split.us:
 194 ; CHECK-NEXT:    br label %loop_exit.split
 195
 196 loop_b_b:
 197   call i32 @c()
 198   br label %latch
 199 ; The 'loop_b_b' unswitched loop.
 200 ;
 201 ; CHECK:       entry.split.split:
 202 ; CHECK-NEXT:    br label %loop_begin
 203 ;
 204 ; CHECK:       loop_begin:
 205 ; CHECK-NEXT:    br label %loop_b
 206 ;
 207 ; CHECK:       loop_b:
 208 ; CHECK-NEXT:    br label %loop_b_b
 209 ;
 210 ; CHECK:       loop_b_b:
 211 ; CHECK-NEXT:    call i32 @c()
 212 ; CHECK-NEXT:    br label %latch
 213 ;
 214 ; CHECK:       latch:
 215 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 216 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split.split
 217 ;
 218 ; CHECK:       loop_exit.split.split:
 219 ; CHECK-NEXT:    br label %loop_exit.split
 220
 221 latch:
 222   %v = load i1, i1* %ptr
 223   br i1 %v, label %loop_begin, label %loop_exit
 224
 225 loop_exit:
 226   ret i32 0
 227 ; CHECK:       loop_exit.split:
 228 ; CHECK-NEXT:    br label %loop_exit
 229 ;
 230 ; CHECK:       loop_exit:
 231 ; CHECK-NEXT:    ret
 232 }
 233
 234 define i32 @test2(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr, i32* %c.ptr) {
 235 ; CHECK-LABEL: @test2(
 236 entry:
 237   br label %loop_begin
 238 ; CHECK-NEXT:  entry:
 239 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 240
 241 loop_begin:
 242   %v = load i1, i1* %ptr
 243   br i1 %cond1, label %loop_a, label %loop_b
 244
 245 loop_a:
 246   %a = load i32, i32* %a.ptr
 247   %ac = load i32, i32* %c.ptr
 248   br i1 %v, label %loop_begin, label %loop_exit
 249 ; The 'loop_a' unswitched loop.
 250 ;
 251 ; CHECK:       entry.split.us:
 252 ; CHECK-NEXT:    br label %loop_begin.us
 253 ;
 254 ; CHECK:       loop_begin.us:
 255 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 256 ; CHECK-NEXT:    br label %loop_a.us
 257 ;
 258 ; CHECK:       loop_a.us:
 259 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 260 ; CHECK-NEXT:    %[[AC:.*]] = load i32, i32* %c.ptr
 261 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us
 262 ;
 263 ; CHECK:       loop_exit.split.us:
 264 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a.us ]
 265 ; CHECK-NEXT:    %[[AC_LCSSA:.*]] = phi i32 [ %[[AC]], %loop_a.us ]
 266 ; CHECK-NEXT:    br label %loop_exit
 267
 268 loop_b:
 269   %b = load i32, i32* %b.ptr
 270   %bc = load i32, i32* %c.ptr
 271   br i1 %v, label %loop_begin, label %loop_exit
 272 ; The 'loop_b' unswitched loop.
 273 ;
 274 ; CHECK:       entry.split:
 275 ; CHECK-NEXT:    br label %loop_begin
 276 ;
 277 ; CHECK:       loop_begin:
 278 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 279 ; CHECK-NEXT:    br label %loop_b
 280 ;
 281 ; CHECK:       loop_b:
 282 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 283 ; CHECK-NEXT:    %[[BC:.*]] = load i32, i32* %c.ptr
 284 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split
 285 ;
 286 ; CHECK:       loop_exit.split:
 287 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
 288 ; CHECK-NEXT:    %[[BC_LCSSA:.*]] = phi i32 [ %[[BC]], %loop_b ]
 289 ; CHECK-NEXT:    br label %loop_exit
 290
 291 loop_exit:
 292   %ab.phi = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
 293   %c.phi = phi i32 [ %ac, %loop_a ], [ %bc, %loop_b ]
 294   %result = add i32 %ab.phi, %c.phi
 295   ret i32 %result
 296 ; CHECK:       loop_exit:
 297 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
 298 ; CHECK-NEXT:    %[[C_PHI:.*]] = phi i32 [ %[[BC_LCSSA]], %loop_exit.split ], [ %[[AC_LCSSA]], %loop_exit.split.us ]
 299 ; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[AB_PHI]], %[[C_PHI]]
 300 ; CHECK-NEXT:    ret i32 %[[RESULT]]
 301 }
 302
 303 ; Test a non-trivial unswitch of an exiting edge to an exit block with other
 304 ; in-loop predecessors.
 305 define i32 @test3a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 306 ; CHECK-LABEL: @test3a(
 307 entry:
 308   br label %loop_begin
 309 ; CHECK-NEXT:  entry:
 310 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 311
 312 loop_begin:
 313   %v = load i1, i1* %ptr
 314   %a = load i32, i32* %a.ptr
 315   br i1 %cond1, label %loop_exit, label %loop_b
 316 ; The 'loop_exit' clone.
 317 ;
 318 ; CHECK:       entry.split.us:
 319 ; CHECK-NEXT:    br label %loop_begin.us
 320 ;
 321 ; CHECK:       loop_begin.us:
 322 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 323 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 324 ; CHECK-NEXT:    br label %loop_exit.split.us
 325 ;
 326 ; CHECK:       loop_exit.split.us:
 327 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
 328 ; CHECK-NEXT:    br label %loop_exit
 329
 330 loop_b:
 331   %b = load i32, i32* %b.ptr
 332   br i1 %v, label %loop_begin, label %loop_exit
 333 ; The 'loop_b' unswitched loop.
 334 ;
 335 ; CHECK:       entry.split:
 336 ; CHECK-NEXT:    br label %loop_begin
 337 ;
 338 ; CHECK:       loop_begin:
 339 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 340 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 341 ; CHECK-NEXT:    br label %loop_b
 342 ;
 343 ; CHECK:       loop_b:
 344 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 345 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 346 ;
 347 ; CHECK:       loop_exit.split:
 348 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
 349 ; CHECK-NEXT:    br label %loop_exit
 350
 351 loop_exit:
 352   %ab.phi = phi i32 [ %a, %loop_begin ], [ %b, %loop_b ]
 353   ret i32 %ab.phi
 354 ; CHECK:       loop_exit:
 355 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
 356 ; CHECK-NEXT:    ret i32 %[[AB_PHI]]
 357 }
 358
 359 ; Test a non-trivial unswitch of an exiting edge to an exit block with other
 360 ; in-loop predecessors. This is the same as @test3a but with the reversed order
 361 ; of successors so that the exiting edge is *not* the cloned edge.
 362 define i32 @test3b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 363 ; CHECK-LABEL: @test3b(
 364 entry:
 365   br label %loop_begin
 366 ; CHECK-NEXT:  entry:
 367 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 368
 369 loop_begin:
 370   %v = load i1, i1* %ptr
 371   %a = load i32, i32* %a.ptr
 372   br i1 %cond1, label %loop_b, label %loop_exit
 373 ; The 'loop_b' unswitched loop.
 374 ;
 375 ; CHECK:       entry.split.us:
 376 ; CHECK-NEXT:    br label %loop_begin.us
 377 ;
 378 ; CHECK:       loop_begin.us:
 379 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 380 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 381 ; CHECK-NEXT:    br label %loop_b.us
 382 ;
 383 ; CHECK:       loop_b.us:
 384 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 385 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 386 ;
 387 ; CHECK:       loop_exit.split.us:
 388 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ]
 389 ; CHECK-NEXT:    br label %loop_exit
 390
 391 loop_b:
 392   %b = load i32, i32* %b.ptr
 393   br i1 %v, label %loop_begin, label %loop_exit
 394 ; The original loop, now non-looping due to unswitching..
 395 ;
 396 ; CHECK:       entry.split:
 397 ; CHECK-NEXT:    br label %loop_begin
 398 ;
 399 ; CHECK:       loop_begin:
 400 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 401 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 402 ; CHECK-NEXT:    br label %loop_exit.split
 403 ;
 404 ; CHECK:       loop_exit.split:
 405 ; CHECK-NEXT:    br label %loop_exit
 406
 407 loop_exit:
 408   %ab.phi = phi i32 [ %b, %loop_b ], [ %a, %loop_begin ]
 409   ret i32 %ab.phi
 410 ; CHECK:       loop_exit:
 411 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A]], %loop_exit.split ], [ %[[B_LCSSA]], %loop_exit.split.us ]
 412 ; CHECK-NEXT:    ret i32 %[[AB_PHI]]
 413 }
 414
 415 ; Test a non-trivial unswitch of an exiting edge to an exit block with no other
 416 ; in-loop predecessors.
 417 define void @test4a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 418 ; CHECK-LABEL: @test4a(
 419 entry:
 420   br label %loop_begin
 421 ; CHECK-NEXT:  entry:
 422 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 423
 424 loop_begin:
 425   %v = load i1, i1* %ptr
 426   %a = load i32, i32* %a.ptr
 427   br i1 %cond1, label %loop_exit1, label %loop_b
 428 ; The 'loop_exit' clone.
 429 ;
 430 ; CHECK:       entry.split.us:
 431 ; CHECK-NEXT:    br label %loop_begin.us
 432 ;
 433 ; CHECK:       loop_begin.us:
 434 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 435 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 436 ; CHECK-NEXT:    br label %loop_exit1.split.us
 437 ;
 438 ; CHECK:       loop_exit1.split.us:
 439 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
 440 ; CHECK-NEXT:    br label %loop_exit1
 441
 442 loop_b:
 443   %b = load i32, i32* %b.ptr
 444   br i1 %v, label %loop_begin, label %loop_exit2
 445 ; The 'loop_b' unswitched loop.
 446 ;
 447 ; CHECK:       entry.split:
 448 ; CHECK-NEXT:    br label %loop_begin
 449 ;
 450 ; CHECK:       loop_begin:
 451 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 452 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 453 ; CHECK-NEXT:    br label %loop_b
 454 ;
 455 ; CHECK:       loop_b:
 456 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 457 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit2
 458
 459 loop_exit1:
 460   %a.phi = phi i32 [ %a, %loop_begin ]
 461   call void @sink1(i32 %a.phi)
 462   ret void
 463 ; CHECK:       loop_exit1:
 464 ; CHECK-NEXT:    call void @sink1(i32 %[[A_LCSSA]])
 465 ; CHECK-NEXT:    ret void
 466
 467 loop_exit2:
 468   %b.phi = phi i32 [ %b, %loop_b ]
 469   call void @sink2(i32 %b.phi)
 470   ret void
 471 ; CHECK:       loop_exit2:
 472 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
 473 ; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
 474 ; CHECK-NEXT:    ret void
 475 }
 476
 477 ; Test a non-trivial unswitch of an exiting edge to an exit block with no other
 478 ; in-loop predecessors. This is the same as @test4a but with the edges reversed
 479 ; so that the exiting edge is *not* the cloned edge.
 480 define void @test4b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 481 ; CHECK-LABEL: @test4b(
 482 entry:
 483   br label %loop_begin
 484 ; CHECK-NEXT:  entry:
 485 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 486
 487 loop_begin:
 488   %v = load i1, i1* %ptr
 489   %a = load i32, i32* %a.ptr
 490   br i1 %cond1, label %loop_b, label %loop_exit1
 491 ; The 'loop_b' clone.
 492 ;
 493 ; CHECK:       entry.split.us:
 494 ; CHECK-NEXT:    br label %loop_begin.us
 495 ;
 496 ; CHECK:       loop_begin.us:
 497 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 498 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 499 ; CHECK-NEXT:    br label %loop_b.us
 500 ;
 501 ; CHECK:       loop_b.us:
 502 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 503 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit2.split.us
 504 ;
 505 ; CHECK:       loop_exit2.split.us:
 506 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ]
 507 ; CHECK-NEXT:    br label %loop_exit2
 508
 509 loop_b:
 510   %b = load i32, i32* %b.ptr
 511   br i1 %v, label %loop_begin, label %loop_exit2
 512 ; The 'loop_exit' unswitched path.
 513 ;
 514 ; CHECK:       entry.split:
 515 ; CHECK-NEXT:    br label %loop_begin
 516 ;
 517 ; CHECK:       loop_begin:
 518 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 519 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 520 ; CHECK-NEXT:    br label %loop_exit1
 521
 522 loop_exit1:
 523   %a.phi = phi i32 [ %a, %loop_begin ]
 524   call void @sink1(i32 %a.phi)
 525   ret void
 526 ; CHECK:       loop_exit1:
 527 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ]
 528 ; CHECK-NEXT:    call void @sink1(i32 %[[A_PHI]])
 529 ; CHECK-NEXT:    ret void
 530
 531 loop_exit2:
 532   %b.phi = phi i32 [ %b, %loop_b ]
 533   call void @sink2(i32 %b.phi)
 534   ret void
 535 ; CHECK:       loop_exit2:
 536 ; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
 537 ; CHECK-NEXT:    ret void
 538 }
 539
 540 ; Test a non-trivial unswitch of an exiting edge to an exit block with no other
 541 ; in-loop predecessors. This is the same as @test4a but with a common merge
 542 ; block after the independent loop exits. This requires a different structural
 543 ; update to the dominator tree.
 544 define void @test4c(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 545 ; CHECK-LABEL: @test4c(
 546 entry:
 547   br label %loop_begin
 548 ; CHECK-NEXT:  entry:
 549 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 550
 551 loop_begin:
 552   %v = load i1, i1* %ptr
 553   %a = load i32, i32* %a.ptr
 554   br i1 %cond1, label %loop_exit1, label %loop_b
 555 ; The 'loop_exit' clone.
 556 ;
 557 ; CHECK:       entry.split.us:
 558 ; CHECK-NEXT:    br label %loop_begin.us
 559 ;
 560 ; CHECK:       loop_begin.us:
 561 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 562 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 563 ; CHECK-NEXT:    br label %loop_exit1.split.us
 564 ;
 565 ; CHECK:       loop_exit1.split.us:
 566 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
 567 ; CHECK-NEXT:    br label %loop_exit1
 568
 569 loop_b:
 570   %b = load i32, i32* %b.ptr
 571   br i1 %v, label %loop_begin, label %loop_exit2
 572 ; The 'loop_b' unswitched loop.
 573 ;
 574 ; CHECK:       entry.split:
 575 ; CHECK-NEXT:    br label %loop_begin
 576 ;
 577 ; CHECK:       loop_begin:
 578 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 579 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 580 ; CHECK-NEXT:    br label %loop_b
 581 ;
 582 ; CHECK:       loop_b:
 583 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 584 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit2
 585
 586 loop_exit1:
 587   %a.phi = phi i32 [ %a, %loop_begin ]
 588   call void @sink1(i32 %a.phi)
 589   br label %exit
 590 ; CHECK:       loop_exit1:
 591 ; CHECK-NEXT:    call void @sink1(i32 %[[A_LCSSA]])
 592 ; CHECK-NEXT:    br label %exit
 593
 594 loop_exit2:
 595   %b.phi = phi i32 [ %b, %loop_b ]
 596   call void @sink2(i32 %b.phi)
 597   br label %exit
 598 ; CHECK:       loop_exit2:
 599 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ]
 600 ; CHECK-NEXT:    call void @sink2(i32 %[[B_LCSSA]])
 601 ; CHECK-NEXT:    br label %exit
 602
 603 exit:
 604   ret void
 605 ; CHECK:       exit:
 606 ; CHECK-NEXT:    ret void
 607 }
 608
 609 ; Test that we can unswitch a condition out of multiple layers of a loop nest.
 610 define i32 @test5(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 611 ; CHECK-LABEL: @test5(
 612 entry:
 613   br label %loop_begin
 614 ; CHECK-NEXT:  entry:
 615 ; CHECK-NEXT:    br i1 %cond1, label %loop_begin.split.us, label %entry.split
 616 ;
 617 ; CHECK:       entry.split:
 618 ; CHECK-NEXT:    br label %loop_begin
 619 ;
 620 ; CHECK:       loop_begin:
 621 ; CHECK-NEXT:    br label %loop_begin.split
 622
 623 loop_begin:
 624   br label %inner_loop_begin
 625
 626 inner_loop_begin:
 627   %v = load i1, i1* %ptr
 628   %a = load i32, i32* %a.ptr
 629   br i1 %cond1, label %loop_exit, label %inner_loop_b
 630 ; The 'loop_exit' clone.
 631 ;
 632 ; CHECK:       loop_begin.split.us:
 633 ; CHECK-NEXT:    br label %inner_loop_begin.us
 634 ;
 635 ; CHECK:       inner_loop_begin.us:
 636 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 637 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 638 ; CHECK-NEXT:    br label %loop_exit.loopexit.split.us
 639 ;
 640 ; CHECK:       loop_exit.loopexit.split.us:
 641 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
 642 ; CHECK-NEXT:    br label %loop_exit
 643
 644 inner_loop_b:
 645   %b = load i32, i32* %b.ptr
 646   br i1 %v, label %inner_loop_begin, label %loop_latch
 647 ; The 'inner_loop_b' unswitched loop.
 648 ;
 649 ; CHECK:       loop_begin.split:
 650 ; CHECK-NEXT:    br label %inner_loop_begin
 651 ;
 652 ; CHECK:       inner_loop_begin:
 653 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 654 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 655 ; CHECK-NEXT:    br label %inner_loop_b
 656 ;
 657 ; CHECK:       inner_loop_b:
 658 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 659 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_begin, label %loop_latch
 660
 661 loop_latch:
 662   %b.phi = phi i32 [ %b, %inner_loop_b ]
 663   %v2 = load i1, i1* %ptr
 664   br i1 %v2, label %loop_begin, label %loop_exit
 665 ; CHECK:       loop_latch:
 666 ; CHECK-NEXT:    %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_b ]
 667 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr
 668 ; CHECK-NEXT:    br i1 %[[V2]], label %loop_begin, label %loop_exit.loopexit1
 669
 670 loop_exit:
 671   %ab.phi = phi i32 [ %a, %inner_loop_begin ], [ %b.phi, %loop_latch ]
 672   ret i32 %ab.phi
 673 ; CHECK:       loop_exit.loopexit:
 674 ; CHECK-NEXT:    br label %loop_exit
 675 ;
 676 ; CHECK:       loop_exit.loopexit1:
 677 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %loop_latch ]
 678 ; CHECK-NEXT:    br label %loop_exit
 679 ;
 680 ; CHECK:       loop_exit:
 681 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[B_LCSSA]], %loop_exit.loopexit1 ]
 682 ; CHECK-NEXT:    ret i32 %[[AB_PHI]]
 683 }
 684
 685 ; Test that we can unswitch a condition where we end up only cloning some of
 686 ; the nested loops and needing to delete some of the nested loops.
 687 define i32 @test6(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) {
 688 ; CHECK-LABEL: @test6(
 689 entry:
 690   br label %loop_begin
 691 ; CHECK-NEXT:  entry:
 692 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
 693
 694 loop_begin:
 695   %v = load i1, i1* %ptr
 696   br i1 %cond1, label %loop_a, label %loop_b
 697
 698 loop_a:
 699   br label %loop_a_inner
 700
 701 loop_a_inner:
 702   %va = load i1, i1* %ptr
 703   %a = load i32, i32* %a.ptr
 704   br i1 %va, label %loop_a_inner, label %loop_a_inner_exit
 705
 706 loop_a_inner_exit:
 707   %a.lcssa = phi i32 [ %a, %loop_a_inner ]
 708   br label %latch
 709 ; The 'loop_a' cloned loop.
 710 ;
 711 ; CHECK:       entry.split.us:
 712 ; CHECK-NEXT:    br label %loop_begin.us
 713 ;
 714 ; CHECK:       loop_begin.us:
 715 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 716 ; CHECK-NEXT:    br label %loop_a.us
 717 ;
 718 ; CHECK:       loop_a.us:
 719 ; CHECK-NEXT:    br label %loop_a_inner.us
 720 ;
 721 ; CHECK:       loop_a_inner.us
 722 ; CHECK-NEXT:    %[[VA:.*]] = load i1, i1* %ptr
 723 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 724 ; CHECK-NEXT:    br i1 %[[VA]], label %loop_a_inner.us, label %loop_a_inner_exit.us
 725 ;
 726 ; CHECK:       loop_a_inner_exit.us:
 727 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a_inner.us ]
 728 ; CHECK-NEXT:    br label %latch.us
 729 ;
 730 ; CHECK:       latch.us:
 731 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %loop_a_inner_exit.us ]
 732 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 733 ;
 734 ; CHECK:       loop_exit.split.us:
 735 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_PHI]], %latch.us ]
 736 ; CHECK-NEXT:    br label %loop_exit
 737
 738 loop_b:
 739   br label %loop_b_inner
 740
 741 loop_b_inner:
 742   %vb = load i1, i1* %ptr
 743   %b = load i32, i32* %b.ptr
 744   br i1 %vb, label %loop_b_inner, label %loop_b_inner_exit
 745
 746 loop_b_inner_exit:
 747   %b.lcssa = phi i32 [ %b, %loop_b_inner ]
 748   br label %latch
 749
 750 latch:
 751   %ab.phi = phi i32 [ %a.lcssa, %loop_a_inner_exit ], [ %b.lcssa, %loop_b_inner_exit ]
 752   br i1 %v, label %loop_begin, label %loop_exit
 753 ; The 'loop_b' unswitched loop.
 754 ;
 755 ; CHECK:       entry.split:
 756 ; CHECK-NEXT:    br label %loop_begin
 757 ;
 758 ; CHECK:       loop_begin:
 759 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 760 ; CHECK-NEXT:    br label %loop_b
 761 ;
 762 ; CHECK:       loop_b:
 763 ; CHECK-NEXT:    br label %loop_b_inner
 764 ;
 765 ; CHECK:       loop_b_inner
 766 ; CHECK-NEXT:    %[[VB:.*]] = load i1, i1* %ptr
 767 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 768 ; CHECK-NEXT:    br i1 %[[VB]], label %loop_b_inner, label %loop_b_inner_exit
 769 ;
 770 ; CHECK:       loop_b_inner_exit:
 771 ; CHECK-NEXT:    %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b_inner ]
 772 ; CHECK-NEXT:    br label %latch
 773 ;
 774 ; CHECK:       latch:
 775 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 776 ;
 777 ; CHECK:       loop_exit.split:
 778 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %latch ]
 779 ; CHECK-NEXT:    br label %loop_exit
 780
 781 loop_exit:
 782   %ab.lcssa = phi i32 [ %ab.phi, %latch ]
 783   ret i32 %ab.lcssa
 784 ; CHECK:       loop_exit:
 785 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ]
 786 ; CHECK-NEXT:    ret i32 %[[AB_PHI]]
 787 }
 788
 789 ; Test that when unswitching a deeply nested loop condition in a way that
 790 ; produces a non-loop clone that can reach multiple exit blocks which are part
 791 ; of different outer loops we correctly divide the cloned loop blocks between
 792 ; the outer loops based on reachability.
 793 define i32 @test7a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
 794 ; CHECK-LABEL: @test7a(
 795 entry:
 796   br label %loop_begin
 797 ; CHECK-NEXT:  entry:
 798 ; CHECK-NEXT:    br label %loop_begin
 799
 800 loop_begin:
 801   %a = load i32, i32* %a.ptr
 802   br label %inner_loop_begin
 803 ; CHECK:       loop_begin:
 804 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 805 ; CHECK-NEXT:    br label %inner_loop_begin
 806
 807 inner_loop_begin:
 808   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
 809   %cond = load i1, i1* %cond.ptr
 810   %b = load i32, i32* %b.ptr
 811   br label %inner_inner_loop_begin
 812 ; CHECK:       inner_loop_begin:
 813 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 814 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 815 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 816 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 817
 818 inner_inner_loop_begin:
 819   %v1 = load i1, i1* %ptr
 820   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 821
 822 inner_inner_loop_a:
 823   %v2 = load i1, i1* %ptr
 824   br i1 %v2, label %loop_exit, label %inner_inner_loop_c
 825
 826 inner_inner_loop_b:
 827   %v3 = load i1, i1* %ptr
 828   br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c
 829
 830 inner_inner_loop_c:
 831   %v4 = load i1, i1* %ptr
 832   br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d
 833
 834 inner_inner_loop_d:
 835   br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_begin
 836 ; The cloned copy that always exits with the adjustments required to fix up
 837 ; loop exits.
 838 ;
 839 ; CHECK:       inner_loop_begin.split.us:
 840 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
 841 ;
 842 ; CHECK:       inner_inner_loop_begin.us:
 843 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 844 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
 845 ;
 846 ; CHECK:       inner_inner_loop_b.us:
 847 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 848 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us.loopexit
 849 ;
 850 ; CHECK:       inner_inner_loop_a.us:
 851 ; CHECK-NEXT:    %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin.us ]
 852 ; CHECK-NEXT:    %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin.us ]
 853 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 854 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us
 855 ;
 856 ; CHECK:       inner_inner_loop_c.us.loopexit:
 857 ; CHECK-NEXT:    br label %inner_inner_loop_c.us
 858 ;
 859 ; CHECK:       inner_inner_loop_c.us:
 860 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 861 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us
 862 ;
 863 ; CHECK:       inner_inner_loop_d.us:
 864 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split
 865 ;
 866 ; CHECK:       inner_inner_loop_exit.split.us:
 867 ; CHECK-NEXT:    br label %inner_inner_loop_exit
 868 ;
 869 ; CHECK:       loop_exit.split.us:
 870 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a.us ]
 871 ; CHECK-NEXT:    %[[B_LCSSA_US:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a.us ]
 872 ; CHECK-NEXT:    br label %loop_exit
 873 ;
 874 ; CHECK:       inner_loop_exit.loopexit.split.us:
 875 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
 876 ;
 877 ; The original copy that continues to loop.
 878 ;
 879 ; CHECK:       inner_loop_begin.split:
 880 ; CHECK-NEXT:    br label %inner_inner_loop_begin
 881 ;
 882 ; CHECK:       inner_inner_loop_begin:
 883 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 884 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
 885 ;
 886 ; CHECK:       inner_inner_loop_a:
 887 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 888 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c
 889 ;
 890 ; CHECK:       inner_inner_loop_b:
 891 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 892 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c
 893 ;
 894 ; CHECK:       inner_inner_loop_c:
 895 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 896 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d
 897 ;
 898 ; CHECK:       inner_inner_loop_d:
 899 ; CHECK-NEXT:    br label %inner_inner_loop_begin
 900 ;
 901 ; CHECK:       inner_inner_loop_exit.split:
 902 ; CHECK-NEXT:    br label %inner_inner_loop_exit
 903
 904 inner_inner_loop_exit:
 905   %a2 = load i32, i32* %a.ptr
 906   %v5 = load i1, i1* %ptr
 907   br i1 %v5, label %inner_loop_exit, label %inner_loop_begin
 908 ; CHECK:       inner_inner_loop_exit:
 909 ; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
 910 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 911 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
 912
 913 inner_loop_exit:
 914   br label %loop_begin
 915 ; CHECK:       inner_loop_exit.loopexit.split:
 916 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
 917 ;
 918 ; CHECK:       inner_loop_exit.loopexit:
 919 ; CHECK-NEXT:    br label %inner_loop_exit
 920 ;
 921 ; CHECK:       inner_loop_exit.loopexit1:
 922 ; CHECK-NEXT:    br label %inner_loop_exit
 923 ;
 924 ; CHECK:       inner_loop_exit:
 925 ; CHECK-NEXT:    br label %loop_begin
 926
 927 loop_exit:
 928   %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ]
 929   %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ]
 930   %result = add i32 %a.lcssa, %b.lcssa
 931   ret i32 %result
 932 ; CHECK:       loop_exit.split:
 933 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ]
 934 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a ]
 935 ; CHECK-NEXT:    br label %loop_exit
 936 ;
 937 ; CHECK:       loop_exit:
 938 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
 939 ; CHECK-NEXT:    %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ]
 940 ; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]]
 941 ; CHECK-NEXT:    ret i32 %[[RESULT]]
 942 }
 943
 944 ; Same pattern as @test7a but here the original loop becomes a non-loop that
 945 ; can reach multiple exit blocks which are part of different outer loops.
 946 define i32 @test7b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
 947 ; CHECK-LABEL: @test7b(
 948 entry:
 949   br label %loop_begin
 950 ; CHECK-NEXT:  entry:
 951 ; CHECK-NEXT:    br label %loop_begin
 952
 953 loop_begin:
 954   %a = load i32, i32* %a.ptr
 955   br label %inner_loop_begin
 956 ; CHECK:       loop_begin:
 957 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
 958 ; CHECK-NEXT:    br label %inner_loop_begin
 959
 960 inner_loop_begin:
 961   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
 962   %cond = load i1, i1* %cond.ptr
 963   %b = load i32, i32* %b.ptr
 964   br label %inner_inner_loop_begin
 965 ; CHECK:       inner_loop_begin:
 966 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
 967 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
 968 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
 969 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
 970
 971 inner_inner_loop_begin:
 972   %v1 = load i1, i1* %ptr
 973   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
 974
 975 inner_inner_loop_a:
 976   %v2 = load i1, i1* %ptr
 977   br i1 %v2, label %loop_exit, label %inner_inner_loop_c
 978
 979 inner_inner_loop_b:
 980   %v3 = load i1, i1* %ptr
 981   br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c
 982
 983 inner_inner_loop_c:
 984   %v4 = load i1, i1* %ptr
 985   br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d
 986
 987 inner_inner_loop_d:
 988   br i1 %cond, label %inner_inner_loop_begin, label %inner_loop_exit
 989 ; The cloned copy that continues looping.
 990 ;
 991 ; CHECK:       inner_loop_begin.split.us:
 992 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
 993 ;
 994 ; CHECK:       inner_inner_loop_begin.us:
 995 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 996 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
 997 ;
 998 ; CHECK:       inner_inner_loop_b.us:
 999 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1000 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us
1001 ;
1002 ; CHECK:       inner_inner_loop_a.us:
1003 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1004 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us
1005 ;
1006 ; CHECK:       inner_inner_loop_c.us:
1007 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1008 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us
1009 ;
1010 ; CHECK:       inner_inner_loop_d.us:
1011 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1012 ;
1013 ; CHECK:       inner_inner_loop_exit.split.us:
1014 ; CHECK-NEXT:    br label %inner_inner_loop_exit
1015 ;
1016 ; CHECK:       loop_exit.split.us:
1017 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ]
1018 ; CHECK-NEXT:    %[[B_LCSSA_US:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a.us ]
1019 ; CHECK-NEXT:    br label %loop_exit
1020 ;
1021 ; CHECK:       inner_loop_exit.loopexit.split.us:
1022 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1023 ;
1024 ; The original copy that now always exits and needs adjustments for exit
1025 ; blocks.
1026 ;
1027 ; CHECK:       inner_loop_begin.split:
1028 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1029 ;
1030 ; CHECK:       inner_inner_loop_begin:
1031 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1032 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1033 ;
1034 ; CHECK:       inner_inner_loop_a:
1035 ; CHECK-NEXT:    %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin ]
1036 ; CHECK-NEXT:    %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin ]
1037 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1038 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c
1039 ;
1040 ; CHECK:       inner_inner_loop_b:
1041 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1042 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c.loopexit
1043 ;
1044 ; CHECK:       inner_inner_loop_c.loopexit:
1045 ; CHECK-NEXT:    br label %inner_inner_loop_c
1046 ;
1047 ; CHECK:       inner_inner_loop_c:
1048 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1049 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d
1050 ;
1051 ; CHECK:       inner_inner_loop_d:
1052 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split
1053 ;
1054 ; CHECK:       inner_inner_loop_exit.split:
1055 ; CHECK-NEXT:    br label %inner_inner_loop_exit
1056
1057 inner_inner_loop_exit:
1058   %a2 = load i32, i32* %a.ptr
1059   %v5 = load i1, i1* %ptr
1060   br i1 %v5, label %inner_loop_exit, label %inner_loop_begin
1061 ; CHECK:       inner_inner_loop_exit:
1062 ; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1063 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1064 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1065
1066 inner_loop_exit:
1067   br label %loop_begin
1068 ; CHECK:       inner_loop_exit.loopexit.split:
1069 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1070 ;
1071 ; CHECK:       inner_loop_exit.loopexit:
1072 ; CHECK-NEXT:    br label %inner_loop_exit
1073 ;
1074 ; CHECK:       inner_loop_exit.loopexit1:
1075 ; CHECK-NEXT:    br label %inner_loop_exit
1076 ;
1077 ; CHECK:       inner_loop_exit:
1078 ; CHECK-NEXT:    br label %loop_begin
1079
1080 loop_exit:
1081   %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ]
1082   %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ]
1083   %result = add i32 %a.lcssa, %b.lcssa
1084   ret i32 %result
1085 ; CHECK:       loop_exit.split:
1086 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a ]
1087 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a ]
1088 ; CHECK-NEXT:    br label %loop_exit
1089 ;
1090 ; CHECK:       loop_exit:
1091 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
1092 ; CHECK-NEXT:    %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ]
1093 ; CHECK-NEXT:    %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]]
1094 ; CHECK-NEXT:    ret i32 %[[RESULT]]
1095 }
1096
1097 ; Test that when the exit block set of an inner loop changes to start at a less
1098 ; high level of the loop nest we correctly hoist the loop up the nest.
1099 define i32 @test8a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1100 ; CHECK-LABEL: @test8a(
1101 entry:
1102   br label %loop_begin
1103 ; CHECK-NEXT:  entry:
1104 ; CHECK-NEXT:    br label %loop_begin
1105
1106 loop_begin:
1107   %a = load i32, i32* %a.ptr
1108   br label %inner_loop_begin
1109 ; CHECK:       loop_begin:
1110 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1111 ; CHECK-NEXT:    br label %inner_loop_begin
1112
1113 inner_loop_begin:
1114   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
1115   %cond = load i1, i1* %cond.ptr
1116   %b = load i32, i32* %b.ptr
1117   br label %inner_inner_loop_begin
1118 ; CHECK:       inner_loop_begin:
1119 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
1120 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1121 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1122 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
1123
1124 inner_inner_loop_begin:
1125   %v1 = load i1, i1* %ptr
1126   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
1127
1128 inner_inner_loop_a:
1129   %v2 = load i1, i1* %ptr
1130   br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit
1131
1132 inner_inner_loop_b:
1133   br i1 %cond, label %inner_inner_loop_latch, label %inner_inner_loop_exit
1134
1135 inner_inner_loop_latch:
1136   br label %inner_inner_loop_begin
1137 ; The cloned region is now an exit from the inner loop.
1138 ;
1139 ; CHECK:       inner_loop_begin.split.us:
1140 ; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ]
1141 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1142 ;
1143 ; CHECK:       inner_inner_loop_begin.us:
1144 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1145 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
1146 ;
1147 ; CHECK:       inner_inner_loop_b.us:
1148 ; CHECK-NEXT:    br label %inner_inner_loop_latch.us
1149 ;
1150 ; CHECK:       inner_inner_loop_a.us:
1151 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1152 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us
1153 ;
1154 ; CHECK:       inner_inner_loop_latch.us:
1155 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1156 ;
1157 ; CHECK:       inner_loop_exit.loopexit.split.us:
1158 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a.us ]
1159 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1160 ;
1161 ; The original region exits the loop earlier.
1162 ;
1163 ; CHECK:       inner_loop_begin.split:
1164 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1165 ;
1166 ; CHECK:       inner_inner_loop_begin:
1167 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1168 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1169 ;
1170 ; CHECK:       inner_inner_loop_a:
1171 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1172 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split
1173 ;
1174 ; CHECK:       inner_inner_loop_b:
1175 ; CHECK-NEXT:    br label %inner_inner_loop_exit
1176 ;
1177 ; CHECK:       inner_inner_loop_latch:
1178 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1179
1180 inner_inner_loop_exit:
1181   %a2 = load i32, i32* %a.ptr
1182   %v4 = load i1, i1* %ptr
1183   br i1 %v4, label %inner_loop_exit, label %inner_loop_begin
1184 ; CHECK:       inner_inner_loop_exit:
1185 ; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1186 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1187 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1188
1189 inner_loop_exit:
1190   %v5 = load i1, i1* %ptr
1191   br i1 %v5, label %loop_exit, label %loop_begin
1192 ; CHECK:       inner_loop_exit.loopexit.split:
1193 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ]
1194 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1195 ;
1196 ; CHECK:       inner_loop_exit.loopexit:
1197 ; CHECK-NEXT:    %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ]
1198 ; CHECK-NEXT:    br label %inner_loop_exit
1199 ;
1200 ; CHECK:       inner_loop_exit.loopexit1:
1201 ; CHECK-NEXT:    %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ]
1202 ; CHECK-NEXT:    br label %inner_loop_exit
1203 ;
1204 ; CHECK:       inner_loop_exit:
1205 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ]
1206 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1207 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit, label %loop_begin
1208
1209 loop_exit:
1210   %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ]
1211   ret i32 %a.lcssa
1212 ; CHECK:       loop_exit:
1213 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1214 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1215 }
1216
1217 ; Same pattern as @test8a but where the original loop looses an exit block and
1218 ; needs to be hoisted up the nest.
1219 define i32 @test8b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1220 ; CHECK-LABEL: @test8b(
1221 entry:
1222   br label %loop_begin
1223 ; CHECK-NEXT:  entry:
1224 ; CHECK-NEXT:    br label %loop_begin
1225
1226 loop_begin:
1227   %a = load i32, i32* %a.ptr
1228   br label %inner_loop_begin
1229 ; CHECK:       loop_begin:
1230 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1231 ; CHECK-NEXT:    br label %inner_loop_begin
1232
1233 inner_loop_begin:
1234   %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ]
1235   %cond = load i1, i1* %cond.ptr
1236   %b = load i32, i32* %b.ptr
1237   br label %inner_inner_loop_begin
1238 ; CHECK:       inner_loop_begin:
1239 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ]
1240 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1241 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1242 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split
1243
1244 inner_inner_loop_begin:
1245   %v1 = load i1, i1* %ptr
1246   br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b
1247
1248 inner_inner_loop_a:
1249   %v2 = load i1, i1* %ptr
1250   br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit
1251
1252 inner_inner_loop_b:
1253   br i1 %cond, label %inner_inner_loop_exit, label %inner_inner_loop_latch
1254
1255 inner_inner_loop_latch:
1256   br label %inner_inner_loop_begin
1257 ; The cloned region is similar to before but with one earlier exit.
1258 ;
1259 ; CHECK:       inner_loop_begin.split.us:
1260 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1261 ;
1262 ; CHECK:       inner_inner_loop_begin.us:
1263 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1264 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us
1265 ;
1266 ; CHECK:       inner_inner_loop_b.us:
1267 ; CHECK-NEXT:    br label %inner_inner_loop_exit.split.us
1268 ;
1269 ; CHECK:       inner_inner_loop_a.us:
1270 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1271 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us
1272 ;
1273 ; CHECK:       inner_inner_loop_latch.us:
1274 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1275 ;
1276 ; CHECK:       inner_inner_loop_exit.split.us:
1277 ; CHECK-NEXT:    br label %inner_inner_loop_exit
1278 ;
1279 ; CHECK:       inner_loop_exit.loopexit.split.us:
1280 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ]
1281 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1282 ;
1283 ; The original region is now an exit in the preheader.
1284 ;
1285 ; CHECK:       inner_loop_begin.split:
1286 ; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ]
1287 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1288 ;
1289 ; CHECK:       inner_inner_loop_begin:
1290 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1291 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b
1292 ;
1293 ; CHECK:       inner_inner_loop_a:
1294 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1295 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split
1296 ;
1297 ; CHECK:       inner_inner_loop_b:
1298 ; CHECK-NEXT:    br label %inner_inner_loop_latch
1299 ;
1300 ; CHECK:       inner_inner_loop_latch:
1301 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1302
1303 inner_inner_loop_exit:
1304   %a2 = load i32, i32* %a.ptr
1305   %v4 = load i1, i1* %ptr
1306   br i1 %v4, label %inner_loop_exit, label %inner_loop_begin
1307 ; CHECK:       inner_inner_loop_exit:
1308 ; CHECK-NEXT:    %[[A2]] = load i32, i32* %a.ptr
1309 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1310 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin
1311
1312 inner_loop_exit:
1313   %v5 = load i1, i1* %ptr
1314   br i1 %v5, label %loop_exit, label %loop_begin
1315 ; CHECK:       inner_loop_exit.loopexit.split:
1316 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a ]
1317 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1318 ;
1319 ; CHECK:       inner_loop_exit.loopexit:
1320 ; CHECK-NEXT:    %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ]
1321 ; CHECK-NEXT:    br label %inner_loop_exit
1322 ;
1323 ; CHECK:       inner_loop_exit.loopexit1:
1324 ; CHECK-NEXT:    %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ]
1325 ; CHECK-NEXT:    br label %inner_loop_exit
1326 ;
1327 ; CHECK:       inner_loop_exit:
1328 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ]
1329 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1330 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit, label %loop_begin
1331
1332 loop_exit:
1333   %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ]
1334   ret i32 %a.lcssa
1335 ; CHECK:       loop_exit:
1336 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1337 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1338 }
1339
1340 ; Test for when unswitching produces a clone of an inner loop but
1341 ; the clone no longer has an exiting edge *at all* and loops infinitely.
1342 ; Because it doesn't ever exit to the outer loop it is no longer an inner loop
1343 ; but needs to be hoisted up the nest to be a top-level loop.
1344 define i32 @test9a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1345 ; CHECK-LABEL: @test9a(
1346 entry:
1347   br label %loop_begin
1348 ; CHECK-NEXT:  entry:
1349 ; CHECK-NEXT:    br label %loop_begin
1350
1351 loop_begin:
1352   %b = load i32, i32* %b.ptr
1353   %cond = load i1, i1* %cond.ptr
1354   br label %inner_loop_begin
1355 ; CHECK:       loop_begin:
1356 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1357 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1358 ; CHECK-NEXT:    br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split
1359
1360 inner_loop_begin:
1361   %a = load i32, i32* %a.ptr
1362   br i1 %cond, label %inner_loop_latch, label %inner_loop_exit
1363
1364 inner_loop_latch:
1365   call void @sink1(i32 %b)
1366   br label %inner_loop_begin
1367 ; The cloned inner loop ends up as an infinite loop and thus being a top-level
1368 ; loop with the preheader as an exit block of the outer loop.
1369 ;
1370 ; CHECK:       loop_begin.split.us
1371 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ]
1372 ; CHECK-NEXT:    br label %inner_loop_begin.us
1373 ;
1374 ; CHECK:       inner_loop_begin.us:
1375 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1376 ; CHECK-NEXT:    br label %inner_loop_latch.us
1377 ;
1378 ; CHECK:       inner_loop_latch.us:
1379 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1380 ; CHECK-NEXT:    br label %inner_loop_begin.us
1381 ;
1382 ; The original loop becomes boring non-loop code.
1383 ;
1384 ; CHECK:       loop_begin.split
1385 ; CHECK-NEXT:    br label %inner_loop_begin
1386 ;
1387 ; CHECK:       inner_loop_begin:
1388 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1389 ; CHECK-NEXT:    br label %inner_loop_exit
1390
1391 inner_loop_exit:
1392   %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ]
1393   %v = load i1, i1* %ptr
1394   br i1 %v, label %loop_begin, label %loop_exit
1395 ; CHECK:       inner_loop_exit:
1396 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ]
1397 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1398 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1399
1400 loop_exit:
1401   %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1402   ret i32 %a.lcssa
1403 ; CHECK:       loop_exit:
1404 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ]
1405 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1406 }
1407
1408 ; The same core pattern as @test9a, but instead of the cloned loop becoming an
1409 ; infinite loop, the original loop has its only exit unswitched and the
1410 ; original loop becomes infinite and must be hoisted out of the loop nest.
1411 define i32 @test9b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1412 ; CHECK-LABEL: @test9b(
1413 entry:
1414   br label %loop_begin
1415 ; CHECK-NEXT:  entry:
1416 ; CHECK-NEXT:    br label %loop_begin
1417
1418 loop_begin:
1419   %b = load i32, i32* %b.ptr
1420   %cond = load i1, i1* %cond.ptr
1421   br label %inner_loop_begin
1422 ; CHECK:       loop_begin:
1423 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1424 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1425 ; CHECK-NEXT:    br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split
1426
1427 inner_loop_begin:
1428   %a = load i32, i32* %a.ptr
1429   br i1 %cond, label %inner_loop_exit, label %inner_loop_latch
1430
1431 inner_loop_latch:
1432   call void @sink1(i32 %b)
1433   br label %inner_loop_begin
1434 ; The cloned inner loop becomes a boring non-loop.
1435 ;
1436 ; CHECK:       loop_begin.split.us
1437 ; CHECK-NEXT:    br label %inner_loop_begin.us
1438 ;
1439 ; CHECK:       inner_loop_begin.us:
1440 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1441 ; CHECK-NEXT:    br label %inner_loop_exit.split.us
1442 ;
1443 ; CHECK:       inner_loop_exit.split.us
1444 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
1445 ; CHECK-NEXT:    br label %inner_loop_exit
1446 ;
1447 ; The original loop becomes an infinite loop and thus a top-level loop with the
1448 ; preheader as an exit block for the outer loop.
1449 ;
1450 ; CHECK:       loop_begin.split
1451 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ]
1452 ; CHECK-NEXT:    br label %inner_loop_begin
1453 ;
1454 ; CHECK:       inner_loop_begin:
1455 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1456 ; CHECK-NEXT:    br label %inner_loop_latch
1457 ;
1458 ; CHECK:       inner_loop_latch:
1459 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1460 ; CHECK-NEXT:    br label %inner_loop_begin
1461
1462 inner_loop_exit:
1463   %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ]
1464   %v = load i1, i1* %ptr
1465   br i1 %v, label %loop_begin, label %loop_exit
1466 ; CHECK:       inner_loop_exit:
1467 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1468 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1469
1470 loop_exit:
1471   %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1472   ret i32 %a.lcssa
1473 ; CHECK:       loop_exit:
1474 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ]
1475 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1476 }
1477
1478 ; Test that requires re-forming dedicated exits for the cloned loop.
1479 define i32 @test10a(i1* %ptr, i1 %cond, i32* %a.ptr) {
1480 ; CHECK-LABEL: @test10a(
1481 entry:
1482   br label %loop_begin
1483 ; CHECK-NEXT:  entry:
1484 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
1485
1486 loop_begin:
1487   %a = load i32, i32* %a.ptr
1488   %v1 = load i1, i1* %ptr
1489   br i1 %v1, label %loop_a, label %loop_b
1490
1491 loop_a:
1492   %v2 = load i1, i1* %ptr
1493   br i1 %v2, label %loop_exit, label %loop_begin
1494
1495 loop_b:
1496   br i1 %cond, label %loop_exit, label %loop_begin
1497 ; The cloned loop with one edge as a direct exit.
1498 ;
1499 ; CHECK:       entry.split.us:
1500 ; CHECK-NEXT:    br label %loop_begin.us
1501 ;
1502 ; CHECK:       loop_begin.us:
1503 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1504 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1505 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
1506 ;
1507 ; CHECK:       loop_b.us:
1508 ; CHECK-NEXT:    %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin.us ]
1509 ; CHECK-NEXT:    br label %loop_exit.split.us
1510 ;
1511 ; CHECK:       loop_a.us:
1512 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1513 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_begin.backedge.us
1514 ;
1515 ; CHECK:       loop_begin.backedge.us:
1516 ; CHECK-NEXT:    br label %loop_begin.us
1517 ;
1518 ; CHECK:       loop_exit.split.us.loopexit:
1519 ; CHECK-NEXT:    %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a.us ]
1520 ; CHECK-NEXT:    br label %loop_exit
1521 ;
1522 ; CHECK:       loop_exit.split.us:
1523 ; CHECK-NEXT:    %[[A_PHI_US:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b.us ], [ %[[A_LCSSA_A]], %loop_exit.split.us.loopexit ]
1524 ; CHECK-NEXT:    br label %loop_exit
1525
1526 ; The original loop without one 'loop_exit' edge.
1527 ;
1528 ; CHECK:       entry.split:
1529 ; CHECK-NEXT:    br label %loop_begin
1530 ;
1531 ; CHECK:       loop_begin:
1532 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1533 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1534 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
1535 ;
1536 ; CHECK:       loop_a:
1537 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1538 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %loop_begin.backedge
1539 ;
1540 ; CHECK:       loop_begin.backedge:
1541 ; CHECK-NEXT:    br label %loop_begin
1542 ;
1543 ; CHECK:       loop_b:
1544 ; CHECK-NEXT:    br label %loop_begin.backedge
1545 ;
1546 ; CHECK:       loop_exit.split:
1547 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
1548 ; CHECK-NEXT:    br label %loop_exit
1549
1550 loop_exit:
1551   %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ]
1552   ret i32 %a.lcssa
1553 ; CHECK:       loop_exit:
1554 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_PHI_US]], %loop_exit.split.us ]
1555 ; CHECK-NEXT:    ret i32 %[[A_PHI]]
1556 }
1557
1558 ; Test that requires re-forming dedicated exits for the original loop.
1559 define i32 @test10b(i1* %ptr, i1 %cond, i32* %a.ptr) {
1560 ; CHECK-LABEL: @test10b(
1561 entry:
1562   br label %loop_begin
1563 ; CHECK-NEXT:  entry:
1564 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
1565
1566 loop_begin:
1567   %a = load i32, i32* %a.ptr
1568   %v1 = load i1, i1* %ptr
1569   br i1 %v1, label %loop_a, label %loop_b
1570
1571 loop_a:
1572   %v2 = load i1, i1* %ptr
1573   br i1 %v2, label %loop_begin, label %loop_exit
1574
1575 loop_b:
1576   br i1 %cond, label %loop_begin, label %loop_exit
1577 ; The cloned loop without one of the exits.
1578 ;
1579 ; CHECK:       entry.split.us:
1580 ; CHECK-NEXT:    br label %loop_begin.us
1581 ;
1582 ; CHECK:       loop_begin.us:
1583 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1584 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1585 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
1586 ;
1587 ; CHECK:       loop_b.us:
1588 ; CHECK-NEXT:    br label %loop_begin.backedge.us
1589 ;
1590 ; CHECK:       loop_a.us:
1591 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1592 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us
1593 ;
1594 ; CHECK:       loop_begin.backedge.us:
1595 ; CHECK-NEXT:    br label %loop_begin.us
1596 ;
1597 ; CHECK:       loop_exit.split.us:
1598 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
1599 ; CHECK-NEXT:    br label %loop_exit
1600
1601 ; The original loop without one 'loop_exit' edge.
1602 ;
1603 ; CHECK:       entry.split:
1604 ; CHECK-NEXT:    br label %loop_begin
1605 ;
1606 ; CHECK:       loop_begin:
1607 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1608 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1609 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
1610 ;
1611 ; CHECK:       loop_a:
1612 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1613 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split.loopexit
1614 ;
1615 ; CHECK:       loop_begin.backedge:
1616 ; CHECK-NEXT:    br label %loop_begin
1617 ;
1618 ; CHECK:       loop_b:
1619 ; CHECK-NEXT:    %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin ]
1620 ; CHECK-NEXT:    br label %loop_exit.split
1621 ;
1622 ; CHECK:       loop_exit.split.loopexit:
1623 ; CHECK-NEXT:    %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a ]
1624 ; CHECK-NEXT:    br label %loop_exit.split
1625 ;
1626 ; CHECK:       loop_exit.split:
1627 ; CHECK-NEXT:    %[[A_PHI_SPLIT:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b ], [ %[[A_LCSSA_A]], %loop_exit.split.loopexit ]
1628 ; CHECK-NEXT:    br label %loop_exit
1629
1630 loop_exit:
1631   %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ]
1632   ret i32 %a.lcssa
1633 ; CHECK:       loop_exit:
1634 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_PHI_SPLIT]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
1635 ; CHECK-NEXT:    ret i32 %[[A_PHI]]
1636 }
1637
1638 ; Check that if a cloned inner loop after unswitching doesn't loop and directly
1639 ; exits even an outer loop, we don't add the cloned preheader to the outer
1640 ; loop and do add the needed LCSSA phi nodes for the new exit block from the
1641 ; outer loop.
1642 define i32 @test11a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1643 ; CHECK-LABEL: @test11a(
1644 entry:
1645   br label %loop_begin
1646 ; CHECK-NEXT:  entry:
1647 ; CHECK-NEXT:    br label %loop_begin
1648
1649 loop_begin:
1650   %b = load i32, i32* %b.ptr
1651   %v1 = load i1, i1* %ptr
1652   br i1 %v1, label %loop_latch, label %inner_loop_ph
1653 ; CHECK:       loop_begin:
1654 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1655 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1656 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
1657
1658 inner_loop_ph:
1659   %cond = load i1, i1* %cond.ptr
1660   br label %inner_loop_begin
1661 ; CHECK:       inner_loop_ph:
1662 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1663 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
1664
1665 inner_loop_begin:
1666   call void @sink1(i32 %b)
1667   %a = load i32, i32* %a.ptr
1668   br i1 %cond, label %loop_exit, label %inner_loop_a
1669
1670 inner_loop_a:
1671   %v2 = load i1, i1* %ptr
1672   br i1 %v2, label %inner_loop_exit, label %inner_loop_begin
1673 ; The cloned path doesn't actually loop and is an exit from the outer loop as
1674 ; well.
1675 ;
1676 ; CHECK:       inner_loop_ph.split.us:
1677 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ]
1678 ; CHECK-NEXT:    br label %inner_loop_begin.us
1679 ;
1680 ; CHECK:       inner_loop_begin.us:
1681 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1682 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1683 ; CHECK-NEXT:    br label %loop_exit.loopexit.split.us
1684 ;
1685 ; CHECK:       loop_exit.loopexit.split.us:
1686 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ]
1687 ; CHECK-NEXT:    br label %loop_exit.loopexit
1688 ;
1689 ; The original remains a loop losing the exit edge.
1690 ;
1691 ; CHECK:       inner_loop_ph.split:
1692 ; CHECK-NEXT:    br label %inner_loop_begin
1693 ;
1694 ; CHECK:       inner_loop_begin:
1695 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1696 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1697 ; CHECK-NEXT:    br label %inner_loop_a
1698 ;
1699 ; CHECK:       inner_loop_a:
1700 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1701 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit, label %inner_loop_begin
1702
1703 inner_loop_exit:
1704   %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ]
1705   %v3 = load i1, i1* %ptr
1706   br i1 %v3, label %loop_latch, label %loop_exit
1707 ; CHECK:       inner_loop_exit:
1708 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_a ]
1709 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1710 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1
1711
1712 loop_latch:
1713   br label %loop_begin
1714 ; CHECK:       loop_latch:
1715 ; CHECK-NEXT:    br label %loop_begin
1716
1717 loop_exit:
1718   %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ]
1719   ret i32 %a.lcssa
1720 ; CHECK:       loop_exit.loopexit:
1721 ; CHECK-NEXT:    br label %loop_exit
1722 ;
1723 ; CHECK:       loop_exit.loopexit1:
1724 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ]
1725 ; CHECK-NEXT:    br label %loop_exit
1726 ;
1727 ; CHECK:       loop_exit:
1728 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %loop_exit.loopexit ], [ %[[A_LCSSA]], %loop_exit.loopexit1 ]
1729 ; CHECK-NEXT:    ret i32 %[[A_PHI]]
1730 }
1731
1732 ; Check that if the original inner loop after unswitching doesn't loop and
1733 ; directly exits even an outer loop, we remove the original preheader from the
1734 ; outer loop and add needed LCSSA phi nodes for the new exit block from the
1735 ; outer loop.
1736 define i32 @test11b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1737 ; CHECK-LABEL: @test11b(
1738 entry:
1739   br label %loop_begin
1740 ; CHECK-NEXT:  entry:
1741 ; CHECK-NEXT:    br label %loop_begin
1742
1743 loop_begin:
1744   %b = load i32, i32* %b.ptr
1745   %v1 = load i1, i1* %ptr
1746   br i1 %v1, label %loop_latch, label %inner_loop_ph
1747 ; CHECK:       loop_begin:
1748 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1749 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1750 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %inner_loop_ph
1751
1752 inner_loop_ph:
1753   %cond = load i1, i1* %cond.ptr
1754   br label %inner_loop_begin
1755 ; CHECK:       inner_loop_ph:
1756 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1757 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split
1758
1759 inner_loop_begin:
1760   call void @sink1(i32 %b)
1761   %a = load i32, i32* %a.ptr
1762   br i1 %cond, label %inner_loop_a, label %loop_exit
1763
1764 inner_loop_a:
1765   %v2 = load i1, i1* %ptr
1766   br i1 %v2, label %inner_loop_exit, label %inner_loop_begin
1767 ; The cloned path continues to loop without the exit out of the entire nest.
1768 ;
1769 ; CHECK:       inner_loop_ph.split.us:
1770 ; CHECK-NEXT:    br label %inner_loop_begin.us
1771 ;
1772 ; CHECK:       inner_loop_begin.us:
1773 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1774 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1775 ; CHECK-NEXT:    br label %inner_loop_a.us
1776 ;
1777 ; CHECK:       inner_loop_a.us:
1778 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1779 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_exit.split.us, label %inner_loop_begin.us
1780 ;
1781 ; CHECK:       inner_loop_exit.split.us:
1782 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_a.us ]
1783 ; CHECK-NEXT:    br label %inner_loop_exit
1784 ;
1785 ; The original remains a loop losing the exit edge.
1786 ;
1787 ; CHECK:       inner_loop_ph.split:
1788 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ]
1789 ; CHECK-NEXT:    br label %inner_loop_begin
1790 ;
1791 ; CHECK:       inner_loop_begin:
1792 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1793 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1794 ; CHECK-NEXT:    br label %loop_exit.loopexit
1795
1796 inner_loop_exit:
1797   %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ]
1798   %v3 = load i1, i1* %ptr
1799   br i1 %v3, label %loop_latch, label %loop_exit
1800 ; CHECK:       inner_loop_exit:
1801 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1802 ; CHECK-NEXT:    br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1
1803
1804 loop_latch:
1805   br label %loop_begin
1806 ; CHECK:       loop_latch:
1807 ; CHECK-NEXT:    br label %loop_begin
1808
1809 loop_exit:
1810   %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ]
1811   ret i32 %a.lcssa
1812 ; CHECK:       loop_exit.loopexit:
1813 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ]
1814 ; CHECK-NEXT:    br label %loop_exit
1815 ;
1816 ; CHECK:       loop_exit.loopexit1:
1817 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ]
1818 ; CHECK-NEXT:    br label %loop_exit
1819 ;
1820 ; CHECK:       loop_exit:
1821 ; CHECK-NEXT:    %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[A_LCSSA_US]], %loop_exit.loopexit1 ]
1822 ; CHECK-NEXT:    ret i32 %[[A_PHI]]
1823 }
1824
1825 ; Like test11a, but checking that when the whole thing is wrapped in yet
1826 ; another loop, we correctly attribute the cloned preheader to that outermost
1827 ; loop rather than only handling the case where the preheader is not in any loop
1828 ; at all.
1829 define i32 @test12a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1830 ; CHECK-LABEL: @test12a(
1831 entry:
1832   br label %loop_begin
1833 ; CHECK-NEXT:  entry:
1834 ; CHECK-NEXT:    br label %loop_begin
1835
1836 loop_begin:
1837   br label %inner_loop_begin
1838 ; CHECK:       loop_begin:
1839 ; CHECK-NEXT:    br label %inner_loop_begin
1840
1841 inner_loop_begin:
1842   %b = load i32, i32* %b.ptr
1843   %v1 = load i1, i1* %ptr
1844   br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph
1845 ; CHECK:       inner_loop_begin:
1846 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1847 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1848 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
1849
1850 inner_inner_loop_ph:
1851   %cond = load i1, i1* %cond.ptr
1852   br label %inner_inner_loop_begin
1853 ; CHECK:       inner_inner_loop_ph:
1854 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1855 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
1856
1857 inner_inner_loop_begin:
1858   call void @sink1(i32 %b)
1859   %a = load i32, i32* %a.ptr
1860   br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_a
1861
1862 inner_inner_loop_a:
1863   %v2 = load i1, i1* %ptr
1864   br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin
1865 ; The cloned path doesn't actually loop and is an exit from the outer loop as
1866 ; well.
1867 ;
1868 ; CHECK:       inner_inner_loop_ph.split.us:
1869 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ]
1870 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1871 ;
1872 ; CHECK:       inner_inner_loop_begin.us:
1873 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1874 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1875 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit.split.us
1876 ;
1877 ; CHECK:       inner_loop_exit.loopexit.split.us:
1878 ; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin.us ]
1879 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
1880 ;
1881 ; The original remains a loop losing the exit edge.
1882 ;
1883 ; CHECK:       inner_inner_loop_ph.split:
1884 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1885 ;
1886 ; CHECK:       inner_inner_loop_begin:
1887 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1888 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1889 ; CHECK-NEXT:    br label %inner_inner_loop_a
1890 ;
1891 ; CHECK:       inner_inner_loop_a:
1892 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1893 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit, label %inner_inner_loop_begin
1894
1895 inner_inner_loop_exit:
1896   %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ]
1897   %v3 = load i1, i1* %ptr
1898   br i1 %v3, label %inner_loop_latch, label %inner_loop_exit
1899 ; CHECK:       inner_inner_loop_exit:
1900 ; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a ]
1901 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1902 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1
1903
1904 inner_loop_latch:
1905   br label %inner_loop_begin
1906 ; CHECK:       inner_loop_latch:
1907 ; CHECK-NEXT:    br label %inner_loop_begin
1908
1909 inner_loop_exit:
1910   %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ]
1911   %v4 = load i1, i1* %ptr
1912   br i1 %v4, label %loop_begin, label %loop_exit
1913 ; CHECK:       inner_loop_exit.loopexit:
1914 ; CHECK-NEXT:    br label %inner_loop_exit
1915 ;
1916 ; CHECK:       inner_loop_exit.loopexit1:
1917 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_exit ]
1918 ; CHECK-NEXT:    br label %inner_loop_exit
1919 ;
1920 ; CHECK:       inner_loop_exit:
1921 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit1 ]
1922 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1923 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
1924
1925 loop_exit:
1926   %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
1927   ret i32 %a.lcssa
1928 ; CHECK:       loop_exit:
1929 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
1930 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
1931 }
1932
1933 ; Like test11b, but checking that when the whole thing is wrapped in yet
1934 ; another loop, we correctly sink the preheader to the outermost loop rather
1935 ; than only handling the case where the preheader is completely removed from
1936 ; a loop.
1937 define i32 @test12b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) {
1938 ; CHECK-LABEL: @test12b(
1939 entry:
1940   br label %loop_begin
1941 ; CHECK-NEXT:  entry:
1942 ; CHECK-NEXT:    br label %loop_begin
1943
1944 loop_begin:
1945   br label %inner_loop_begin
1946 ; CHECK:       loop_begin:
1947 ; CHECK-NEXT:    br label %inner_loop_begin
1948
1949 inner_loop_begin:
1950   %b = load i32, i32* %b.ptr
1951   %v1 = load i1, i1* %ptr
1952   br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph
1953 ; CHECK:       inner_loop_begin:
1954 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
1955 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1956 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph
1957
1958 inner_inner_loop_ph:
1959   %cond = load i1, i1* %cond.ptr
1960   br label %inner_inner_loop_begin
1961 ; CHECK:       inner_inner_loop_ph:
1962 ; CHECK-NEXT:    %[[COND:.*]] = load i1, i1* %cond.ptr
1963 ; CHECK-NEXT:    br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split
1964
1965 inner_inner_loop_begin:
1966   call void @sink1(i32 %b)
1967   %a = load i32, i32* %a.ptr
1968   br i1 %cond, label %inner_inner_loop_a, label %inner_loop_exit
1969
1970 inner_inner_loop_a:
1971   %v2 = load i1, i1* %ptr
1972   br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin
1973 ; The cloned path continues to loop without the exit out of the entire nest.
1974 ;
1975 ; CHECK:       inner_inner_loop_ph.split.us:
1976 ; CHECK-NEXT:    br label %inner_inner_loop_begin.us
1977 ;
1978 ; CHECK:       inner_inner_loop_begin.us:
1979 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
1980 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
1981 ; CHECK-NEXT:    br label %inner_inner_loop_a.us
1982 ;
1983 ; CHECK:       inner_inner_loop_a.us:
1984 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
1985 ; CHECK-NEXT:    br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_begin.us
1986 ;
1987 ; CHECK:       inner_inner_loop_exit.split.us:
1988 ; CHECK-NEXT:    %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a.us ]
1989 ; CHECK-NEXT:    br label %inner_inner_loop_exit
1990 ;
1991 ; The original remains a loop losing the exit edge.
1992 ;
1993 ; CHECK:       inner_inner_loop_ph.split:
1994 ; CHECK-NEXT:    %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ]
1995 ; CHECK-NEXT:    br label %inner_inner_loop_begin
1996 ;
1997 ; CHECK:       inner_inner_loop_begin:
1998 ; CHECK-NEXT:    call void @sink1(i32 %[[B_LCSSA]])
1999 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2000 ; CHECK-NEXT:    br label %inner_loop_exit.loopexit
2001
2002 inner_inner_loop_exit:
2003   %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ]
2004   %v3 = load i1, i1* %ptr
2005   br i1 %v3, label %inner_loop_latch, label %inner_loop_exit
2006 ; CHECK:       inner_inner_loop_exit:
2007 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2008 ; CHECK-NEXT:    br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1
2009
2010 inner_loop_latch:
2011   br label %inner_loop_begin
2012 ; CHECK:       inner_loop_latch:
2013 ; CHECK-NEXT:    br label %inner_loop_begin
2014
2015 inner_loop_exit:
2016   %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ]
2017   %v4 = load i1, i1* %ptr
2018   br i1 %v4, label %loop_begin, label %loop_exit
2019 ; CHECK:       inner_loop_exit.loopexit:
2020 ; CHECK-NEXT:    %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin ]
2021 ; CHECK-NEXT:    br label %inner_loop_exit
2022 ;
2023 ; CHECK:       inner_loop_exit.loopexit1:
2024 ; CHECK-NEXT:    %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_inner_loop_exit ]
2025 ; CHECK-NEXT:    br label %inner_loop_exit
2026 ;
2027 ; CHECK:       inner_loop_exit:
2028 ; CHECK-NEXT:    %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit1 ]
2029 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2030 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit
2031
2032 loop_exit:
2033   %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ]
2034   ret i32 %a.lcssa
2035 ; CHECK:       loop_exit:
2036 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ]
2037 ; CHECK-NEXT:    ret i32 %[[A_LCSSA]]
2038 }
2039
2040 ; Test where the cloned loop has an inner loop that has to be traversed to form
2041 ; the cloned loop, and where this inner loop has multiple blocks, and where the
2042 ; exiting block that connects the inner loop to the cloned loop is not the header
2043 ; block. This ensures that we correctly handle interesting corner cases of
2044 ; traversing back to the header when establishing the cloned loop.
2045 define i32 @test13a(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
2046 ; CHECK-LABEL: @test13a(
2047 entry:
2048   br label %loop_begin
2049 ; CHECK-NEXT:  entry:
2050 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
2051
2052 loop_begin:
2053   %a = load i32, i32* %a.ptr
2054   %v1 = load i1, i1* %ptr
2055   br i1 %v1, label %loop_a, label %loop_b
2056
2057 loop_a:
2058   %v2 = load i1, i1* %ptr
2059   br i1 %v2, label %loop_exit, label %loop_latch
2060
2061 loop_b:
2062   %b = load i32, i32* %b.ptr
2063   br i1 %cond, label %loop_b_inner_ph, label %loop_exit
2064
2065 loop_b_inner_ph:
2066   br label %loop_b_inner_header
2067
2068 loop_b_inner_header:
2069   %v3 = load i1, i1* %ptr
2070   br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body
2071
2072 loop_b_inner_body:
2073   %v4 = load i1, i1* %ptr
2074   br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit
2075
2076 loop_b_inner_latch:
2077   br label %loop_b_inner_header
2078
2079 loop_b_inner_exit:
2080   br label %loop_latch
2081
2082 loop_latch:
2083   br label %loop_begin
2084 ; The cloned loop contains an inner loop within it.
2085 ;
2086 ; CHECK:       entry.split.us:
2087 ; CHECK-NEXT:    br label %loop_begin.us
2088 ;
2089 ; CHECK:       loop_begin.us:
2090 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2091 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2092 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
2093 ;
2094 ; CHECK:       loop_b.us:
2095 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2096 ; CHECK-NEXT:    br label %loop_b_inner_ph.us
2097 ;
2098 ; CHECK:       loop_b_inner_ph.us:
2099 ; CHECK-NEXT:    br label %loop_b_inner_header.us
2100 ;
2101 ; CHECK:       loop_b_inner_header.us:
2102 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2103 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_body.us
2104 ;
2105 ; CHECK:       loop_b_inner_body.us:
2106 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2107 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_exit.us
2108 ;
2109 ; CHECK:       loop_b_inner_exit.us:
2110 ; CHECK-NEXT:    br label %loop_latch.us
2111 ;
2112 ; CHECK:       loop_b_inner_latch.us:
2113 ; CHECK-NEXT:    br label %loop_b_inner_header.us
2114 ;
2115 ; CHECK:       loop_a.us:
2116 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2117 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us, label %loop_latch.us
2118 ;
2119 ; CHECK:       loop_latch.us:
2120 ; CHECK-NEXT:    br label %loop_begin.us
2121 ;
2122 ; CHECK:       loop_exit.split.us:
2123 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
2124 ; CHECK-NEXT:    br label %loop_exit
2125 ;
2126 ; And the original loop no longer contains an inner loop.
2127 ;
2128 ; CHECK:       entry.split:
2129 ; CHECK-NEXT:    br label %loop_begin
2130 ;
2131 ; CHECK:       loop_begin:
2132 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2133 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2134 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
2135 ;
2136 ; CHECK:       loop_a:
2137 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2138 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.loopexit, label %loop_latch
2139 ;
2140 ; CHECK:       loop_b:
2141 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2142 ; CHECK-NEXT:    br label %loop_exit.split
2143 ;
2144 ; CHECK:       loop_latch:
2145 ; CHECK-NEXT:    br label %loop_begin
2146
2147 loop_exit:
2148   %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
2149   ret i32 %lcssa
2150 ; CHECK:       loop_exit.split.loopexit:
2151 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
2152 ; CHECK-NEXT:    br label %loop_exit.split
2153 ;
2154 ; CHECK:       loop_exit.split:
2155 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[B]], %loop_b ], [ %[[A_LCSSA]], %loop_exit.split.loopexit ]
2156 ; CHECK-NEXT:    br label %loop_exit
2157 ;
2158 ; CHECK:       loop_exit:
2159 ; CHECK-NEXT:    %[[AB_PHI_US:.*]] = phi i32 [ %[[AB_PHI]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ]
2160 ; CHECK-NEXT:    ret i32 %[[AB_PHI_US]]
2161 }
2162
2163 ; Test where the original loop has an inner loop that has to be traversed to
2164 ; rebuild the loop, and where this inner loop has multiple blocks, and where
2165 ; the exiting block that connects the inner loop to the original loop is not
2166 ; the header block. This ensures that we correctly handle interesting corner
2167 ; cases of traversing back to the header when re-establishing the original loop
2168 ; still exists after unswitching.
2169 define i32 @test13b(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) {
2170 ; CHECK-LABEL: @test13b(
2171 entry:
2172   br label %loop_begin
2173 ; CHECK-NEXT:  entry:
2174 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
2175
2176 loop_begin:
2177   %a = load i32, i32* %a.ptr
2178   %v1 = load i1, i1* %ptr
2179   br i1 %v1, label %loop_a, label %loop_b
2180
2181 loop_a:
2182   %v2 = load i1, i1* %ptr
2183   br i1 %v2, label %loop_exit, label %loop_latch
2184
2185 loop_b:
2186   %b = load i32, i32* %b.ptr
2187   br i1 %cond, label %loop_exit, label %loop_b_inner_ph
2188
2189 loop_b_inner_ph:
2190   br label %loop_b_inner_header
2191
2192 loop_b_inner_header:
2193   %v3 = load i1, i1* %ptr
2194   br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body
2195
2196 loop_b_inner_body:
2197   %v4 = load i1, i1* %ptr
2198   br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit
2199
2200 loop_b_inner_latch:
2201   br label %loop_b_inner_header
2202
2203 loop_b_inner_exit:
2204   br label %loop_latch
2205
2206 loop_latch:
2207   br label %loop_begin
2208 ; The cloned loop doesn't contain an inner loop.
2209 ;
2210 ; CHECK:       entry.split.us:
2211 ; CHECK-NEXT:    br label %loop_begin.us
2212 ;
2213 ; CHECK:       loop_begin.us:
2214 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2215 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2216 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a.us, label %loop_b.us
2217 ;
2218 ; CHECK:       loop_b.us:
2219 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2220 ; CHECK-NEXT:    br label %loop_exit.split.us
2221 ;
2222 ; CHECK:       loop_a.us:
2223 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2224 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_latch.us
2225 ;
2226 ; CHECK:       loop_latch.us:
2227 ; CHECK-NEXT:    br label %loop_begin.us
2228 ;
2229 ; CHECK:       loop_exit.split.us.loopexit:
2230 ; CHECK-NEXT:    %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ]
2231 ; CHECK-NEXT:    br label %loop_exit.split.us
2232 ;
2233 ; CHECK:       loop_exit.split.us:
2234 ; CHECK-NEXT:    %[[AB_PHI_US:.*]] = phi i32 [ %[[B]], %loop_b.us ], [ %[[A_LCSSA_US]], %loop_exit.split.us.loopexit ]
2235 ; CHECK-NEXT:    br label %loop_exit
2236 ;
2237 ; But the original loop contains an inner loop that must be traversed.;
2238 ;
2239 ; CHECK:       entry.split:
2240 ; CHECK-NEXT:    br label %loop_begin
2241 ;
2242 ; CHECK:       loop_begin:
2243 ; CHECK-NEXT:    %[[A:.*]] = load i32, i32* %a.ptr
2244 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2245 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a, label %loop_b
2246 ;
2247 ; CHECK:       loop_a:
2248 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2249 ; CHECK-NEXT:    br i1 %[[V]], label %loop_exit.split, label %loop_latch
2250 ;
2251 ; CHECK:       loop_b:
2252 ; CHECK-NEXT:    %[[B:.*]] = load i32, i32* %b.ptr
2253 ; CHECK-NEXT:    br label %loop_b_inner_ph
2254 ;
2255 ; CHECK:       loop_b_inner_ph:
2256 ; CHECK-NEXT:    br label %loop_b_inner_header
2257 ;
2258 ; CHECK:       loop_b_inner_header:
2259 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2260 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_body
2261 ;
2262 ; CHECK:       loop_b_inner_body:
2263 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2264 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_exit
2265 ;
2266 ; CHECK:       loop_b_inner_latch:
2267 ; CHECK-NEXT:    br label %loop_b_inner_header
2268 ;
2269 ; CHECK:       loop_b_inner_exit:
2270 ; CHECK-NEXT:    br label %loop_latch
2271 ;
2272 ; CHECK:       loop_latch:
2273 ; CHECK-NEXT:    br label %loop_begin
2274
2275 loop_exit:
2276   %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ]
2277   ret i32 %lcssa
2278 ; CHECK:       loop_exit.split:
2279 ; CHECK-NEXT:    %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ]
2280 ; CHECK-NEXT:    br label %loop_exit
2281 ;
2282 ; CHECK:       loop_exit:
2283 ; CHECK-NEXT:    %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[AB_PHI_US]], %loop_exit.split.us ]
2284 ; CHECK-NEXT:    ret i32 %[[AB_PHI]]
2285 }
2286
2287 define i32 @test20(i32* %var, i32 %cond1, i32 %cond2) {
2288 ; CHECK-LABEL: @test20(
2289 entry:
2290   br label %loop_begin
2291 ; CHECK-NEXT:  entry:
2292 ; CHECK-NEXT:    switch i32 %cond2, label %[[ENTRY_SPLIT_EXIT:.*]] [
2293 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
2294 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
2295 ; CHECK-NEXT:      i32 13, label %[[ENTRY_SPLIT_B:.*]]
2296 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_A]]
2297 ; CHECK-NEXT:      i32 42, label %[[ENTRY_SPLIT_C:.*]]
2298 ; CHECK-NEXT:    ]
2299
2300 loop_begin:
2301   %var_val = load i32, i32* %var
2302   switch i32 %cond2, label %loop_exit [
2303     i32 0, label %loop_a
2304     i32 1, label %loop_a
2305     i32 13, label %loop_b
2306     i32 2, label %loop_a
2307     i32 42, label %loop_c
2308   ]
2309
2310 loop_a:
2311   call i32 @a()
2312   br label %loop_latch
2313 ; Unswitched 'a' loop.
2314 ;
2315 ; CHECK:       [[ENTRY_SPLIT_A]]:
2316 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_A:.*]]
2317 ;
2318 ; CHECK:       [[LOOP_BEGIN_A]]:
2319 ; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2320 ; CHECK-NEXT:    br label %[[LOOP_A:.*]]
2321 ;
2322 ; CHECK:       [[LOOP_A]]:
2323 ; CHECK-NEXT:    call i32 @a()
2324 ; CHECK-NEXT:    br label %[[LOOP_LATCH_A:.*]]
2325 ;
2326 ; CHECK:       [[LOOP_LATCH_A]]:
2327 ; CHECK:         br label %[[LOOP_BEGIN_A]]
2328
2329 loop_b:
2330   call i32 @b()
2331   br label %loop_latch
2332 ; Unswitched 'b' loop.
2333 ;
2334 ; CHECK:       [[ENTRY_SPLIT_B]]:
2335 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_B:.*]]
2336 ;
2337 ; CHECK:       [[LOOP_BEGIN_B]]:
2338 ; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2339 ; CHECK-NEXT:    br label %[[LOOP_B:.*]]
2340 ;
2341 ; CHECK:       [[LOOP_B]]:
2342 ; CHECK-NEXT:    call i32 @b()
2343 ; CHECK-NEXT:    br label %[[LOOP_LATCH_B:.*]]
2344 ;
2345 ; CHECK:       [[LOOP_LATCH_B]]:
2346 ; CHECK:         br label %[[LOOP_BEGIN_B]]
2347
2348 loop_c:
2349   call i32 @c() noreturn nounwind
2350   br label %loop_latch
2351 ; Unswitched 'c' loop.
2352 ;
2353 ; CHECK:       [[ENTRY_SPLIT_C]]:
2354 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_C:.*]]
2355 ;
2356 ; CHECK:       [[LOOP_BEGIN_C]]:
2357 ; CHECK-NEXT:    %{{.*}} = load i32, i32* %var
2358 ; CHECK-NEXT:    br label %[[LOOP_C:.*]]
2359 ;
2360 ; CHECK:       [[LOOP_C]]:
2361 ; CHECK-NEXT:    call i32 @c()
2362 ; CHECK-NEXT:    br label %[[LOOP_LATCH_C:.*]]
2363 ;
2364 ; CHECK:       [[LOOP_LATCH_C]]:
2365 ; CHECK:         br label %[[LOOP_BEGIN_C]]
2366
2367 loop_latch:
2368   br label %loop_begin
2369
2370 loop_exit:
2371   %lcssa = phi i32 [ %var_val, %loop_begin ]
2372   ret i32 %lcssa
2373 ; Unswitched exit edge (no longer a loop).
2374 ;
2375 ; CHECK:       [[ENTRY_SPLIT_EXIT]]:
2376 ; CHECK-NEXT:    br label %loop_begin
2377 ;
2378 ; CHECK:       loop_begin:
2379 ; CHECK-NEXT:    %[[V:.*]] = load i32, i32* %var
2380 ; CHECK-NEXT:    br label %loop_exit
2381 ;
2382 ; CHECK:       loop_exit:
2383 ; CHECK-NEXT:    %[[LCSSA:.*]] = phi i32 [ %[[V]], %loop_begin ]
2384 ; CHECK-NEXT:    ret i32 %[[LCSSA]]
2385 }
2386
2387 ; Negative test: we do not switch when the loop contains unstructured control
2388 ; flows as it would significantly complicate the process as novel loops might
2389 ; be formed, etc.
2390 define void @test_no_unswitch_unstructured_cfg(i1* %ptr, i1 %cond) {
2391 ; CHECK-LABEL: @test_no_unswitch_unstructured_cfg(
2392 entry:
2393   br label %loop_begin
2394
2395 loop_begin:
2396   br i1 %cond, label %loop_left, label %loop_right
2397
2398 loop_left:
2399   %v1 = load i1, i1* %ptr
2400   br i1 %v1, label %loop_right, label %loop_merge
2401
2402 loop_right:
2403   %v2 = load i1, i1* %ptr
2404   br i1 %v2, label %loop_left, label %loop_merge
2405
2406 loop_merge:
2407   %v3 = load i1, i1* %ptr
2408   br i1 %v3, label %loop_latch, label %loop_exit
2409
2410 loop_latch:
2411   br label %loop_begin
2412
2413 loop_exit:
2414   ret void
2415 }
2416
2417 ; A test reduced out of 403.gcc with interesting nested loops that trigger
2418 ; multiple unswitches. A key component of this test is that there are multiple
2419 ; paths to reach an inner loop after unswitching, and one of them is via the
2420 ; predecessors of the unswitched loop header. That can allow us to find the loop
2421 ; through multiple different paths.
2422 define void @test21(i1 %a, i1 %b) {
2423 ; CHECK-LABEL: @test21(
2424 bb:
2425   br label %bb3
2426 ; CHECK-NOT:     br i1 %a
2427 ;
2428 ; CHECK:         br i1 %a, label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]]
2429 ;
2430 ; CHECK-NOT:     br i1 %a
2431 ; CHECK-NOT:     br i1 %b
2432 ;
2433 ; CHECK:       [[BB_SPLIT]]:
2434 ; CHECK:         br i1 %b
2435 ;
2436 ; CHECK-NOT:     br i1 %a
2437 ; CHECK-NOT:     br i1 %b
2438
2439 bb3:
2440   %tmp1.0 = phi i32 [ 0, %bb ], [ %tmp1.3, %bb23 ]
2441   br label %bb7
2442
2443 bb7:
2444   %tmp.0 = phi i1 [ true, %bb3 ], [ false, %bb19 ]
2445   %tmp1.1 = phi i32 [ %tmp1.0, %bb3 ], [ %tmp1.2.lcssa, %bb19 ]
2446   br i1 %tmp.0, label %bb11.preheader, label %bb23
2447
2448 bb11.preheader:
2449   br i1 %a, label %bb19, label %bb14.lr.ph
2450
2451 bb14.lr.ph:
2452   br label %bb14
2453
2454 bb14:
2455   %tmp2.02 = phi i32 [ 0, %bb14.lr.ph ], [ 1, %bb14 ]
2456   br i1 %b, label %bb11.bb19_crit_edge, label %bb14
2457
2458 bb11.bb19_crit_edge:
2459   %split = phi i32 [ %tmp2.02, %bb14 ]
2460   br label %bb19
2461
2462 bb19:
2463   %tmp1.2.lcssa = phi i32 [ %split, %bb11.bb19_crit_edge ], [ %tmp1.1, %bb11.preheader ]
2464   %tmp21 = icmp eq i32 %tmp1.2.lcssa, 0
2465   br i1 %tmp21, label %bb23, label %bb7
2466
2467 bb23:
2468   %tmp1.3 = phi i32 [ %tmp1.2.lcssa, %bb19 ], [ %tmp1.1, %bb7 ]
2469   br label %bb3
2470 }
2471
2472 ; A test reduced out of 400.perlbench that when unswitching the `%stop`
2473 ; condition clones a loop nest outside of a containing loop. This excercises a
2474 ; different cloning path from our other test cases and in turn verifying the
2475 ; resulting structure can catch any failures to correctly clone these nested
2476 ; loops.
2477 declare void @f()
2478 declare void @g()
2479 declare i32 @h(i32 %arg)
2480 define void @test22(i32 %arg) {
2481 ; CHECK-LABEL: define void @test22(
2482 entry:
2483   br label %loop1.header
2484
2485 loop1.header:
2486   %stop = phi i1 [ true, %loop1.latch ], [ false, %entry ]
2487   %i = phi i32 [ %i.lcssa, %loop1.latch ], [ %arg, %entry ]
2488 ; CHECK:         %[[I:.*]] = phi i32 [ %{{.*}}, %loop1.latch ], [ %arg, %entry ]
2489   br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph
2490 ; CHECK:         br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph
2491
2492 loop1.body.loop2.ph:
2493   br label %loop2.header
2494 ; Just check that the we unswitched the key condition and that leads to the
2495 ; inner loop header.
2496 ;
2497 ; CHECK:       loop1.body.loop2.ph:
2498 ; CHECK-NEXT:    br i1 %stop, label %[[SPLIT_US:.*]], label %[[SPLIT:.*]]
2499 ;
2500 ; CHECK:       [[SPLIT_US]]:
2501 ; CHECK-NEXT:    br label %[[LOOP2_HEADER_US:.*]]
2502 ;
2503 ; CHECK:       [[LOOP2_HEADER_US]]:
2504 ; CHECK-NEXT:    %{{.*}} = phi i32 [ %[[I]], %[[SPLIT_US]] ]
2505 ;
2506 ; CHECK:       [[SPLIT]]:
2507 ; CHECK-NEXT:    br label %[[LOOP2_HEADER:.*]]
2508 ;
2509 ; CHECK:       [[LOOP2_HEADER]]:
2510 ; CHECK-NEXT:    %{{.*}} = phi i32 [ %[[I]], %[[SPLIT]] ]
2511
2512 loop2.header:
2513   %i.inner = phi i32 [ %i, %loop1.body.loop2.ph ], [ %i.next, %loop2.latch ]
2514   br label %loop3.header
2515
2516 loop3.header:
2517   %sw = call i32 @h(i32 %i.inner)
2518   switch i32 %sw, label %loop3.exit [
2519     i32 32, label %loop3.header
2520     i32 59, label %loop2.latch
2521     i32 36, label %loop1.latch
2522   ]
2523
2524 loop2.latch:
2525   %i.next = add i32 %i.inner, 1
2526   br i1 %stop, label %loop2.exit, label %loop2.header
2527
2528 loop1.latch:
2529   %i.lcssa = phi i32 [ %i.inner, %loop3.header ]
2530   br label %loop1.header
2531
2532 loop3.exit:
2533   call void @f()
2534   ret void
2535
2536 loop2.exit:
2537   call void @g()
2538   ret void
2539
2540 loop1.exit:
2541   call void @g()
2542   ret void
2543 }
2544
2545 ; Test that when we are unswitching and need to rebuild the loop block set we
2546 ; correctly skip past inner loops. We want to use the inner loop to efficiently
2547 ; skip whole subregions of the outer loop blocks but just because the header of
2548 ; the outer loop is also the preheader of an inner loop shouldn't confuse this
2549 ; walk.
2550 define void @test23(i1 %arg, i1* %ptr) {
2551 ; CHECK-LABEL: define void @test23(
2552 entry:
2553   br label %outer.header
2554 ; CHECK:       entry:
2555 ; CHECK-NEXT:    br i1 %arg,
2556 ;
2557 ; Just verify that we unswitched the correct bits. We should call `@f` twice in
2558 ; one unswitch and `@f` and then `@g` in the other.
2559 ; CHECK:         call void
2560 ; CHECK-SAME:              @f
2561 ; CHECK:         call void
2562 ; CHECK-SAME:              @f
2563 ;
2564 ; CHECK:         call void
2565 ; CHECK-SAME:              @f
2566 ; CHECK:         call void
2567 ; CHECK-SAME:              @g
2568
2569 outer.header:
2570   br label %inner.header
2571
2572 inner.header:
2573   call void @f()
2574   br label %inner.latch
2575
2576 inner.latch:
2577   %inner.cond = load i1, i1* %ptr
2578   br i1 %inner.cond, label %inner.header, label %outer.body
2579
2580 outer.body:
2581   br i1 %arg, label %outer.body.left, label %outer.body.right
2582
2583 outer.body.left:
2584   call void @f()
2585   br label %outer.latch
2586
2587 outer.body.right:
2588   call void @g()
2589   br label %outer.latch
2590
2591 outer.latch:
2592   %outer.cond = load i1, i1* %ptr
2593   br i1 %outer.cond, label %outer.header, label %exit
2594
2595 exit:
2596   ret void
2597 }
2598
2599 ; Non-trivial loop unswitching where there are two invariant conditions, but the
2600 ; second one is only in the cloned copy of the loop after unswitching.
2601 define i32 @test24(i1* %ptr, i1 %cond1, i1 %cond2) {
2602 ; CHECK-LABEL: @test24(
2603 entry:
2604   br label %loop_begin
2605 ; CHECK-NEXT:  entry:
2606 ; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
2607
2608 loop_begin:
2609   br i1 %cond1, label %loop_a, label %loop_b
2610
2611 loop_a:
2612   br i1 %cond2, label %loop_a_a, label %loop_a_c
2613 ; The second unswitched condition.
2614 ;
2615 ; CHECK:       entry.split.us:
2616 ; CHECK-NEXT:    br i1 %cond2, label %entry.split.us.split.us, label %entry.split.us.split
2617
2618 loop_a_a:
2619   call i32 @a()
2620   br label %latch
2621 ; The 'loop_a_a' unswitched loop.
2622 ;
2623 ; CHECK:       entry.split.us.split.us:
2624 ; CHECK-NEXT:    br label %loop_begin.us.us
2625 ;
2626 ; CHECK:       loop_begin.us.us:
2627 ; CHECK-NEXT:    br label %loop_a.us.us
2628 ;
2629 ; CHECK:       loop_a.us.us:
2630 ; CHECK-NEXT:    br label %loop_a_a.us.us
2631 ;
2632 ; CHECK:       loop_a_a.us.us:
2633 ; CHECK-NEXT:    call i32 @a()
2634 ; CHECK-NEXT:    br label %latch.us.us
2635 ;
2636 ; CHECK:       latch.us.us:
2637 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2638 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us.us, label %loop_exit.split.us.split.us
2639 ;
2640 ; CHECK:       loop_exit.split.us.split.us:
2641 ; CHECK-NEXT:    br label %loop_exit.split
2642
2643 loop_a_c:
2644   call i32 @c()
2645   br label %latch
2646 ; The 'loop_a_c' unswitched loop.
2647 ;
2648 ; CHECK:       entry.split.us.split:
2649 ; CHECK-NEXT:    br label %loop_begin.us
2650 ;
2651 ; CHECK:       loop_begin.us:
2652 ; CHECK-NEXT:    br label %loop_a.us
2653 ;
2654 ; CHECK:       loop_a.us:
2655 ; CHECK-NEXT:    br label %loop_a_c.us
2656 ;
2657 ; CHECK:       loop_a_c.us:
2658 ; CHECK-NEXT:    call i32 @c()
2659 ; CHECK-NEXT:    br label %latch
2660 ;
2661 ; CHECK:       latch.us:
2662 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2663 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us.split
2664 ;
2665 ; CHECK:       loop_exit.split.us.split:
2666 ; CHECK-NEXT:    br label %loop_exit.split
2667
2668 loop_b:
2669   call i32 @b()
2670   br label %latch
2671 ; The 'loop_b' unswitched loop.
2672 ;
2673 ; CHECK:       entry.split:
2674 ; CHECK-NEXT:    br label %loop_begin
2675 ;
2676 ; CHECK:       loop_begin:
2677 ; CHECK-NEXT:    br label %loop_b
2678 ;
2679 ; CHECK:       loop_b:
2680 ; CHECK-NEXT:    call i32 @b()
2681 ; CHECK-NEXT:    br label %latch
2682 ;
2683 ; CHECK:       latch:
2684 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
2685 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
2686 ;
2687 ; CHECK:       loop_exit.split:
2688 ; CHECK-NEXT:    br label %loop_exit
2689
2690 latch:
2691   %v = load i1, i1* %ptr
2692   br i1 %v, label %loop_begin, label %loop_exit
2693
2694 loop_exit:
2695   ret i32 0
2696 ; CHECK:       loop_exit:
2697 ; CHECK-NEXT:    ret
2698 }
2699
2700 ; Non-trivial partial loop unswitching of an invariant input to an 'or'.
2701 define i32 @test25(i1* %ptr, i1 %cond) {
2702 ; CHECK-LABEL: @test25(
2703 entry:
2704   br label %loop_begin
2705 ; CHECK-NEXT:  entry:
2706 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
2707
2708 loop_begin:
2709   %v1 = load i1, i1* %ptr
2710   %cond_or = or i1 %v1, %cond
2711   br i1 %cond_or, label %loop_a, label %loop_b
2712
2713 loop_a:
2714   call i32 @a()
2715   br label %latch
2716 ; The 'loop_a' unswitched loop.
2717 ;
2718 ; CHECK:       entry.split.us:
2719 ; CHECK-NEXT:    br label %loop_begin.us
2720 ;
2721 ; CHECK:       loop_begin.us:
2722 ; CHECK-NEXT:    %[[V1_US:.*]] = load i1, i1* %ptr
2723 ; CHECK-NEXT:    %[[OR_US:.*]] = or i1 %[[V1_US]], true
2724 ; CHECK-NEXT:    br label %loop_a.us
2725 ;
2726 ; CHECK:       loop_a.us:
2727 ; CHECK-NEXT:    call i32 @a()
2728 ; CHECK-NEXT:    br label %latch.us
2729 ;
2730 ; CHECK:       latch.us:
2731 ; CHECK-NEXT:    %[[V2_US:.*]] = load i1, i1* %ptr
2732 ; CHECK-NEXT:    br i1 %[[V2_US]], label %loop_begin.us, label %loop_exit.split.us
2733 ;
2734 ; CHECK:       loop_exit.split.us:
2735 ; CHECK-NEXT:    br label %loop_exit
2736
2737 loop_b:
2738   call i32 @b()
2739   br label %latch
2740 ; The original loop.
2741 ;
2742 ; CHECK:       entry.split:
2743 ; CHECK-NEXT:    br label %loop_begin
2744 ;
2745 ; CHECK:       loop_begin:
2746 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr
2747 ; CHECK-NEXT:    %[[OR:.*]] = or i1 %[[V1]], false
2748 ; CHECK-NEXT:    br i1 %[[OR]], label %loop_a, label %loop_b
2749 ;
2750 ; CHECK:       loop_a:
2751 ; CHECK-NEXT:    call i32 @a()
2752 ; CHECK-NEXT:    br label %latch
2753 ;
2754 ; CHECK:       loop_b:
2755 ; CHECK-NEXT:    call i32 @b()
2756 ; CHECK-NEXT:    br label %latch
2757
2758 latch:
2759   %v2 = load i1, i1* %ptr
2760   br i1 %v2, label %loop_begin, label %loop_exit
2761 ; CHECK:       latch:
2762 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr
2763 ; CHECK-NEXT:    br i1 %[[V2]], label %loop_begin, label %loop_exit.split
2764
2765 loop_exit:
2766   ret i32 0
2767 ; CHECK:       loop_exit.split:
2768 ; CHECK-NEXT:    br label %loop_exit
2769 ;
2770 ; CHECK:       loop_exit:
2771 ; CHECK-NEXT:    ret
2772 }
2773
2774 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `and`
2775 ; chain.
2776 define i32 @test26(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2777 ; CHECK-LABEL: @test26(
2778 entry:
2779   br label %loop_begin
2780 ; CHECK-NEXT:  entry:
2781 ; CHECK-NEXT:    %[[INV_AND:.*]] = and i1 %cond3, %cond1
2782 ; CHECK-NEXT:    br i1 %[[INV_AND]], label %entry.split, label %entry.split.us
2783
2784 loop_begin:
2785   %v1 = load i1, i1* %ptr1
2786   %v2 = load i1, i1* %ptr2
2787   %cond_and1 = and i1 %v1, %cond1
2788   %cond_or1 = or i1 %v2, %cond2
2789   %cond_and2 = and i1 %cond_and1, %cond_or1
2790   %cond_and3 = and i1 %cond_and2, %cond3
2791   br i1 %cond_and3, label %loop_a, label %loop_b
2792 ; The 'loop_b' unswitched loop.
2793 ;
2794 ; CHECK:       entry.split.us:
2795 ; CHECK-NEXT:    br label %loop_begin.us
2796 ;
2797 ; CHECK:       loop_begin.us:
2798 ; CHECK-NEXT:    %[[V1_US:.*]] = load i1, i1* %ptr1
2799 ; CHECK-NEXT:    %[[V2_US:.*]] = load i1, i1* %ptr2
2800 ; CHECK-NEXT:    %[[AND1_US:.*]] = and i1 %[[V1_US]], %cond1
2801 ; CHECK-NEXT:    %[[OR1_US:.*]] = or i1 %[[V2_US]], %cond2
2802 ; CHECK-NEXT:    %[[AND2_US:.*]] = and i1 %[[AND1_US]], %[[OR1_US]]
2803 ; CHECK-NEXT:    %[[AND3_US:.*]] = and i1 %[[AND2_US]], %cond3
2804 ; CHECK-NEXT:    br label %loop_b.us
2805 ;
2806 ; CHECK:       loop_b.us:
2807 ; CHECK-NEXT:    call i32 @b()
2808 ; CHECK-NEXT:    br label %latch.us
2809 ;
2810 ; CHECK:       latch.us:
2811 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2812 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2813 ;
2814 ; CHECK:       loop_exit.split.us:
2815 ; CHECK-NEXT:    br label %loop_exit
2816
2817 ; The original loop.
2818 ;
2819 ; CHECK:       entry.split:
2820 ; CHECK-NEXT:    br label %loop_begin
2821 ;
2822 ; CHECK:       loop_begin:
2823 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2824 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2825 ; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V1]], true
2826 ; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V2]], %cond2
2827 ; CHECK-NEXT:    %[[AND2:.*]] = and i1 %[[AND1]], %[[OR1]]
2828 ; CHECK-NEXT:    %[[AND3:.*]] = and i1 %[[AND2]], true
2829 ; CHECK-NEXT:    br i1 %[[AND3]], label %loop_a, label %loop_b
2830
2831 loop_a:
2832   call i32 @a()
2833   br label %latch
2834 ; CHECK:       loop_a:
2835 ; CHECK-NEXT:    call i32 @a()
2836 ; CHECK-NEXT:    br label %latch
2837
2838 loop_b:
2839   call i32 @b()
2840   br label %latch
2841 ; CHECK:       loop_b:
2842 ; CHECK-NEXT:    call i32 @b()
2843 ; CHECK-NEXT:    br label %latch
2844
2845 latch:
2846   %v3 = load i1, i1* %ptr3
2847   br i1 %v3, label %loop_begin, label %loop_exit
2848 ; CHECK:       latch:
2849 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2850 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2851
2852 loop_exit:
2853   ret i32 0
2854 ; CHECK:       loop_exit.split:
2855 ; CHECK-NEXT:    br label %loop_exit
2856 ;
2857 ; CHECK:       loop_exit:
2858 ; CHECK-NEXT:    ret
2859 }
2860
2861 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `or`
2862 ; chain. Basically an inverted version of corresponding `and` test (test26).
2863 define i32 @test27(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2864 ; CHECK-LABEL: @test27(
2865 entry:
2866   br label %loop_begin
2867 ; CHECK-NEXT:  entry:
2868 ; CHECK-NEXT:    %[[INV_OR:.*]] = or i1 %cond3, %cond1
2869 ; CHECK-NEXT:    br i1 %[[INV_OR]], label %entry.split.us, label %entry.split
2870
2871 loop_begin:
2872   %v1 = load i1, i1* %ptr1
2873   %v2 = load i1, i1* %ptr2
2874   %cond_or1 = or i1 %v1, %cond1
2875   %cond_and1 = and i1 %v2, %cond2
2876   %cond_or2 = or i1 %cond_or1, %cond_and1
2877   %cond_or3 = or i1 %cond_or2, %cond3
2878   br i1 %cond_or3, label %loop_b, label %loop_a
2879 ; The 'loop_b' unswitched loop.
2880 ;
2881 ; CHECK:       entry.split.us:
2882 ; CHECK-NEXT:    br label %loop_begin.us
2883 ;
2884 ; CHECK:       loop_begin.us:
2885 ; CHECK-NEXT:    %[[V1_US:.*]] = load i1, i1* %ptr1
2886 ; CHECK-NEXT:    %[[V2_US:.*]] = load i1, i1* %ptr2
2887 ; CHECK-NEXT:    %[[OR1_US:.*]] = or i1 %[[V1_US]], %cond1
2888 ; CHECK-NEXT:    %[[AND1_US:.*]] = and i1 %[[V2_US]], %cond2
2889 ; CHECK-NEXT:    %[[OR2_US:.*]] = or i1 %[[OR1_US]], %[[AND1_US]]
2890 ; CHECK-NEXT:    %[[OR3_US:.*]] = or i1 %[[OR2_US]], %cond3
2891 ; CHECK-NEXT:    br label %loop_b.us
2892 ;
2893 ; CHECK:       loop_b.us:
2894 ; CHECK-NEXT:    call i32 @b()
2895 ; CHECK-NEXT:    br label %latch.us
2896 ;
2897 ; CHECK:       latch.us:
2898 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2899 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2900 ;
2901 ; CHECK:       loop_exit.split.us:
2902 ; CHECK-NEXT:    br label %loop_exit
2903
2904 ; The original loop.
2905 ;
2906 ; CHECK:       entry.split:
2907 ; CHECK-NEXT:    br label %loop_begin
2908 ;
2909 ; CHECK:       loop_begin:
2910 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2911 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2912 ; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V1]], false
2913 ; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V2]], %cond2
2914 ; CHECK-NEXT:    %[[OR2:.*]] = or i1 %[[OR1]], %[[AND1]]
2915 ; CHECK-NEXT:    %[[OR3:.*]] = or i1 %[[OR2]], false
2916 ; CHECK-NEXT:    br i1 %[[OR3]], label %loop_b, label %loop_a
2917
2918 loop_a:
2919   call i32 @a()
2920   br label %latch
2921 ; CHECK:       loop_a:
2922 ; CHECK-NEXT:    call i32 @a()
2923 ; CHECK-NEXT:    br label %latch
2924
2925 loop_b:
2926   call i32 @b()
2927   br label %latch
2928 ; CHECK:       loop_b:
2929 ; CHECK-NEXT:    call i32 @b()
2930 ; CHECK-NEXT:    br label %latch
2931
2932 latch:
2933   %v3 = load i1, i1* %ptr3
2934   br i1 %v3, label %loop_begin, label %loop_exit
2935 ; CHECK:       latch:
2936 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2937 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2938
2939 loop_exit:
2940   ret i32 0
2941 ; CHECK:       loop_exit.split:
2942 ; CHECK-NEXT:    br label %loop_exit
2943 ;
2944 ; CHECK:       loop_exit:
2945 ; CHECK-NEXT:    ret
2946 }
2947
2948 ; Non-trivial unswitching of a switch.
2949 define i32 @test28(i1* %ptr, i32 %cond) {
2950 ; CHECK-LABEL: @test28(
2951 entry:
2952   br label %loop_begin
2953 ; CHECK-NEXT:  entry:
2954 ; CHECK-NEXT:    switch i32 %cond, label %[[ENTRY_SPLIT_LATCH:.*]] [
2955 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
2956 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
2957 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_C:.*]]
2958 ; CHECK-NEXT:    ]
2959
2960 loop_begin:
2961   switch i32 %cond, label %latch [
2962     i32 0, label %loop_a
2963     i32 1, label %loop_b
2964     i32 2, label %loop_c
2965   ]
2966
2967 loop_a:
2968   call i32 @a()
2969   br label %latch
2970 ; Unswitched 'a' loop.
2971 ;
2972 ; CHECK:       [[ENTRY_SPLIT_A]]:
2973 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_A:.*]]
2974 ;
2975 ; CHECK:       [[LOOP_BEGIN_A]]:
2976 ; CHECK-NEXT:    br label %[[LOOP_A:.*]]
2977 ;
2978 ; CHECK:       [[LOOP_A]]:
2979 ; CHECK-NEXT:    call i32 @a()
2980 ; CHECK-NEXT:    br label %[[LOOP_LATCH_A:.*]]
2981 ;
2982 ; CHECK:       [[LOOP_LATCH_A]]:
2983 ; CHECK-NEXT:    %[[V_A:.*]] = load i1, i1* %ptr
2984 ; CHECK:         br i1 %[[V_A]], label %[[LOOP_BEGIN_A]], label %[[LOOP_EXIT_A:.*]]
2985 ;
2986 ; CHECK:       [[LOOP_EXIT_A]]:
2987 ; CHECK-NEXT:    br label %loop_exit
2988
2989 loop_b:
2990   call i32 @b()
2991   br label %latch
2992 ; Unswitched 'b' loop.
2993 ;
2994 ; CHECK:       [[ENTRY_SPLIT_B]]:
2995 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_B:.*]]
2996 ;
2997 ; CHECK:       [[LOOP_BEGIN_B]]:
2998 ; CHECK-NEXT:    br label %[[LOOP_B:.*]]
2999 ;
3000 ; CHECK:       [[LOOP_B]]:
3001 ; CHECK-NEXT:    call i32 @b()
3002 ; CHECK-NEXT:    br label %[[LOOP_LATCH_B:.*]]
3003 ;
3004 ; CHECK:       [[LOOP_LATCH_B]]:
3005 ; CHECK-NEXT:    %[[V_B:.*]] = load i1, i1* %ptr
3006 ; CHECK:         br i1 %[[V_B]], label %[[LOOP_BEGIN_B]], label %[[LOOP_EXIT_B:.*]]
3007 ;
3008 ; CHECK:       [[LOOP_EXIT_B]]:
3009 ; CHECK-NEXT:    br label %loop_exit
3010
3011 loop_c:
3012   call i32 @c()
3013   br label %latch
3014 ; Unswitched 'c' loop.
3015 ;
3016 ; CHECK:       [[ENTRY_SPLIT_C]]:
3017 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_C:.*]]
3018 ;
3019 ; CHECK:       [[LOOP_BEGIN_C]]:
3020 ; CHECK-NEXT:    br label %[[LOOP_C:.*]]
3021 ;
3022 ; CHECK:       [[LOOP_C]]:
3023 ; CHECK-NEXT:    call i32 @c()
3024 ; CHECK-NEXT:    br label %[[LOOP_LATCH_C:.*]]
3025 ;
3026 ; CHECK:       [[LOOP_LATCH_C]]:
3027 ; CHECK-NEXT:    %[[V_C:.*]] = load i1, i1* %ptr
3028 ; CHECK:         br i1 %[[V_C]], label %[[LOOP_BEGIN_C]], label %[[LOOP_EXIT_C:.*]]
3029 ;
3030 ; CHECK:       [[LOOP_EXIT_C]]:
3031 ; CHECK-NEXT:    br label %loop_exit
3032
3033 latch:
3034   %v = load i1, i1* %ptr
3035   br i1 %v, label %loop_begin, label %loop_exit
3036 ; Unswitched the 'latch' only loop.
3037 ;
3038 ; CHECK:       [[ENTRY_SPLIT_LATCH]]:
3039 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_LATCH:.*]]
3040 ;
3041 ; CHECK:       [[LOOP_BEGIN_LATCH]]:
3042 ; CHECK-NEXT:    br label %[[LOOP_LATCH_LATCH:.*]]
3043 ;
3044 ; CHECK:       [[LOOP_LATCH_LATCH]]:
3045 ; CHECK-NEXT:    %[[V_LATCH:.*]] = load i1, i1* %ptr
3046 ; CHECK:         br i1 %[[V_LATCH]], label %[[LOOP_BEGIN_LATCH]], label %[[LOOP_EXIT_LATCH:.*]]
3047 ;
3048 ; CHECK:       [[LOOP_EXIT_LATCH]]:
3049 ; CHECK-NEXT:    br label %loop_exit
3050
3051 loop_exit:
3052   ret i32 0
3053 ; CHECK:       loop_exit:
3054 ; CHECK-NEXT:    ret i32 0
3055 }
3056
3057 ; A test case designed to exercise unusual properties of switches: they
3058 ; can introduce multiple edges to successors. These need lots of special case
3059 ; handling as they get collapsed in many cases (domtree, the unswitch itself)
3060 ; but not in all cases (the PHI node operands).
3061 define i32 @test29(i32 %arg) {
3062 ; CHECK-LABEL: @test29(
3063 entry:
3064   br label %header
3065 ; CHECK-NEXT:  entry:
3066 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_C:.*]] [
3067 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3068 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
3069 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B:.*]]
3070 ; CHECK-NEXT:      i32 3, label %[[ENTRY_SPLIT_C]]
3071 ; CHECK-NEXT:    ]
3072
3073 header:
3074   %tmp = call i32 @d()
3075   %cmp1 = icmp eq i32 %tmp, 0
3076   ; We set up a chain through all the successors of the switch that doesn't
3077   ; involve the switch so that we can have interesting PHI nodes in them.
3078   br i1 %cmp1, label %body.a, label %dispatch
3079
3080 dispatch:
3081   ; Switch with multiple successors. We arrange the last successor to be the
3082   ; default to make the test case easier to read. This has a duplicate edge
3083   ; both to the default destination (which is completely superfluous but
3084   ; technically valid IR) and to a regular successor.
3085   switch i32 %arg, label %body.c [
3086     i32 0, label %body.a
3087     i32 1, label %body.a
3088     i32 2, label %body.b
3089     i32 3, label %body.c
3090   ]
3091
3092 body.a:
3093   %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3094   %tmp.a = call i32 @a()
3095   %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3096   br label %body.b
3097 ; Unswitched 'a' loop.
3098 ;
3099 ; CHECK:       [[ENTRY_SPLIT_A]]:
3100 ; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3101 ;
3102 ; CHECK:       [[HEADER_A]]:
3103 ; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3104 ; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3105 ; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3106 ;
3107 ; CHECK:       [[DISPATCH_A]]:
3108 ; CHECK-NEXT:    br label %[[BODY_A_A]]
3109 ;
3110 ; CHECK:       [[BODY_A_A]]:
3111 ; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3112 ; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3113 ; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3114 ; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3115 ;
3116 ; CHECK:       [[BODY_B_A]]:
3117 ; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3118 ; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3119 ; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3120 ; CHECK-NEXT:    br label %[[BODY_C_A:.*]]
3121 ;
3122 ; CHECK:       [[BODY_C_A]]:
3123 ; CHECK-NEXT:    %[[TMP_C_PHI_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[BODY_B_A]] ]
3124 ; CHECK-NEXT:    %[[TMP_C_A:.*]] = call i32 @c()
3125 ; CHECK-NEXT:    %[[TMP_C_SUM_A:.*]] = add i32 %[[TMP_C_PHI_A]], %[[TMP_C_A]]
3126 ; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3127 ;
3128 ; CHECK:       [[LATCH_A]]:
3129 ; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_C_SUM_A]], 42
3130 ; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3131 ;
3132 ; CHECK:       [[LOOP_EXIT_A]]:
3133 ; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_C_SUM_A]], %[[LATCH_A]] ]
3134 ; CHECK-NEXT:    br label %exit
3135
3136 body.b:
3137   %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3138   %tmp.b = call i32 @b()
3139   %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3140   br label %body.c
3141 ; Unswitched 'b' loop.
3142 ;
3143 ; CHECK:       [[ENTRY_SPLIT_B]]:
3144 ; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3145 ;
3146 ; CHECK:       [[HEADER_B]]:
3147 ; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3148 ; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3149 ; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3150 ;
3151 ; CHECK:       [[DISPATCH_B]]:
3152 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3153 ;
3154 ; CHECK:       [[BODY_A_B]]:
3155 ; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3156 ; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3157 ; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3158 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3159 ;
3160 ; CHECK:       [[BODY_B_B]]:
3161 ; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3162 ; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3163 ; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3164 ; CHECK-NEXT:    br label %[[BODY_C_B:.*]]
3165 ;
3166 ; CHECK:       [[BODY_C_B]]:
3167 ; CHECK-NEXT:    %[[TMP_C_PHI_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[BODY_B_B]] ]
3168 ; CHECK-NEXT:    %[[TMP_C_B:.*]] = call i32 @c()
3169 ; CHECK-NEXT:    %[[TMP_C_SUM_B:.*]] = add i32 %[[TMP_C_PHI_B]], %[[TMP_C_B]]
3170 ; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3171 ;
3172 ; CHECK:       [[LATCH_B]]:
3173 ; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_C_SUM_B]], 42
3174 ; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3175 ;
3176 ; CHECK:       [[LOOP_EXIT_B]]:
3177 ; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_C_SUM_B]], %[[LATCH_B]] ]
3178 ; CHECK-NEXT:    br label %[[EXIT_SPLIT:.*]]
3179
3180 body.c:
3181   %tmp.c.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.b.sum, %body.b ]
3182   %tmp.c = call i32 @c()
3183   %tmp.c.sum = add i32 %tmp.c.phi, %tmp.c
3184   br label %latch
3185 ; Unswitched 'c' loop.
3186 ;
3187 ; CHECK:       [[ENTRY_SPLIT_C]]:
3188 ; CHECK-NEXT:    br label %[[HEADER_C:.*]]
3189 ;
3190 ; CHECK:       [[HEADER_C]]:
3191 ; CHECK-NEXT:    %[[TMP_C:.*]] = call i32 @d()
3192 ; CHECK-NEXT:    %[[CMP1_C:.*]] = icmp eq i32 %[[TMP_C]], 0
3193 ; CHECK-NEXT:    br i1 %[[CMP1_C]], label %[[BODY_A_C:.*]], label %[[DISPATCH_C:.*]]
3194 ;
3195 ; CHECK:       [[DISPATCH_C]]:
3196 ; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3197 ;
3198 ; CHECK:       [[BODY_A_C]]:
3199 ; CHECK-NEXT:    %[[TMP_A_PHI_C:.*]] = phi i32 [ 0, %[[HEADER_C]] ]
3200 ; CHECK-NEXT:    %[[TMP_A_C:.*]] = call i32 @a()
3201 ; CHECK-NEXT:    %[[TMP_A_SUM_C:.*]] = add i32 %[[TMP_A_PHI_C]], %[[TMP_A_C]]
3202 ; CHECK-NEXT:    br label %[[BODY_B_C:.*]]
3203 ;
3204 ; CHECK:       [[BODY_B_C]]:
3205 ; CHECK-NEXT:    %[[TMP_B_PHI_C:.*]] = phi i32 [ %[[TMP_A_SUM_C]], %[[BODY_A_C]] ]
3206 ; CHECK-NEXT:    %[[TMP_B_C:.*]] = call i32 @b()
3207 ; CHECK-NEXT:    %[[TMP_B_SUM_C:.*]] = add i32 %[[TMP_B_PHI_C]], %[[TMP_B_C]]
3208 ; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3209 ;
3210 ; CHECK:       [[BODY_C_C]]:
3211 ; CHECK-NEXT:    %[[TMP_C_PHI_C:.*]] = phi i32 [ %[[TMP_C]], %[[DISPATCH_C]] ], [ %[[TMP_B_SUM_C]], %[[BODY_B_C]] ]
3212 ; CHECK-NEXT:    %[[TMP_C_C:.*]] = call i32 @c()
3213 ; CHECK-NEXT:    %[[TMP_C_SUM_C:.*]] = add i32 %[[TMP_C_PHI_C]], %[[TMP_C_C]]
3214 ; CHECK-NEXT:    br label %[[LATCH_C:.*]]
3215 ;
3216 ; CHECK:       [[LATCH_C]]:
3217 ; CHECK-NEXT:    %[[CMP2_C:.*]] = icmp slt i32 %[[TMP_C_SUM_C]], 42
3218 ; CHECK:         br i1 %[[CMP2_C]], label %[[HEADER_C]], label %[[LOOP_EXIT_C:.*]]
3219 ;
3220 ; CHECK:       [[LOOP_EXIT_C]]:
3221 ; CHECK-NEXT:    %[[LCSSA_C:.*]] = phi i32 [ %[[TMP_C_SUM_C]], %[[LATCH_C]] ]
3222 ; CHECK-NEXT:    br label %[[EXIT_SPLIT]]
3223
3224 latch:
3225   %cmp2 = icmp slt i32 %tmp.c.sum, 42
3226   br i1 %cmp2, label %header, label %exit
3227
3228 exit:
3229   %lcssa.phi = phi i32 [ %tmp.c.sum, %latch ]
3230   ret i32 %lcssa.phi
3231 ; CHECK:       [[EXIT_SPLIT]]:
3232 ; CHECK-NEXT:    %[[EXIT_PHI1:.*]] = phi i32 [ %[[LCSSA_C]], %[[LOOP_EXIT_C]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3233 ; CHECK-NEXT:    br label %exit
3234
3235 ; CHECK:       exit:
3236 ; CHECK-NEXT:    %[[EXIT_PHI2:.*]] = phi i32 [ %[[EXIT_PHI1]], %[[EXIT_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3237 ; CHECK-NEXT:    ret i32 %[[EXIT_PHI2]]
3238 }
3239
3240 ; Similar to @test29 but designed to have one of the duplicate edges be
3241 ; a loop exit edge as those can in some cases be special. Among other things,
3242 ; this includes an LCSSA phi with multiple entries despite being a dedicated
3243 ; exit block.
3244 define i32 @test30(i32 %arg) {
3245 ; CHECK-LABEL: define i32 @test30(
3246 entry:
3247   br label %header
3248 ; CHECK-NEXT:  entry:
3249 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_EXIT:.*]] [
3250 ; CHECK-NEXT:      i32 -1, label %[[ENTRY_SPLIT_EXIT]]
3251 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3252 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
3253 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B]]
3254 ; CHECK-NEXT:    ]
3255
3256 header:
3257   %tmp = call i32 @d()
3258   %cmp1 = icmp eq i32 %tmp, 0
3259   br i1 %cmp1, label %body.a, label %dispatch
3260
3261 dispatch:
3262   switch i32 %arg, label %loop.exit1 [
3263     i32 -1, label %loop.exit1
3264     i32 0, label %body.a
3265     i32 1, label %body.b
3266     i32 2, label %body.b
3267   ]
3268
3269 body.a:
3270   %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ]
3271   %tmp.a = call i32 @a()
3272   %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3273   br label %body.b
3274 ; Unswitched 'a' loop.
3275 ;
3276 ; CHECK:       [[ENTRY_SPLIT_A]]:
3277 ; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3278 ;
3279 ; CHECK:       [[HEADER_A]]:
3280 ; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3281 ; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3282 ; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3283 ;
3284 ; CHECK:       [[DISPATCH_A]]:
3285 ; CHECK-NEXT:    br label %[[BODY_A_A]]
3286 ;
3287 ; CHECK:       [[BODY_A_A]]:
3288 ; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3289 ; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3290 ; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3291 ; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3292 ;
3293 ; CHECK:       [[BODY_B_A]]:
3294 ; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3295 ; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3296 ; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3297 ; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3298 ;
3299 ; CHECK:       [[LATCH_A]]:
3300 ; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_B_SUM_A]], 42
3301 ; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3302 ;
3303 ; CHECK:       [[LOOP_EXIT_A]]:
3304 ; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[LATCH_A]] ]
3305 ; CHECK-NEXT:    br label %loop.exit2
3306
3307 body.b:
3308   %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3309   %tmp.b = call i32 @b()
3310   %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3311   br label %latch
3312 ; Unswitched 'b' loop.
3313 ;
3314 ; CHECK:       [[ENTRY_SPLIT_B]]:
3315 ; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3316 ;
3317 ; CHECK:       [[HEADER_B]]:
3318 ; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3319 ; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3320 ; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3321 ;
3322 ; CHECK:       [[DISPATCH_B]]:
3323 ; CHECK-NEXT:    br label %[[BODY_B_B]]
3324 ;
3325 ; CHECK:       [[BODY_A_B]]:
3326 ; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3327 ; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3328 ; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3329 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3330 ;
3331 ; CHECK:       [[BODY_B_B]]:
3332 ; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3333 ; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3334 ; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3335 ; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3336 ;
3337 ; CHECK:       [[LATCH_B]]:
3338 ; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_B_SUM_B]], 42
3339 ; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3340 ;
3341 ; CHECK:       [[LOOP_EXIT_B]]:
3342 ; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[LATCH_B]] ]
3343 ; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT:.*]]
3344
3345 latch:
3346   %cmp2 = icmp slt i32 %tmp.b.sum, 42
3347   br i1 %cmp2, label %header, label %loop.exit2
3348
3349 loop.exit1:
3350   %l1.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3351   br label %exit
3352 ; Unswitched 'exit' loop.
3353 ;
3354 ; CHECK:       [[ENTRY_SPLIT_EXIT]]:
3355 ; CHECK-NEXT:    br label %[[HEADER_EXIT:.*]]
3356 ;
3357 ; CHECK:       [[HEADER_EXIT]]:
3358 ; CHECK-NEXT:    %[[TMP_EXIT:.*]] = call i32 @d()
3359 ; CHECK-NEXT:    %[[CMP1_EXIT:.*]] = icmp eq i32 %[[TMP_EXIT]], 0
3360 ; CHECK-NEXT:    br i1 %[[CMP1_EXIT]], label %[[BODY_A_EXIT:.*]], label %[[DISPATCH_EXIT:.*]]
3361 ;
3362 ; CHECK:       [[DISPATCH_EXIT]]:
3363 ; CHECK-NEXT:    %[[TMP_LCSSA:.*]] = phi i32 [ %[[TMP_EXIT]], %[[HEADER_EXIT]] ]
3364 ; CHECK-NEXT:    br label %loop.exit1
3365 ;
3366 ; CHECK:       [[BODY_A_EXIT]]:
3367 ; CHECK-NEXT:    %[[TMP_A_PHI_EXIT:.*]] = phi i32 [ 0, %[[HEADER_EXIT]] ]
3368 ; CHECK-NEXT:    %[[TMP_A_EXIT:.*]] = call i32 @a()
3369 ; CHECK-NEXT:    %[[TMP_A_SUM_EXIT:.*]] = add i32 %[[TMP_A_PHI_EXIT]], %[[TMP_A_EXIT]]
3370 ; CHECK-NEXT:    br label %[[BODY_B_EXIT:.*]]
3371 ;
3372 ; CHECK:       [[BODY_B_EXIT]]:
3373 ; CHECK-NEXT:    %[[TMP_B_PHI_EXIT:.*]] = phi i32 [ %[[TMP_A_SUM_EXIT]], %[[BODY_A_EXIT]] ]
3374 ; CHECK-NEXT:    %[[TMP_B_EXIT:.*]] = call i32 @b()
3375 ; CHECK-NEXT:    %[[TMP_B_SUM_EXIT:.*]] = add i32 %[[TMP_B_PHI_EXIT]], %[[TMP_B_EXIT]]
3376 ; CHECK-NEXT:    br label %[[LATCH_EXIT:.*]]
3377 ;
3378 ; CHECK:       [[LATCH_EXIT]]:
3379 ; CHECK-NEXT:    %[[CMP2_EXIT:.*]] = icmp slt i32 %[[TMP_B_SUM_EXIT]], 42
3380 ; CHECK:         br i1 %[[CMP2_EXIT]], label %[[HEADER_EXIT]], label %[[LOOP_EXIT_EXIT:.*]]
3381 ;
3382 ; CHECK:       loop.exit1:
3383 ; CHECK-NEXT:    %[[L1_PHI:.*]] = phi i32 [ %[[TMP_LCSSA]], %[[DISPATCH_EXIT]] ]
3384 ; CHECK-NEXT:    br label %exit
3385 ;
3386 ; CHECK:       [[LOOP_EXIT_EXIT]]:
3387 ; CHECK-NEXT:    %[[L2_PHI:.*]] = phi i32 [ %[[TMP_B_SUM_EXIT]], %[[LATCH_EXIT]] ]
3388 ; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT]]
3389
3390 loop.exit2:
3391   %l2.phi = phi i32 [ %tmp.b.sum, %latch ]
3392   br label %exit
3393 ; CHECK:       [[LOOP_EXIT2_SPLIT]]:
3394 ; CHECK-NEXT:    %[[LOOP_EXIT_PHI1:.*]] = phi i32 [ %[[L2_PHI]], %[[LOOP_EXIT_EXIT]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3395 ; CHECK-NEXT:    br label %loop.exit2
3396 ;
3397 ; CHECK:       loop.exit2:
3398 ; CHECK-NEXT:    %[[LOOP_EXIT_PHI2:.*]] = phi i32 [ %[[LOOP_EXIT_PHI1]], %[[LOOP_EXIT2_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3399 ; CHECK-NEXT:    br label %exit
3400
3401 exit:
3402   %l.phi = phi i32 [ %l1.phi, %loop.exit1 ], [ %l2.phi, %loop.exit2 ]
3403   ret i32 %l.phi
3404 ; CHECK:       exit:
3405 ; CHECK-NEXT:    %[[EXIT_PHI:.*]] = phi i32 [ %[[L1_PHI]], %loop.exit1 ], [ %[[LOOP_EXIT_PHI2]], %loop.exit2 ]
3406 ; CHECK-NEXT:    ret i32 %[[EXIT_PHI]]
3407 }
3408
3409 ; Unswitch will not actually change the loop nest from:
3410 ;   A < B < C
3411 define void @hoist_inner_loop0() {
3412 ; CHECK-LABEL: define void @hoist_inner_loop0(
3413 entry:
3414   br label %a.header
3415 ; CHECK:       entry:
3416 ; CHECK-NEXT:    br label %a.header
3417
3418 a.header:
3419   br label %b.header
3420 ; CHECK:       a.header:
3421 ; CHECK-NEXT:    br label %b.header
3422
3423 b.header:
3424   %v1 = call i1 @cond()
3425   br label %c.header
3426 ; CHECK:       b.header:
3427 ; CHECK-NEXT:    %v1 = call i1 @cond()
3428 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3429 ;
3430 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3431 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3432 ;
3433 ; CHECK:       [[C_HEADER_US]]:
3434 ; CHECK-NEXT:    call i32 @c()
3435 ; CHECK-NEXT:    br label %[[B_LATCH_SPLIT_US:.*]]
3436 ;
3437 ; CHECK:       [[B_LATCH_SPLIT_US]]:
3438 ; CHECK-NEXT:    br label %b.latch
3439 ;
3440 ; CHECK:       [[B_HEADER_SPLIT]]:
3441 ; CHECK-NEXT:    br label %c.header
3442
3443 c.header:
3444   call i32 @c()
3445   br i1 %v1, label %b.latch, label %c.latch
3446 ; CHECK:       c.header:
3447 ; CHECK-NEXT:    call i32 @c()
3448 ; CHECK-NEXT:    br label %c.latch
3449
3450 c.latch:
3451   %v2 = call i1 @cond()
3452   br i1 %v2, label %c.header, label %b.latch
3453 ; CHECK:       c.latch:
3454 ; CHECK-NEXT:    %v2 = call i1 @cond()
3455 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]]
3456
3457 b.latch:
3458   %v3 = call i1 @cond()
3459   br i1 %v3, label %b.header, label %a.latch
3460 ; CHECK:       [[B_LATCH_SPLIT]]:
3461 ; CHECK-NEXT:    br label %b.latch
3462 ;
3463 ; CHECK:       b.latch:
3464 ; CHECK-NEXT:    %v3 = call i1 @cond()
3465 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3466
3467 a.latch:
3468   br label %a.header
3469 ; CHECK:       a.latch:
3470 ; CHECK-NEXT:    br label %a.header
3471
3472 exit:
3473   ret void
3474 ; CHECK:       exit:
3475 ; CHECK-NEXT:    ret void
3476 }
3477
3478 ; Unswitch will transform the loop nest from:
3479 ;   A < B < C
3480 ; into
3481 ;   A < (B, C)
3482 define void @hoist_inner_loop1(i32* %ptr) {
3483 ; CHECK-LABEL: define void @hoist_inner_loop1(
3484 entry:
3485   br label %a.header
3486 ; CHECK:       entry:
3487 ; CHECK-NEXT:    br label %a.header
3488
3489 a.header:
3490   %x.a = load i32, i32* %ptr
3491   br label %b.header
3492 ; CHECK:       a.header:
3493 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3494 ; CHECK-NEXT:    br label %b.header
3495
3496 b.header:
3497   %x.b = load i32, i32* %ptr
3498   %v1 = call i1 @cond()
3499   br label %c.header
3500 ; CHECK:       b.header:
3501 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3502 ; CHECK-NEXT:    %v1 = call i1 @cond()
3503 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3504 ;
3505 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3506 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3507 ;
3508 ; CHECK:       [[C_HEADER_US]]:
3509 ; CHECK-NEXT:    call i32 @c()
3510 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3511 ;
3512 ; CHECK:       [[B_LATCH_US]]:
3513 ; CHECK-NEXT:    br label %b.latch
3514 ;
3515 ; CHECK:       [[B_HEADER_SPLIT]]:
3516 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3517 ; CHECK-NEXT:    br label %c.header
3518
3519 c.header:
3520   call i32 @c()
3521   br i1 %v1, label %b.latch, label %c.latch
3522 ; CHECK:       c.header:
3523 ; CHECK-NEXT:    call i32 @c()
3524 ; CHECK-NEXT:    br label %c.latch
3525
3526 c.latch:
3527   ; Use values from other loops to check LCSSA form.
3528   store i32 %x.a, i32* %ptr
3529   store i32 %x.b, i32* %ptr
3530   %v2 = call i1 @cond()
3531   br i1 %v2, label %c.header, label %a.exit.c
3532 ; CHECK:       c.latch:
3533 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3534 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3535 ; CHECK-NEXT:    %v2 = call i1 @cond()
3536 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
3537
3538 b.latch:
3539   %v3 = call i1 @cond()
3540   br i1 %v3, label %b.header, label %a.exit.b
3541 ; CHECK:       b.latch:
3542 ; CHECK-NEXT:    %v3 = call i1 @cond()
3543 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
3544
3545 a.exit.c:
3546   br label %a.latch
3547 ; CHECK:       a.exit.c
3548 ; CHECK-NEXT:    br label %a.latch
3549
3550 a.exit.b:
3551   br label %a.latch
3552 ; CHECK:       a.exit.b:
3553 ; CHECK-NEXT:    br label %a.latch
3554
3555 a.latch:
3556   br label %a.header
3557 ; CHECK:       a.latch:
3558 ; CHECK-NEXT:    br label %a.header
3559
3560 exit:
3561   ret void
3562 ; CHECK:       exit:
3563 ; CHECK-NEXT:    ret void
3564 }
3565
3566 ; Unswitch will transform the loop nest from:
3567 ;   A < B < C
3568 ; into
3569 ;   (A < B), C
3570 define void @hoist_inner_loop2(i32* %ptr) {
3571 ; CHECK-LABEL: define void @hoist_inner_loop2(
3572 entry:
3573   br label %a.header
3574 ; CHECK:       entry:
3575 ; CHECK-NEXT:    br label %a.header
3576
3577 a.header:
3578   %x.a = load i32, i32* %ptr
3579   br label %b.header
3580 ; CHECK:       a.header:
3581 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3582 ; CHECK-NEXT:    br label %b.header
3583
3584 b.header:
3585   %x.b = load i32, i32* %ptr
3586   %v1 = call i1 @cond()
3587   br label %c.header
3588 ; CHECK:       b.header:
3589 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3590 ; CHECK-NEXT:    %v1 = call i1 @cond()
3591 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3592 ;
3593 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3594 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3595 ;
3596 ; CHECK:       [[C_HEADER_US]]:
3597 ; CHECK-NEXT:    call i32 @c()
3598 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3599 ;
3600 ; CHECK:       [[B_LATCH_US]]:
3601 ; CHECK-NEXT:    br label %b.latch
3602 ;
3603 ; CHECK:       [[B_HEADER_SPLIT]]:
3604 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3605 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3606 ; CHECK-NEXT:    br label %c.header
3607
3608 c.header:
3609   call i32 @c()
3610   br i1 %v1, label %b.latch, label %c.latch
3611 ; CHECK:       c.header:
3612 ; CHECK-NEXT:    call i32 @c()
3613 ; CHECK-NEXT:    br label %c.latch
3614
3615 c.latch:
3616   ; Use values from other loops to check LCSSA form.
3617   store i32 %x.a, i32* %ptr
3618   store i32 %x.b, i32* %ptr
3619   %v2 = call i1 @cond()
3620   br i1 %v2, label %c.header, label %exit
3621 ; CHECK:       c.latch:
3622 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3623 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3624 ; CHECK-NEXT:    %v2 = call i1 @cond()
3625 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
3626
3627 b.latch:
3628   %v3 = call i1 @cond()
3629   br i1 %v3, label %b.header, label %a.latch
3630 ; CHECK:       b.latch:
3631 ; CHECK-NEXT:    %v3 = call i1 @cond()
3632 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3633
3634 a.latch:
3635   br label %a.header
3636 ; CHECK:       a.latch:
3637 ; CHECK-NEXT:    br label %a.header
3638
3639 exit:
3640   ret void
3641 ; CHECK:       exit:
3642 ; CHECK-NEXT:    ret void
3643 }
3644
3645 ; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
3646 ; Unswitch will transform the loop nest from:
3647 ;   A < B < C < D
3648 ; into
3649 ;   (A < B), (C < D)
3650 define void @hoist_inner_loop3(i32* %ptr) {
3651 ; CHECK-LABEL: define void @hoist_inner_loop3(
3652 entry:
3653   br label %a.header
3654 ; CHECK:       entry:
3655 ; CHECK-NEXT:    br label %a.header
3656
3657 a.header:
3658   %x.a = load i32, i32* %ptr
3659   br label %b.header
3660 ; CHECK:       a.header:
3661 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3662 ; CHECK-NEXT:    br label %b.header
3663
3664 b.header:
3665   %x.b = load i32, i32* %ptr
3666   %v1 = call i1 @cond()
3667   br label %c.header
3668 ; CHECK:       b.header:
3669 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3670 ; CHECK-NEXT:    %v1 = call i1 @cond()
3671 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3672 ;
3673 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3674 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3675 ;
3676 ; CHECK:       [[C_HEADER_US]]:
3677 ; CHECK-NEXT:    call i32 @c()
3678 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3679 ;
3680 ; CHECK:       [[B_LATCH_US]]:
3681 ; CHECK-NEXT:    br label %b.latch
3682 ;
3683 ; CHECK:       [[B_HEADER_SPLIT]]:
3684 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3685 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3686 ; CHECK-NEXT:    br label %c.header
3687
3688 c.header:
3689   call i32 @c()
3690   br i1 %v1, label %b.latch, label %c.body
3691 ; CHECK:       c.header:
3692 ; CHECK-NEXT:    call i32 @c()
3693 ; CHECK-NEXT:    br label %c.body
3694
3695 c.body:
3696   %x.c = load i32, i32* %ptr
3697   br label %d.header
3698 ; CHECK:       c.body:
3699 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3700 ; CHECK-NEXT:    br label %d.header
3701
3702 d.header:
3703   ; Use values from other loops to check LCSSA form.
3704   store i32 %x.a, i32* %ptr
3705   store i32 %x.b, i32* %ptr
3706   store i32 %x.c, i32* %ptr
3707   %v2 = call i1 @cond()
3708   br i1 %v2, label %d.header, label %c.latch
3709 ; CHECK:       d.header:
3710 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3711 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3712 ; CHECK-NEXT:    store i32 %x.c, i32* %ptr
3713 ; CHECK-NEXT:    %v2 = call i1 @cond()
3714 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
3715
3716 c.latch:
3717   %v3 = call i1 @cond()
3718   br i1 %v3, label %c.header, label %exit
3719 ; CHECK:       c.latch:
3720 ; CHECK-NEXT:    %v3 = call i1 @cond()
3721 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
3722
3723 b.latch:
3724   %v4 = call i1 @cond()
3725   br i1 %v4, label %b.header, label %a.latch
3726 ; CHECK:       b.latch:
3727 ; CHECK-NEXT:    %v4 = call i1 @cond()
3728 ; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
3729
3730 a.latch:
3731   br label %a.header
3732 ; CHECK:       a.latch:
3733 ; CHECK-NEXT:    br label %a.header
3734
3735 exit:
3736   ret void
3737 ; CHECK:       exit:
3738 ; CHECK-NEXT:    ret void
3739 }
3740
3741 ; This test is designed to exercise checking multiple remaining exits from the
3742 ; loop being unswitched.
3743 ; Unswitch will transform the loop nest from:
3744 ;   A < B < C < D
3745 ; into
3746 ;   A < B < (C, D)
3747 define void @hoist_inner_loop4() {
3748 ; CHECK-LABEL: define void @hoist_inner_loop4(
3749 entry:
3750   br label %a.header
3751 ; CHECK:       entry:
3752 ; CHECK-NEXT:    br label %a.header
3753
3754 a.header:
3755   br label %b.header
3756 ; CHECK:       a.header:
3757 ; CHECK-NEXT:    br label %b.header
3758
3759 b.header:
3760   br label %c.header
3761 ; CHECK:       b.header:
3762 ; CHECK-NEXT:    br label %c.header
3763
3764 c.header:
3765   %v1 = call i1 @cond()
3766   br label %d.header
3767 ; CHECK:       c.header:
3768 ; CHECK-NEXT:    %v1 = call i1 @cond()
3769 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3770 ;
3771 ; CHECK:       [[C_HEADER_SPLIT_US]]:
3772 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3773 ;
3774 ; CHECK:       [[D_HEADER_US]]:
3775 ; CHECK-NEXT:    call i32 @d()
3776 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3777 ;
3778 ; CHECK:       [[C_LATCH_US]]:
3779 ; CHECK-NEXT:    br label %c.latch
3780 ;
3781 ; CHECK:       [[C_HEADER_SPLIT]]:
3782 ; CHECK-NEXT:    br label %d.header
3783
3784 d.header:
3785   call i32 @d()
3786   br i1 %v1, label %c.latch, label %d.exiting1
3787 ; CHECK:       d.header:
3788 ; CHECK-NEXT:    call i32 @d()
3789 ; CHECK-NEXT:    br label %d.exiting1
3790
3791 d.exiting1:
3792   %v2 = call i1 @cond()
3793   br i1 %v2, label %d.exiting2, label %a.latch
3794 ; CHECK:       d.exiting1:
3795 ; CHECK-NEXT:    %v2 = call i1 @cond()
3796 ; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
3797
3798 d.exiting2:
3799   %v3 = call i1 @cond()
3800   br i1 %v3, label %d.exiting3, label %loopexit.d
3801 ; CHECK:       d.exiting2:
3802 ; CHECK-NEXT:    %v3 = call i1 @cond()
3803 ; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
3804
3805 d.exiting3:
3806   %v4 = call i1 @cond()
3807   br i1 %v4, label %d.latch, label %b.latch
3808 ; CHECK:       d.exiting3:
3809 ; CHECK-NEXT:    %v4 = call i1 @cond()
3810 ; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
3811
3812 d.latch:
3813   br label %d.header
3814 ; CHECK:       d.latch:
3815 ; CHECK-NEXT:    br label %d.header
3816
3817 c.latch:
3818   %v5 = call i1 @cond()
3819   br i1 %v5, label %c.header, label %loopexit.c
3820 ; CHECK:       c.latch:
3821 ; CHECK-NEXT:    %v5 = call i1 @cond()
3822 ; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
3823
3824 b.latch:
3825   br label %b.header
3826 ; CHECK:       b.latch:
3827 ; CHECK-NEXT:    br label %b.header
3828
3829 a.latch:
3830   br label %a.header
3831 ; CHECK:       a.latch:
3832 ; CHECK-NEXT:    br label %a.header
3833
3834 loopexit.d:
3835   br label %exit
3836 ; CHECK:       loopexit.d:
3837 ; CHECK-NEXT:    br label %exit
3838
3839 loopexit.c:
3840   br label %exit
3841 ; CHECK:       loopexit.c:
3842 ; CHECK-NEXT:    br label %exit
3843
3844 exit:
3845   ret void
3846 ; CHECK:       exit:
3847 ; CHECK-NEXT:    ret void
3848 }
3849
3850 ; Unswitch will transform the loop nest from:
3851 ;   A < B < C < D
3852 ; into
3853 ;   A < ((B < C), D)
3854 define void @hoist_inner_loop5(i32* %ptr) {
3855 ; CHECK-LABEL: define void @hoist_inner_loop5(
3856 entry:
3857   br label %a.header
3858 ; CHECK:       entry:
3859 ; CHECK-NEXT:    br label %a.header
3860
3861 a.header:
3862   %x.a = load i32, i32* %ptr
3863   br label %b.header
3864 ; CHECK:       a.header:
3865 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3866 ; CHECK-NEXT:    br label %b.header
3867
3868 b.header:
3869   %x.b = load i32, i32* %ptr
3870   br label %c.header
3871 ; CHECK:       b.header:
3872 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3873 ; CHECK-NEXT:    br label %c.header
3874
3875 c.header:
3876   %x.c = load i32, i32* %ptr
3877   %v1 = call i1 @cond()
3878   br label %d.header
3879 ; CHECK:       c.header:
3880 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3881 ; CHECK-NEXT:    %v1 = call i1 @cond()
3882 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3883 ;
3884 ; CHECK:       [[C_HEADER_SPLIT_US]]:
3885 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3886 ;
3887 ; CHECK:       [[D_HEADER_US]]:
3888 ; CHECK-NEXT:    call i32 @d()
3889 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3890 ;
3891 ; CHECK:       [[C_LATCH_US]]:
3892 ; CHECK-NEXT:    br label %c.latch
3893 ;
3894 ; CHECK:       [[C_HEADER_SPLIT]]:
3895 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
3896 ; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
3897 ; CHECK-NEXT:    br label %d.header
3898
3899 d.header:
3900   call i32 @d()
3901   br i1 %v1, label %c.latch, label %d.latch
3902 ; CHECK:       d.header:
3903 ; CHECK-NEXT:    call i32 @d()
3904 ; CHECK-NEXT:    br label %d.latch
3905
3906 d.latch:
3907   ; Use values from other loops to check LCSSA form.
3908   store i32 %x.a, i32* %ptr
3909   store i32 %x.b, i32* %ptr
3910   store i32 %x.c, i32* %ptr
3911   %v2 = call i1 @cond()
3912   br i1 %v2, label %d.header, label %a.latch
3913 ; CHECK:       d.latch:
3914 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3915 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3916 ; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
3917 ; CHECK-NEXT:    %v2 = call i1 @cond()
3918 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
3919
3920 c.latch:
3921   %v3 = call i1 @cond()
3922   br i1 %v3, label %c.header, label %b.latch
3923 ; CHECK:       c.latch:
3924 ; CHECK-NEXT:    %v3 = call i1 @cond()
3925 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
3926
3927 b.latch:
3928   br label %b.header
3929 ; CHECK:       b.latch:
3930 ; CHECK-NEXT:    br label %b.header
3931
3932 a.latch:
3933   br label %a.header
3934 ; CHECK:       a.latch:
3935 ; CHECK-NEXT:    br label %a.header
3936
3937 exit:
3938   ret void
3939 ; CHECK:       exit:
3940 ; CHECK-NEXT:    ret void
3941 }
3942
3943 define void @hoist_inner_loop_switch(i32* %ptr) {
3944 ; CHECK-LABEL: define void @hoist_inner_loop_switch(
3945 entry:
3946   br label %a.header
3947 ; CHECK:       entry:
3948 ; CHECK-NEXT:    br label %a.header
3949
3950 a.header:
3951   %x.a = load i32, i32* %ptr
3952   br label %b.header
3953 ; CHECK:       a.header:
3954 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3955 ; CHECK-NEXT:    br label %b.header
3956
3957 b.header:
3958   %x.b = load i32, i32* %ptr
3959   %v1 = call i32 @cond.i32()
3960   br label %c.header
3961 ; CHECK:       b.header:
3962 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3963 ; CHECK-NEXT:    %v1 = call i32 @cond.i32()
3964 ; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
3965 ; CHECK-NEXT:      i32 1, label %[[B_HEADER_SPLIT_US:.*]]
3966 ; CHECK-NEXT:      i32 2, label %[[B_HEADER_SPLIT_US]]
3967 ; CHECK-NEXT:      i32 3, label %[[B_HEADER_SPLIT_US]]
3968 ; CHECK-NEXT:    ]
3969 ;
3970 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3971 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3972 ;
3973 ; CHECK:       [[C_HEADER_US]]:
3974 ; CHECK-NEXT:    call i32 @c()
3975 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3976 ;
3977 ; CHECK:       [[B_LATCH_US]]:
3978 ; CHECK-NEXT:    br label %b.latch
3979 ;
3980 ; CHECK:       [[B_HEADER_SPLIT]]:
3981 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3982 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3983 ; CHECK-NEXT:    br label %c.header
3984
3985 c.header:
3986   call i32 @c()
3987   switch i32 %v1, label %c.latch [
3988     i32 1, label %b.latch
3989     i32 2, label %b.latch
3990     i32 3, label %b.latch
3991   ]
3992 ; CHECK:       c.header:
3993 ; CHECK-NEXT:    call i32 @c()
3994 ; CHECK-NEXT:    br label %c.latch
3995
3996 c.latch:
3997   ; Use values from other loops to check LCSSA form.
3998   store i32 %x.a, i32* %ptr
3999   store i32 %x.b, i32* %ptr
4000   %v2 = call i1 @cond()
4001   br i1 %v2, label %c.header, label %exit
4002 ; CHECK:       c.latch:
4003 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
4004 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
4005 ; CHECK-NEXT:    %v2 = call i1 @cond()
4006 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
4007
4008 b.latch:
4009   %v3 = call i1 @cond()
4010   br i1 %v3, label %b.header, label %a.latch
4011 ; CHECK:       b.latch:
4012 ; CHECK-NEXT:    %v3 = call i1 @cond()
4013 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
4014
4015 a.latch:
4016   br label %a.header
4017 ; CHECK:       a.latch:
4018 ; CHECK-NEXT:    br label %a.header
4019
4020 exit:
4021   ret void
4022 ; CHECK:       exit:
4023 ; CHECK-NEXT:    ret void
4024 }
4025
4026 ; A devilish pattern. This is a crafty, crafty test case designed to risk
4027 ; creating indirect cycles with trivial and non-trivial unswitching. The inner
4028 ; loop has a switch with a trivial exit edge that can be unswitched, but the
4029 ; rest of the switch cannot be unswitched because its cost is too high.
4030 ; However, the unswitching of the trivial edge creates a new switch in the
4031 ; outer loop. *This* switch isn't trivial, but has a low cost to unswitch. When
4032 ; we unswitch this switch from the outer loop, we will remove it completely and
4033 ; create a clone of the inner loop on one side. This clone will then again be
4034 ; viable for unswitching the inner-most loop. This lets us check that the
4035 ; unswitching doesn't end up cycling infinitely even when the cycle is
4036 ; indirect and due to revisiting a loop after cloning.
4037 define void @test31(i32 %arg) {
4038 ; CHECK-LABEL: define void @test31(
4039 entry:
4040   br label %outer.header
4041 ; CHECK-NEXT:  entry:
4042 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT:.*]] [
4043 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US:.*]]
4044 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_US]]
4045 ; CHECK-NEXT:    ]
4046 ;
4047 ; CHECK:       [[ENTRY_SPLIT_US]]:
4048 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_US_SPLIT:.*]] [
4049 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US_SPLIT_US:.*]]
4050 ; CHECK-NEXT:    ]
4051
4052 outer.header:
4053   br label %inner.header
4054
4055 inner.header:
4056   switch i32 %arg, label %inner.loopexit1 [
4057     i32 1, label %inner.body1
4058     i32 2, label %inner.body2
4059   ]
4060
4061 inner.body1:
4062   %a = call i32 @a()
4063   br label %inner.latch
4064 ; The (super convoluted) fully unswitched loop around `@a`.
4065 ;
4066 ; CHECK:       [[ENTRY_SPLIT_US_SPLIT_US]]:
4067 ; CHECK-NEXT:    br label %[[OUTER_HEADER_US_US:.*]]
4068 ;
4069 ; CHECK:       [[OUTER_HEADER_US_US]]:
4070 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US_US:.*]]
4071 ;
4072 ; CHECK:       [[OUTER_LATCH_US_US:.*]]:
4073 ; CHECK-NEXT:    %[[OUTER_COND_US_US:.*]] = call i1 @cond()
4074 ; CHECK-NEXT:    br i1 %[[OUTER_COND_US_US]], label %[[OUTER_HEADER_US_US]], label %[[EXIT_SPLIT_US_SPLIT_US:.*]]
4075 ;
4076 ; CHECK:       [[OUTER_HEADER_SPLIT_US_US]]:
4077 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US_US_US:.*]]
4078 ;
4079 ; CHECK:       [[INNER_LOOPEXIT2_US_US:.*]]:
4080 ; CHECK-NEXT:    br label %[[OUTER_LATCH_US_US]]
4081 ;
4082 ; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US_US_US]]:
4083 ; CHECK-NEXT:    br label %[[INNER_HEADER_US_US_US:.*]]
4084 ;
4085 ; CHECK:       [[INNER_HEADER_US_US_US]]:
4086 ; CHECK-NEXT:    br label %[[INNER_BODY1_US_US_US:.*]]
4087 ;
4088 ; CHECK:       [[INNER_BODY1_US_US_US]]:
4089 ; CHECK-NEXT:    %[[A:.*]] = call i32 @a()
4090 ; CHECK-NEXT:    br label %[[INNER_LATCH_US_US_US:.*]]
4091 ;
4092 ; CHECK:       [[INNER_LATCH_US_US_US]]:
4093 ; CHECK-NEXT:    %[[PHI_A:.*]] = phi i32 [ %[[A]], %[[INNER_BODY1_US_US_US]] ]
4094 ; CHECK-NEXT:    call void @sink1(i32 0)
4095 ; CHECK-NEXT:    call void @sink1(i32 0)
4096 ; CHECK-NEXT:    call void @sink1(i32 0)
4097 ; CHECK-NEXT:    call void @sink1(i32 0)
4098 ; CHECK-NEXT:    call void @sink1(i32 0)
4099 ; CHECK-NEXT:    call void @sink1(i32 0)
4100 ; CHECK-NEXT:    call void @sink1(i32 0)
4101 ; CHECK-NEXT:    call void @sink1(i32 0)
4102 ; CHECK-NEXT:    call void @sink1(i32 0)
4103 ; CHECK-NEXT:    call void @sink1(i32 0)
4104 ; CHECK-NEXT:    call void @sink1(i32 %[[PHI_A]])
4105 ; CHECK-NEXT:    %[[INNER_COND_US_US_US:.*]] = call i1 @cond()
4106 ; CHECK-NEXT:    br i1 %[[INNER_COND_US_US_US]], label %[[INNER_HEADER_US_US_US]], label %[[INNER_LOOPEXIT2_SPLIT_US_US_US:.*]]
4107 ;
4108 ; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US_US_US]]:
4109 ; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US_US]]
4110 ;
4111 ; CHECK:       [[EXIT_SPLIT_US_SPLIT_US]]:
4112 ; CHECK-NEXT:    br label %[[EXIT_SPLIT_US:.*]]
4113
4114
4115 inner.body2:
4116   %b = call i32 @b()
4117   br label %inner.latch
4118 ; The fully unswitched loop around `@b`.
4119 ;
4120 ; CHECK:       [[ENTRY_SPLIT_US_SPLIT]]:
4121 ; CHECK-NEXT:    br label %[[OUTER_HEADER_US:.*]]
4122 ;
4123 ; CHECK:       [[OUTER_HEADER_US]]:
4124 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US:.*]]
4125 ;
4126 ; CHECK:       [[INNER_HEADER_US:.*]]:
4127 ; CHECK-NEXT:    br label %[[INNER_BODY2_US:.*]]
4128 ;
4129 ; CHECK:       [[INNER_BODY2_US]]:
4130 ; CHECK-NEXT:    %[[B:.*]] = call i32 @b()
4131 ; CHECK-NEXT:    br label %[[INNER_LATCH_US:.*]]
4132 ;
4133 ; CHECK:       [[INNER_LATCH_US]]:
4134 ; CHECK-NEXT:    call void @sink1(i32 0)
4135 ; CHECK-NEXT:    call void @sink1(i32 0)
4136 ; CHECK-NEXT:    call void @sink1(i32 0)
4137 ; CHECK-NEXT:    call void @sink1(i32 0)
4138 ; CHECK-NEXT:    call void @sink1(i32 0)
4139 ; CHECK-NEXT:    call void @sink1(i32 0)
4140 ; CHECK-NEXT:    call void @sink1(i32 0)
4141 ; CHECK-NEXT:    call void @sink1(i32 0)
4142 ; CHECK-NEXT:    call void @sink1(i32 0)
4143 ; CHECK-NEXT:    call void @sink1(i32 0)
4144 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
4145 ; CHECK-NEXT:    %[[INNER_COND_US:.*]] = call i1 @cond()
4146 ; CHECK-NEXT:    br i1 %[[INNER_COND_US]], label %[[INNER_HEADER_US]], label %[[INNER_LOOPEXIT2_SPLIT_US:.*]]
4147 ;
4148 ; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US]]:
4149 ; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US:.*]]
4150 ;
4151 ; CHECK:       [[OUTER_LATCH_US:.*]]:
4152 ; CHECK-NEXT:    %[[OUTER_COND_US:.*]] = call i1 @cond()
4153 ; CHECK-NEXT:    br i1 %[[OUTER_COND_US]], label %[[OUTER_HEADER_US]], label %[[EXIT_SPLIT_US_SPLIT:.*]]
4154 ;
4155 ; CHECK:       [[OUTER_HEADER_SPLIT_US]]:
4156 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US:.*]]
4157 ;
4158 ; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US]]:
4159 ; CHECK-NEXT:    br label %[[INNER_HEADER_US]]
4160 ;
4161 ; CHECK:       [[INNER_LOOPEXIT2_US]]:
4162 ; CHECK-NEXT:    br label %[[OUTER_LATCH_US]]
4163 ;
4164 ; CHECK:       [[EXIT_SPLIT_US]]:
4165 ; CHECK-NEXT:    br label %exit
4166
4167 inner.latch:
4168   %phi = phi i32 [ %a, %inner.body1 ], [ %b, %inner.body2 ]
4169   ; Make 10 junk calls here to ensure we're over the "50" cost threshold of
4170   ; non-trivial unswitching for this inner switch.
4171   call void @sink1(i32 0)
4172   call void @sink1(i32 0)
4173   call void @sink1(i32 0)
4174   call void @sink1(i32 0)
4175   call void @sink1(i32 0)
4176   call void @sink1(i32 0)
4177   call void @sink1(i32 0)
4178   call void @sink1(i32 0)
4179   call void @sink1(i32 0)
4180   call void @sink1(i32 0)
4181   call void @sink1(i32 %phi)
4182   %inner.cond = call i1 @cond()
4183   br i1 %inner.cond, label %inner.header, label %inner.loopexit2
4184
4185 inner.loopexit1:
4186   br label %outer.latch
4187 ; The unswitched `loopexit1` path.
4188 ;
4189 ; CHECK:       [[ENTRY_SPLIT]]:
4190 ; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
4191 ;
4192 ; CHECK:       outer.header:
4193 ; CHECK-NEXT:    br label %inner.loopexit1
4194 ;
4195 ; CHECK:       inner.loopexit1:
4196 ; CHECK-NEXT:    br label %outer.latch
4197 ;
4198 ; CHECK:       outer.latch:
4199 ; CHECK-NEXT:    %outer.cond = call i1 @cond()
4200 ; CHECK-NEXT:    br i1 %outer.cond, label %outer.header, label %[[EXIT_SPLIT:.*]]
4201 ;
4202 ; CHECK:       [[EXIT_SPLIT]]:
4203 ; CHECK-NEXT:    br label %exit
4204
4205 inner.loopexit2:
4206   br label %outer.latch
4207
4208 outer.latch:
4209   %outer.cond = call i1 @cond()
4210   br i1 %outer.cond, label %outer.header, label %exit
4211
4212 exit:
4213   ret void
4214 ; CHECK:       exit:
4215 ; CHECK-NEXT:    ret void
4216 }