test/Transforms/LICM/hoist-mustexec.ll

   1 ; REQUIRES: asserts
   2 ; RUN: opt -S -basicaa -licm -ipt-expensive-asserts=true < %s | FileCheck %s
   3 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -ipt-expensive-asserts=true -S %s | FileCheck %s
   4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 declare void @f() nounwind
   8 declare void @llvm.experimental.guard(i1,...)
   9
  10 ; constant fold on first ieration
  11 define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
  12 ; CHECK-LABEL: @test1(
  13 entry:
  14 ; CHECK: %i1 = load i32, i32* %a, align 4
  15 ; CHECK-NEXT: br label %for.body
  16   br label %for.body
  17
  18 for.body:
  19   %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
  20   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  21   %r.chk = icmp ult i32 %iv, 2000
  22   br i1 %r.chk, label %continue, label %fail
  23 continue:
  24   %i1 = load i32, i32* %a, align 4
  25   %add = add nsw i32 %i1, %acc
  26   %inc = add nuw nsw i32 %iv, 1
  27   %exitcond = icmp eq i32 %inc, 1000
  28   br i1 %exitcond, label %for.cond.cleanup, label %for.body
  29
  30 for.cond.cleanup:
  31   ret i32 %add
  32
  33 fail:
  34   call void @f()
  35   ret i32 -1
  36 }
  37
  38 ; Same as test1, but with a floating point IR and fcmp
  39 define i32 @test_fcmp(i32* noalias nocapture readonly %a) nounwind uwtable {
  40 ; CHECK-LABEL: @test_fcmp(
  41 entry:
  42 ; CHECK: %i1 = load i32, i32* %a, align 4
  43 ; CHECK-NEXT: br label %for.body
  44   br label %for.body
  45
  46 for.body:
  47   %iv = phi float [ 0.0, %entry ], [ %inc, %continue ]
  48   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  49   %r.chk = fcmp olt float %iv, 2000.0
  50   br i1 %r.chk, label %continue, label %fail
  51 continue:
  52   %i1 = load i32, i32* %a, align 4
  53   %add = add nsw i32 %i1, %acc
  54   %inc = fadd float %iv, 1.0
  55   %exitcond = fcmp ogt float %inc, 1000.0
  56   br i1 %exitcond, label %for.cond.cleanup, label %for.body
  57
  58 for.cond.cleanup:
  59   ret i32 %add
  60
  61 fail:
  62   call void @f()
  63   ret i32 -1
  64 }
  65
  66 ; Count down from a.length w/entry guard
  67 ; TODO: currently unable to prove the following:
  68 ; ule i32 (add nsw i32 %len, -1), %len where len is [0, 512]
  69 define i32 @test2(i32* noalias nocapture readonly %a) nounwind uwtable {
  70 ; CHECK-LABEL: @test2(
  71 entry:
  72   %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
  73   %is.non.pos = icmp eq i32 %len, 0
  74   br i1 %is.non.pos, label %fail, label %preheader
  75 preheader:
  76   %lenminusone = add nsw i32 %len, -1
  77   br label %for.body
  78 for.body:
  79   %iv = phi i32 [ %lenminusone, %preheader ], [ %dec, %continue ]
  80   %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
  81   %r.chk = icmp ule i32 %iv, %len
  82   br i1 %r.chk, label %continue, label %fail
  83 continue:
  84 ; CHECK-LABEL: continue
  85 ; CHECK: %i1 = load i32, i32* %a, align 4
  86   %i1 = load i32, i32* %a, align 4
  87   %add = add nsw i32 %i1, %acc
  88   %dec = add nsw i32 %iv, -1
  89   %exitcond = icmp eq i32 %dec, 0
  90   br i1 %exitcond, label %for.cond.cleanup, label %for.body
  91
  92 for.cond.cleanup:
  93   ret i32 %add
  94
  95 fail:
  96   call void @f()
  97   ret i32 -1
  98 }
  99
 100 ; trivially true for zero
 101 define i32 @test3(i32* noalias nocapture readonly %a) nounwind uwtable {
 102 ; CHECK-LABEL: @test3(
 103 entry:
 104   %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
 105   %is.zero = icmp eq i32 %len, 0
 106   br i1 %is.zero, label %fail, label %preheader
 107 preheader:
 108 ; CHECK: %i1 = load i32, i32* %a, align 4
 109 ; CHECK-NEXT: br label %for.body
 110   br label %for.body
 111 for.body:
 112   %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
 113   %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
 114   %r.chk = icmp ule i32 %iv, %len
 115   br i1 %r.chk, label %continue, label %fail
 116 continue:
 117   %i1 = load i32, i32* %a, align 4
 118   %add = add nsw i32 %i1, %acc
 119   %inc = add nuw nsw i32 %iv, 1
 120   %exitcond = icmp eq i32 %inc, 1000
 121   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 122
 123 for.cond.cleanup:
 124   ret i32 %add
 125
 126 fail:
 127   call void @f()
 128   ret i32 -1
 129 }
 130
 131 ; requires fact length is non-zero
 132 ; TODO: IsKnownNonNullFromDominatingConditions is currently only be done for
 133 ; pointers; should handle integers too
 134 define i32 @test4(i32* noalias nocapture readonly %a) nounwind uwtable {
 135 ; CHECK-LABEL: @test4(
 136 entry:
 137   %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
 138   %is.zero = icmp eq i32 %len, 0
 139   br i1 %is.zero, label %fail, label %preheader
 140 preheader:
 141   br label %for.body
 142 for.body:
 143   %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
 144   %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
 145   %r.chk = icmp ult i32 %iv, %len
 146   br i1 %r.chk, label %continue, label %fail
 147 continue:
 148 ; CHECK-LABEL: continue
 149 ; CHECK: %i1 = load i32, i32* %a, align 4
 150   %i1 = load i32, i32* %a, align 4
 151   %add = add nsw i32 %i1, %acc
 152   %inc = add nuw nsw i32 %iv, 1
 153   %exitcond = icmp eq i32 %inc, 1000
 154   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 155
 156 for.cond.cleanup:
 157   ret i32 %add
 158
 159 fail:
 160   call void @f()
 161   ret i32 -1
 162 }
 163
 164 ; variation on test1 with branch swapped
 165 define i32 @test-brswap(i32* noalias nocapture readonly %a) nounwind uwtable {
 166 ; CHECK-LABEL: @test-brswap(
 167 entry:
 168 ; CHECK: %i1 = load i32, i32* %a, align 4
 169 ; CHECK-NEXT: br label %for.body
 170   br label %for.body
 171
 172 for.body:
 173   %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
 174   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
 175   %r.chk = icmp ugt i32 %iv, 2000
 176   br i1 %r.chk, label %fail, label %continue
 177 continue:
 178   %i1 = load i32, i32* %a, align 4
 179   %add = add nsw i32 %i1, %acc
 180   %inc = add nuw nsw i32 %iv, 1
 181   %exitcond = icmp eq i32 %inc, 1000
 182   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 183
 184 for.cond.cleanup:
 185   ret i32 %add
 186
 187 fail:
 188   call void @f()
 189   ret i32 -1
 190 }
 191
 192 define i32 @test-nonphi(i32* noalias nocapture readonly %a) nounwind uwtable {
 193 ; CHECK-LABEL: @test-nonphi(
 194 entry:
 195   br label %for.body
 196
 197 for.body:
 198 ; CHECK-LABEL: continue
 199 ; CHECK: %i1 = load i32, i32* %a, align 4
 200   %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
 201   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
 202   %xor = xor i32 %iv, 72
 203   %r.chk = icmp ugt i32 %xor, 2000
 204   br i1 %r.chk, label %fail, label %continue
 205 continue:
 206   %i1 = load i32, i32* %a, align 4
 207   %add = add nsw i32 %i1, %acc
 208   %inc = add nuw nsw i32 %iv, 1
 209   %exitcond = icmp eq i32 %inc, 1000
 210   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 211
 212 for.cond.cleanup:
 213   ret i32 %add
 214
 215 fail:
 216   call void @f()
 217   ret i32 -1
 218 }
 219
 220 define i32 @test-wrongphi(i32* noalias nocapture readonly %a) nounwind uwtable {
 221 ; CHECK-LABEL: @test-wrongphi(
 222 entry:
 223   br label %for.body
 224
 225 for.body:
 226   %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
 227   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
 228   %cond = icmp ult i32 %iv, 500
 229   br i1 %cond, label %dummy_block1, label %dummy_block2
 230
 231 dummy_block1:
 232   br label %dummy_block2
 233
 234 dummy_block2:
 235   %wrongphi = phi i32 [11, %for.body], [12, %dummy_block1]
 236   %r.chk = icmp ugt i32 %wrongphi, 2000
 237   br i1 %r.chk, label %fail, label %continue
 238 continue:
 239 ; CHECK-LABEL: continue
 240 ; CHECK: %i1 = load i32, i32* %a, align 4
 241   %i1 = load i32, i32* %a, align 4
 242   %add = add nsw i32 %i1, %acc
 243   %inc = add nuw nsw i32 %iv, 1
 244   %exitcond = icmp eq i32 %inc, 1000
 245   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 246
 247 for.cond.cleanup:
 248   ret i32 %add
 249
 250 fail:
 251   call void @f()
 252   ret i32 -1
 253 }
 254
 255 ; This works because loop-simplify is run implicitly, but test for it anyways
 256 define i32 @test-multiple-latch(i32* noalias nocapture readonly %a) nounwind uwtable {
 257 ; CHECK-LABEL: @test-multiple-latch(
 258 entry:
 259 ; CHECK: %i1 = load i32, i32* %a, align 4
 260 ; CHECK-NEXT: br label %for.body
 261   br label %for.body
 262
 263 for.body:
 264   %iv = phi i32 [ 0, %entry ], [ %inc, %continue1 ], [ %inc, %continue2 ]
 265   %acc = phi i32 [ 0, %entry ], [ %add, %continue1 ], [ %add, %continue2 ]
 266   %r.chk = icmp ult i32 %iv, 2000
 267   br i1 %r.chk, label %continue1, label %fail
 268 continue1:
 269   %i1 = load i32, i32* %a, align 4
 270   %add = add nsw i32 %i1, %acc
 271   %inc = add nuw nsw i32 %iv, 1
 272   %cmp = icmp eq i32 %add, 0
 273   br i1 %cmp, label %continue2, label %for.body
 274 continue2:
 275   %exitcond = icmp eq i32 %inc, 1000
 276   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 277
 278 for.cond.cleanup:
 279   ret i32 %add
 280
 281 fail:
 282   call void @f()
 283   ret i32 -1
 284 }
 285
 286 define void @test-hoisting-in-presence-of-guards(i1 %c, i32* %p) {
 287
 288 ; CHECK-LABEL: @test-hoisting-in-presence-of-guards
 289 ; CHECK:       entry:
 290 ; CHECK:         %a = load i32, i32* %p
 291 ; CHECK:         %invariant_cond = icmp ne i32 %a, 100
 292 ; CHECK:       loop:
 293
 294 entry:
 295   br label %loop
 296
 297 loop:
 298   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
 299   %iv.next = add i32 %iv, 1
 300   %a = load i32, i32* %p
 301   %invariant_cond = icmp ne i32 %a, 100
 302   call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
 303   %loop_cond = icmp slt i32 %iv.next, 1000
 304   br i1 %loop_cond, label %loop, label %exit
 305
 306 exit:
 307   ret void
 308 }
 309
 310
 311 declare void @may_throw() inaccessiblememonly
 312
 313 ; Test that we can sink a mustexecute load from loop header even in presence of
 314 ; throwing instructions after it.
 315 define void @test_hoist_from_header_01(i32* %p, i32 %n) {
 316
 317 ; CHECK-LABEL: @test_hoist_from_header_01(
 318 ; CHECK:       entry:
 319 ; CHECK-NEXT:  %load = load i32, i32* %p
 320 ; CHECK-NOT:   load i32
 321
 322 entry:
 323   br label %loop
 324
 325 loop:
 326   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 327   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 328   %load = load i32, i32* %p
 329   call void @may_throw()
 330   %cond = icmp slt i32 %iv, %n
 331   br i1 %cond, label %if.true, label %if.false
 332
 333 if.true:
 334   %a = add i32 %iv, %iv
 335   br label %backedge
 336
 337 if.false:
 338   %b = mul i32 %iv, %iv
 339   br label %backedge
 340
 341 backedge:
 342   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 343   %iv.next = add i32 %iv, %merge
 344   %loop.cond = icmp ult i32 %iv.next, %load
 345   br i1 %loop.cond, label %loop, label %exit
 346
 347 exit:
 348   ret void
 349 }
 350
 351 define void @test_hoist_from_header_02(i32* %p, i32 %n) {
 352
 353 ; CHECK-LABEL: @test_hoist_from_header_02(
 354 ; CHECK:       entry:
 355 ; CHECK-NEXT:  %load = load i32, i32* %p
 356 ; CHECK-NOT:   load i32
 357
 358 entry:
 359   br label %loop
 360
 361 loop:
 362   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 363   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 364   %load = load i32, i32* %p
 365   %cond = icmp slt i32 %iv, %n
 366   br i1 %cond, label %if.true, label %if.false
 367
 368 if.true:
 369   call void @may_throw()
 370   %a = add i32 %iv, %iv
 371   br label %backedge
 372
 373 if.false:
 374   %b = mul i32 %iv, %iv
 375   br label %backedge
 376
 377 backedge:
 378   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 379   %iv.next = add i32 %iv, %merge
 380   %loop.cond = icmp ult i32 %iv.next, %load
 381   br i1 %loop.cond, label %loop, label %exit
 382
 383 exit:
 384   ret void
 385 }
 386
 387 define void @test_hoist_from_header_03(i32* %p, i32 %n) {
 388
 389 ; CHECK-LABEL: @test_hoist_from_header_03(
 390 ; CHECK:       entry:
 391 ; CHECK-NEXT:  %load = load i32, i32* %p
 392 ; CHECK-NOT:   load i32
 393
 394 entry:
 395   br label %loop
 396
 397 loop:
 398   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 399   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 400   %load = load i32, i32* %p
 401   %cond = icmp slt i32 %iv, %n
 402   br i1 %cond, label %if.true, label %if.false
 403
 404 if.true:
 405   %a = add i32 %iv, %iv
 406   br label %backedge
 407
 408 if.false:
 409   %b = mul i32 %iv, %iv
 410   br label %backedge
 411
 412 backedge:
 413   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 414   call void @may_throw()
 415   %iv.next = add i32 %iv, %merge
 416   %loop.cond = icmp ult i32 %iv.next, %load
 417   br i1 %loop.cond, label %loop, label %exit
 418
 419 exit:
 420   ret void
 421 }
 422
 423 ; Check that a throwing instruction prohibits hoisting across it.
 424 define void @test_hoist_from_header_04(i32* %p, i32 %n) {
 425
 426 ; CHECK-LABEL: @test_hoist_from_header_04(
 427 ; CHECK:       entry:
 428 ; CHECK:       loop:
 429 ; CHECK:       %load = load i32, i32* %p
 430
 431 entry:
 432   br label %loop
 433
 434 loop:
 435   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 436   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 437   call void @may_throw()
 438   %load = load i32, i32* %p
 439   %cond = icmp slt i32 %iv, %n
 440   br i1 %cond, label %if.true, label %if.false
 441
 442 if.true:
 443   %a = add i32 %iv, %iv
 444   br label %backedge
 445
 446 if.false:
 447   %b = mul i32 %iv, %iv
 448   br label %backedge
 449
 450 backedge:
 451   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 452   %iv.next = add i32 %iv, %merge
 453   %loop.cond = icmp ult i32 %iv.next, %load
 454   br i1 %loop.cond, label %loop, label %exit
 455
 456 exit:
 457   ret void
 458 }
 459
 460 ; Check that we can hoist a mustexecute load from backedge even if something
 461 ; throws after it.
 462 define void @test_hoist_from_backedge_01(i32* %p, i32 %n) {
 463
 464 ; CHECK-LABEL: @test_hoist_from_backedge_01(
 465 ; CHECK:       entry:
 466 ; CHECK-NEXT:  %load = load i32, i32* %p
 467 ; CHECK-NOT:   load i32
 468
 469 entry:
 470   br label %loop
 471
 472 loop:
 473   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 474   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 475   %cond = icmp slt i32 %iv, %n
 476   br i1 %cond, label %if.true, label %if.false
 477
 478 if.true:
 479   %a = add i32 %iv, %iv
 480   br label %backedge
 481
 482 if.false:
 483   %b = mul i32 %iv, %iv
 484   br label %backedge
 485
 486 backedge:
 487   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 488   %iv.next = add i32 %iv, %merge
 489   %load = load i32, i32* %p
 490   call void @may_throw()
 491   %loop.cond = icmp ult i32 %iv.next, %load
 492   br i1 %loop.cond, label %loop, label %exit
 493
 494 exit:
 495   ret void
 496 }
 497
 498 ; Check that we don't hoist the load if something before it can throw.
 499 define void @test_hoist_from_backedge_02(i32* %p, i32 %n) {
 500
 501 ; CHECK-LABEL: @test_hoist_from_backedge_02(
 502 ; CHECK:       entry:
 503 ; CHECK:       loop:
 504 ; CHECK:       %load = load i32, i32* %p
 505
 506 entry:
 507   br label %loop
 508
 509 loop:
 510   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 511   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 512   %cond = icmp slt i32 %iv, %n
 513   br i1 %cond, label %if.true, label %if.false
 514
 515 if.true:
 516   %a = add i32 %iv, %iv
 517   br label %backedge
 518
 519 if.false:
 520   %b = mul i32 %iv, %iv
 521   br label %backedge
 522
 523 backedge:
 524   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 525   %iv.next = add i32 %iv, %merge
 526   call void @may_throw()
 527   %load = load i32, i32* %p
 528   %loop.cond = icmp ult i32 %iv.next, %load
 529   br i1 %loop.cond, label %loop, label %exit
 530
 531 exit:
 532   ret void
 533 }
 534
 535 define void @test_hoist_from_backedge_03(i32* %p, i32 %n) {
 536
 537 ; CHECK-LABEL: @test_hoist_from_backedge_03(
 538 ; CHECK:       entry:
 539 ; CHECK:       loop:
 540 ; CHECK:       %load = load i32, i32* %p
 541
 542 entry:
 543   br label %loop
 544
 545 loop:
 546   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 547   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 548   %cond = icmp slt i32 %iv, %n
 549   br i1 %cond, label %if.true, label %if.false
 550
 551 if.true:
 552   %a = add i32 %iv, %iv
 553   br label %backedge
 554
 555 if.false:
 556   %b = mul i32 %iv, %iv
 557   call void @may_throw()
 558   br label %backedge
 559
 560 backedge:
 561   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 562   %iv.next = add i32 %iv, %merge
 563   %load = load i32, i32* %p
 564   %loop.cond = icmp ult i32 %iv.next, %load
 565   br i1 %loop.cond, label %loop, label %exit
 566
 567 exit:
 568   ret void
 569 }
 570
 571 define void @test_hoist_from_backedge_04(i32* %p, i32 %n) {
 572
 573 ; CHECK-LABEL: @test_hoist_from_backedge_04(
 574 ; CHECK:       entry:
 575 ; CHECK:       loop:
 576 ; CHECK:       %load = load i32, i32* %p
 577
 578 entry:
 579   br label %loop
 580
 581 loop:
 582   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 583   %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
 584   call void @may_throw()
 585   %cond = icmp slt i32 %iv, %n
 586   br i1 %cond, label %if.true, label %if.false
 587
 588 if.true:
 589   %a = add i32 %iv, %iv
 590   br label %backedge
 591
 592 if.false:
 593   %b = mul i32 %iv, %iv
 594   br label %backedge
 595
 596 backedge:
 597   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
 598   %iv.next = add i32 %iv, %merge
 599   %load = load i32, i32* %p
 600   %loop.cond = icmp ult i32 %iv.next, %load
 601   br i1 %loop.cond, label %loop, label %exit
 602
 603 exit:
 604   ret void
 605 }