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