Enable tail call in MemCpyOptimization

[uenoku]

Summary

This fixes https://bugs.llvm.org/show_bug.cgi?id=41047.
IRBuilderBase::CreateMemCpy and similar functions are called in memcpy optimization(lib/Transforms/Scalar/MemCpyOptimizer.cpp). I think it is safe to enable tail call.

[uenoku]

Sorry, I have noticed that test fails so please wait.

[uenoku]

Change test/CodeGen/X86/memset-nonzero.ll and test passed

[efriedma]

A "tail" call is a call which does not refer to any memory allocated in the current stack frame. You aren't actually proving that invariant anywhere.

[uenoku]

I'm sorry, I misunderstood "tail". I will revert IRBuilder.cpp changes.

I have two ideas to enable tail call.

1. Add TailCallElimPass after MemCpyOptPass.
2. In the end of MemCpyOptPass, use lib/Transforms/Scalar/TailRecursionElimination.cpp/markTails.

I think 1 is simpler and better.
Is there any problem?

[efriedma]

Rerunning the analysis at some point after memcpyopt definitely makes sense. I'm not sure where exactly you'd put it, though... I guess after memcpyopt, nothing is really likely to create new tail calls, so just sticking it after memcpyopt might be fine. Maybe interesting to gather statistics for a few different placements, though.

Actually performing tail recursion elimination after loop optimizations is probably a bad idea, so we might want to split the pass.

[uenoku]

I guess after memcpyopt, nothing is really likely to create new tail calls, so just sticking it after memcpyopt might be fine.

I think so too.

As you said, I'd like to split TailCallElimPass into two passes, "TailCallMarkingPass" and "TailCallElimPass".

TailCallMarkingPass is only for marking function calls as "tail".
New TailCallElimPass does what old TailCallElimPass did except for marking the calls.

I will make a new patch for these.

[uenoku]

I submit a patch
https://reviews.llvm.org/D60031

[xbolva00]

Couldn’t passes like FunctionAttrs / Attributor infer “tail call mark” ?
Not sure how many times these passes go, indeed.

[xbolva00]

Maybe Attributor can infer tail call marks too?

@jdoerfert

[jdoerfert]

In D59534#1448954, @xbolva00 wrote:

Maybe Attributor can infer tail call marks too?

@jdoerfert

Sure. I already have (down-stream) code for other instruction attributes, adding more is what I wanted to do anyway.
I'll look into and let you know!

For those who missed it: "Attributor" is a proposed replacement of function attribute detection, see D59918 and its child patches.

lib/IR/IRBuilder.cpp

CreateMemSet(Value *Ptr, Value *Val, Value *Size, unsigned Align,
              MDNode *NoAliasTag) {
   Ptr = getCastedInt8PtrValue(Ptr);
   Value *Ops[] = {Ptr, Val, Size, getInt1(isVolatile)};
   Type *Tys[] = { Ptr->getType(), Size->getType() };
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memset, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   if (Align > 0)
     cast<MemSetInst>(CI)->setDestAlignment(Align);
 
   // Set the TBAA info if present.
   if (TBAATag)
     CI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
 
CallInst *IRBuilderBase::CreateElementUnorderedAtomicMemSet(
   Ptr = getCastedInt8PtrValue(Ptr);
   Value *Ops[] = {Ptr, Val, Size, getInt32(ElementSize)};
   Type *Tys[] = {Ptr->getType(), Size->getType()};
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(
       M, Intrinsic::memset_element_unordered_atomic, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   cast<AtomicMemSetInst>(CI)->setDestAlignment(Align);
 
   // Set the TBAA info if present.
   if (TBAATag)
     CI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
 
   if (ScopeTag)
CreateMemCpy(Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign,
   Src = getCastedInt8PtrValue(Src);
 
   Value *Ops[] = {Dst, Src, Size, getInt1(isVolatile)};
   Type *Tys[] = { Dst->getType(), Src->getType(), Size->getType() };
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memcpy, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   auto* MCI = cast<MemCpyInst>(CI);
   if (DstAlign > 0)
     MCI->setDestAlignment(DstAlign);
   if (SrcAlign > 0)
     MCI->setSourceAlignment(SrcAlign);
 
   // Set the TBAA info if present.
CallInst *IRBuilderBase::CreateElementUnorderedAtomicMemCpy(
 
   Value *Ops[] = {Dst, Src, Size, getInt32(ElementSize)};
   Type *Tys[] = {Dst->getType(), Src->getType(), Size->getType()};
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(
       M, Intrinsic::memcpy_element_unordered_atomic, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   // Set the alignment of the pointer args.
   auto *AMCI = cast<AtomicMemCpyInst>(CI);
   AMCI->setDestAlignment(DstAlign);
   AMCI->setSourceAlignment(SrcAlign);
 
   // Set the TBAA info if present.
   if (TBAATag)
CreateMemMove(Value *Dst, unsigned DstAlign, Value *Src, unsigned SrcAlign,
   Src = getCastedInt8PtrValue(Src);
 
   Value *Ops[] = {Dst, Src, Size, getInt1(isVolatile)};
   Type *Tys[] = { Dst->getType(), Src->getType(), Size->getType() };
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(M, Intrinsic::memmove, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   auto *MMI = cast<MemMoveInst>(CI);
   if (DstAlign > 0)
     MMI->setDestAlignment(DstAlign);
   if (SrcAlign > 0)
     MMI->setSourceAlignment(SrcAlign);
 
   // Set the TBAA info if present.
CallInst *IRBuilderBase::CreateElementUnorderedAtomicMemMove(
 
   Value *Ops[] = {Dst, Src, Size, getInt32(ElementSize)};
   Type *Tys[] = {Dst->getType(), Src->getType(), Size->getType()};
   Module *M = BB->getParent()->getParent();
   Function *TheFn = Intrinsic::getDeclaration(
       M, Intrinsic::memmove_element_unordered_atomic, Tys);
 
   CallInst *CI = createCallHelper(TheFn, Ops, this);
+  CI->setTailCall(true);
 
   // Set the alignment of the pointer args.
   CI->addParamAttr(0, Attribute::getWithAlignment(CI->getContext(), DstAlign));
   CI->addParamAttr(1, Attribute::getWithAlignment(CI->getContext(), SrcAlign));
 
   // Set the TBAA info if present.
   if (TBAATag)
     CI->setMetadata(LLVMContext::MD_tbaa, TBAATag);

test/CodeGen/X86/memset-nonzero.ll

 ; AVX-NEXT:    retq
   %call = tail call i8* @__memset_chk(i8* %x, i32 42, i64 128, i64 -1)
   ret void
 }
 
 define void @memset_256_nonzero_bytes(i8* %x) {
 ; SSE-LABEL: memset_256_nonzero_bytes:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    pushq %rax
-; SSE-NEXT:    .cfi_def_cfa_offset 16
 ; SSE-NEXT:    movl $256, %edx # imm = 0x100
 ; SSE-NEXT:    movl $42, %esi
-; SSE-NEXT:    callq memset
-; SSE-NEXT:    popq %rax
-; SSE-NEXT:    .cfi_def_cfa_offset 8
-; SSE-NEXT:    retq
+; SSE-NEXT:    jmp memset
 ;
 ; SSE2FAST-LABEL: memset_256_nonzero_bytes:
 ; SSE2FAST:       # %bb.0:
 ; SSE2FAST-NEXT:    movaps {{.*#+}} xmm0 = [42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42]
 ; SSE2FAST-NEXT:    movups %xmm0, 240(%rdi)
 ; SSE2FAST-NEXT:    movups %xmm0, 224(%rdi)
 ; SSE2FAST-NEXT:    movups %xmm0, 208(%rdi)
 ; SSE2FAST-NEXT:    movups %xmm0, 192(%rdi)

test/Transforms/MemCpyOpt/enable-tail-call.ll

+; RUN: opt -memcpyopt -S < %s | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+%S = type { i8*, i8, i32 }
+
+define void @copy(%S* %src, %S* %dst) {
+; CHECK-LABEL: copy
+; CHECK-NOT: load
+; CHECK: tail call void @llvm.memmove.p0i8.p0i8.i64
+; CHECK-NEXT: ret void
+  %1 = load %S, %S* %src
+  store %S %1, %S* %dst
+  ret void
+}
+
+define void @noaliassrc(%S* noalias %src, %S* %dst) {
+; CHECK-LABEL: noaliassrc
+; CHECK-NOT: load
+; CHECK: tail call void @llvm.memcpy.p0i8.p0i8.i64
+; CHECK-NEXT: ret void
+  %1 = load %S, %S* %src
+  store %S %1, %S* %dst
+  ret void
+}
+
+
+define void @destroysrc(%S* %src, %S* %dst) {
+; CHECK-LABEL: destroysrc
+; CHECK: load %S, %S* %src
+; CHECK: tail call void @llvm.memset.p0i8.i64
+; CHECK-NEXT: store %S %1, %S* %dst
+; CHECK-NEXT: ret void
+  %1 = load %S, %S* %src
+  store %S zeroinitializer, %S* %src
+  store %S %1, %S* %dst
+  ret void
+}
+