[BasicAA] Don't assume tail calls with byval don't alias allocas

[rnk]

Summary

Calls marked 'tail' cannot read or write allocas from the current frame
because the current frame might be destroyed by the time they run.
However, a tail call may use an alloca with byval. Calling with byval
copies the contents of the alloca into argument registers or stack
slots, so there is no lifetime issue.

Fixes PR38466, a longstanding bug.

[hfinkel]

The DSE test is fine, and I think that you should keep it, but can you please add a direct AA test (like, e.g., test/Analysis/BasicAA/cs-cs.ll)?

Should we just always return ModRefInfo::Ref in this case? It can read the data (to copy it), but can't write, correct?

[rnk]

In D50679#1198237, @hfinkel wrote:

The DSE test is fine, and I think that you should keep it, but can you please add a direct AA test (like, e.g., test/Analysis/BasicAA/cs-cs.ll)?

Should we just always return ModRefInfo::Ref in this case? It can read the data (to copy it), but can't write, correct?

I thought about that, but I think the code below this check is usually more precise in these cases. It tests if the alloca isNonEscapingLocalObject and then looks at each argument to see if it is actually used by the call. For local objects that *are* escaping, we could return ModRefInfo::Ref. Basically, we already get this test case:

define void @dead(i32* byval %x) {
entry:
  %p = alloca i32
  %q = alloca i32
  %v = load i32, i32* %x
  store i32 %v, i32* %p
  store i32 1, i32* %q  ; DEAD
  tail call void @g(i32* byval %p)
  store i32 2, i32* %q
  call void @escape(i32* %q)
  ret void
}

[hfinkel]

In D50679#1198248, @rnk wrote:

In D50679#1198237, @hfinkel wrote:

The DSE test is fine, and I think that you should keep it, but can you please add a direct AA test (like, e.g., test/Analysis/BasicAA/cs-cs.ll)?

Should we just always return ModRefInfo::Ref in this case? It can read the data (to copy it), but can't write, correct?

I thought about that, but I think the code below this check is usually more precise in these cases. It tests if the alloca isNonEscapingLocalObject and then looks at each argument to see if it is actually used by the call. For local objects that *are* escaping, we could return ModRefInfo::Ref. Basically, we already get this test case:

define void @dead(i32* byval %x) {
entry:
  %p = alloca i32
  %q = alloca i32
  %v = load i32, i32* %x
  store i32 %v, i32* %p
  store i32 1, i32* %q  ; DEAD
  tail call void @g(i32* byval %p)
  store i32 2, i32* %q
  call void @escape(i32* %q)
  ret void
}

Ah. Good point.

Please add a direct AA test case. Otherwise, LGTM.

[rnk]

• add tests, make it ref only

[rnk]

• nevermind, be precise

[rnk]

In D50679#1198255, @hfinkel wrote:

Ah. Good point.

Please add a direct AA test case. Otherwise, LGTM.

The BasicAA test case revealed that CallSite::onlyReadsMemory doesn't check for byval, but it probably could. That's probably a big change that should be committed separately. I added the test with a FIXME that we should treat byval call arg uses as readonly.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 /// analysis on local objects.
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
                                         const MemoryLocation &Loc) {
   assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
          "AliasAnalysis query involving multiple functions!");
 
   const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
 
-  // If this is a tail call and Loc.Ptr points to a stack location, we know that
-  // the tail call cannot access or modify the local stack.
-  // We cannot exclude byval arguments here; these belong to the caller of
-  // the current function not to the current function, and a tail callee
-  // may reference them.
+  // Calls marked 'tail' cannot read or write allocas from the current frame
+  // because the current frame might be destroyed by the time they run. However,
+  // a tail call may use an alloca with byval. Calling with byval copies the
+  // contents of the alloca into argument registers or stack slots, so there is
+  // no lifetime issue.
   if (isa<AllocaInst>(Object))
     if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
-      if (CI->isTailCall())
+      if (CI->isTailCall() &&
+          !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
         return ModRefInfo::NoModRef;
 
   // If the pointer is to a locally allocated object that does not escape,
   // then the call can not mod/ref the pointer unless the call takes the pointer
   // as an argument, and itself doesn't capture it.
   if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
       isNonEscapingLocalObject(Object)) {
 

llvm/test/Analysis/BasicAA/tail-byval.ll

+; RUN: opt -basicaa -aa-eval -print-all-alias-modref-info -disable-output < %s 2>&1 | FileCheck %s
+
+declare void @takebyval(i32* byval %p)
+
+define i32 @tailbyval() {
+entry:
+  %p = alloca i32
+  store i32 42, i32* %p
+  tail call void @takebyval(i32* byval %p)
+  %rv = load i32, i32* %p
+  ret i32 %rv
+}
+; FIXME: This should be Just Ref.
+; CHECK-LABEL: Function: tailbyval: 1 pointers, 1 call sites
+; CHECK-NEXT:   Both ModRef:  Ptr: i32* %p       <->  tail call void @takebyval(i32* byval %p)

llvm/test/Transforms/DeadStoreElimination/tail-byval.ll

+; RUN: opt -dse -S < %s | FileCheck %s
+
+; Don't eliminate stores to allocas before tail calls to functions that use
+; byval. It's correct to mark calls like these as 'tail'. To implement this tail
+; call, the backend should copy the bytes from the alloca into the argument area
+; before clearing the stack.
+
+target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
+target triple = "i386-unknown-linux-gnu"
+
+declare void @g(i32* byval %p)
+
+define void @f(i32* byval %x) {
+entry:
+  %p = alloca i32
+  %v = load i32, i32* %x
+  store i32 %v, i32* %p
+  tail call void @g(i32* byval %p)
+  ret void
+}
+; CHECK-LABEL: define void @f(i32* byval %x)
+; CHECK:   store i32 %v, i32* %p
+; CHECK:   tail call void @g(i32* byval %p)

llvm/test/Transforms/InstCombine/load.ll

 ; RUN: opt -instcombine -S < %s | FileCheck %s
-; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes=instcombine -S < %s | FileCheck %s
 
 ; This test makes sure that these instructions are properly eliminated.
 
 target datalayout = "e-m:e-p:64:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 @X = constant i32 42    ; <i32*> [#uses=2]
 @X2 = constant i32 47   ; <i32*> [#uses=1]
 @Y = constant [2 x { i32, float }] [ { i32, float } { i32 12, float 1.000000e+00 }, { i32, float } { i32 37, float 0x3FF3B2FEC0000000 } ]    ; <[2 x { i32, float }]*> [#uses=2]