[MemCpyOpt] Check uses of found Clobber in writtenBetween.

[fhahn]

Summary

Currently writtenBetween can miss clobbers of Loc between End and Clobber
if Loc is not clobbered by End itself. End's defining accesses only have
to contain defs/phis that may clobber memory clobbered by End. But
writtenBetween needs to check for all write-clobbers of Loc.

To guarantee we see all write clobbers of Loc between the found Clobber
and End, I think we have to look at all uses of Clobber between Clobber
and End.

This fixes 2 mis-compiles illustrated in
llvm/test/Transforms/MemCpyOpt/memcpy-byval-forwarding-clobbers.ll

The implementation in this patch may consider write-clobbers on paths
that do not reach End as writes between Clobber and End. There's
potential to improve this as follow-up.

[nikic]

I'm not sure this is the right approach. The getDefininingAccess() here is essentially only supposed to skip over End itself during the clobber walk. As you correctly note, this is not correct if End is a MemoryUse. But shouldn't we be able to still do basically the same thing, but with the previous def in the block? Something like stepping one back on getReverseDefsIterator()?

[fhahn]

In D119929#3326038, @nikic wrote:

I'm not sure this is the right approach. The getDefininingAccess() here is essentially only supposed to skip over End itself during the clobber walk. As you correctly note, this is not correct if End is a MemoryUse. But shouldn't we be able to still do basically the same thing, but with the previous def in the block? Something like stepping one back on getReverseDefsIterator()?

I wasn't aware of the available reverse iterators for defs/accesses. I updated the code to recursively walk over the previous accesses. Because the iterator is block-only, we'd need to also go through the predecessors manually I think which makes it a bit trickier, unless there's already some existing functionaltiy I missed

I think we also need to do that for MemoryDefs, if End doesn't clobber Loc, because then the defining access could be optimized by skipping any accesses to Loc unless I am missing something.

[fhahn]

Update this patch to just scan if start & end are in the same block, otherwise conservatively return true. It might be easier to fix the mis-compile first and subsequently re-add cross-bb scanning.

[nikic]

I think we also need to do that for MemoryDefs, if End doesn't clobber Loc, because then the defining access could be optimized by skipping any accesses to Loc unless I am missing something.

Unlike MemoryUses, MemoryDefs have a separate defining access and optimized access. The defining access always points to the dominating MemoryDef/MemoryPhi, regardless of whether it clobbers any locations of the access. The optimized access does take clobbers into account.

If you are looking for a quick fix here, then the way to do it is to use the code as-is for MemoryDefs and only limit to the single-BB walk for MemoryUses. That should fix the issue with readonly byval calls, while keeping the much more important memcpy-memcpy dependence optimization working as before.

[fhahn]

In D119929#3333385, @nikic wrote:

I think we also need to do that for MemoryDefs, if End doesn't clobber Loc, because then the defining access could be optimized by skipping any accesses to Loc unless I am missing something.

Unlike MemoryUses, MemoryDefs have a separate defining access and optimized access. The defining access always points to the dominating MemoryDef/MemoryPhi, regardless of whether it clobbers any locations of the access. The optimized access does take clobbers into account.

Ah right, the walker always only uses the optimized accesses for MemoryUses!

If you are looking for a quick fix here, then the way to do it is to use the code as-is for MemoryDefs and only limit to the single-BB walk for MemoryUses. That should fix the issue with readonly byval calls, while keeping the much more important memcpy-memcpy dependence optimization working as before.

Done in the latest version, thanks!

[nikic]

LGTM

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

376

I'd move the getClobberingMemoryAccess() call into the !isa<MemoryUse> branch. Not much point doing it if we're going to discard it.

[fhahn]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

376

I reordered the checks in the committed version, thanks!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

if (isModOrRefSet(AA.getModRefInfo(cast<MemoryUseOrDef>(MA).getMemoryInst(),
                                        Loc)))
       return true;
   }
   return false;
 }
 
 // Check for mod of Loc between Start and End, excluding both boundaries.
 // Start and End can be in different blocks.
-static bool writtenBetween(MemorySSA *MSSA, MemoryLocation Loc,
-                           const MemoryUseOrDef *Start,
+static bool writtenBetween(MemorySSA *MSSA, AliasAnalysis &AA,
+                           MemoryLocation Loc, const MemoryUseOrDef *Start,
                            const MemoryUseOrDef *End) {
+  if (isa<MemoryUse>(End)) {
+    // For MemoryUses, getClobberingMemoryAccess may skip non-clobbering writes.
+    // Manually check read accesses between Start and End, if they are in the
+    // same block, for clobbers. Otherwise assume Loc is clobbered.
+    return Start->getBlock() != End->getBlock() ||
+           any_of(
+               make_range(std::next(Start->getIterator()), End->getIterator()),
+               [&AA, Loc](const MemoryAccess &Acc) {
+                 if (isa<MemoryUse>(&Acc))
+                   return false;
+                 Instruction *AccInst =
+                     cast<MemoryUseOrDef>(&Acc)->getMemoryInst();
+                 return isModSet(AA.getModRefInfo(AccInst, Loc));
+               });
+  }
+
   // TODO: Only walk until we hit Start.
   MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
       End->getDefiningAccess(), Loc);
   return !MSSA->dominates(Clobber, Start);
 }
 
 /// When scanning forward over instructions, we look for some other patterns to
 /// fold away. In particular, this looks for stores to neighboring locations of
 /// memory. If it sees enough consecutive ones, it attempts to merge them
 /// together into a memcpy/memset.
 Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
   //    *b = 42;
   //    memcpy(c <- a)
   // It would be invalid to transform the second memcpy into memcpy(c <- b).
   //
   // TODO: If the code between M and MDep is transparent to the destination "c",
   // then we could still perform the xform by moving M up to the first memcpy.
   // TODO: It would be sufficient to check the MDep source up to the memcpy
   // size of M, rather than MDep.
-  if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
+  if (writtenBetween(MSSA, *AA, MemoryLocation::getForSource(MDep),
                      MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(M)))
     return false;
 
   // If the dest of the second might alias the source of the first, then the
   // source and dest might overlap. In addition, if the source of the first
   // points to constant memory, they won't overlap by definition. Otherwise, we
   // still want to eliminate the intermediate value, but we have to generate a
   // memmove instead of memcpy.
if (MDep->getSource()->getType()->getPointerAddressSpace() !=
     return false;
 
   // Verify that the copied-from memory doesn't change in between the memcpy and
   // the byval call.
   //    memcpy(a <- b)
   //    *b = 42;
   //    foo(*a)
   // It would be invalid to transform the second memcpy into foo(*b).
-  if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
+  if (writtenBetween(MSSA, *AA, MemoryLocation::getForSource(MDep),
                      MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(&CB)))
     return false;
 
   Value *TmpCast = MDep->getSource();
   if (MDep->getSource()->getType() != ByValArg->getType()) {
     BitCastInst *TmpBitCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
                                               "tmpcast", &CB);
     // Set the tmpcast's DebugLoc to MDep's

llvm/test/Transforms/MemCpyOpt/memcpy-byval-forwarding-clobbers.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=memcpyopt -S %s | FileCheck %s
 
 declare void @init(i64* nocapture sret(i64) align 8)
 
 declare i1 @check(i64* readonly byval(i64) align 8) readonly argmemonly
 
 declare void @clobber(i8*) argmemonly
 
 declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture)
 declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
 
 ; %a.2's lifetime ends before the call to @check. Cannot replace
 ; %a.1 with %a.2 in the call to @check.
-; FIXME: Find lifetime.end, prevent optimization.
 define i1 @alloca_forwarding_lifetime_end_clobber() {
 ; CHECK-LABEL: @alloca_forwarding_lifetime_end_clobber(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i64, align 8
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i64, align 8
 ; CHECK-NEXT:    [[BC_A_1:%.*]] = bitcast i64* [[A_1]] to i8*
 ; CHECK-NEXT:    [[BC_A_2:%.*]] = bitcast i64* [[A_2]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 8, i8* [[BC_A_2]])
 ; CHECK-NEXT:    call void @init(i64* sret(i64) align 8 [[A_2]])
 ; CHECK-NEXT:    store i8 0, i8* [[BC_A_2]], align 1
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[BC_A_1]], i8* [[BC_A_2]], i64 8, i1 false)
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 8, i8* [[BC_A_2]])
-; CHECK-NEXT:    [[CALL:%.*]] = call i1 @check(i64* byval(i64) align 8 [[A_2]])
+; CHECK-NEXT:    [[CALL:%.*]] = call i1 @check(i64* byval(i64) align 8 [[A_1]])
 ; CHECK-NEXT:    ret i1 [[CALL]]
 ;
 entry:
   %a.1 = alloca i64, align 8
   %a.2 = alloca i64, align 8
   %bc.a.1 = bitcast i64* %a.1 to i8*
   %bc.a.2 = bitcast i64* %a.2 to i8*
   call void @llvm.lifetime.start.p0i8(i64 8, i8* %bc.a.2)
   call void @init(i64* sret(i64) align 8 %a.2)
   store i8 0, i8* %bc.a.2
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %bc.a.1, i8* %bc.a.2, i64 8, i1 false)
   call void @llvm.lifetime.end.p0i8(i64 8, i8* %bc.a.2)
   ;call void @clobber(i8* %bc.a.2)
   %call = call i1 @check(i64* byval(i64) align 8 %a.1)
   ret i1 %call
 }
 
 ; There is a call clobbering %a.2 before the call to @check. Cannot replace
 ; %a.1 with %a.2 in the call to @check.
-; FIXME: Find clobber, prevent optimization.
 define i1 @alloca_forwarding_call_clobber() {
 ; CHECK-LABEL: @alloca_forwarding_call_clobber(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i64, align 8
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i64, align 8
 ; CHECK-NEXT:    [[BC_A_1:%.*]] = bitcast i64* [[A_1]] to i8*
 ; CHECK-NEXT:    [[BC_A_2:%.*]] = bitcast i64* [[A_2]] to i8*
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 8, i8* [[BC_A_2]])
 ; CHECK-NEXT:    call void @init(i64* sret(i64) align 8 [[A_2]])
 ; CHECK-NEXT:    store i8 0, i8* [[BC_A_2]], align 1
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[BC_A_1]], i8* [[BC_A_2]], i64 8, i1 false)
 ; CHECK-NEXT:    call void @clobber(i8* [[BC_A_2]])
-; CHECK-NEXT:    [[CALL:%.*]] = call i1 @check(i64* byval(i64) align 8 [[A_2]])
+; CHECK-NEXT:    [[CALL:%.*]] = call i1 @check(i64* byval(i64) align 8 [[A_1]])
 ; CHECK-NEXT:    ret i1 [[CALL]]
 ;
 entry:
   %a.1 = alloca i64, align 8
   %a.2 = alloca i64, align 8
   %bc.a.1 = bitcast i64* %a.1 to i8*
   %bc.a.2 = bitcast i64* %a.2 to i8*
   call void @llvm.lifetime.start.p0i8(i64 8, i8* %bc.a.2)