llvm/test/Transforms/LICM/sinking.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -basic-aa -licm -S -verify-memoryssa | FileCheck %s
   3
   4
   5 declare i32 @strlen(i8*) readonly nounwind willreturn
   6
   7 declare void @foo()
   8
   9 ; Sink readonly function.
  10 define i32 @test1(i8* %P) {
  11 ; CHECK-LABEL: @test1(
  12 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  13 ; CHECK:       Loop:
  14 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[OUT:%.*]]
  15 ; CHECK:       Out:
  16 ; CHECK-NEXT:    [[A_LE:%.*]] = call i32 @strlen(i8* [[P:%.*]]) #[[ATTR3:[0-9]+]]
  17 ; CHECK-NEXT:    ret i32 [[A_LE]]
  18 ;
  19   br label %Loop
  20
  21 Loop:           ; preds = %Loop, %0
  22   %A = call i32 @strlen( i8* %P ) readonly
  23   br i1 false, label %Loop, label %Out
  24
  25 Out:            ; preds = %Loop
  26   ret i32 %A
  27 }
  28
  29 declare double @sin(double) readnone nounwind willreturn
  30
  31 ; Sink readnone function out of loop with unknown memory behavior.
  32 define double @test2(double %X) {
  33 ; CHECK-LABEL: @test2(
  34 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  35 ; CHECK:       Loop:
  36 ; CHECK-NEXT:    call void @foo()
  37 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[OUT:%.*]]
  38 ; CHECK:       Out:
  39 ; CHECK-NEXT:    [[A_LE:%.*]] = call double @sin(double [[X:%.*]]) #[[ATTR4:[0-9]+]]
  40 ; CHECK-NEXT:    ret double [[A_LE]]
  41 ;
  42   br label %Loop
  43
  44 Loop:           ; preds = %Loop, %0
  45   call void @foo( )
  46   %A = call double @sin( double %X ) readnone
  47   br i1 true, label %Loop, label %Out
  48
  49 Out:            ; preds = %Loop
  50   ret double %A
  51 }
  52
  53 ; FIXME: Should be able to sink this case
  54 define i32 @test2b(i32 %X) {
  55 ; CHECK-LABEL: @test2b(
  56 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  57 ; CHECK:       Loop:
  58 ; CHECK-NEXT:    call void @foo()
  59 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[OUT:%.*]]
  60 ; CHECK:       Out:
  61 ; CHECK-NEXT:    [[A_LE:%.*]] = sdiv i32 10, [[X:%.*]]
  62 ; CHECK-NEXT:    ret i32 [[A_LE]]
  63 ;
  64   br label %Loop
  65
  66 Loop:           ; preds = %Loop, %0
  67   call void @foo( )
  68   %A = sdiv i32 10, %X
  69   br i1 true, label %Loop, label %Out
  70
  71 Out:            ; preds = %Loop
  72   ret i32 %A
  73 }
  74
  75 define double @test2c(double* %P) {
  76 ; CHECK-LABEL: @test2c(
  77 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  78 ; CHECK:       Loop:
  79 ; CHECK-NEXT:    call void @foo()
  80 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[OUT:%.*]]
  81 ; CHECK:       Out:
  82 ; CHECK-NEXT:    [[A_LE:%.*]] = load double, double* [[P:%.*]], align 8, !invariant.load !0
  83 ; CHECK-NEXT:    ret double [[A_LE]]
  84 ;
  85   br label %Loop
  86
  87 Loop:           ; preds = %Loop, %0
  88   call void @foo( )
  89   %A = load double, double* %P, !invariant.load !{}
  90   br i1 true, label %Loop, label %Out
  91
  92 Out:            ; preds = %Loop
  93   ret double %A
  94 }
  95
  96 ; This testcase checks to make sure the sinker does not cause problems with
  97 ; critical edges.
  98 define void @test3() {
  99 ; CHECK-LABEL: @test3(
 100 ; CHECK-NEXT:  Entry:
 101 ; CHECK-NEXT:    br i1 false, label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 102 ; CHECK:       Loop.preheader:
 103 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 104 ; CHECK:       Loop:
 105 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 106 ; CHECK:       Exit.loopexit:
 107 ; CHECK-NEXT:    [[X_LE:%.*]] = add i32 0, 1
 108 ; CHECK-NEXT:    br label [[EXIT]]
 109 ; CHECK:       Exit:
 110 ; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_LE]], [[EXIT_LOOPEXIT]] ]
 111 ; CHECK-NEXT:    ret void
 112 ;
 113 Entry:
 114   br i1 false, label %Loop, label %Exit
 115 Loop:
 116   %X = add i32 0, 1
 117   br i1 false, label %Loop, label %Exit
 118 Exit:
 119   %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ]
 120   ret void
 121
 122
 123 }
 124
 125 ; If the result of an instruction is only used outside of the loop, sink
 126 ; the instruction to the exit blocks instead of executing it on every
 127 ; iteration of the loop.
 128 ;
 129 define i32 @test4(i32 %N) {
 130 ; CHECK-LABEL: @test4(
 131 ; CHECK-NEXT:  Entry:
 132 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 133 ; CHECK:       Loop:
 134 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[LOOP]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 135 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 136 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
 137 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT:%.*]]
 138 ; CHECK:       Out:
 139 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 140 ; CHECK-NEXT:    [[TMP_6_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 141 ; CHECK-NEXT:    [[TMP_7_LE:%.*]] = sub i32 [[TMP_6_LE]], [[N]]
 142 ; CHECK-NEXT:    ret i32 [[TMP_7_LE]]
 143 ;
 144 Entry:
 145   br label %Loop
 146 Loop:           ; preds = %Loop, %Entry
 147   %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
 148   %tmp.6 = mul i32 %N, %N_addr.0.pn             ; <i32> [#uses=1]
 149   %tmp.7 = sub i32 %tmp.6, %N           ; <i32> [#uses=1]
 150   %dec = add i32 %N_addr.0.pn, -1               ; <i32> [#uses=1]
 151   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1          ; <i1> [#uses=1]
 152   br i1 %tmp.1, label %Loop, label %Out
 153 Out:            ; preds = %Loop
 154   ret i32 %tmp.7
 155 }
 156
 157 ; To reduce register pressure, if a load is hoistable out of the loop, and the
 158 ; result of the load is only used outside of the loop, sink the load instead of
 159 ; hoisting it!
 160 ;
 161 @X = global i32 5               ; <i32*> [#uses=1]
 162
 163 define i32 @test5(i32 %N) {
 164 ; CHECK-LABEL: @test5(
 165 ; CHECK-NEXT:  Entry:
 166 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 167 ; CHECK:       Loop:
 168 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[LOOP]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 169 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 170 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
 171 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT:%.*]]
 172 ; CHECK:       Out:
 173 ; CHECK-NEXT:    [[TMP_6_LE:%.*]] = load i32, i32* @X, align 4
 174 ; CHECK-NEXT:    ret i32 [[TMP_6_LE]]
 175 ;
 176 Entry:
 177   br label %Loop
 178 Loop:           ; preds = %Loop, %Entry
 179   %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
 180   %tmp.6 = load i32, i32* @X            ; <i32> [#uses=1]
 181   %dec = add i32 %N_addr.0.pn, -1               ; <i32> [#uses=1]
 182   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1          ; <i1> [#uses=1]
 183   br i1 %tmp.1, label %Loop, label %Out
 184 Out:            ; preds = %Loop
 185   ret i32 %tmp.6
 186 }
 187
 188
 189
 190 ; The loop sinker was running from the bottom of the loop to the top, causing
 191 ; it to miss opportunities to sink instructions that depended on sinking other
 192 ; instructions from the loop.  Instead they got hoisted, which is better than
 193 ; leaving them in the loop, but increases register pressure pointlessly.
 194
 195   %Ty = type { i32, i32 }
 196 @X2 = external global %Ty
 197
 198 define i32 @test6() {
 199 ; CHECK-LABEL: @test6(
 200 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 201 ; CHECK:       Loop:
 202 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[OUT:%.*]]
 203 ; CHECK:       Out:
 204 ; CHECK-NEXT:    [[DEAD_LE:%.*]] = getelementptr [[TY:%.*]], %Ty* @X2, i64 0, i32 0
 205 ; CHECK-NEXT:    [[SUNK2_LE:%.*]] = load i32, i32* [[DEAD_LE]], align 4
 206 ; CHECK-NEXT:    ret i32 [[SUNK2_LE]]
 207 ;
 208   br label %Loop
 209 Loop:
 210   %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 211   %sunk2 = load i32, i32* %dead
 212   br i1 false, label %Loop, label %Out
 213 Out:            ; preds = %Loop
 214   ret i32 %sunk2
 215 }
 216
 217
 218
 219 ; This testcase ensures that we can sink instructions from loops with
 220 ; multiple exits.
 221 ;
 222 define i32 @test7(i32 %N, i1 %C) {
 223 ; CHECK-LABEL: @test7(
 224 ; CHECK-NEXT:  Entry:
 225 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 226 ; CHECK:       Loop:
 227 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 228 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 229 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CONTLOOP]], label [[OUT1:%.*]]
 230 ; CHECK:       ContLoop:
 231 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
 232 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT2:%.*]]
 233 ; CHECK:       Out1:
 234 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 235 ; CHECK-NEXT:    [[TMP_6_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 236 ; CHECK-NEXT:    [[TMP_7_LE2:%.*]] = sub i32 [[TMP_6_LE]], [[N]]
 237 ; CHECK-NEXT:    ret i32 [[TMP_7_LE2]]
 238 ; CHECK:       Out2:
 239 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA5:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP]] ]
 240 ; CHECK-NEXT:    [[TMP_6_LE4:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA5]]
 241 ; CHECK-NEXT:    [[TMP_7_LE:%.*]] = sub i32 [[TMP_6_LE4]], [[N]]
 242 ; CHECK-NEXT:    ret i32 [[TMP_7_LE]]
 243 ;
 244 Entry:
 245   br label %Loop
 246 Loop:           ; preds = %ContLoop, %Entry
 247   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 248   %tmp.6 = mul i32 %N, %N_addr.0.pn
 249   %tmp.7 = sub i32 %tmp.6, %N           ; <i32> [#uses=2]
 250   %dec = add i32 %N_addr.0.pn, -1               ; <i32> [#uses=1]
 251   br i1 %C, label %ContLoop, label %Out1
 252 ContLoop:
 253   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 254   br i1 %tmp.1, label %Loop, label %Out2
 255 Out1:           ; preds = %Loop
 256   ret i32 %tmp.7
 257 Out2:           ; preds = %ContLoop
 258   ret i32 %tmp.7
 259 }
 260
 261
 262 ; This testcase checks to make sure we can sink values which are only live on
 263 ; some exits out of the loop, and that we can do so without breaking dominator
 264 ; info.
 265 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
 266 ; CHECK-LABEL: @test8(
 267 ; CHECK-NEXT:  Entry:
 268 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 269 ; CHECK:       Loop:
 270 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[CONT:%.*]], label [[EXIT1:%.*]]
 271 ; CHECK:       Cont:
 272 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4
 273 ; CHECK-NEXT:    store i32 [[X]], i32* [[Q:%.*]], align 4
 274 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP]], label [[EXIT2:%.*]]
 275 ; CHECK:       exit1:
 276 ; CHECK-NEXT:    ret i32 0
 277 ; CHECK:       exit2:
 278 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[CONT]] ]
 279 ; CHECK-NEXT:    [[V_LE:%.*]] = add i32 [[X_LCSSA]], 1
 280 ; CHECK-NEXT:    ret i32 [[V_LE]]
 281 ;
 282 Entry:
 283   br label %Loop
 284 Loop:           ; preds = %Cont, %Entry
 285   br i1 %C1, label %Cont, label %exit1
 286 Cont:           ; preds = %Loop
 287   %X = load i32, i32* %P                ; <i32> [#uses=2]
 288   store i32 %X, i32* %Q
 289   %V = add i32 %X, 1            ; <i32> [#uses=1]
 290   br i1 %C2, label %Loop, label %exit2
 291 exit1:          ; preds = %Loop
 292   ret i32 0
 293 exit2:          ; preds = %Cont
 294   ret i32 %V
 295 }
 296
 297
 298 define void @test9() {
 299 ; CHECK-LABEL: @test9(
 300 ; CHECK-NEXT:  loopentry.2.i:
 301 ; CHECK-NEXT:    br i1 false, label [[NO_EXIT_1_I_PREHEADER:%.*]], label [[LOOPENTRY_3_I_PREHEADER:%.*]]
 302 ; CHECK:       no_exit.1.i.preheader:
 303 ; CHECK-NEXT:    br label [[NO_EXIT_1_I:%.*]]
 304 ; CHECK:       no_exit.1.i:
 305 ; CHECK-NEXT:    br i1 false, label [[RETURN_I:%.*]], label [[ENDIF_8_I:%.*]]
 306 ; CHECK:       endif.8.i:
 307 ; CHECK-NEXT:    br i1 false, label [[NO_EXIT_1_I]], label [[LOOPENTRY_3_I_PREHEADER_LOOPEXIT:%.*]]
 308 ; CHECK:       loopentry.3.i.preheader.loopexit:
 309 ; CHECK-NEXT:    [[INC_1_I_LE:%.*]] = add i32 0, 1
 310 ; CHECK-NEXT:    br label [[LOOPENTRY_3_I_PREHEADER]]
 311 ; CHECK:       loopentry.3.i.preheader:
 312 ; CHECK-NEXT:    [[ARG_NUM_0_I_PH13000:%.*]] = phi i32 [ 0, [[LOOPENTRY_2_I:%.*]] ], [ [[INC_1_I_LE]], [[LOOPENTRY_3_I_PREHEADER_LOOPEXIT]] ]
 313 ; CHECK-NEXT:    ret void
 314 ; CHECK:       return.i:
 315 ; CHECK-NEXT:    ret void
 316 ;
 317 loopentry.2.i:
 318   br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
 319 no_exit.1.i.preheader:          ; preds = %loopentry.2.i
 320   br label %no_exit.1.i
 321 no_exit.1.i:            ; preds = %endif.8.i, %no_exit.1.i.preheader
 322   br i1 false, label %return.i, label %endif.8.i
 323 endif.8.i:              ; preds = %no_exit.1.i
 324   %inc.1.i = add i32 0, 1               ; <i32> [#uses=1]
 325   br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit
 326 loopentry.3.i.preheader.loopexit:               ; preds = %endif.8.i
 327   br label %loopentry.3.i.preheader
 328 loopentry.3.i.preheader:                ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i
 329   %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ]         ; <i32> [#uses=0]
 330   ret void
 331 return.i:               ; preds = %no_exit.1.i
 332   ret void
 333
 334 }
 335
 336
 337 ; Potentially trapping instructions may be sunk as long as they are guaranteed
 338 ; to be executed.
 339 define i32 @test10(i32 %N) {
 340 ; CHECK-LABEL: @test10(
 341 ; CHECK-NEXT:  Entry:
 342 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 343 ; CHECK:       Loop:
 344 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[LOOP]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 345 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 346 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 0
 347 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT:%.*]]
 348 ; CHECK:       Out:
 349 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 350 ; CHECK-NEXT:    [[TMP_6_LE:%.*]] = sdiv i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 351 ; CHECK-NEXT:    ret i32 [[TMP_6_LE]]
 352 ;
 353 Entry:
 354   br label %Loop
 355 Loop:           ; preds = %Loop, %Entry
 356   %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]                ; <i32> [#uses=3]
 357   %tmp.6 = sdiv i32 %N, %N_addr.0.pn            ; <i32> [#uses=1]
 358   %dec = add i32 %N_addr.0.pn, -1               ; <i32> [#uses=1]
 359   %tmp.1 = icmp ne i32 %N_addr.0.pn, 0          ; <i1> [#uses=1]
 360   br i1 %tmp.1, label %Loop, label %Out
 361 Out:            ; preds = %Loop
 362   ret i32 %tmp.6
 363
 364 }
 365
 366 ; Should delete, not sink, dead instructions.
 367 define void @test11() {
 368 ; CHECK-LABEL: @test11(
 369 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 370 ; CHECK:       Loop:
 371 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[OUT:%.*]]
 372 ; CHECK:       Out:
 373 ; CHECK-NEXT:    ret void
 374 ;
 375   br label %Loop
 376 Loop:
 377   %dead1 = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 378   %dead2 = getelementptr %Ty, %Ty* @X2, i64 0, i32 1
 379   br i1 false, label %Loop, label %Out
 380 Out:
 381   ret void
 382 }
 383
 384 @c = common global [1 x i32] zeroinitializer, align 4
 385
 386 ; Test a *many* way nested loop with multiple exit blocks both of which exit
 387 ; multiple loop nests. This exercises LCSSA corner cases.
 388 define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) {
 389 ; CHECK-LABEL: @PR18753(
 390 ; CHECK-NEXT:  entry:
 391 ; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
 392 ; CHECK:       l1.header:
 393 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[L1_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 394 ; CHECK-NEXT:    [[ARRAYIDX_I:%.*]] = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 [[IV]]
 395 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
 396 ; CHECK:       l2.header:
 397 ; CHECK-NEXT:    [[X0:%.*]] = load i1, i1* [[C:%.*]], align 4
 398 ; CHECK-NEXT:    br i1 [[X0]], label [[L1_LATCH]], label [[L3_PREHEADER:%.*]]
 399 ; CHECK:       l3.preheader:
 400 ; CHECK-NEXT:    br label [[L3_HEADER:%.*]]
 401 ; CHECK:       l3.header:
 402 ; CHECK-NEXT:    [[X1:%.*]] = load i1, i1* [[D:%.*]], align 4
 403 ; CHECK-NEXT:    br i1 [[X1]], label [[L2_LATCH:%.*]], label [[L4_PREHEADER:%.*]]
 404 ; CHECK:       l4.preheader:
 405 ; CHECK-NEXT:    br label [[L4_HEADER:%.*]]
 406 ; CHECK:       l4.header:
 407 ; CHECK-NEXT:    [[X2:%.*]] = load i1, i1* [[A:%.*]], align 1
 408 ; CHECK-NEXT:    br i1 [[X2]], label [[L3_LATCH:%.*]], label [[L4_BODY:%.*]]
 409 ; CHECK:       l4.body:
 410 ; CHECK-NEXT:    call void @f(i32* [[ARRAYIDX_I]])
 411 ; CHECK-NEXT:    [[X3:%.*]] = load i1, i1* [[B:%.*]], align 1
 412 ; CHECK-NEXT:    br i1 [[X3]], label [[L4_LATCH:%.*]], label [[EXIT:%.*]]
 413 ; CHECK:       l4.latch:
 414 ; CHECK-NEXT:    call void @g()
 415 ; CHECK-NEXT:    [[X4:%.*]] = load i1, i1* [[B]], align 4
 416 ; CHECK-NEXT:    br i1 [[X4]], label [[L4_HEADER]], label [[EXIT]]
 417 ; CHECK:       l3.latch:
 418 ; CHECK-NEXT:    br label [[L3_HEADER]]
 419 ; CHECK:       l2.latch:
 420 ; CHECK-NEXT:    br label [[L2_HEADER]]
 421 ; CHECK:       l1.latch:
 422 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
 423 ; CHECK-NEXT:    br label [[L1_HEADER]]
 424 ; CHECK:       exit:
 425 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i64 [ [[IV]], [[L4_LATCH]] ], [ [[IV]], [[L4_BODY]] ]
 426 ; CHECK-NEXT:    [[L_LE:%.*]] = trunc i64 [[IV_LCSSA]] to i32
 427 ; CHECK-NEXT:    ret i32 [[L_LE]]
 428 ;
 429 entry:
 430   br label %l1.header
 431
 432 l1.header:
 433   %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ]
 434   %arrayidx.i = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 %iv
 435   br label %l2.header
 436
 437 l2.header:
 438   %x0 = load i1, i1* %c, align 4
 439   br i1 %x0, label %l1.latch, label %l3.preheader
 440
 441 l3.preheader:
 442   br label %l3.header
 443
 444 l3.header:
 445   %x1 = load i1, i1* %d, align 4
 446   br i1 %x1, label %l2.latch, label %l4.preheader
 447
 448 l4.preheader:
 449   br label %l4.header
 450
 451 l4.header:
 452   %x2 = load i1, i1* %a
 453   br i1 %x2, label %l3.latch, label %l4.body
 454
 455 l4.body:
 456   call void @f(i32* %arrayidx.i)
 457   %x3 = load i1, i1* %b
 458   %l = trunc i64 %iv to i32
 459   br i1 %x3, label %l4.latch, label %exit
 460
 461 l4.latch:
 462   call void @g()
 463   %x4 = load i1, i1* %b, align 4
 464   br i1 %x4, label %l4.header, label %exit
 465
 466 l3.latch:
 467   br label %l3.header
 468
 469 l2.latch:
 470   br label %l2.header
 471
 472 l1.latch:
 473   %iv.next = add nsw i64 %iv, 1
 474   br label %l1.header
 475
 476 exit:
 477   %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ]
 478
 479   ret i32 %lcssa
 480 }
 481
 482 ; @test12 moved to sink-promote.ll, as it tests sinking and promotion.
 483
 484 ; Test that we don't crash when trying to sink stores and there's no preheader
 485 ; available (which is used for creating loads that may be used by the SSA
 486 ; updater)
 487 define void @test13() {
 488 ; CHECK-LABEL: @test13(
 489 ; CHECK-NEXT:    br label [[LAB59:%.*]]
 490 ; CHECK:       lab19:
 491 ; CHECK-NEXT:    br i1 false, label [[LAB20:%.*]], label [[LAB38_LOOPEXIT:%.*]]
 492 ; CHECK:       lab20:
 493 ; CHECK-NEXT:    br label [[LAB60:%.*]]
 494 ; CHECK:       lab21:
 495 ; CHECK-NEXT:    br i1 undef, label [[LAB22:%.*]], label [[LAB38:%.*]]
 496 ; CHECK:       lab22:
 497 ; CHECK-NEXT:    br label [[LAB38]]
 498 ; CHECK:       lab38.loopexit:
 499 ; CHECK-NEXT:    br label [[LAB38]]
 500 ; CHECK:       lab38:
 501 ; CHECK-NEXT:    ret void
 502 ; CHECK:       lab59:
 503 ; CHECK-NEXT:    indirectbr i8* undef, [label [[LAB60]], label %lab38]
 504 ; CHECK:       lab60:
 505 ; CHECK-NEXT:    store i32 2145244101, i32* undef, align 4
 506 ; CHECK-NEXT:    indirectbr i8* undef, [label [[LAB21:%.*]], label %lab19]
 507 ;
 508   br label %lab59
 509
 510 lab19:
 511   br i1 undef, label %lab20, label %lab38
 512
 513 lab20:
 514   br label %lab60
 515
 516 lab21:
 517   br i1 undef, label %lab22, label %lab38
 518
 519 lab22:
 520   br label %lab38
 521
 522 lab38:
 523   ret void
 524
 525 lab59:
 526   indirectbr i8* undef, [label %lab60, label %lab38]
 527
 528 lab60:
 529   store i32 2145244101, i32* undef, align 4
 530   indirectbr i8* undef, [label %lab21, label %lab19]
 531 }
 532
 533 ; Check if LICM can sink a sinkable instruction the exit blocks through
 534 ; a non-trivially replacable PHI node.
 535 define i32 @test14(i32 %N, i32 %N2, i1 %C) {
 536 ; CHECK-LABEL: @test14(
 537 ; CHECK-NEXT:  Entry:
 538 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 539 ; CHECK:       Loop:
 540 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 541 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 542 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CONTLOOP]], label [[OUT12_SPLIT_LOOP_EXIT1:%.*]]
 543 ; CHECK:       ContLoop:
 544 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
 545 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT12_SPLIT_LOOP_EXIT:%.*]]
 546 ; CHECK:       Out12.split.loop.exit:
 547 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA4:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP]] ]
 548 ; CHECK-NEXT:    [[SINK_MUL_LE3:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA4]]
 549 ; CHECK-NEXT:    br label [[OUT12:%.*]]
 550 ; CHECK:       Out12.split.loop.exit1:
 551 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 552 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 553 ; CHECK-NEXT:    [[SINK_SUB_LE:%.*]] = sub i32 [[SINK_MUL_LE]], [[N]]
 554 ; CHECK-NEXT:    br label [[OUT12]]
 555 ; CHECK:       Out12:
 556 ; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[SINK_MUL_LE3]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
 557 ; CHECK-NEXT:    ret i32 [[TMP]]
 558 ;
 559 Entry:
 560   br label %Loop
 561 Loop:
 562   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 563   %sink.mul = mul i32 %N, %N_addr.0.pn
 564   %sink.sub = sub i32 %sink.mul, %N
 565   %dec = add i32 %N_addr.0.pn, -1
 566   br i1 %C, label %ContLoop, label %Out12
 567 ContLoop:
 568   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 569   br i1 %tmp.1, label %Loop, label %Out12
 570 Out12:
 571   %tmp = phi i32 [%sink.mul,  %ContLoop], [%sink.sub, %Loop]
 572   ret i32 %tmp
 573 }
 574
 575 ; In this test, splitting predecessors is not really required because the
 576 ; operations of sinkable instructions (sub and mul) are same. In this case, we
 577 ; can sink the same sinkable operations and modify the PHI to pass the operands
 578 ; to the shared operations. As of now, we split predecessors of non-trivially
 579 ; replicalbe PHIs by default in LICM because all incoming edges of a
 580 ; non-trivially replacable PHI in LCSSA is critical.
 581 define i32 @test15(i32 %N, i32 %N2, i1 %C) {
 582 ; CHECK-LABEL: @test15(
 583 ; CHECK-NEXT:  Entry:
 584 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 585 ; CHECK:       Loop:
 586 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 587 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 588 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CONTLOOP]], label [[OUT12_SPLIT_LOOP_EXIT1:%.*]]
 589 ; CHECK:       ContLoop:
 590 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp ne i32 [[N_ADDR_0_PN]], 1
 591 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[LOOP]], label [[OUT12_SPLIT_LOOP_EXIT:%.*]]
 592 ; CHECK:       Out12.split.loop.exit:
 593 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA5:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP]] ]
 594 ; CHECK-NEXT:    [[SINK_MUL_LE4:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA5]]
 595 ; CHECK-NEXT:    [[SINK_SUB2_LE:%.*]] = sub i32 [[SINK_MUL_LE4]], [[N2:%.*]]
 596 ; CHECK-NEXT:    br label [[OUT12:%.*]]
 597 ; CHECK:       Out12.split.loop.exit1:
 598 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[LOOP]] ]
 599 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 600 ; CHECK-NEXT:    [[SINK_SUB_LE:%.*]] = sub i32 [[SINK_MUL_LE]], [[N]]
 601 ; CHECK-NEXT:    br label [[OUT12]]
 602 ; CHECK:       Out12:
 603 ; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[SINK_SUB2_LE]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
 604 ; CHECK-NEXT:    ret i32 [[TMP]]
 605 ;
 606 Entry:
 607   br label %Loop
 608 Loop:
 609   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 610   %sink.mul = mul i32 %N, %N_addr.0.pn
 611   %sink.sub = sub i32 %sink.mul, %N
 612   %sink.sub2 = sub i32 %sink.mul, %N2
 613   %dec = add i32 %N_addr.0.pn, -1
 614   br i1 %C, label %ContLoop, label %Out12
 615 ContLoop:
 616   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 617   br i1 %tmp.1, label %Loop, label %Out12
 618 Out12:
 619   %tmp = phi i32 [%sink.sub2, %ContLoop], [%sink.sub, %Loop]
 620   ret i32 %tmp
 621 }
 622
 623 ; Sink through a non-trivially replacable PHI node which use the same sinkable
 624 ; instruction multiple times.
 625 define i32 @test16(i1 %c, i8** %P, i32* %P2, i64 %V) {
 626 ; CHECK-LABEL: @test16(
 627 ; CHECK-NEXT:  entry:
 628 ; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
 629 ; CHECK:       loop.ph:
 630 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 631 ; CHECK:       Loop:
 632 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[LOOP_PH]] ], [ [[NEXT:%.*]], [[CONTLOOP:%.*]] ]
 633 ; CHECK-NEXT:    [[L2:%.*]] = call i32 @getv()
 634 ; CHECK-NEXT:    switch i32 [[L2]], label [[CONTLOOP]] [
 635 ; CHECK-NEXT:    i32 32, label [[OUT_SPLIT_LOOP_EXIT1:%.*]]
 636 ; CHECK-NEXT:    i32 46, label [[OUT_SPLIT_LOOP_EXIT1]]
 637 ; CHECK-NEXT:    i32 95, label [[OUT_SPLIT_LOOP_EXIT1]]
 638 ; CHECK-NEXT:    ]
 639 ; CHECK:       ContLoop:
 640 ; CHECK-NEXT:    [[NEXT]] = add nuw i64 [[IV]], 1
 641 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @getc()
 642 ; CHECK-NEXT:    br i1 [[C1]], label [[LOOP]], label [[OUT_SPLIT_LOOP_EXIT:%.*]]
 643 ; CHECK:       Out.split.loop.exit:
 644 ; CHECK-NEXT:    [[IDX_PH:%.*]] = phi i32 [ [[L2]], [[CONTLOOP]] ]
 645 ; CHECK-NEXT:    br label [[OUT:%.*]]
 646 ; CHECK:       Out.split.loop.exit1:
 647 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i64 [ [[IV]], [[LOOP]] ], [ [[IV]], [[LOOP]] ], [ [[IV]], [[LOOP]] ]
 648 ; CHECK-NEXT:    [[L2_LCSSA:%.*]] = phi i32 [ [[L2]], [[LOOP]] ], [ [[L2]], [[LOOP]] ], [ [[L2]], [[LOOP]] ]
 649 ; CHECK-NEXT:    [[T_LE:%.*]] = trunc i64 [[IV_LCSSA]] to i32
 650 ; CHECK-NEXT:    [[SINKABLE_LE:%.*]] = mul i32 [[L2_LCSSA]], [[T_LE]]
 651 ; CHECK-NEXT:    br label [[OUT]]
 652 ; CHECK:       Out:
 653 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_PH]], [[OUT_SPLIT_LOOP_EXIT]] ], [ [[SINKABLE_LE]], [[OUT_SPLIT_LOOP_EXIT1]] ]
 654 ; CHECK-NEXT:    ret i32 [[IDX]]
 655 ;
 656 entry:
 657   br label %loop.ph
 658 loop.ph:
 659   br label %Loop
 660 Loop:
 661   %iv = phi i64 [ 0, %loop.ph ], [ %next, %ContLoop ]
 662   %l2 = call i32 @getv()
 663   %t = trunc i64 %iv to i32
 664   %sinkable = mul i32 %l2,  %t
 665   switch i32 %l2, label %ContLoop [
 666   i32 32, label %Out
 667   i32 46, label %Out
 668   i32 95, label %Out
 669   ]
 670 ContLoop:
 671   %next = add nuw i64 %iv, 1
 672   %c1 = call i1 @getc()
 673   br i1 %c1, label %Loop, label %Out
 674 Out:
 675   %idx = phi i32 [ %l2, %ContLoop ], [ %sinkable, %Loop ], [ %sinkable, %Loop ], [ %sinkable, %Loop ]
 676   ret i32 %idx
 677 }
 678
 679 ; Sink a sinkable instruction through multiple non-trivially replacable PHIs in
 680 ; differect exit blocks.
 681 define i32 @test17(i32 %N, i32 %N2) {
 682 ; CHECK-LABEL: @test17(
 683 ; CHECK-NEXT:  Entry:
 684 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 685 ; CHECK:       Loop:
 686 ; CHECK-NEXT:    [[N_ADDR_0_PN:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP3:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 687 ; CHECK-NEXT:    [[C0:%.*]] = call i1 @getc()
 688 ; CHECK-NEXT:    br i1 [[C0]], label [[CONTLOOP1:%.*]], label [[OUTA_SPLIT_LOOP_EXIT3:%.*]]
 689 ; CHECK:       ContLoop1:
 690 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @getc()
 691 ; CHECK-NEXT:    br i1 [[C1]], label [[CONTLOOP2:%.*]], label [[OUTA_SPLIT_LOOP_EXIT:%.*]]
 692 ; CHECK:       ContLoop2:
 693 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @getc()
 694 ; CHECK-NEXT:    br i1 [[C2]], label [[CONTLOOP3]], label [[OUTB_SPLIT_LOOP_EXIT1:%.*]]
 695 ; CHECK:       ContLoop3:
 696 ; CHECK-NEXT:    [[C3:%.*]] = call i1 @getc()
 697 ; CHECK-NEXT:    [[DEC]] = add i32 [[N_ADDR_0_PN]], -1
 698 ; CHECK-NEXT:    br i1 [[C3]], label [[LOOP]], label [[OUTB_SPLIT_LOOP_EXIT:%.*]]
 699 ; CHECK:       OutA.split.loop.exit:
 700 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP1]] ]
 701 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA]]
 702 ; CHECK-NEXT:    br label [[OUTA:%.*]]
 703 ; CHECK:       OutA.split.loop.exit3:
 704 ; CHECK-NEXT:    [[TMP1_PH4:%.*]] = phi i32 [ [[N2:%.*]], [[LOOP]] ]
 705 ; CHECK-NEXT:    br label [[OUTA]]
 706 ; CHECK:       OutA:
 707 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[SINK_MUL_LE]], [[OUTA_SPLIT_LOOP_EXIT]] ], [ [[TMP1_PH4]], [[OUTA_SPLIT_LOOP_EXIT3]] ]
 708 ; CHECK-NEXT:    br label [[OUT12:%.*]]
 709 ; CHECK:       OutB.split.loop.exit:
 710 ; CHECK-NEXT:    [[TMP2_PH:%.*]] = phi i32 [ [[DEC]], [[CONTLOOP3]] ]
 711 ; CHECK-NEXT:    br label [[OUTB:%.*]]
 712 ; CHECK:       OutB.split.loop.exit1:
 713 ; CHECK-NEXT:    [[N_ADDR_0_PN_LCSSA6:%.*]] = phi i32 [ [[N_ADDR_0_PN]], [[CONTLOOP2]] ]
 714 ; CHECK-NEXT:    [[SINK_MUL_LE5:%.*]] = mul i32 [[N]], [[N_ADDR_0_PN_LCSSA6]]
 715 ; CHECK-NEXT:    br label [[OUTB]]
 716 ; CHECK:       OutB:
 717 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ [[TMP2_PH]], [[OUTB_SPLIT_LOOP_EXIT]] ], [ [[SINK_MUL_LE5]], [[OUTB_SPLIT_LOOP_EXIT1]] ]
 718 ; CHECK-NEXT:    br label [[OUT12]]
 719 ; CHECK:       Out12:
 720 ; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[TMP1]], [[OUTA]] ], [ [[TMP2]], [[OUTB]] ]
 721 ; CHECK-NEXT:    ret i32 [[TMP]]
 722 ;
 723 Entry:
 724   br label %Loop
 725 Loop:
 726   %N_addr.0.pn = phi i32 [ %dec, %ContLoop3 ], [ %N, %Entry ]
 727   %sink.mul = mul i32 %N, %N_addr.0.pn
 728   %c0 = call i1 @getc()
 729   br i1 %c0 , label %ContLoop1, label %OutA
 730 ContLoop1:
 731   %c1 = call i1 @getc()
 732   br i1 %c1, label %ContLoop2, label %OutA
 733
 734 ContLoop2:
 735   %c2 = call i1 @getc()
 736   br i1 %c2, label %ContLoop3, label %OutB
 737 ContLoop3:
 738   %c3 = call i1 @getc()
 739   %dec = add i32 %N_addr.0.pn, -1
 740   br i1 %c3, label %Loop, label %OutB
 741 OutA:
 742   %tmp1 = phi i32 [%sink.mul, %ContLoop1], [%N2, %Loop]
 743   br label %Out12
 744 OutB:
 745   %tmp2 = phi i32 [%sink.mul, %ContLoop2], [%dec, %ContLoop3]
 746   br label %Out12
 747 Out12:
 748   %tmp = phi i32 [%tmp1, %OutA], [%tmp2, %OutB]
 749   ret i32 %tmp
 750 }
 751
 752
 753 ; Sink a sinkable instruction through both trivially and non-trivially replacable PHIs.
 754 define i32 @test18(i32 %N, i32 %N2) {
 755 ; CHECK-LABEL: @test18(
 756 ; CHECK-NEXT:  Entry:
 757 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 758 ; CHECK:       Loop:
 759 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[DEC:%.*]], [[CONTLOOP:%.*]] ], [ [[N:%.*]], [[ENTRY:%.*]] ]
 760 ; CHECK-NEXT:    [[C0:%.*]] = call i1 @getc()
 761 ; CHECK-NEXT:    br i1 [[C0]], label [[CONTLOOP]], label [[OUT12_SPLIT_LOOP_EXIT1:%.*]]
 762 ; CHECK:       ContLoop:
 763 ; CHECK-NEXT:    [[DEC]] = add i32 [[IV]], -1
 764 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @getc()
 765 ; CHECK-NEXT:    br i1 [[C1]], label [[LOOP]], label [[OUT12_SPLIT_LOOP_EXIT:%.*]]
 766 ; CHECK:       Out12.split.loop.exit:
 767 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[CONTLOOP]] ]
 768 ; CHECK-NEXT:    [[TMP2_PH:%.*]] = phi i32 [ [[DEC]], [[CONTLOOP]] ]
 769 ; CHECK-NEXT:    [[SINK_MUL_LE:%.*]] = mul i32 [[N]], [[IV_LCSSA]]
 770 ; CHECK-NEXT:    [[SINK_SUB_LE4:%.*]] = sub i32 [[SINK_MUL_LE]], [[N2:%.*]]
 771 ; CHECK-NEXT:    br label [[OUT12:%.*]]
 772 ; CHECK:       Out12.split.loop.exit1:
 773 ; CHECK-NEXT:    [[IV_LCSSA7:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
 774 ; CHECK-NEXT:    [[SINK_MUL_LE6:%.*]] = mul i32 [[N]], [[IV_LCSSA7]]
 775 ; CHECK-NEXT:    [[SINK_SUB_LE:%.*]] = sub i32 [[SINK_MUL_LE6]], [[N2]]
 776 ; CHECK-NEXT:    br label [[OUT12]]
 777 ; CHECK:       Out12:
 778 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[SINK_SUB_LE4]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
 779 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ [[TMP2_PH]], [[OUT12_SPLIT_LOOP_EXIT]] ], [ [[SINK_SUB_LE]], [[OUT12_SPLIT_LOOP_EXIT1]] ]
 780 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP1]], [[TMP2]]
 781 ; CHECK-NEXT:    ret i32 [[ADD]]
 782 ;
 783 Entry:
 784   br label %Loop
 785 Loop:
 786   %iv = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 787   %sink.mul = mul i32 %N, %iv
 788   %sink.sub = sub i32 %sink.mul, %N2
 789   %c0 = call i1 @getc()
 790   br i1 %c0, label %ContLoop, label %Out12
 791 ContLoop:
 792   %dec = add i32 %iv, -1
 793   %c1 = call i1 @getc()
 794   br i1 %c1, label %Loop, label %Out12
 795 Out12:
 796   %tmp1 = phi i32 [%sink.sub, %ContLoop], [%sink.sub, %Loop]
 797   %tmp2 = phi i32 [%dec, %ContLoop], [%sink.sub, %Loop]
 798   %add = add i32 %tmp1, %tmp2
 799   ret i32 %add
 800 }
 801
 802 ; Do not sink an instruction through a non-trivially replacable PHI, to avoid
 803 ; assert while splitting predecessors, if the terminator of predecessor is an
 804 ; indirectbr.
 805 define i32 @test19(i1 %cond, i1 %cond2, i8* %address, i32 %v1) nounwind {
 806 ; CHECK-LABEL: @test19(
 807 ; CHECK-NEXT:  entry:
 808 ; CHECK-NEXT:    [[INDIRECT_GOTO_DEST:%.*]] = select i1 [[COND:%.*]], i8* blockaddress(@test19, [[EXIT:%.*]]), i8* [[ADDRESS:%.*]]
 809 ; CHECK-NEXT:    [[INDIRECT_GOTO_DEST2:%.*]] = select i1 [[COND2:%.*]], i8* blockaddress(@test19, [[EXIT]]), i8* [[ADDRESS]]
 810 ; CHECK-NEXT:    br label [[L0:%.*]]
 811 ; CHECK:       L0:
 812 ; CHECK-NEXT:    [[V2:%.*]] = call i32 @getv()
 813 ; CHECK-NEXT:    [[SINKABLE:%.*]] = mul i32 [[V1:%.*]], [[V2]]
 814 ; CHECK-NEXT:    [[SINKABLE2:%.*]] = add i32 [[V1]], [[V2]]
 815 ; CHECK-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST]], [label [[L1:%.*]], label %exit]
 816 ; CHECK:       L1:
 817 ; CHECK-NEXT:    indirectbr i8* [[INDIRECT_GOTO_DEST2]], [label [[L0]], label %exit]
 818 ; CHECK:       exit:
 819 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SINKABLE]], [[L0]] ], [ [[SINKABLE2]], [[L1]] ]
 820 ; CHECK-NEXT:    ret i32 [[R]]
 821 ;
 822 entry:
 823   br label %L0
 824 L0:
 825   %indirect.goto.dest = select i1 %cond, i8* blockaddress(@test19, %exit), i8* %address
 826   %v2 = call i32 @getv()
 827   %sinkable = mul i32 %v1, %v2
 828   %sinkable2 = add i32 %v1, %v2
 829   indirectbr i8* %indirect.goto.dest, [label %L1, label %exit]
 830
 831 L1:
 832   %indirect.goto.dest2 = select i1 %cond2, i8* blockaddress(@test19, %exit), i8* %address
 833   indirectbr i8* %indirect.goto.dest2, [label %L0, label %exit]
 834
 835 exit:
 836   %r = phi i32 [%sinkable, %L0], [%sinkable2, %L1]
 837   ret i32 %r
 838 }
 839
 840
 841 ; Do not sink through a non-trivially replacable PHI if splitting predecessors
 842 ; not allowed in SplitBlockPredecessors().
 843 define void @test20(i32* %s, i1 %b, i32 %v1, i32 %v2) personality i32 (...)* @__CxxFrameHandler3 {
 844 ; CHECK-LABEL: @test20(
 845 ; CHECK-NEXT:  entry:
 846 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 847 ; CHECK:       while.cond:
 848 ; CHECK-NEXT:    [[V:%.*]] = call i32 @getv()
 849 ; CHECK-NEXT:    [[SINKABLE:%.*]] = mul i32 [[V]], [[V2:%.*]]
 850 ; CHECK-NEXT:    [[SINKABLE2:%.*]] = add i32 [[V]], [[V2]]
 851 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[TRY_CONT:%.*]], label [[WHILE_BODY:%.*]]
 852 ; CHECK:       while.body:
 853 ; CHECK-NEXT:    invoke void @may_throw()
 854 ; CHECK-NEXT:    to label [[WHILE_BODY2:%.*]] unwind label [[CATCH_DISPATCH:%.*]]
 855 ; CHECK:       while.body2:
 856 ; CHECK-NEXT:    invoke void @may_throw2()
 857 ; CHECK-NEXT:    to label [[WHILE_COND]] unwind label [[CATCH_DISPATCH]]
 858 ; CHECK:       catch.dispatch:
 859 ; CHECK-NEXT:    [[DOTLCSSA1:%.*]] = phi i32 [ [[SINKABLE]], [[WHILE_BODY]] ], [ [[SINKABLE2]], [[WHILE_BODY2]] ]
 860 ; CHECK-NEXT:    [[CP:%.*]] = cleanuppad within none []
 861 ; CHECK-NEXT:    store i32 [[DOTLCSSA1]], i32* [[S:%.*]], align 4
 862 ; CHECK-NEXT:    cleanupret from [[CP]] unwind to caller
 863 ; CHECK:       try.cont:
 864 ; CHECK-NEXT:    ret void
 865 ;
 866 entry:
 867   br label %while.cond
 868 while.cond:
 869   %v = call i32 @getv()
 870   %sinkable = mul i32 %v, %v2
 871   %sinkable2 = add  i32 %v, %v2
 872   br i1 %b, label %try.cont, label %while.body
 873 while.body:
 874   invoke void @may_throw()
 875   to label %while.body2 unwind label %catch.dispatch
 876 while.body2:
 877   invoke void @may_throw2()
 878   to label %while.cond unwind label %catch.dispatch
 879 catch.dispatch:
 880   %.lcssa1 = phi i32 [ %sinkable, %while.body ], [ %sinkable2, %while.body2 ]
 881   %cp = cleanuppad within none []
 882   store i32 %.lcssa1, i32* %s
 883   cleanupret from %cp unwind to caller
 884 try.cont:
 885   ret void
 886 }
 887
 888 ; The sinkable call should be sunk into an exit block split. After splitting
 889 ; the exit block, BlockColor for new blocks should be added properly so
 890 ; that we should be able to access valid ColorVector.
 891 define i32 @test21_pr36184(i8* %P) personality i32 (...)* @__CxxFrameHandler3 {
 892 ; CHECK-LABEL: @test21_pr36184(
 893 ; CHECK-NEXT:  entry:
 894 ; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
 895 ; CHECK:       loop.ph:
 896 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 897 ; CHECK:       Loop:
 898 ; CHECK-NEXT:    br i1 false, label [[CONTLOOP:%.*]], label [[OUT_SPLIT_LOOP_EXIT1:%.*]]
 899 ; CHECK:       ContLoop:
 900 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[OUT_SPLIT_LOOP_EXIT:%.*]]
 901 ; CHECK:       Out.split.loop.exit:
 902 ; CHECK-NEXT:    [[IDX_PH:%.*]] = phi i32 [ 0, [[CONTLOOP]] ]
 903 ; CHECK-NEXT:    br label [[OUT:%.*]]
 904 ; CHECK:       Out.split.loop.exit1:
 905 ; CHECK-NEXT:    [[SINKABLECALL_LE:%.*]] = call i32 @strlen(i8* [[P:%.*]]) #[[ATTR3]]
 906 ; CHECK-NEXT:    br label [[OUT]]
 907 ; CHECK:       Out:
 908 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_PH]], [[OUT_SPLIT_LOOP_EXIT]] ], [ [[SINKABLECALL_LE]], [[OUT_SPLIT_LOOP_EXIT1]] ]
 909 ; CHECK-NEXT:    ret i32 [[IDX]]
 910 ;
 911 entry:
 912   br label %loop.ph
 913
 914 loop.ph:
 915   br label %Loop
 916
 917 Loop:
 918   %sinkableCall = call i32 @strlen( i8* %P ) readonly
 919   br i1 undef, label %ContLoop, label %Out
 920
 921 ContLoop:
 922   br i1 undef, label %Loop, label %Out
 923
 924 Out:
 925   %idx = phi i32 [ %sinkableCall, %Loop ], [0, %ContLoop ]
 926   ret i32 %idx
 927 }
 928
 929 ; We do not support splitting a landingpad block if BlockColors is not empty.
 930 define void @test22(i1 %b, i32 %v1, i32 %v2) personality i32 (...)* @__CxxFrameHandler3 {
 931 ; CHECK-LABEL: @test22(
 932 ; CHECK-NEXT:  entry:
 933 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 934 ; CHECK:       while.cond:
 935 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[TRY_CONT:%.*]], label [[WHILE_BODY:%.*]]
 936 ; CHECK:       while.body:
 937 ; CHECK-NEXT:    invoke void @may_throw()
 938 ; CHECK-NEXT:    to label [[WHILE_BODY2:%.*]] unwind label [[LPADBB:%.*]]
 939 ; CHECK:       while.body2:
 940 ; CHECK-NEXT:    [[V:%.*]] = call i32 @getv()
 941 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[V]], [[V2:%.*]]
 942 ; CHECK-NEXT:    invoke void @may_throw2()
 943 ; CHECK-NEXT:    to label [[WHILE_COND]] unwind label [[LPADBB]]
 944 ; CHECK:       lpadBB:
 945 ; CHECK-NEXT:    [[DOTLCSSA1:%.*]] = phi i32 [ 0, [[WHILE_BODY]] ], [ [[MUL]], [[WHILE_BODY2]] ]
 946 ; CHECK-NEXT:    [[TMP0:%.*]] = landingpad { i8*, i32 }
 947 ; CHECK-NEXT:    catch i8* null
 948 ; CHECK-NEXT:    br label [[LPADBBSUCC1:%.*]]
 949 ; CHECK:       lpadBBSucc1:
 950 ; CHECK-NEXT:    ret void
 951 ; CHECK:       try.cont:
 952 ; CHECK-NEXT:    ret void
 953 ;
 954 entry:
 955   br label %while.cond
 956 while.cond:
 957   br i1 %b, label %try.cont, label %while.body
 958
 959 while.body:
 960   invoke void @may_throw()
 961   to label %while.body2 unwind label %lpadBB
 962
 963 while.body2:
 964   %v = call i32 @getv()
 965   %mul = mul i32 %v, %v2
 966   invoke void @may_throw2()
 967   to label %while.cond unwind label %lpadBB
 968 lpadBB:
 969   %.lcssa1 = phi i32 [ 0, %while.body ], [ %mul, %while.body2 ]
 970   landingpad { i8*, i32 }
 971   catch i8* null
 972   br label %lpadBBSucc1
 973
 974 lpadBBSucc1:
 975   ret void
 976
 977 try.cont:
 978   ret void
 979 }
 980
 981 define i32 @not_willreturn(i8* %p) {
 982 ; CHECK-LABEL: @not_willreturn(
 983 ; CHECK-NEXT:    [[X:%.*]] = call i32 @getv() #[[ATTR5:[0-9]+]]
 984 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 985 ; CHECK:       loop:
 986 ; CHECK-NEXT:    store volatile i8 0, i8* [[P:%.*]], align 1
 987 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[OUT:%.*]]
 988 ; CHECK:       out:
 989 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[LOOP]] ]
 990 ; CHECK-NEXT:    ret i32 [[X_LCSSA]]
 991 ;
 992   br label %loop
 993
 994 loop:
 995   %x = call i32 @getv() nounwind readnone
 996   store volatile i8 0, i8* %p
 997   br i1 true, label %loop, label %out
 998
 999 out:
1000   ret i32 %x
1001 }
1002
1003 declare void @may_throw()
1004 declare void @may_throw2()
1005 declare i32 @__CxxFrameHandler3(...)
1006 declare i32 @getv()
1007 declare i1 @getc()
1008 declare void @f(i32*)
1009 declare void @g()