[MemCpyOptimizer] Optimize passing byref function arguments down the stack

[atrosinenko]

Summary

When a byref function argument is passed through like this:

void leaf(struct X);
void middle(struct X a) {
  leaf(a);
}

... an unnecessary temporary copy may be introduced inside middle().

This patch makes that copy being eliminated by MemCpyOptimizer unless size of
the byref argument is 8 bytes or less (in that case memcpy() is eliminated by
InstCombine first preventing later optimization).

[rjmccall]

If this optimization is valid, it's valid regardless of byref.

[jdoerfert]

This needs an LLVM IR test.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1332

I thought we have a shortcut to check for both attributes. If not, we might want one.

[atrosinenko]

Restrict transformation to passing through byref arguments, not arbitrary pointers.

[jdoerfert]

This looks reasonable on first glance. @arsenm ?

[arsenm]

llvm/test/Transforms/MemCpyOpt/byref-memcpy.ll

44 ↗

(On Diff #286037)

I think this is missing an alignment check. Can you add a test where the callee requires a higher parameter alignment than the caller?

[rjmccall]

Sorry, I tried to say thiis more succinctly before, but what exactly is the semantic property of byref that allows this optimization?

[atrosinenko]

Add a test for insufficiently aligned source.

[atrosinenko]

@rjmccall

Maybe I overestimated similarity of byval and recently introduced byref... Looks like some aliasing restrictions are not mentioned in LLVM Language Reference. For example, the only way for Clang to emit the byref attribute to LLVM IR I know about is via ABIArgInfo with Kind == IndirectAliased introduced in D79744: clang: Use byref for aggregate kernel arguments - and it has a note that "The object is known to not be through any other references for the duration of the call, and the callee must not itself modify the object". This seems to be necessary for correctness of this transformation. If LLVM Language Reference does not mention such restrictions intentionally, then it may be clang that should be responsible for such optimizations.

llvm/test/Transforms/MemCpyOpt/byref-memcpy.ll

55 ↗

(On Diff #286097)

Interestingly, if I change the alignment of the second argument from 2 back to 4, then memcpy() is successfully dropped (as if everything has big-enough alignment) while it seemingly shouldn't be. Is it just due to the code being ill-formed?

[arsenm]

In D86020#2222103, @atrosinenko wrote:

@rjmccall

Maybe I overestimated similarity of byval and recently introduced byref... Looks like some aliasing restrictions are not mentioned in LLVM Language Reference. For example, the only way for Clang to emit the byref attribute to LLVM IR I know about is via ABIArgInfo with Kind == IndirectAliased introduced in D79744: clang: Use byref for aggregate kernel arguments - and it has a note that "The object is known to not be through any other references for the duration of the call, and the callee must not itself modify the object". This seems to be necessary for correctness of this transformation. If LLVM Language Reference does not mention such restrictions intentionally, then it may be clang that should be responsible for such optimizations.

I think this lost the word written or stored

llvm/test/Transforms/MemCpyOpt/byref-memcpy.ll

8 ↗

(On Diff #286097)

Typo attrbiute

55 ↗

(On Diff #286097)

I'm not sure I follow, if you change it to 4 it is big enough?

clang/test/CodeGen/msp430-struct-or-union-args.c

 // REQUIRES: msp430-registered-target
-// RUN: %clang -target msp430 -fno-inline-functions -S -o- %s | FileCheck --check-prefixes=ASM %s
+// Optimized to check that some of memcpy intrinsic invocations are optimized out.
+// RUN: %clang -target msp430 -fno-inline-functions -S -Os -o- %s | FileCheck --check-prefixes=ASM %s
+// Do not use any optimization to not clutter the output with deduced LLVM IR attributes.
 // RUN: %clang -target msp430 -fno-inline-functions -S -emit-llvm -o- %s | FileCheck --check-prefixes=IR %s
 
 #include <limits.h>
 #include <stdint.h>
 
 // According to Section 3.5 of MSP430 EABI, structures and unions are passed
 // by reference, even if an equally-sized integer argument could be passed
 // in registers.

 // IR: ret void
 
 // ASM:      caller_u:
 // ASM:      mov #u, r12
 // ASM-NEXT: call #middle_u
 // ASM-NEXT: ret
   middle_u(u);
 }
+
+// No need to create a temporary copy of the struct/union-typed argument
+// if it is just passed to other function as-is.
+// TODO For now, it works when size of structure is more than 8 bytes,
+// otherwise the memcpy intrinsic will be replaced by InstCombiner.
+
+struct LL {
+  long long a[2];
+};
+
+extern struct LL ll;
+
+extern void leaf(struct LL x);
+
+void middle(struct LL x) {
+// ASM:      middle:
+// No stack-allocated objects:
+// ASM-NOT:  r1
+// ASM: call #leaf
+// ASM-NEXT: ret
+  leaf(x);
+}
+
+void caller(void) {
+// ASM:      caller:
+// ASM:      mov #ll, r12
+// ASM-NEXT: call #middle
+// ASM-NEXT: ret
+  middle(ll);
+}

llvm/include/llvm/Transforms/Scalar/MemCpyOptimizer.h

private:
   bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
   bool processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI);
   bool processMemMove(MemMoveInst *M);
   bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc,
                             uint64_t cpyLen, Align cpyAlign, CallInst *C);
   bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep);
   bool processMemSetMemCpyDependence(MemCpyInst *MemCpy, MemSetInst *MemSet);
   bool performMemCpyToMemSetOptzn(MemCpyInst *MemCpy, MemSetInst *MemSet);
-  bool processByValArgument(CallBase &CB, unsigned ArgNo);
+  bool processByValOrByRefArgument(CallBase &CB, unsigned ArgNo);
   Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr,
                                     Value *ByteVal);
 
   bool iterateOnFunction(Function &F);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
   // MemDep may have over conservative information about this instruction, just
   // conservatively flush it from the cache.
   MD->removeInstruction(M);
 
   ++NumMoveToCpy;
   return true;
 }
 
-/// This is called on every byval argument in call sites.
-bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {
+/// This is called on every byval/byref argument in call sites.
+bool MemCpyOptPass::processByValOrByRefArgument(CallBase &CB, unsigned ArgNo) {
   const DataLayout &DL = CB.getCaller()->getParent()->getDataLayout();
-  // Find out what feeds this byval argument.
+  // Find out what feeds this byval/byref argument.
   Value *ByValArg = CB.getArgOperand(ArgNo);
   Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
   uint64_t ByValSize = DL.getTypeAllocSize(ByValTy);
   MemDepResult DepInfo = MD->getPointerDependencyFrom(
       MemoryLocation(ByValArg, LocationSize::precise(ByValSize)), true,
       CB.getIterator(), CB.getParent());
   if (!DepInfo.isClobber())
     return false;
bool MemCpyOptPass::processByValOrByRefArgument(CallBase &CB, unsigned ArgNo) {
   if (MDep->getSource()->getType() != ByValArg->getType()) {
     BitCastInst *TmpBitCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
                                               "tmpcast", &CB);
     // Set the tmpcast's DebugLoc to MDep's
     TmpBitCast->setDebugLoc(MDep->getDebugLoc());
     TmpCast = TmpBitCast;
   }
 
-  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
+  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval or byref:\n"
                     << "  " << *MDep << "\n"
                     << "  " << CB << "\n");
 
   // Otherwise we're good!  Update the byval argument.
   CB.setArgOperand(ArgNo, TmpCast);
   ++NumMemCpyInstr;
   return true;
 }
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
       else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
         RepeatInstruction = processMemSet(M, BI);
       else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
         RepeatInstruction = processMemCpy(M, BI);
       else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
         RepeatInstruction = processMemMove(M);
       else if (auto *CB = dyn_cast<CallBase>(I)) {
         for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
-          if (CB->isByValArgument(i))
-            MadeChange |= processByValArgument(*CB, i);
+          if (CB->isByValArgument(i) || CB->paramHasAttr(i, Attribute::ByRef))
+            MadeChange |= processByValOrByRefArgument(*CB, i);
       }
 
       // Reprocess the instruction if desired.
       if (RepeatInstruction) {
         if (BI != BB.begin())
           --BI;
         MadeChange = true;
       }