test/Transforms/LICM/sinking.ll

   1 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s
   2
   3 declare i32 @strlen(i8*) readonly nounwind
   4
   5 declare void @foo()
   6
   7 ; Sink readonly function.
   8 define i32 @test1(i8* %P) {
   9         br label %Loop
  10
  11 Loop:           ; preds = %Loop, %0
  12         %A = call i32 @strlen( i8* %P ) readonly
  13         br i1 false, label %Loop, label %Out
  14
  15 Out:            ; preds = %Loop
  16         ret i32 %A
  17 ; CHECK-LABEL: @test1(
  18 ; CHECK: Out:
  19 ; CHECK-NEXT: call i32 @strlen
  20 ; CHECK-NEXT: ret i32 %A
  21 }
  22
  23 declare double @sin(double) readnone nounwind
  24
  25 ; Sink readnone function out of loop with unknown memory behavior.
  26 define double @test2(double %X) {
  27         br label %Loop
  28
  29 Loop:           ; preds = %Loop, %0
  30         call void @foo( )
  31         %A = call double @sin( double %X ) readnone
  32         br i1 true, label %Loop, label %Out
  33
  34 Out:            ; preds = %Loop
  35         ret double %A
  36 ; CHECK-LABEL: @test2(
  37 ; CHECK: Out:
  38 ; CHECK-NEXT: call double @sin
  39 ; CHECK-NEXT: ret double %A
  40 }
  41
  42 ; This testcase checks to make sure the sinker does not cause problems with
  43 ; critical edges.
  44 define void @test3() {
  45 Entry:
  46         br i1 false, label %Loop, label %Exit
  47 Loop:
  48         %X = add i32 0, 1
  49         br i1 false, label %Loop, label %Exit
  50 Exit:
  51         %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ]
  52         ret void
  53
  54 ; CHECK-LABEL: @test3(
  55 ; CHECK:     Exit.loopexit:
  56 ; CHECK-NEXT:  %X.le = add i32 0, 1
  57 ; CHECK-NEXT:  br label %Exit
  58
  59 }
  60
  61 ; If the result of an instruction is only used outside of the loop, sink
  62 ; the instruction to the exit blocks instead of executing it on every
  63 ; iteration of the loop.
  64 ;
  65 define i32 @test4(i32 %N) {
  66 Entry:
  67         br label %Loop
  68 Loop:           ; preds = %Loop, %Entry
  69         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
  70         %tmp.6 = mul i32 %N, %N_addr.0.pn               ; <i32> [#uses=1]
  71         %tmp.7 = sub i32 %tmp.6, %N             ; <i32> [#uses=1]
  72         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
  73         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1            ; <i1> [#uses=1]
  74         br i1 %tmp.1, label %Loop, label %Out
  75 Out:            ; preds = %Loop
  76         ret i32 %tmp.7
  77 ; CHECK-LABEL: @test4(
  78 ; CHECK:     Out:
  79 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
  80 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
  81 ; CHECK-NEXT:  sub i32 %tmp.6.le, %N
  82 ; CHECK-NEXT:  ret i32
  83 }
  84
  85 ; To reduce register pressure, if a load is hoistable out of the loop, and the
  86 ; result of the load is only used outside of the loop, sink the load instead of
  87 ; hoisting it!
  88 ;
  89 @X = global i32 5               ; <i32*> [#uses=1]
  90
  91 define i32 @test5(i32 %N) {
  92 Entry:
  93         br label %Loop
  94 Loop:           ; preds = %Loop, %Entry
  95         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]
  96         %tmp.6 = load i32, i32* @X              ; <i32> [#uses=1]
  97         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
  98         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1            ; <i1> [#uses=1]
  99         br i1 %tmp.1, label %Loop, label %Out
 100 Out:            ; preds = %Loop
 101         ret i32 %tmp.6
 102 ; CHECK-LABEL: @test5(
 103 ; CHECK:     Out:
 104 ; CHECK-NEXT:  %tmp.6.le = load i32, i32* @X
 105 ; CHECK-NEXT:  ret i32 %tmp.6.le
 106 }
 107
 108
 109
 110 ; The loop sinker was running from the bottom of the loop to the top, causing
 111 ; it to miss opportunities to sink instructions that depended on sinking other
 112 ; instructions from the loop.  Instead they got hoisted, which is better than
 113 ; leaving them in the loop, but increases register pressure pointlessly.
 114
 115         %Ty = type { i32, i32 }
 116 @X2 = external global %Ty
 117
 118 define i32 @test6() {
 119         br label %Loop
 120 Loop:
 121         %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 122         %sunk2 = load i32, i32* %dead
 123         br i1 false, label %Loop, label %Out
 124 Out:            ; preds = %Loop
 125         ret i32 %sunk2
 126 ; CHECK-LABEL: @test6(
 127 ; CHECK:     Out:
 128 ; CHECK-NEXT:  %dead.le = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 129 ; CHECK-NEXT:  %sunk2.le = load i32, i32* %dead.le
 130 ; CHECK-NEXT:  ret i32 %sunk2.le
 131 }
 132
 133
 134
 135 ; This testcase ensures that we can sink instructions from loops with
 136 ; multiple exits.
 137 ;
 138 define i32 @test7(i32 %N, i1 %C) {
 139 Entry:
 140         br label %Loop
 141 Loop:           ; preds = %ContLoop, %Entry
 142         %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
 143         %tmp.6 = mul i32 %N, %N_addr.0.pn
 144         %tmp.7 = sub i32 %tmp.6, %N             ; <i32> [#uses=2]
 145         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 146         br i1 %C, label %ContLoop, label %Out1
 147 ContLoop:
 148         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 149         br i1 %tmp.1, label %Loop, label %Out2
 150 Out1:           ; preds = %Loop
 151         ret i32 %tmp.7
 152 Out2:           ; preds = %ContLoop
 153         ret i32 %tmp.7
 154 ; CHECK-LABEL: @test7(
 155 ; CHECK:     Out1:
 156 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 157 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 158 ; CHECK-NEXT:  sub i32 %tmp.6.le, %N
 159 ; CHECK-NEXT:  ret
 160 ; CHECK:     Out2:
 161 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 162 ; CHECK-NEXT:  mul i32 %N, %[[LCSSAPHI]]
 163 ; CHECK-NEXT:  sub i32 %tmp.6.le4, %N
 164 ; CHECK-NEXT:  ret
 165 }
 166
 167
 168 ; This testcase checks to make sure we can sink values which are only live on
 169 ; some exits out of the loop, and that we can do so without breaking dominator
 170 ; info.
 171 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
 172 Entry:
 173         br label %Loop
 174 Loop:           ; preds = %Cont, %Entry
 175         br i1 %C1, label %Cont, label %exit1
 176 Cont:           ; preds = %Loop
 177         %X = load i32, i32* %P          ; <i32> [#uses=2]
 178         store i32 %X, i32* %Q
 179         %V = add i32 %X, 1              ; <i32> [#uses=1]
 180         br i1 %C2, label %Loop, label %exit2
 181 exit1:          ; preds = %Loop
 182         ret i32 0
 183 exit2:          ; preds = %Cont
 184         ret i32 %V
 185 ; CHECK-LABEL: @test8(
 186 ; CHECK:     exit1:
 187 ; CHECK-NEXT:  ret i32 0
 188 ; CHECK:     exit2:
 189 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %X
 190 ; CHECK-NEXT:  %V.le = add i32 %[[LCSSAPHI]], 1
 191 ; CHECK-NEXT:  ret i32 %V.le
 192 }
 193
 194
 195 define void @test9() {
 196 loopentry.2.i:
 197         br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
 198 no_exit.1.i.preheader:          ; preds = %loopentry.2.i
 199         br label %no_exit.1.i
 200 no_exit.1.i:            ; preds = %endif.8.i, %no_exit.1.i.preheader
 201         br i1 false, label %return.i, label %endif.8.i
 202 endif.8.i:              ; preds = %no_exit.1.i
 203         %inc.1.i = add i32 0, 1         ; <i32> [#uses=1]
 204         br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit
 205 loopentry.3.i.preheader.loopexit:               ; preds = %endif.8.i
 206         br label %loopentry.3.i.preheader
 207 loopentry.3.i.preheader:                ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i
 208         %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ]           ; <i32> [#uses=0]
 209         ret void
 210 return.i:               ; preds = %no_exit.1.i
 211         ret void
 212
 213 ; CHECK-LABEL: @test9(
 214 ; CHECK: loopentry.3.i.preheader.loopexit:
 215 ; CHECK-NEXT:  %inc.1.i.le = add i32 0, 1
 216 ; CHECK-NEXT:  br label %loopentry.3.i.preheader
 217 }
 218
 219
 220 ; Potentially trapping instructions may be sunk as long as they are guaranteed
 221 ; to be executed.
 222 define i32 @test10(i32 %N) {
 223 Entry:
 224         br label %Loop
 225 Loop:           ; preds = %Loop, %Entry
 226         %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ]          ; <i32> [#uses=3]
 227         %tmp.6 = sdiv i32 %N, %N_addr.0.pn              ; <i32> [#uses=1]
 228         %dec = add i32 %N_addr.0.pn, -1         ; <i32> [#uses=1]
 229         %tmp.1 = icmp ne i32 %N_addr.0.pn, 0            ; <i1> [#uses=1]
 230         br i1 %tmp.1, label %Loop, label %Out
 231 Out:            ; preds = %Loop
 232         ret i32 %tmp.6
 233
 234 ; CHECK-LABEL: @test10(
 235 ; CHECK: Out:
 236 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn
 237 ; CHECK-NEXT:  %tmp.6.le = sdiv i32 %N, %[[LCSSAPHI]]
 238 ; CHECK-NEXT:  ret i32 %tmp.6.le
 239 }
 240
 241 ; Should delete, not sink, dead instructions.
 242 define void @test11() {
 243         br label %Loop
 244 Loop:
 245         %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0
 246         br i1 false, label %Loop, label %Out
 247 Out:
 248         ret void
 249 ; CHECK-LABEL: @test11(
 250 ; CHECK:     Out:
 251 ; CHECK-NEXT:  ret void
 252 }
 253
 254 @c = common global [1 x i32] zeroinitializer, align 4
 255
 256 ; Test a *many* way nested loop with multiple exit blocks both of which exit
 257 ; multiple loop nests. This exercises LCSSA corner cases.
 258 define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) {
 259 entry:
 260   br label %l1.header
 261
 262 l1.header:
 263   %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ]
 264   %arrayidx.i = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 %iv
 265   br label %l2.header
 266
 267 l2.header:
 268   %x0 = load i1, i1* %c, align 4
 269   br i1 %x0, label %l1.latch, label %l3.preheader
 270
 271 l3.preheader:
 272   br label %l3.header
 273
 274 l3.header:
 275   %x1 = load i1, i1* %d, align 4
 276   br i1 %x1, label %l2.latch, label %l4.preheader
 277
 278 l4.preheader:
 279   br label %l4.header
 280
 281 l4.header:
 282   %x2 = load i1, i1* %a
 283   br i1 %x2, label %l3.latch, label %l4.body
 284
 285 l4.body:
 286   call void @f(i32* %arrayidx.i)
 287   %x3 = load i1, i1* %b
 288   %l = trunc i64 %iv to i32
 289   br i1 %x3, label %l4.latch, label %exit
 290
 291 l4.latch:
 292   call void @g()
 293   %x4 = load i1, i1* %b, align 4
 294   br i1 %x4, label %l4.header, label %exit
 295
 296 l3.latch:
 297   br label %l3.header
 298
 299 l2.latch:
 300   br label %l2.header
 301
 302 l1.latch:
 303   %iv.next = add nsw i64 %iv, 1
 304   br label %l1.header
 305
 306 exit:
 307   %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ]
 308 ; CHECK-LABEL: @PR18753(
 309 ; CHECK:       exit:
 310 ; CHECK-NEXT:    %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
 311 ; CHECK-NEXT:    %l.le = trunc i64 %[[LCSSAPHI]] to i32
 312 ; CHECK-NEXT:    ret i32 %l.le
 313
 314   ret i32 %lcssa
 315 }
 316
 317 ; Can't sink stores out of exit blocks containing indirectbr instructions
 318 ; because loop simplify does not create dedicated exits for such blocks. Test
 319 ; that by sinking the store from lab21 to lab22, but not further.
 320 define void @test12() {
 321 ; CHECK-LABEL: @test12
 322   br label %lab4
 323
 324 lab4:
 325   br label %lab20
 326
 327 lab5:
 328   br label %lab20
 329
 330 lab6:
 331   br label %lab4
 332
 333 lab7:
 334   br i1 undef, label %lab8, label %lab13
 335
 336 lab8:
 337   br i1 undef, label %lab13, label %lab10
 338
 339 lab10:
 340   br label %lab7
 341
 342 lab13:
 343   ret void
 344
 345 lab20:
 346   br label %lab21
 347
 348 lab21:
 349 ; CHECK: lab21:
 350 ; CHECK-NOT: store
 351 ; CHECK: br i1 false, label %lab21, label %lab22
 352   store i32 36127957, i32* undef, align 4
 353   br i1 undef, label %lab21, label %lab22
 354
 355 lab22:
 356 ; CHECK: lab22:
 357 ; CHECK: store
 358 ; CHECK-NEXT: indirectbr i8* undef
 359   indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]
 360 }
 361
 362 ; Test that we don't crash when trying to sink stores and there's no preheader
 363 ; available (which is used for creating loads that may be used by the SSA
 364 ; updater)
 365 define void @test13() {
 366 ; CHECK-LABEL: @test13
 367   br label %lab59
 368
 369 lab19:
 370   br i1 undef, label %lab20, label %lab38
 371
 372 lab20:
 373   br label %lab60
 374
 375 lab21:
 376   br i1 undef, label %lab22, label %lab38
 377
 378 lab22:
 379   br label %lab38
 380
 381 lab38:
 382   ret void
 383
 384 lab59:
 385   indirectbr i8* undef, [label %lab60, label %lab38]
 386
 387 lab60:
 388 ; CHECK: lab60:
 389 ; CHECK: store
 390 ; CHECK-NEXT: indirectbr
 391   store i32 2145244101, i32* undef, align 4
 392   indirectbr i8* undef, [label %lab21, label %lab19]
 393 }
 394
 395 declare void @f(i32*)
 396
 397 declare void @g()