test/Transforms/LICM/store-hoisting.ll

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