llvm/test/Transforms/LICM/hoist-phi.ll

   1 ; RUN: opt -S -licm < %s | FileCheck %s -check-prefixes=CHECK,CHECK-DISABLED
   2 ; RUN: opt -S -licm -licm-control-flow-hoisting=1 < %s | FileCheck %s -check-prefixes=CHECK,CHECK-ENABLED
   3 ; RUN: opt -S -licm -licm-control-flow-hoisting=0 < %s | FileCheck %s -check-prefixes=CHECK,CHECK-DISABLED
   4 ; RUN: opt -passes='require<opt-remark-emit>,loop-mssa(licm)' -S < %s | FileCheck %s -check-prefixes=CHECK,CHECK-DISABLED
   5
   6 ; RUN: opt -passes='require<opt-remark-emit>,loop-mssa(licm)' -licm-control-flow-hoisting=1 -verify-memoryssa -S < %s | FileCheck %s -check-prefixes=CHECK,CHECK-ENABLED
   7 ; Enable run below when adding promotion. e.g. "store i32 %phi, i32* %p" is promoted to phi.lcssa.
   8 ; opt -passes='require<opt-remark-emit>,loop-mssa(licm)' -licm-control-flow-hoisting=0 -verify-memoryssa -S < %s | FileCheck %s -check-prefixes=CHECK,CHECK-DISABLED
   9
  10
  11 ; CHECK-LABEL: @triangle_phi
  12 define void @triangle_phi(i32 %x, i32* %p) {
  13 ; CHECK-LABEL: entry:
  14 ; CHECK: %cmp1 = icmp sgt i32 %x, 0
  15 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
  16 entry:
  17   br label %loop
  18
  19 ; CHECK-ENABLED: [[IF_LICM]]:
  20 ; CHECK: %add = add i32 %x, 1
  21 ; CHECK-ENABLED: br label %[[THEN_LICM]]
  22
  23 ; CHECK-ENABLED: [[THEN_LICM]]:
  24 ; CHECK-ENABLED: phi i32 [ %add, %[[IF_LICM]] ], [ %x, %entry ]
  25 ; CHECK-ENABLED: store i32 %phi, i32* %p
  26 ; CHECK-ENABLED: %cmp2 = icmp ne i32 %phi, 0
  27 ; CHECK: br label %loop
  28
  29 loop:
  30   %cmp1 = icmp sgt i32 %x, 0
  31   br i1 %cmp1, label %if, label %then
  32
  33 if:
  34   %add = add i32 %x, 1
  35   br label %then
  36
  37 ; CHECK-LABEL: then:
  38 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %x, %loop ]
  39 ; CHECK-DISABLED: %cmp2 = icmp ne i32 %phi, 0
  40 then:
  41   %phi = phi i32 [ %add, %if ], [ %x, %loop ]
  42   store i32 %phi, i32* %p
  43   %cmp2 = icmp ne i32 %phi, 0
  44   br i1 %cmp2, label %loop, label %end
  45
  46 ; CHECK-LABEL: end:
  47 ; CHECK-DISABLED: %[[PHI_LCSSA:.*]] = phi i32 [ %phi, %then ]
  48 ; CHECK-DISABLED: store i32 %[[PHI_LCSSA]], i32* %p
  49 end:
  50   ret void
  51 }
  52
  53 ; CHECK-LABEL: @diamond_phi
  54 define void @diamond_phi(i32 %x, i32* %p) {
  55 ; CHECK-LABEL: entry:
  56 ; CHECK: %cmp1 = icmp sgt i32 %x, 0
  57 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[ELSE_LICM:.*]]
  58 entry:
  59   br label %loop
  60
  61 ; CHECK-ENABLED: [[IF_LICM]]:
  62 ; CHECK-DAG: %add = add i32 %x, 1
  63 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
  64
  65 ; CHECK-ENABLED: [[ELSE_LICM]]:
  66 ; CHECK-DAG: %sub = sub i32 %x, 1
  67 ; CHECK-ENABLED: br label %[[THEN_LICM]]
  68
  69 ; CHECK-ENABLED: [[THEN_LICM]]
  70 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %sub, %[[ELSE_LICM]] ]
  71 ; CHECK-ENABLED: store i32 %phi, i32* %p
  72 ; CHECK-ENABLED: %cmp2 = icmp ne i32 %phi, 0
  73 ; CHECK: br label %loop
  74
  75 loop:
  76   %cmp1 = icmp sgt i32 %x, 0
  77   br i1 %cmp1, label %if, label %else
  78
  79 if:
  80   %add = add i32 %x, 1
  81   br label %then
  82
  83 else:
  84   %sub = sub i32 %x, 1
  85   br label %then
  86
  87 ; CHECK-LABEL: then:
  88 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %sub, %else ]
  89 ; CHECK-DISABLED: %cmp2 = icmp ne i32 %phi, 0
  90 then:
  91   %phi = phi i32 [ %add, %if ], [ %sub, %else ]
  92   store i32 %phi, i32* %p
  93   %cmp2 = icmp ne i32 %phi, 0
  94   br i1 %cmp2, label %loop, label %end
  95
  96 ; CHECK-LABEL: end:
  97 ; CHECK-DISABLED: %[[PHI_LCSSA:.*]] = phi i32 [ %phi, %then ]
  98 ; CHECK-DISABLED: store i32 %[[PHI_LCSSA]], i32* %p
  99 end:
 100   ret void
 101 }
 102
 103 ; TODO: This is currently too complicated for us to be able to hoist the phi.
 104 ; CHECK-LABEL: @three_way_phi
 105 define void @three_way_phi(i32 %x, i32* %p) {
 106 ; CHECK-LABEL: entry:
 107 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 108 ; CHECK-DAG: %add = add i32 %x, 1
 109 ; CHECK-DAG: %cmp2 = icmp sgt i32 %add, 0
 110 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[ELSE_LICM:.*]]
 111
 112 ; CHECK-ENABLED: [[IF_LICM]]:
 113 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 114
 115 ; CHECK-ENABLED: [[THEN_LICM]]:
 116 ; CHECK: %sub = sub i32 %x, 1
 117 ; CHECK: br label %loop
 118
 119 entry:
 120   br label %loop
 121
 122 loop:
 123   %cmp1 = icmp sgt i32 %x, 0
 124   br i1 %cmp1, label %if, label %then
 125
 126 if:
 127   %add = add i32 %x, 1
 128   %cmp2 = icmp sgt i32 %add, 0
 129   br i1 %cmp2, label %if.if, label %then
 130
 131 if.if:
 132   %sub = sub i32 %x, 1
 133   br label %then
 134
 135 then:
 136   %phi = phi i32 [ 0, %loop ], [ %add, %if ], [ %sub, %if.if ]
 137   store i32 %phi, i32* %p
 138   %cmp3 = icmp ne i32 %phi, 0
 139   br i1 %cmp3, label %loop, label %end
 140
 141 end:
 142   ret void
 143 }
 144
 145 ; TODO: This is currently too complicated for us to be able to hoist the phi.
 146 ; CHECK-LABEL: @tree_phi
 147 define void @tree_phi(i32 %x, i32* %p) {
 148 ; CHECK-LABEL: entry:
 149 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 150 ; CHECK-DAG: %add = add i32 %x, 1
 151 ; CHECK-DAG: %cmp2 = icmp sgt i32 %add, 0
 152 ; CHECK-DAG: %sub = sub i32 %x, 1
 153 ; CHECK: br label %loop
 154
 155 entry:
 156   br label %loop
 157
 158 loop:
 159   %cmp1 = icmp sgt i32 %x, 0
 160   br i1 %cmp1, label %if, label %else
 161
 162 if:
 163   %add = add i32 %x, 1
 164   %cmp2 = icmp sgt i32 %add, 0
 165   br i1 %cmp2, label %if.if, label %if.else
 166
 167 if.if:
 168   br label %then
 169
 170 if.else:
 171   br label %then
 172
 173 else:
 174   %sub = sub i32 %x, 1
 175   br label %then
 176
 177 then:
 178   %phi = phi i32 [ %add, %if.if ], [ 0, %if.else ], [ %sub, %else ]
 179   store i32 %phi, i32* %p
 180   %cmp3 = icmp ne i32 %phi, 0
 181   br i1 %cmp3, label %loop, label %end
 182
 183 end:
 184   ret void
 185 }
 186
 187 ; TODO: We can hoist the first phi, but not the second.
 188 ; CHECK-LABEL: @phi_phi
 189 define void @phi_phi(i32 %x, i32* %p) {
 190 ; CHECK-LABEL: entry:
 191 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 192 ; CHECK-DAG: %add = add i32 %x, 1
 193 ; CHECK-DAG: %cmp2 = icmp sgt i32 %add, 0
 194 ; CHECK-DAG: %sub = sub i32 %x, 1
 195 ; CHECK-ENABLED: br i1 %cmp2, label %[[IF_IF_LICM:.*]], label %[[IF_ELSE_LICM:.*]]
 196
 197 ; CHECK-ENABLED: [[IF_IF_LICM]]:
 198 ; CHECK-ENABLED: br label %[[IF_THEN_LICM:.*]]
 199
 200 ; CHECK-ENABLED: [[IF_ELSE_LICM]]:
 201 ; CHECK-ENABLED: br label %[[IF_THEN_LICM]]
 202
 203 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
 204 ; CHECK-ENABLED: %phi1 = phi i32 [ %add, %[[IF_IF_LICM]] ], [ 0, %[[IF_ELSE_LICM]] ]
 205 ; CHECK: br label %loop
 206
 207 entry:
 208   br label %loop
 209
 210 loop:
 211   %cmp1 = icmp sgt i32 %x, 0
 212   br i1 %cmp1, label %if, label %else
 213
 214 if:
 215   %add = add i32 %x, 1
 216   %cmp2 = icmp sgt i32 %add, 0
 217   br i1 %cmp2, label %if.if, label %if.else
 218
 219 if.if:
 220   br label %if.then
 221
 222 if.else:
 223   br label %if.then
 224
 225 ; CHECK-LABEL: if.then:
 226 ; CHECK-DISABLED: %phi1 = phi i32 [ %add, %if.if ], [ 0, %if.else ]
 227 if.then:
 228   %phi1 = phi i32 [ %add, %if.if ], [ 0, %if.else ]
 229   br label %then
 230
 231 else:
 232   %sub = sub i32 %x, 1
 233   br label %then
 234
 235 ; CHECK-LABEL: then:
 236 ; CHECK: %phi2 = phi i32 [ %phi1, %if.then ], [ %sub, %else ]
 237 then:
 238   %phi2 = phi i32 [ %phi1, %if.then ], [ %sub, %else ]
 239   store i32 %phi2, i32* %p
 240   %cmp3 = icmp ne i32 %phi2, 0
 241   br i1 %cmp3, label %loop, label %end
 242
 243 end:
 244   ret void
 245 }
 246
 247 ; Check that we correctly duplicate empty control flow.
 248 ; CHECK-LABEL: @empty_triangle_phi
 249 define i8 @empty_triangle_phi(i32 %x, i32 %y) {
 250 ; CHECK-LABEL: entry:
 251 ; CHECK: %cmp1 = icmp eq i32 %x, 0
 252 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 253 entry:
 254   br label %loop
 255
 256 ; CHECK-ENABLED: [[IF_LICM]]:
 257 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 258
 259 ; CHECK-ENABLED: [[THEN_LICM]]:
 260 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %entry ]
 261 ; CHECK: %cmp2 = icmp eq i32 %y, 0
 262 ; CHECK: br label %loop
 263
 264 loop:
 265   %cmp1 = icmp eq i32 %x, 0
 266   br i1 %cmp1, label %if, label %then
 267
 268 if:
 269   br label %then
 270
 271 ; CHECK-LABEL: then:
 272 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %loop ]
 273 then:
 274   %phi = phi i8 [ 0, %if ], [ 1, %loop ]
 275   %cmp2 = icmp eq i32 %y, 0
 276   br i1 %cmp2, label %end, label %loop
 277
 278 end:
 279   ret i8 %phi
 280 }
 281
 282 ; CHECK-LABEL: @empty_diamond_phi
 283 define i8 @empty_diamond_phi(i32 %x, i32 %y) {
 284 ; CHECK-LABEL: entry:
 285 ; CHECK: %cmp1 = icmp eq i32 %x, 0
 286 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[ELSE_LICM:.*]]
 287 entry:
 288   br label %loop
 289
 290 ; CHECK-ENABLED: [[IF_LICM]]:
 291 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 292
 293 ; CHECK-ENABLED: [[ELSE_LICM]]:
 294 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 295
 296 ; CHECK-ENABLED: [[THEN_LICM]]:
 297 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %[[ELSE_LICM]] ]
 298 ; CHECK: %cmp2 = icmp eq i32 %y, 0
 299 ; CHECK: br label %loop
 300
 301 loop:
 302   %cmp1 = icmp eq i32 %x, 0
 303   br i1 %cmp1, label %if, label %else
 304
 305 if:
 306   br label %then
 307
 308 else:
 309   br label %then
 310
 311 ; CHECK-LABEL: then:
 312 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %else ]
 313 then:
 314   %phi = phi i8 [ 0, %if ], [ 1, %else ]
 315   %cmp2 = icmp eq i32 %y, 0
 316   br i1 %cmp2, label %end, label %loop
 317
 318 end:
 319   ret i8 %phi
 320 }
 321
 322 ; Check that we correctly handle the case that the first thing we try to hoist is a phi.
 323 ; CHECK-LABEL: @empty_triangle_phi_first
 324 define i8 @empty_triangle_phi_first(i32 %x, i1 %cond) {
 325 ; CHECK-LABEL: entry:
 326 ; CHECK-ENABLED: br i1 %cond, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 327 entry:
 328   br label %loop
 329
 330 ; CHECK-ENABLED: [[IF_LICM]]:
 331 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 332
 333 ; CHECK-ENABLED: [[THEN_LICM]]:
 334 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %entry ]
 335 ; CHECK: %cmp = icmp eq i32 %x, 0
 336 ; CHECK: br label %loop
 337
 338 loop:
 339   br i1 %cond, label %if, label %then
 340
 341 if:
 342   br label %then
 343
 344 ; CHECK-LABEL: then:
 345 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %loop ]
 346 then:
 347   %phi = phi i8 [ 0, %if ], [ 1, %loop ]
 348   %cmp = icmp eq i32 %x, 0
 349   br i1 %cmp, label %end, label %loop
 350
 351 end:
 352   ret i8 %phi
 353 }
 354
 355 ; CHECK-LABEL: @empty_diamond_phi
 356 define i8 @empty_diamond_phi_first(i32 %x, i1 %cond) {
 357 ; CHECK-LABEL: entry:
 358 ; CHECK-ENABLED: br i1 %cond, label %[[IF_LICM:.*]], label %[[ELSE_LICM:.*]]
 359 entry:
 360   br label %loop
 361
 362 ; CHECK-ENABLED: [[IF_LICM]]:
 363 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 364
 365 ; CHECK-ENABLED: [[ELSE_LICM]]:
 366 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 367
 368 ; CHECK-ENABLED: [[THEN_LICM]]:
 369 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %[[ELSE_LICM]] ]
 370 ; CHECK: %cmp = icmp eq i32 %x, 0
 371 ; CHECK: br label %loop
 372
 373 loop:
 374   br i1 %cond, label %if, label %else
 375
 376 if:
 377   br label %then
 378
 379 else:
 380   br label %then
 381
 382 ; CHECK-LABEL: then:
 383 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %else ]
 384 then:
 385   %phi = phi i8 [ 0, %if ], [ 1, %else ]
 386   %cmp = icmp eq i32 %x, 0
 387   br i1 %cmp, label %end, label %loop
 388
 389 end:
 390   ret i8 %phi
 391 }
 392
 393 ; CHECK-LABEL: @empty_triangle_phi_first
 394 define i8 @empty_triangle_phi_first_empty_loop_head(i32 %x, i1 %cond) {
 395 ; CHECK-LABEL: entry:
 396 ; CHECK-ENABLED: br i1 %cond, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 397 entry:
 398   br label %loop
 399
 400 ; CHECK-ENABLED: [[IF_LICM]]:
 401 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 402
 403 ; CHECK-ENABLED: [[THEN_LICM]]:
 404 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %entry ]
 405 ; CHECK: %cmp = icmp eq i32 %x, 0
 406 ; CHECK: br label %loop
 407
 408 loop:
 409   br label %test
 410
 411 test:
 412   br i1 %cond, label %if, label %then
 413
 414 if:
 415   br label %then
 416
 417 ; CHECK-LABEL: then:
 418 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %test ]
 419 then:
 420   %phi = phi i8 [ 0, %if ], [ 1, %test ]
 421   %cmp = icmp eq i32 %x, 0
 422   br i1 %cmp, label %end, label %loop
 423
 424 end:
 425   ret i8 %phi
 426 }
 427
 428 ; CHECK-LABEL: @empty_diamond_phi_first_empty_loop_head
 429 define i8 @empty_diamond_phi_first_empty_loop_head(i32 %x, i1 %cond) {
 430 ; CHECK-LABEL: entry:
 431 ; CHECK-ENABLED: br i1 %cond, label %[[IF_LICM:.*]], label %[[ELSE_LICM:.*]]
 432 entry:
 433   br label %loop
 434
 435 ; CHECK-ENABLED: [[IF_LICM]]:
 436 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 437
 438 ; CHECK-ENABLED: [[ELSE_LICM]]:
 439 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 440
 441 ; CHECK-ENABLED: [[THEN_LICM]]:
 442 ; CHECK-ENABLED: %phi = phi i8 [ 0, %[[IF_LICM]] ], [ 1, %[[ELSE_LICM]] ]
 443 ; CHECK: %cmp = icmp eq i32 %x, 0
 444 ; CHECK: br label %loop
 445
 446 loop:
 447   br label %test
 448
 449 test:
 450   br i1 %cond, label %if, label %else
 451
 452 if:
 453   br label %then
 454
 455 else:
 456   br label %then
 457
 458 ; CHECK-LABEL: then:
 459 ; CHECK-DISABLED: %phi = phi i8 [ 0, %if ], [ 1, %else ]
 460 then:
 461   %phi = phi i8 [ 0, %if ], [ 1, %else ]
 462   %cmp = icmp eq i32 %x, 0
 463   br i1 %cmp, label %end, label %loop
 464
 465 end:
 466   ret i8 %phi
 467 }
 468
 469 ; The phi is on one branch of a diamond while simultaneously at the end of a
 470 ; triangle. Check that we duplicate the triangle and not the diamond.
 471 ; CHECK-LABEL: @triangle_diamond
 472 define void @triangle_diamond(i32* %ptr, i32 %x, i32 %y) {
 473 ; CHECK-LABEL: entry:
 474 ; CHECK-DAG: %cmp1 = icmp ne i32 %x, 0
 475 ; CHECK-DAG: %cmp2 = icmp ne i32 %y, 0
 476 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 477 entry:
 478   br label %loop
 479
 480 ; CHECK-ENABLED: [[IF_LICM]]:
 481 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 482
 483 ; CHECK-ENABLED: [[THEN_LICM]]:
 484 ; CHECK-ENABLED: %phi = phi i32 [ 0, %[[IF_LICM]] ], [ 127, %entry ]
 485 ; CHECK: br label %loop
 486
 487 loop:
 488   %cmp1 = icmp ne i32 %x, 0
 489   br i1 %cmp1, label %if, label %then
 490
 491 if:
 492   %cmp2 = icmp ne i32 %y, 0
 493   br i1 %cmp2, label %if.then, label %then
 494
 495 ; CHECK-LABEL: then:
 496 ; CHECK-DISABLED: %phi = phi i32 [ 0, %if ], [ 127, %loop ]
 497 then:
 498   %phi = phi i32 [ 0, %if ], [ 127, %loop ]
 499   store i32 %phi, i32* %ptr
 500   br label %end
 501
 502 if.then:
 503   br label %end
 504
 505 end:
 506   br label %loop
 507 }
 508
 509 ; As the previous, but the end of the diamond is the head of the loop.
 510 ; CHECK-LABEL: @triangle_diamond_backedge
 511 define void @triangle_diamond_backedge(i32* %ptr, i32 %x, i32 %y) {
 512 ; CHECK-LABEL: entry:
 513 ; CHECK-DAG: %cmp1 = icmp ne i32 %x, 0
 514 ; CHECK-DAG: %cmp2 = icmp ne i32 %y, 0
 515 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 516 entry:
 517   br label %loop
 518
 519 ; CHECK-ENABLED: [[IF_LICM]]:
 520 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 521
 522 ; CHECK-ENABLED: [[THEN_LICM]]:
 523 ; CHECK-ENABLED: %phi = phi i32 [ 0, %[[IF_LICM]] ], [ 127, %entry ]
 524 ; CHECK: br label %loop
 525
 526 loop:
 527   %cmp1 = icmp ne i32 %x, 0
 528   br i1 %cmp1, label %if, label %then
 529
 530 if:
 531   %cmp2 = icmp ne i32 %y, 0
 532   br i1 %cmp2, label %backedge, label %then
 533
 534 ; CHECK-LABEL: then:
 535 ; CHECK-DISABLED: %phi = phi i32 [ 0, %if ], [ 127, %loop ]
 536 then:
 537   %phi = phi i32 [ 0, %if ], [ 127, %loop ]
 538   store i32 %phi, i32* %ptr
 539   br label %loop
 540
 541 backedge:
 542   br label %loop
 543 }
 544
 545 ; TODO: The inner diamonds can be hoisted, but not currently the outer diamond
 546 ; CHECK-LABEL: @diamonds_inside_diamond
 547 define void @diamonds_inside_diamond(i32 %x, i32* %p) {
 548 ; CHECK-LABEL: entry:
 549 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 550 ; CHECK-DAG: %cmp3 = icmp slt i32 %x, -10
 551 ; CHECK-ENABLED: br i1 %cmp3, label %[[ELSE_IF_LICM:.*]], label %[[ELSE_ELSE_LICM:.*]]
 552 entry:
 553   br label %loop
 554
 555 ; CHECK-ENABLED: [[ELSE_IF_LICM]]:
 556 ; CHECK-ENABLED: br label %[[ELSE_THEN_LICM:.*]]
 557
 558 ; CHECK-ENABLED: [[ELSE_ELSE_LICM]]:
 559 ; CHECK-ENABLED: br label %[[ELSE_THEN_LICM]]
 560
 561 ; CHECK-ENABLED: [[ELSE_THEN_LICM]]:
 562 ; CHECK-ENABLED: %phi2 = phi i32 [ 2, %[[ELSE_IF_LICM]] ], [ 3, %[[ELSE_ELSE_LICM]] ]
 563 ; CHECK: %cmp2 = icmp sgt i32 %x, 10
 564 ; CHECK-ENABLED: br i1 %cmp2, label %[[IF_IF_LICM:.*]], label %[[IF_ELSE_LICM:.*]]
 565
 566 ; CHECK-ENABLED: [[IF_IF_LICM]]:
 567 ; CHECK-ENABLED: br label %[[IF_THEN_LICM:.*]]
 568
 569 ; CHECK-ENABLED: [[IF_ELSE_LICM]]:
 570 ; CHECK-ENABLED: br label %[[IF_THEN_LICM]]
 571
 572 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
 573 ; CHECK-ENABLED: %phi1 = phi i32 [ 0, %[[IF_IF_LICM]] ], [ 1, %[[IF_ELSE_LICM]] ]
 574 ; CHECK: br label %loop
 575
 576 loop:
 577   %cmp1 = icmp sgt i32 %x, 0
 578   br i1 %cmp1, label %if, label %else
 579
 580 if:
 581   %cmp2 = icmp sgt i32 %x, 10
 582   br i1 %cmp2, label %if.if, label %if.else
 583
 584 if.if:
 585   br label %if.then
 586
 587 if.else:
 588   br label %if.then
 589
 590 ; CHECK-LABEL: if.then:
 591 ; CHECK-DISABLED: %phi1 = phi i32 [ 0, %if.if ], [ 1, %if.else ]
 592 if.then:
 593   %phi1 = phi i32 [ 0, %if.if ], [ 1, %if.else ]
 594   br label %then
 595
 596 else:
 597   %cmp3 = icmp slt i32 %x, -10
 598   br i1 %cmp3, label %else.if, label %else.else
 599
 600 else.if:
 601   br label %else.then
 602
 603 else.else:
 604   br label %else.then
 605
 606 ; CHECK-LABEL: else.then:
 607 ; CHECK-DISABLED: %phi2 = phi i32 [ 2, %else.if ], [ 3, %else.else ]
 608 else.then:
 609   %phi2 = phi i32 [ 2, %else.if ], [ 3, %else.else ]
 610   br label %then
 611
 612 ; CHECK-LABEL: then:
 613 ; CHECK: %phi3 = phi i32 [ %phi1, %if.then ], [ %phi2, %else.then ]
 614 ; CHECK: %cmp4 = icmp ne i32 %phi3, 0
 615 then:
 616   %phi3 = phi i32 [ %phi1, %if.then ], [ %phi2, %else.then ]
 617   store i32 %phi3, i32* %p
 618   %cmp4 = icmp ne i32 %phi3, 0
 619   br i1 %cmp4, label %loop, label %end
 620
 621 end:
 622   ret void
 623 }
 624
 625 ; We can hoist blocks that contain an edge that exits the loop by ignoring that
 626 ; edge in the hoisted block.
 627 ; CHECK-LABEL: @triangle_phi_loopexit
 628 define void @triangle_phi_loopexit(i32 %x, i32* %p) {
 629 ; CHECK-LABEL: entry:
 630 ; CHECK-DAG: %add = add i32 %x, 1
 631 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 632 ; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
 633 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 634 entry:
 635   br label %loop
 636
 637 ; CHECK-ENABLED: [[IF_LICM]]:
 638 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 639
 640 ; CHECK-ENABLED: [[THEN_LICM]]:
 641 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %x, %entry ]
 642 ; CHECK: br label %loop
 643
 644 loop:
 645   %cmp1 = icmp sgt i32 %x, 0
 646   br i1 %cmp1, label %if, label %then
 647
 648 if:
 649   %add = add i32 %x, 1
 650   %cmp2 = icmp sgt i32 10, %add
 651   br i1 %cmp2, label %then, label %end
 652
 653 ; CHECK-LABEL: then:
 654 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %x, %loop ]
 655 then:
 656   %phi = phi i32 [ %add, %if ], [ %x, %loop ]
 657   store i32 %phi, i32* %p
 658   %cmp3 = icmp ne i32 %phi, 0
 659   br i1 %cmp3, label %loop, label %end
 660
 661 end:
 662   ret void
 663 }
 664
 665 ; CHECK-LABEL: @diamond_phi_oneloopexit
 666 define void @diamond_phi_oneloopexit(i32 %x, i32* %p) {
 667 ; CHECK-LABEL: entry:
 668 ; CHECK-DAG: %add = add i32 %x, 1
 669 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 670 ; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
 671 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 672 entry:
 673   br label %loop
 674
 675 ; CHECK-ENABLED: [[IF_LICM]]:
 676 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 677
 678 ; CHECK-ENABLED: [[ELSE_LICM]]:
 679 ; CHECK-DAG: %sub = sub i32 %x, 1
 680 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 681
 682 ; CHECK-ENABLED: [[THEN_LICM]]
 683 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %sub, %[[ELSE_LICM]] ]
 684 ; CHECK-ENABLED: %cmp3 = icmp ne i32 %phi, 0
 685 ; CHECK: br label %loop
 686
 687 loop:
 688   %cmp1 = icmp sgt i32 %x, 0
 689   br i1 %cmp1, label %if, label %else
 690
 691 if:
 692   %add = add i32 %x, 1
 693   %cmp2 = icmp sgt i32 10, %add
 694   br i1 %cmp2, label %then, label %end
 695
 696 else:
 697   %sub = sub i32 %x, 1
 698   br label %then
 699
 700 ; CHECK-LABEL: then:
 701 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 702 then:
 703   %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 704   store i32 %phi, i32* %p
 705   %cmp3 = icmp ne i32 %phi, 0
 706   br i1 %cmp3, label %loop, label %end
 707
 708 end:
 709   ret void
 710 }
 711
 712 ; CHECK-LABEL: @diamond_phi_twoloopexit
 713 define void @diamond_phi_twoloopexit(i32 %x, i32* %p) {
 714 ; CHECK-LABEL: entry:
 715 ; CHECK-DAG: %sub = sub i32 %x, 1
 716 ; CHECK-DAG: %add = add i32 %x, 1
 717 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 718 ; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
 719 ; CHECK-DAG: %cmp3 = icmp sgt i32 10, %sub
 720 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 721 entry:
 722   br label %loop
 723
 724 ; CHECK-ENABLED: [[IF_LICM]]:
 725 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 726
 727 ; CHECK-ENABLED: [[ELSE_LICM]]:
 728 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 729
 730 ; CHECK-ENABLED: [[THEN_LICM]]
 731 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %sub, %[[ELSE_LICM]] ]
 732 ; CHECK-ENABLED: %cmp4 = icmp ne i32 %phi, 0
 733 ; CHECK: br label %loop
 734
 735 loop:
 736   %cmp1 = icmp sgt i32 %x, 0
 737   br i1 %cmp1, label %if, label %else
 738
 739 if:
 740   %add = add i32 %x, 1
 741   %cmp2 = icmp sgt i32 10, %add
 742   br i1 %cmp2, label %then, label %end
 743
 744 else:
 745   %sub = sub i32 %x, 1
 746   %cmp3 = icmp sgt i32 10, %sub
 747   br i1 %cmp3, label %then, label %end
 748
 749 ; CHECK-LABEL: then:
 750 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 751 ; CHECK-DISABLED: %cmp4 = icmp ne i32 %phi, 0
 752 then:
 753   %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 754   store i32 %phi, i32* %p
 755   %cmp4 = icmp ne i32 %phi, 0
 756   br i1 %cmp4, label %loop, label %end
 757
 758 end:
 759   ret void
 760 }
 761
 762 ; The store cannot be hoisted, so add and shr cannot be hoisted into a
 763 ; conditional block.
 764 ; CHECK-LABEL: @conditional_use
 765 define void @conditional_use(i32 %x, i32* %p) {
 766 ; CHECK-LABEL: entry:
 767 ; CHECK-DAG: %cond = icmp ugt i32 %x, 0
 768 ; CHECK-DAG: %add = add i32 %x, 5
 769 ; CHECK-DAG: %shr = ashr i32 %add, 1
 770 ; CHECK: br label %loop
 771 entry:
 772   br label %loop
 773
 774 loop:
 775   %cond = icmp ugt i32 %x, 0
 776   br i1 %cond, label %if, label %else
 777
 778 ; CHECK-LABEL: if:
 779 ; CHECK: store i32 %shr, i32* %p, align 4
 780 if:
 781   %add = add i32 %x, 5
 782   %shr = ashr i32 %add, 1
 783   store i32 %shr, i32* %p, align 4
 784   br label %then
 785
 786 else:
 787   br label %then
 788
 789 then:
 790   br label %loop
 791 }
 792
 793 ; A diamond with two triangles on the left and one on the right. This test is
 794 ; to check that we have a unique loop preheader when we hoist the store (and so
 795 ; don't fail an assertion).
 796 ; CHECK-LABEL: @triangles_in_diamond
 797 define void @triangles_in_diamond(i32* %ptr) {
 798 ; CHECK-LABEL: entry:
 799 ; CHECK: store i32 0, i32* %ptr, align 4
 800 ; CHECK: br label %loop
 801 entry:
 802   br label %loop
 803
 804 loop:
 805   br i1 undef, label %left_triangle_1, label %right_triangle
 806
 807 left_triangle_1:
 808   br i1 undef, label %left_triangle_1_if, label %left_triangle_2
 809
 810 left_triangle_1_if:
 811   br label %left_triangle_2
 812
 813 left_triangle_2:
 814   br i1 undef, label %left_triangle_2_if, label %left_triangle_2_then
 815
 816 left_triangle_2_if:
 817   br label %left_triangle_2_then
 818
 819 left_triangle_2_then:
 820   br label %loop.end
 821
 822 right_triangle:
 823   br i1 undef, label %right_triangle.if, label %right_triangle.then
 824
 825 right_triangle.if:
 826   br label %right_triangle.then
 827
 828 right_triangle.then:
 829   br label %loop.end
 830
 831 loop.end:
 832   store i32 0, i32* %ptr, align 4
 833   br label %loop
 834 }
 835
 836 ; %cmp dominates its used after being hoisted, but not after %brmerge is rehoisted
 837 ; CHECK-LABEL: @rehoist
 838 define void @rehoist(i8* %this, i32 %x) {
 839 ; CHECK-LABEL: entry:
 840 ; CHECK-DAG: %sub = add nsw i32 %x, -1
 841 ; CHECK-DAG: %fptr = bitcast i8* %this to void (i8*)*
 842 ; CHECK-DAG: %cmp = icmp eq i32 0, %sub
 843 ; CHECK-DAG: %brmerge = or i1 %cmp, true
 844 entry:
 845   %sub = add nsw i32 %x, -1
 846   br label %loop
 847
 848 loop:
 849   br i1 undef, label %if1, label %else1
 850
 851 if1:
 852   %fptr = bitcast i8* %this to void (i8*)*
 853   call void %fptr(i8* %this)
 854   br label %then1
 855
 856 else1:
 857   br label %then1
 858
 859 then1:
 860   %cmp = icmp eq i32 0, %sub
 861   br i1 %cmp, label %end, label %else2
 862
 863 else2:
 864   %brmerge = or i1 %cmp, true
 865   br i1 %brmerge, label %if3, label %end
 866
 867 if3:
 868   br label %end
 869
 870 end:
 871   br label %loop
 872 }
 873
 874 ; A test case that uses empty blocks in a way that can cause control flow
 875 ; hoisting to get confused.
 876 ; CHECK-LABEL: @empty_blocks_multiple_conditional_branches
 877 define void @empty_blocks_multiple_conditional_branches(float %arg, float* %ptr) {
 878 ; CHECK-LABEL: entry
 879 ; CHECK-DAG: %div1 = fmul float %arg, 4.000000e+00
 880 ; CHECK-DAG: %div2 = fmul float %arg, 2.000000e+00
 881 entry:
 882   br label %loop
 883
 884 ; The exact path to the phi isn't checked here, because it depends on whether
 885 ; cond2 or cond3 is hoisted first
 886 ; CHECK-ENABLED: %phi = phi float [ 0.000000e+00, %{{.*}} ], [ %div1, %{{.*}} ]
 887 ; CHECK: br label %loop
 888
 889 loop:
 890   br i1 undef, label %backedge2, label %cond1
 891
 892 cond1:
 893   br i1 undef, label %cond1.if, label %cond1.else
 894
 895 cond1.else:
 896   br label %cond3
 897
 898 cond1.if:
 899   br label %cond1.if.next
 900
 901 cond1.if.next:
 902   br label %cond2
 903
 904 cond2:
 905   %div1 = fmul float %arg, 4.000000e+00
 906   br i1 undef, label %cond2.if, label %cond2.then
 907
 908 cond2.if:
 909   br label %cond2.then
 910
 911 ; CHECK-LABEL: cond2.then:
 912 ; CHECK-DISABLED: %phi = phi float [ 0.000000e+00, %cond2 ], [ %div1, %cond2.if ]
 913 cond2.then:
 914   %phi = phi float [ 0.000000e+00, %cond2 ], [ %div1, %cond2.if ]
 915   store float %phi, float* %ptr
 916   br label %backedge2
 917
 918 cond3:
 919   br i1 undef, label %cond3.then, label %cond3.if
 920
 921 cond3.if:
 922   %div2 = fmul float %arg, 2.000000e+00
 923   store float %div2, float* %ptr
 924   br label %cond3.then
 925
 926 cond3.then:
 927   br label %loop
 928
 929 backedge2:
 930   br label %loop
 931 }
 932
 933 ; We can't do much here, so mainly just check that we don't crash.
 934 ; CHECK-LABEL: @many_path_phi
 935 define void @many_path_phi(i32* %ptr1, i32* %ptr2) {
 936 ; CHECK-LABEL: entry:
 937 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, i32* %ptr2, i32 2
 938 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr2, i32 2
 939 ; CHECK: br label %loop
 940 entry:
 941   br label %loop
 942
 943 loop:
 944   %phi1 = phi i32 [ 0, %entry ], [ %phi2, %end ]
 945   %cmp1 = icmp ugt i32 %phi1, 3
 946   br i1 %cmp1, label %cond2, label %cond1
 947
 948 cond1:
 949   br i1 undef, label %end, label %cond1.else
 950
 951 cond1.else:
 952   %gep2 = getelementptr inbounds i32, i32* %ptr2, i32 2
 953   %val2 = load i32, i32* %gep2, align 4
 954   %cmp2 = icmp eq i32 %val2, 13
 955   br i1 %cmp2, label %cond1.end, label %end
 956
 957 cond1.end:
 958   br label %end
 959
 960 cond2:
 961   br i1 undef, label %end, label %cond2.else
 962
 963 cond2.else:
 964   %gep3 = getelementptr inbounds i32, i32* %ptr2, i32 2
 965   %val3 = load i32, i32* %gep3, align 4
 966   %cmp3 = icmp eq i32 %val3, 13
 967   br i1 %cmp3, label %cond2.end, label %end
 968
 969 cond2.end:
 970   br label %end
 971
 972 end:
 973   %phi2 = phi i32 [ 1, %cond1 ], [ 2, %cond1.else ], [ 3, %cond1.end ], [ 4, %cond2 ], [ 5, %cond2.else ], [ 6, %cond2.end ]
 974   br label %loop
 975 }
 976
 977 ; Check that we correctly handle the hoisting of %gep when theres a critical
 978 ; edge that branches to the preheader.
 979 ; CHECK-LABEL: @crit_edge
 980 define void @crit_edge(i32* %ptr, i32 %idx, i1 %cond1, i1 %cond2) {
 981 ; CHECK-LABEL: entry:
 982 ; CHECK: %gep = getelementptr inbounds i32, i32* %ptr, i32 %idx
 983 ; CHECK: br label %preheader
 984 entry:
 985   br label %preheader
 986
 987 preheader:
 988   br label %loop
 989
 990 loop:
 991   br i1 %cond1, label %then, label %if
 992
 993 if:
 994   %gep = getelementptr inbounds i32, i32* %ptr, i32 %idx
 995   %val = load i32, i32* %gep
 996   br label %then
 997
 998 then:
 999   %phi = phi i32 [ %val, %if ], [ 0, %loop ]
1000   store i32 %phi, i32* %ptr
1001   br i1 %cond2, label %loop, label %crit_edge
1002
1003 crit_edge:
1004   br label %preheader
1005 }
1006
1007 ; Check that the conditional sub is correctly hoisted from the inner loop to the
1008 ; preheader of the outer loop.
1009 ; CHECK-LABEL: @hoist_from_innermost_loop
1010 define void @hoist_from_innermost_loop(i32 %nx, i32* %ptr) {
1011 ; CHECK-LABEL: entry:
1012 ; CHECK-DAG: %sub = sub nsw i32 0, %nx
1013 ; CHECK: br label %outer_loop
1014 entry:
1015   br label %outer_loop
1016
1017 outer_loop:
1018   br label %middle_loop
1019
1020 middle_loop:
1021   br label %inner_loop
1022
1023 inner_loop:
1024   br i1 undef, label %inner_loop_end, label %if
1025
1026 if:
1027   %sub = sub nsw i32 0, %nx
1028   store i32 %sub, i32* %ptr, align 4
1029   br label %inner_loop_end
1030
1031 inner_loop_end:
1032   br i1 undef, label %inner_loop, label %middle_loop_end
1033
1034 middle_loop_end:
1035   br i1 undef, label %middle_loop, label %outer_loop_end
1036
1037 outer_loop_end:
1038   br label %outer_loop
1039 }
1040
1041 ; We have a diamond starting from %if, but %if.if is also reachable from %loop,
1042 ; so %gep should not be conditionally hoisted.
1043 ; CHECK-LABEL: @diamond_with_extra_in_edge
1044 define void @diamond_with_extra_in_edge(i32* %ptr1, i32* %ptr2, i32 %arg) {
1045 ; CHECK-LABEL: entry:
1046 ; CHECK-DAG: %cmp2 = icmp ne i32 0, %arg
1047 ; CHECK-DAG: %gep = getelementptr i32, i32* %ptr1, i32 4
1048 ; CHECK: br label %loop
1049 entry:
1050   br label %loop
1051
1052 loop:
1053   %phi1 = phi i32 [ 0, %entry ], [ %phi2, %then ]
1054   %cmp1 = icmp ugt i32 16, %phi1
1055   br i1 %cmp1, label %if, label %if.if
1056
1057 if:
1058   %cmp2 = icmp ne i32 0, %arg
1059   br i1 %cmp2, label %if.if, label %if.else
1060
1061 if.if:
1062   %gep = getelementptr i32, i32* %ptr1, i32 4
1063   %val = load i32, i32* %gep, align 4
1064   br label %then
1065
1066 if.else:
1067   br label %then
1068
1069 then:
1070   %phi2 = phi i32 [ %val, %if.if ], [ %phi1, %if.else ]
1071   store i32 %phi2, i32* %ptr2, align 4
1072   br label %loop
1073 }
1074
1075 ; %loop/%if/%then form a triangle, but %loop/%if/%then/%end also form a diamond.
1076 ; The triangle should be picked for conditional hoisting.
1077 ; CHECK-LABEL: @both_triangle_and_diamond
1078 define void @both_triangle_and_diamond(i32* %ptr1, i32* %ptr2, i32 %arg) {
1079 ; CHECK-LABEL: entry:
1080 ; CHECK-DAG: %cmp1 = icmp ne i32 0, %arg
1081 ; CHECK-DAG: %gep = getelementptr i32, i32* %ptr1, i32 4
1082 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
1083 entry:
1084   br label %loop
1085
1086 ; CHECK-ENABLED: [[IF_LICM]]:
1087 ; CHECK-ENABLED: br label %[[THEN_LICM]]
1088
1089 ; CHECK-ENABLED: [[THEN_LICM]]:
1090 ; CHECK-ENABLED: %phi2 = phi i32 [ 0, %[[IF_LICM]] ], [ 1, %entry ]
1091 ; CHECK: br label %loop
1092
1093 loop:
1094   %phi1 = phi i32 [ 0, %entry ], [ %phi3, %end ]
1095   %cmp1 = icmp ne i32 0, %arg
1096   br i1 %cmp1, label %if, label %then
1097
1098 if:
1099   %gep = getelementptr i32, i32* %ptr1, i32 4
1100   %val = load i32, i32* %gep, align 4
1101   %cmp2 = icmp ugt i32 16, %phi1
1102   br i1 %cmp2, label %end, label %then
1103
1104 ; CHECK-LABEL: then:
1105 ; CHECK-DISABLED: %phi2 = phi i32 [ 0, %if ], [ 1, %loop ]
1106 then:
1107   %phi2 = phi i32 [ 0, %if ], [ 1, %loop ]
1108   br label %end
1109
1110 end:
1111   %phi3 = phi i32 [ %phi2, %then ], [ %val, %if ]
1112   store i32 %phi3, i32* %ptr2, align 4
1113   br label %loop
1114 }
1115
1116 ; We shouldn't duplicate the branch at the end of %loop and should instead hoist
1117 ; %val to %entry.
1118 ; CHECK-LABEL: @same_destination_branch
1119 define i32 @same_destination_branch(i32 %arg1, i32 %arg2) {
1120 ; CHECK-LABEL: entry:
1121 ; CHECK-DAG: %cmp1 = icmp ne i32 %arg2, 0
1122 ; CHECK-DAG: %val = add i32 %arg1, 1
1123 ; CHECK: br label %loop
1124 entry:
1125   br label %loop
1126
1127 ; CHECK-LABEL: loop:
1128 ; CHECK: %phi = phi i32 [ 0, %entry ], [ %add, %then ]
1129 loop:
1130   %phi = phi i32 [ 0, %entry ], [ %add, %then ]
1131   %add = add i32 %phi, 1
1132   %cmp1 = icmp ne i32 %arg2, 0
1133   br i1 %cmp1, label %if, label %if
1134
1135 if:
1136   %val = add i32 %arg1, 1
1137   br label %then
1138
1139 then:
1140   %cmp2 = icmp ne i32 %val, %phi
1141   br i1 %cmp2, label %loop, label %end
1142
1143 end:
1144   ret i32 %val
1145 }
1146
1147 ; Diamond-like control flow but the left/right blocks actually have the same
1148 ; destinations.
1149 ; TODO: We could potentially hoist all of phi2-4, but currently only hoist phi2.
1150 ; CHECK-LABEL: @diamond_like_same_destinations
1151 define i32 @diamond_like_same_destinations(i32 %arg1, i32 %arg2) {
1152 ; CHECK-LABEL: entry:
1153 ; CHECK-DAG: %cmp1 = icmp ne i32 %arg1, 0
1154 ; CHECK-DAG: %cmp2 = icmp ugt i32 %arg2, 1
1155 ; CHECK-DAG: %cmp3 = icmp ugt i32 %arg2, 2
1156 ; CHECK-ENABLED: br i1 %cmp1, label %[[LEFT1_LICM:.*]], label %[[RIGHT1_LICM:.*]]
1157 entry:
1158   br label %loop
1159
1160 ; CHECK-ENABLED: [[LEFT1_LICM]]:
1161 ; CHECK-ENABLED: br label %[[LEFT2_LICM:.*]]
1162
1163 ; CHECK-ENABLED: [[RIGHT1_LICM]]:
1164 ; CHECK-ENABLED: br label %[[LEFT2_LICM]]
1165
1166 ; CHECK-ENABLED: [[LEFT2_LICM]]:
1167 ; CHECK-ENABLED: %phi2 = phi i32 [ 0, %[[LEFT1_LICM]] ], [ 1, %[[RIGHT1_LICM]] ]
1168 ; CHECK: br label %loop
1169
1170 loop:
1171   %phi1 = phi i32 [ 0, %entry ], [ %add, %loopend ]
1172   %add = add i32 %phi1, 1
1173   %cmp1 = icmp ne i32 %arg1, 0
1174   br i1 %cmp1, label %left1, label %right1
1175
1176 left1:
1177   %cmp2 = icmp ugt i32 %arg2, 1
1178   br i1 %cmp2, label %left2, label %right2
1179
1180 right1:
1181   %cmp3 = icmp ugt i32 %arg2, 2
1182   br i1 %cmp3, label %left2, label %right2
1183
1184 ; CHECK-LABEL: left2:
1185 ; CHECK-DISABLED: %phi2 = phi i32 [ 0, %left1 ], [ 1, %right1 ]
1186 left2:
1187   %phi2 = phi i32 [ 0, %left1 ], [ 1, %right1 ]
1188   br label %loopend
1189
1190 ; CHECK-LABEL: right2:
1191 ; CHECK: %phi3 = phi i32 [ 2, %left1 ], [ 3, %right1 ]
1192 right2:
1193   %phi3 = phi i32 [ 2, %left1 ], [ 3, %right1 ]
1194   br label %loopend
1195
1196 ; CHECK-LABEL: loopend:
1197 ; CHECK: %phi4 = phi i32 [ %phi2, %left2 ], [ %phi3, %right2 ]
1198 loopend:
1199   %phi4 = phi i32 [ %phi2, %left2 ], [ %phi3, %right2 ]
1200   %cmp4 = icmp ne i32 %phi1, 32
1201   br i1 %cmp4, label %loop, label %end
1202
1203 end:
1204   ret i32 %phi4
1205 }
1206
1207 ; A phi with multiple incoming values for the same block due to a branch with
1208 ; two destinations that are actually the same. We can't hoist this.
1209 ; TODO: This could be hoisted by erasing one of the incoming values.
1210 ; CHECK-LABEL: @phi_multiple_values_same_block
1211 define i32 @phi_multiple_values_same_block(i32 %arg) {
1212 ; CHECK-LABEL: entry:
1213 ; CHECK: %cmp = icmp sgt i32 %arg, 4
1214 ; CHECK-NOT: phi
1215 ; CHECK: br label %loop
1216 entry:
1217   br label %loop
1218
1219 loop:
1220   %cmp = icmp sgt i32 %arg, 4
1221   br i1 %cmp, label %if, label %then
1222
1223 if:
1224   br i1 undef, label %then, label %then
1225
1226 then:
1227   %phi = phi i32 [ %arg, %loop ], [ 1, %if ], [ 1, %if ]
1228   br i1 undef, label %exit, label %loop
1229
1230 exit:
1231   ret i32 %phi
1232 }
1233
1234 ; %phi is conditionally used in %d, and the store that %d is used in cannot be
1235 ; hoisted. This means that we have to rehoist %d, but have to make sure to
1236 ; rehoist it after %phi.
1237 ; CHECK-LABEL: @phi_conditional_use
1238 define i64 @phi_conditional_use(i32 %f, i32* %g) {
1239 ; CHECK-LABEL: entry:
1240 ; CHECK: %cmp1 = icmp eq i32 %f, 1
1241 ; CHECK: %cmp2 = icmp eq i32 %f, 0
1242 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_END_LICM:.*]], label %[[IF_THEN_LICM:.*]]
1243 entry:
1244   %cmp1 = icmp eq i32 %f, 1
1245   %cmp2 = icmp eq i32 %f, 0
1246   br label %loop
1247
1248 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
1249 ; CHECK-ENABLED: br label %[[IF_END_LICM]]
1250
1251 ; CHECK-ENABLED: [[IF_END_LICM]]:
1252 ; CHECK-ENABLED: %phi = phi i64 [ 0, %entry ], [ 1, %[[IF_THEN_LICM]] ]
1253 ; CHECK-ENABLED: %d = getelementptr inbounds i32, i32* %g, i64 %phi
1254 ; CHECK-ENABLED: i1 %cmp2, label %[[LOOP_BACKEDGE_LICM:.*]], label %[[IF_THEN2_LICM:.*]]
1255
1256 ; CHECK-ENABLED: [[IF_THEN2_LICM]]:
1257 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1258
1259 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1260 ; CHECK: br label %loop
1261
1262 loop:
1263   br i1 %cmp1, label %if.end, label %if.then
1264
1265 if.then:
1266   br label %if.end
1267
1268 ; CHECK-LABEL: if.end:
1269 ; CHECK-DISABLED: %phi = phi i64 [ 0, %loop ], [ 1, %if.then ]
1270 if.end:
1271   %phi = phi i64 [ 0, %loop ], [ 1, %if.then ]
1272   br i1 %cmp2, label %loop.backedge, label %if.then2
1273
1274 ; CHECK-LABEL: if.then2:
1275 ; CHECK-DISABLED: %d = getelementptr inbounds i32, i32* %g, i64 %phi
1276 if.then2:
1277   %d = getelementptr inbounds i32, i32* %g, i64 %phi
1278   store i32 1, i32* %d, align 4
1279   br label %loop.backedge
1280
1281 loop.backedge:
1282   br label %loop
1283 }
1284
1285 ; As above, but we have two such phis
1286 ; CHECK-LABEL: @phi_conditional_use_twice
1287 define i64 @phi_conditional_use_twice(i32 %f, i32* %g) {
1288 ; CHECK-LABEL: entry:
1289 ; CHECK: %cmp1 = icmp eq i32 %f, 1
1290 ; CHECK: %cmp2 = icmp eq i32 %f, 0
1291 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_END_LICM:.*]], label %[[IF_THEN_LICM:.*]]
1292 entry:
1293   %cmp1 = icmp eq i32 %f, 1
1294   %cmp2 = icmp eq i32 %f, 0
1295   %cmp3 = icmp sgt i32 %f, 0
1296   br label %loop
1297
1298 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
1299 ; CHECK-ENABLED: br label %[[IF_END_LICM]]
1300
1301 ; CHECK-ENABLED: [[IF_END_LICM]]:
1302 ; CHECK-ENABLED: %phi1 = phi i64 [ 0, %entry ], [ 1, %[[IF_THEN_LICM]] ]
1303 ; CHECK-ENABLED: %d = getelementptr inbounds i32, i32* %g, i64 %phi1
1304 ; CHECK-ENABLED: i1 %cmp2, label %[[IF_END2_LICM:.*]], label %[[IF_THEN2_LICM:.*]]
1305
1306 ; CHECK-ENABLED: [[IF_THEN2_LICM]]:
1307 ; CHECK-ENABLED: br label %[[IF_END2_LICM]]
1308
1309 ; CHECK-ENABLED: [[IF_END2_LICM]]:
1310 ; CHECK-ENABLED: %phi2 = phi i64 [ 2, %[[IF_END_LICM]] ], [ 3, %[[IF_THEN2_LICM]] ]
1311 ; CHECK-ENABLED: %e = getelementptr inbounds i32, i32* %g, i64 %phi2
1312 ; CHECK-ENABLED: i1 %cmp3, label %[[LOOP_BACKEDGE_LICM:.*]], label %[[IF_THEN3_LICM:.*]]
1313
1314 ; CHECK-ENABLED: [[IF_THEN3_LICM]]:
1315 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1316
1317 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1318 ; CHECK: br label %loop
1319
1320 loop:
1321   br i1 %cmp1, label %if.end, label %if.then
1322
1323 if.then:
1324   br label %if.end
1325
1326 ; CHECK-LABEL: if.end:
1327 ; CHECK-DISABLED: %phi1 = phi i64 [ 0, %loop ], [ 1, %if.then ]
1328 if.end:
1329   %phi1 = phi i64 [ 0, %loop ], [ 1, %if.then ]
1330   br i1 %cmp2, label %if.end2, label %if.then2
1331
1332 ; CHECK-LABEL: if.then2:
1333 ; CHECK-DISABLED: %d = getelementptr inbounds i32, i32* %g, i64 %phi1
1334 if.then2:
1335   %d = getelementptr inbounds i32, i32* %g, i64 %phi1
1336   store i32 1, i32* %d, align 4
1337   br label %if.end2
1338
1339 ; CHECK-LABEL: if.end2:
1340 ; CHECK-DISABLED: %phi2 = phi i64 [ 2, %if.end ], [ 3, %if.then2 ]
1341 if.end2:
1342   %phi2 = phi i64 [ 2, %if.end ], [ 3, %if.then2 ]
1343   br i1 %cmp3, label %loop.backedge, label %if.then3
1344
1345 ; CHECK-LABEL: if.then3:
1346 ; CHECK-DISABLED: %e = getelementptr inbounds i32, i32* %g, i64 %phi2
1347 if.then3:
1348   %e = getelementptr inbounds i32, i32* %g, i64 %phi2
1349   store i32 1, i32* %e, align 4
1350   br label %loop.backedge
1351
1352 loop.backedge:
1353   br label %loop
1354 }
1355
1356 ; The order that we hoist instructions from the loop is different to the textual
1357 ; order in the function. Check that we can rehoist this correctly.
1358 ; CHECK-LABEL: @rehoist_wrong_order_1
1359 define void @rehoist_wrong_order_1(i32* %ptr) {
1360 ; CHECK-LABEL: entry
1361 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1362 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
1363 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1364 ; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1365 entry:
1366   br label %loop
1367
1368 ; CHECK-ENABLED: [[IF1_LICM]]:
1369 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
1370
1371 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1372 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1373
1374 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1375 ; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1376
1377 ; CHECK-ENABLED: [[IF3_LICM]]:
1378 ; CHECK-ENABLED: br label %[[END_LICM]]
1379
1380 ; CHECK-ENABLED: [[END_LICM]]:
1381 ; CHECK: br label %loop
1382
1383 loop:
1384   br i1 undef, label %if1, label %else1
1385
1386 if1:
1387   %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1388   store i32 0, i32* %gep1, align 4
1389   br label %loop.backedge
1390
1391 else1:
1392   %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1393   store i32 0, i32* %gep2, align 4
1394   br i1 undef, label %if2, label %loop.backedge
1395
1396 if2:
1397   br i1 undef, label %if3, label %end
1398
1399 if3:
1400   %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
1401   store i32 0, i32* %gep3, align 4
1402   br label %end
1403
1404 end:
1405   br label %loop.backedge
1406
1407 loop.backedge:
1408   br label %loop
1409
1410 }
1411
1412 ; CHECK-LABEL: @rehoist_wrong_order_2
1413 define void @rehoist_wrong_order_2(i32* %ptr) {
1414 ; CHECK-LABEL: entry
1415 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1416 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, i32* %gep2, i64 3
1417 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1418 ; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1419 entry:
1420   br label %loop
1421
1422 ; CHECK-ENABLED: [[IF1_LICM]]:
1423 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
1424
1425 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1426 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1427
1428 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1429 ; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1430
1431 ; CHECK-ENABLED: [[IF3_LICM]]:
1432 ; CHECK-ENABLED: br label %[[END_LICM]]
1433
1434 ; CHECK-ENABLED: [[END_LICM]]:
1435 ; CHECK: br label %loop
1436
1437 loop:
1438   br i1 undef, label %if1, label %else1
1439
1440 if1:
1441   %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1442   store i32 0, i32* %gep1, align 4
1443   br label %loop.backedge
1444
1445 else1:
1446   %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1447   store i32 0, i32* %gep2, align 4
1448   br i1 undef, label %if2, label %loop.backedge
1449
1450 if2:
1451   br i1 undef, label %if3, label %end
1452
1453 if3:
1454   %gep3 = getelementptr inbounds i32, i32* %gep2, i64 3
1455   store i32 0, i32* %gep3, align 4
1456   br label %end
1457
1458 end:
1459   br label %loop.backedge
1460
1461 loop.backedge:
1462   br label %loop
1463 }
1464
1465 ; CHECK-LABEL: @rehoist_wrong_order_3
1466 define void @rehoist_wrong_order_3(i32* %ptr) {
1467 ; CHECK-LABEL: entry
1468 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1469 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1470 ; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1471 entry:
1472   br label %loop
1473
1474 ; CHECK-ENABLED: [[IF1_LICM]]:
1475 ; CHECK-ENABLED: br label %[[IF2_LICM:.*]]
1476
1477 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1478 ; CHECK-ENABLED: br label %[[IF2_LICM]]
1479
1480 ; CHECK-ENABLED: [[IF2_LICM]]:
1481 ; CHECK-ENABLED: %phi = phi i32* [ %gep1, %[[IF1_LICM]] ], [ %gep2, %[[ELSE1_LICM]] ]
1482 ; CHECK-ENABLED: %gep3 = getelementptr inbounds i32, i32* %phi, i64 3
1483 ; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1484
1485 ; CHECK-ENABLED: [[IF3_LICM]]:
1486 ; CHECK-ENABLED: br label %[[END_LICM]]
1487
1488 ; CHECK-ENABLED: [[END_LICM]]:
1489 ; CHECK: br label %loop
1490
1491 loop:
1492   br i1 undef, label %if1, label %else1
1493
1494 if1:
1495   %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
1496   store i32 0, i32* %gep1, align 4
1497   br label %if2
1498
1499 else1:
1500   %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
1501   store i32 0, i32* %gep2, align 4
1502   br i1 undef, label %if2, label %loop.backedge
1503
1504 if2:
1505   %phi = phi i32* [ %gep1, %if1 ], [ %gep2, %else1 ]
1506   br i1 undef, label %if3, label %end
1507
1508 if3:
1509   %gep3 = getelementptr inbounds i32, i32* %phi, i64 3
1510   store i32 0, i32* %gep3, align 4
1511   br label %end
1512
1513 end:
1514   br label %loop.backedge
1515
1516 loop.backedge:
1517   br label %loop
1518 }