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

   1 ; RUN: opt -S -passes=licm < %s | FileCheck %s -check-prefixes=CHECK,CHECK-DISABLED
   2 ; RUN: opt -S -passes=licm -licm-control-flow-hoisting=1 < %s | FileCheck %s -check-prefixes=CHECK,CHECK-ENABLED
   3 ; RUN: opt -S -passes=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, ptr %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, ptr %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, ptr %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, ptr %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]], ptr %p
  49 end:
  50   ret void
  51 }
  52
  53 ; CHECK-LABEL: @diamond_phi
  54 define void @diamond_phi(i32 %x, ptr %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, ptr %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, ptr %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]], ptr %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, ptr %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, ptr %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, ptr %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, ptr %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, ptr %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, ptr %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(ptr %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, ptr %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(ptr %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, ptr %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, ptr %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, ptr %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 define void @triangle_phi_loopexit(i32 %x, ptr %p) {
 628 ; CHECK-DISABLED-LABEL: @triangle_phi_loopexit(
 629 ; CHECK-DISABLED-NEXT:  entry:
 630 ; CHECK-DISABLED-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], 1
 631 ; CHECK-DISABLED-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[X]], 0
 632 ; CHECK-DISABLED-NEXT:    [[CMP2:%.*]] = icmp sgt i32 10, [[ADD]]
 633 ; CHECK-DISABLED-NEXT:    br label [[LOOP:%.*]]
 634 ; CHECK-DISABLED:       loop:
 635 ; CHECK-DISABLED-NEXT:    br i1 [[CMP1]], label [[IF:%.*]], label [[THEN:%.*]]
 636 ; CHECK-DISABLED:       if:
 637 ; CHECK-DISABLED-NEXT:    br i1 [[CMP2]], label [[THEN]], label [[END:%.*]]
 638 ; CHECK-DISABLED:       then:
 639 ; CHECK-DISABLED-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD]], [[IF]] ], [ [[X]], [[LOOP]] ]
 640 ; CHECK-DISABLED-NEXT:    store i32 [[PHI]], ptr [[P:%.*]], align 4
 641 ; CHECK-DISABLED-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[PHI]], 0
 642 ; CHECK-DISABLED-NEXT:    br i1 [[CMP3]], label [[LOOP]], label [[END]]
 643 ; CHECK-DISABLED:       end:
 644 ; CHECK-DISABLED-NEXT:    ret void
 645 ;
 646 ; CHECK-ENABLED-LABEL: @triangle_phi_loopexit(
 647 ; CHECK-ENABLED-NEXT:  entry:
 648 ; CHECK-ENABLED-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], 1
 649 ; CHECK-ENABLED-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[X]], 0
 650 ; CHECK-ENABLED-NEXT:    [[CMP2:%.*]] = icmp sgt i32 10, [[ADD]]
 651 ; CHECK-ENABLED-NEXT:    br i1 [[CMP1]], label [[IF_LICM:%.*]], label [[THEN_LICM:%.*]]
 652 ; CHECK-ENABLED:       if.licm:
 653 ; CHECK-ENABLED-NEXT:    br label [[THEN_LICM]]
 654 ; CHECK-ENABLED:       then.licm:
 655 ; CHECK-ENABLED-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD]], [[IF_LICM]] ], [ [[X]], [[ENTRY:%.*]] ]
 656 ; CHECK-ENABLED-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[PHI]], 0
 657 ; CHECK-ENABLED-NEXT:    br label [[LOOP:%.*]]
 658 ; CHECK-ENABLED:       loop:
 659 ; CHECK-ENABLED-NEXT:    br i1 [[CMP1]], label [[IF:%.*]], label [[THEN:%.*]]
 660 ; CHECK-ENABLED:       if:
 661 ; CHECK-ENABLED-NEXT:    br i1 [[CMP2]], label [[THEN]], label [[END:%.*]]
 662 ; CHECK-ENABLED:       then:
 663 ; CHECK-ENABLED-NEXT:    store i32 [[PHI]], ptr [[P:%.*]], align 4
 664 ; CHECK-ENABLED-NEXT:    br i1 [[CMP3]], label [[LOOP]], label [[END]]
 665 ; CHECK-ENABLED:       end:
 666 ; CHECK-ENABLED-NEXT:    ret void
 667 ;
 668 entry:
 669   br label %loop
 670
 671 loop:
 672   %cmp1 = icmp sgt i32 %x, 0
 673   br i1 %cmp1, label %if, label %then
 674
 675 if:
 676   %add = add i32 %x, 1
 677   %cmp2 = icmp sgt i32 10, %add
 678   br i1 %cmp2, label %then, label %end
 679
 680 then:
 681   %phi = phi i32 [ %add, %if ], [ %x, %loop ]
 682   store i32 %phi, ptr %p
 683   %cmp3 = icmp ne i32 %phi, 0
 684   br i1 %cmp3, label %loop, label %end
 685
 686 end:
 687   ret void
 688 }
 689
 690 ; CHECK-LABEL: @diamond_phi_oneloopexit
 691 define void @diamond_phi_oneloopexit(i32 %x, ptr %p) {
 692 ; CHECK-LABEL: entry:
 693 ; CHECK-DAG: %add = add i32 %x, 1
 694 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 695 ; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
 696 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 697 entry:
 698   br label %loop
 699
 700 ; CHECK-ENABLED: [[IF_LICM]]:
 701 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 702
 703 ; CHECK-ENABLED: [[ELSE_LICM]]:
 704 ; CHECK-DAG: %sub = sub i32 %x, 1
 705 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 706
 707 ; CHECK-ENABLED: [[THEN_LICM]]
 708 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %sub, %[[ELSE_LICM]] ]
 709 ; CHECK-ENABLED: %cmp3 = icmp ne i32 %phi, 0
 710 ; CHECK: br label %loop
 711
 712 loop:
 713   %cmp1 = icmp sgt i32 %x, 0
 714   br i1 %cmp1, label %if, label %else
 715
 716 if:
 717   %add = add i32 %x, 1
 718   %cmp2 = icmp sgt i32 10, %add
 719   br i1 %cmp2, label %then, label %end
 720
 721 else:
 722   %sub = sub i32 %x, 1
 723   br label %then
 724
 725 ; CHECK-LABEL: then:
 726 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 727 then:
 728   %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 729   store i32 %phi, ptr %p
 730   %cmp3 = icmp ne i32 %phi, 0
 731   br i1 %cmp3, label %loop, label %end
 732
 733 end:
 734   ret void
 735 }
 736
 737 ; CHECK-LABEL: @diamond_phi_twoloopexit
 738 define void @diamond_phi_twoloopexit(i32 %x, ptr %p) {
 739 ; CHECK-LABEL: entry:
 740 ; CHECK-DAG: %sub = sub i32 %x, 1
 741 ; CHECK-DAG: %add = add i32 %x, 1
 742 ; CHECK-DAG: %cmp1 = icmp sgt i32 %x, 0
 743 ; CHECK-DAG: %cmp2 = icmp sgt i32 10, %add
 744 ; CHECK-DAG: %cmp3 = icmp sgt i32 10, %sub
 745 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
 746 entry:
 747   br label %loop
 748
 749 ; CHECK-ENABLED: [[IF_LICM]]:
 750 ; CHECK-ENABLED: br label %[[THEN_LICM:.*]]
 751
 752 ; CHECK-ENABLED: [[ELSE_LICM]]:
 753 ; CHECK-ENABLED: br label %[[THEN_LICM]]
 754
 755 ; CHECK-ENABLED: [[THEN_LICM]]
 756 ; CHECK-ENABLED: %phi = phi i32 [ %add, %[[IF_LICM]] ], [ %sub, %[[ELSE_LICM]] ]
 757 ; CHECK-ENABLED: %cmp4 = icmp ne i32 %phi, 0
 758 ; CHECK: br label %loop
 759
 760 loop:
 761   %cmp1 = icmp sgt i32 %x, 0
 762   br i1 %cmp1, label %if, label %else
 763
 764 if:
 765   %add = add i32 %x, 1
 766   %cmp2 = icmp sgt i32 10, %add
 767   br i1 %cmp2, label %then, label %end
 768
 769 else:
 770   %sub = sub i32 %x, 1
 771   %cmp3 = icmp sgt i32 10, %sub
 772   br i1 %cmp3, label %then, label %end
 773
 774 ; CHECK-LABEL: then:
 775 ; CHECK-DISABLED: %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 776 ; CHECK-DISABLED: %cmp4 = icmp ne i32 %phi, 0
 777 then:
 778   %phi = phi i32 [ %add, %if ], [ %sub, %else ]
 779   store i32 %phi, ptr %p
 780   %cmp4 = icmp ne i32 %phi, 0
 781   br i1 %cmp4, label %loop, label %end
 782
 783 end:
 784   ret void
 785 }
 786
 787 ; The store cannot be hoisted, so add and shr cannot be hoisted into a
 788 ; conditional block.
 789 ; CHECK-LABEL: @conditional_use
 790 define void @conditional_use(i32 %x, ptr %p) {
 791 ; CHECK-LABEL: entry:
 792 ; CHECK-DAG: %cond = icmp ugt i32 %x, 0
 793 ; CHECK-DAG: %add = add i32 %x, 5
 794 ; CHECK-DAG: %shr = ashr i32 %add, 1
 795 ; CHECK: br label %loop
 796 entry:
 797   br label %loop
 798
 799 loop:
 800   %cond = icmp ugt i32 %x, 0
 801   br i1 %cond, label %if, label %else
 802
 803 ; CHECK-LABEL: if:
 804 ; CHECK: store i32 %shr, ptr %p, align 4
 805 if:
 806   %add = add i32 %x, 5
 807   %shr = ashr i32 %add, 1
 808   store i32 %shr, ptr %p, align 4
 809   br label %then
 810
 811 else:
 812   br label %then
 813
 814 then:
 815   br label %loop
 816 }
 817
 818 ; A diamond with two triangles on the left and one on the right. This test is
 819 ; to check that we have a unique loop preheader when we hoist the store (and so
 820 ; don't fail an assertion).
 821 ; CHECK-LABEL: @triangles_in_diamond
 822 define void @triangles_in_diamond(ptr %ptr, i1 %arg) {
 823 ; CHECK-LABEL: entry:
 824 ; CHECK: store i32 0, ptr %ptr, align 4
 825 ; CHECK: br label %loop
 826 entry:
 827   br label %loop
 828
 829 loop:
 830   br i1 %arg, label %left_triangle_1, label %right_triangle
 831
 832 left_triangle_1:
 833   br i1 %arg, label %left_triangle_1_if, label %left_triangle_2
 834
 835 left_triangle_1_if:
 836   br label %left_triangle_2
 837
 838 left_triangle_2:
 839   br i1 %arg, label %left_triangle_2_if, label %left_triangle_2_then
 840
 841 left_triangle_2_if:
 842   br label %left_triangle_2_then
 843
 844 left_triangle_2_then:
 845   br label %loop.end
 846
 847 right_triangle:
 848   br i1 %arg, label %right_triangle.if, label %right_triangle.then
 849
 850 right_triangle.if:
 851   br label %right_triangle.then
 852
 853 right_triangle.then:
 854   br label %loop.end
 855
 856 loop.end:
 857   store i32 0, ptr %ptr, align 4
 858   br label %loop
 859 }
 860
 861 ; %cmp dominates its used after being hoisted, but not after %brmerge is rehoisted
 862 ; CHECK-LABEL: @rehoist
 863 define void @rehoist(ptr %this, i32 %x, i1 %arg) {
 864 ; CHECK-LABEL: entry:
 865 ; CHECK-DAG: %sub = add nsw i32 %x, -1
 866 ; CHECK-DAG: %cmp = icmp eq i32 0, %sub
 867 ; CHECK-DAG: %brmerge = or i1 %cmp, true
 868 entry:
 869   %sub = add nsw i32 %x, -1
 870   br label %loop
 871
 872 loop:
 873   br i1 %arg, label %if1, label %else1
 874
 875 if1:
 876   call void %this(ptr %this)
 877   br label %then1
 878
 879 else1:
 880   br label %then1
 881
 882 then1:
 883   %cmp = icmp eq i32 0, %sub
 884   br i1 %cmp, label %end, label %else2
 885
 886 else2:
 887   %brmerge = or i1 %cmp, true
 888   br i1 %brmerge, label %if3, label %end
 889
 890 if3:
 891   br label %end
 892
 893 end:
 894   br label %loop
 895 }
 896
 897 ; A test case that uses empty blocks in a way that can cause control flow
 898 ; hoisting to get confused.
 899 ; CHECK-LABEL: @empty_blocks_multiple_conditional_branches
 900 define void @empty_blocks_multiple_conditional_branches(float %arg, ptr %ptr, i1 %arg2) {
 901 ; CHECK-LABEL: entry
 902 ; CHECK-DAG: %div1 = fmul float %arg, 4.000000e+00
 903 ; CHECK-DAG: %div2 = fmul float %arg, 2.000000e+00
 904 entry:
 905   br label %loop
 906
 907 ; The exact path to the phi isn't checked here, because it depends on whether
 908 ; cond2 or cond3 is hoisted first
 909 ; CHECK-ENABLED: %phi = phi float [ 0.000000e+00, %{{.*}} ], [ %div1, %{{.*}} ]
 910 ; CHECK: br label %loop
 911
 912 loop:
 913   br i1 %arg2, label %backedge2, label %cond1
 914
 915 cond1:
 916   br i1 %arg2, label %cond1.if, label %cond1.else
 917
 918 cond1.else:
 919   br label %cond3
 920
 921 cond1.if:
 922   br label %cond1.if.next
 923
 924 cond1.if.next:
 925   br label %cond2
 926
 927 cond2:
 928   %div1 = fmul float %arg, 4.000000e+00
 929   br i1 %arg2, label %cond2.if, label %cond2.then
 930
 931 cond2.if:
 932   br label %cond2.then
 933
 934 ; CHECK-LABEL: cond2.then:
 935 ; CHECK-DISABLED: %phi = phi float [ 0.000000e+00, %cond2 ], [ %div1, %cond2.if ]
 936 cond2.then:
 937   %phi = phi float [ 0.000000e+00, %cond2 ], [ %div1, %cond2.if ]
 938   store float %phi, ptr %ptr
 939   br label %backedge2
 940
 941 cond3:
 942   br i1 %arg2, label %cond3.then, label %cond3.if
 943
 944 cond3.if:
 945   %div2 = fmul float %arg, 2.000000e+00
 946   store float %div2, ptr %ptr
 947   br label %cond3.then
 948
 949 cond3.then:
 950   br label %loop
 951
 952 backedge2:
 953   br label %loop
 954 }
 955
 956 ; We can't do much here, so mainly just check that we don't crash.
 957 ; CHECK-LABEL: @many_path_phi
 958 define void @many_path_phi(ptr %ptr1, ptr %ptr2, i1 %arg) {
 959 ; CHECK-LABEL: entry:
 960 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, ptr %ptr2, i32 2
 961 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, ptr %ptr2, i32 2
 962 ; CHECK: br label %loop
 963 entry:
 964   br label %loop
 965
 966 loop:
 967   %phi1 = phi i32 [ 0, %entry ], [ %phi2, %end ]
 968   %cmp1 = icmp ugt i32 %phi1, 3
 969   br i1 %cmp1, label %cond2, label %cond1
 970
 971 cond1:
 972   br i1 %arg, label %end, label %cond1.else
 973
 974 cond1.else:
 975   %gep2 = getelementptr inbounds i32, ptr %ptr2, i32 2
 976   %val2 = load i32, ptr %gep2, align 4
 977   %cmp2 = icmp eq i32 %val2, 13
 978   br i1 %cmp2, label %cond1.end, label %end
 979
 980 cond1.end:
 981   br label %end
 982
 983 cond2:
 984   br i1 %arg, label %end, label %cond2.else
 985
 986 cond2.else:
 987   %gep3 = getelementptr inbounds i32, ptr %ptr2, i32 2
 988   %val3 = load i32, ptr %gep3, align 4
 989   %cmp3 = icmp eq i32 %val3, 13
 990   br i1 %cmp3, label %cond2.end, label %end
 991
 992 cond2.end:
 993   br label %end
 994
 995 end:
 996   %phi2 = phi i32 [ 1, %cond1 ], [ 2, %cond1.else ], [ 3, %cond1.end ], [ 4, %cond2 ], [ 5, %cond2.else ], [ 6, %cond2.end ]
 997   br label %loop
 998 }
 999
1000 ; Check that we correctly handle the hoisting of %gep when theres a critical
1001 ; edge that branches to the preheader.
1002 ; CHECK-LABEL: @crit_edge
1003 define void @crit_edge(ptr %ptr, i32 %idx, i1 %cond1, i1 %cond2, i1 %arg) {
1004 ; CHECK-LABEL: entry:
1005 ; CHECK: %gep = getelementptr inbounds i32, ptr %ptr, i32 %idx
1006 ; CHECK: br label %preheader
1007 entry:
1008   br label %preheader
1009
1010 preheader:
1011   br label %loop
1012
1013 loop:
1014   br i1 %cond1, label %then, label %if
1015
1016 if:
1017   %gep = getelementptr inbounds i32, ptr %ptr, i32 %idx
1018   %val = load i32, ptr %gep
1019   br label %then
1020
1021 then:
1022   %phi = phi i32 [ %val, %if ], [ 0, %loop ]
1023   store i32 %phi, ptr %ptr
1024   br i1 %cond2, label %loop, label %crit_edge
1025
1026 crit_edge:
1027   br label %preheader
1028 }
1029
1030 ; Check that the conditional sub is correctly hoisted from the inner loop to the
1031 ; preheader of the outer loop.
1032 ; CHECK-LABEL: @hoist_from_innermost_loop
1033 define void @hoist_from_innermost_loop(i32 %nx, ptr %ptr, i1 %arg) {
1034 ; CHECK-LABEL: entry:
1035 ; CHECK-DAG: %sub = sub nsw i32 0, %nx
1036 ; CHECK: br label %outer_loop
1037 entry:
1038   br label %outer_loop
1039
1040 outer_loop:
1041   br label %middle_loop
1042
1043 middle_loop:
1044   br label %inner_loop
1045
1046 inner_loop:
1047   br i1 %arg, label %inner_loop_end, label %if
1048
1049 if:
1050   %sub = sub nsw i32 0, %nx
1051   store i32 %sub, ptr %ptr, align 4
1052   br label %inner_loop_end
1053
1054 inner_loop_end:
1055   br i1 %arg, label %inner_loop, label %middle_loop_end
1056
1057 middle_loop_end:
1058   br i1 %arg, label %middle_loop, label %outer_loop_end
1059
1060 outer_loop_end:
1061   br label %outer_loop
1062 }
1063
1064 ; We have a diamond starting from %if, but %if.if is also reachable from %loop,
1065 ; so %gep should not be conditionally hoisted.
1066 ; CHECK-LABEL: @diamond_with_extra_in_edge
1067 define void @diamond_with_extra_in_edge(ptr %ptr1, ptr %ptr2, i32 %arg) {
1068 ; CHECK-LABEL: entry:
1069 ; CHECK-DAG: %cmp2 = icmp ne i32 0, %arg
1070 ; CHECK-DAG: %gep = getelementptr i32, ptr %ptr1, i32 4
1071 ; CHECK: br label %loop
1072 entry:
1073   br label %loop
1074
1075 loop:
1076   %phi1 = phi i32 [ 0, %entry ], [ %phi2, %then ]
1077   %cmp1 = icmp ugt i32 16, %phi1
1078   br i1 %cmp1, label %if, label %if.if
1079
1080 if:
1081   %cmp2 = icmp ne i32 0, %arg
1082   br i1 %cmp2, label %if.if, label %if.else
1083
1084 if.if:
1085   %gep = getelementptr i32, ptr %ptr1, i32 4
1086   %val = load i32, ptr %gep, align 4
1087   br label %then
1088
1089 if.else:
1090   br label %then
1091
1092 then:
1093   %phi2 = phi i32 [ %val, %if.if ], [ %phi1, %if.else ]
1094   store i32 %phi2, ptr %ptr2, align 4
1095   br label %loop
1096 }
1097
1098 ; %loop/%if/%then form a triangle, but %loop/%if/%then/%end also form a diamond.
1099 ; The triangle should be picked for conditional hoisting.
1100 ; CHECK-LABEL: @both_triangle_and_diamond
1101 define void @both_triangle_and_diamond(ptr %ptr1, ptr %ptr2, i32 %arg) {
1102 ; CHECK-LABEL: entry:
1103 ; CHECK-DAG: %cmp1 = icmp ne i32 0, %arg
1104 ; CHECK-DAG: %gep = getelementptr i32, ptr %ptr1, i32 4
1105 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_LICM:.*]], label %[[THEN_LICM:.*]]
1106 entry:
1107   br label %loop
1108
1109 ; CHECK-ENABLED: [[IF_LICM]]:
1110 ; CHECK-ENABLED: br label %[[THEN_LICM]]
1111
1112 ; CHECK-ENABLED: [[THEN_LICM]]:
1113 ; CHECK-ENABLED: %phi2 = phi i32 [ 0, %[[IF_LICM]] ], [ 1, %entry ]
1114 ; CHECK: br label %loop
1115
1116 loop:
1117   %phi1 = phi i32 [ 0, %entry ], [ %phi3, %end ]
1118   %cmp1 = icmp ne i32 0, %arg
1119   br i1 %cmp1, label %if, label %then
1120
1121 if:
1122   %gep = getelementptr i32, ptr %ptr1, i32 4
1123   %val = load i32, ptr %gep, align 4
1124   %cmp2 = icmp ugt i32 16, %phi1
1125   br i1 %cmp2, label %end, label %then
1126
1127 ; CHECK-LABEL: then:
1128 ; CHECK-DISABLED: %phi2 = phi i32 [ 0, %if ], [ 1, %loop ]
1129 then:
1130   %phi2 = phi i32 [ 0, %if ], [ 1, %loop ]
1131   br label %end
1132
1133 end:
1134   %phi3 = phi i32 [ %phi2, %then ], [ %val, %if ]
1135   store i32 %phi3, ptr %ptr2, align 4
1136   br label %loop
1137 }
1138
1139 ; We shouldn't duplicate the branch at the end of %loop and should instead hoist
1140 ; %val to %entry.
1141 ; CHECK-LABEL: @same_destination_branch
1142 define i32 @same_destination_branch(i32 %arg1, i32 %arg2) {
1143 ; CHECK-LABEL: entry:
1144 ; CHECK-DAG: %cmp1 = icmp ne i32 %arg2, 0
1145 ; CHECK-DAG: %val = add i32 %arg1, 1
1146 ; CHECK: br label %loop
1147 entry:
1148   br label %loop
1149
1150 ; CHECK-LABEL: loop:
1151 ; CHECK: %phi = phi i32 [ 0, %entry ], [ %add, %then ]
1152 loop:
1153   %phi = phi i32 [ 0, %entry ], [ %add, %then ]
1154   %add = add i32 %phi, 1
1155   %cmp1 = icmp ne i32 %arg2, 0
1156   br i1 %cmp1, label %if, label %if
1157
1158 if:
1159   %val = add i32 %arg1, 1
1160   br label %then
1161
1162 then:
1163   %cmp2 = icmp ne i32 %val, %phi
1164   br i1 %cmp2, label %loop, label %end
1165
1166 end:
1167   ret i32 %val
1168 }
1169
1170 ; Diamond-like control flow but the left/right blocks actually have the same
1171 ; destinations.
1172 ; TODO: We could potentially hoist all of phi2-4, but currently only hoist phi2.
1173 ; CHECK-LABEL: @diamond_like_same_destinations
1174 define i32 @diamond_like_same_destinations(i32 %arg1, i32 %arg2) {
1175 ; CHECK-LABEL: entry:
1176 ; CHECK-DAG: %cmp1 = icmp ne i32 %arg1, 0
1177 ; CHECK-DAG: %cmp2 = icmp ugt i32 %arg2, 1
1178 ; CHECK-DAG: %cmp3 = icmp ugt i32 %arg2, 2
1179 ; CHECK-ENABLED: br i1 %cmp1, label %[[LEFT1_LICM:.*]], label %[[RIGHT1_LICM:.*]]
1180 entry:
1181   br label %loop
1182
1183 ; CHECK-ENABLED: [[LEFT1_LICM]]:
1184 ; CHECK-ENABLED: br label %[[LEFT2_LICM:.*]]
1185
1186 ; CHECK-ENABLED: [[RIGHT1_LICM]]:
1187 ; CHECK-ENABLED: br label %[[LEFT2_LICM]]
1188
1189 ; CHECK-ENABLED: [[LEFT2_LICM]]:
1190 ; CHECK-ENABLED: %phi2 = phi i32 [ 0, %[[LEFT1_LICM]] ], [ 1, %[[RIGHT1_LICM]] ]
1191 ; CHECK: br label %loop
1192
1193 loop:
1194   %phi1 = phi i32 [ 0, %entry ], [ %add, %loopend ]
1195   %add = add i32 %phi1, 1
1196   %cmp1 = icmp ne i32 %arg1, 0
1197   br i1 %cmp1, label %left1, label %right1
1198
1199 left1:
1200   %cmp2 = icmp ugt i32 %arg2, 1
1201   br i1 %cmp2, label %left2, label %right2
1202
1203 right1:
1204   %cmp3 = icmp ugt i32 %arg2, 2
1205   br i1 %cmp3, label %left2, label %right2
1206
1207 ; CHECK-LABEL: left2:
1208 ; CHECK-DISABLED: %phi2 = phi i32 [ 0, %left1 ], [ 1, %right1 ]
1209 left2:
1210   %phi2 = phi i32 [ 0, %left1 ], [ 1, %right1 ]
1211   br label %loopend
1212
1213 ; CHECK-LABEL: right2:
1214 ; CHECK: %phi3 = phi i32 [ 2, %left1 ], [ 3, %right1 ]
1215 right2:
1216   %phi3 = phi i32 [ 2, %left1 ], [ 3, %right1 ]
1217   br label %loopend
1218
1219 ; CHECK-LABEL: loopend:
1220 ; CHECK: %phi4 = phi i32 [ %phi2, %left2 ], [ %phi3, %right2 ]
1221 loopend:
1222   %phi4 = phi i32 [ %phi2, %left2 ], [ %phi3, %right2 ]
1223   %cmp4 = icmp ne i32 %phi1, 32
1224   br i1 %cmp4, label %loop, label %end
1225
1226 end:
1227   ret i32 %phi4
1228 }
1229
1230 ; A phi with multiple incoming values for the same block due to a branch with
1231 ; two destinations that are actually the same. We can't hoist this.
1232 ; TODO: This could be hoisted by erasing one of the incoming values.
1233 ; CHECK-LABEL: @phi_multiple_values_same_block
1234 define i32 @phi_multiple_values_same_block(i32 %arg, i1 %arg2) {
1235 ; CHECK-LABEL: entry:
1236 ; CHECK: %cmp = icmp sgt i32 %arg, 4
1237 ; CHECK-NOT: phi
1238 ; CHECK: br label %loop
1239 entry:
1240   br label %loop
1241
1242 loop:
1243   %cmp = icmp sgt i32 %arg, 4
1244   br i1 %cmp, label %if, label %then
1245
1246 if:
1247   br i1 %arg2, label %then, label %then
1248
1249 then:
1250   %phi = phi i32 [ %arg, %loop ], [ 1, %if ], [ 1, %if ]
1251   br i1 %arg2, label %exit, label %loop
1252
1253 exit:
1254   ret i32 %phi
1255 }
1256
1257 ; %phi is conditionally used in %d, and the store that %d is used in cannot be
1258 ; hoisted. This means that we have to rehoist %d, but have to make sure to
1259 ; rehoist it after %phi.
1260 ; CHECK-LABEL: @phi_conditional_use
1261 define i64 @phi_conditional_use(i32 %f, ptr %g) {
1262 ; CHECK-LABEL: entry:
1263 ; CHECK: %cmp1 = icmp eq i32 %f, 1
1264 ; CHECK: %cmp2 = icmp eq i32 %f, 0
1265 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_END_LICM:.*]], label %[[IF_THEN_LICM:.*]]
1266 entry:
1267   %cmp1 = icmp eq i32 %f, 1
1268   %cmp2 = icmp eq i32 %f, 0
1269   br label %loop
1270
1271 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
1272 ; CHECK-ENABLED: br label %[[IF_END_LICM]]
1273
1274 ; CHECK-ENABLED: [[IF_END_LICM]]:
1275 ; CHECK-ENABLED: %phi = phi i64 [ 0, %entry ], [ 1, %[[IF_THEN_LICM]] ]
1276 ; CHECK-ENABLED: %d = getelementptr inbounds i32, ptr %g, i64 %phi
1277 ; CHECK-ENABLED: i1 %cmp2, label %[[LOOP_BACKEDGE_LICM:.*]], label %[[IF_THEN2_LICM:.*]]
1278
1279 ; CHECK-ENABLED: [[IF_THEN2_LICM]]:
1280 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1281
1282 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1283 ; CHECK: br label %loop
1284
1285 loop:
1286   br i1 %cmp1, label %if.end, label %if.then
1287
1288 if.then:
1289   br label %if.end
1290
1291 ; CHECK-LABEL: if.end:
1292 ; CHECK-DISABLED: %phi = phi i64 [ 0, %loop ], [ 1, %if.then ]
1293 if.end:
1294   %phi = phi i64 [ 0, %loop ], [ 1, %if.then ]
1295   br i1 %cmp2, label %loop.backedge, label %if.then2
1296
1297 ; CHECK-LABEL: if.then2:
1298 ; CHECK-DISABLED: %d = getelementptr inbounds i32, ptr %g, i64 %phi
1299 if.then2:
1300   %d = getelementptr inbounds i32, ptr %g, i64 %phi
1301   store i32 1, ptr %d, align 4
1302   br label %loop.backedge
1303
1304 loop.backedge:
1305   br label %loop
1306 }
1307
1308 ; As above, but we have two such phis
1309 ; CHECK-LABEL: @phi_conditional_use_twice
1310 define i64 @phi_conditional_use_twice(i32 %f, ptr %g) {
1311 ; CHECK-LABEL: entry:
1312 ; CHECK: %cmp1 = icmp eq i32 %f, 1
1313 ; CHECK: %cmp2 = icmp eq i32 %f, 0
1314 ; CHECK-ENABLED: br i1 %cmp1, label %[[IF_END_LICM:.*]], label %[[IF_THEN_LICM:.*]]
1315 entry:
1316   %cmp1 = icmp eq i32 %f, 1
1317   %cmp2 = icmp eq i32 %f, 0
1318   %cmp3 = icmp sgt i32 %f, 0
1319   br label %loop
1320
1321 ; CHECK-ENABLED: [[IF_THEN_LICM]]:
1322 ; CHECK-ENABLED: br label %[[IF_END_LICM]]
1323
1324 ; CHECK-ENABLED: [[IF_END_LICM]]:
1325 ; CHECK-ENABLED: %phi1 = phi i64 [ 0, %entry ], [ 1, %[[IF_THEN_LICM]] ]
1326 ; CHECK-ENABLED: %d = getelementptr inbounds i32, ptr %g, i64 %phi1
1327 ; CHECK-ENABLED: i1 %cmp2, label %[[IF_END2_LICM:.*]], label %[[IF_THEN2_LICM:.*]]
1328
1329 ; CHECK-ENABLED: [[IF_THEN2_LICM]]:
1330 ; CHECK-ENABLED: br label %[[IF_END2_LICM]]
1331
1332 ; CHECK-ENABLED: [[IF_END2_LICM]]:
1333 ; CHECK-ENABLED: %phi2 = phi i64 [ 2, %[[IF_END_LICM]] ], [ 3, %[[IF_THEN2_LICM]] ]
1334 ; CHECK-ENABLED: %e = getelementptr inbounds i32, ptr %g, i64 %phi2
1335 ; CHECK-ENABLED: i1 %cmp3, label %[[LOOP_BACKEDGE_LICM:.*]], label %[[IF_THEN3_LICM:.*]]
1336
1337 ; CHECK-ENABLED: [[IF_THEN3_LICM]]:
1338 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1339
1340 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1341 ; CHECK: br label %loop
1342
1343 loop:
1344   br i1 %cmp1, label %if.end, label %if.then
1345
1346 if.then:
1347   br label %if.end
1348
1349 ; CHECK-LABEL: if.end:
1350 ; CHECK-DISABLED: %phi1 = phi i64 [ 0, %loop ], [ 1, %if.then ]
1351 if.end:
1352   %phi1 = phi i64 [ 0, %loop ], [ 1, %if.then ]
1353   br i1 %cmp2, label %if.end2, label %if.then2
1354
1355 ; CHECK-LABEL: if.then2:
1356 ; CHECK-DISABLED: %d = getelementptr inbounds i32, ptr %g, i64 %phi1
1357 if.then2:
1358   %d = getelementptr inbounds i32, ptr %g, i64 %phi1
1359   store i32 1, ptr %d, align 4
1360   br label %if.end2
1361
1362 ; CHECK-LABEL: if.end2:
1363 ; CHECK-DISABLED: %phi2 = phi i64 [ 2, %if.end ], [ 3, %if.then2 ]
1364 if.end2:
1365   %phi2 = phi i64 [ 2, %if.end ], [ 3, %if.then2 ]
1366   br i1 %cmp3, label %loop.backedge, label %if.then3
1367
1368 ; CHECK-LABEL: if.then3:
1369 ; CHECK-DISABLED: %e = getelementptr inbounds i32, ptr %g, i64 %phi2
1370 if.then3:
1371   %e = getelementptr inbounds i32, ptr %g, i64 %phi2
1372   store i32 1, ptr %e, align 4
1373   br label %loop.backedge
1374
1375 loop.backedge:
1376   br label %loop
1377 }
1378
1379 ; The order that we hoist instructions from the loop is different to the textual
1380 ; order in the function. Check that we can rehoist this correctly.
1381 ; CHECK-LABEL: @rehoist_wrong_order_1
1382 define void @rehoist_wrong_order_1(ptr %ptr, i1 %arg) {
1383 ; CHECK-LABEL: entry
1384 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1385 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, ptr %ptr, i64 3
1386 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1387 ; CHECK-ENABLED: br i1 %arg, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1388 entry:
1389   br label %loop
1390
1391 ; CHECK-ENABLED: [[IF1_LICM]]:
1392 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
1393
1394 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1395 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1396
1397 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1398 ; CHECK-ENABLED: br i1 %arg, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1399
1400 ; CHECK-ENABLED: [[IF3_LICM]]:
1401 ; CHECK-ENABLED: br label %[[END_LICM]]
1402
1403 ; CHECK-ENABLED: [[END_LICM]]:
1404 ; CHECK: br label %loop
1405
1406 loop:
1407   br i1 %arg, label %if1, label %else1
1408
1409 if1:
1410   %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1411   store i32 0, ptr %gep1, align 4
1412   br label %loop.backedge
1413
1414 else1:
1415   %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1416   store i32 0, ptr %gep2, align 4
1417   br i1 %arg, label %if2, label %loop.backedge
1418
1419 if2:
1420   br i1 %arg, label %if3, label %end
1421
1422 if3:
1423   %gep3 = getelementptr inbounds i32, ptr %ptr, i64 3
1424   store i32 0, ptr %gep3, align 4
1425   br label %end
1426
1427 end:
1428   br label %loop.backedge
1429
1430 loop.backedge:
1431   br label %loop
1432
1433 }
1434
1435 ; CHECK-LABEL: @rehoist_wrong_order_2
1436 define void @rehoist_wrong_order_2(ptr %ptr, i1 %arg) {
1437 ; CHECK-LABEL: entry
1438 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1439 ; CHECK-DAG: %gep3 = getelementptr inbounds i32, ptr %gep2, i64 3
1440 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1441 ; CHECK-ENABLED: br i1 %arg, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1442 entry:
1443   br label %loop
1444
1445 ; CHECK-ENABLED: [[IF1_LICM]]:
1446 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
1447
1448 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1449 ; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
1450
1451 ; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
1452 ; CHECK-ENABLED: br i1 %arg, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1453
1454 ; CHECK-ENABLED: [[IF3_LICM]]:
1455 ; CHECK-ENABLED: br label %[[END_LICM]]
1456
1457 ; CHECK-ENABLED: [[END_LICM]]:
1458 ; CHECK: br label %loop
1459
1460 loop:
1461   br i1 %arg, label %if1, label %else1
1462
1463 if1:
1464   %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1465   store i32 0, ptr %gep1, align 4
1466   br label %loop.backedge
1467
1468 else1:
1469   %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1470   store i32 0, ptr %gep2, align 4
1471   br i1 %arg, label %if2, label %loop.backedge
1472
1473 if2:
1474   br i1 %arg, label %if3, label %end
1475
1476 if3:
1477   %gep3 = getelementptr inbounds i32, ptr %gep2, i64 3
1478   store i32 0, ptr %gep3, align 4
1479   br label %end
1480
1481 end:
1482   br label %loop.backedge
1483
1484 loop.backedge:
1485   br label %loop
1486 }
1487
1488 ; CHECK-LABEL: @rehoist_wrong_order_3
1489 define void @rehoist_wrong_order_3(ptr %ptr, i1 %arg) {
1490 ; CHECK-LABEL: entry
1491 ; CHECK-DAG: %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1492 ; CHECK-DAG: %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1493 ; CHECK-ENABLED: br i1 %arg, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
1494 entry:
1495   br label %loop
1496
1497 ; CHECK-ENABLED: [[IF1_LICM]]:
1498 ; CHECK-ENABLED: br label %[[IF2_LICM:.*]]
1499
1500 ; CHECK-ENABLED: [[ELSE1_LICM]]:
1501 ; CHECK-ENABLED: br label %[[IF2_LICM]]
1502
1503 ; CHECK-ENABLED: [[IF2_LICM]]:
1504 ; CHECK-ENABLED: %phi = phi ptr [ %gep1, %[[IF1_LICM]] ], [ %gep2, %[[ELSE1_LICM]] ]
1505 ; CHECK-ENABLED: %gep3 = getelementptr inbounds i32, ptr %phi, i64 3
1506 ; CHECK-ENABLED: br i1 %arg, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
1507
1508 ; CHECK-ENABLED: [[IF3_LICM]]:
1509 ; CHECK-ENABLED: br label %[[END_LICM]]
1510
1511 ; CHECK-ENABLED: [[END_LICM]]:
1512 ; CHECK: br label %loop
1513
1514 loop:
1515   br i1 %arg, label %if1, label %else1
1516
1517 if1:
1518   %gep1 = getelementptr inbounds i32, ptr %ptr, i64 1
1519   store i32 0, ptr %gep1, align 4
1520   br label %if2
1521
1522 else1:
1523   %gep2 = getelementptr inbounds i32, ptr %ptr, i64 2
1524   store i32 0, ptr %gep2, align 4
1525   br i1 %arg, label %if2, label %loop.backedge
1526
1527 if2:
1528   %phi = phi ptr [ %gep1, %if1 ], [ %gep2, %else1 ]
1529   br i1 %arg, label %if3, label %end
1530
1531 if3:
1532   %gep3 = getelementptr inbounds i32, ptr %phi, i64 3
1533   store i32 0, ptr %gep3, align 4
1534   br label %end
1535
1536 end:
1537   br label %loop.backedge
1538
1539 loop.backedge:
1540   br label %loop
1541 }