[DSE] Handle memcpy/memset with equal non-const sizes.

[fhahn]

Summary

Currently DSE misses cases where the size is a non-const IR value, even
if they match. For example, this means that llvm.memcpy/llvm.memset
calls are not eliminated, even if they write the same number of bytes.

This patch extends isOverwite to try to get IR values for the number of
bytes written from the analyzed instructions. If the values match,
alias checks are performed and the result is returned.

At the moment this only covers llvm.memcpy/llvm.memset. In the future,
we may enable MemoryLocation to also track variable sizes, but this
simple approach should allow us to cover the important cases in DSE.

[xbolva00]

Can you add test like:

llvm.memcpy(dst, src, len)
llvm.memset(dst, 0, len)

?

[asbirlea]

Changes looks good.
+1 on the additional testcase.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

393

I'd directly call AA.isMustAlias(Ealier, Later) here and forego the manual pointer cast stripping.

llvm/test/Transforms/DeadStoreElimination/memory-intrinsics-sizes.ll

73

Is it actually necessary that the parameters are noalias? This looks valid to me even if src and dst alias.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

393

Good point, I initially kept it symmetric with the code below, but it's not really needed. I adjusted that in the committed version

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
             const MemoryLocation &Later, const MemoryLocation &Earlier,
             const DataLayout &DL, const TargetLibraryInfo &TLI,
             int64_t &EarlierOff, int64_t &LaterOff, BatchAAResults &AA,
             const Function *F) {
   // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
   // get imprecise values here, though (except for unknown sizes).
   if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) {
+    // In case no constant size is known, try to an IR values for the number
+    // of bytes written and check if they match.
+    auto GetSizeFromInstr = [](const Instruction *I) -> Value * {
+      if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        switch (II->getIntrinsicID()) {
+        default:
+          return nullptr;
+        case Intrinsic::memcpy:
+        case Intrinsic::memset:
+          return II->getArgOperand(2);
+        }
+      }
+      return nullptr;
+    };
+    Value *LaterV = GetSizeFromInstr(LaterI);
+    Value *EarlierV = GetSizeFromInstr(EarlierI);
+    if (LaterV && LaterV == EarlierV && AA.isMustAlias(Earlier, Later))
+      return OW_Complete;
+
     // Masked stores have imprecise locations, but we can reason about them
     // to some extent.
     return isMaskedStoreOverwrite(LaterI, EarlierI, AA);
   }
 
   const uint64_t LaterSize = Later.Size.getValue();
   const uint64_t EarlierSize = Earlier.Size.getValue();
 
   const Value *P1 = Earlier.Ptr->stripPointerCasts();

llvm/test/Transforms/DeadStoreElimination/memory-intrinsics-sizes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -dse -S %s | FileCheck %s
 
 define void @memset_equal_size_values(i8* %ptr, i64 %len) {
 ; CHECK-LABEL: @memset_equal_size_values(
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[PTR:%.*]], i8 0, i64 [[LEN:%.*]], i1 false)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[PTR]], i8 0, i64 [[LEN]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 %len, i1 false)
   call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 %len, i1 false)
   ret void
 }
 
 define void @memset_different_size_values_1(i8* %ptr, i64 %len.1, i64 %len.2) {

 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[PTR]], i8 0, i64 [[LEN:%.*]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 100, i1 false)
   call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 %len, i1 false)
   ret void
 }
 
+define void @memset_and_store_1(i8* %ptr, i64 %len) {
+; CHECK-LABEL: @memset_and_store_1(
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i8* [[PTR:%.*]] to i64*
+; CHECK-NEXT:    store i64 123, i64* [[BC]], align 4
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[PTR]], i8 0, i64 [[LEN:%.*]], i1 false)
+; CHECK-NEXT:    ret void
+;
+  %bc = bitcast i8* %ptr to i64*
+  store i64 123, i64* %bc
+  call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 %len, i1 false)
+  ret void
+}
+
+define void @memset_and_store_2(i8* %ptr, i64 %len) {
+; CHECK-LABEL: @memset_and_store_2(
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i8* [[PTR:%.*]] to i64*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[PTR]], i8 0, i64 [[LEN:%.*]], i1 false)
+; CHECK-NEXT:    store i64 123, i64* [[BC]], align 4
+; CHECK-NEXT:    ret void
+;
+  %bc = bitcast i8* %ptr to i64*
+  call void @llvm.memset.p0i8.i64(i8* align 1 %ptr, i8 0, i64 %len, i1 false)
+  store i64 123, i64* %bc
+  ret void
+}
+
 define void @memcpy_equal_size_values(i8* noalias %src, i8* noalias %dst, i64 %len) {
 ; CHECK-LABEL: @memcpy_equal_size_values(
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST:%.*]], i8* [[SRC:%.*]], i64 [[LEN:%.*]], i1 false)
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC]], i64 [[LEN]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len, i1 false)
   ret void
 }
 
 define void @memcpy_different_size_values_1(i8* noalias %src, i8* noalias %dst, i64 %len.1, i64 %len.2) {

 ;
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 100, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len, i1 false)
   ret void
 }
 
 define void @memset_and_memcpy_equal_size_values(i8* noalias %src, i8* noalias %dst, i64 %len) {
 ; CHECK-LABEL: @memset_and_memcpy_equal_size_values(
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[DST:%.*]], i8 0, i64 [[LEN:%.*]], i1 false)
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC:%.*]], i64 [[LEN]], i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST:%.*]], i8* [[SRC:%.*]], i64 [[LEN:%.*]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* align 1 %dst, i8 0, i64 %len, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len, i1 false)
   ret void
 }
 
 define void @memset_and_memcpy_different_size_values_1(i8* noalias %src, i8* noalias %dst, i64 %len.1, i64 %len.2) {

 ;
   call void @llvm.memset.p0i8.i64(i8* align 1 %dst, i8 0, i64 100, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len.1, i1 false)
   ret void
 }
 
 define void @memcpy_and_memset_equal_size_values(i8* noalias %src, i8* noalias %dst, i64 %len) {
 ; CHECK-LABEL: @memcpy_and_memset_equal_size_values(
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST:%.*]], i8* [[SRC:%.*]], i64 [[LEN:%.*]], i1 false)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[DST]], i8 0, i64 [[LEN]], i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[DST:%.*]], i8 0, i64 [[LEN:%.*]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %len, i1 false)
   call void @llvm.memset.p0i8.i64(i8* align 1 %dst, i8 0, i64 %len, i1 false)
   ret void
 }
 
 define void @memcpy_and_memset_different_size_values_1(i8* noalias %src, i8* noalias %dst, i64 %len.1, i64 %len.2) {