[DSE,MSSA] Treat passed by value args as invisible to caller.

[fhahn]

Summary

This updates the MemorySSA backed implementation to treat arguments
passed by value similar to allocas: in they are assumed to be invisible
in the caller. This is similar to how they are treated in legacy DSE.

[efriedma]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1584

For inalloca and preallocated, the argument has the same address in the caller and the callee. So if I'm understanding correctly, InvisibleToCallerBeforeRet should only apply specifically to byval.

[efriedma]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1591

Is there an incorrectly resolved merge conflict here?

[fhahn]

Remove unintended duplication, limit InivisibleBeforeRet to byval.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1584

Right, I thought the caller cannot expect to observe any writes to any PassPointeeByVal argument, but it is not entirely clear from the langref. I've updated the code as suggested. Legacy DSE seems to treat them at least as if writes are not observable after the function returns.

1591

Yes that was unintentional. sorry about that!

[efriedma]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1584

For all of byval, inalloca, and preallocated, the allocation is implicitly freed when the function's stack frame is freed (when the function returns or unwinds).

The aspect where inalloca and preallocated differ is related to escaping. Essentially, for inalloca/preallocated arguments, the address has already escaped before the function starts executing.

Not sure what "even if the function exits through an exception" means in this context. The comment should be something more like "for byval, the caller doesn't know the address of the allocation".

[fhahn]

Update comment as suggested, thanks Eli!

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1584

Makes sense, I've updated the comment, thanks!

Currently the InvisbleToCallerSets are framed as the object being invisible to the caller, but I think the key point is whether modifications in the callee are visible to the caller. I think then it would be possible to include inalloca & preallocate as invisible before returning (i.e. when unwinding). But that's potential for another patch.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

for (BasicBlock *BB : post_order(&F)) {
             State.InvisibleToCallerBeforeRet.insert(&I);
             if (!PointerMayBeCaptured(&I, true, false))
               State.InvisibleToCallerAfterRet.insert(&I);
           }
         }
       }
     }
 
+    // Treat byval or inalloca arguments the same, stores to them are dead at
+    // the end of the function.
+    for (Argument &AI : F.args())
+      if (AI.hasPassPointeeByValueAttr()) {
+        State.InvisibleToCallerBeforeRet.insert(&AI);
+        State.InvisibleToCallerAfterRet.insert(&AI);
+      }
+
     // Treat byval or inalloca arguments the same as Allocas, stores to them are
     // dead at the end of the function.
     for (Argument &AI : F.args())
       if (AI.hasPassPointeeByValueAttr())
         State.InvisibleToCallerBeforeRet.insert(&AI);
     return State;
   }
 
   Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
     if (!I->mayWriteToMemory())
       return None;
 
     if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; XFAIL: *
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -enable-dse-memoryssa -S | FileCheck %s
 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"
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) nounwind
 declare void @llvm.memset.element.unordered.atomic.p0i8.i64(i8* nocapture, i8, i64, i32) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32) nounwind
 declare void @llvm.init.trampoline(i8*, i8*, i8*)
 
-; Test for byval handling.
-%struct.x = type { i32, i32, i32, i32 }
-define void @test9(%struct.x* byval  %a) nounwind  {
-; CHECK-LABEL: @test9(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
-; Test for inalloca handling.
-define void @test9_2(%struct.x* inalloca  %a) nounwind  {
-; CHECK-LABEL: @test9_2(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
-; Test for preallocated handling.
-define void @test9_3(%struct.x* preallocated(%struct.x)  %a) nounwind  {
-; CHECK-LABEL: @test9_3(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
 ; DSE should delete the dead trampoline.
 declare void @test11f()
 define void @test11() {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:    ret void
 ;
   %storage = alloca [10 x i8], align 16    ; <[10 x i8]*> [#uses=1]
   %cast = getelementptr [10 x i8], [10 x i8]* %storage, i32 0, i32 0    ; <i8*> [#uses=1]
   call void @llvm.init.trampoline( i8* %cast, i8* bitcast (void ()* @test11f to i8*), i8* null )    ; <i8*> [#uses=1]
   ret void
 }
 
 
 declare noalias i8* @malloc(i32)
 declare noalias i8* @calloc(i32, i32)
 
-define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
-; CHECK-LABEL: @test22(
-; CHECK-NEXT:    ret void
-;
-  %k.addr = alloca i32
-  %m.addr = alloca i32
-  %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
-  store i32 0, i32* %k.addr.m.addr, align 4
-  ret void
-}
-
 declare void @unknown_func()
 
 ; Remove redundant store if loaded value is in another block inside a loop.
 define i32 @test31(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test31(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

;
   store i32 %DEAD, i32* %P
   store i32 0, i32* %P
   ret void
 }
 
 ; PR8677
 @g = global i32 1
 
+
 define i32 @test3(i32* %g_addr) nounwind {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[G_VALUE:%.*]] = load i32, i32* [[G_ADDR:%.*]], align 4
 ; CHECK-NEXT:    store i32 -1, i32* @g, align 4
 ; CHECK-NEXT:    store i32 [[G_VALUE]], i32* [[G_ADDR]], align 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* @g, align 4
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
;
   store i32 1234567, i32* %V
   %V2 = bitcast i32* %V to i8*
   store i8 0, i8* %V2
   %X = load i32, i32* %V
   ret i32 %X
 
 }
 
+; Test for byval handling.
+%struct.x = type { i32, i32, i32, i32 }
+define void @test9(%struct.x* byval  %a) nounwind  {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
+; Test for inalloca handling.
+define void @test9_2(%struct.x* inalloca  %a) nounwind  {
+; CHECK-LABEL: @test9_2(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
+; Test for preallocated handling.
+define void @test9_3(%struct.x* preallocated(%struct.x)  %a) nounwind  {
+; CHECK-LABEL: @test9_3(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
 ; va_arg has fuzzy dependence, the store shouldn't be zapped.
 define double @test10(i8* %X) {
 ; CHECK-LABEL: @test10(
 ; CHECK-NEXT:    [[X_ADDR:%.*]] = alloca i8*, align 8
 ; CHECK-NEXT:    store i8* [[X:%.*]], i8** [[X_ADDR]], align 8
 ; CHECK-NEXT:    [[TMP_0:%.*]] = va_arg i8** [[X_ADDR]], double
 ; CHECK-NEXT:    ret double [[TMP_0]]
 ;

 ; CHECK-LABEL: @test21(
 ; CHECK-NEXT:    ret void
 ;
   %m = call i8* @calloc(i32 9, i32 7)
   store i8 0, i8* %m
   ret void
 }
 
+define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
+; CHECK-LABEL: @test22(
+; CHECK-NEXT:    ret void
+;
+  %k.addr = alloca i32
+  %m.addr = alloca i32
+  %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
+  store i32 0, i32* %k.addr.m.addr, align 4
+  ret void
+}
+
 ; The store here is not dead because the byval call reads it.
 declare void @test19f({i32}* byval align 4 %P)
 
 define void @test19({i32} * nocapture byval align 4 %arg5) nounwind ssp {
 ; CHECK-LABEL: @test19(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds { i32 }, { i32 }* [[ARG5:%.*]], i32 0, i32 0
 ; CHECK-NEXT:    store i32 912, i32* [[TMP7]], align 4