[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 ↗

(On Diff #53067)

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

300 ↗

(On Diff #53067)

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

303 ↗

(On Diff #53067)

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

348 ↗

(On Diff #53067)

location. -> location,

429 ↗

(On Diff #53067)

The other interesting case -> Another interesting case

442 ↗

(On Diff #53067)

We also need -> Finally, we also need

452 ↗

(On Diff #53067)

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 ↗

(On Diff #53067)

I believe you dropped a comment:

// Otherwise, they don't completely overlap.

test/Transforms/DeadStoreElimination/OverwriteStoreBegin.ll

3 ↗

(On Diff #53067)

4to8 -> 4to7?

16 ↗

(On Diff #53067)

0to4 -> 0to3?

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

52 ↗

(On Diff #53067)

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 ↗

(On Diff #53067)

Yes, I will do that.

452 ↗

(On Diff #53067)

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 ↗

(On Diff #53067)

Oh.. Thanks ..

test/Transforms/DeadStoreElimination/OverwriteStoreBegin.ll

16 ↗

(On Diff #53067)

Thanks, I will fix them.

52 ↗

(On Diff #53067)

Okay, I will comment it.

[mgrang]

lib/Transforms/Scalar/DeadStoreElimination.cpp

341 ↗

(On Diff #53067)

It's better to list the enum members alphabetically.

639 ↗

(On Diff #53067)

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

656 ↗

(On Diff #53067)

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 ↗

(On Diff #53067)

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 ↗

(On Diff #54263)

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

303 ↗

(On Diff #54263)

Supporting memcpy/memmove should...

430 ↗

(On Diff #54263)

Please add a period.

658 ↗

(On Diff #54263)

I agree with Jun on this one.

[junbuml]

Addressed Chad's comments. Thanks for reviewing this.

llvm/trunk/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
+/// Returns true if the end of this instruction can be safely shortened in
 /// length.
-static bool isShortenable(Instruction *I) {
+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.
+        // FIXME: Add memmove if it's also safe to transform.
         return true;
     }
   }
 
   // Don't shorten libcalls calls for now.
 
   return false;
 }
 
+/// 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/memmove 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
+/// 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',
+/// '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
+  // Another 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;
 
+  // Finally, 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) {
+    assert (int64_t(LaterOff + Later.Size) < int64_t(EarlierOff + Earlier.Size)
+            && "Expect to be handled as OverwriteComplete" );
+    return OverwriteBegin;
+  }
   // Otherwise, they don't completely overlap.
   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:
 ///
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:

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

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+define void @write4to7(i32* nocapture %p) {
+; CHECK-LABEL: @write4to7(
+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 @write0to3(i32* nocapture %p) {
+; CHECK-LABEL: @write0to3(
+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 @write0to7(i32* nocapture %p) {
+; CHECK-LABEL: @write0to7(
+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 @write0to7_2(i32* nocapture %p) {
+; CHECK-LABEL: @write0to7_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
+}
+
+; We do not trim the beginning of the eariler write if the alignment of the
+; start pointer is changed.
+define void @dontwrite0to3_align8(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite0to3_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 @dontwrite0to1(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite0to1(
+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 @dontwrite2to9(i32* nocapture %p) {
+; CHECK-LABEL: @dontwrite2to9(
+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
+