test/Transforms/DeadStoreElimination/simple.ll

   1 ; RUN: opt < %s -basicaa -dse -S | FileCheck %s
   2 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -S | FileCheck %s
   3 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
   4
   5 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
   6 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
   7 declare void @llvm.init.trampoline(i8*, i8*, i8*)
   8
   9 define void @test1(i32* %Q, i32* %P) {
  10         %DEAD = load i32, i32* %Q
  11         store i32 %DEAD, i32* %P
  12         store i32 0, i32* %P
  13         ret void
  14 ; CHECK-LABEL: @test1(
  15 ; CHECK-NEXT: store i32 0, i32* %P
  16 ; CHECK-NEXT: ret void
  17 }
  18
  19 ; PR8576 - Should delete store of 10 even though p/q are may aliases.
  20 define void @test2(i32 *%p, i32 *%q) {
  21   store i32 10, i32* %p, align 4
  22   store i32 20, i32* %q, align 4
  23   store i32 30, i32* %p, align 4
  24   ret void
  25 ; CHECK-LABEL: @test2(
  26 ; CHECK-NEXT: store i32 20
  27 }
  28
  29
  30 ; PR8677
  31 @g = global i32 1
  32
  33 define i32 @test3(i32* %g_addr) nounwind {
  34 ; CHECK-LABEL: @test3(
  35 ; CHECK: load i32, i32* %g_addr
  36   %g_value = load i32, i32* %g_addr, align 4
  37   store i32 -1, i32* @g, align 4
  38   store i32 %g_value, i32* %g_addr, align 4
  39   %tmp3 = load i32, i32* @g, align 4
  40   ret i32 %tmp3
  41 }
  42
  43
  44 define void @test4(i32* %Q) {
  45         %a = load i32, i32* %Q
  46         store volatile i32 %a, i32* %Q
  47         ret void
  48 ; CHECK-LABEL: @test4(
  49 ; CHECK-NEXT: load i32
  50 ; CHECK-NEXT: store volatile
  51 ; CHECK-NEXT: ret void
  52 }
  53
  54 define void @test5(i32* %Q) {
  55         %a = load volatile i32, i32* %Q
  56         store i32 %a, i32* %Q
  57         ret void
  58 ; CHECK-LABEL: @test5(
  59 ; CHECK-NEXT: load volatile
  60 ; CHECK-NEXT: ret void
  61 }
  62
  63 ; Should delete store of 10 even though memset is a may-store to P (P and Q may
  64 ; alias).
  65 define void @test6(i32 *%p, i8 *%q) {
  66   store i32 10, i32* %p, align 4       ;; dead.
  67   call void @llvm.memset.p0i8.i64(i8* %q, i8 42, i64 900, i32 1, i1 false)
  68   store i32 30, i32* %p, align 4
  69   ret void
  70 ; CHECK-LABEL: @test6(
  71 ; CHECK-NEXT: call void @llvm.memset
  72 }
  73
  74 ; Should delete store of 10 even though memcpy is a may-store to P (P and Q may
  75 ; alias).
  76 define void @test7(i32 *%p, i8 *%q, i8* noalias %r) {
  77   store i32 10, i32* %p, align 4       ;; dead.
  78   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %r, i64 900, i32 1, i1 false)
  79   store i32 30, i32* %p, align 4
  80   ret void
  81 ; CHECK-LABEL: @test7(
  82 ; CHECK-NEXT: call void @llvm.memcpy
  83 }
  84
  85 ; Do not delete stores that are only partially killed.
  86 define i32 @test8() {
  87         %V = alloca i32
  88         store i32 1234567, i32* %V
  89         %V2 = bitcast i32* %V to i8*
  90         store i8 0, i8* %V2
  91         %X = load i32, i32* %V
  92         ret i32 %X
  93
  94 ; CHECK-LABEL: @test8(
  95 ; CHECK: store i32 1234567
  96 }
  97
  98
  99 ; Test for byval handling.
 100 %struct.x = type { i32, i32, i32, i32 }
 101 define void @test9(%struct.x* byval  %a) nounwind  {
 102         %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
 103         store i32 1, i32* %tmp2, align 4
 104         ret void
 105 ; CHECK-LABEL: @test9(
 106 ; CHECK-NEXT: ret void
 107 }
 108
 109 ; Test for inalloca handling.
 110 define void @test9_2(%struct.x* inalloca  %a) nounwind  {
 111         %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
 112         store i32 1, i32* %tmp2, align 4
 113         ret void
 114 ; CHECK-LABEL: @test9_2(
 115 ; CHECK-NEXT: ret void
 116 }
 117
 118 ; va_arg has fuzzy dependence, the store shouldn't be zapped.
 119 define double @test10(i8* %X) {
 120         %X_addr = alloca i8*
 121         store i8* %X, i8** %X_addr
 122         %tmp.0 = va_arg i8** %X_addr, double
 123         ret double %tmp.0
 124 ; CHECK-LABEL: @test10(
 125 ; CHECK: store
 126 }
 127
 128
 129 ; DSE should delete the dead trampoline.
 130 declare void @test11f()
 131 define void @test11() {
 132 ; CHECK-LABEL: @test11(
 133         %storage = alloca [10 x i8], align 16           ; <[10 x i8]*> [#uses=1]
 134 ; CHECK-NOT: alloca
 135         %cast = getelementptr [10 x i8], [10 x i8]* %storage, i32 0, i32 0              ; <i8*> [#uses=1]
 136         call void @llvm.init.trampoline( i8* %cast, i8* bitcast (void ()* @test11f to i8*), i8* null )          ; <i8*> [#uses=1]
 137 ; CHECK-NOT: trampoline
 138         ret void
 139 ; CHECK: ret void
 140 }
 141
 142
 143 ; PR2599 - load -> store to same address.
 144 define void @test12({ i32, i32 }* %x) nounwind  {
 145         %tmp4 = getelementptr { i32, i32 }, { i32, i32 }* %x, i32 0, i32 0
 146         %tmp5 = load i32, i32* %tmp4, align 4
 147         %tmp7 = getelementptr { i32, i32 }, { i32, i32 }* %x, i32 0, i32 1
 148         %tmp8 = load i32, i32* %tmp7, align 4
 149         %tmp17 = sub i32 0, %tmp8
 150         store i32 %tmp5, i32* %tmp4, align 4
 151         store i32 %tmp17, i32* %tmp7, align 4
 152         ret void
 153 ; CHECK-LABEL: @test12(
 154 ; CHECK-NOT: tmp5
 155 ; CHECK: ret void
 156 }
 157
 158
 159 ; %P doesn't escape, the DEAD instructions should be removed.
 160 declare void @test13f()
 161 define i32* @test13() {
 162         %p = tail call i8* @malloc(i32 4)
 163         %P = bitcast i8* %p to i32*
 164         %DEAD = load i32, i32* %P
 165         %DEAD2 = add i32 %DEAD, 1
 166         store i32 %DEAD2, i32* %P
 167         call void @test13f( )
 168         store i32 0, i32* %P
 169         ret i32* %P
 170 ; CHECK: @test13()
 171 ; CHECK-NEXT: malloc
 172 ; CHECK-NEXT: bitcast
 173 ; CHECK-NEXT: call void
 174 }
 175
 176 define i32 addrspace(1)* @test13_addrspacecast() {
 177   %p = tail call i8* @malloc(i32 4)
 178   %p.bc = bitcast i8* %p to i32*
 179   %P = addrspacecast i32* %p.bc to i32 addrspace(1)*
 180   %DEAD = load i32, i32 addrspace(1)* %P
 181   %DEAD2 = add i32 %DEAD, 1
 182   store i32 %DEAD2, i32 addrspace(1)* %P
 183   call void @test13f( )
 184   store i32 0, i32 addrspace(1)* %P
 185   ret i32 addrspace(1)* %P
 186 ; CHECK: @test13_addrspacecast()
 187 ; CHECK-NEXT: malloc
 188 ; CHECK-NEXT: bitcast
 189 ; CHECK-NEXT: addrspacecast
 190 ; CHECK-NEXT: call void
 191 }
 192
 193 declare noalias i8* @malloc(i32)
 194 declare noalias i8* @calloc(i32, i32)
 195
 196
 197 define void @test14(i32* %Q) {
 198         %P = alloca i32
 199         %DEAD = load i32, i32* %Q
 200         store i32 %DEAD, i32* %P
 201         ret void
 202
 203 ; CHECK-LABEL: @test14(
 204 ; CHECK-NEXT: ret void
 205 }
 206
 207
 208 ; PR8701
 209
 210 ;; Fully dead overwrite of memcpy.
 211 define void @test15(i8* %P, i8* %Q) nounwind ssp {
 212   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 213   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 214   ret void
 215 ; CHECK-LABEL: @test15(
 216 ; CHECK-NEXT: call void @llvm.memcpy
 217 ; CHECK-NEXT: ret
 218 }
 219
 220 ;; Full overwrite of smaller memcpy.
 221 define void @test16(i8* %P, i8* %Q) nounwind ssp {
 222   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 8, i32 1, i1 false)
 223   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 224   ret void
 225 ; CHECK-LABEL: @test16(
 226 ; CHECK-NEXT: call void @llvm.memcpy
 227 ; CHECK-NEXT: ret
 228 }
 229
 230 ;; Overwrite of memset by memcpy.
 231 define void @test17(i8* %P, i8* noalias %Q) nounwind ssp {
 232   tail call void @llvm.memset.p0i8.i64(i8* %P, i8 42, i64 8, i32 1, i1 false)
 233   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 234   ret void
 235 ; CHECK-LABEL: @test17(
 236 ; CHECK-NEXT: call void @llvm.memcpy
 237 ; CHECK-NEXT: ret
 238 }
 239
 240 ; Should not delete the volatile memset.
 241 define void @test17v(i8* %P, i8* %Q) nounwind ssp {
 242   tail call void @llvm.memset.p0i8.i64(i8* %P, i8 42, i64 8, i32 1, i1 true)
 243   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 244   ret void
 245 ; CHECK-LABEL: @test17v(
 246 ; CHECK-NEXT: call void @llvm.memset
 247 ; CHECK-NEXT: call void @llvm.memcpy
 248 ; CHECK-NEXT: ret
 249 }
 250
 251 ; PR8728
 252 ; Do not delete instruction where possible situation is:
 253 ; A = B
 254 ; A = A
 255 define void @test18(i8* %P, i8* %Q, i8* %R) nounwind ssp {
 256   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
 257   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false)
 258   ret void
 259 ; CHECK-LABEL: @test18(
 260 ; CHECK-NEXT: call void @llvm.memcpy
 261 ; CHECK-NEXT: call void @llvm.memcpy
 262 ; CHECK-NEXT: ret
 263 }
 264
 265
 266 ; The store here is not dead because the byval call reads it.
 267 declare void @test19f({i32}* byval align 4 %P)
 268
 269 define void @test19({i32} * nocapture byval align 4 %arg5) nounwind ssp {
 270 bb:
 271   %tmp7 = getelementptr inbounds {i32}, {i32}* %arg5, i32 0, i32 0
 272   store i32 912, i32* %tmp7
 273   call void @test19f({i32}* byval align 4 %arg5)
 274   ret void
 275
 276 ; CHECK-LABEL: @test19(
 277 ; CHECK: store i32 912
 278 ; CHECK: call void @test19f
 279 }
 280
 281 define void @test20() {
 282   %m = call i8* @malloc(i32 24)
 283   store i8 0, i8* %m
 284   ret void
 285 }
 286 ; CHECK-LABEL: @test20(
 287 ; CHECK-NEXT: ret void
 288
 289 ; CHECK-LABEL: @test21(
 290 define void @test21() {
 291   %m = call i8* @calloc(i32 9, i32 7)
 292   store i8 0, i8* %m
 293 ; CHECK-NEXT: ret void
 294   ret void
 295 }
 296
 297 ; CHECK-LABEL: @test22(
 298 define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
 299   %k.addr = alloca i32
 300   %m.addr = alloca i32
 301   %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
 302   store i32 0, i32* %k.addr.m.addr, align 4
 303 ; CHECK-NEXT: ret void
 304   ret void
 305 }
 306
 307 ; PR13547
 308 ; CHECK-LABEL: @test23(
 309 ; CHECK: store i8 97
 310 ; CHECK: store i8 0
 311 declare noalias i8* @strdup(i8* nocapture) nounwind
 312 define noalias i8* @test23() nounwind uwtable ssp {
 313   %x = alloca [2 x i8], align 1
 314   %arrayidx = getelementptr inbounds [2 x i8], [2 x i8]* %x, i64 0, i64 0
 315   store i8 97, i8* %arrayidx, align 1
 316   %arrayidx1 = getelementptr inbounds [2 x i8], [2 x i8]* %x, i64 0, i64 1
 317   store i8 0, i8* %arrayidx1, align 1
 318   %call = call i8* @strdup(i8* %arrayidx) nounwind
 319   ret i8* %call
 320 }
 321
 322 ; Make sure same sized store to later element is deleted
 323 ; CHECK-LABEL: @test24(
 324 ; CHECK-NOT: store i32 0
 325 ; CHECK-NOT: store i32 0
 326 ; CHECK: store i32 %b
 327 ; CHECK: store i32 %c
 328 ; CHECK: ret void
 329 define void @test24([2 x i32]* %a, i32 %b, i32 %c) nounwind {
 330   %1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 0
 331   store i32 0, i32* %1, align 4
 332   %2 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 1
 333   store i32 0, i32* %2, align 4
 334   %3 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 0
 335   store i32 %b, i32* %3, align 4
 336   %4 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 0, i64 1
 337   store i32 %c, i32* %4, align 4
 338   ret void
 339 }
 340
 341 ; Check another case like PR13547 where strdup is not like malloc.
 342 ; CHECK-LABEL: @test25(
 343 ; CHECK: load i8
 344 ; CHECK: store i8 0
 345 ; CHECK: store i8 %tmp
 346 define i8* @test25(i8* %p) nounwind {
 347   %p.4 = getelementptr i8, i8* %p, i64 4
 348   %tmp = load i8, i8* %p.4, align 1
 349   store i8 0, i8* %p.4, align 1
 350   %q = call i8* @strdup(i8* %p) nounwind optsize
 351   store i8 %tmp, i8* %p.4, align 1
 352   ret i8* %q
 353 }
 354
 355 ; Remove redundant store if loaded value is in another block.
 356 ; CHECK-LABEL: @test26(
 357 ; CHECK-NOT: store
 358 ; CHECK: ret
 359 define i32 @test26(i1 %c, i32* %p) {
 360 entry:
 361   %v = load i32, i32* %p, align 4
 362   br i1 %c, label %bb1, label %bb2
 363 bb1:
 364   br label %bb3
 365 bb2:
 366   store i32 %v, i32* %p, align 4
 367   br label %bb3
 368 bb3:
 369   ret i32 0
 370 }
 371
 372 ; Remove redundant store if loaded value is in another block.
 373 ; CHECK-LABEL: @test27(
 374 ; CHECK-NOT: store
 375 ; CHECK: ret
 376 define i32 @test27(i1 %c, i32* %p) {
 377 entry:
 378   %v = load i32, i32* %p, align 4
 379   br i1 %c, label %bb1, label %bb2
 380 bb1:
 381   br label %bb3
 382 bb2:
 383   br label %bb3
 384 bb3:
 385   store i32 %v, i32* %p, align 4
 386   ret i32 0
 387 }
 388
 389 ; Don't remove redundant store because of may-aliased store.
 390 ; CHECK-LABEL: @test28(
 391 ; CHECK: bb3:
 392 ; CHECK-NEXT: store i32 %v
 393 define i32 @test28(i1 %c, i32* %p, i32* %p2, i32 %i) {
 394 entry:
 395   %v = load i32, i32* %p, align 4
 396
 397   ; Might overwrite value at %p
 398   store i32 %i, i32* %p2, align 4
 399   br i1 %c, label %bb1, label %bb2
 400 bb1:
 401   br label %bb3
 402 bb2:
 403   br label %bb3
 404 bb3:
 405   store i32 %v, i32* %p, align 4
 406   ret i32 0
 407 }
 408
 409 ; Don't remove redundant store because of may-aliased store.
 410 ; CHECK-LABEL: @test29(
 411 ; CHECK: bb3:
 412 ; CHECK-NEXT: store i32 %v
 413 define i32 @test29(i1 %c, i32* %p, i32* %p2, i32 %i) {
 414 entry:
 415   %v = load i32, i32* %p, align 4
 416   br i1 %c, label %bb1, label %bb2
 417 bb1:
 418   br label %bb3
 419 bb2:
 420   ; Might overwrite value at %p
 421   store i32 %i, i32* %p2, align 4
 422   br label %bb3
 423 bb3:
 424   store i32 %v, i32* %p, align 4
 425   ret i32 0
 426 }
 427
 428 declare void @unknown_func()
 429
 430 ; Don't remove redundant store because of unknown call.
 431 ; CHECK-LABEL: @test30(
 432 ; CHECK: bb3:
 433 ; CHECK-NEXT: store i32 %v
 434 define i32 @test30(i1 %c, i32* %p, i32 %i) {
 435 entry:
 436   %v = load i32, i32* %p, align 4
 437   br i1 %c, label %bb1, label %bb2
 438 bb1:
 439   br label %bb3
 440 bb2:
 441   ; Might overwrite value at %p
 442   call void @unknown_func()
 443   br label %bb3
 444 bb3:
 445   store i32 %v, i32* %p, align 4
 446   ret i32 0
 447 }
 448
 449 ; Remove redundant store if loaded value is in another block inside a loop.
 450 ; CHECK-LABEL: @test31(
 451 ; CHECK-NOT: store
 452 ; CHECK: ret
 453 define i32 @test31(i1 %c, i32* %p, i32 %i) {
 454 entry:
 455   %v = load i32, i32* %p, align 4
 456   br label %bb1
 457 bb1:
 458   store i32 %v, i32* %p, align 4
 459   br i1 undef, label %bb1, label %bb2
 460 bb2:
 461   ret i32 0
 462 }
 463
 464 ; Don't remove redundant store in a loop with a may-alias store.
 465 ; CHECK-LABEL: @test32(
 466 ; CHECK: bb1:
 467 ; CHECK-NEXT: store i32 %v
 468 ; CHECK-NEXT: call void @unknown_func
 469 define i32 @test32(i1 %c, i32* %p, i32 %i) {
 470 entry:
 471   %v = load i32, i32* %p, align 4
 472   br label %bb1
 473 bb1:
 474   store i32 %v, i32* %p, align 4
 475   ; Might read and overwrite value at %p
 476   call void @unknown_func()
 477   br i1 undef, label %bb1, label %bb2
 478 bb2:
 479   ret i32 0
 480 }
 481
 482 ; Remove redundant store, which is in the lame loop as the load.
 483 ; CHECK-LABEL: @test33(
 484 ; CHECK-NOT: store
 485 ; CHECK: ret
 486 define i32 @test33(i1 %c, i32* %p, i32 %i) {
 487 entry:
 488   br label %bb1
 489 bb1:
 490   %v = load i32, i32* %p, align 4
 491   br label %bb2
 492 bb2:
 493   store i32 %v, i32* %p, align 4
 494   ; Might read and overwrite value at %p, but doesn't matter.
 495   call void @unknown_func()
 496   br i1 undef, label %bb1, label %bb3
 497 bb3:
 498   ret i32 0
 499 }
 500
 501 ; Don't remove redundant store: unknown_func could unwind
 502 ; CHECK-LABEL: @test34(
 503 ; CHECK: store i32 1
 504 ; CHECK: store i32 0
 505 ; CHECK: ret
 506 define void @test34(i32* noalias %p) {
 507   store i32 1, i32* %p
 508   call void @unknown_func()
 509   store i32 0, i32* %p
 510   ret void
 511 }
 512
 513 ; Remove redundant store even with an unwinding function in the same block
 514 ; CHECK-LABEL: @test35(
 515 ; CHECK: call void @unknown_func
 516 ; CHECK-NEXT: store i32 0
 517 ; CHECK-NEXT: ret void
 518 define void @test35(i32* noalias %p) {
 519   call void @unknown_func()
 520   store i32 1, i32* %p
 521   store i32 0, i32* %p
 522   ret void
 523 }