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