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

   1 ; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
   2 ; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
   3 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -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:    br label %loop_a.us
2723 ;
2724 ; CHECK:       loop_a.us:
2725 ; CHECK-NEXT:    call i32 @a()
2726 ; CHECK-NEXT:    br label %latch.us
2727 ;
2728 ; CHECK:       latch.us:
2729 ; CHECK-NEXT:    %[[V2_US:.*]] = load i1, i1* %ptr
2730 ; CHECK-NEXT:    br i1 %[[V2_US]], label %loop_begin.us, label %loop_exit.split.us
2731 ;
2732 ; CHECK:       loop_exit.split.us:
2733 ; CHECK-NEXT:    br label %loop_exit
2734
2735 loop_b:
2736   call i32 @b()
2737   br label %latch
2738 ; The original loop.
2739 ;
2740 ; CHECK:       entry.split:
2741 ; CHECK-NEXT:    br label %loop_begin
2742 ;
2743 ; CHECK:       loop_begin:
2744 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr
2745 ; CHECK-NEXT:    %[[OR:.*]] = or i1 %[[V1]], false
2746 ; CHECK-NEXT:    br i1 %[[OR]], label %loop_a, label %loop_b
2747 ;
2748 ; CHECK:       loop_a:
2749 ; CHECK-NEXT:    call i32 @a()
2750 ; CHECK-NEXT:    br label %latch
2751 ;
2752 ; CHECK:       loop_b:
2753 ; CHECK-NEXT:    call i32 @b()
2754 ; CHECK-NEXT:    br label %latch
2755
2756 latch:
2757   %v2 = load i1, i1* %ptr
2758   br i1 %v2, label %loop_begin, label %loop_exit
2759 ; CHECK:       latch:
2760 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr
2761 ; CHECK-NEXT:    br i1 %[[V2]], label %loop_begin, label %loop_exit.split
2762
2763 loop_exit:
2764   ret i32 0
2765 ; CHECK:       loop_exit.split:
2766 ; CHECK-NEXT:    br label %loop_exit
2767 ;
2768 ; CHECK:       loop_exit:
2769 ; CHECK-NEXT:    ret
2770 }
2771
2772 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `and`
2773 ; chain.
2774 define i32 @test26(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2775 ; CHECK-LABEL: @test26(
2776 entry:
2777   br label %loop_begin
2778 ; CHECK-NEXT:  entry:
2779 ; CHECK-NEXT:    %[[INV_AND:.*]] = and i1 %cond3, %cond1
2780 ; CHECK-NEXT:    br i1 %[[INV_AND]], label %entry.split, label %entry.split.us
2781
2782 loop_begin:
2783   %v1 = load i1, i1* %ptr1
2784   %v2 = load i1, i1* %ptr2
2785   %cond_and1 = and i1 %v1, %cond1
2786   %cond_or1 = or i1 %v2, %cond2
2787   %cond_and2 = and i1 %cond_and1, %cond_or1
2788   %cond_and3 = and i1 %cond_and2, %cond3
2789   br i1 %cond_and3, label %loop_a, label %loop_b
2790 ; The 'loop_b' unswitched loop.
2791 ;
2792 ; CHECK:       entry.split.us:
2793 ; CHECK-NEXT:    br label %loop_begin.us
2794 ;
2795 ; CHECK:       loop_begin.us:
2796 ; CHECK-NEXT:    br label %loop_b.us
2797 ;
2798 ; CHECK:       loop_b.us:
2799 ; CHECK-NEXT:    call i32 @b()
2800 ; CHECK-NEXT:    br label %latch.us
2801 ;
2802 ; CHECK:       latch.us:
2803 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2804 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2805 ;
2806 ; CHECK:       loop_exit.split.us:
2807 ; CHECK-NEXT:    br label %loop_exit
2808
2809 ; The original loop.
2810 ;
2811 ; CHECK:       entry.split:
2812 ; CHECK-NEXT:    br label %loop_begin
2813 ;
2814 ; CHECK:       loop_begin:
2815 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2816 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2817 ; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V1]], true
2818 ; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V2]], %cond2
2819 ; CHECK-NEXT:    %[[AND2:.*]] = and i1 %[[AND1]], %[[OR1]]
2820 ; CHECK-NEXT:    %[[AND3:.*]] = and i1 %[[AND2]], true
2821 ; CHECK-NEXT:    br i1 %[[AND3]], label %loop_a, label %loop_b
2822
2823 loop_a:
2824   call i32 @a()
2825   br label %latch
2826 ; CHECK:       loop_a:
2827 ; CHECK-NEXT:    call i32 @a()
2828 ; CHECK-NEXT:    br label %latch
2829
2830 loop_b:
2831   call i32 @b()
2832   br label %latch
2833 ; CHECK:       loop_b:
2834 ; CHECK-NEXT:    call i32 @b()
2835 ; CHECK-NEXT:    br label %latch
2836
2837 latch:
2838   %v3 = load i1, i1* %ptr3
2839   br i1 %v3, label %loop_begin, label %loop_exit
2840 ; CHECK:       latch:
2841 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2842 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2843
2844 loop_exit:
2845   ret i32 0
2846 ; CHECK:       loop_exit.split:
2847 ; CHECK-NEXT:    br label %loop_exit
2848 ;
2849 ; CHECK:       loop_exit:
2850 ; CHECK-NEXT:    ret
2851 }
2852
2853 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `or`
2854 ; chain. Basically an inverted version of corresponding `and` test (test26).
2855 define i32 @test27(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) {
2856 ; CHECK-LABEL: @test27(
2857 entry:
2858   br label %loop_begin
2859 ; CHECK-NEXT:  entry:
2860 ; CHECK-NEXT:    %[[INV_OR:.*]] = or i1 %cond3, %cond1
2861 ; CHECK-NEXT:    br i1 %[[INV_OR]], label %entry.split.us, label %entry.split
2862
2863 loop_begin:
2864   %v1 = load i1, i1* %ptr1
2865   %v2 = load i1, i1* %ptr2
2866   %cond_or1 = or i1 %v1, %cond1
2867   %cond_and1 = and i1 %v2, %cond2
2868   %cond_or2 = or i1 %cond_or1, %cond_and1
2869   %cond_or3 = or i1 %cond_or2, %cond3
2870   br i1 %cond_or3, label %loop_b, label %loop_a
2871 ; The 'loop_b' unswitched loop.
2872 ;
2873 ; CHECK:       entry.split.us:
2874 ; CHECK-NEXT:    br label %loop_begin.us
2875 ;
2876 ; CHECK:       loop_begin.us:
2877 ; CHECK-NEXT:    br label %loop_b.us
2878 ;
2879 ; CHECK:       loop_b.us:
2880 ; CHECK-NEXT:    call i32 @b()
2881 ; CHECK-NEXT:    br label %latch.us
2882 ;
2883 ; CHECK:       latch.us:
2884 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3
2885 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
2886 ;
2887 ; CHECK:       loop_exit.split.us:
2888 ; CHECK-NEXT:    br label %loop_exit
2889
2890 ; The original loop.
2891 ;
2892 ; CHECK:       entry.split:
2893 ; CHECK-NEXT:    br label %loop_begin
2894 ;
2895 ; CHECK:       loop_begin:
2896 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
2897 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
2898 ; CHECK-NEXT:    %[[OR1:.*]] = or i1 %[[V1]], false
2899 ; CHECK-NEXT:    %[[AND1:.*]] = and i1 %[[V2]], %cond2
2900 ; CHECK-NEXT:    %[[OR2:.*]] = or i1 %[[OR1]], %[[AND1]]
2901 ; CHECK-NEXT:    %[[OR3:.*]] = or i1 %[[OR2]], false
2902 ; CHECK-NEXT:    br i1 %[[OR3]], label %loop_b, label %loop_a
2903
2904 loop_a:
2905   call i32 @a()
2906   br label %latch
2907 ; CHECK:       loop_a:
2908 ; CHECK-NEXT:    call i32 @a()
2909 ; CHECK-NEXT:    br label %latch
2910
2911 loop_b:
2912   call i32 @b()
2913   br label %latch
2914 ; CHECK:       loop_b:
2915 ; CHECK-NEXT:    call i32 @b()
2916 ; CHECK-NEXT:    br label %latch
2917
2918 latch:
2919   %v3 = load i1, i1* %ptr3
2920   br i1 %v3, label %loop_begin, label %loop_exit
2921 ; CHECK:       latch:
2922 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3
2923 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
2924
2925 loop_exit:
2926   ret i32 0
2927 ; CHECK:       loop_exit.split:
2928 ; CHECK-NEXT:    br label %loop_exit
2929 ;
2930 ; CHECK:       loop_exit:
2931 ; CHECK-NEXT:    ret
2932 }
2933
2934 ; Non-trivial unswitching of a switch.
2935 define i32 @test28(i1* %ptr, i32 %cond) {
2936 ; CHECK-LABEL: @test28(
2937 entry:
2938   br label %loop_begin
2939 ; CHECK-NEXT:  entry:
2940 ; CHECK-NEXT:    switch i32 %cond, label %[[ENTRY_SPLIT_LATCH:.*]] [
2941 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
2942 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
2943 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_C:.*]]
2944 ; CHECK-NEXT:    ]
2945
2946 loop_begin:
2947   switch i32 %cond, label %latch [
2948     i32 0, label %loop_a
2949     i32 1, label %loop_b
2950     i32 2, label %loop_c
2951   ]
2952
2953 loop_a:
2954   call i32 @a()
2955   br label %latch
2956 ; Unswitched 'a' loop.
2957 ;
2958 ; CHECK:       [[ENTRY_SPLIT_A]]:
2959 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_A:.*]]
2960 ;
2961 ; CHECK:       [[LOOP_BEGIN_A]]:
2962 ; CHECK-NEXT:    br label %[[LOOP_A:.*]]
2963 ;
2964 ; CHECK:       [[LOOP_A]]:
2965 ; CHECK-NEXT:    call i32 @a()
2966 ; CHECK-NEXT:    br label %[[LOOP_LATCH_A:.*]]
2967 ;
2968 ; CHECK:       [[LOOP_LATCH_A]]:
2969 ; CHECK-NEXT:    %[[V_A:.*]] = load i1, i1* %ptr
2970 ; CHECK:         br i1 %[[V_A]], label %[[LOOP_BEGIN_A]], label %[[LOOP_EXIT_A:.*]]
2971 ;
2972 ; CHECK:       [[LOOP_EXIT_A]]:
2973 ; CHECK-NEXT:    br label %loop_exit
2974
2975 loop_b:
2976   call i32 @b()
2977   br label %latch
2978 ; Unswitched 'b' loop.
2979 ;
2980 ; CHECK:       [[ENTRY_SPLIT_B]]:
2981 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_B:.*]]
2982 ;
2983 ; CHECK:       [[LOOP_BEGIN_B]]:
2984 ; CHECK-NEXT:    br label %[[LOOP_B:.*]]
2985 ;
2986 ; CHECK:       [[LOOP_B]]:
2987 ; CHECK-NEXT:    call i32 @b()
2988 ; CHECK-NEXT:    br label %[[LOOP_LATCH_B:.*]]
2989 ;
2990 ; CHECK:       [[LOOP_LATCH_B]]:
2991 ; CHECK-NEXT:    %[[V_B:.*]] = load i1, i1* %ptr
2992 ; CHECK:         br i1 %[[V_B]], label %[[LOOP_BEGIN_B]], label %[[LOOP_EXIT_B:.*]]
2993 ;
2994 ; CHECK:       [[LOOP_EXIT_B]]:
2995 ; CHECK-NEXT:    br label %loop_exit
2996
2997 loop_c:
2998   call i32 @c()
2999   br label %latch
3000 ; Unswitched 'c' loop.
3001 ;
3002 ; CHECK:       [[ENTRY_SPLIT_C]]:
3003 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_C:.*]]
3004 ;
3005 ; CHECK:       [[LOOP_BEGIN_C]]:
3006 ; CHECK-NEXT:    br label %[[LOOP_C:.*]]
3007 ;
3008 ; CHECK:       [[LOOP_C]]:
3009 ; CHECK-NEXT:    call i32 @c()
3010 ; CHECK-NEXT:    br label %[[LOOP_LATCH_C:.*]]
3011 ;
3012 ; CHECK:       [[LOOP_LATCH_C]]:
3013 ; CHECK-NEXT:    %[[V_C:.*]] = load i1, i1* %ptr
3014 ; CHECK:         br i1 %[[V_C]], label %[[LOOP_BEGIN_C]], label %[[LOOP_EXIT_C:.*]]
3015 ;
3016 ; CHECK:       [[LOOP_EXIT_C]]:
3017 ; CHECK-NEXT:    br label %loop_exit
3018
3019 latch:
3020   %v = load i1, i1* %ptr
3021   br i1 %v, label %loop_begin, label %loop_exit
3022 ; Unswitched the 'latch' only loop.
3023 ;
3024 ; CHECK:       [[ENTRY_SPLIT_LATCH]]:
3025 ; CHECK-NEXT:    br label %[[LOOP_BEGIN_LATCH:.*]]
3026 ;
3027 ; CHECK:       [[LOOP_BEGIN_LATCH]]:
3028 ; CHECK-NEXT:    br label %[[LOOP_LATCH_LATCH:.*]]
3029 ;
3030 ; CHECK:       [[LOOP_LATCH_LATCH]]:
3031 ; CHECK-NEXT:    %[[V_LATCH:.*]] = load i1, i1* %ptr
3032 ; CHECK:         br i1 %[[V_LATCH]], label %[[LOOP_BEGIN_LATCH]], label %[[LOOP_EXIT_LATCH:.*]]
3033 ;
3034 ; CHECK:       [[LOOP_EXIT_LATCH]]:
3035 ; CHECK-NEXT:    br label %loop_exit
3036
3037 loop_exit:
3038   ret i32 0
3039 ; CHECK:       loop_exit:
3040 ; CHECK-NEXT:    ret i32 0
3041 }
3042
3043 ; A test case designed to exercise unusual properties of switches: they
3044 ; can introduce multiple edges to successors. These need lots of special case
3045 ; handling as they get collapsed in many cases (domtree, the unswitch itself)
3046 ; but not in all cases (the PHI node operands).
3047 define i32 @test29(i32 %arg) {
3048 ; CHECK-LABEL: @test29(
3049 entry:
3050   br label %header
3051 ; CHECK-NEXT:  entry:
3052 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_C:.*]] [
3053 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3054 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_A]]
3055 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B:.*]]
3056 ; CHECK-NEXT:      i32 3, label %[[ENTRY_SPLIT_C]]
3057 ; CHECK-NEXT:    ]
3058
3059 header:
3060   %tmp = call i32 @d()
3061   %cmp1 = icmp eq i32 %tmp, 0
3062   ; We set up a chain through all the successors of the switch that doesn't
3063   ; involve the switch so that we can have interesting PHI nodes in them.
3064   br i1 %cmp1, label %body.a, label %dispatch
3065
3066 dispatch:
3067   ; Switch with multiple successors. We arrange the last successor to be the
3068   ; default to make the test case easier to read. This has a duplicate edge
3069   ; both to the default destination (which is completely superfluous but
3070   ; technically valid IR) and to a regular successor.
3071   switch i32 %arg, label %body.c [
3072     i32 0, label %body.a
3073     i32 1, label %body.a
3074     i32 2, label %body.b
3075     i32 3, label %body.c
3076   ]
3077
3078 body.a:
3079   %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3080   %tmp.a = call i32 @a()
3081   %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3082   br label %body.b
3083 ; Unswitched 'a' loop.
3084 ;
3085 ; CHECK:       [[ENTRY_SPLIT_A]]:
3086 ; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3087 ;
3088 ; CHECK:       [[HEADER_A]]:
3089 ; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3090 ; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3091 ; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3092 ;
3093 ; CHECK:       [[DISPATCH_A]]:
3094 ; CHECK-NEXT:    br label %[[BODY_A_A]]
3095 ;
3096 ; CHECK:       [[BODY_A_A]]:
3097 ; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3098 ; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3099 ; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3100 ; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3101 ;
3102 ; CHECK:       [[BODY_B_A]]:
3103 ; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3104 ; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3105 ; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3106 ; CHECK-NEXT:    br label %[[BODY_C_A:.*]]
3107 ;
3108 ; CHECK:       [[BODY_C_A]]:
3109 ; CHECK-NEXT:    %[[TMP_C_PHI_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[BODY_B_A]] ]
3110 ; CHECK-NEXT:    %[[TMP_C_A:.*]] = call i32 @c()
3111 ; CHECK-NEXT:    %[[TMP_C_SUM_A:.*]] = add i32 %[[TMP_C_PHI_A]], %[[TMP_C_A]]
3112 ; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3113 ;
3114 ; CHECK:       [[LATCH_A]]:
3115 ; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_C_SUM_A]], 42
3116 ; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3117 ;
3118 ; CHECK:       [[LOOP_EXIT_A]]:
3119 ; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_C_SUM_A]], %[[LATCH_A]] ]
3120 ; CHECK-NEXT:    br label %exit
3121
3122 body.b:
3123   %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3124   %tmp.b = call i32 @b()
3125   %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3126   br label %body.c
3127 ; Unswitched 'b' loop.
3128 ;
3129 ; CHECK:       [[ENTRY_SPLIT_B]]:
3130 ; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3131 ;
3132 ; CHECK:       [[HEADER_B]]:
3133 ; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3134 ; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3135 ; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3136 ;
3137 ; CHECK:       [[DISPATCH_B]]:
3138 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3139 ;
3140 ; CHECK:       [[BODY_A_B]]:
3141 ; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3142 ; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3143 ; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3144 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3145 ;
3146 ; CHECK:       [[BODY_B_B]]:
3147 ; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3148 ; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3149 ; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3150 ; CHECK-NEXT:    br label %[[BODY_C_B:.*]]
3151 ;
3152 ; CHECK:       [[BODY_C_B]]:
3153 ; CHECK-NEXT:    %[[TMP_C_PHI_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[BODY_B_B]] ]
3154 ; CHECK-NEXT:    %[[TMP_C_B:.*]] = call i32 @c()
3155 ; CHECK-NEXT:    %[[TMP_C_SUM_B:.*]] = add i32 %[[TMP_C_PHI_B]], %[[TMP_C_B]]
3156 ; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3157 ;
3158 ; CHECK:       [[LATCH_B]]:
3159 ; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_C_SUM_B]], 42
3160 ; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3161 ;
3162 ; CHECK:       [[LOOP_EXIT_B]]:
3163 ; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_C_SUM_B]], %[[LATCH_B]] ]
3164 ; CHECK-NEXT:    br label %[[EXIT_SPLIT:.*]]
3165
3166 body.c:
3167   %tmp.c.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.b.sum, %body.b ]
3168   %tmp.c = call i32 @c()
3169   %tmp.c.sum = add i32 %tmp.c.phi, %tmp.c
3170   br label %latch
3171 ; Unswitched 'c' loop.
3172 ;
3173 ; CHECK:       [[ENTRY_SPLIT_C]]:
3174 ; CHECK-NEXT:    br label %[[HEADER_C:.*]]
3175 ;
3176 ; CHECK:       [[HEADER_C]]:
3177 ; CHECK-NEXT:    %[[TMP_C:.*]] = call i32 @d()
3178 ; CHECK-NEXT:    %[[CMP1_C:.*]] = icmp eq i32 %[[TMP_C]], 0
3179 ; CHECK-NEXT:    br i1 %[[CMP1_C]], label %[[BODY_A_C:.*]], label %[[DISPATCH_C:.*]]
3180 ;
3181 ; CHECK:       [[DISPATCH_C]]:
3182 ; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3183 ;
3184 ; CHECK:       [[BODY_A_C]]:
3185 ; CHECK-NEXT:    %[[TMP_A_PHI_C:.*]] = phi i32 [ 0, %[[HEADER_C]] ]
3186 ; CHECK-NEXT:    %[[TMP_A_C:.*]] = call i32 @a()
3187 ; CHECK-NEXT:    %[[TMP_A_SUM_C:.*]] = add i32 %[[TMP_A_PHI_C]], %[[TMP_A_C]]
3188 ; CHECK-NEXT:    br label %[[BODY_B_C:.*]]
3189 ;
3190 ; CHECK:       [[BODY_B_C]]:
3191 ; CHECK-NEXT:    %[[TMP_B_PHI_C:.*]] = phi i32 [ %[[TMP_A_SUM_C]], %[[BODY_A_C]] ]
3192 ; CHECK-NEXT:    %[[TMP_B_C:.*]] = call i32 @b()
3193 ; CHECK-NEXT:    %[[TMP_B_SUM_C:.*]] = add i32 %[[TMP_B_PHI_C]], %[[TMP_B_C]]
3194 ; CHECK-NEXT:    br label %[[BODY_C_C:.*]]
3195 ;
3196 ; CHECK:       [[BODY_C_C]]:
3197 ; CHECK-NEXT:    %[[TMP_C_PHI_C:.*]] = phi i32 [ %[[TMP_C]], %[[DISPATCH_C]] ], [ %[[TMP_B_SUM_C]], %[[BODY_B_C]] ]
3198 ; CHECK-NEXT:    %[[TMP_C_C:.*]] = call i32 @c()
3199 ; CHECK-NEXT:    %[[TMP_C_SUM_C:.*]] = add i32 %[[TMP_C_PHI_C]], %[[TMP_C_C]]
3200 ; CHECK-NEXT:    br label %[[LATCH_C:.*]]
3201 ;
3202 ; CHECK:       [[LATCH_C]]:
3203 ; CHECK-NEXT:    %[[CMP2_C:.*]] = icmp slt i32 %[[TMP_C_SUM_C]], 42
3204 ; CHECK:         br i1 %[[CMP2_C]], label %[[HEADER_C]], label %[[LOOP_EXIT_C:.*]]
3205 ;
3206 ; CHECK:       [[LOOP_EXIT_C]]:
3207 ; CHECK-NEXT:    %[[LCSSA_C:.*]] = phi i32 [ %[[TMP_C_SUM_C]], %[[LATCH_C]] ]
3208 ; CHECK-NEXT:    br label %[[EXIT_SPLIT]]
3209
3210 latch:
3211   %cmp2 = icmp slt i32 %tmp.c.sum, 42
3212   br i1 %cmp2, label %header, label %exit
3213
3214 exit:
3215   %lcssa.phi = phi i32 [ %tmp.c.sum, %latch ]
3216   ret i32 %lcssa.phi
3217 ; CHECK:       [[EXIT_SPLIT]]:
3218 ; CHECK-NEXT:    %[[EXIT_PHI1:.*]] = phi i32 [ %[[LCSSA_C]], %[[LOOP_EXIT_C]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3219 ; CHECK-NEXT:    br label %exit
3220
3221 ; CHECK:       exit:
3222 ; CHECK-NEXT:    %[[EXIT_PHI2:.*]] = phi i32 [ %[[EXIT_PHI1]], %[[EXIT_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3223 ; CHECK-NEXT:    ret i32 %[[EXIT_PHI2]]
3224 }
3225
3226 ; Similar to @test29 but designed to have one of the duplicate edges be
3227 ; a loop exit edge as those can in some cases be special. Among other things,
3228 ; this includes an LCSSA phi with multiple entries despite being a dedicated
3229 ; exit block.
3230 define i32 @test30(i32 %arg) {
3231 ; CHECK-LABEL: define i32 @test30(
3232 entry:
3233   br label %header
3234 ; CHECK-NEXT:  entry:
3235 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_EXIT:.*]] [
3236 ; CHECK-NEXT:      i32 -1, label %[[ENTRY_SPLIT_EXIT]]
3237 ; CHECK-NEXT:      i32 0, label %[[ENTRY_SPLIT_A:.*]]
3238 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_B:.*]]
3239 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_B]]
3240 ; CHECK-NEXT:    ]
3241
3242 header:
3243   %tmp = call i32 @d()
3244   %cmp1 = icmp eq i32 %tmp, 0
3245   br i1 %cmp1, label %body.a, label %dispatch
3246
3247 dispatch:
3248   switch i32 %arg, label %loop.exit1 [
3249     i32 -1, label %loop.exit1
3250     i32 0, label %body.a
3251     i32 1, label %body.b
3252     i32 2, label %body.b
3253   ]
3254
3255 body.a:
3256   %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ]
3257   %tmp.a = call i32 @a()
3258   %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a
3259   br label %body.b
3260 ; Unswitched 'a' loop.
3261 ;
3262 ; CHECK:       [[ENTRY_SPLIT_A]]:
3263 ; CHECK-NEXT:    br label %[[HEADER_A:.*]]
3264 ;
3265 ; CHECK:       [[HEADER_A]]:
3266 ; CHECK-NEXT:    %[[TMP_A:.*]] = call i32 @d()
3267 ; CHECK-NEXT:    %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0
3268 ; CHECK-NEXT:    br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]]
3269 ;
3270 ; CHECK:       [[DISPATCH_A]]:
3271 ; CHECK-NEXT:    br label %[[BODY_A_A]]
3272 ;
3273 ; CHECK:       [[BODY_A_A]]:
3274 ; CHECK-NEXT:    %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ]
3275 ; CHECK-NEXT:    %[[TMP_A_A:.*]] = call i32 @a()
3276 ; CHECK-NEXT:    %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]]
3277 ; CHECK-NEXT:    br label %[[BODY_B_A:.*]]
3278 ;
3279 ; CHECK:       [[BODY_B_A]]:
3280 ; CHECK-NEXT:    %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ]
3281 ; CHECK-NEXT:    %[[TMP_B_A:.*]] = call i32 @b()
3282 ; CHECK-NEXT:    %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]]
3283 ; CHECK-NEXT:    br label %[[LATCH_A:.*]]
3284 ;
3285 ; CHECK:       [[LATCH_A]]:
3286 ; CHECK-NEXT:    %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_B_SUM_A]], 42
3287 ; CHECK:         br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]]
3288 ;
3289 ; CHECK:       [[LOOP_EXIT_A]]:
3290 ; CHECK-NEXT:    %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[LATCH_A]] ]
3291 ; CHECK-NEXT:    br label %loop.exit2
3292
3293 body.b:
3294   %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ]
3295   %tmp.b = call i32 @b()
3296   %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b
3297   br label %latch
3298 ; Unswitched 'b' loop.
3299 ;
3300 ; CHECK:       [[ENTRY_SPLIT_B]]:
3301 ; CHECK-NEXT:    br label %[[HEADER_B:.*]]
3302 ;
3303 ; CHECK:       [[HEADER_B]]:
3304 ; CHECK-NEXT:    %[[TMP_B:.*]] = call i32 @d()
3305 ; CHECK-NEXT:    %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0
3306 ; CHECK-NEXT:    br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]]
3307 ;
3308 ; CHECK:       [[DISPATCH_B]]:
3309 ; CHECK-NEXT:    br label %[[BODY_B_B]]
3310 ;
3311 ; CHECK:       [[BODY_A_B]]:
3312 ; CHECK-NEXT:    %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ]
3313 ; CHECK-NEXT:    %[[TMP_A_B:.*]] = call i32 @a()
3314 ; CHECK-NEXT:    %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]]
3315 ; CHECK-NEXT:    br label %[[BODY_B_B:.*]]
3316 ;
3317 ; CHECK:       [[BODY_B_B]]:
3318 ; CHECK-NEXT:    %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ]
3319 ; CHECK-NEXT:    %[[TMP_B_B:.*]] = call i32 @b()
3320 ; CHECK-NEXT:    %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]]
3321 ; CHECK-NEXT:    br label %[[LATCH_B:.*]]
3322 ;
3323 ; CHECK:       [[LATCH_B]]:
3324 ; CHECK-NEXT:    %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_B_SUM_B]], 42
3325 ; CHECK:         br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]]
3326 ;
3327 ; CHECK:       [[LOOP_EXIT_B]]:
3328 ; CHECK-NEXT:    %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[LATCH_B]] ]
3329 ; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT:.*]]
3330
3331 latch:
3332   %cmp2 = icmp slt i32 %tmp.b.sum, 42
3333   br i1 %cmp2, label %header, label %loop.exit2
3334
3335 loop.exit1:
3336   %l1.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ]
3337   br label %exit
3338 ; Unswitched 'exit' loop.
3339 ;
3340 ; CHECK:       [[ENTRY_SPLIT_EXIT]]:
3341 ; CHECK-NEXT:    br label %[[HEADER_EXIT:.*]]
3342 ;
3343 ; CHECK:       [[HEADER_EXIT]]:
3344 ; CHECK-NEXT:    %[[TMP_EXIT:.*]] = call i32 @d()
3345 ; CHECK-NEXT:    %[[CMP1_EXIT:.*]] = icmp eq i32 %[[TMP_EXIT]], 0
3346 ; CHECK-NEXT:    br i1 %[[CMP1_EXIT]], label %[[BODY_A_EXIT:.*]], label %[[DISPATCH_EXIT:.*]]
3347 ;
3348 ; CHECK:       [[DISPATCH_EXIT]]:
3349 ; CHECK-NEXT:    %[[TMP_LCSSA:.*]] = phi i32 [ %[[TMP_EXIT]], %[[HEADER_EXIT]] ]
3350 ; CHECK-NEXT:    br label %loop.exit1
3351 ;
3352 ; CHECK:       [[BODY_A_EXIT]]:
3353 ; CHECK-NEXT:    %[[TMP_A_PHI_EXIT:.*]] = phi i32 [ 0, %[[HEADER_EXIT]] ]
3354 ; CHECK-NEXT:    %[[TMP_A_EXIT:.*]] = call i32 @a()
3355 ; CHECK-NEXT:    %[[TMP_A_SUM_EXIT:.*]] = add i32 %[[TMP_A_PHI_EXIT]], %[[TMP_A_EXIT]]
3356 ; CHECK-NEXT:    br label %[[BODY_B_EXIT:.*]]
3357 ;
3358 ; CHECK:       [[BODY_B_EXIT]]:
3359 ; CHECK-NEXT:    %[[TMP_B_PHI_EXIT:.*]] = phi i32 [ %[[TMP_A_SUM_EXIT]], %[[BODY_A_EXIT]] ]
3360 ; CHECK-NEXT:    %[[TMP_B_EXIT:.*]] = call i32 @b()
3361 ; CHECK-NEXT:    %[[TMP_B_SUM_EXIT:.*]] = add i32 %[[TMP_B_PHI_EXIT]], %[[TMP_B_EXIT]]
3362 ; CHECK-NEXT:    br label %[[LATCH_EXIT:.*]]
3363 ;
3364 ; CHECK:       [[LATCH_EXIT]]:
3365 ; CHECK-NEXT:    %[[CMP2_EXIT:.*]] = icmp slt i32 %[[TMP_B_SUM_EXIT]], 42
3366 ; CHECK:         br i1 %[[CMP2_EXIT]], label %[[HEADER_EXIT]], label %[[LOOP_EXIT_EXIT:.*]]
3367 ;
3368 ; CHECK:       loop.exit1:
3369 ; CHECK-NEXT:    %[[L1_PHI:.*]] = phi i32 [ %[[TMP_LCSSA]], %[[DISPATCH_EXIT]] ]
3370 ; CHECK-NEXT:    br label %exit
3371 ;
3372 ; CHECK:       [[LOOP_EXIT_EXIT]]:
3373 ; CHECK-NEXT:    %[[L2_PHI:.*]] = phi i32 [ %[[TMP_B_SUM_EXIT]], %[[LATCH_EXIT]] ]
3374 ; CHECK-NEXT:    br label %[[LOOP_EXIT2_SPLIT]]
3375
3376 loop.exit2:
3377   %l2.phi = phi i32 [ %tmp.b.sum, %latch ]
3378   br label %exit
3379 ; CHECK:       [[LOOP_EXIT2_SPLIT]]:
3380 ; CHECK-NEXT:    %[[LOOP_EXIT_PHI1:.*]] = phi i32 [ %[[L2_PHI]], %[[LOOP_EXIT_EXIT]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ]
3381 ; CHECK-NEXT:    br label %loop.exit2
3382 ;
3383 ; CHECK:       loop.exit2:
3384 ; CHECK-NEXT:    %[[LOOP_EXIT_PHI2:.*]] = phi i32 [ %[[LOOP_EXIT_PHI1]], %[[LOOP_EXIT2_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ]
3385 ; CHECK-NEXT:    br label %exit
3386
3387 exit:
3388   %l.phi = phi i32 [ %l1.phi, %loop.exit1 ], [ %l2.phi, %loop.exit2 ]
3389   ret i32 %l.phi
3390 ; CHECK:       exit:
3391 ; CHECK-NEXT:    %[[EXIT_PHI:.*]] = phi i32 [ %[[L1_PHI]], %loop.exit1 ], [ %[[LOOP_EXIT_PHI2]], %loop.exit2 ]
3392 ; CHECK-NEXT:    ret i32 %[[EXIT_PHI]]
3393 }
3394
3395 ; Unswitch will not actually change the loop nest from:
3396 ;   A < B < C
3397 define void @hoist_inner_loop0() {
3398 ; CHECK-LABEL: define void @hoist_inner_loop0(
3399 entry:
3400   br label %a.header
3401 ; CHECK:       entry:
3402 ; CHECK-NEXT:    br label %a.header
3403
3404 a.header:
3405   br label %b.header
3406 ; CHECK:       a.header:
3407 ; CHECK-NEXT:    br label %b.header
3408
3409 b.header:
3410   %v1 = call i1 @cond()
3411   br label %c.header
3412 ; CHECK:       b.header:
3413 ; CHECK-NEXT:    %v1 = call i1 @cond()
3414 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3415 ;
3416 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3417 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3418 ;
3419 ; CHECK:       [[C_HEADER_US]]:
3420 ; CHECK-NEXT:    call i32 @c()
3421 ; CHECK-NEXT:    br label %[[B_LATCH_SPLIT_US:.*]]
3422 ;
3423 ; CHECK:       [[B_LATCH_SPLIT_US]]:
3424 ; CHECK-NEXT:    br label %b.latch
3425 ;
3426 ; CHECK:       [[B_HEADER_SPLIT]]:
3427 ; CHECK-NEXT:    br label %c.header
3428
3429 c.header:
3430   call i32 @c()
3431   br i1 %v1, label %b.latch, label %c.latch
3432 ; CHECK:       c.header:
3433 ; CHECK-NEXT:    call i32 @c()
3434 ; CHECK-NEXT:    br label %c.latch
3435
3436 c.latch:
3437   %v2 = call i1 @cond()
3438   br i1 %v2, label %c.header, label %b.latch
3439 ; CHECK:       c.latch:
3440 ; CHECK-NEXT:    %v2 = call i1 @cond()
3441 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]]
3442
3443 b.latch:
3444   %v3 = call i1 @cond()
3445   br i1 %v3, label %b.header, label %a.latch
3446 ; CHECK:       [[B_LATCH_SPLIT]]:
3447 ; CHECK-NEXT:    br label %b.latch
3448 ;
3449 ; CHECK:       b.latch:
3450 ; CHECK-NEXT:    %v3 = call i1 @cond()
3451 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3452
3453 a.latch:
3454   br label %a.header
3455 ; CHECK:       a.latch:
3456 ; CHECK-NEXT:    br label %a.header
3457
3458 exit:
3459   ret void
3460 ; CHECK:       exit:
3461 ; CHECK-NEXT:    ret void
3462 }
3463
3464 ; Unswitch will transform the loop nest from:
3465 ;   A < B < C
3466 ; into
3467 ;   A < (B, C)
3468 define void @hoist_inner_loop1(i32* %ptr) {
3469 ; CHECK-LABEL: define void @hoist_inner_loop1(
3470 entry:
3471   br label %a.header
3472 ; CHECK:       entry:
3473 ; CHECK-NEXT:    br label %a.header
3474
3475 a.header:
3476   %x.a = load i32, i32* %ptr
3477   br label %b.header
3478 ; CHECK:       a.header:
3479 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3480 ; CHECK-NEXT:    br label %b.header
3481
3482 b.header:
3483   %x.b = load i32, i32* %ptr
3484   %v1 = call i1 @cond()
3485   br label %c.header
3486 ; CHECK:       b.header:
3487 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3488 ; CHECK-NEXT:    %v1 = call i1 @cond()
3489 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3490 ;
3491 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3492 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3493 ;
3494 ; CHECK:       [[C_HEADER_US]]:
3495 ; CHECK-NEXT:    call i32 @c()
3496 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3497 ;
3498 ; CHECK:       [[B_LATCH_US]]:
3499 ; CHECK-NEXT:    br label %b.latch
3500 ;
3501 ; CHECK:       [[B_HEADER_SPLIT]]:
3502 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3503 ; CHECK-NEXT:    br label %c.header
3504
3505 c.header:
3506   call i32 @c()
3507   br i1 %v1, label %b.latch, label %c.latch
3508 ; CHECK:       c.header:
3509 ; CHECK-NEXT:    call i32 @c()
3510 ; CHECK-NEXT:    br label %c.latch
3511
3512 c.latch:
3513   ; Use values from other loops to check LCSSA form.
3514   store i32 %x.a, i32* %ptr
3515   store i32 %x.b, i32* %ptr
3516   %v2 = call i1 @cond()
3517   br i1 %v2, label %c.header, label %a.exit.c
3518 ; CHECK:       c.latch:
3519 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3520 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3521 ; CHECK-NEXT:    %v2 = call i1 @cond()
3522 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %a.exit.c
3523
3524 b.latch:
3525   %v3 = call i1 @cond()
3526   br i1 %v3, label %b.header, label %a.exit.b
3527 ; CHECK:       b.latch:
3528 ; CHECK-NEXT:    %v3 = call i1 @cond()
3529 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.exit.b
3530
3531 a.exit.c:
3532   br label %a.latch
3533 ; CHECK:       a.exit.c
3534 ; CHECK-NEXT:    br label %a.latch
3535
3536 a.exit.b:
3537   br label %a.latch
3538 ; CHECK:       a.exit.b:
3539 ; CHECK-NEXT:    br label %a.latch
3540
3541 a.latch:
3542   br label %a.header
3543 ; CHECK:       a.latch:
3544 ; CHECK-NEXT:    br label %a.header
3545
3546 exit:
3547   ret void
3548 ; CHECK:       exit:
3549 ; CHECK-NEXT:    ret void
3550 }
3551
3552 ; Unswitch will transform the loop nest from:
3553 ;   A < B < C
3554 ; into
3555 ;   (A < B), C
3556 define void @hoist_inner_loop2(i32* %ptr) {
3557 ; CHECK-LABEL: define void @hoist_inner_loop2(
3558 entry:
3559   br label %a.header
3560 ; CHECK:       entry:
3561 ; CHECK-NEXT:    br label %a.header
3562
3563 a.header:
3564   %x.a = load i32, i32* %ptr
3565   br label %b.header
3566 ; CHECK:       a.header:
3567 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3568 ; CHECK-NEXT:    br label %b.header
3569
3570 b.header:
3571   %x.b = load i32, i32* %ptr
3572   %v1 = call i1 @cond()
3573   br label %c.header
3574 ; CHECK:       b.header:
3575 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3576 ; CHECK-NEXT:    %v1 = call i1 @cond()
3577 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3578 ;
3579 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3580 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3581 ;
3582 ; CHECK:       [[C_HEADER_US]]:
3583 ; CHECK-NEXT:    call i32 @c()
3584 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3585 ;
3586 ; CHECK:       [[B_LATCH_US]]:
3587 ; CHECK-NEXT:    br label %b.latch
3588 ;
3589 ; CHECK:       [[B_HEADER_SPLIT]]:
3590 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3591 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3592 ; CHECK-NEXT:    br label %c.header
3593
3594 c.header:
3595   call i32 @c()
3596   br i1 %v1, label %b.latch, label %c.latch
3597 ; CHECK:       c.header:
3598 ; CHECK-NEXT:    call i32 @c()
3599 ; CHECK-NEXT:    br label %c.latch
3600
3601 c.latch:
3602   ; Use values from other loops to check LCSSA form.
3603   store i32 %x.a, i32* %ptr
3604   store i32 %x.b, i32* %ptr
3605   %v2 = call i1 @cond()
3606   br i1 %v2, label %c.header, label %exit
3607 ; CHECK:       c.latch:
3608 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3609 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3610 ; CHECK-NEXT:    %v2 = call i1 @cond()
3611 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
3612
3613 b.latch:
3614   %v3 = call i1 @cond()
3615   br i1 %v3, label %b.header, label %a.latch
3616 ; CHECK:       b.latch:
3617 ; CHECK-NEXT:    %v3 = call i1 @cond()
3618 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
3619
3620 a.latch:
3621   br label %a.header
3622 ; CHECK:       a.latch:
3623 ; CHECK-NEXT:    br label %a.header
3624
3625 exit:
3626   ret void
3627 ; CHECK:       exit:
3628 ; CHECK-NEXT:    ret void
3629 }
3630
3631 ; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop.
3632 ; Unswitch will transform the loop nest from:
3633 ;   A < B < C < D
3634 ; into
3635 ;   (A < B), (C < D)
3636 define void @hoist_inner_loop3(i32* %ptr) {
3637 ; CHECK-LABEL: define void @hoist_inner_loop3(
3638 entry:
3639   br label %a.header
3640 ; CHECK:       entry:
3641 ; CHECK-NEXT:    br label %a.header
3642
3643 a.header:
3644   %x.a = load i32, i32* %ptr
3645   br label %b.header
3646 ; CHECK:       a.header:
3647 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3648 ; CHECK-NEXT:    br label %b.header
3649
3650 b.header:
3651   %x.b = load i32, i32* %ptr
3652   %v1 = call i1 @cond()
3653   br label %c.header
3654 ; CHECK:       b.header:
3655 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3656 ; CHECK-NEXT:    %v1 = call i1 @cond()
3657 ; CHECK-NEXT:    br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]]
3658 ;
3659 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3660 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3661 ;
3662 ; CHECK:       [[C_HEADER_US]]:
3663 ; CHECK-NEXT:    call i32 @c()
3664 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3665 ;
3666 ; CHECK:       [[B_LATCH_US]]:
3667 ; CHECK-NEXT:    br label %b.latch
3668 ;
3669 ; CHECK:       [[B_HEADER_SPLIT]]:
3670 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3671 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3672 ; CHECK-NEXT:    br label %c.header
3673
3674 c.header:
3675   call i32 @c()
3676   br i1 %v1, label %b.latch, label %c.body
3677 ; CHECK:       c.header:
3678 ; CHECK-NEXT:    call i32 @c()
3679 ; CHECK-NEXT:    br label %c.body
3680
3681 c.body:
3682   %x.c = load i32, i32* %ptr
3683   br label %d.header
3684 ; CHECK:       c.body:
3685 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3686 ; CHECK-NEXT:    br label %d.header
3687
3688 d.header:
3689   ; Use values from other loops to check LCSSA form.
3690   store i32 %x.a, i32* %ptr
3691   store i32 %x.b, i32* %ptr
3692   store i32 %x.c, i32* %ptr
3693   %v2 = call i1 @cond()
3694   br i1 %v2, label %d.header, label %c.latch
3695 ; CHECK:       d.header:
3696 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3697 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3698 ; CHECK-NEXT:    store i32 %x.c, i32* %ptr
3699 ; CHECK-NEXT:    %v2 = call i1 @cond()
3700 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %c.latch
3701
3702 c.latch:
3703   %v3 = call i1 @cond()
3704   br i1 %v3, label %c.header, label %exit
3705 ; CHECK:       c.latch:
3706 ; CHECK-NEXT:    %v3 = call i1 @cond()
3707 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %exit
3708
3709 b.latch:
3710   %v4 = call i1 @cond()
3711   br i1 %v4, label %b.header, label %a.latch
3712 ; CHECK:       b.latch:
3713 ; CHECK-NEXT:    %v4 = call i1 @cond()
3714 ; CHECK-NEXT:    br i1 %v4, label %b.header, label %a.latch
3715
3716 a.latch:
3717   br label %a.header
3718 ; CHECK:       a.latch:
3719 ; CHECK-NEXT:    br label %a.header
3720
3721 exit:
3722   ret void
3723 ; CHECK:       exit:
3724 ; CHECK-NEXT:    ret void
3725 }
3726
3727 ; This test is designed to exercise checking multiple remaining exits from the
3728 ; loop being unswitched.
3729 ; Unswitch will transform the loop nest from:
3730 ;   A < B < C < D
3731 ; into
3732 ;   A < B < (C, D)
3733 define void @hoist_inner_loop4() {
3734 ; CHECK-LABEL: define void @hoist_inner_loop4(
3735 entry:
3736   br label %a.header
3737 ; CHECK:       entry:
3738 ; CHECK-NEXT:    br label %a.header
3739
3740 a.header:
3741   br label %b.header
3742 ; CHECK:       a.header:
3743 ; CHECK-NEXT:    br label %b.header
3744
3745 b.header:
3746   br label %c.header
3747 ; CHECK:       b.header:
3748 ; CHECK-NEXT:    br label %c.header
3749
3750 c.header:
3751   %v1 = call i1 @cond()
3752   br label %d.header
3753 ; CHECK:       c.header:
3754 ; CHECK-NEXT:    %v1 = call i1 @cond()
3755 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3756 ;
3757 ; CHECK:       [[C_HEADER_SPLIT_US]]:
3758 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3759 ;
3760 ; CHECK:       [[D_HEADER_US]]:
3761 ; CHECK-NEXT:    call i32 @d()
3762 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3763 ;
3764 ; CHECK:       [[C_LATCH_US]]:
3765 ; CHECK-NEXT:    br label %c.latch
3766 ;
3767 ; CHECK:       [[C_HEADER_SPLIT]]:
3768 ; CHECK-NEXT:    br label %d.header
3769
3770 d.header:
3771   call i32 @d()
3772   br i1 %v1, label %c.latch, label %d.exiting1
3773 ; CHECK:       d.header:
3774 ; CHECK-NEXT:    call i32 @d()
3775 ; CHECK-NEXT:    br label %d.exiting1
3776
3777 d.exiting1:
3778   %v2 = call i1 @cond()
3779   br i1 %v2, label %d.exiting2, label %a.latch
3780 ; CHECK:       d.exiting1:
3781 ; CHECK-NEXT:    %v2 = call i1 @cond()
3782 ; CHECK-NEXT:    br i1 %v2, label %d.exiting2, label %a.latch
3783
3784 d.exiting2:
3785   %v3 = call i1 @cond()
3786   br i1 %v3, label %d.exiting3, label %loopexit.d
3787 ; CHECK:       d.exiting2:
3788 ; CHECK-NEXT:    %v3 = call i1 @cond()
3789 ; CHECK-NEXT:    br i1 %v3, label %d.exiting3, label %loopexit.d
3790
3791 d.exiting3:
3792   %v4 = call i1 @cond()
3793   br i1 %v4, label %d.latch, label %b.latch
3794 ; CHECK:       d.exiting3:
3795 ; CHECK-NEXT:    %v4 = call i1 @cond()
3796 ; CHECK-NEXT:    br i1 %v4, label %d.latch, label %b.latch
3797
3798 d.latch:
3799   br label %d.header
3800 ; CHECK:       d.latch:
3801 ; CHECK-NEXT:    br label %d.header
3802
3803 c.latch:
3804   %v5 = call i1 @cond()
3805   br i1 %v5, label %c.header, label %loopexit.c
3806 ; CHECK:       c.latch:
3807 ; CHECK-NEXT:    %v5 = call i1 @cond()
3808 ; CHECK-NEXT:    br i1 %v5, label %c.header, label %loopexit.c
3809
3810 b.latch:
3811   br label %b.header
3812 ; CHECK:       b.latch:
3813 ; CHECK-NEXT:    br label %b.header
3814
3815 a.latch:
3816   br label %a.header
3817 ; CHECK:       a.latch:
3818 ; CHECK-NEXT:    br label %a.header
3819
3820 loopexit.d:
3821   br label %exit
3822 ; CHECK:       loopexit.d:
3823 ; CHECK-NEXT:    br label %exit
3824
3825 loopexit.c:
3826   br label %exit
3827 ; CHECK:       loopexit.c:
3828 ; CHECK-NEXT:    br label %exit
3829
3830 exit:
3831   ret void
3832 ; CHECK:       exit:
3833 ; CHECK-NEXT:    ret void
3834 }
3835
3836 ; Unswitch will transform the loop nest from:
3837 ;   A < B < C < D
3838 ; into
3839 ;   A < ((B < C), D)
3840 define void @hoist_inner_loop5(i32* %ptr) {
3841 ; CHECK-LABEL: define void @hoist_inner_loop5(
3842 entry:
3843   br label %a.header
3844 ; CHECK:       entry:
3845 ; CHECK-NEXT:    br label %a.header
3846
3847 a.header:
3848   %x.a = load i32, i32* %ptr
3849   br label %b.header
3850 ; CHECK:       a.header:
3851 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3852 ; CHECK-NEXT:    br label %b.header
3853
3854 b.header:
3855   %x.b = load i32, i32* %ptr
3856   br label %c.header
3857 ; CHECK:       b.header:
3858 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3859 ; CHECK-NEXT:    br label %c.header
3860
3861 c.header:
3862   %x.c = load i32, i32* %ptr
3863   %v1 = call i1 @cond()
3864   br label %d.header
3865 ; CHECK:       c.header:
3866 ; CHECK-NEXT:    %x.c = load i32, i32* %ptr
3867 ; CHECK-NEXT:    %v1 = call i1 @cond()
3868 ; CHECK-NEXT:    br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]]
3869 ;
3870 ; CHECK:       [[C_HEADER_SPLIT_US]]:
3871 ; CHECK-NEXT:    br label %[[D_HEADER_US:.*]]
3872 ;
3873 ; CHECK:       [[D_HEADER_US]]:
3874 ; CHECK-NEXT:    call i32 @d()
3875 ; CHECK-NEXT:    br label %[[C_LATCH_US:.*]]
3876 ;
3877 ; CHECK:       [[C_LATCH_US]]:
3878 ; CHECK-NEXT:    br label %c.latch
3879 ;
3880 ; CHECK:       [[C_HEADER_SPLIT]]:
3881 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ]
3882 ; CHECK-NEXT:    %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ]
3883 ; CHECK-NEXT:    br label %d.header
3884
3885 d.header:
3886   call i32 @d()
3887   br i1 %v1, label %c.latch, label %d.latch
3888 ; CHECK:       d.header:
3889 ; CHECK-NEXT:    call i32 @d()
3890 ; CHECK-NEXT:    br label %d.latch
3891
3892 d.latch:
3893   ; Use values from other loops to check LCSSA form.
3894   store i32 %x.a, i32* %ptr
3895   store i32 %x.b, i32* %ptr
3896   store i32 %x.c, i32* %ptr
3897   %v2 = call i1 @cond()
3898   br i1 %v2, label %d.header, label %a.latch
3899 ; CHECK:       d.latch:
3900 ; CHECK-NEXT:    store i32 %x.a, i32* %ptr
3901 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3902 ; CHECK-NEXT:    store i32 %[[X_C_LCSSA]], i32* %ptr
3903 ; CHECK-NEXT:    %v2 = call i1 @cond()
3904 ; CHECK-NEXT:    br i1 %v2, label %d.header, label %a.latch
3905
3906 c.latch:
3907   %v3 = call i1 @cond()
3908   br i1 %v3, label %c.header, label %b.latch
3909 ; CHECK:       c.latch:
3910 ; CHECK-NEXT:    %v3 = call i1 @cond()
3911 ; CHECK-NEXT:    br i1 %v3, label %c.header, label %b.latch
3912
3913 b.latch:
3914   br label %b.header
3915 ; CHECK:       b.latch:
3916 ; CHECK-NEXT:    br label %b.header
3917
3918 a.latch:
3919   br label %a.header
3920 ; CHECK:       a.latch:
3921 ; CHECK-NEXT:    br label %a.header
3922
3923 exit:
3924   ret void
3925 ; CHECK:       exit:
3926 ; CHECK-NEXT:    ret void
3927 }
3928
3929 define void @hoist_inner_loop_switch(i32* %ptr) {
3930 ; CHECK-LABEL: define void @hoist_inner_loop_switch(
3931 entry:
3932   br label %a.header
3933 ; CHECK:       entry:
3934 ; CHECK-NEXT:    br label %a.header
3935
3936 a.header:
3937   %x.a = load i32, i32* %ptr
3938   br label %b.header
3939 ; CHECK:       a.header:
3940 ; CHECK-NEXT:    %x.a = load i32, i32* %ptr
3941 ; CHECK-NEXT:    br label %b.header
3942
3943 b.header:
3944   %x.b = load i32, i32* %ptr
3945   %v1 = call i32 @cond.i32()
3946   br label %c.header
3947 ; CHECK:       b.header:
3948 ; CHECK-NEXT:    %x.b = load i32, i32* %ptr
3949 ; CHECK-NEXT:    %v1 = call i32 @cond.i32()
3950 ; CHECK-NEXT:    switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [
3951 ; CHECK-NEXT:      i32 1, label %[[B_HEADER_SPLIT_US:.*]]
3952 ; CHECK-NEXT:      i32 2, label %[[B_HEADER_SPLIT_US]]
3953 ; CHECK-NEXT:      i32 3, label %[[B_HEADER_SPLIT_US]]
3954 ; CHECK-NEXT:    ]
3955 ;
3956 ; CHECK:       [[B_HEADER_SPLIT_US]]:
3957 ; CHECK-NEXT:    br label %[[C_HEADER_US:.*]]
3958 ;
3959 ; CHECK:       [[C_HEADER_US]]:
3960 ; CHECK-NEXT:    call i32 @c()
3961 ; CHECK-NEXT:    br label %[[B_LATCH_US:.*]]
3962 ;
3963 ; CHECK:       [[B_LATCH_US]]:
3964 ; CHECK-NEXT:    br label %b.latch
3965 ;
3966 ; CHECK:       [[B_HEADER_SPLIT]]:
3967 ; CHECK-NEXT:    %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ]
3968 ; CHECK-NEXT:    %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ]
3969 ; CHECK-NEXT:    br label %c.header
3970
3971 c.header:
3972   call i32 @c()
3973   switch i32 %v1, label %c.latch [
3974     i32 1, label %b.latch
3975     i32 2, label %b.latch
3976     i32 3, label %b.latch
3977   ]
3978 ; CHECK:       c.header:
3979 ; CHECK-NEXT:    call i32 @c()
3980 ; CHECK-NEXT:    br label %c.latch
3981
3982 c.latch:
3983   ; Use values from other loops to check LCSSA form.
3984   store i32 %x.a, i32* %ptr
3985   store i32 %x.b, i32* %ptr
3986   %v2 = call i1 @cond()
3987   br i1 %v2, label %c.header, label %exit
3988 ; CHECK:       c.latch:
3989 ; CHECK-NEXT:    store i32 %[[X_A_LCSSA]], i32* %ptr
3990 ; CHECK-NEXT:    store i32 %[[X_B_LCSSA]], i32* %ptr
3991 ; CHECK-NEXT:    %v2 = call i1 @cond()
3992 ; CHECK-NEXT:    br i1 %v2, label %c.header, label %exit
3993
3994 b.latch:
3995   %v3 = call i1 @cond()
3996   br i1 %v3, label %b.header, label %a.latch
3997 ; CHECK:       b.latch:
3998 ; CHECK-NEXT:    %v3 = call i1 @cond()
3999 ; CHECK-NEXT:    br i1 %v3, label %b.header, label %a.latch
4000
4001 a.latch:
4002   br label %a.header
4003 ; CHECK:       a.latch:
4004 ; CHECK-NEXT:    br label %a.header
4005
4006 exit:
4007   ret void
4008 ; CHECK:       exit:
4009 ; CHECK-NEXT:    ret void
4010 }
4011
4012 ; A devilish pattern. This is a crafty, crafty test case designed to risk
4013 ; creating indirect cycles with trivial and non-trivial unswitching. The inner
4014 ; loop has a switch with a trivial exit edge that can be unswitched, but the
4015 ; rest of the switch cannot be unswitched because its cost is too high.
4016 ; However, the unswitching of the trivial edge creates a new switch in the
4017 ; outer loop. *This* switch isn't trivial, but has a low cost to unswitch. When
4018 ; we unswitch this switch from the outer loop, we will remove it completely and
4019 ; create a clone of the inner loop on one side. This clone will then again be
4020 ; viable for unswitching the inner-most loop. This lets us check that the
4021 ; unswitching doesn't end up cycling infinitely even when the cycle is
4022 ; indirect and due to revisiting a loop after cloning.
4023 define void @test31(i32 %arg) {
4024 ; CHECK-LABEL: define void @test31(
4025 entry:
4026   br label %outer.header
4027 ; CHECK-NEXT:  entry:
4028 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT:.*]] [
4029 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US:.*]]
4030 ; CHECK-NEXT:      i32 2, label %[[ENTRY_SPLIT_US]]
4031 ; CHECK-NEXT:    ]
4032 ;
4033 ; CHECK:       [[ENTRY_SPLIT_US]]:
4034 ; CHECK-NEXT:    switch i32 %arg, label %[[ENTRY_SPLIT_US_SPLIT:.*]] [
4035 ; CHECK-NEXT:      i32 1, label %[[ENTRY_SPLIT_US_SPLIT_US:.*]]
4036 ; CHECK-NEXT:    ]
4037
4038 outer.header:
4039   br label %inner.header
4040
4041 inner.header:
4042   switch i32 %arg, label %inner.loopexit1 [
4043     i32 1, label %inner.body1
4044     i32 2, label %inner.body2
4045   ]
4046
4047 inner.body1:
4048   %a = call i32 @a()
4049   br label %inner.latch
4050 ; The (super convoluted) fully unswitched loop around `@a`.
4051 ;
4052 ; CHECK:       [[ENTRY_SPLIT_US_SPLIT_US]]:
4053 ; CHECK-NEXT:    br label %[[OUTER_HEADER_US_US:.*]]
4054 ;
4055 ; CHECK:       [[OUTER_HEADER_US_US]]:
4056 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US_US:.*]]
4057 ;
4058 ; CHECK:       [[OUTER_LATCH_US_US:.*]]:
4059 ; CHECK-NEXT:    %[[OUTER_COND_US_US:.*]] = call i1 @cond()
4060 ; CHECK-NEXT:    br i1 %[[OUTER_COND_US_US]], label %[[OUTER_HEADER_US_US]], label %[[EXIT_SPLIT_US_SPLIT_US:.*]]
4061 ;
4062 ; CHECK:       [[OUTER_HEADER_SPLIT_US_US]]:
4063 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US_US_US:.*]]
4064 ;
4065 ; CHECK:       [[INNER_LOOPEXIT2_US_US:.*]]:
4066 ; CHECK-NEXT:    br label %[[OUTER_LATCH_US_US]]
4067 ;
4068 ; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US_US_US]]:
4069 ; CHECK-NEXT:    br label %[[INNER_HEADER_US_US_US:.*]]
4070 ;
4071 ; CHECK:       [[INNER_HEADER_US_US_US]]:
4072 ; CHECK-NEXT:    br label %[[INNER_BODY1_US_US_US:.*]]
4073 ;
4074 ; CHECK:       [[INNER_BODY1_US_US_US]]:
4075 ; CHECK-NEXT:    %[[A:.*]] = call i32 @a()
4076 ; CHECK-NEXT:    br label %[[INNER_LATCH_US_US_US:.*]]
4077 ;
4078 ; CHECK:       [[INNER_LATCH_US_US_US]]:
4079 ; CHECK-NEXT:    %[[PHI_A:.*]] = phi i32 [ %[[A]], %[[INNER_BODY1_US_US_US]] ]
4080 ; CHECK-NEXT:    call void @sink1(i32 0)
4081 ; CHECK-NEXT:    call void @sink1(i32 0)
4082 ; CHECK-NEXT:    call void @sink1(i32 0)
4083 ; CHECK-NEXT:    call void @sink1(i32 0)
4084 ; CHECK-NEXT:    call void @sink1(i32 0)
4085 ; CHECK-NEXT:    call void @sink1(i32 0)
4086 ; CHECK-NEXT:    call void @sink1(i32 0)
4087 ; CHECK-NEXT:    call void @sink1(i32 0)
4088 ; CHECK-NEXT:    call void @sink1(i32 0)
4089 ; CHECK-NEXT:    call void @sink1(i32 0)
4090 ; CHECK-NEXT:    call void @sink1(i32 %[[PHI_A]])
4091 ; CHECK-NEXT:    %[[INNER_COND_US_US_US:.*]] = call i1 @cond()
4092 ; CHECK-NEXT:    br i1 %[[INNER_COND_US_US_US]], label %[[INNER_HEADER_US_US_US]], label %[[INNER_LOOPEXIT2_SPLIT_US_US_US:.*]]
4093 ;
4094 ; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US_US_US]]:
4095 ; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US_US]]
4096 ;
4097 ; CHECK:       [[EXIT_SPLIT_US_SPLIT_US]]:
4098 ; CHECK-NEXT:    br label %[[EXIT_SPLIT_US:.*]]
4099
4100
4101 inner.body2:
4102   %b = call i32 @b()
4103   br label %inner.latch
4104 ; The fully unswitched loop around `@b`.
4105 ;
4106 ; CHECK:       [[ENTRY_SPLIT_US_SPLIT]]:
4107 ; CHECK-NEXT:    br label %[[OUTER_HEADER_US:.*]]
4108 ;
4109 ; CHECK:       [[OUTER_HEADER_US]]:
4110 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_US:.*]]
4111 ;
4112 ; CHECK:       [[INNER_HEADER_US:.*]]:
4113 ; CHECK-NEXT:    br label %[[INNER_BODY2_US:.*]]
4114 ;
4115 ; CHECK:       [[INNER_BODY2_US]]:
4116 ; CHECK-NEXT:    %[[B:.*]] = call i32 @b()
4117 ; CHECK-NEXT:    br label %[[INNER_LATCH_US:.*]]
4118 ;
4119 ; CHECK:       [[INNER_LATCH_US]]:
4120 ; CHECK-NEXT:    call void @sink1(i32 0)
4121 ; CHECK-NEXT:    call void @sink1(i32 0)
4122 ; CHECK-NEXT:    call void @sink1(i32 0)
4123 ; CHECK-NEXT:    call void @sink1(i32 0)
4124 ; CHECK-NEXT:    call void @sink1(i32 0)
4125 ; CHECK-NEXT:    call void @sink1(i32 0)
4126 ; CHECK-NEXT:    call void @sink1(i32 0)
4127 ; CHECK-NEXT:    call void @sink1(i32 0)
4128 ; CHECK-NEXT:    call void @sink1(i32 0)
4129 ; CHECK-NEXT:    call void @sink1(i32 0)
4130 ; CHECK-NEXT:    call void @sink1(i32 %[[B]])
4131 ; CHECK-NEXT:    %[[INNER_COND_US:.*]] = call i1 @cond()
4132 ; CHECK-NEXT:    br i1 %[[INNER_COND_US]], label %[[INNER_HEADER_US]], label %[[INNER_LOOPEXIT2_SPLIT_US:.*]]
4133 ;
4134 ; CHECK:       [[INNER_LOOPEXIT2_SPLIT_US]]:
4135 ; CHECK-NEXT:    br label %[[INNER_LOOPEXIT2_US:.*]]
4136 ;
4137 ; CHECK:       [[OUTER_LATCH_US:.*]]:
4138 ; CHECK-NEXT:    %[[OUTER_COND_US:.*]] = call i1 @cond()
4139 ; CHECK-NEXT:    br i1 %[[OUTER_COND_US]], label %[[OUTER_HEADER_US]], label %[[EXIT_SPLIT_US_SPLIT:.*]]
4140 ;
4141 ; CHECK:       [[OUTER_HEADER_SPLIT_US]]:
4142 ; CHECK-NEXT:    br label %[[OUTER_HEADER_SPLIT_SPLIT_US:.*]]
4143 ;
4144 ; CHECK:       [[OUTER_HEADER_SPLIT_SPLIT_US]]:
4145 ; CHECK-NEXT:    br label %[[INNER_HEADER_US]]
4146 ;
4147 ; CHECK:       [[INNER_LOOPEXIT2_US]]:
4148 ; CHECK-NEXT:    br label %[[OUTER_LATCH_US]]
4149 ;
4150 ; CHECK:       [[EXIT_SPLIT_US]]:
4151 ; CHECK-NEXT:    br label %exit
4152
4153 inner.latch:
4154   %phi = phi i32 [ %a, %inner.body1 ], [ %b, %inner.body2 ]
4155   ; Make 10 junk calls here to ensure we're over the "50" cost threshold of
4156   ; non-trivial unswitching for this inner switch.
4157   call void @sink1(i32 0)
4158   call void @sink1(i32 0)
4159   call void @sink1(i32 0)
4160   call void @sink1(i32 0)
4161   call void @sink1(i32 0)
4162   call void @sink1(i32 0)
4163   call void @sink1(i32 0)
4164   call void @sink1(i32 0)
4165   call void @sink1(i32 0)
4166   call void @sink1(i32 0)
4167   call void @sink1(i32 %phi)
4168   %inner.cond = call i1 @cond()
4169   br i1 %inner.cond, label %inner.header, label %inner.loopexit2
4170
4171 inner.loopexit1:
4172   br label %outer.latch
4173 ; The unswitched `loopexit1` path.
4174 ;
4175 ; CHECK:       [[ENTRY_SPLIT]]:
4176 ; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
4177 ;
4178 ; CHECK:       outer.header:
4179 ; CHECK-NEXT:    br label %inner.loopexit1
4180 ;
4181 ; CHECK:       inner.loopexit1:
4182 ; CHECK-NEXT:    br label %outer.latch
4183 ;
4184 ; CHECK:       outer.latch:
4185 ; CHECK-NEXT:    %outer.cond = call i1 @cond()
4186 ; CHECK-NEXT:    br i1 %outer.cond, label %outer.header, label %[[EXIT_SPLIT:.*]]
4187 ;
4188 ; CHECK:       [[EXIT_SPLIT]]:
4189 ; CHECK-NEXT:    br label %exit
4190
4191 inner.loopexit2:
4192   br label %outer.latch
4193
4194 outer.latch:
4195   %outer.cond = call i1 @cond()
4196   br i1 %outer.cond, label %outer.header, label %exit
4197
4198 exit:
4199   ret void
4200 ; CHECK:       exit:
4201 ; CHECK-NEXT:    ret void
4202 }
4203
4204 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `and`
4205 ; chain (select version).
4206 define i32 @test32(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) {
4207 ; CHECK-LABEL: @test32(
4208 entry:
4209   br label %loop_begin
4210 ; CHECK-NEXT:  entry:
4211 ; CHECK-NEXT:    %[[INV_AND:.*]] = and i1 %cond2, %cond1
4212 ; CHECK-NEXT:    br i1 %[[INV_AND]], label %entry.split, label %entry.split.us
4213
4214 loop_begin:
4215   %v1 = load i1, i1* %ptr1
4216   %v2 = load i1, i1* %ptr2
4217   %cond_and1 = select i1 %v1, i1 %cond1, i1 false
4218   %cond_and2 = select i1 %cond_and1, i1 %cond2, i1 false
4219   br i1 %cond_and2, label %loop_a, label %loop_b
4220 ; The 'loop_b' unswitched loop.
4221 ;
4222 ; CHECK:       entry.split.us:
4223 ; CHECK-NEXT:    br label %loop_begin.us
4224 ;
4225 ; CHECK:       loop_begin.us:
4226 ; CHECK-NEXT:    %[[V2_US]] = load i1, i1* %ptr2, align 1
4227 ; CHECK-NEXT:    br label %loop_b.us
4228 ;
4229 ; CHECK:       loop_b.us:
4230 ; CHECK-NEXT:    call i32 @b()
4231 ; CHECK-NEXT:    br label %latch.us
4232 ;
4233 ; CHECK:       latch.us:
4234 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3, align 1
4235 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
4236 ;
4237 ; CHECK:       loop_exit.split.us:
4238 ; CHECK-NEXT:    br label %loop_exit
4239
4240 ; The original loop.
4241 ;
4242 ; CHECK:       entry.split:
4243 ; CHECK-NEXT:    br label %loop_begin
4244 ;
4245 ; CHECK:       loop_begin:
4246 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
4247 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
4248 ; CHECK-NEXT:    %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false
4249 ; CHECK-NEXT:    %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false
4250 ; CHECK-NEXT:    br i1 %[[V1]], label %loop_a, label %loop_b
4251
4252 loop_a:
4253   call i32 @a()
4254   br label %latch
4255 ; CHECK:       loop_a:
4256 ; CHECK-NEXT:    call i32 @a()
4257 ; CHECK-NEXT:    br label %latch
4258
4259 loop_b:
4260   call i32 @b()
4261   br label %latch
4262 ; CHECK:       loop_b:
4263 ; CHECK-NEXT:    call i32 @b()
4264 ; CHECK-NEXT:    br label %latch
4265
4266 latch:
4267   %v3 = load i1, i1* %ptr3
4268   br i1 %v3, label %loop_begin, label %loop_exit
4269 ; CHECK:       latch:
4270 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3, align 1
4271 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
4272
4273 loop_exit:
4274   ret i32 0
4275 ; CHECK:       loop_exit.split:
4276 ; CHECK-NEXT:    br label %loop_exit
4277 ;
4278 ; CHECK:       loop_exit:
4279 ; CHECK-NEXT:    ret
4280 }
4281
4282 ; Non-trivial partial loop unswitching of multiple invariant inputs to an `or`
4283 ; chain (select version).
4284 define i32 @test33(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) {
4285 ; CHECK-LABEL: @test33(
4286 entry:
4287   br label %loop_begin
4288 ; CHECK-NEXT:  entry:
4289 ; CHECK-NEXT:    %[[INV_OR:.*]] = or i1 %cond2, %cond1
4290 ; CHECK-NEXT:    br i1 %[[INV_OR]], label %entry.split.us, label %entry.split
4291
4292 loop_begin:
4293   %v1 = load i1, i1* %ptr1
4294   %v2 = load i1, i1* %ptr2
4295   %cond_and1 = select i1 %v1, i1 true, i1 %cond1
4296   %cond_and2 = select i1 %cond_and1, i1 true, i1 %cond2
4297   br i1 %cond_and2, label %loop_b, label %loop_a
4298 ; The 'loop_b' unswitched loop.
4299 ;
4300 ; CHECK:       entry.split.us:
4301 ; CHECK-NEXT:    br label %loop_begin.us
4302 ;
4303 ; CHECK:       loop_begin.us:
4304 ; CHECK-NEXT:    %[[V2_US]] = load i1, i1* %ptr2, align 1
4305 ; CHECK-NEXT:    br label %loop_b.us
4306 ;
4307 ; CHECK:       loop_b.us:
4308 ; CHECK-NEXT:    call i32 @b()
4309 ; CHECK-NEXT:    br label %latch.us
4310 ;
4311 ; CHECK:       latch.us:
4312 ; CHECK-NEXT:    %[[V3_US:.*]] = load i1, i1* %ptr3, align 1
4313 ; CHECK-NEXT:    br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us
4314 ;
4315 ; CHECK:       loop_exit.split.us:
4316 ; CHECK-NEXT:    br label %loop_exit
4317
4318 ; The original loop.
4319 ;
4320 ; CHECK:       entry.split:
4321 ; CHECK-NEXT:    br label %loop_begin
4322 ;
4323 ; CHECK:       loop_begin:
4324 ; CHECK-NEXT:    %[[V1:.*]] = load i1, i1* %ptr1
4325 ; CHECK-NEXT:    %[[V2:.*]] = load i1, i1* %ptr2
4326 ; CHECK-NEXT:    %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false
4327 ; CHECK-NEXT:    %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false
4328 ; CHECK-NEXT:    br i1 %[[V1]], label %loop_b, label %loop_a
4329
4330 loop_a:
4331   call i32 @a()
4332   br label %latch
4333 ; CHECK:       loop_a:
4334 ; CHECK-NEXT:    call i32 @a()
4335 ; CHECK-NEXT:    br label %latch
4336
4337 loop_b:
4338   call i32 @b()
4339   br label %latch
4340 ; CHECK:       loop_b:
4341 ; CHECK-NEXT:    call i32 @b()
4342 ; CHECK-NEXT:    br label %latch
4343
4344 latch:
4345   %v3 = load i1, i1* %ptr3
4346   br i1 %v3, label %loop_begin, label %loop_exit
4347 ; CHECK:       latch:
4348 ; CHECK-NEXT:    %[[V3:.*]] = load i1, i1* %ptr3, align 1
4349 ; CHECK-NEXT:    br i1 %[[V3]], label %loop_begin, label %loop_exit.split
4350
4351 loop_exit:
4352   ret i32 0
4353 ; CHECK:       loop_exit.split:
4354 ; CHECK-NEXT:    br label %loop_exit
4355 ;
4356 ; CHECK:       loop_exit:
4357 ; CHECK-NEXT:    ret
4358 }