[MemCpyOpt] Fix thread-safety of call slot opimization

[nikic]

Summary

This is a followup to D88799 to address the thread-safety issue raised there. If the destination is captured, we need to check that the copy instruction is executed, to exclude concurrent access from another thread.

It turns out that this doesn't really change much: If the destination is captured, then the call itself needs to be argmemonly to not potentially modify the destination, and argmemonly currently (incorrectly...) implies willreturn. Thus the only requirement that actually gets added in practice is nounwind (even for alloca dest).

[efriedma]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

callCapturesBefore only checks the call C itself. Don't we also care if the pointer is captured somewhere before the call?

[jdoerfert]

It turns out that this doesn't really change much: If the destination is captured, then the call itself needs to be argmemonly to not potentially modify the destination, and argmemonly currently (incorrectly...) implies willreturn. Thus the only requirement that actually gets added in practice is nounwind (even for alloca dest).

I did not get this :(

---

If the caller is nosync there is no need for all this thread safety checking.

---

The isGuaranteedToTransferExecutionToSuccessor loop is not necessary for nounwind + willreturn functions.

---

I feel we probably need the same logic in different places and this might even deserve a helper.

[efriedma]

If the caller is nosync there is no need for all this thread safety checking.

I'm not sure nosync helps here? The issue this patch is trying to solve is the case where the memcpy is dynamically dead due to an infinite loop; there isn't any synchronization involved.

[nikic]

In D88921#2315685, @efriedma wrote:

If the caller is nosync there is no need for all this thread safety checking.

I'm not sure nosync helps here? The issue this patch is trying to solve is the case where the memcpy is dynamically dead due to an infinite loop; there isn't any synchronization involved.

That's right. If we synchronized between the copy and the memcpy, then we'd see that as the memcpy dependency. This only applies to the unsynchronized, dynamically dead case.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

I find this method to be somewhat confusingly named, but what it actually does is to a) check for captures up to and including the call (-> ModRef) and b) a potential access via a non-capturing argument in the call itself.

See https://github.com/llvm/llvm-project/blob/334ec6f807fa65e09571fa42a0c3be0eb39e7c0f/llvm/lib/Analysis/AliasAnalysis.cpp#L652.

[efriedma]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

That makes sense.

That said, I don't think the handling of noalias arguments here is correct. In general, noalias only affects memory accesses that dynamically execute. So here, if the write to destLoc is dynamically dead, you can't do anything useful with the noalias attribute; you have to treat it like any other captured pointer.

Not sure if that's a bug in callCapturesBefore(), or the way it's used here.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

That said, I don't think the handling of noalias arguments here is correct. In general, noalias only affects memory accesses that dynamically execute. So here, if the write to destLoc is dynamically dead, you can't do anything useful with the noalias attribute; you have to treat it like any other captured pointer.

But doesn't (a non-captured) noalias imply that a write also cannot happen from a different thread, as that means that a write to the noalias object occurred without going through the noalias pointer?

[efriedma]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

The description of noalias in LangRef starts with "This indicates that memory locations accessed via pointer values based on the argument [...]". If that set of memory locations is empty, the rest of the description doesn't guarantee anything.

[nikic]

Handle noalias arguments the same as other captures. Now this change does have a practical effect, and I had to annotate some existing tests with willreturn.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

810

I see, that's unfortunate :( I've updated the implementation to treat noalias arguments the same as other captures now.

[efriedma]

Any opinion on whether we should change callCapturesBefore()? Given it only has three existing callers, probably worth looking into.

[nikic]

In D88921#2317223, @efriedma wrote:

Any opinion on whether we should change callCapturesBefore()? Given it only has three existing callers, probably worth looking into.

There's actually only one other caller in MemDepAnalysis (rest is comments or trivial forwarding), where it is used to determine whether a call can mod/ref a location: https://github.com/llvm/llvm-project/blob/9c09e2055ee4d4e3b26e393ab460635825a79538/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp#L622 The current noalias handling seems reasonable to me, mostly in the sense that it matches how noalias would be treated for non-calls. (If I understand the full implication here, whether the result of an AA/MD query is "correct" actually depends on whether you are querying a location that corresponds to a real IR access, and then it is only valid at that access.)

[efriedma]

Oh, I see, the unmodified callCapturesBefore result is correct if you're trying to determine whether the the call might modify a value that can be consumed by a load, but not if you're trying to determine if a store clobbers memory that might be used in another thread.

I think I'd prefer to sink the conditional into callCapturesBefore itself, so anyone who modifies it in the future has the necessary context. I think the isa<Argument> check is too tightly coupled to the implementation of callCapturesBefore, as opposed to its abstract semantics.

[nikic]

In D88921#2322695, @efriedma wrote:

Oh, I see, the unmodified callCapturesBefore result is correct if you're trying to determine whether the the call might modify a value that can be consumed by a load, but not if you're trying to determine if a store clobbers memory that might be used in another thread.

I think I'd prefer to sink the conditional into callCapturesBefore itself, so anyone who modifies it in the future has the necessary context. I think the isa<Argument> check is too tightly coupled to the implementation of callCapturesBefore, as opposed to its abstract semantics.

To clarify, the suggestion here is to add a boolean flag to callCapturesBefore() that determines whether arguments should always be considered capturing?

One thing to note is that this would not allow us to treat the call modref check (which does not care about noalias arguments) and the willreturn check (which does) separately. That is, the following code would no longer fold:

define void @test(i8* noalias dereferenceable(16) %dest.i8) {
  %src = alloca [16 x i8]
  %src.i8 = bitcast [16 x i8]* %src to i8*
  call void @accept_ptr(i8* %src.i8) nounwind willreturn
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest.i8, i8* %src.i8, i64 16, i1 false)
  call void @accept_ptr(i8* %dest.i8) ; capture
  ret void
}

Of course, it's not a big loss.

[efriedma]

To clarify, the suggestion here is to add a boolean flag to callCapturesBefore() that determines whether arguments should always be considered capturing?

Something like that.

One thing to note is that this would not allow us to treat the call modref check (which does not care about noalias arguments) and the willreturn check (which does) separately. That is, the following code would no longer fold:

I guess if we cared, we could make callCapturesBefore() return two results, instead of adding a boolean argument.

[jdoerfert]

Commit message:

If the destination is captured, we need to check that the copy instruction is executed, to exclude concurrent access from another thread.

In D88921#2315685, @efriedma wrote:

If the caller is nosync there is no need for all this thread safety checking.

I'm not sure nosync helps here? The issue this patch is trying to solve is the case where the memcpy is dynamically dead due to an infinite loop; there isn't any synchronization involved.

If it is nosync there is no concurrent access without it being a race and therefore UB.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
   if (!isDereferenceableAndAlignedPointer(cpyDest, Align(1), APInt(64, cpyLen),
                                           DL, C, DT))
     return false;
 
   // Make sure that nothing can observe cpyDest being written early. There are
   // a number of cases to consider:
   //  1. cpyDest cannot be accessed between C and cpyStore as a precondition of
   //     the transform.
-  //  2. C itself may not access cpyDest (prior to the transform). This is
-  //     checked further below.
-  //  3. If cpyDest is accessible to the caller of this function (potentially
-  //     captured and not based on an alloca), we need to ensure that we cannot
-  //     unwind between C and cpyStore. This is checked here.
+  //  2. C itself must not access cpyDest (prior to the transform).
+  //  3. If cpyDest is potentially accessible to the caller of this function
+  //     (captured or an argument), we need to ensure that we cannot unwind
+  //     between C and cpyStore.
   //  4. If cpyDest is potentially captured, there may be accesses to it from
   //     another thread. In this case, we need to check that cpyStore is
   //     guaranteed to be executed if C is. As it is a non-atomic access, it
   //     renders accesses from other threads undefined.
-  //     TODO: This is currently not checked.
-  // TODO: Check underlying object, so we can look through GEPs.
-  if (!isa<AllocaInst>(cpyDest)) {
-    assert(C->getParent() == cpyStore->getParent() &&
-           "call and copy must be in the same block");
+
+  MemoryLocation destLoc(cpyDest, srcSize);
+  bool callCaptures = isModOrRefSet(AA->callCapturesBefore(C, destLoc, DT));
+
+  // Ensure dest is not accessed by the call.
+  if (callCaptures && isModOrRefSet(AA->getModRefInfo(C, destLoc)))
+    return false;
+
+  // Explicitly check for arguments, as callCapturesBefore() considers
+  // noalias arguments to be non-capturing.
+  if (callCaptures || isa<Argument>(getUnderlyingObject(cpyDest))) {
+    // Ensure cpyStore is executed, rendering accesses from other threads UB.
     for (const Instruction &I : make_range(C->getIterator(),
                                            cpyStore->getIterator())) {
-      if (I.mayThrow())
+      if (!isGuaranteedToTransferExecutionToSuccessor(&I))
         return false;
     }
   }
 
   // Check that dest points to memory that is at least as aligned as src.
   Align srcAlign = srcAlloca->getAlign();
   bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
   // If dest is not aligned enough and we can't increase its alignment then
bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
 
   // Since we're changing the parameter to the callsite, we need to make sure
   // that what would be the new parameter dominates the callsite.
   // TODO: Support moving instructions like GEPs upwards.
   if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest))
     if (!DT->dominates(cpyDestInst, C))
       return false;
 
-  // In addition to knowing that the call does not access src in some
-  // unexpected manner, for example via a global, which we deduce from
-  // the use analysis, we also need to know that it does not sneakily
-  // access dest.  We rely on AA to figure this out for us.
-  ModRefInfo MR = AA->getModRefInfo(C, cpyDest, LocationSize::precise(srcSize));
-  // If necessary, perform additional analysis.
-  if (isModOrRefSet(MR))
-    MR = AA->callCapturesBefore(C, cpyDest, LocationSize::precise(srcSize), DT);
-  if (isModOrRefSet(MR))
-    return false;
-
   // We can't create address space casts here because we don't know if they're
   // safe for the target.
   if (cpySrc->getType()->getPointerAddressSpace() !=
       cpyDest->getType()->getPointerAddressSpace())
     return false;
   for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
     if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
         cpySrc->getType()->getPointerAddressSpace() !=

llvm/test/Transforms/MemCpyOpt/callslot.ll

 }
 
 define void @dest_is_gep_may_throw_call() {
 ; CHECK-LABEL: @dest_is_gep_may_throw_call(
 ; CHECK-NEXT:    [[DEST:%.*]] = alloca [16 x i8], align 1
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [8 x i8], align 1
 ; CHECK-NEXT:    [[SRC_I8:%.*]] = bitcast [8 x i8]* [[SRC]] to i8*
 ; CHECK-NEXT:    [[DEST_I8:%.*]] = getelementptr [16 x i8], [16 x i8]* [[DEST]], i64 0, i64 8
-; CHECK-NEXT:    call void @accept_ptr(i8* [[SRC_I8]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DEST_I8]], i8* [[SRC_I8]], i64 8, i1 false)
+; CHECK-NEXT:    [[DEST_I81:%.*]] = bitcast i8* [[DEST_I8]] to [8 x i8]*
+; CHECK-NEXT:    [[DEST_I812:%.*]] = bitcast [8 x i8]* [[DEST_I81]] to i8*
+; CHECK-NEXT:    call void @accept_ptr(i8* [[DEST_I812]])
 ; CHECK-NEXT:    ret void
 ;
   %dest = alloca [16 x i8]
   %src = alloca [8 x i8]
   %src.i8 = bitcast [8 x i8]* %src to i8*
   %dest.i8 = getelementptr [16 x i8], [16 x i8]* %dest, i64 0, i64 8
   call void @accept_ptr(i8* %src.i8)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest.i8, i8* %src.i8, i64 8, i1 false)

 
 define void @capture_before_call_argmemonly() {
 ; CHECK-LABEL: @capture_before_call_argmemonly(
 ; CHECK-NEXT:    [[DEST:%.*]] = alloca [16 x i8], align 1
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [16 x i8], align 1
 ; CHECK-NEXT:    [[DEST_I8:%.*]] = bitcast [16 x i8]* [[DEST]] to i8*
 ; CHECK-NEXT:    [[SRC_I8:%.*]] = bitcast [16 x i8]* [[SRC]] to i8*
 ; CHECK-NEXT:    call void @accept_ptr(i8* [[DEST_I8]])
-; CHECK-NEXT:    [[DEST1:%.*]] = bitcast [16 x i8]* [[DEST]] to i8*
-; CHECK-NEXT:    call void @accept_ptr(i8* [[DEST1]]) [[ATTR4:#.*]]
+; CHECK-NEXT:    call void @accept_ptr(i8* [[SRC_I8]]) [[ATTR4:#.*]]
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DEST_I8]], i8* [[SRC_I8]], i64 16, i1 false)
 ; CHECK-NEXT:    ret void
 ;
   %dest = alloca [16 x i8]
   %src = alloca [16 x i8]
   %dest.i8 = bitcast [16 x i8]* %dest to i8*
   %src.i8 = bitcast [16 x i8]* %src to i8*
   call void @accept_ptr(i8* %dest.i8) ; capture
   call void @accept_ptr(i8* %src.i8) argmemonly

llvm/test/Transforms/MemCpyOpt/loadstore-sret.ll

_ZNSt8auto_ptrIiED1Ev.exit:
   call void @_Z3barv(%"class.std::auto_ptr"* sret %temp.lvalue)
   %tmp.i.i = getelementptr inbounds %"class.std::auto_ptr", %"class.std::auto_ptr"* %temp.lvalue, i64 0, i32 0
   %tmp2.i.i = load i32*, i32** %tmp.i.i, align 8
   %tmp.i.i4 = getelementptr inbounds %"class.std::auto_ptr", %"class.std::auto_ptr"* %agg.result, i64 0, i32 0
   store i32* %tmp2.i.i, i32** %tmp.i.i4, align 8
   ret void
 }
 
-declare void @_Z3barv(%"class.std::auto_ptr"* nocapture sret) nounwind
+declare void @_Z3barv(%"class.std::auto_ptr"* nocapture sret) nounwind willreturn

llvm/test/Transforms/MemCpyOpt/sret.ll

entry:
   store x86_fp80 %tmp8, x86_fp80* %tmp4, align 16
   call void @ccoshl(%0* noalias sret %memtmp, %0* byval align 8 %iz) nounwind
   %memtmp14 = bitcast %0* %memtmp to i8*
   %agg.result15 = bitcast %0* %agg.result to i8*
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 16 %agg.result15, i8* align 16 %memtmp14, i32 32, i1 false)
   ret void
 }
 
-declare void @ccoshl(%0* noalias nocapture sret, %0* byval) nounwind
+declare void @ccoshl(%0* noalias nocapture sret, %0* byval) nounwind willreturn
 
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture, i8* nocapture, i32, i1) nounwind