[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

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

[rsmith]

lib/Transforms/Scalar/DeadStoreElimination.cpp

513–514

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

524

Remove unused parameter DepWrite?

test/Transforms/DeadStoreElimination/simple.ll

261

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

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

test/Transforms/DeadStoreElimination/simple.ll

261

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

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)
 ///
 /// 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;
-
-  // 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.
-  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;
+  // If the read and written loc obviously don't alias, it isn't a self-read.
+  // llvm.memcpy has undefined behavior when the source and the destination
+  // overlap so if Inst is a memcpy InstReadLoc and InstStoreLoc don't overlap
+  // by definition.
+  return !isa<MemCpyInst>(Inst) && !AA.isNoAlias(InstReadLoc, InstStoreLoc);
 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.
 /// Precondition: Second instruction must be dominated by the first
 /// instruction.
 static bool memoryIsNotModifiedBetween(Instruction *FirstI,
                                        Instruction *SecondI,

test/Transforms/DeadStoreElimination/simple.ll

define void @test17v(i8* %P, i8* %Q) nounwind ssp {
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i1 false)
   ret void
 ; CHECK-LABEL: @test17v(
 ; CHECK-NEXT: call void @llvm.memset
 ; CHECK-NEXT: call void @llvm.memcpy
 ; CHECK-NEXT: ret
 }
 
-; PR8728
-; Do not delete instruction where possible situation is:
-; A = B
-; A = A
 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
+
+; We can delete the first memcpy here even though we have no information about
+; %Q and %R.  The only way the writes to %P...%P+12 due to the first memcpy can
+; be live is if the second memcpy reads those writes.  However, the second
+; memcpy also writes to %P...%P+12 and therefore could not have read from those
+; locations without invoking undefined behavior.
+
 ; CHECK-LABEL: @test18(
-; CHECK-NEXT: call void @llvm.memcpy
-; CHECK-NEXT: call void @llvm.memcpy
+; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i1 false)
 ; CHECK-NEXT: ret
 }
 
 
 ; The store here is not dead because the byval call reads it.
 declare void @test19f({i32}* byval align 4 %P)
 
 define void @test19({i32} * nocapture byval align 4 %arg5) nounwind ssp {

 ; 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
+}
+
+define void @test38(i8* %P, i8* %Q, i8* %R) {
+; CHECK-LABEL: @test38(
+; 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)