test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll

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