test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; REQUIRES: asserts
   3 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
   4 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
   5 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
   6
   7 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
   8
   9 ; Make sure that we can eliminate a provably dead backedge.
  10 define i32 @dead_backedge_test_branch_loop(i32 %end) {
  11 ; CHECK-LABEL: @dead_backedge_test_branch_loop(
  12 ; CHECK-NEXT:  preheader:
  13 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  14 ; CHECK:       header:
  15 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ]
  16 ; CHECK-NEXT:    [[I_1:%.*]] = add i32 [[I]], 1
  17 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100
  18 ; CHECK-NEXT:    br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]]
  19 ; CHECK:       header.backedge:
  20 ; CHECK-NEXT:    [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ]
  21 ; CHECK-NEXT:    br label [[HEADER]]
  22 ; CHECK:       dead_backedge:
  23 ; CHECK-NEXT:    [[I_2]] = add i32 [[I_1]], 10
  24 ; CHECK-NEXT:    br i1 false, label [[HEADER_BACKEDGE]], label [[EXIT:%.*]]
  25 ; CHECK:       exit:
  26 ; CHECK-NEXT:    [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ]
  27 ; CHECK-NEXT:    ret i32 [[I_2_LCSSA]]
  28 ;
  29 preheader:
  30   br label %header
  31
  32 header:
  33   %i = phi i32 [0, %preheader], [%i.1, %header], [%i.2, %dead_backedge]
  34   %i.1 = add i32 %i, 1
  35   %cmp1 = icmp slt i32 %i.1, 100
  36   br i1 %cmp1, label %header, label %dead_backedge
  37
  38 dead_backedge:
  39   %i.2 = add i32 %i.1, 10
  40   br i1 false, label %header, label %exit
  41
  42 exit:
  43   ret i32 %i.2
  44 }
  45
  46 ; Make sure that we can eliminate a provably dead backedge with switch.
  47 define i32 @dead_backedge_test_switch_loop(i32 %end) {
  48 ; CHECK-LABEL: @dead_backedge_test_switch_loop(
  49 ; CHECK-NEXT:  preheader:
  50 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  51 ; CHECK:       header:
  52 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ]
  53 ; CHECK-NEXT:    [[I_1:%.*]] = add i32 [[I]], 1
  54 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100
  55 ; CHECK-NEXT:    br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]]
  56 ; CHECK:       header.backedge:
  57 ; CHECK-NEXT:    [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ]
  58 ; CHECK-NEXT:    br label [[HEADER]]
  59 ; CHECK:       dead_backedge:
  60 ; CHECK-NEXT:    [[I_2]] = add i32 [[I_1]], 10
  61 ; CHECK-NEXT:    switch i32 1, label [[EXIT:%.*]] [
  62 ; CHECK-NEXT:    i32 0, label [[HEADER_BACKEDGE]]
  63 ; CHECK-NEXT:    ]
  64 ; CHECK:       exit:
  65 ; CHECK-NEXT:    [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ]
  66 ; CHECK-NEXT:    ret i32 [[I_2_LCSSA]]
  67 ;
  68 preheader:
  69   br label %header
  70
  71 header:
  72   %i = phi i32 [0, %preheader], [%i.1, %header], [%i.2, %dead_backedge]
  73   %i.1 = add i32 %i, 1
  74   %cmp1 = icmp slt i32 %i.1, 100
  75   br i1 %cmp1, label %header, label %dead_backedge
  76
  77 dead_backedge:
  78   %i.2 = add i32 %i.1, 10
  79   switch i32 1, label %exit [i32 0, label %header]
  80
  81 exit:
  82   ret i32 %i.2
  83 }
  84
  85 ; Check that we can eliminate a triangle.
  86 define i32 @dead_block_test_branch_loop(i32 %end) {
  87 ; CHECK-LABEL: @dead_block_test_branch_loop(
  88 ; CHECK-NEXT:  preheader:
  89 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  90 ; CHECK:       header:
  91 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
  92 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
  93 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
  94 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
  95 ; CHECK:       exit:
  96 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
  97 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
  98 ;
  99 preheader:
 100   br label %header
 101
 102 header:
 103   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 104   br i1 true, label %backedge, label %dead
 105
 106 dead:
 107   %i.2 = add i32 %i, 1
 108   br label %backedge
 109
 110 backedge:
 111   %i.1 = phi i32 [%i, %header], [%i.2, %dead]
 112   %i.inc = add i32 %i.1, 1
 113   %cmp = icmp slt i32 %i.inc, %end
 114   br i1 %cmp, label %header, label %exit
 115
 116 exit:
 117   ret i32 %i.inc
 118 }
 119
 120 ; Check that we can eliminate dead branches of a switch.
 121 define i32 @dead_block_test_switch_loop(i32 %end) {
 122 ; CHECK-LABEL: @dead_block_test_switch_loop(
 123 ; CHECK-NEXT:  preheader:
 124 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 125 ; CHECK:       header:
 126 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 127 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 128 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 129 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 130 ; CHECK:       exit:
 131 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 132 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 133 ;
 134 preheader:
 135   br label %header
 136
 137 header:
 138   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 139   switch i32 1, label %dead [i32 0, label %dead
 140   i32 1, label %backedge
 141   i32 2, label %dead]
 142
 143 dead:
 144   %i.2 = add i32 %i, 1
 145   br label %backedge
 146
 147 backedge:
 148   %i.1 = phi i32 [%i, %header], [%i.2, %dead]
 149   %i.inc = add i32 %i.1, 1
 150   %cmp = icmp slt i32 %i.inc, %end
 151   br i1 %cmp, label %header, label %exit
 152 exit:
 153   ret i32 %i.inc
 154 }
 155
 156 ; Check that we can eliminate several dead blocks.
 157 define i32 @dead_block_propogate_test_branch_loop(i32 %end) {
 158 ; CHECK-LABEL: @dead_block_propogate_test_branch_loop(
 159 ; CHECK-NEXT:  preheader:
 160 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 161 ; CHECK:       header:
 162 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 163 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 164 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 165 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 166 ; CHECK:       exit:
 167 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 168 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 169 ;
 170 preheader:
 171   br label %header
 172
 173 header:
 174   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 175   br i1 true, label %backedge, label %dead
 176
 177 dead:
 178   %i.2 = add i32 %i, 1
 179   br label %dummy
 180
 181 dummy:
 182   br label %backedge
 183
 184 backedge:
 185   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 186   %i.inc = add i32 %i.1, 1
 187   %cmp = icmp slt i32 %i.inc, %end
 188   br i1 %cmp, label %header, label %exit
 189
 190 exit:
 191   ret i32 %i.inc
 192 }
 193
 194 ; Check that we can eliminate several blocks while removing a switch.
 195 define i32 @dead_block_propogate_test_switch_loop(i32 %end) {
 196 ; CHECK-LABEL: @dead_block_propogate_test_switch_loop(
 197 ; CHECK-NEXT:  preheader:
 198 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 199 ; CHECK:       header:
 200 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 201 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 202 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 203 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 204 ; CHECK:       exit:
 205 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 206 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 207 ;
 208 preheader:
 209   br label %header
 210
 211 header:
 212   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 213   switch i32 1, label %dead [i32 0, label %dead
 214   i32 1, label %backedge
 215   i32 2, label %dead]
 216
 217 dead:
 218   %i.2 = add i32 %i, 1
 219   br label %dummy
 220
 221 dummy:
 222   br label %backedge
 223
 224 backedge:
 225   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 226   %i.inc = add i32 %i.1, 1
 227   %cmp = icmp slt i32 %i.inc, %end
 228   br i1 %cmp, label %header, label %exit
 229
 230 exit:
 231   ret i32 %i.inc
 232 }
 233
 234 ; Check that we preserve static reachibility of a dead exit block while deleting
 235 ; a branch.
 236 define i32 @dead_exit_test_branch_loop(i32 %end) {
 237 ; CHECK-LABEL: @dead_exit_test_branch_loop(
 238 ; CHECK-NEXT:  preheader:
 239 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
 240 ; CHECK-NEXT:    i32 1, label [[DEAD:%.*]]
 241 ; CHECK-NEXT:    ]
 242 ; CHECK:       preheader.split:
 243 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 244 ; CHECK:       header:
 245 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 246 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 247 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 248 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]]
 249 ; CHECK:       dead:
 250 ; CHECK-NEXT:    br label [[DUMMY:%.*]]
 251 ; CHECK:       dummy:
 252 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 253 ; CHECK:       exit.loopexit:
 254 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 255 ; CHECK-NEXT:    br label [[EXIT]]
 256 ; CHECK:       exit:
 257 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
 258 ; CHECK-NEXT:    ret i32 [[I_1]]
 259 ;
 260 preheader:
 261   br label %header
 262
 263 header:
 264   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 265   br i1 true, label %backedge, label %dead
 266
 267 dead:
 268   br label %dummy
 269
 270 dummy:
 271   br label %exit
 272
 273 backedge:
 274   %i.inc = add i32 %i, 1
 275   %cmp = icmp slt i32 %i.inc, %end
 276   br i1 %cmp, label %header, label %exit
 277
 278 exit:
 279   %i.1 = phi i32 [%i.inc, %backedge], [%i, %dummy]
 280   ret i32 %i.1
 281 }
 282
 283 ; Check that we preserve static reachibility of a dead exit block while deleting
 284 ; a switch.
 285 define i32 @dead_exit_test_switch_loop(i32 %end) {
 286 ; CHECK-LABEL: @dead_exit_test_switch_loop(
 287 ; CHECK-NEXT:  preheader:
 288 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
 289 ; CHECK-NEXT:    i32 1, label [[DEAD:%.*]]
 290 ; CHECK-NEXT:    ]
 291 ; CHECK:       preheader.split:
 292 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 293 ; CHECK:       header:
 294 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 295 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 296 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 297 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]]
 298 ; CHECK:       dead:
 299 ; CHECK-NEXT:    br label [[DUMMY:%.*]]
 300 ; CHECK:       dummy:
 301 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 302 ; CHECK:       exit.loopexit:
 303 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 304 ; CHECK-NEXT:    br label [[EXIT]]
 305 ; CHECK:       exit:
 306 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
 307 ; CHECK-NEXT:    ret i32 [[I_1]]
 308 ;
 309 preheader:
 310   br label %header
 311
 312 header:
 313   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 314   switch i32 1, label %dead [i32 0, label %dead
 315   i32 1, label %backedge
 316   i32 2, label %dead]
 317
 318 dead:
 319   br label %dummy
 320
 321 dummy:
 322   br label %exit
 323
 324 backedge:
 325   %i.inc = add i32 %i, 1
 326   %cmp = icmp slt i32 %i.inc, %end
 327   br i1 %cmp, label %header, label %exit
 328
 329 exit:
 330   %i.1 = phi i32 [%i.inc, %backedge], [%i, %dummy]
 331   ret i32 %i.1
 332 }
 333
 334 ; Check that we can completely eliminate the current loop, branch case.
 335 define i32 @dead_loop_test_branch_loop(i32 %end) {
 336 ; CHECK-LABEL: @dead_loop_test_branch_loop(
 337 ; CHECK-NEXT:  preheader:
 338 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 339 ; CHECK:       header:
 340 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 341 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
 342 ; CHECK:       dead:
 343 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 344 ; CHECK-NEXT:    br label [[BACKEDGE]]
 345 ; CHECK:       backedge:
 346 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
 347 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 348 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 349 ; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[EXIT:%.*]]
 350 ; CHECK:       exit:
 351 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 352 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 353 ;
 354 preheader:
 355   br label %header
 356
 357 header:
 358   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 359   br i1 true, label %backedge, label %dead
 360
 361 dead:
 362   %i.2 = add i32 %i, 1
 363   br label %dummy
 364
 365 dummy:
 366   br label %backedge
 367
 368 backedge:
 369   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 370   %i.inc = add i32 %i.1, 1
 371   %cmp = icmp slt i32 %i.inc, %end
 372   br i1 false, label %header, label %exit
 373
 374 exit:
 375   ret i32 %i.inc
 376 }
 377
 378 ; Check that we can completely eliminate the current loop, switch case.
 379 define i32 @dead_loop_test_switch_loop(i32 %end) {
 380 ; CHECK-LABEL: @dead_loop_test_switch_loop(
 381 ; CHECK-NEXT:  preheader:
 382 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 383 ; CHECK:       header:
 384 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 385 ; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
 386 ; CHECK-NEXT:    i32 0, label [[DEAD]]
 387 ; CHECK-NEXT:    i32 1, label [[BACKEDGE]]
 388 ; CHECK-NEXT:    i32 2, label [[DEAD]]
 389 ; CHECK-NEXT:    ]
 390 ; CHECK:       dead:
 391 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 392 ; CHECK-NEXT:    br label [[BACKEDGE]]
 393 ; CHECK:       backedge:
 394 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
 395 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 396 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 397 ; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[EXIT:%.*]]
 398 ; CHECK:       exit:
 399 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 400 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 401 ;
 402 preheader:
 403   br label %header
 404 header:
 405   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 406   switch i32 1, label %dead [i32 0, label %dead
 407   i32 1, label %backedge
 408   i32 2, label %dead]
 409 dead:
 410   %i.2 = add i32 %i, 1
 411   br label %dummy
 412
 413 dummy:
 414   br label %backedge
 415
 416 backedge:
 417   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 418   %i.inc = add i32 %i.1, 1
 419   %cmp = icmp slt i32 %i.inc, %end
 420   br i1 false, label %header, label %exit
 421
 422 exit:
 423   ret i32 %i.inc
 424 }
 425
 426 ; Check that we can delete a dead inner loop entirely.
 427 define i32 @dead_sub_loop_test_branch_loop(i32 %end) {
 428 ; CHECK-LABEL: @dead_sub_loop_test_branch_loop(
 429 ; CHECK-NEXT:  preheader:
 430 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 431 ; CHECK:       header:
 432 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ]
 433 ; CHECK-NEXT:    br label [[LIVE_LOOP:%.*]]
 434 ; CHECK:       live_loop:
 435 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
 436 ; CHECK-NEXT:    [[A_INC]] = add i32 [[A]], 1
 437 ; CHECK-NEXT:    [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]]
 438 ; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]]
 439 ; CHECK:       exit.a:
 440 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 441 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END]]
 442 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 443 ; CHECK:       exit:
 444 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ]
 445 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 446 ;
 447 preheader:
 448   br label %header
 449
 450 header:
 451   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 452   br i1 true, label %live_preheader, label %dead_preheader
 453
 454 live_preheader:
 455   br label %live_loop
 456
 457 live_loop:
 458   %a = phi i32 [0, %live_preheader], [%a.inc, %live_loop]
 459   %a.inc = add i32 %a, 1
 460   %cmp.a = icmp slt i32 %a.inc, %end
 461   br i1 %cmp.a, label %live_loop, label %exit.a
 462
 463 exit.a:
 464   br label %backedge
 465
 466 dead_preheader:
 467   br label %dead_loop
 468
 469 dead_loop:
 470   %b = phi i32 [0, %dead_preheader], [%b.inc, %dead_loop]
 471   %b.inc = add i32 %b, 1
 472   %cmp.b = icmp slt i32 %b.inc, %end
 473   br i1 %cmp.b, label %dead_loop, label %exit.b
 474
 475 exit.b:
 476   br label %backedge
 477
 478 backedge:
 479   %i.inc = add i32 %i, 1
 480   %cmp = icmp slt i32 %i.inc, %end
 481   br i1 %cmp, label %header, label %exit
 482
 483 exit:
 484   ret i32 %i.inc
 485 }
 486
 487 define i32 @dead_sub_loop_test_switch_loop(i32 %end) {
 488 ; CHECK-LABEL: @dead_sub_loop_test_switch_loop(
 489 ; CHECK-NEXT:  preheader:
 490 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 491 ; CHECK:       header:
 492 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ]
 493 ; CHECK-NEXT:    br label [[LIVE_LOOP:%.*]]
 494 ; CHECK:       live_loop:
 495 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
 496 ; CHECK-NEXT:    [[A_INC]] = add i32 [[A]], 1
 497 ; CHECK-NEXT:    [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]]
 498 ; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]]
 499 ; CHECK:       exit.a:
 500 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 501 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END]]
 502 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 503 ; CHECK:       exit:
 504 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ]
 505 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 506 ;
 507 preheader:
 508   br label %header
 509
 510 header:
 511   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 512   switch i32 1, label %dead_preheader [i32 0, label %dead_preheader
 513   i32 1, label %live_preheader
 514   i32 2, label %dead_preheader]
 515
 516 live_preheader:
 517   br label %live_loop
 518
 519 live_loop:
 520   %a = phi i32 [0, %live_preheader], [%a.inc, %live_loop]
 521   %a.inc = add i32 %a, 1
 522   %cmp.a = icmp slt i32 %a.inc, %end
 523   br i1 %cmp.a, label %live_loop, label %exit.a
 524
 525 exit.a:
 526   br label %backedge
 527
 528 dead_preheader:
 529   br label %dead_loop
 530
 531 dead_loop:
 532   %b = phi i32 [0, %dead_preheader], [%b.inc, %dead_loop]
 533   %b.inc = add i32 %b, 1
 534   %cmp.b = icmp slt i32 %b.inc, %end
 535   br i1 %cmp.b, label %dead_loop, label %exit.b
 536
 537 exit.b:
 538   br label %backedge
 539
 540 backedge:
 541   %i.inc = add i32 %i, 1
 542   %cmp = icmp slt i32 %i.inc, %end
 543   br i1 %cmp, label %header, label %exit
 544
 545 exit:
 546   ret i32 %i.inc
 547 }
 548
 549 ; Check that we preserve static reachability of an exit block even if we prove
 550 ; that the loop is infinite. Branch case.
 551 define i32 @inf_loop_test_branch_loop(i32 %end) {
 552 ; CHECK-LABEL: @inf_loop_test_branch_loop(
 553 ; CHECK-NEXT:  preheader:
 554 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
 555 ; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
 556 ; CHECK-NEXT:    ]
 557 ; CHECK:       preheader.split:
 558 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 559 ; CHECK:       header:
 560 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 561 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 562 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 563 ; CHECK-NEXT:    br label [[HEADER]]
 564 ; CHECK:       exit:
 565 ; CHECK-NEXT:    ret i32 undef
 566 ;
 567 preheader:
 568   br label %header
 569
 570 header:
 571   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 572   br i1 true, label %backedge, label %dead
 573
 574 dead:
 575   %i.2 = add i32 %i, 1
 576   br label %dummy
 577
 578 dummy:
 579   br label %backedge
 580
 581 backedge:
 582   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 583   %i.inc = add i32 %i.1, 1
 584   %cmp = icmp slt i32 %i.inc, %end
 585   br i1 true, label %header, label %exit
 586
 587 exit:
 588   ret i32 %i.inc
 589 }
 590
 591 define i32 @inf_loop_test_switch_loop(i32 %end) {
 592 ; CHECK-LABEL: @inf_loop_test_switch_loop(
 593 ; CHECK-NEXT:  preheader:
 594 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
 595 ; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
 596 ; CHECK-NEXT:    ]
 597 ; CHECK:       preheader.split:
 598 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 599 ; CHECK:       header:
 600 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 601 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 602 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 603 ; CHECK-NEXT:    br label [[HEADER]]
 604 ; CHECK:       exit:
 605 ; CHECK-NEXT:    ret i32 undef
 606 ;
 607 preheader:
 608   br label %header
 609 header:
 610   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 611   switch i32 1, label %dead [i32 0, label %dead
 612   i32 1, label %backedge
 613   i32 2, label %dead]
 614 dead:
 615   %i.2 = add i32 %i, 1
 616   br label %dummy
 617 dummy:
 618   br label %backedge
 619 backedge:
 620   %i.1 = phi i32 [%i, %header], [%i.2, %dummy]
 621   %i.inc = add i32 %i.1, 1
 622   %cmp = icmp slt i32 %i.inc, %end
 623   br i1 true, label %header, label %exit
 624 exit:
 625   ret i32 %i.inc
 626 }
 627
 628 ; Check that when the block is not actually dead, we don't remove it.
 629 define i32 @live_block_test_branch_loop(i1 %c, i32 %end) {
 630 ; CHECK-LABEL: @live_block_test_branch_loop(
 631 ; CHECK-NEXT:  preheader:
 632 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 633 ; CHECK:       header:
 634 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 635 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 636 ; CHECK:       check:
 637 ; CHECK-NEXT:    br label [[BACKEDGE]]
 638 ; CHECK:       live:
 639 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 640 ; CHECK-NEXT:    br label [[BACKEDGE]]
 641 ; CHECK:       backedge:
 642 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[CHECK]] ], [ [[I_2]], [[LIVE]] ]
 643 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 644 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 645 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 646 ; CHECK:       exit:
 647 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 648 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 649 ;
 650 preheader:
 651   br label %header
 652
 653 header:
 654   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 655   br i1 %c, label %check, label %live
 656
 657 check:
 658   br i1 true, label %backedge, label %live
 659
 660 live:
 661   %i.2 = add i32 %i, 1
 662   br label %backedge
 663
 664 backedge:
 665   %i.1 = phi i32 [%i, %check], [%i.2, %live]
 666   %i.inc = add i32 %i.1, 1
 667   %cmp = icmp slt i32 %i.inc, %end
 668   br i1 %cmp, label %header, label %exit
 669
 670 exit:
 671   ret i32 %i.inc
 672 }
 673
 674 ; Check that when the block is not actually dead, we don't remove it. Version
 675 ; with Phi node.
 676 define i32 @live_block_test_branch_loop_phis(i1 %c, i32 %end) {
 677 ; CHECK-LABEL: @live_block_test_branch_loop_phis(
 678 ; CHECK-NEXT:  preheader:
 679 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 680 ; CHECK:       header:
 681 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 682 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 683 ; CHECK:       check:
 684 ; CHECK-NEXT:    br label [[BACKEDGE]]
 685 ; CHECK:       live:
 686 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 687 ; CHECK-NEXT:    br label [[BACKEDGE]]
 688 ; CHECK:       backedge:
 689 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[CHECK]] ], [ [[I_2]], [[LIVE]] ]
 690 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 691 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 692 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 693 ; CHECK:       exit:
 694 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 695 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 696 ;
 697 preheader:
 698   br label %header
 699
 700 header:
 701   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 702   br i1 %c, label %check, label %live
 703
 704 check:
 705   br i1 true, label %backedge, label %live
 706
 707 live:
 708   %phi = phi i32 [ 1, %header ], [ -1, %check ]
 709   %i.2 = add i32 %i, %phi
 710   br label %backedge
 711
 712 backedge:
 713   %i.1 = phi i32 [%i, %check], [%i.2, %live]
 714   %i.inc = add i32 %i.1, 1
 715   %cmp = icmp slt i32 %i.inc, %end
 716   br i1 %cmp, label %header, label %exit
 717
 718 exit:
 719   ret i32 %i.inc
 720 }
 721
 722 define i32 @live_block_test_switch_loop(i1 %c, i32 %end) {
 723 ; CHECK-LABEL: @live_block_test_switch_loop(
 724 ; CHECK-NEXT:  preheader:
 725 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 726 ; CHECK:       header:
 727 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 728 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 729 ; CHECK:       check:
 730 ; CHECK-NEXT:    br label [[BACKEDGE]]
 731 ; CHECK:       live:
 732 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 733 ; CHECK-NEXT:    br label [[BACKEDGE]]
 734 ; CHECK:       backedge:
 735 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[CHECK]] ], [ [[I_2]], [[LIVE]] ]
 736 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 737 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 738 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 739 ; CHECK:       exit:
 740 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 741 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 742 ;
 743 preheader:
 744   br label %header
 745
 746 header:
 747   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 748   br i1 %c, label %check, label %live
 749
 750 check:
 751   switch i32 1, label %live [i32 0, label %live
 752   i32 1, label %backedge
 753   i32 2, label %live]
 754
 755 live:
 756   %i.2 = add i32 %i, 1
 757   br label %backedge
 758
 759 backedge:
 760   %i.1 = phi i32 [%i, %check], [%i.2, %live]
 761   %i.inc = add i32 %i.1, 1
 762   %cmp = icmp slt i32 %i.inc, %end
 763   br i1 %cmp, label %header, label %exit
 764
 765 exit:
 766   ret i32 %i.inc
 767 }
 768
 769 define i32 @live_block_test_switch_loop_phis(i1 %c, i32 %end) {
 770 ; CHECK-LABEL: @live_block_test_switch_loop_phis(
 771 ; CHECK-NEXT:  preheader:
 772 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 773 ; CHECK:       header:
 774 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 775 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 776 ; CHECK:       check:
 777 ; CHECK-NEXT:    br label [[BACKEDGE]]
 778 ; CHECK:       live:
 779 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 780 ; CHECK-NEXT:    br label [[BACKEDGE]]
 781 ; CHECK:       backedge:
 782 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[CHECK]] ], [ [[I_2]], [[LIVE]] ]
 783 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 784 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 785 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 786 ; CHECK:       exit:
 787 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 788 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 789 ;
 790 preheader:
 791   br label %header
 792
 793 header:
 794   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 795   br i1 %c, label %check, label %live
 796
 797 check:
 798   switch i32 1, label %live [i32 0, label %live
 799   i32 1, label %backedge
 800   i32 2, label %live]
 801
 802 live:
 803   %phi = phi i32 [ 1, %header ], [ -1, %check ], [ -1, %check ], [ -1, %check ]
 804   %i.2 = add i32 %i, %phi
 805   br label %backedge
 806
 807 backedge:
 808   %i.1 = phi i32 [%i, %check], [%i.2, %live]
 809   %i.inc = add i32 %i.1, 1
 810   %cmp = icmp slt i32 %i.inc, %end
 811   br i1 %cmp, label %header, label %exit
 812
 813 exit:
 814   ret i32 %i.inc
 815 }
 816
 817 ; Check that we can remove part of blocks of inner loop while the loop still
 818 ; preserves, in presence of outer loop.
 819 define i32 @partial_sub_loop_test_branch_loop(i32 %end) {
 820 ; CHECK-LABEL: @partial_sub_loop_test_branch_loop(
 821 ; CHECK-NEXT:  entry:
 822 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 823 ; CHECK:       outer_header:
 824 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 825 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 826 ; CHECK:       header:
 827 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 828 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 829 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 830 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[OUTER_BACKEDGE]]
 831 ; CHECK:       outer_backedge:
 832 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 833 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
 834 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END]]
 835 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
 836 ; CHECK:       exit:
 837 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
 838 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 839 ;
 840 entry:
 841   br label %outer_header
 842
 843 outer_header:
 844   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
 845   br label %preheader
 846
 847 preheader:
 848   br label %header
 849
 850 header:
 851   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 852   br i1 true, label %backedge, label %dead
 853
 854 dead:
 855   %i.2 = add i32 %i, 1
 856   br label %backedge
 857
 858 backedge:
 859   %i.1 = phi i32 [%i, %header], [%i.2, %dead]
 860   %i.inc = add i32 %i.1, 1
 861   %cmp = icmp slt i32 %i.inc, %end
 862   br i1 %cmp, label %header, label %outer_backedge
 863
 864 outer_backedge:
 865   %j.inc = add i32 %j, 1
 866   %cmp.j = icmp slt i32 %j.inc, %end
 867   br i1 %cmp.j, label %outer_header, label %exit
 868
 869 exit:
 870   ret i32 %i.inc
 871 }
 872
 873 define i32 @partial_sub_loop_test_switch_loop(i32 %end) {
 874 ; CHECK-LABEL: @partial_sub_loop_test_switch_loop(
 875 ; CHECK-NEXT:  entry:
 876 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 877 ; CHECK:       outer_header:
 878 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 879 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 880 ; CHECK:       header:
 881 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 882 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 883 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 884 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[OUTER_BACKEDGE]]
 885 ; CHECK:       outer_backedge:
 886 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 887 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
 888 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END]]
 889 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
 890 ; CHECK:       exit:
 891 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
 892 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 893 ;
 894 entry:
 895   br label %outer_header
 896
 897 outer_header:
 898   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
 899   br label %preheader
 900
 901 preheader:
 902   br label %header
 903
 904 header:
 905   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 906   switch i32 1, label %dead [i32 0, label %dead
 907   i32 1, label %backedge
 908   i32 2, label %dead]
 909
 910 dead:
 911   %i.2 = add i32 %i, 1
 912   br label %backedge
 913
 914 backedge:
 915   %i.1 = phi i32 [%i, %header], [%i.2, %dead]
 916   %i.inc = add i32 %i.1, 1
 917   %cmp = icmp slt i32 %i.inc, %end
 918   br i1 %cmp, label %header, label %outer_backedge
 919
 920 outer_backedge:
 921   %j.inc = add i32 %j, 1
 922   %cmp.j = icmp slt i32 %j.inc, %end
 923   br i1 %cmp.j, label %outer_header, label %exit
 924
 925 exit:
 926   ret i32 %i.inc
 927 }
 928
 929 ; Check that we can completely delete inner loop and preserve the outer loop.
 930 define i32 @full_sub_loop_test_branch_loop(i32 %end) {
 931 ; CHECK-LABEL: @full_sub_loop_test_branch_loop(
 932 ; CHECK-NEXT:  entry:
 933 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 934 ; CHECK:       outer_header:
 935 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 936 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 937 ; CHECK:       header:
 938 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 939 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
 940 ; CHECK-NEXT:    br i1 false, label [[BACKEDGE]], label [[DEAD:%.*]]
 941 ; CHECK:       dead:
 942 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 943 ; CHECK-NEXT:    br label [[BACKEDGE]]
 944 ; CHECK:       backedge:
 945 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
 946 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
 947 ; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
 948 ; CHECK:       outer_backedge:
 949 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 950 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
 951 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
 952 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
 953 ; CHECK:       exit:
 954 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
 955 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 956 ;
 957 entry:
 958   br label %outer_header
 959
 960 outer_header:
 961   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
 962   br label %preheader
 963
 964 preheader:
 965   br label %header
 966
 967 header:
 968   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
 969   br label  %live_part
 970
 971 live_part:
 972   %mul = mul i32 %i, %i
 973   br i1 false, label %backedge, label %dead
 974
 975 dead:
 976   %i.2 = add i32 %i, 1
 977   br label %backedge
 978
 979 backedge:
 980   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
 981   %i.inc = add i32 %i.1, 1
 982   br i1 false, label %header, label %outer_backedge
 983
 984 outer_backedge:
 985   %j.inc = add i32 %j, 1
 986   %cmp.j = icmp slt i32 %j.inc, %end
 987   br i1 %cmp.j, label %outer_header, label %exit
 988
 989 exit:
 990   ret i32 %i.inc
 991 }
 992
 993 define i32 @full_sub_loop_test_switch_loop(i32 %end) {
 994 ; CHECK-LABEL: @full_sub_loop_test_switch_loop(
 995 ; CHECK-NEXT:  entry:
 996 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 997 ; CHECK:       outer_header:
 998 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 999 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1000 ; CHECK:       header:
1001 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
1002 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1003 ; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
1004 ; CHECK-NEXT:    i32 0, label [[BACKEDGE]]
1005 ; CHECK-NEXT:    ]
1006 ; CHECK:       dead:
1007 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
1008 ; CHECK-NEXT:    br label [[BACKEDGE]]
1009 ; CHECK:       backedge:
1010 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
1011 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
1012 ; CHECK-NEXT:    switch i32 1, label [[OUTER_BACKEDGE]] [
1013 ; CHECK-NEXT:    i32 0, label [[HEADER]]
1014 ; CHECK-NEXT:    ]
1015 ; CHECK:       outer_backedge:
1016 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
1017 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1018 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1019 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1020 ; CHECK:       exit:
1021 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
1022 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1023 ;
1024 entry:
1025   br label %outer_header
1026
1027 outer_header:
1028   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1029   br label %preheader
1030
1031 preheader:
1032   br label %header
1033
1034 header:
1035   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1036   br label  %live_part
1037
1038 live_part:
1039   %mul = mul i32 %i, %i
1040   switch i32 1, label %dead [i32 0, label %backedge]
1041
1042 dead:
1043   %i.2 = add i32 %i, 1
1044   br label %backedge
1045
1046 backedge:
1047   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1048   %i.inc = add i32 %i.1, 1
1049   switch i32 1, label %outer_backedge [i32 0, label %header]
1050
1051 outer_backedge:
1052   %j.inc = add i32 %j, 1
1053   %cmp.j = icmp slt i32 %j.inc, %end
1054   br i1 %cmp.j, label %outer_header, label %exit
1055
1056 exit:
1057   ret i32 %i.inc
1058 }
1059
1060 ; Inverted condition in live_part.
1061 define i32 @full_sub_loop_test_branch_loop_inverse_1(i32 %end) {
1062 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_1(
1063 ; CHECK-NEXT:  entry:
1064 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1065 ; CHECK:       outer_header:
1066 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1067 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1068 ; CHECK:       header:
1069 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
1070 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1071 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
1072 ; CHECK:       dead:
1073 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
1074 ; CHECK-NEXT:    br label [[BACKEDGE]]
1075 ; CHECK:       backedge:
1076 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
1077 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
1078 ; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
1079 ; CHECK:       outer_backedge:
1080 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
1081 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1082 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1083 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1084 ; CHECK:       exit:
1085 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
1086 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1087 ;
1088 entry:
1089   br label %outer_header
1090
1091 outer_header:
1092   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1093   br label %preheader
1094
1095 preheader:
1096   br label %header
1097
1098 header:
1099   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1100   br label  %live_part
1101
1102 live_part:
1103   %mul = mul i32 %i, %i
1104   br i1 true, label %backedge, label %dead
1105
1106 dead:
1107   %i.2 = add i32 %i, 1
1108   br label %backedge
1109
1110 backedge:
1111   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1112   %i.inc = add i32 %i.1, 1
1113   br i1 false, label %header, label %outer_backedge
1114
1115 outer_backedge:
1116   %j.inc = add i32 %j, 1
1117   %cmp.j = icmp slt i32 %j.inc, %end
1118   br i1 %cmp.j, label %outer_header, label %exit
1119
1120 exit:
1121   ret i32 %i.inc
1122 }
1123
1124 define i32 @full_sub_loop_test_switch_loop_inverse_1(i32 %end) {
1125 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_1(
1126 ; CHECK-NEXT:  entry:
1127 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1128 ; CHECK:       outer_header:
1129 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1130 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1131 ; CHECK:       header:
1132 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
1133 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1134 ; CHECK-NEXT:    switch i32 1, label [[BACKEDGE]] [
1135 ; CHECK-NEXT:    i32 0, label [[DEAD:%.*]]
1136 ; CHECK-NEXT:    ]
1137 ; CHECK:       dead:
1138 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
1139 ; CHECK-NEXT:    br label [[BACKEDGE]]
1140 ; CHECK:       backedge:
1141 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
1142 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
1143 ; CHECK-NEXT:    switch i32 1, label [[OUTER_BACKEDGE]] [
1144 ; CHECK-NEXT:    i32 0, label [[HEADER]]
1145 ; CHECK-NEXT:    ]
1146 ; CHECK:       outer_backedge:
1147 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
1148 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1149 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1150 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1151 ; CHECK:       exit:
1152 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
1153 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1154 ;
1155 entry:
1156   br label %outer_header
1157
1158 outer_header:
1159   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1160   br label %preheader
1161
1162 preheader:
1163   br label %header
1164
1165 header:
1166   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1167   br label  %live_part
1168
1169 live_part:
1170   %mul = mul i32 %i, %i
1171   switch i32 1, label %backedge [i32 0, label %dead]
1172
1173 dead:
1174   %i.2 = add i32 %i, 1
1175   br label %backedge
1176
1177 backedge:
1178   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1179   %i.inc = add i32 %i.1, 1
1180   switch i32 1, label %outer_backedge [i32 0, label %header]
1181
1182 outer_backedge:
1183   %j.inc = add i32 %j, 1
1184   %cmp.j = icmp slt i32 %j.inc, %end
1185   br i1 %cmp.j, label %outer_header, label %exit
1186
1187 exit:
1188   ret i32 %i.inc
1189 }
1190
1191 define i32 @full_sub_loop_test_branch_loop_inverse_2(i32 %end) {
1192 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_2(
1193 ; CHECK-NEXT:  entry:
1194 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1195 ; CHECK:       outer_header:
1196 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1197 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
1198 ; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
1199 ; CHECK-NEXT:    ]
1200 ; CHECK:       preheader.split:
1201 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1202 ; CHECK:       header:
1203 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
1204 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1205 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
1206 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
1207 ; CHECK-NEXT:    br label [[HEADER]]
1208 ; CHECK:       outer_backedge:
1209 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1210 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1211 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1212 ; CHECK:       exit:
1213 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
1214 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1215 ;
1216 entry:
1217   br label %outer_header
1218
1219 outer_header:
1220   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1221   br label %preheader
1222
1223 preheader:
1224   br label %header
1225
1226 header:
1227   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1228   br label  %live_part
1229
1230 live_part:
1231   %mul = mul i32 %i, %i
1232   br i1 false, label %backedge, label %dead
1233
1234 dead:
1235   %i.2 = add i32 %i, 1
1236   br label %backedge
1237
1238 backedge:
1239   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1240   %i.inc = add i32 %i.1, 1
1241   br i1 true, label %header, label %outer_backedge
1242
1243 outer_backedge:
1244   %j.inc = add i32 %j, 1
1245   %cmp.j = icmp slt i32 %j.inc, %end
1246   br i1 %cmp.j, label %outer_header, label %exit
1247
1248 exit:
1249   ret i32 %i.inc
1250 }
1251
1252 define i32 @full_sub_loop_test_switch_loop_inverse_2(i32 %end) {
1253 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_2(
1254 ; CHECK-NEXT:  entry:
1255 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1256 ; CHECK:       outer_header:
1257 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1258 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
1259 ; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
1260 ; CHECK-NEXT:    ]
1261 ; CHECK:       preheader.split:
1262 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1263 ; CHECK:       header:
1264 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
1265 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1266 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
1267 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
1268 ; CHECK-NEXT:    br label [[HEADER]]
1269 ; CHECK:       outer_backedge:
1270 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1271 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1272 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1273 ; CHECK:       exit:
1274 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
1275 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1276 ;
1277 entry:
1278   br label %outer_header
1279
1280 outer_header:
1281   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1282   br label %preheader
1283
1284 preheader:
1285   br label %header
1286
1287 header:
1288   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1289   br label  %live_part
1290
1291 live_part:
1292   %mul = mul i32 %i, %i
1293   switch i32 1, label %dead [i32 0, label %backedge]
1294
1295 dead:
1296   %i.2 = add i32 %i, 1
1297   br label %backedge
1298
1299 backedge:
1300   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1301   %i.inc = add i32 %i.1, 1
1302   switch i32 1, label %header [i32 0, label %outer_backedge]
1303
1304 outer_backedge:
1305   %j.inc = add i32 %j, 1
1306   %cmp.j = icmp slt i32 %j.inc, %end
1307   br i1 %cmp.j, label %outer_header, label %exit
1308
1309 exit:
1310   ret i32 %i.inc
1311 }
1312
1313
1314 define i32 @full_sub_loop_test_branch_loop_inverse_3(i32 %end) {
1315 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_3(
1316 ; CHECK-NEXT:  entry:
1317 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1318 ; CHECK:       outer_header:
1319 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1320 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
1321 ; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
1322 ; CHECK-NEXT:    ]
1323 ; CHECK:       preheader.split:
1324 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1325 ; CHECK:       header:
1326 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
1327 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1328 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
1329 ; CHECK-NEXT:    br label [[HEADER]]
1330 ; CHECK:       outer_backedge:
1331 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1332 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1333 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1334 ; CHECK:       exit:
1335 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
1336 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1337 ;
1338 entry:
1339   br label %outer_header
1340
1341 outer_header:
1342   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1343   br label %preheader
1344
1345 preheader:
1346   br label %header
1347
1348 header:
1349   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1350   br label  %live_part
1351
1352 live_part:
1353   %mul = mul i32 %i, %i
1354   br i1 true, label %backedge, label %dead
1355
1356 dead:
1357   %i.2 = add i32 %i, 1
1358   br label %backedge
1359
1360 backedge:
1361   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1362   %i.inc = add i32 %i.1, 1
1363   br i1 true, label %header, label %outer_backedge
1364
1365 outer_backedge:
1366   %j.inc = add i32 %j, 1
1367   %cmp.j = icmp slt i32 %j.inc, %end
1368   br i1 %cmp.j, label %outer_header, label %exit
1369
1370 exit:
1371   ret i32 %i.inc
1372 }
1373
1374 define i32 @full_sub_loop_test_switch_loop_inverse_3(i32 %end) {
1375 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_3(
1376 ; CHECK-NEXT:  entry:
1377 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
1378 ; CHECK:       outer_header:
1379 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
1380 ; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
1381 ; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
1382 ; CHECK-NEXT:    ]
1383 ; CHECK:       preheader.split:
1384 ; CHECK-NEXT:    br label [[HEADER:%.*]]
1385 ; CHECK:       header:
1386 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
1387 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
1388 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
1389 ; CHECK-NEXT:    br label [[HEADER]]
1390 ; CHECK:       outer_backedge:
1391 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
1392 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
1393 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
1394 ; CHECK:       exit:
1395 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
1396 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
1397 ;
1398 entry:
1399   br label %outer_header
1400
1401 outer_header:
1402   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
1403   br label %preheader
1404
1405 preheader:
1406   br label %header
1407
1408 header:
1409   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
1410   br label  %live_part
1411
1412 live_part:
1413   %mul = mul i32 %i, %i
1414   switch i32 1, label %backedge [i32 0, label %dead]
1415
1416 dead:
1417   %i.2 = add i32 %i, 1
1418   br label %backedge
1419
1420 backedge:
1421   %i.1 = phi i32 [%i, %live_part], [%i.2, %dead]
1422   %i.inc = add i32 %i.1, 1
1423   switch i32 1, label %header [i32 0, label %outer_backedge]
1424
1425 outer_backedge:
1426   %j.inc = add i32 %j, 1
1427   %cmp.j = icmp slt i32 %j.inc, %end
1428   br i1 %cmp.j, label %outer_header, label %exit
1429
1430 exit:
1431   ret i32 %i.inc
1432 }
1433
1434 define i32 @exit_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
1435 ; CHECK-LABEL: @exit_branch_from_inner_to_grandparent(
1436 ; CHECK-NEXT:  preheader:
1437 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1438 ; CHECK:       loop_1:
1439 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1440 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1441 ; CHECK:       loop_2:
1442 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1443 ; CHECK-NEXT:    switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
1444 ; CHECK-NEXT:    i32 1, label [[LOOP_2_BACKEDGE]]
1445 ; CHECK-NEXT:    ]
1446 ; CHECK:       loop_2.split:
1447 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1448 ; CHECK:       loop_3:
1449 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1450 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
1451 ; CHECK:       loop_3_backedge:
1452 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1453 ; CHECK-NEXT:    br label [[LOOP_3]]
1454 ; CHECK:       loop_2_backedge:
1455 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1456 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1457 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1458 ; CHECK:       loop_1_backedge.loopexit:
1459 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1460 ; CHECK:       loop_1_backedge.loopexit1:
1461 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1462 ; CHECK:       loop_1_backedge:
1463 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1464 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1465 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1466 ; CHECK:       exit:
1467 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1468 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1469 ;
1470 preheader:
1471   br label %loop_1
1472
1473 loop_1:
1474   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1475   br label %loop_2
1476
1477 loop_2:
1478   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1479   br label %loop_3
1480
1481 loop_3:
1482   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1483   br i1 %cond1, label %loop_3_backedge, label %loop_1_backedge
1484
1485 loop_3_backedge:
1486   %k.next = add i32 %k, 1
1487   br i1 true, label %loop_3, label %loop_2_backedge
1488
1489 loop_2_backedge:
1490   %j.next = add i32 %j, 1
1491   %c_2 = icmp slt i32 %j.next, %N
1492   br i1 %c_2, label %loop_2, label %loop_1_backedge
1493
1494 loop_1_backedge:
1495   %i.next = add i32 %i, 1
1496   %c_1 = icmp slt i32 %i.next, %N
1497   br i1 %c_1, label %loop_1, label %exit
1498
1499 exit:
1500   ret i32 %i
1501 }
1502
1503 define i32 @exit_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
1504 ; CHECK-LABEL: @exit_switch_from_inner_to_grandparent(
1505 ; CHECK-NEXT:  preheader:
1506 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1507 ; CHECK:       loop_1:
1508 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1509 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1510 ; CHECK:       loop_2:
1511 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1512 ; CHECK-NEXT:    switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
1513 ; CHECK-NEXT:    i32 1, label [[LOOP_2_BACKEDGE]]
1514 ; CHECK-NEXT:    ]
1515 ; CHECK:       loop_2.split:
1516 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1517 ; CHECK:       loop_3:
1518 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1519 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
1520 ; CHECK:       loop_3_backedge:
1521 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1522 ; CHECK-NEXT:    br label [[LOOP_3]]
1523 ; CHECK:       loop_2_backedge:
1524 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1525 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1526 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1527 ; CHECK:       loop_1_backedge.loopexit:
1528 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1529 ; CHECK:       loop_1_backedge.loopexit1:
1530 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1531 ; CHECK:       loop_1_backedge:
1532 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1533 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1534 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1535 ; CHECK:       exit:
1536 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1537 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1538 ;
1539 preheader:
1540   br label %loop_1
1541
1542 loop_1:
1543   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1544   br label %loop_2
1545
1546 loop_2:
1547   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1548   br label %loop_3
1549
1550 loop_3:
1551   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1552   br i1 %cond1, label %loop_3_backedge, label %loop_1_backedge
1553
1554 loop_3_backedge:
1555   %k.next = add i32 %k, 1
1556   switch i32 1, label %loop_3 [i32 0, label %loop_2_backedge]
1557
1558 loop_2_backedge:
1559   %j.next = add i32 %j, 1
1560   %c_2 = icmp slt i32 %j.next, %N
1561   br i1 %c_2, label %loop_2, label %loop_1_backedge
1562
1563 loop_1_backedge:
1564   %i.next = add i32 %i, 1
1565   %c_1 = icmp slt i32 %i.next, %N
1566   br i1 %c_1, label %loop_1, label %exit
1567
1568 exit:
1569   ret i32 %i
1570 }
1571
1572 define i32 @intermediate_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
1573 ; CHECK-LABEL: @intermediate_branch_from_inner_to_grandparent(
1574 ; CHECK-NEXT:  preheader:
1575 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1576 ; CHECK:       loop_1:
1577 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1578 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1579 ; CHECK:       loop_2:
1580 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1581 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1582 ; CHECK:       loop_3:
1583 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1584 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1585 ; CHECK:       intermediate:
1586 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
1587 ; CHECK:       loop_3_backedge:
1588 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1589 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1590 ; CHECK:       loop_2_backedge:
1591 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1592 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1593 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1594 ; CHECK:       loop_1_backedge.loopexit:
1595 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1596 ; CHECK:       loop_1_backedge.loopexit1:
1597 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1598 ; CHECK:       loop_1_backedge:
1599 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1600 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1601 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1602 ; CHECK:       exit:
1603 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1604 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1605 ;
1606 preheader:
1607   br label %loop_1
1608
1609 loop_1:
1610   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1611   br label %loop_2
1612
1613 loop_2:
1614   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1615   br label %loop_3
1616
1617 loop_3:
1618   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1619   br i1 %cond1, label %loop_3_backedge, label %intermediate
1620
1621 intermediate:
1622   br i1 false, label %loop_3_backedge, label %loop_1_backedge
1623
1624 loop_3_backedge:
1625   %k.next = add i32 %k, 1
1626   br i1 %cond2, label %loop_3, label %loop_2_backedge
1627
1628 loop_2_backedge:
1629   %j.next = add i32 %j, 1
1630   %c_2 = icmp slt i32 %j.next, %N
1631   br i1 %c_2, label %loop_2, label %loop_1_backedge
1632
1633 loop_1_backedge:
1634   %i.next = add i32 %i, 1
1635   %c_1 = icmp slt i32 %i.next, %N
1636   br i1 %c_1, label %loop_1, label %exit
1637
1638 exit:
1639   ret i32 %i
1640 }
1641
1642 define i32 @intermediate_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
1643 ; CHECK-LABEL: @intermediate_switch_from_inner_to_grandparent(
1644 ; CHECK-NEXT:  preheader:
1645 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1646 ; CHECK:       loop_1:
1647 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1648 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1649 ; CHECK:       loop_2:
1650 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1651 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1652 ; CHECK:       loop_3:
1653 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1654 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1655 ; CHECK:       intermediate:
1656 ; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
1657 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
1658 ; CHECK-NEXT:    ]
1659 ; CHECK:       loop_3_backedge:
1660 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1661 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1662 ; CHECK:       loop_2_backedge:
1663 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1664 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1665 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1666 ; CHECK:       loop_1_backedge.loopexit:
1667 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1668 ; CHECK:       loop_1_backedge.loopexit1:
1669 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1670 ; CHECK:       loop_1_backedge:
1671 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1672 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1673 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1674 ; CHECK:       exit:
1675 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1676 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1677 ;
1678 preheader:
1679   br label %loop_1
1680
1681 loop_1:
1682   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1683   br label %loop_2
1684
1685 loop_2:
1686   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1687   br label %loop_3
1688
1689 loop_3:
1690   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1691   br i1 %cond1, label %loop_3_backedge, label %intermediate
1692
1693 intermediate:
1694   switch i32 1, label %loop_1_backedge [i32 0, label %loop_3_backedge]
1695
1696 loop_3_backedge:
1697   %k.next = add i32 %k, 1
1698   br i1 %cond2, label %loop_3, label %loop_2_backedge
1699
1700 loop_2_backedge:
1701   %j.next = add i32 %j, 1
1702   %c_2 = icmp slt i32 %j.next, %N
1703   br i1 %c_2, label %loop_2, label %loop_1_backedge
1704
1705 loop_1_backedge:
1706   %i.next = add i32 %i, 1
1707   %c_1 = icmp slt i32 %i.next, %N
1708   br i1 %c_1, label %loop_1, label %exit
1709
1710 exit:
1711   ret i32 %i
1712 }
1713
1714 define i32 @intermediate_branch_from_inner_to_parent(i1 %cond1, i1 %cond2, i32 %N) {
1715 ; CHECK-LABEL: @intermediate_branch_from_inner_to_parent(
1716 ; CHECK-NEXT:  preheader:
1717 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1718 ; CHECK:       loop_1:
1719 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1720 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1721 ; CHECK:       loop_2:
1722 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1723 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1724 ; CHECK:       loop_3:
1725 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1726 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1727 ; CHECK:       intermediate:
1728 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
1729 ; CHECK:       loop_3_backedge:
1730 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1731 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1732 ; CHECK:       loop_2_backedge:
1733 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1734 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1735 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
1736 ; CHECK:       loop_1_backedge:
1737 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1738 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1739 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1740 ; CHECK:       exit:
1741 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1742 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1743 ;
1744 preheader:
1745   br label %loop_1
1746
1747 loop_1:
1748   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1749   br label %loop_2
1750
1751 loop_2:
1752   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1753   br label %loop_3
1754
1755 loop_3:
1756   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1757   br i1 %cond1, label %loop_3_backedge, label %intermediate
1758
1759 intermediate:
1760   br i1 false, label %loop_3_backedge, label %loop_2_backedge
1761
1762 loop_3_backedge:
1763   %k.next = add i32 %k, 1
1764   br i1 %cond2, label %loop_3, label %loop_2_backedge
1765
1766 loop_2_backedge:
1767   %j.next = add i32 %j, 1
1768   %c_2 = icmp slt i32 %j.next, %N
1769   br i1 %c_2, label %loop_2, label %loop_1_backedge
1770
1771 loop_1_backedge:
1772   %i.next = add i32 %i, 1
1773   %c_1 = icmp slt i32 %i.next, %N
1774   br i1 %c_1, label %loop_1, label %exit
1775
1776 exit:
1777   ret i32 %i
1778 }
1779
1780 define i32 @intermediate_switch_from_inner_to_parent(i1 %cond1, i1 %cond2, i32 %N) {
1781 ; CHECK-LABEL: @intermediate_switch_from_inner_to_parent(
1782 ; CHECK-NEXT:  preheader:
1783 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1784 ; CHECK:       loop_1:
1785 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1786 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1787 ; CHECK:       loop_2:
1788 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1789 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1790 ; CHECK:       loop_3:
1791 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1792 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1793 ; CHECK:       intermediate:
1794 ; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
1795 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
1796 ; CHECK-NEXT:    ]
1797 ; CHECK:       loop_3_backedge:
1798 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1799 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1800 ; CHECK:       loop_2_backedge:
1801 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1802 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1803 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
1804 ; CHECK:       loop_1_backedge:
1805 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1806 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1807 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1808 ; CHECK:       exit:
1809 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1810 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1811 ;
1812 preheader:
1813   br label %loop_1
1814
1815 loop_1:
1816   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1817   br label %loop_2
1818
1819 loop_2:
1820   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1821   br label %loop_3
1822
1823 loop_3:
1824   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1825   br i1 %cond1, label %loop_3_backedge, label %intermediate
1826
1827 intermediate:
1828   switch i32 1, label %loop_2_backedge [i32 0, label %loop_3_backedge]
1829
1830 loop_3_backedge:
1831   %k.next = add i32 %k, 1
1832   br i1 %cond2, label %loop_3, label %loop_2_backedge
1833
1834 loop_2_backedge:
1835   %j.next = add i32 %j, 1
1836   %c_2 = icmp slt i32 %j.next, %N
1837   br i1 %c_2, label %loop_2, label %loop_1_backedge
1838
1839 loop_1_backedge:
1840   %i.next = add i32 %i, 1
1841   %c_1 = icmp slt i32 %i.next, %N
1842   br i1 %c_1, label %loop_1, label %exit
1843
1844 exit:
1845   ret i32 %i
1846 }
1847
1848 define i32 @intermediate_subloop_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
1849 ; CHECK-LABEL: @intermediate_subloop_branch_from_inner_to_grandparent(
1850 ; CHECK-NEXT:  preheader:
1851 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1852 ; CHECK:       loop_1:
1853 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1854 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1855 ; CHECK:       loop_2:
1856 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1857 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1858 ; CHECK:       loop_3:
1859 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1860 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1861 ; CHECK:       intermediate:
1862 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
1863 ; CHECK:       intermediate_loop:
1864 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
1865 ; CHECK:       intermediate_exit:
1866 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
1867 ; CHECK:       loop_3_backedge:
1868 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1869 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1870 ; CHECK:       loop_2_backedge:
1871 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1872 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1873 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1874 ; CHECK:       loop_1_backedge.loopexit:
1875 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1876 ; CHECK:       loop_1_backedge.loopexit1:
1877 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1878 ; CHECK:       loop_1_backedge:
1879 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1880 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1881 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1882 ; CHECK:       exit:
1883 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1884 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1885 ;
1886 preheader:
1887   br label %loop_1
1888
1889 loop_1:
1890   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1891   br label %loop_2
1892
1893 loop_2:
1894   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1895   br label %loop_3
1896
1897 loop_3:
1898   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1899   br i1 %cond1, label %loop_3_backedge, label %intermediate
1900
1901 intermediate:
1902   br label %intermediate_loop
1903
1904 intermediate_loop:
1905   br i1 %cond3, label %intermediate_loop, label %intermediate_exit
1906
1907 intermediate_exit:
1908   br i1 false, label %loop_3_backedge, label %loop_1_backedge
1909
1910 loop_3_backedge:
1911   %k.next = add i32 %k, 1
1912   br i1 %cond2, label %loop_3, label %loop_2_backedge
1913
1914 loop_2_backedge:
1915   %j.next = add i32 %j, 1
1916   %c_2 = icmp slt i32 %j.next, %N
1917   br i1 %c_2, label %loop_2, label %loop_1_backedge
1918
1919 loop_1_backedge:
1920   %i.next = add i32 %i, 1
1921   %c_1 = icmp slt i32 %i.next, %N
1922   br i1 %c_1, label %loop_1, label %exit
1923
1924 exit:
1925   ret i32 %i
1926 }
1927
1928 define i32 @intermediate_subloop_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
1929 ; CHECK-LABEL: @intermediate_subloop_switch_from_inner_to_grandparent(
1930 ; CHECK-NEXT:  preheader:
1931 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
1932 ; CHECK:       loop_1:
1933 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
1934 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
1935 ; CHECK:       loop_2:
1936 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
1937 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
1938 ; CHECK:       loop_3:
1939 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
1940 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
1941 ; CHECK:       intermediate:
1942 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
1943 ; CHECK:       intermediate_loop:
1944 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
1945 ; CHECK:       intermediate_exit:
1946 ; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
1947 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
1948 ; CHECK-NEXT:    ]
1949 ; CHECK:       loop_3_backedge:
1950 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
1951 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
1952 ; CHECK:       loop_2_backedge:
1953 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
1954 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
1955 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
1956 ; CHECK:       loop_1_backedge.loopexit:
1957 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1958 ; CHECK:       loop_1_backedge.loopexit1:
1959 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
1960 ; CHECK:       loop_1_backedge:
1961 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
1962 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
1963 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
1964 ; CHECK:       exit:
1965 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
1966 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
1967 ;
1968 preheader:
1969   br label %loop_1
1970
1971 loop_1:
1972   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
1973   br label %loop_2
1974
1975 loop_2:
1976   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
1977   br label %loop_3
1978
1979 loop_3:
1980   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
1981   br i1 %cond1, label %loop_3_backedge, label %intermediate
1982
1983 intermediate:
1984   br label %intermediate_loop
1985
1986 intermediate_loop:
1987   br i1 %cond3, label %intermediate_loop, label %intermediate_exit
1988
1989 intermediate_exit:
1990   switch i32 1, label %loop_1_backedge [i32 0, label %loop_3_backedge]
1991
1992 loop_3_backedge:
1993   %k.next = add i32 %k, 1
1994   br i1 %cond2, label %loop_3, label %loop_2_backedge
1995
1996 loop_2_backedge:
1997   %j.next = add i32 %j, 1
1998   %c_2 = icmp slt i32 %j.next, %N
1999   br i1 %c_2, label %loop_2, label %loop_1_backedge
2000
2001 loop_1_backedge:
2002   %i.next = add i32 %i, 1
2003   %c_1 = icmp slt i32 %i.next, %N
2004   br i1 %c_1, label %loop_1, label %exit
2005
2006 exit:
2007   ret i32 %i
2008 }
2009
2010 define i32 @intermediate_subloop_branch_from_inner_to_parent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2011 ; CHECK-LABEL: @intermediate_subloop_branch_from_inner_to_parent(
2012 ; CHECK-NEXT:  preheader:
2013 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2014 ; CHECK:       loop_1:
2015 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2016 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2017 ; CHECK:       loop_2:
2018 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2019 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2020 ; CHECK:       loop_3:
2021 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2022 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2023 ; CHECK:       intermediate:
2024 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2025 ; CHECK:       intermediate_loop:
2026 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
2027 ; CHECK:       intermediate_exit:
2028 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
2029 ; CHECK:       loop_3_backedge:
2030 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2031 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2032 ; CHECK:       loop_2_backedge:
2033 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2034 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2035 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
2036 ; CHECK:       loop_1_backedge:
2037 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2038 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2039 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2040 ; CHECK:       exit:
2041 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2042 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2043 ;
2044 preheader:
2045   br label %loop_1
2046
2047 loop_1:
2048   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2049   br label %loop_2
2050
2051 loop_2:
2052   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2053   br label %loop_3
2054
2055 loop_3:
2056   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2057   br i1 %cond1, label %loop_3_backedge, label %intermediate
2058
2059 intermediate:
2060   br label %intermediate_loop
2061
2062 intermediate_loop:
2063   br i1 %cond3, label %intermediate_loop, label %intermediate_exit
2064
2065 intermediate_exit:
2066   br i1 false, label %loop_3_backedge, label %loop_2_backedge
2067
2068 loop_3_backedge:
2069   %k.next = add i32 %k, 1
2070   br i1 %cond2, label %loop_3, label %loop_2_backedge
2071
2072 loop_2_backedge:
2073   %j.next = add i32 %j, 1
2074   %c_2 = icmp slt i32 %j.next, %N
2075   br i1 %c_2, label %loop_2, label %loop_1_backedge
2076
2077 loop_1_backedge:
2078   %i.next = add i32 %i, 1
2079   %c_1 = icmp slt i32 %i.next, %N
2080   br i1 %c_1, label %loop_1, label %exit
2081
2082 exit:
2083   ret i32 %i
2084 }
2085
2086 define i32 @intermediate_subloop_switch_from_inner_to_parent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2087 ; CHECK-LABEL: @intermediate_subloop_switch_from_inner_to_parent(
2088 ; CHECK-NEXT:  preheader:
2089 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2090 ; CHECK:       loop_1:
2091 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2092 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2093 ; CHECK:       loop_2:
2094 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2095 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2096 ; CHECK:       loop_3:
2097 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2098 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2099 ; CHECK:       intermediate:
2100 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2101 ; CHECK:       intermediate_loop:
2102 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
2103 ; CHECK:       intermediate_exit:
2104 ; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
2105 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
2106 ; CHECK-NEXT:    ]
2107 ; CHECK:       loop_3_backedge:
2108 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2109 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2110 ; CHECK:       loop_2_backedge:
2111 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2112 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2113 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
2114 ; CHECK:       loop_1_backedge:
2115 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2116 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2117 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2118 ; CHECK:       exit:
2119 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2120 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2121 ;
2122 preheader:
2123   br label %loop_1
2124
2125 loop_1:
2126   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2127   br label %loop_2
2128
2129 loop_2:
2130   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2131   br label %loop_3
2132
2133 loop_3:
2134   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2135   br i1 %cond1, label %loop_3_backedge, label %intermediate
2136
2137 intermediate:
2138   br label %intermediate_loop
2139
2140 intermediate_loop:
2141   br i1 %cond3, label %intermediate_loop, label %intermediate_exit
2142
2143 intermediate_exit:
2144   switch i32 1, label %loop_2_backedge [i32 0, label %loop_3_backedge]
2145
2146 loop_3_backedge:
2147   %k.next = add i32 %k, 1
2148   br i1 %cond2, label %loop_3, label %loop_2_backedge
2149
2150 loop_2_backedge:
2151   %j.next = add i32 %j, 1
2152   %c_2 = icmp slt i32 %j.next, %N
2153   br i1 %c_2, label %loop_2, label %loop_1_backedge
2154
2155 loop_1_backedge:
2156   %i.next = add i32 %i, 1
2157   %c_1 = icmp slt i32 %i.next, %N
2158   br i1 %c_1, label %loop_1, label %exit
2159
2160 exit:
2161   ret i32 %i
2162 }
2163
2164 define i32 @intermediate_complex_subloop_branch_from_inner_to_parent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2165 ; CHECK-LABEL: @intermediate_complex_subloop_branch_from_inner_to_parent(
2166 ; CHECK-NEXT:  preheader:
2167 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2168 ; CHECK:       loop_1:
2169 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2170 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2171 ; CHECK:       loop_2:
2172 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2173 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2174 ; CHECK:       loop_3:
2175 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2176 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2177 ; CHECK:       intermediate:
2178 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2179 ; CHECK:       intermediate_loop:
2180 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
2181 ; CHECK:       intermediate_loop.backedge:
2182 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
2183 ; CHECK:       intermediate_block:
2184 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
2185 ; CHECK:       intermediate_exit:
2186 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
2187 ; CHECK:       loop_3_backedge:
2188 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2189 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2190 ; CHECK:       loop_2_backedge:
2191 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2192 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2193 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
2194 ; CHECK:       loop_1_backedge:
2195 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2196 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2197 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2198 ; CHECK:       exit:
2199 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2200 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2201 ;
2202 preheader:
2203   br label %loop_1
2204
2205 loop_1:
2206   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2207   br label %loop_2
2208
2209 loop_2:
2210   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2211   br label %loop_3
2212
2213 loop_3:
2214   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2215   br i1 %cond1, label %loop_3_backedge, label %intermediate
2216
2217 intermediate:
2218   br label %intermediate_loop
2219
2220 intermediate_loop:
2221   br i1 %cond3, label %intermediate_loop, label %intermediate_block
2222
2223 intermediate_block:
2224   br i1 %cond2, label %intermediate_loop, label %intermediate_exit
2225
2226 intermediate_exit:
2227   br i1 false, label %loop_3_backedge, label %loop_2_backedge
2228
2229 loop_3_backedge:
2230   %k.next = add i32 %k, 1
2231   br i1 %cond2, label %loop_3, label %loop_2_backedge
2232
2233 loop_2_backedge:
2234   %j.next = add i32 %j, 1
2235   %c_2 = icmp slt i32 %j.next, %N
2236   br i1 %c_2, label %loop_2, label %loop_1_backedge
2237
2238 loop_1_backedge:
2239   %i.next = add i32 %i, 1
2240   %c_1 = icmp slt i32 %i.next, %N
2241   br i1 %c_1, label %loop_1, label %exit
2242
2243 exit:
2244   ret i32 %i
2245 }
2246
2247 define i32 @intermediate_complex_subloop_switch_from_inner_to_parent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2248 ; CHECK-LABEL: @intermediate_complex_subloop_switch_from_inner_to_parent(
2249 ; CHECK-NEXT:  preheader:
2250 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2251 ; CHECK:       loop_1:
2252 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2253 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2254 ; CHECK:       loop_2:
2255 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2256 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2257 ; CHECK:       loop_3:
2258 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2259 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2260 ; CHECK:       intermediate:
2261 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2262 ; CHECK:       intermediate_loop:
2263 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
2264 ; CHECK:       intermediate_loop.backedge:
2265 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
2266 ; CHECK:       intermediate_block:
2267 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
2268 ; CHECK:       intermediate_exit:
2269 ; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
2270 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
2271 ; CHECK-NEXT:    ]
2272 ; CHECK:       loop_3_backedge:
2273 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2274 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2275 ; CHECK:       loop_2_backedge:
2276 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2277 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2278 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE]]
2279 ; CHECK:       loop_1_backedge:
2280 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2281 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2282 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2283 ; CHECK:       exit:
2284 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2285 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2286 ;
2287 preheader:
2288   br label %loop_1
2289
2290 loop_1:
2291   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2292   br label %loop_2
2293
2294 loop_2:
2295   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2296   br label %loop_3
2297
2298 loop_3:
2299   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2300   br i1 %cond1, label %loop_3_backedge, label %intermediate
2301
2302 intermediate:
2303   br label %intermediate_loop
2304
2305 intermediate_loop:
2306   br i1 %cond3, label %intermediate_loop, label %intermediate_block
2307
2308 intermediate_block:
2309   br i1 %cond2, label %intermediate_loop, label %intermediate_exit
2310
2311 intermediate_exit:
2312   switch i32 1, label %loop_2_backedge [i32 0, label %loop_3_backedge]
2313
2314 loop_3_backedge:
2315   %k.next = add i32 %k, 1
2316   br i1 %cond2, label %loop_3, label %loop_2_backedge
2317
2318 loop_2_backedge:
2319   %j.next = add i32 %j, 1
2320   %c_2 = icmp slt i32 %j.next, %N
2321   br i1 %c_2, label %loop_2, label %loop_1_backedge
2322
2323 loop_1_backedge:
2324   %i.next = add i32 %i, 1
2325   %c_1 = icmp slt i32 %i.next, %N
2326   br i1 %c_1, label %loop_1, label %exit
2327
2328 exit:
2329   ret i32 %i
2330 }
2331
2332
2333 define i32 @intermediate_complex_subloop_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2334 ; CHECK-LABEL: @intermediate_complex_subloop_branch_from_inner_to_grandparent(
2335 ; CHECK-NEXT:  preheader:
2336 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2337 ; CHECK:       loop_1:
2338 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2339 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2340 ; CHECK:       loop_2:
2341 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2342 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2343 ; CHECK:       loop_3:
2344 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2345 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2346 ; CHECK:       intermediate:
2347 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2348 ; CHECK:       intermediate_loop:
2349 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
2350 ; CHECK:       intermediate_loop.backedge:
2351 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
2352 ; CHECK:       intermediate_block:
2353 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
2354 ; CHECK:       intermediate_exit:
2355 ; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
2356 ; CHECK:       loop_3_backedge:
2357 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2358 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2359 ; CHECK:       loop_2_backedge:
2360 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2361 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2362 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
2363 ; CHECK:       loop_1_backedge.loopexit:
2364 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
2365 ; CHECK:       loop_1_backedge.loopexit1:
2366 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
2367 ; CHECK:       loop_1_backedge:
2368 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2369 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2370 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2371 ; CHECK:       exit:
2372 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2373 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2374 ;
2375 preheader:
2376   br label %loop_1
2377
2378 loop_1:
2379   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2380   br label %loop_2
2381
2382 loop_2:
2383   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2384   br label %loop_3
2385
2386 loop_3:
2387   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2388   br i1 %cond1, label %loop_3_backedge, label %intermediate
2389
2390 intermediate:
2391   br label %intermediate_loop
2392
2393 intermediate_loop:
2394   br i1 %cond3, label %intermediate_loop, label %intermediate_block
2395
2396 intermediate_block:
2397   br i1 %cond2, label %intermediate_loop, label %intermediate_exit
2398
2399 intermediate_exit:
2400   br i1 false, label %loop_3_backedge, label %loop_1_backedge
2401
2402 loop_3_backedge:
2403   %k.next = add i32 %k, 1
2404   br i1 %cond2, label %loop_3, label %loop_2_backedge
2405
2406 loop_2_backedge:
2407   %j.next = add i32 %j, 1
2408   %c_2 = icmp slt i32 %j.next, %N
2409   br i1 %c_2, label %loop_2, label %loop_1_backedge
2410
2411 loop_1_backedge:
2412   %i.next = add i32 %i, 1
2413   %c_1 = icmp slt i32 %i.next, %N
2414   br i1 %c_1, label %loop_1, label %exit
2415
2416 exit:
2417   ret i32 %i
2418 }
2419
2420 define i32 @intermediate_complex_subloop_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i1 %cond3, i32 %N) {
2421 ; CHECK-LABEL: @intermediate_complex_subloop_switch_from_inner_to_grandparent(
2422 ; CHECK-NEXT:  preheader:
2423 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
2424 ; CHECK:       loop_1:
2425 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
2426 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
2427 ; CHECK:       loop_2:
2428 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
2429 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
2430 ; CHECK:       loop_3:
2431 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
2432 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
2433 ; CHECK:       intermediate:
2434 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
2435 ; CHECK:       intermediate_loop:
2436 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
2437 ; CHECK:       intermediate_loop.backedge:
2438 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
2439 ; CHECK:       intermediate_block:
2440 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
2441 ; CHECK:       intermediate_exit:
2442 ; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
2443 ; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
2444 ; CHECK-NEXT:    ]
2445 ; CHECK:       loop_3_backedge:
2446 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
2447 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
2448 ; CHECK:       loop_2_backedge:
2449 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
2450 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
2451 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
2452 ; CHECK:       loop_1_backedge.loopexit:
2453 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
2454 ; CHECK:       loop_1_backedge.loopexit1:
2455 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
2456 ; CHECK:       loop_1_backedge:
2457 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
2458 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
2459 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
2460 ; CHECK:       exit:
2461 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
2462 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
2463 ;
2464 preheader:
2465   br label %loop_1
2466
2467 loop_1:
2468   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
2469   br label %loop_2
2470
2471 loop_2:
2472   %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ]
2473   br label %loop_3
2474
2475 loop_3:
2476   %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ]
2477   br i1 %cond1, label %loop_3_backedge, label %intermediate
2478
2479 intermediate:
2480   br label %intermediate_loop
2481
2482 intermediate_loop:
2483   br i1 %cond3, label %intermediate_loop, label %intermediate_block
2484
2485 intermediate_block:
2486   br i1 %cond2, label %intermediate_loop, label %intermediate_exit
2487
2488 intermediate_exit:
2489   switch i32 1, label %loop_1_backedge [i32 0, label %loop_3_backedge]
2490
2491 loop_3_backedge:
2492   %k.next = add i32 %k, 1
2493   br i1 %cond2, label %loop_3, label %loop_2_backedge
2494
2495 loop_2_backedge:
2496   %j.next = add i32 %j, 1
2497   %c_2 = icmp slt i32 %j.next, %N
2498   br i1 %c_2, label %loop_2, label %loop_1_backedge
2499
2500 loop_1_backedge:
2501   %i.next = add i32 %i, 1
2502   %c_1 = icmp slt i32 %i.next, %N
2503   br i1 %c_1, label %loop_1, label %exit
2504
2505 exit:
2506   ret i32 %i
2507 }
2508
2509 define i32 @complex_dead_subloop_branch(i1 %cond1, i1 %cond2, i1 %cond3) {
2510 ; CHECK-LABEL: @complex_dead_subloop_branch(
2511 ; CHECK-NEXT:  entry:
2512 ; CHECK-NEXT:    br label [[LOOP:%.*]]
2513 ; CHECK:       loop:
2514 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[LOOP]], label [[EXIT:%.*]]
2515 ; CHECK:       exit:
2516 ; CHECK-NEXT:    [[RESULT_LCSSA:%.*]] = phi i32 [ 0, [[LOOP]] ]
2517 ; CHECK-NEXT:    ret i32 [[RESULT_LCSSA]]
2518 ;
2519 entry:
2520   br label %loop
2521
2522 loop:
2523   br i1 true, label %latch, label %subloop
2524
2525 subloop:
2526   br i1 %cond1, label %x, label %y
2527
2528 x:
2529   br label %subloop_latch
2530
2531 y:
2532   br label %subloop_latch
2533
2534 subloop_latch:
2535   %dead_phi = phi i32 [ 1, %x ], [ 2, %y ]
2536   br i1 %cond2, label %latch, label %subloop
2537
2538 latch:
2539   %result = phi i32 [ 0, %loop ], [ %dead_phi, %subloop_latch ]
2540   br i1 %cond3, label %loop, label %exit
2541
2542 exit:
2543   ret i32 %result
2544 }
2545
2546 define i32 @complex_dead_subloop_switch(i1 %cond1, i1 %cond2, i1 %cond3) {
2547 ; CHECK-LABEL: @complex_dead_subloop_switch(
2548 ; CHECK-NEXT:  entry:
2549 ; CHECK-NEXT:    br label [[LOOP:%.*]]
2550 ; CHECK:       loop:
2551 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[LOOP]], label [[EXIT:%.*]]
2552 ; CHECK:       exit:
2553 ; CHECK-NEXT:    [[RESULT_LCSSA:%.*]] = phi i32 [ 0, [[LOOP]] ]
2554 ; CHECK-NEXT:    ret i32 [[RESULT_LCSSA]]
2555 ;
2556 entry:
2557   br label %loop
2558
2559 loop:
2560   switch i32 1, label %latch [ i32 0, label %subloop ]
2561
2562 subloop:
2563   br i1 %cond1, label %x, label %y
2564
2565 x:
2566   br label %subloop_latch
2567
2568 y:
2569   br label %subloop_latch
2570
2571 subloop_latch:
2572   %dead_phi = phi i32 [ 1, %x ], [ 2, %y ]
2573   br i1 %cond2, label %latch, label %subloop
2574
2575 latch:
2576   %result = phi i32 [ 0, %loop ], [ %dead_phi, %subloop_latch ]
2577   br i1 %cond3, label %loop, label %exit
2578
2579 exit:
2580   ret i32 %result
2581 }
2582
2583 define void @test_crash_01() {
2584 ; CHECK-LABEL: @test_crash_01(
2585 ; CHECK-NEXT:  bb:
2586 ; CHECK-NEXT:    br label [[BB1:%.*]]
2587 ; CHECK:       bb1:
2588 ; CHECK-NEXT:    br i1 undef, label [[BB17:%.*]], label [[BB2:%.*]]
2589 ; CHECK:       bb2:
2590 ; CHECK-NEXT:    switch i32 0, label [[BB2_SPLIT:%.*]] [
2591 ; CHECK-NEXT:    i32 1, label [[BB19:%.*]]
2592 ; CHECK-NEXT:    ]
2593 ; CHECK:       bb2.split:
2594 ; CHECK-NEXT:    br label [[BB3:%.*]]
2595 ; CHECK:       bb3:
2596 ; CHECK-NEXT:    switch i32 undef, label [[BB16:%.*]] [
2597 ; CHECK-NEXT:    i32 0, label [[BB15:%.*]]
2598 ; CHECK-NEXT:    i32 1, label [[BB14:%.*]]
2599 ; CHECK-NEXT:    i32 2, label [[BB13:%.*]]
2600 ; CHECK-NEXT:    i32 3, label [[BB12:%.*]]
2601 ; CHECK-NEXT:    i32 4, label [[BB11:%.*]]
2602 ; CHECK-NEXT:    i32 5, label [[BB8:%.*]]
2603 ; CHECK-NEXT:    i32 6, label [[BB10:%.*]]
2604 ; CHECK-NEXT:    i32 7, label [[BB9:%.*]]
2605 ; CHECK-NEXT:    i32 8, label [[BB7:%.*]]
2606 ; CHECK-NEXT:    ]
2607 ; CHECK:       bb7:
2608 ; CHECK-NEXT:    unreachable
2609 ; CHECK:       bb8:
2610 ; CHECK-NEXT:    switch i32 undef, label [[BB28:%.*]] [
2611 ; CHECK-NEXT:    i32 0, label [[BB27:%.*]]
2612 ; CHECK-NEXT:    i32 1, label [[BB26:%.*]]
2613 ; CHECK-NEXT:    i32 2, label [[BB23:%.*]]
2614 ; CHECK-NEXT:    i32 3, label [[BB24:%.*]]
2615 ; CHECK-NEXT:    i32 4, label [[BB25:%.*]]
2616 ; CHECK-NEXT:    i32 5, label [[BB29:%.*]]
2617 ; CHECK-NEXT:    i32 6, label [[BB22:%.*]]
2618 ; CHECK-NEXT:    i32 7, label [[BB20:%.*]]
2619 ; CHECK-NEXT:    i32 8, label [[BB21:%.*]]
2620 ; CHECK-NEXT:    ]
2621 ; CHECK:       bb9:
2622 ; CHECK-NEXT:    unreachable
2623 ; CHECK:       bb10:
2624 ; CHECK-NEXT:    unreachable
2625 ; CHECK:       bb11:
2626 ; CHECK-NEXT:    br label [[BB8]]
2627 ; CHECK:       bb12:
2628 ; CHECK-NEXT:    unreachable
2629 ; CHECK:       bb13:
2630 ; CHECK-NEXT:    unreachable
2631 ; CHECK:       bb14:
2632 ; CHECK-NEXT:    unreachable
2633 ; CHECK:       bb15:
2634 ; CHECK-NEXT:    unreachable
2635 ; CHECK:       bb16:
2636 ; CHECK-NEXT:    unreachable
2637 ; CHECK:       bb17:
2638 ; CHECK-NEXT:    ret void
2639 ; CHECK:       bb19:
2640 ; CHECK-NEXT:    ret void
2641 ; CHECK:       bb20:
2642 ; CHECK-NEXT:    unreachable
2643 ; CHECK:       bb21:
2644 ; CHECK-NEXT:    unreachable
2645 ; CHECK:       bb22:
2646 ; CHECK-NEXT:    unreachable
2647 ; CHECK:       bb23:
2648 ; CHECK-NEXT:    unreachable
2649 ; CHECK:       bb24:
2650 ; CHECK-NEXT:    unreachable
2651 ; CHECK:       bb25:
2652 ; CHECK-NEXT:    unreachable
2653 ; CHECK:       bb26:
2654 ; CHECK-NEXT:    unreachable
2655 ; CHECK:       bb27:
2656 ; CHECK-NEXT:    unreachable
2657 ; CHECK:       bb28:
2658 ; CHECK-NEXT:    unreachable
2659 ; CHECK:       bb29:
2660 ; CHECK-NEXT:    br label [[BB3]]
2661 ;
2662 bb:
2663   br label %bb1
2664
2665 bb1:                                              ; preds = %bb
2666   br i1 undef, label %bb17, label %bb2
2667
2668 bb2:                                              ; preds = %bb1
2669   br label %bb3
2670
2671 bb3:                                              ; preds = %bb6, %bb2
2672   br label %bb4
2673
2674 bb4:                                              ; preds = %bb3
2675   switch i32 0, label %bb5 [
2676   i32 1, label %bb19
2677   i32 2, label %bb18
2678   ]
2679
2680 bb5:                                              ; preds = %bb4
2681   switch i32 undef, label %bb16 [
2682   i32 0, label %bb15
2683   i32 1, label %bb14
2684   i32 2, label %bb13
2685   i32 3, label %bb12
2686   i32 4, label %bb11
2687   i32 5, label %bb8
2688   i32 6, label %bb10
2689   i32 7, label %bb9
2690   i32 8, label %bb7
2691   ]
2692
2693 bb6:                                              ; preds = %bb29, %bb18
2694   br label %bb3
2695
2696 bb7:                                              ; preds = %bb5
2697   unreachable
2698
2699 bb8:                                              ; preds = %bb11, %bb5
2700   switch i32 undef, label %bb28 [
2701   i32 0, label %bb27
2702   i32 1, label %bb26
2703   i32 2, label %bb23
2704   i32 3, label %bb24
2705   i32 4, label %bb25
2706   i32 5, label %bb29
2707   i32 6, label %bb22
2708   i32 7, label %bb20
2709   i32 8, label %bb21
2710   ]
2711
2712 bb9:                                              ; preds = %bb5
2713   unreachable
2714
2715 bb10:                                             ; preds = %bb5
2716   unreachable
2717
2718 bb11:                                             ; preds = %bb5
2719   br label %bb8
2720
2721 bb12:                                             ; preds = %bb5
2722   unreachable
2723
2724 bb13:                                             ; preds = %bb5
2725   unreachable
2726
2727 bb14:                                             ; preds = %bb5
2728   unreachable
2729
2730 bb15:                                             ; preds = %bb5
2731   unreachable
2732
2733 bb16:                                             ; preds = %bb5
2734   unreachable
2735
2736 bb17:                                             ; preds = %bb1
2737   ret void
2738
2739 bb18:                                             ; preds = %bb4
2740   br label %bb6
2741
2742 bb19:                                             ; preds = %bb4
2743   ret void
2744
2745 bb20:                                             ; preds = %bb8
2746   unreachable
2747
2748 bb21:                                             ; preds = %bb8
2749   unreachable
2750
2751 bb22:                                             ; preds = %bb8
2752   unreachable
2753
2754 bb23:                                             ; preds = %bb8
2755   unreachable
2756
2757 bb24:                                             ; preds = %bb8
2758   unreachable
2759
2760 bb25:                                             ; preds = %bb8
2761   unreachable
2762
2763 bb26:                                             ; preds = %bb8
2764   unreachable
2765
2766 bb27:                                             ; preds = %bb8
2767   unreachable
2768
2769 bb28:                                             ; preds = %bb8
2770   unreachable
2771
2772 bb29:                                             ; preds = %bb8
2773   br label %bb6
2774 }