[DSE] Don't DSE stores that subsequent memmove calls read from

[sanjoy]

Summary

We used to remove the first memmove in cases like this:

memmove(p, p+2, 8);
memmove(p, p+2, 8);

which is incorrect. Fix this by changing isPossibleSelfRead to what was most
likely the intended behavior.

Historical note: the buggy code was added in https://reviews.llvm.org/rL120974
to address PR8728.

[efriedma]

test/Transforms/DeadStoreElimination/simple.ll

261 ↗

(On Diff #134777)

See https://bugs.llvm.org/show_bug.cgi?id=11763 .

[rsmith]

lib/Transforms/Scalar/DeadStoreElimination.cpp

513–514 ↗

(On Diff #134777)

Change these to memmove so the second line isn't UB.

524 ↗

(On Diff #134777)

Remove unused parameter DepWrite?

test/Transforms/DeadStoreElimination/simple.ll

261 ↗

(On Diff #134777)

Gross. Until we figure out what we're going to do about that, perhaps we should just treat memcpy the same as memmove here.

[sanjoy]

• Relax memcpy handling

[sanjoy]

Reverted back to a more conservative memcpy handling.

lib/Transforms/Scalar/DeadStoreElimination.cpp

524 ↗

(On Diff #134777)

Not relevant anymore since in this version of the patch I use DepWrite.

test/Transforms/DeadStoreElimination/simple.ll

261 ↗

(On Diff #134777)

Wow, that's a huge omission from the langref (which specifically says that the source and destination cannot overlap).

Given that, the previous code makes more sense to me that it did initially.

[efriedma]

LGTM

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

static OverwriteResult isOverwrite(const MemoryLocation &Later,
   // Otherwise, they don't completely overlap.
   return OW_Unknown;
 }
 
 /// If 'Inst' might be a self read (i.e. a noop copy of a
 /// memory region into an identical pointer) then it doesn't actually make its
 /// input dead in the traditional sense.  Consider this case:
 ///
-///   memcpy(A <- B)
-///   memcpy(A <- A)
+///   memmove(A <- B)
+///   memmove(A <- A)
 ///
 /// In this case, the second store to A does not make the first store to A dead.
 /// The usual situation isn't an explicit A<-A store like this (which can be
 /// trivially removed) but a case where two pointers may alias.
 ///
 /// This function detects when it is unsafe to remove a dependent instruction
 /// because the DSE inducing instruction may be a self-read.
 static bool isPossibleSelfRead(Instruction *Inst,
                                const MemoryLocation &InstStoreLoc,
                                Instruction *DepWrite,
                                const TargetLibraryInfo &TLI,
                                AliasAnalysis &AA) {
   // Self reads can only happen for instructions that read memory.  Get the
   // location read.
   MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
-  if (!InstReadLoc.Ptr) return false;  // Not a reading instruction.
+  if (!InstReadLoc.Ptr)
+    return false; // Not a reading instruction.
 
   // If the read and written loc obviously don't alias, it isn't a read.
-  if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false;
+  if (AA.isNoAlias(InstReadLoc, InstStoreLoc))
+    return false;
 
-  // Okay, 'Inst' may copy over itself.  However, we can still remove a the
-  // DepWrite instruction if we can prove that it reads from the same location
-  // as Inst.  This handles useful cases like:
-  //   memcpy(A <- B)
-  //   memcpy(A <- B)
-  // Here we don't know if A/B may alias, but we do know that B/B are must
-  // aliases, so removing the first memcpy is safe (assuming it writes <= #
-  // bytes as the second one.
+  if (isa<MemCpyInst>(Inst)) {
+    // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
+    // but in practice memcpy(A <- B) either means that A and B are disjoint or
+    // are equal (i.e. there are not partial overlaps).  Given that, if we have:
+    //
+    //   memcpy/memmove(A <- B)  // DepWrite
+    //   memcpy(A <- B)  // Inst
+    //
+    // with Inst reading/writing a >= size than DepWrite, we can reason as
+    // follows:
+    //
+    //   - If A == B then both the copies are no-ops, so the DepWrite can be
+    //     removed.
+    //   - If A != B then A and B are disjoint locations in Inst.  Since
+    //     Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
+    //     Therefore DepWrite can be removed.
     MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
 
     if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
       return false;
+  }
 
   // If DepWrite doesn't read memory or if we can't prove it is a must alias,
   // then it can't be considered dead.
   return true;
 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.

llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll

 ; CHECK-NEXT: call void @llvm.memcpy
 ; CHECK-NEXT: ret
 }
 
 ; PR8728
 ; Do not delete instruction where possible situation is:
 ; A = B
 ; A = A
+;
+; NB! See PR11763 - currently LLVM allows memcpy's source and destination to be
+; equal (but not inequal and overlapping).
 define void @test18(i8* %P, i8* %Q, i8* %R) nounwind ssp {
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
   ret void
 ; CHECK-LABEL: @test18(
 ; CHECK-NEXT: call void @llvm.memcpy
 ; CHECK-NEXT: call void @llvm.memcpy
 ; CHECK-NEXT: ret

 ; CHECK-NEXT: store i32 0
 ; CHECK-NEXT: ret void
 define void @test35(i32* noalias %p) {
   call void @unknown_func()
   store i32 1, i32* %p
   store i32 0, i32* %p
   ret void
 }
+
+; We cannot optimize away the first memmove since %P could overlap with %Q.
+define void @test36(i8* %P, i8* %Q) {
+; CHECK-LABEL: @test36(
+; CHECK-NEXT:  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+; CHECK-NEXT:  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+; CHECK-NEXT:  ret
+
+  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+  ret void
+}
+
+define void @test37(i8* %P, i8* %Q, i8* %R) {
+; CHECK-LABEL: @test37(
+; CHECK-NEXT:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+; CHECK-NEXT:  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
+; CHECK-NEXT:  ret
+
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
+  ret void
+}
+
+; Same caveat about memcpy as in @test18 applies here.
+define void @test38(i8* %P, i8* %Q, i8* %R) {
+; CHECK-LABEL: @test38(
+; CHECK-NEXT:  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+; CHECK-NEXT:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
+; CHECK-NEXT:  ret
+
+  tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
+  ret void
+}
+
+define void @test39(i8* %P, i8* %Q, i8* %R) {
+; CHECK-LABEL: @test39(
+; CHECK-NEXT:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+; CHECK-NEXT:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 8, i1 false)
+; CHECK-NEXT:  ret
+
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 8, i1 false)
+  ret void
+}
+
+declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i1)