test/Transforms/LICM/store-hoisting.ll

   1 ; RUN: opt -S -basicaa -licm %s | FileCheck -check-prefixes=CHECK,AST %s
   2 ; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true %s | FileCheck  -check-prefixes=CHECK,MSSA %s
   3 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck -check-prefixes=CHECK,AST %s
   4
   5 define void @test(i32* %loc) {
   6 ; CHECK-LABEL: @test
   7 ; CHECK-LABEL: entry:
   8 ; CHECK: store i32 0, i32* %loc
   9 ; CHECK-LABEL: loop:
  10 entry:
  11   br label %loop
  12
  13 loop:
  14   %iv = phi i32 [0, %entry], [%iv.next, %loop]
  15   store i32 0, i32* %loc
  16   %iv.next = add i32 %iv, 1
  17   %cmp = icmp slt i32 %iv, 200
  18   br i1 %cmp, label %loop, label %exit
  19
  20 exit:
  21   ret void
  22 }
  23
  24 define void @test_multiexit(i32* %loc, i1 %earlycnd) {
  25 ; CHECK-LABEL: @test_multiexit
  26 ; CHECK-LABEL: entry:
  27 ; CHECK: store i32 0, i32* %loc
  28 ; CHECK-LABEL: loop:
  29 entry:
  30   br label %loop
  31
  32 loop:
  33   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
  34   store i32 0, i32* %loc
  35   %iv.next = add i32 %iv, 1
  36   br i1 %earlycnd, label %exit1, label %backedge
  37
  38 backedge:
  39   %cmp = icmp slt i32 %iv, 200
  40   br i1 %cmp, label %loop, label %exit2
  41
  42 exit1:
  43   ret void
  44 exit2:
  45   ret void
  46 }
  47
  48 define i32* @false_negative_2use(i32* %loc) {
  49 ; CHECK-LABEL: @false_negative_2use
  50 ; AST-LABEL: exit:
  51 ; AST: store i32 0, i32* %loc
  52 ; MSSA-LABEL: entry:
  53 ; MSSA: store i32 0, i32* %loc
  54 ; MSSA-LABEL: loop:
  55 entry:
  56   br label %loop
  57
  58 loop:
  59   %iv = phi i32 [0, %entry], [%iv.next, %loop]
  60   store i32 0, i32* %loc
  61   %iv.next = add i32 %iv, 1
  62   %cmp = icmp slt i32 %iv, 200
  63   br i1 %cmp, label %loop, label %exit
  64
  65 exit:
  66   ret i32* %loc
  67 }
  68
  69 define void @neg_lv_value(i32* %loc) {
  70 ; CHECK-LABEL: @neg_lv_value
  71 ; CHECK-LABEL: exit:
  72 ; CHECK: store i32 %iv.lcssa, i32* %loc
  73 entry:
  74   br label %loop
  75
  76 loop:
  77   %iv = phi i32 [0, %entry], [%iv.next, %loop]
  78   store i32 %iv, i32* %loc
  79   %iv.next = add i32 %iv, 1
  80   %cmp = icmp slt i32 %iv, 200
  81   br i1 %cmp, label %loop, label %exit
  82
  83 exit:
  84   ret void
  85 }
  86
  87 define void @neg_lv_addr(i32* %loc) {
  88 ; CHECK-LABEL: @neg_lv_addr
  89 ; CHECK-LABEL: loop:
  90 ; CHECK: store i32 0, i32* %p
  91 ; CHECK-LABEL: exit:
  92 entry:
  93   br label %loop
  94
  95 loop:
  96   %iv = phi i32 [0, %entry], [%iv.next, %loop]
  97   %p = getelementptr i32, i32* %loc, i32 %iv
  98   store i32 0, i32* %p
  99   %iv.next = add i32 %iv, 1
 100   %cmp = icmp slt i32 %iv, 200
 101   br i1 %cmp, label %loop, label %exit
 102
 103 exit:
 104   ret void
 105 }
 106
 107 define void @neg_mod(i32* %loc) {
 108 ; CHECK-LABEL: @neg_mod
 109 ; CHECK-LABEL: exit:
 110 ; CHECK: store i32 %iv.lcssa, i32* %loc
 111 entry:
 112   br label %loop
 113
 114 loop:
 115   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 116   store i32 0, i32* %loc
 117   store i32 %iv, i32* %loc
 118   %iv.next = add i32 %iv, 1
 119   %cmp = icmp slt i32 %iv, 200
 120   br i1 %cmp, label %loop, label %exit
 121
 122 exit:
 123   ret void
 124 }
 125
 126 ; Hoisting the store is actually valid here, as it dominates the load.
 127 define void @neg_ref(i32* %loc) {
 128 ; CHECK-LABEL: @neg_ref
 129 ; CHECK-LABEL: exit1:
 130 ; CHECK: store i32 0, i32* %loc
 131 ; CHECK-LABEL: exit2:
 132 ; CHECK: store i32 0, i32* %loc
 133 entry:
 134   br label %loop
 135
 136 loop:
 137   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
 138   store i32 0, i32* %loc
 139   %v = load i32, i32* %loc
 140   %earlycnd = icmp eq i32 %v, 198
 141   br i1 %earlycnd, label %exit1, label %backedge
 142
 143 backedge:
 144   %iv.next = add i32 %iv, 1
 145   %cmp = icmp slt i32 %iv, 200
 146   br i1 %cmp, label %loop, label %exit2
 147
 148 exit1:
 149   ret void
 150 exit2:
 151   ret void
 152 }
 153
 154 ; Hoisting the store here leads to a miscompile.
 155 define void @neg_ref2(i32* %loc) {
 156 ; CHECK-LABEL: @neg_ref2
 157 ; CHECK-LABEL: exit1:
 158 ; CHECK: store i32 0, i32* %loc
 159 ; CHECK-LABEL: exit2:
 160 ; CHECK: store i32 0, i32* %loc
 161 entry:
 162   store i32 198, i32* %loc
 163   br label %loop
 164
 165 loop:
 166   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
 167   %v = load i32, i32* %loc
 168   store i32 0, i32* %loc
 169   %earlycnd = icmp eq i32 %v, 198
 170   br i1 %earlycnd, label %exit1, label %backedge
 171
 172 backedge:
 173   %iv.next = add i32 %iv, 1
 174   %cmp = icmp slt i32 %iv, 200
 175   br i1 %cmp, label %loop, label %exit2
 176
 177 exit1:
 178   ret void
 179 exit2:
 180   ret void
 181 }
 182
 183 declare void @modref()
 184
 185 define void @neg_modref(i32* %loc) {
 186 ; CHECK-LABEL: @neg_modref
 187 ; CHECK-LABEL: loop:
 188 ; CHECK: store i32 0, i32* %loc
 189 ; CHECK-LABEL: exit:
 190 entry:
 191   br label %loop
 192
 193 loop:
 194   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 195   store i32 0, i32* %loc
 196   call void @modref()
 197   %iv.next = add i32 %iv, 1
 198   %cmp = icmp slt i32 %iv, 200
 199   br i1 %cmp, label %loop, label %exit
 200
 201 exit:
 202   ret void
 203 }
 204
 205 define void @neg_fence(i32* %loc) {
 206 ; CHECK-LABEL: @neg_fence
 207 ; CHECK-LABEL: loop:
 208 ; CHECK: store i32 0, i32* %loc
 209 ; CHECK-LABEL: exit:
 210 entry:
 211   br label %loop
 212
 213 loop:
 214   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 215   store i32 0, i32* %loc
 216   fence seq_cst
 217   %iv.next = add i32 %iv, 1
 218   %cmp = icmp slt i32 %iv, 200
 219   br i1 %cmp, label %loop, label %exit
 220
 221 exit:
 222   ret void
 223 }
 224
 225 define void @neg_volatile(i32* %loc) {
 226 ; CHECK-LABEL: @neg_volatile
 227 ; CHECK-LABEL: loop:
 228 ; CHECK: store volatile i32 0, i32* %loc
 229 ; CHECK-LABEL: exit:
 230 entry:
 231   br label %loop
 232
 233 loop:
 234   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 235   store volatile i32 0, i32* %loc
 236   %iv.next = add i32 %iv, 1
 237   %cmp = icmp slt i32 %iv, 200
 238   br i1 %cmp, label %loop, label %exit
 239
 240 exit:
 241   ret void
 242 }
 243
 244 define void @neg_release(i32* %loc) {
 245 ; CHECK-LABEL: @neg_release
 246 ; CHECK-LABEL: loop:
 247 ; CHECK: store atomic i32 0, i32* %loc release, align 4
 248 ; CHECK-LABEL: exit:
 249 entry:
 250   br label %loop
 251
 252 loop:
 253   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 254   store atomic i32 0, i32* %loc release, align 4
 255   %iv.next = add i32 %iv, 1
 256   %cmp = icmp slt i32 %iv, 200
 257   br i1 %cmp, label %loop, label %exit
 258
 259 exit:
 260   ret void
 261 }
 262
 263 define void @neg_seq_cst(i32* %loc) {
 264 ; CHECK-LABEL: @neg_seq_cst
 265 ; CHECK-LABEL: loop:
 266 ; CHECK: store atomic i32 0, i32* %loc seq_cst, align 4
 267 ; CHECK-LABEL: exit:
 268 entry:
 269   br label %loop
 270
 271 loop:
 272   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 273   store atomic i32 0, i32* %loc seq_cst, align 4
 274   %iv.next = add i32 %iv, 1
 275   %cmp = icmp slt i32 %iv, 200
 276   br i1 %cmp, label %loop, label %exit
 277
 278 exit:
 279   ret void
 280 }
 281
 282 declare void @maythrow() inaccessiblememonly
 283
 284 define void @neg_early_exit(i32* %loc) {
 285 ; CHECK-LABEL: @neg_early_exit
 286 ; CHECK-LABEL: body:
 287 ; CHECK: store i32 0, i32* %loc
 288 ; CHECK-LABEL: exit:
 289 entry:
 290   br label %loop
 291
 292 loop:
 293   %iv = phi i32 [0, %entry], [%iv.next, %body]
 294   %is_null = icmp eq i32* %loc, null
 295   br i1 %is_null, label %exit, label %body
 296 body:
 297   call void @maythrow()
 298   store i32 0, i32* %loc
 299   %iv.next = add i32 %iv, 1
 300   %cmp = icmp slt i32 %iv, 200
 301   br i1 %cmp, label %loop, label %exit
 302
 303 exit:
 304   ret void
 305 }
 306
 307 define void @neg_early_throw(i32* %loc) {
 308 ; CHECK-LABEL: @neg_early_throw
 309 ; CHECK-LABEL: loop:
 310 ; CHECK: store i32 0, i32* %loc
 311 ; CHECK-LABEL: exit:
 312 entry:
 313   br label %loop
 314
 315 loop:
 316   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 317   call void @maythrow()
 318   store i32 0, i32* %loc
 319   %iv.next = add i32 %iv, 1
 320   %cmp = icmp slt i32 %iv, 200
 321   br i1 %cmp, label %loop, label %exit
 322
 323 exit:
 324   ret void
 325 }
 326
 327 define void @test_late_throw(i32* %loc) {
 328 ; CHECK-LABEL: @test_late_throw
 329 ; CHECK-LABEL: entry:
 330 ; CHECK: store i32 0, i32* %loc
 331 ; CHECK-LABEL: loop:
 332 entry:
 333   br label %loop
 334
 335 loop:
 336   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 337   store i32 0, i32* %loc
 338   call void @maythrow()
 339   %iv.next = add i32 %iv, 1
 340   %cmp = icmp slt i32 %iv, 200
 341   br i1 %cmp, label %loop, label %exit
 342
 343 exit:
 344   ret void
 345 }
 346
 347 ; TODO: could validly hoist the store here since we know what value
 348 ; the load must observe.
 349 define i32 @test_dominated_read(i32* %loc) {
 350 ; CHECK-LABEL: @test_dominated_read
 351 ; MSSA-LABEL: entry:
 352 ; MSSA: store i32 0, i32* %loc
 353 ; MSSA-LABEL: loop:
 354 ; AST-LABEL: exit:
 355 ; AST:  store i32 0, i32* %loc
 356 entry:
 357   br label %loop
 358
 359 loop:
 360   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 361   store i32 0, i32* %loc
 362   %reload = load i32, i32* %loc
 363   %iv.next = add i32 %iv, 1
 364   %cmp = icmp slt i32 %iv, 200
 365   br i1 %cmp, label %loop, label %exit
 366
 367 exit:
 368   ret i32 %reload
 369 }
 370
 371 ; TODO: could validly hoist the store since we already hoisted the load and
 372 ; it's no longer in the loop.
 373 define i32 @test_dominating_read(i32* %loc) {
 374 ; CHECK-LABEL: @test_dominating_read
 375 ; CHECK-LABEL: exit:
 376 ; CHECK: store i32 0, i32* %loc
 377 entry:
 378   br label %loop
 379
 380 loop:
 381   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 382   %reload = load i32, i32* %loc
 383   store i32 0, i32* %loc
 384   %iv.next = add i32 %iv, 1
 385   %cmp = icmp slt i32 %iv, 200
 386   br i1 %cmp, label %loop, label %exit
 387
 388 exit:
 389   ret i32 %reload
 390 }
 391
 392 declare void @readonly() readonly
 393
 394 ; TODO: can legally hoist since value read by call is known
 395 define void @test_dominated_readonly(i32* %loc) {
 396 ; CHECK-LABEL: @test_dominated_readonly
 397 ; CHECK-LABEL: loop:
 398 ; CHECK: store i32 0, i32* %loc
 399 ; CHECK-LABEL: exit:
 400 entry:
 401   br label %loop
 402
 403 loop:
 404   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 405   store i32 0, i32* %loc
 406   call void @readonly()
 407   %iv.next = add i32 %iv, 1
 408   %cmp = icmp slt i32 %iv, 200
 409   br i1 %cmp, label %loop, label %exit
 410
 411 exit:
 412   ret void
 413 }
 414
 415 ; While technically possible to hoist the store to %loc, this runs across
 416 ; a funemental limitation of alias sets since both stores and the call are
 417 ; within the same alias set and we can't distinguish them cheaply.
 418 define void @test_aliasset_fn(i32* %loc, i32* %loc2) {
 419 ; CHECK-LABEL: @test_aliasset_fn
 420 ; CHECK-LABEL: loop:
 421 ; CHECK: store i32 0, i32* %loc
 422 ; CHECK-LABEL: exit:
 423 entry:
 424   br label %loop
 425
 426 loop:
 427   %iv = phi i32 [0, %entry], [%iv.next, %loop]
 428   store i32 0, i32* %loc
 429   call void @readonly()
 430   store i32 %iv, i32* %loc2
 431   %iv.next = add i32 %iv, 1
 432   %cmp = icmp slt i32 %iv, 200
 433   br i1 %cmp, label %loop, label %exit
 434
 435 exit:
 436   ret void
 437 }
 438
 439
 440 ; If we can't tell if the value is read before the write, we can't hoist the
 441 ; write over the potential read (since we don't know the value read)
 442 define void @neg_may_read(i32* %loc, i1 %maybe) {
 443 ; CHECK-LABEL: @neg_may_read
 444 ; CHECK-LABEL: loop:
 445 ; CHECK: store i32 0, i32* %loc
 446 ; CHECK-LABEL: exit:
 447 entry:
 448   br label %loop
 449
 450 loop:
 451   %iv = phi i32 [0, %entry], [%iv.next, %merge]
 452   ;; maybe is a placeholder for an unanalyzable condition
 453   br i1 %maybe, label %taken, label %merge
 454 taken:
 455   call void @readonly()
 456   br label %merge
 457 merge:
 458   store i32 0, i32* %loc
 459   %iv.next = add i32 %iv, 1
 460   %cmp = icmp slt i32 %iv, 200
 461   br i1 %cmp, label %loop, label %exit
 462
 463 exit:
 464   ret void
 465 }