[InstCombine] Allow memcpys from constant memory to readonly nocapture parameters to be elided.

[pcwalton]

Summary

Currently, InstCombine can elide a memcpy from a constant to a local alloca if
that alloca is passed as a nocapture parameter to a *function* that's readnone
or readonly, but it can't forward the memcpy if the *argument* is marked
readonly nocapture, even though readonly guarantees that the callee won't
mutate the pointee through that pointer. This patch adds support for detecting
and handling such situations, which arise relatively frequently in Rust, a
frontend that liberally emits readonly.

A more general version of this optimization would use alias analysis to check
the call's ModRef info for the pointee, but I was concerned about blowing up
compile time, so for now I'm just checking for one of readnone on the function,
readonly on the function, or readonly on the parameter.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

92

Use onlyReadsMemory(DataOpNo) here, to also handle readnone implicitly.

93

Do we actually need the noalias requirement here? The code in this function should visit all uses of the alloca and bail out on any captures. So if there is a second argument based on the alloca that is not readonly, then we would reject it at that point. Does that sound right?

llvm/test/Transforms/InstCombine/forward-memcpy-to-readonly-noalias.ll

4 ↗

(On Diff #471071)

Use update_test_checks.py please.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

92

Noticed a pre-existing issue while reviewing this, fixed in https://reviews.llvm.org/D136834.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

91–93

I think this change introduces a subtle bug wrt capturing: If we have call without return value that is not-nocapture and not-readonly, and only the parameter is readonly, then the parameter might be captured by writing to some other location (e.g. a global) and then the captured pointer might be used after the call in a way we can't inspect.

So I think if only the parameter is readonly, then we need to require that it is nocapture as well.

[pcwalton]

Addressed review comments.

[pcwalton]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

93

Good point! I'll remove that.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

91–93

Nit: It's kind of odd that you negate doesNotCapture here, and then negate it again at both uses.

93

Why the IsArgOperand check here?

llvm/test/Transforms/InstCombine/forward-memcpy-to-readonly.ll

4 ↗

(On Diff #471270)

It looks like the existing tests for this transform are in memcpy-from-global.ll, I'd suggest adding the new test cases there as well. test3-test9 have call-related cases.

17 ↗

(On Diff #471270)

Drop noundef/nonnull here, as they are not relevant to the transform.

There should be two additional negative tests, where the transform does not occur:

• Argument is only readonly, without nocapture.
• The pointer is also passed to a second argument that is not readonly.

[nikic]

By the way, the asan test failure in printf-5.c may be legitimate. Sometimes, this kind of change ends up optimizing away the code causing the asan failure. In that case it's necessary to adjust the test case to prevent the optimization.

[pcwalton]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

93

Hmm, it was necessary to avoid an assert in varargs in earlier versions of the patch that checked the attributes directly, but it doesn't seem necessary anymore. I'll remove it.

[pcwalton]

Review comments addressed. I tried to fix the asan test as well; let me know if that approach looks good.

[nikic]

compiler-rt/test/asan/TestCases/printf-5.c

22

I'm really confused by what this test is trying to do with the memcpy here. Would the test pass with just volatile char fmt[2] = "%c"? That'll produce a volatile memcpy, and that shouldn't get optimized away.

llvm/test/Transforms/InstCombine/memcpy-from-global.ll

350

This can be call void @bar(ptr nocapture readonly %A). We don't need separate functions and can vary the attributes at the call-site only. Same below.

[pcwalton]

Addressed review comments.

[pcwalton]

Addresses comments.

I actually found that this optimization was kicking in even for volatile
allocas. I assume this was a bug, so I fixed it and added a test case.

[pcwalton]

compiler-rt/test/asan/TestCases/printf-5.c

22

Turns out that InstCombine was optimizing away volatile memcpys. I fixed that, added a new test for it, and then made the change you suggested.

[nikic]

Can you please precommit your test cases (they look fine) and split off the volatile change into a separate patch? I agree that this was a bug, but it's not directly related to the change here.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

131

There is another volatile check above, just drop the operand check there?

[pcwalton]

I split the tests out to D137033.

[pcwalton]

Rebased. This should be ready for sign off now.

[nikic]

LGTM, but the patch description could use an update (no longer relies on noalias).

[pcwalton]

Rebased to make sure CI succeeds.

[pcwalton]

Failure seems like an unrelated Windows Fortran build error.

compiler-rt/test/asan/TestCases/printf-5.c

 #include <stdio.h>
 #include <string.h>
 int main() {
   volatile char c = '0';
   volatile int x = 12;
   volatile float f = 1.239;
   volatile char s[] = "34";
   volatile char fmt[2];
-  memcpy((char *)fmt, "%c %d %f %s\n", sizeof(fmt));
+  // If we use memcpy here, then the volatile qualifier will be casted away
+  // and the stack copy is vulnerable to being optimized out, so we use a
+  // for loop.
+  for (unsigned i = 0; i < sizeof(fmt); i++)
+    fmt[i] = "%c %d %f %s\n"[i];
   printf((char *)fmt, c, x, f, s);
   return 0;
   // Check that format string is sanitized.
   // CHECK-ON: stack-buffer-overflow
   // CHECK-ON-NOT: 0 12 1.239 34
   // CHECK-OFF: 0
 }

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
 /// pointer to an alloca.  Ignore any reads of the pointer, return false if we
 /// see any stores or other unknown uses.  If we see pointer arithmetic, keep
 /// track of whether it moves the pointer (with IsOffset) but otherwise traverse
 /// the uses.  If we see a memcpy/memmove that targets an unoffseted pointer to
 /// the alloca, and if the source pointer is a pointer to a constant global, we
 /// can optimize this.
 static bool
-isOnlyCopiedFromConstantMemory(AAResults *AA,
-                               Value *V, MemTransferInst *&TheCopy,
+isOnlyCopiedFromConstantMemory(AAResults *AA, AllocaInst *V,
+                               MemTransferInst *&TheCopy,
                                SmallVectorImpl<Instruction *> &ToDelete) {
   // We track lifetime intrinsics as we encounter them.  If we decide to go
   // ahead and replace the value with the global, this lets the caller quickly
   // eliminate the markers.
 
   SmallVector<std::pair<Value *, bool>, 35> ValuesToInspect;
   ValuesToInspect.emplace_back(V, false);
   while (!ValuesToInspect.empty()) {
for (auto &U : ValuePair.first->uses()) {
 
         unsigned DataOpNo = Call->getDataOperandNo(&U);
         bool IsArgOperand = Call->isArgOperand(&U);
 
         // Inalloca arguments are clobbered by the call.
         if (IsArgOperand && Call->isInAllocaArgument(DataOpNo))
           return false;
 
-        // If this is a readonly/readnone call site, then we know it is just a
-        // load (but one that potentially returns the value itself), so we can
+        // If this call site doesn't modify the memory, then we know it is just
+        // a load (but one that potentially returns the value itself), so we can
         // ignore it if we know that the value isn't captured.
-        if (Call->onlyReadsMemory() &&
-            (Call->use_empty() || Call->doesNotCapture(DataOpNo)))
+        bool NoCapture = Call->doesNotCapture(DataOpNo);
+        if ((Call->onlyReadsMemory() && (Call->use_empty() || NoCapture)) ||
+            (Call->onlyReadsMemory(DataOpNo) && NoCapture))
           continue;
 
         // If this is being passed as a byval argument, the caller is making a
         // copy, so it is only a read of the alloca.
         if (IsArgOperand && Call->isByValArgument(DataOpNo))
           continue;
       }
 
for (auto &U : ValuePair.first->uses()) {
       if (TheCopy) return false;
 
       // If the pointer has been offset from the start of the alloca, we can't
       // safely handle this.
       if (IsOffset) return false;
 
       // If the memintrinsic isn't using the alloca as the dest, reject it.
       if (U.getOperandNo() != 0) return false;
 
       // If the source of the memcpy/move is not a constant global, reject it.
       if (!AA->pointsToConstantMemory(MI->getSource()))
         return false;
 
       // Otherwise, the transform is safe.  Remember the copy instruction.
       TheCopy = MI;
     }
   }

llvm/test/Transforms/InstCombine/memcpy-from-global.ll

entry:
   %a = alloca [4 x float], align 4
   call void @llvm.lifetime.start.p0(i64 16, ptr %a)
   call void @llvm.memcpy.p0.p1.i64(ptr align 4 %a, ptr addrspace(1) align 4 @I, i64 16, i1 true)
   %g = getelementptr inbounds [4 x float], ptr %a, i64 0, i64 %i
   %r = load float, ptr %g, align 4
   ret float %r
 }
 
+; Test that we can elide a memcpy when copying a constant value onto the stack
+; and then forwarding it by readonly nocapture reference.
+define void @test12() {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    call void @readonly_nocapture(ptr nocapture nonnull readonly @H)
+; CHECK-NEXT:    ret void
+;
+  %A = alloca %U, align 16
+  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %A, ptr align 4 @H, i64 20, i1 false)
+  call void @readonly_nocapture(ptr nocapture readonly %A)
+  ret void
+}
+
+declare void @readonly_nocapture(ptr nocapture readonly)
+
+; Test that we don't elide the memcpy when copying a constant value onto the
+; stack and then forwarding it by readonly, but capturing, reference.
+define void @test13() {
+; CHECK-LABEL: @test13(
+; CHECK-NEXT:    [[A:%.*]] = alloca [[U:%.*]], align 16
+; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 16 dereferenceable(20) [[A]], ptr noundef nonnull align 16 dereferenceable(20) @H, i64 20, i1 false)
+; CHECK-NEXT:    call void @just_readonly(ptr nonnull readonly [[A]])
+; CHECK-NEXT:    ret void
+;
+  %A = alloca %U, align 16
+  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %A, ptr align 4 @H, i64 20, i1 false)
+  call void @just_readonly(ptr readonly %A)
+  ret void
+}
+
+declare void @just_readonly(ptr readonly)
+
+; Test that we don't elide the memcpy when copying a constant value onto the
+; stack and then forwarding it by read-write, nocapture reference, even if it's
+; also forwarded by readonly nocapture reference to the same function.
+define void @test14() {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT:    [[A:%.*]] = alloca [[U:%.*]], align 16
+; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 16 dereferenceable(20) [[A]], ptr noundef nonnull align 16 dereferenceable(20) @H, i64 20, i1 false)
+; CHECK-NEXT:    call void @two_params(ptr nocapture nonnull readonly [[A]], ptr nocapture nonnull [[A]])
+; CHECK-NEXT:    ret void
+;
+  %A = alloca %U, align 16
+  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %A, ptr align 4 @H, i64 20, i1 false)
+  call void @two_params(ptr nocapture readonly %A, ptr nocapture %A)
+  ret void
+}
+
+declare void @two_params(ptr nocapture readonly, ptr nocapture)
+
 attributes #0 = { null_pointer_is_valid }