test/Transforms/LICM/loopsink.ll

   1 ; RUN: opt -S -loop-sink < %s | FileCheck %s
   2 ; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
   3
   4 @g = global i32 0, align 4
   5
   6 ;     b1
   7 ;    /  \
   8 ;   b2  b6
   9 ;  /  \  |
  10 ; b3  b4 |
  11 ;  \  /  |
  12 ;   b5   |
  13 ;    \  /
  14 ;     b7
  15 ; preheader: 1000
  16 ; b2: 15
  17 ; b3: 7
  18 ; b4: 7
  19 ; Sink load to b2
  20 ; CHECK: t1
  21 ; CHECK: .b2:
  22 ; CHECK: load i32, i32* @g
  23 ; CHECK: .b3:
  24 ; CHECK-NOT:  load i32, i32* @g
  25 define i32 @t1(i32, i32) #0 !prof !0 {
  26   %3 = icmp eq i32 %1, 0
  27   br i1 %3, label %.exit, label %.preheader
  28
  29 .preheader:
  30   %invariant = load i32, i32* @g
  31   br label %.b1
  32
  33 .b1:
  34   %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
  35   %c1 = icmp sgt i32 %iv, %0
  36   br i1 %c1, label %.b2, label %.b6, !prof !1
  37
  38 .b2:
  39   %c2 = icmp sgt i32 %iv, 1
  40   br i1 %c2, label %.b3, label %.b4
  41
  42 .b3:
  43   %t3 = sub nsw i32 %invariant, %iv
  44   br label %.b5
  45
  46 .b4:
  47   %t4 = add nsw i32 %invariant, %iv
  48   br label %.b5
  49
  50 .b5:
  51   %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
  52   %t5 = mul nsw i32 %p5, 5
  53   br label %.b7
  54
  55 .b6:
  56   %t6 = add nsw i32 %iv, 100
  57   br label %.b7
  58
  59 .b7:
  60   %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
  61   %t7 = add nuw nsw i32 %iv, 1
  62   %c7 = icmp eq i32 %t7, %p7
  63   br i1 %c7, label %.b1, label %.exit, !prof !3
  64
  65 .exit:
  66   ret i32 10
  67 }
  68
  69 ;     b1
  70 ;    /  \
  71 ;   b2  b6
  72 ;  /  \  |
  73 ; b3  b4 |
  74 ;  \  /  |
  75 ;   b5   |
  76 ;    \  /
  77 ;     b7
  78 ; preheader: 500
  79 ; b1: 16016
  80 ; b3: 8
  81 ; b6: 8
  82 ; Sink load to b3 and b6
  83 ; CHECK: t2
  84 ; CHECK: .preheader:
  85 ; CHECK-NOT: load i32, i32* @g
  86 ; CHECK: .b3:
  87 ; CHECK: load i32, i32* @g
  88 ; CHECK: .b4:
  89 ; CHECK: .b6:
  90 ; CHECK: load i32, i32* @g
  91 ; CHECK: .b7:
  92 define i32 @t2(i32, i32) #0 !prof !0 {
  93   %3 = icmp eq i32 %1, 0
  94   br i1 %3, label %.exit, label %.preheader
  95
  96 .preheader:
  97   %invariant = load i32, i32* @g
  98   br label %.b1
  99
 100 .b1:
 101   %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
 102   %c1 = icmp sgt i32 %iv, %0
 103   br i1 %c1, label %.b2, label %.b6, !prof !2
 104
 105 .b2:
 106   %c2 = icmp sgt i32 %iv, 1
 107   br i1 %c2, label %.b3, label %.b4, !prof !1
 108
 109 .b3:
 110   %t3 = sub nsw i32 %invariant, %iv
 111   br label %.b5
 112
 113 .b4:
 114   %t4 = add nsw i32 5, %iv
 115   br label %.b5
 116
 117 .b5:
 118   %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
 119   %t5 = mul nsw i32 %p5, 5
 120   br label %.b7
 121
 122 .b6:
 123   %t6 = add nsw i32 %iv, %invariant
 124   br label %.b7
 125
 126 .b7:
 127   %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
 128   %t7 = add nuw nsw i32 %iv, 1
 129   %c7 = icmp eq i32 %t7, %p7
 130   br i1 %c7, label %.b1, label %.exit, !prof !3
 131
 132 .exit:
 133   ret i32 10
 134 }
 135
 136 ;     b1
 137 ;    /  \
 138 ;   b2  b6
 139 ;  /  \  |
 140 ; b3  b4 |
 141 ;  \  /  |
 142 ;   b5   |
 143 ;    \  /
 144 ;     b7
 145 ; preheader: 500
 146 ; b3: 8
 147 ; b5: 16008
 148 ; Do not sink load from preheader.
 149 ; CHECK: t3
 150 ; CHECK: .preheader:
 151 ; CHECK: load i32, i32* @g
 152 ; CHECK: .b1:
 153 ; CHECK-NOT: load i32, i32* @g
 154 define i32 @t3(i32, i32) #0 !prof !0 {
 155   %3 = icmp eq i32 %1, 0
 156   br i1 %3, label %.exit, label %.preheader
 157
 158 .preheader:
 159   %invariant = load i32, i32* @g
 160   br label %.b1
 161
 162 .b1:
 163   %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
 164   %c1 = icmp sgt i32 %iv, %0
 165   br i1 %c1, label %.b2, label %.b6, !prof !2
 166
 167 .b2:
 168   %c2 = icmp sgt i32 %iv, 1
 169   br i1 %c2, label %.b3, label %.b4, !prof !1
 170
 171 .b3:
 172   %t3 = sub nsw i32 %invariant, %iv
 173   br label %.b5
 174
 175 .b4:
 176   %t4 = add nsw i32 5, %iv
 177   br label %.b5
 178
 179 .b5:
 180   %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
 181   %t5 = mul nsw i32 %p5, %invariant
 182   br label %.b7
 183
 184 .b6:
 185   %t6 = add nsw i32 %iv, 5
 186   br label %.b7
 187
 188 .b7:
 189   %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
 190   %t7 = add nuw nsw i32 %iv, 1
 191   %c7 = icmp eq i32 %t7, %p7
 192   br i1 %c7, label %.b1, label %.exit, !prof !3
 193
 194 .exit:
 195   ret i32 10
 196 }
 197
 198 ; For single-BB loop with <=1 avg trip count, sink load to b1
 199 ; CHECK: t4
 200 ; CHECK: .preheader:
 201 ; CHECK-NOT: load i32, i32* @g
 202 ; CHECK: .b1:
 203 ; CHECK: load i32, i32* @g
 204 ; CHECK: .exit:
 205 define i32 @t4(i32, i32) #0 !prof !0 {
 206 .preheader:
 207   %invariant = load i32, i32* @g
 208   br label %.b1
 209
 210 .b1:
 211   %iv = phi i32 [ %t1, %.b1 ], [ 0, %.preheader ]
 212   %t1 = add nsw i32 %invariant, %iv
 213   %c1 = icmp sgt i32 %iv, %0
 214   br i1 %c1, label %.b1, label %.exit, !prof !1
 215
 216 .exit:
 217   ret i32 10
 218 }
 219
 220 ;     b1
 221 ;    /  \
 222 ;   b2  b6
 223 ;  /  \  |
 224 ; b3  b4 |
 225 ;  \  /  |
 226 ;   b5   |
 227 ;    \  /
 228 ;     b7
 229 ; preheader: 1000
 230 ; b2: 15
 231 ; b3: 7
 232 ; b4: 7
 233 ; There is alias store in loop, do not sink load
 234 ; CHECK: t5
 235 ; CHECK: .preheader:
 236 ; CHECK: load i32, i32* @g
 237 ; CHECK: .b1:
 238 ; CHECK-NOT: load i32, i32* @g
 239 define i32 @t5(i32, i32*) #0 !prof !0 {
 240   %3 = icmp eq i32 %0, 0
 241   br i1 %3, label %.exit, label %.preheader
 242
 243 .preheader:
 244   %invariant = load i32, i32* @g
 245   br label %.b1
 246
 247 .b1:
 248   %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
 249   %c1 = icmp sgt i32 %iv, %0
 250   br i1 %c1, label %.b2, label %.b6, !prof !1
 251
 252 .b2:
 253   %c2 = icmp sgt i32 %iv, 1
 254   br i1 %c2, label %.b3, label %.b4
 255
 256 .b3:
 257   %t3 = sub nsw i32 %invariant, %iv
 258   br label %.b5
 259
 260 .b4:
 261   %t4 = add nsw i32 %invariant, %iv
 262   br label %.b5
 263
 264 .b5:
 265   %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
 266   %t5 = mul nsw i32 %p5, 5
 267   br label %.b7
 268
 269 .b6:
 270   %t6 = call i32 @foo()
 271   br label %.b7
 272
 273 .b7:
 274   %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
 275   %t7 = add nuw nsw i32 %iv, 1
 276   %c7 = icmp eq i32 %t7, %p7
 277   br i1 %c7, label %.b1, label %.exit, !prof !3
 278
 279 .exit:
 280   ret i32 10
 281 }
 282
 283 ;     b1
 284 ;    /  \
 285 ;   b2  b6
 286 ;  /  \  |
 287 ; b3  b4 |
 288 ;  \  /  |
 289 ;   b5   |
 290 ;    \  /
 291 ;     b7
 292 ; preheader: 1000
 293 ; b2: 15
 294 ; b3: 7
 295 ; b4: 7
 296 ; Regardless of aliasing store in loop this load from constant memory can be sunk.
 297 ; CHECK: t5_const_memory
 298 ; CHECK: .preheader:
 299 ; CHECK-NOT: load i32, i32* @g_const
 300 ; CHECK: .b2:
 301 ; CHECK: load i32, i32* @g_const
 302 ; CHECK: br i1 %c2, label %.b3, label %.b4
 303 define i32 @t5_const_memory(i32, i32*) #0 !prof !0 {
 304   %3 = icmp eq i32 %0, 0
 305   br i1 %3, label %.exit, label %.preheader
 306
 307 .preheader:
 308   %invariant = load i32, i32* @g_const
 309   br label %.b1
 310
 311 .b1:
 312   %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
 313   %c1 = icmp sgt i32 %iv, %0
 314   br i1 %c1, label %.b2, label %.b6, !prof !1
 315
 316 .b2:
 317   %c2 = icmp sgt i32 %iv, 1
 318   br i1 %c2, label %.b3, label %.b4
 319
 320 .b3:
 321   %t3 = sub nsw i32 %invariant, %iv
 322   br label %.b5
 323
 324 .b4:
 325   %t4 = add nsw i32 %invariant, %iv
 326   br label %.b5
 327
 328 .b5:
 329   %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
 330   %t5 = mul nsw i32 %p5, 5
 331   br label %.b7
 332
 333 .b6:
 334   %t6 = call i32 @foo()
 335   br label %.b7
 336
 337 .b7:
 338   %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
 339   %t7 = add nuw nsw i32 %iv, 1
 340   %c7 = icmp eq i32 %t7, %p7
 341   br i1 %c7, label %.b1, label %.exit, !prof !3
 342
 343 .exit:
 344   ret i32 10
 345 }
 346
 347 ;     b1
 348 ;    /  \
 349 ;   b2  b3
 350 ;    \  /
 351 ;     b4
 352 ; preheader: 1000
 353 ; b2: 15
 354 ; b3: 7
 355 ; Do not sink unordered atomic load to b2
 356 ; CHECK: t6
 357 ; CHECK: .preheader:
 358 ; CHECK:  load atomic i32, i32* @g unordered, align 4
 359 ; CHECK: .b2:
 360 ; CHECK-NOT: load atomic i32, i32* @g unordered, align 4
 361 define i32 @t6(i32, i32) #0 !prof !0 {
 362   %3 = icmp eq i32 %1, 0
 363   br i1 %3, label %.exit, label %.preheader
 364
 365 .preheader:
 366   %invariant = load atomic i32, i32* @g unordered, align 4
 367   br label %.b1
 368
 369 .b1:
 370   %iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]
 371   %c1 = icmp sgt i32 %iv, %0
 372   br i1 %c1, label %.b2, label %.b3, !prof !1
 373
 374 .b2:
 375   %t1 = add nsw i32 %invariant, %iv
 376   br label %.b4
 377
 378 .b3:
 379   %t2 = add nsw i32 %iv, 100
 380   br label %.b4
 381
 382 .b4:
 383   %p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]
 384   %t3 = add nuw nsw i32 %iv, 1
 385   %c2 = icmp eq i32 %t3, %p1
 386   br i1 %c2, label %.b1, label %.exit, !prof !3
 387
 388 .exit:
 389   ret i32 10
 390 }
 391
 392 @g_const = constant i32 0, align 4
 393
 394 ;     b1
 395 ;    /  \
 396 ;   b2  b3
 397 ;    \  /
 398 ;     b4
 399 ; preheader: 1000
 400 ; b2: 0.5
 401 ; b3: 999.5
 402 ; Sink unordered atomic load to b2. It is allowed to sink into loop unordered
 403 ; load from constant.
 404 ; CHECK: t7
 405 ; CHECK: .preheader:
 406 ; CHECK-NOT:  load atomic i32, i32* @g_const unordered, align 4
 407 ; CHECK: .b2:
 408 ; CHECK: load atomic i32, i32* @g_const unordered, align 4
 409 define i32 @t7(i32, i32) #0 !prof !0 {
 410   %3 = icmp eq i32 %1, 0
 411   br i1 %3, label %.exit, label %.preheader
 412
 413 .preheader:
 414   %invariant = load atomic i32, i32* @g_const unordered, align 4
 415   br label %.b1
 416
 417 .b1:
 418   %iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]
 419   %c1 = icmp sgt i32 %iv, %0
 420   br i1 %c1, label %.b2, label %.b3, !prof !1
 421
 422 .b2:
 423   %t1 = add nsw i32 %invariant, %iv
 424   br label %.b4
 425
 426 .b3:
 427   %t2 = add nsw i32 %iv, 100
 428   br label %.b4
 429
 430 .b4:
 431   %p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]
 432   %t3 = add nuw nsw i32 %iv, 1
 433   %c2 = icmp eq i32 %t3, %p1
 434   br i1 %c2, label %.b1, label %.exit, !prof !3
 435
 436 .exit:
 437   ret i32 10
 438 }
 439
 440 declare i32 @foo()
 441
 442 !0 = !{!"function_entry_count", i64 1}
 443 !1 = !{!"branch_weights", i32 1, i32 2000}
 444 !2 = !{!"branch_weights", i32 2000, i32 1}
 445 !3 = !{!"branch_weights", i32 100, i32 1}