[DeadStoreElimination] Shorten beginning of memset overwritten by later stores

[junbuml]

Summary

This change will shorten memset if the beginning of memset is overwritten by later stores.

[junbuml]

Kindly ping

[mcrosier]

The patch looks to be in good shape generally. I've inlined a few nits and questions/suggestions.

lib/Transforms/Scalar/DeadStoreElimination.cpp

278

The preferred doxygen style is to drop the function name in the comments.

300

The preferred doxygen style is to drop the function name in the comments.

303

Once this gets committed please file a PR unless you plan on doing the follow up work.

348

location. -> location,

429

The other interesting case -> Another interesting case

442

We also need -> Finally, we also need

452

I suspect this condition 'int64_t(LaterOff + Later.Size) < int64_t(EarlierOff + Earlier.Size)' will always be true because the OverwriteComplete case will return true when LaterEnd is >= EarlyEnd.

If I am correct and the condition is true, perhaps add an assert that it's always true.

454

I believe you dropped a comment:

// Otherwise, they don't completely overlap.

test/Transforms/DeadStoreElimination/OverwriteStoreBegin.ll

3

4to8 -> 4to7?

16

0to4 -> 0to3?

Should you decide to make this change, more instances below..

52

Perhaps add a comments stating why this transformation is unsafe (i.e., we must not change the alignment of the earlier write, if I'm not mistaken).

[junbuml]

Thanks Chad for the review. I will address your comments soon.

lib/Transforms/Scalar/DeadStoreElimination.cpp

303

Yes, I will do that.

452

Agree. If the first two condition is true and the the third condition is false, that means OverwriteComplete. As you pointed, the third condition could be an assert().

454

Oh.. Thanks ..

test/Transforms/DeadStoreElimination/OverwriteStoreBegin.ll

16

Thanks, I will fix them.

52

Okay, I will comment it.

[mgrang]

lib/Transforms/Scalar/DeadStoreElimination.cpp

341

It's better to list the enum members alphabetically.

639

Enclosing the RHS in parentheses makes it more readable.
bool IsOverwriteEnd = (OR == OverwriteEnd);

656

Parentheses not really needed:

DepLoc.Size - (InstWriteOffset - DepWriteOffset) equals DepLoc.Size - InstWriteOffset - DepWriteOffset

[junbuml]

Addressed Chad's comments.

[junbuml]

Addressed Mandeep's comments. Thanks for the review.

lib/Transforms/Scalar/DeadStoreElimination.cpp

656

DepLoc.Size - (InstWriteOffset - DepWriteOffset) is same as DepLoc.Size - InstWriteOffset + DepWriteOffset, but I think DepLoc.Size - (InstWriteOffset - DepWriteOffset) is more readable.

[mcrosier]

LGTM, assuming my minor nits are addressed.

lib/Transforms/Scalar/DeadStoreElimination.cpp

289

Any particular reason we don't support memmove? Maybe add a FIXME if it's safe to transform memmove.

303

Supporting memcpy/memmove should...

431

Please add a period.

656

I agree with Jun on this one.

[junbuml]

Addressed Chad's comments. Thanks for reviewing this.

lib/Transforms/Scalar/DeadStoreElimination.cpp

static bool isRemovable(Instruction *I) {
 
   if (auto CS = CallSite(I))
     return CS.getInstruction()->use_empty();
 
   return false;
 }
 
 
-/// isShortenable - Returns true if this instruction can be safely shortened in
-/// length.
-static bool isShortenable(Instruction *I) {
+/// isShortenableAtTheEnd - Returns true if the end of this instruction can be
+/// safely shortened in length.
+static bool isShortenableAtTheEnd(Instruction *I) {
   // Don't shorten stores for now
   if (isa<StoreInst>(I))
     return false;
 
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
       default: return false;
       case Intrinsic::memset:
       case Intrinsic::memcpy:
         // Do shorten memory intrinsics.
         return true;
     }
   }
 
   // Don't shorten libcalls calls for now.
 
   return false;
 }
 
+/// isShortenableAtTheBeginning - Returns true if the beginning of this
+/// instruction can be safely shortened in length.
+static bool isShortenableAtTheBeginning(Instruction *I) {
+  // FIXME: Handle only memset for now. Supporting memcpy should be easily done
+  // by offsetting the source address.
+  IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
+  return II && II->getIntrinsicID() == Intrinsic::memset;
+}
+
 /// getStoredPointerOperand - Return the pointer that is being written to.
 static Value *getStoredPointerOperand(Instruction *I) {
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return SI->getPointerOperand();
   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
     return MI->getDest();
 
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
                                const TargetLibraryInfo &TLI) {
   uint64_t Size;
   if (getObjectSize(V, Size, DL, &TLI))
     return Size;
   return MemoryLocation::UnknownSize;
 }
 
 namespace {
-  enum OverwriteResult
-  {
-    OverwriteComplete,
-    OverwriteEnd,
-    OverwriteUnknown
-  };
+enum OverwriteResult {
+  OverwriteBegin,
 }
 
 /// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location
-/// completely overwrites a store to the 'Earlier' location.
-/// 'OverwriteEnd' if the end of the 'Earlier' location is completely
-/// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined
+/// completely overwrites a store to the 'Earlier' location. 'OverwriteEnd' if
+/// the end of the 'Earlier' location is completely overwritten by 'Later',
+/// 'OverwriteBegin' if the beginning of the 'Earlier' location is overwritten
+/// by 'Later', or 'OverwriteUnknown' if nothing can be determined.
 static OverwriteResult isOverwrite(const MemoryLocation &Later,
                                    const MemoryLocation &Earlier,
                                    const DataLayout &DL,
                                    const TargetLibraryInfo &TLI,
                                    int64_t &EarlierOff, int64_t &LaterOff) {
   const Value *P1 = Earlier.Ptr->stripPointerCasts();
   const Value *P2 = Later.Ptr->stripPointerCasts();
 
static OverwriteResult isOverwrite(const MemoryLocation &Later,
   //    |-----  later  ------|
   //
   // We have to be careful here as *Off is signed while *.Size is unsigned.
   if (EarlierOff >= LaterOff &&
       Later.Size >= Earlier.Size &&
       uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
     return OverwriteComplete;
 
   // The other interesting case is if the later store overwrites the end of
   // the earlier store
   //
   //      |--earlier--|
   //                |--   later   --|
   //
   // In this case we may want to trim the size of earlier to avoid generating
   // writes to addresses which will definitely be overwritten later
   if (LaterOff > EarlierOff &&
       LaterOff < int64_t(EarlierOff + Earlier.Size) &&
       int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size))
     return OverwriteEnd;
 
-  // Otherwise, they don't completely overlap.
+  // We also need to check if the later store overwrites the beginning of
+  // the earlier store
+  //
+  //                |--earlier--|
+  //      |--   later   --|
+  //
+  // In this case we may want to move the destination address and trim the size
+  // of earlier to avoid generating writes to addresses which will definitely
+  // be overwritten later.
+  if (LaterOff <= EarlierOff && int64_t(LaterOff + Later.Size) > EarlierOff &&
+      int64_t(LaterOff + Later.Size) < int64_t(EarlierOff + Earlier.Size))
+    return OverwriteBegin;
+
   return OverwriteUnknown;
 }
 
 /// isPossibleSelfRead - 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)
while (InstDep.isDef() || InstDep.isClobber()) {
           MadeChange = true;
 
           // DeleteDeadInstruction can delete the current instruction in loop
           // cases, reset BBI.
           BBI = Inst->getIterator();
           if (BBI != BB.begin())
             --BBI;
           break;
-        } else if (OR == OverwriteEnd && isShortenable(DepWrite)) {
+        } else if ((OR == OverwriteEnd && isShortenableAtTheEnd(DepWrite)) ||
+                   ((OR == OverwriteBegin &&
+                     isShortenableAtTheBeginning(DepWrite)))) {
           // TODO: base this on the target vector size so that if the earlier
           // store was too small to get vector writes anyway then its likely
           // a good idea to shorten it
           // Power of 2 vector writes are probably always a bad idea to optimize
           // as any store/memset/memcpy is likely using vector instructions so
           // shortening it to not vector size is likely to be slower
-          MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite);
+          MemIntrinsic *DepIntrinsic = cast<MemIntrinsic>(DepWrite);
           unsigned DepWriteAlign = DepIntrinsic->getAlignment();
-          if (llvm::isPowerOf2_64(InstWriteOffset) ||
+          bool IsOverwriteEnd = OR == OverwriteEnd;
+          if (!IsOverwriteEnd)
+            InstWriteOffset = int64_t(InstWriteOffset + Loc.Size);
+
+          if ((llvm::isPowerOf2_64(InstWriteOffset) &&
+               DepWriteAlign <= InstWriteOffset) ||
               ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) {
 
-            DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW END: "
+            DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "
+                         << (IsOverwriteEnd ? "END" : "BEGIN") << ": "
                          << *DepWrite << "\n  KILLER (offset "
-                  << InstWriteOffset << ", "
-                  << DepLoc.Size << ")"
+                         << InstWriteOffset << ", " << DepLoc.Size << ")"
                          << *Inst << '\n');
 
-            Value* DepWriteLength = DepIntrinsic->getLength();
-            Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(),
-                                                    InstWriteOffset -
-                                                    DepWriteOffset);
+            int64_t NewLength =
+                IsOverwriteEnd
+                    ? InstWriteOffset - DepWriteOffset
+                    : DepLoc.Size - (InstWriteOffset - DepWriteOffset);
+
+            Value *DepWriteLength = DepIntrinsic->getLength();
+            Value *TrimmedLength =
+                ConstantInt::get(DepWriteLength->getType(), NewLength);
             DepIntrinsic->setLength(TrimmedLength);
+
+            if (!IsOverwriteEnd) {
+              int64_t OffsetMoved = (InstWriteOffset - DepWriteOffset);
+              Value *Indices[1] = {
+                  ConstantInt::get(DepWriteLength->getType(), OffsetMoved)};
+              GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
+                  DepIntrinsic->getRawDest(), Indices, "", DepWrite);
+              DepIntrinsic->setDest(NewDestGEP);
+            }
             MadeChange = true;
           }
         }
       }
 
       // If this is a may-aliased store that is clobbering the store value, we
       // can keep searching past it for another must-aliased pointer that stores
       // to the same location.  For example, in:

test/Transforms/DeadStoreElimination/OverwriteStoreBegin.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+define void @write4to8(i32* nocapture %p) {
+; CHECK-LABEL: @write4to8(
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %p, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+; CHECK: [[GEP:%[0-9]+]] = getelementptr inbounds i8, i8* %p3, i64 4
+; CHECK: call void @llvm.memset.p0i8.i64(i8* [[GEP]], i8 0, i64 24, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  %arrayidx1 = getelementptr inbounds i32, i32* %p, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  ret void
+}
+
+define void @write0to4(i32* nocapture %p) {
+; CHECK-LABEL: @write0to4(
+entry:
+  %p3 = bitcast i32* %p to i8*
+; CHECK: [[GEP:%[0-9]+]] = getelementptr inbounds i8, i8* %p3, i64 4
+; CHECK: call void @llvm.memset.p0i8.i64(i8* [[GEP]], i8 0, i64 24, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  store i32 1, i32* %p, align 4
+  ret void
+}
+
+define void @write0to8(i32* nocapture %p) {
+; CHECK-LABEL: @write0to8(
+entry:
+  %p3 = bitcast i32* %p to i8*
+; CHECK: [[GEP:%[0-9]+]] = getelementptr inbounds i8, i8* %p3, i64 8
+; CHECK: call void @llvm.memset.p0i8.i64(i8* [[GEP]], i8 0, i64 24, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 4, i1 false)
+  %p4 = bitcast i32* %p to i64*
+  store i64 1, i64* %p4, align 8
+  ret void
+}
+
+define void @write0to8_2(i32* nocapture %p) {
+; CHECK-LABEL: @write0to8_2(
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %p, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+; CHECK: [[GEP:%[0-9]+]] = getelementptr inbounds i8, i8* %p3, i64 4
+; CHECK: call void @llvm.memset.p0i8.i64(i8* [[GEP]], i8 0, i64 24, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  %p4 = bitcast i32* %p to i64*
+  store i64 1, i64* %p4, align 8
+  ret void
+}
+
+define void @dontwrite0to4_align8(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite0to4_align8(
+entry:
+  %p3 = bitcast i32* %p to i8*
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 8, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 8, i1 false)
+  store i32 1, i32* %p, align 4
+  ret void
+}
+
+define void @dontwrite0to2(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite0to2(
+entry:
+  %p3 = bitcast i32* %p to i8*
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 4, i1 false)
+  %p4 = bitcast i32* %p to i16*
+  store i16 1, i16* %p4, align 4
+  ret void
+}
+
+define void @dontwrite2to10(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite2to10(
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %p, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 4, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 32, i32 4, i1 false)
+  %p4 = bitcast i32* %p to i16*
+  %arrayidx2 = getelementptr inbounds i16, i16* %p4, i64 1
+  %p5 = bitcast i16* %arrayidx2 to i64*
+  store i64 1, i64* %p5, align 8
+  ret void
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
+