test/Transforms/LICM/sinking.ll

   1 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s
   2 ; RUN: opt < %s -debugify -basicaa -licm -S | FileCheck %s -check-prefix=DEBUGIFY
   3 ; RUN: opt < %s -basicaa -licm -S -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
   4
   5
   6 declare i32 @strlen(i8*) readonly nounwind
   7
   8 declare void @foo()
   9
  10 ; Sink readonly function.
  11 define i32 @test1(i8* %P) {
  12         br label %Loop
  13
  14 Loop:           ; preds = %Loop, %0
  15         %A = call i32 @strlen( i8* %P ) readonly
  16         br i1 false, label %Loop, label %Out
  17
  18 Out:            ; preds = %Loop
  19         ret i32 %A
  20 ; CHECK-LABEL: @test1(
  21 ; CHECK: Out:
  22 ; CHECK-NEXT: call i32 @strlen
  23 ; CHECK-NEXT: ret i32 %A
  24 }
  25
  26 declare double @sin(double) readnone nounwind
  27
  28 ; Sink readnone function out of loop with unknown memory behavior.
  29 define double @test2(double %X) {
  30         br label %Loop
  31
  32 Loop:           ; preds = %Loop, %0
  33         call void @foo( )
  34         %A = call double @sin( double %X ) readnone
  35         br i1 true, label %Loop, label %Out
  36
  37 Out:            ; preds = %Loop
  38         ret double %A
  39 ; CHECK-LABEL: @test2(
  40 ; CHECK: Out:
  41 ; CHECK-NEXT: call double @sin
  42 ; CHECK-NEXT: ret double %A
  43 }
  44
  45 ; FIXME: Should be able to sink this case
  46 define i32 @test2b(i32 %X) {
  47         br label %Loop
  48
  49 Loop:           ; preds = %Loop, %0
  50         call void @foo( )
  51         %A = sdiv i32 10, %X
  52         br i1 true, label %Loop, label %Out
  53
  54 Out:            ; preds = %Loop
  55         ret i32 %A
  56 ; CHECK-LABEL: @test2b(
  57 ; CHECK: Out:
  58 ; CHECK-NEXT: sdiv
  59 ; CHECK-NEXT: ret i32 %A
  60 }
  61
  62 define double @test2c(double* %P) {
  63         br label %Loop
  64
  65 Loop:           ; preds = %Loop, %0
  66         call void @foo( )
  67         %A = load double, double* %P, !invariant.load !{}
  68         br i1 true, label %Loop, label %Out
  69
  70 Out:            ; preds = %Loop
  71         ret double %A
  72 ; CHECK-LABEL: @test2c(
  73 ; CHECK: Out:
  74 ; CHECK-NEXT: load double
  75 ; CHECK-NEXT: ret double %A
  76 }
  77
  78 ; This testcase checks to make sure the sinker does not cause problems with
  79 ; critical edges.
  80 define void @test3() {
  81 Entry:
  82         br i1 false, label %Loop, label %Exit
  83 Loop:
  84         %X = add i32 0, 1
  85         br i1 false, label %Loop, label %Exit
  86 Exit:
  87         %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ]
  88         ret void
  89
  90 ; CHECK-LABEL: @test3(
  91 ; CHECK:     Exit.loopexit:
  92 ; CHECK-NEXT:  %X.le = add i32 0, 1
  93 ; CHECK-NEXT:  br label %Exit
  94
  95 }
  96
  97 ; If the result of an instruction is only used outside of the loop, sink
  98 ; the instruction to the exit blocks instead of executing it on every
  99 ; iteration of the loop.
 100 ;
 101 define i32 @test4(i32 %N) {
 102 Entry:
 103         br label %Loop
 104 Loop:           ; preds = %Loop, %Entry
 105         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
 106         %tmp.6 = mul i32 %N, %N_addr.0.pn               ; <i32> [#uses=1]
 107         %tmp.7 = sub i32 %tmp.6, %N             ; <i32> [#uses=1]
 108         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 109         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1            ; <i1> [#uses=1]
 110         br i1 %tmp.1, label %Loop, label %Out
 111 Out:            ; preds = %Loop
 112         ret i32 %tmp.7
 113 ; CHECK-LABEL: @test4(
 114 ; CHECK:     Out:
 115 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 116 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 117 ; CHECK-NEXT:  sub i32 %tmp.6.le, %N
 118 ; CHECK-NEXT:  ret i32
 119 }
 120
 121 ; To reduce register pressure, if a load is hoistable out of the loop, and the
 122 ; result of the load is only used outside of the loop, sink the load instead of
 123 ; hoisting it!
 124 ;
 125 @X = global i32 5               ; <i32*> [#uses=1]
 126
 127 define i32 @test5(i32 %N) {
 128 Entry:
 129         br label %Loop
 130 Loop:           ; preds = %Loop, %Entry
 131         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
 132         %tmp.6 = load i32, i32* @X              ; <i32> [#uses=1]
 133         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 134         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1            ; <i1> [#uses=1]
 135         br i1 %tmp.1, label %Loop, label %Out
 136 Out:            ; preds = %Loop
 137         ret i32 %tmp.6
 138 ; CHECK-LABEL: @test5(
 139 ; CHECK:     Out:
 140 ; CHECK-NEXT:  %tmp.6.le = load i32, i32* @X
 141 ; CHECK-NEXT:  ret i32 %tmp.6.le
 142 }
 143
 144
 145
 146 ; The loop sinker was running from the bottom of the loop to the top, causing
 147 ; it to miss opportunities to sink instructions that depended on sinking other
 148 ; instructions from the loop.  Instead they got hoisted, which is better than
 149 ; leaving them in the loop, but increases register pressure pointlessly.
 150
 151         %Ty = type { i32, i32 }
 152 @X2 = external global %Ty
 153
 154 define i32 @test6() {
 155         br label %Loop
 156 Loop:
 157         %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 158         %sunk2 = load i32, i32* %dead
 159         br i1 false, label %Loop, label %Out
 160 Out:            ; preds = %Loop
 161         ret i32 %sunk2
 162 ; CHECK-LABEL: @test6(
 163 ; CHECK:     Out:
 164 ; CHECK-NEXT:  %dead.le = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 165 ; CHECK-NEXT:  %sunk2.le = load i32, i32* %dead.le
 166 ; CHECK-NEXT:  ret i32 %sunk2.le
 167 }
 168
 169
 170
 171 ; This testcase ensures that we can sink instructions from loops with
 172 ; multiple exits.
 173 ;
 174 define i32 @test7(i32 %N, i1 %C) {
 175 Entry:
 176         br label %Loop
 177 Loop:           ; preds = %ContLoop, %Entry
 178         %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 179         %tmp.6 = mul i32 %N, %N_addr.0.pn
 180         %tmp.7 = sub i32 %tmp.6, %N             ; <i32> [#uses=2]
 181         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 182         br i1 %C, label %ContLoop, label %Out1
 183 ContLoop:
 184         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 185         br i1 %tmp.1, label %Loop, label %Out2
 186 Out1:           ; preds = %Loop
 187         ret i32 %tmp.7
 188 Out2:           ; preds = %ContLoop
 189         ret i32 %tmp.7
 190 ; CHECK-LABEL: @test7(
 191 ; CHECK:     Out1:
 192 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 193 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 194 ; CHECK-NEXT:  sub i32 %tmp.6.le, %N
 195 ; CHECK-NEXT:  ret
 196 ; CHECK:     Out2:
 197 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 198 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 199 ; CHECK-NEXT:  sub i32 %tmp.6.le4, %N
 200 ; CHECK-NEXT:  ret
 201 }
 202
 203
 204 ; This testcase checks to make sure we can sink values which are only live on
 205 ; some exits out of the loop, and that we can do so without breaking dominator
 206 ; info.
 207 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
 208 Entry:
 209         br label %Loop
 210 Loop:           ; preds = %Cont, %Entry
 211         br i1 %C1, label %Cont, label %exit1
 212 Cont:           ; preds = %Loop
 213         %X = load i32, i32* %P          ; <i32> [#uses=2]
 214         store i32 %X, i32* %Q
 215         %V = add i32 %X, 1              ; <i32> [#uses=1]
 216         br i1 %C2, label %Loop, label %exit2
 217 exit1:          ; preds = %Loop
 218         ret i32 0
 219 exit2:          ; preds = %Cont
 220         ret i32 %V
 221 ; CHECK-LABEL: @test8(
 222 ; CHECK:     exit1:
 223 ; CHECK-NEXT:  ret i32 0
 224 ; CHECK:     exit2:
 225 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %X
 226 ; CHECK-NEXT:  %V.le = add i32 %[[LCSSAPHI]], 1
 227 ; CHECK-NEXT:  ret i32 %V.le
 228 }
 229
 230
 231 define void @test9() {
 232 loopentry.2.i:
 233         br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
 234 no_exit.1.i.preheader:          ; preds = %loopentry.2.i
 235         br label %no_exit.1.i
 236 no_exit.1.i:            ; preds = %endif.8.i, %no_exit.1.i.preheader
 237         br i1 false, label %return.i, label %endif.8.i
 238 endif.8.i:              ; preds = %no_exit.1.i
 239         %inc.1.i = add i32 0, 1         ; <i32> [#uses=1]
 240         br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit
 241 loopentry.3.i.preheader.loopexit:               ; preds = %endif.8.i
 242         br label %loopentry.3.i.preheader
 243 loopentry.3.i.preheader:                ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i
 244         %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ]           ; <i32> [#uses=0]
 245         ret void
 246 return.i:               ; preds = %no_exit.1.i
 247         ret void
 248
 249 ; CHECK-LABEL: @test9(
 250 ; CHECK: loopentry.3.i.preheader.loopexit:
 251 ; CHECK-NEXT:  %inc.1.i.le = add i32 0, 1
 252 ; CHECK-NEXT:  br label %loopentry.3.i.preheader
 253 }
 254
 255
 256 ; Potentially trapping instructions may be sunk as long as they are guaranteed
 257 ; to be executed.
 258 define i32 @test10(i32 %N) {
 259 Entry:
 260         br label %Loop
 261 Loop:           ; preds = %Loop, %Entry
 262         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]          ; <i32> [#uses=3]
 263         %tmp.6 = sdiv i32 %N, %N_addr.0.pn              ; <i32> [#uses=1]
 264         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 265         %tmp.1 = icmp ne i32 %N_addr.0.pn, 0            ; <i1> [#uses=1]
 266         br i1 %tmp.1, label %Loop, label %Out
 267 Out:            ; preds = %Loop
 268         ret i32 %tmp.6
 269
 270 ; CHECK-LABEL: @test10(
 271 ; CHECK: Out:
 272 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 273 ; CHECK-NEXT:  %tmp.6.le = sdiv i32 %N, %[[LCSSAPHI]]
 274 ; CHECK-NEXT:  ret i32 %tmp.6.le
 275 }
 276
 277 ; Should delete, not sink, dead instructions.
 278 define void @test11() {
 279         br label %Loop
 280 Loop:
 281         %dead1 = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 282         %dead2 = getelementptr %Ty, %Ty* @X2, i64 0, i32 1
 283         br i1 false, label %Loop, label %Out
 284 Out:
 285         ret void
 286 ; CHECK-LABEL: @test11(
 287 ; CHECK:     Out:
 288 ; CHECK-NEXT:  ret void
 289
 290 ; The GEP in dead1 is adding a zero offset, so the DIExpression can be kept as
 291 ; a "register location".
 292 ; The GEP in dead2 is adding a 4 bytes to the pointer, so the DIExpression is
 293 ; turned into an "implicit location" using DW_OP_stack_value.
 294 ;
 295 ; DEBUGIFY-LABEL: @test11(
 296 ; DEBUGIFY: call void @llvm.dbg.value(metadata %Ty* @X2, metadata {{.*}}, metadata !DIExpression())
 297 ; DEBUGIFY: call void @llvm.dbg.value(metadata %Ty* @X2, metadata {{.*}}, metadata !DIExpression(DW_OP_plus_uconst, 4, DW_OP_stack_value))
 298 }
 299
 300 @c = common global [1 x i32] zeroinitializer, align 4
 301
 302 ; Test a *many* way nested loop with multiple exit blocks both of which exit
 303 ; multiple loop nests. This exercises LCSSA corner cases.
 304 define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) {
 305 entry:
 306   br label %l1.header
 307
 308 l1.header:
 309   %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ]
 310   %arrayidx.i = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 %iv
 311   br label %l2.header
 312
 313 l2.header:
 314   %x0 = load i1, i1* %c, align 4
 315   br i1 %x0, label %l1.latch, label %l3.preheader
 316
 317 l3.preheader:
 318   br label %l3.header
 319
 320 l3.header:
 321   %x1 = load i1, i1* %d, align 4
 322   br i1 %x1, label %l2.latch, label %l4.preheader
 323
 324 l4.preheader:
 325   br label %l4.header
 326
 327 l4.header:
 328   %x2 = load i1, i1* %a
 329   br i1 %x2, label %l3.latch, label %l4.body
 330
 331 l4.body:
 332   call void @f(i32* %arrayidx.i)
 333   %x3 = load i1, i1* %b
 334   %l = trunc i64 %iv to i32
 335   br i1 %x3, label %l4.latch, label %exit
 336
 337 l4.latch:
 338   call void @g()
 339   %x4 = load i1, i1* %b, align 4
 340   br i1 %x4, label %l4.header, label %exit
 341
 342 l3.latch:
 343   br label %l3.header
 344
 345 l2.latch:
 346   br label %l2.header
 347
 348 l1.latch:
 349   %iv.next = add nsw i64 %iv, 1
 350   br label %l1.header
 351
 352 exit:
 353   %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ]
 354 ; CHECK-LABEL: @PR18753(
 355 ; CHECK:       exit:
 356 ; CHECK-NEXT:    %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
 357 ; CHECK-NEXT:    %l.le = trunc i64 %[[LCSSAPHI]] to i32
 358 ; CHECK-NEXT:    ret i32 %l.le
 359
 360   ret i32 %lcssa
 361 }
 362
 363 ; @test12 moved to sink-promote.ll, as it tests sinking and promotion.
 364
 365 ; Test that we don't crash when trying to sink stores and there's no preheader
 366 ; available (which is used for creating loads that may be used by the SSA
 367 ; updater)
 368 define void @test13() {
 369 ; CHECK-LABEL: @test13
 370   br label %lab59
 371
 372 lab19:
 373   br i1 undef, label %lab20, label %lab38
 374
 375 lab20:
 376   br label %lab60
 377
 378 lab21:
 379   br i1 undef, label %lab22, label %lab38
 380
 381 lab22:
 382   br label %lab38
 383
 384 lab38:
 385   ret void
 386
 387 lab59:
 388   indirectbr i8* undef, [label %lab60, label %lab38]
 389
 390 lab60:
 391 ; CHECK: lab60:
 392 ; CHECK: store
 393 ; CHECK-NEXT: indirectbr
 394   store i32 2145244101, i32* undef, align 4
 395   indirectbr i8* undef, [label %lab21, label %lab19]
 396 }
 397
 398 ; Check if LICM can sink a sinkable instruction the exit blocks through
 399 ; a non-trivially replacable PHI node.
 400 ;
 401 ; CHECK-LABEL: @test14
 402 ; CHECK-LABEL: Loop:
 403 ; CHECK-NOT: mul
 404 ; CHECK-NOT: sub
 405 ;
 406 ; CHECK-LABEL: Out12.split.loop.exit:
 407 ; CHECK: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn, %ContLoop ]
 408 ; CHECK: %[[MUL:.*]] = mul i32 %N, %[[LCSSAPHI]]
 409 ; CHECK: br label %Out12
 410 ;
 411 ; CHECK-LABEL: Out12.split.loop.exit1:
 412 ; CHECK: %[[LCSSAPHI2:.*]] = phi i32 [ %N_addr.0.pn, %Loop ]
 413 ; CHECK: %[[MUL2:.*]] = mul i32 %N, %[[LCSSAPHI2]]
 414 ; CHECK: %[[SUB:.*]] = sub i32 %[[MUL2]], %N
 415 ; CHECK: br label %Out12
 416 ;
 417 ; CHECK-LABEL: Out12:
 418 ; CHECK: phi i32 [ %[[MUL]], %Out12.split.loop.exit ], [ %[[SUB]], %Out12.split.loop.exit1 ]
 419 define i32 @test14(i32 %N, i32 %N2, i1 %C) {
 420 Entry:
 421         br label %Loop
 422 Loop:
 423         %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 424         %sink.mul = mul i32 %N, %N_addr.0.pn
 425         %sink.sub = sub i32 %sink.mul, %N
 426         %dec = add i32 %N_addr.0.pn, -1
 427         br i1 %C, label %ContLoop, label %Out12
 428 ContLoop:
 429         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 430         br i1 %tmp.1, label %Loop, label %Out12
 431 Out12:
 432   %tmp = phi i32 [%sink.mul,  %ContLoop], [%sink.sub, %Loop]
 433   ret i32 %tmp
 434 }
 435
 436 ; In this test, splitting predecessors is not really required because the
 437 ; operations of sinkable instructions (sub and mul) are same. In this case, we
 438 ; can sink the same sinkable operations and modify the PHI to pass the operands
 439 ; to the shared operations. As of now, we split predecessors of non-trivially
 440 ; replicalbe PHIs by default in LICM because all incoming edges of a
 441 ; non-trivially replacable PHI in LCSSA is critical.
 442 ;
 443 ; CHECK-LABEL: @test15
 444 ; CHECK-LABEL: Loop:
 445 ; CHECK-NOT: mul
 446 ; CHECK-NOT: sub
 447 ;
 448 ; CHECK-LABEL: Out12.split.loop.exit:
 449 ; CHECK: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn, %ContLoop ]
 450 ; CHECK: %[[MUL:.*]] = mul i32 %N, %[[LCSSAPHI]]
 451 ; CHECK: %[[SUB:.*]] = sub i32 %[[MUL]], %N2
 452 ; CHECK: br label %Out12
 453 ;
 454 ; CHECK-LABEL: Out12.split.loop.exit1:
 455 ; CHECK: %[[LCSSAPHI2:.*]] = phi i32 [ %N_addr.0.pn, %Loop ]
 456 ; CHECK: %[[MUL2:.*]] = mul i32 %N, %[[LCSSAPHI2]]
 457 ; CHECK: %[[SUB2:.*]] = sub i32 %[[MUL2]], %N
 458 ; CHECK: br label %Out12
 459 ;
 460 ; CHECK-LABEL: Out12:
 461 ; CHECK: phi i32 [ %[[SUB]], %Out12.split.loop.exit ], [ %[[SUB2]], %Out12.split.loop.exit1 ]
 462 define i32 @test15(i32 %N, i32 %N2, i1 %C) {
 463 Entry:
 464         br label %Loop
 465 Loop:
 466         %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 467         %sink.mul = mul i32 %N, %N_addr.0.pn
 468         %sink.sub = sub i32 %sink.mul, %N
 469         %sink.sub2 = sub i32 %sink.mul, %N2
 470         %dec = add i32 %N_addr.0.pn, -1
 471         br i1 %C, label %ContLoop, label %Out12
 472 ContLoop:
 473         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 474         br i1 %tmp.1, label %Loop, label %Out12
 475 Out12:
 476   %tmp = phi i32 [%sink.sub2, %ContLoop], [%sink.sub, %Loop]
 477   ret i32 %tmp
 478 }
 479
 480 ; Sink through a non-trivially replacable PHI node which use the same sinkable
 481 ; instruction multiple times.
 482 ;
 483 ; CHECK-LABEL: @test16
 484 ; CHECK-LABEL: Loop:
 485 ; CHECK-NOT: mul
 486 ;
 487 ; CHECK-LABEL: Out.split.loop.exit:
 488 ; CHECK: %[[PHI:.*]] = phi i32 [ %l2, %ContLoop ]
 489 ; CHECK: br label %Out
 490 ;
 491 ; CHECK-LABEL: Out.split.loop.exit1:
 492 ; CHECK: %[[SINKABLE:.*]] = mul i32 %l2.lcssa, %t.le
 493 ; CHECK: br label %Out
 494 ;
 495 ; CHECK-LABEL: Out:
 496 ; CHECK: %idx = phi i32 [ %[[PHI]], %Out.split.loop.exit ], [ %[[SINKABLE]], %Out.split.loop.exit1 ]
 497 define i32 @test16(i1 %c, i8** %P, i32* %P2, i64 %V) {
 498 entry:
 499   br label %loop.ph
 500 loop.ph:
 501   br label %Loop
 502 Loop:
 503   %iv = phi i64 [ 0, %loop.ph ], [ %next, %ContLoop ]
 504   %l2 = call i32 @getv()
 505   %t = trunc i64 %iv to i32
 506   %sinkable = mul i32 %l2,  %t
 507   switch i32 %l2, label %ContLoop [
 508     i32 32, label %Out
 509     i32 46, label %Out
 510     i32 95, label %Out
 511   ]
 512 ContLoop:
 513   %next = add nuw i64 %iv, 1
 514   %c1 = call i1 @getc()
 515   br i1 %c1, label %Loop, label %Out
 516 Out:
 517   %idx = phi i32 [ %l2, %ContLoop ], [ %sinkable, %Loop ], [ %sinkable, %Loop ], [ %sinkable, %Loop ]
 518   ret i32 %idx
 519 }
 520
 521 ; Sink a sinkable instruction through multiple non-trivially replacable PHIs in
 522 ; differect exit blocks.
 523 ;
 524 ; CHECK-LABEL: @test17
 525 ; CHECK-LABEL: Loop:
 526 ; CHECK-NOT: mul
 527 ;
 528 ; CHECK-LABEL:OutA.split.loop.exit{{.*}}:
 529 ; CHECK:  %[[OP1:.*]] = phi i32 [ %N_addr.0.pn, %ContLoop1 ]
 530 ; CHECK:  %[[SINKABLE:.*]] = mul i32 %N, %[[OP1]]
 531 ; CHECK:  br label %OutA
 532 ;
 533 ; CHECK-LABEL:OutA:
 534 ; CHECK: phi i32{{.*}}[ %[[SINKABLE]], %OutA.split.loop.exit{{.*}} ]
 535 ;
 536 ; CHECK-LABEL:OutB.split.loop.exit{{.*}}:
 537 ; CHECK:  %[[OP2:.*]] = phi i32 [ %N_addr.0.pn, %ContLoop2 ]
 538 ; CHECK:  %[[SINKABLE2:.*]] = mul i32 %N, %[[OP2]]
 539 ; CHECK:  br label %OutB
 540 ;
 541 ; CHECK-LABEL:OutB:
 542 ; CHECK:  phi i32 {{.*}}[ %[[SINKABLE2]], %OutB.split.loop.exit{{.*}} ]
 543 define i32 @test17(i32 %N, i32 %N2) {
 544 Entry:
 545         br label %Loop
 546 Loop:
 547         %N_addr.0.pn = phi i32 [ %dec, %ContLoop3 ], [ %N, %Entry ]
 548         %sink.mul = mul i32 %N, %N_addr.0.pn
 549         %c0 = call i1 @getc()
 550         br i1 %c0 , label %ContLoop1, label %OutA
 551 ContLoop1:
 552         %c1 = call i1 @getc()
 553         br i1 %c1, label %ContLoop2, label %OutA
 554
 555 ContLoop2:
 556         %c2 = call i1 @getc()
 557         br i1 %c2, label %ContLoop3, label %OutB
 558 ContLoop3:
 559         %c3 = call i1 @getc()
 560         %dec = add i32 %N_addr.0.pn, -1
 561         br i1 %c3, label %Loop, label %OutB
 562 OutA:
 563         %tmp1 = phi i32 [%sink.mul, %ContLoop1], [%N2, %Loop]
 564         br label %Out12
 565 OutB:
 566         %tmp2 = phi i32 [%sink.mul, %ContLoop2], [%dec, %ContLoop3]
 567         br label %Out12
 568 Out12:
 569   %tmp = phi i32 [%tmp1, %OutA], [%tmp2, %OutB]
 570   ret i32 %tmp
 571 }
 572
 573
 574 ; Sink a sinkable instruction through both trivially and non-trivially replacable PHIs.
 575 ;
 576 ; CHECK-LABEL: @test18
 577 ; CHECK-LABEL: Loop:
 578 ; CHECK-NOT: mul
 579 ; CHECK-NOT: sub
 580 ;
 581 ; CHECK-LABEL:Out12.split.loop.exit:
 582 ; CHECK:  %[[OP:.*]] = phi i32 [ %iv, %ContLoop ]
 583 ; CHECK:  %[[DEC:.*]] = phi i32 [ %dec, %ContLoop ]
 584 ; CHECK:  %[[SINKMUL:.*]] = mul i32 %N, %[[OP]]
 585 ; CHECK:  %[[SINKSUB:.*]] = sub i32 %[[SINKMUL]], %N2
 586 ; CHECK:  br label %Out12
 587 ;
 588 ; CHECK-LABEL:Out12.split.loop.exit1:
 589 ; CHECK:  %[[OP2:.*]] = phi i32 [ %iv, %Loop ]
 590 ; CHECK:  %[[SINKMUL2:.*]] = mul i32 %N, %[[OP2]]
 591 ; CHECK:  %[[SINKSUB2:.*]] = sub i32 %[[SINKMUL2]], %N2
 592 ; CHECK:  br label %Out12
 593 ;
 594 ; CHECK-LABEL:Out12:
 595 ; CHECK:  %tmp1 = phi i32 [ %[[SINKSUB]], %Out12.split.loop.exit ], [ %[[SINKSUB2]], %Out12.split.loop.exit1 ]
 596 ; CHECK:  %tmp2 = phi i32 [ %[[DEC]], %Out12.split.loop.exit ], [ %[[SINKSUB2]], %Out12.split.loop.exit1 ]
 597 ; CHECK:  %add = add i32 %tmp1, %tmp2
 598 define i32 @test18(i32 %N, i32 %N2) {
 599 Entry:
 600         br label %Loop
 601 Loop:
 602         %iv = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 603         %sink.mul = mul i32 %N, %iv
 604         %sink.sub = sub i32 %sink.mul, %N2
 605         %c0 = call i1 @getc()
 606         br i1 %c0, label %ContLoop, label %Out12
 607 ContLoop:
 608         %dec = add i32 %iv, -1
 609         %c1 = call i1 @getc()
 610         br i1 %c1, label %Loop, label %Out12
 611 Out12:
 612   %tmp1 = phi i32 [%sink.sub, %ContLoop], [%sink.sub, %Loop]
 613   %tmp2 = phi i32 [%dec, %ContLoop], [%sink.sub, %Loop]
 614   %add = add i32 %tmp1, %tmp2
 615   ret i32 %add
 616 }
 617
 618 ; Do not sink an instruction through a non-trivially replacable PHI, to avoid
 619 ; assert while splitting predecessors, if the terminator of predecessor is an
 620 ; indirectbr.
 621 ; CHECK-LABEL: @test19
 622 ; CHECK-LABEL: L0:
 623 ; CHECK: %sinkable = mul
 624 ; CHECK: %sinkable2 = add
 625
 626 define i32 @test19(i1 %cond, i1 %cond2, i8* %address, i32 %v1) nounwind {
 627 entry:
 628   br label %L0
 629 L0:
 630   %indirect.goto.dest = select i1 %cond, i8* blockaddress(@test19, %exit), i8* %address
 631   %v2 = call i32 @getv()
 632   %sinkable = mul i32 %v1, %v2
 633   %sinkable2 = add i32 %v1, %v2
 634   indirectbr i8* %indirect.goto.dest, [label %L1, label %exit]
 635
 636 L1:
 637   %indirect.goto.dest2 = select i1 %cond2, i8* blockaddress(@test19, %exit), i8* %address
 638   indirectbr i8* %indirect.goto.dest2, [label %L0, label %exit]
 639
 640 exit:
 641   %r = phi i32 [%sinkable, %L0], [%sinkable2, %L1]
 642   ret i32 %r
 643 }
 644
 645
 646 ; Do not sink through a non-trivially replacable PHI if splitting predecessors
 647 ; not allowed in SplitBlockPredecessors().
 648 ;
 649 ; CHECK-LABEL: @test20
 650 ; CHECK-LABEL: while.cond
 651 ; CHECK: %sinkable = mul
 652 ; CHECK: %sinkable2 = add
 653 define void @test20(i32* %s, i1 %b, i32 %v1, i32 %v2) personality i32 (...)* @__CxxFrameHandler3 {
 654 entry:
 655   br label %while.cond
 656 while.cond:
 657   %v = call i32 @getv()
 658   %sinkable = mul i32 %v, %v2
 659   %sinkable2 = add  i32 %v, %v2
 660   br i1 %b, label %try.cont, label %while.body
 661 while.body:
 662   invoke void @may_throw()
 663           to label %while.body2 unwind label %catch.dispatch
 664 while.body2:
 665   invoke void @may_throw2()
 666           to label %while.cond unwind label %catch.dispatch
 667 catch.dispatch:
 668   %.lcssa1 = phi i32 [ %sinkable, %while.body ], [ %sinkable2, %while.body2 ]
 669   %cp = cleanuppad within none []
 670   store i32 %.lcssa1, i32* %s
 671   cleanupret from %cp unwind to caller
 672 try.cont:
 673   ret void
 674 }
 675
 676 ; The sinkable call should be sunk into an exit block split. After splitting
 677 ; the exit block, BlockColor for new blocks should be added properly so
 678 ; that we should be able to access valid ColorVector.
 679 ;
 680 ; CHECK-LABEL:@test21_pr36184
 681 ; CHECK-LABEL: Loop
 682 ; CHECK-NOT: %sinkableCall
 683 ; CHECK-LABEL:Out.split.loop.exit
 684 ; CHECK: %sinkableCall
 685 define i32 @test21_pr36184(i8* %P) personality i32 (...)* @__CxxFrameHandler3 {
 686 entry:
 687   br label %loop.ph
 688
 689 loop.ph:
 690   br label %Loop
 691
 692 Loop:
 693   %sinkableCall = call i32 @strlen( i8* %P ) readonly
 694   br i1 undef, label %ContLoop, label %Out
 695
 696 ContLoop:
 697   br i1 undef, label %Loop, label %Out
 698
 699 Out:
 700   %idx = phi i32 [ %sinkableCall, %Loop ], [0, %ContLoop ]
 701   ret i32 %idx
 702 }
 703
 704 ; We do not support splitting a landingpad block if BlockColors is not empty.
 705 ; CHECK-LABEL: @test22
 706 ; CHECK-LABEL: while.body2
 707 ; CHECK-LABEL: %mul
 708 ; CHECK-NOT: lpadBB.split{{.*}}
 709 define void @test22(i1 %b, i32 %v1, i32 %v2) personality i32 (...)* @__CxxFrameHandler3 {
 710 entry:
 711   br label %while.cond
 712 while.cond:
 713   br i1 %b, label %try.cont, label %while.body
 714
 715 while.body:
 716   invoke void @may_throw()
 717           to label %while.body2 unwind label %lpadBB
 718
 719 while.body2:
 720   %v = call i32 @getv()
 721   %mul = mul i32 %v, %v2
 722   invoke void @may_throw2()
 723           to label %while.cond unwind label %lpadBB
 724 lpadBB:
 725   %.lcssa1 = phi i32 [ 0, %while.body ], [ %mul, %while.body2 ]
 726   landingpad { i8*, i32 }
 727                catch i8* null
 728   br label %lpadBBSucc1
 729
 730 lpadBBSucc1:
 731   ret void
 732
 733 try.cont:
 734   ret void
 735 }
 736
 737 declare void @may_throw()
 738 declare void @may_throw2()
 739 declare i32 @__CxxFrameHandler3(...)
 740 declare i32 @getv()
 741 declare i1 @getc()
 742 declare void @f(i32*)
 743 declare void @g()