[DSE]Split memset when the memset is small enough to be lowered to stores

[junbuml]

Summary

This change split a memset into two parts if it is partially overlapped with later stores.
We split a memset only when it is small enough to be lowered to stores in backend
and the total number of expected stores after splitting should be smaller than the original one.

[junbuml]

Minor changes in test cases.

[junbuml]

Rebased and fixed typo.

[• dberlin]

These tests don't seem to give me a lot of information about what you expect to happen and when.
Can you modify them to actually test that stores get eliminated (because if they are not, this whole thing seems speculative enough that it probably should be value profile guided in some fashion)

test/Transforms/DeadStoreElimination/SplitMemintrinsic.ll

11

Errr, so what gets eliminated here?

35

Again, if your goal is to test that perform dead store elimination, you should test that, not just test that we turn the memset into stores.

[junbuml]

These tests don't seem to give me a lot of information about what you expect to happen and when. Can you modify them to actually test that stores get eliminated (because if they are not, this whole thing seems speculative enough that it probably should be value profile guided in some fashion)

Thanks Daniel for your quick feedback. I will change the tests to check final stores impacted by this patch in DSE.

[junbuml]

Updated test cases which will now check the final stores impacted by this change.

[• dberlin]

So, in terms of high level optimization, this looks correct at a glance.
I'd wait for quentin to say whether he thinks this makes sense for LLVM's backends.
Assuming he thinks it looks good on that front, looks good to me.

lib/Transforms/Scalar/DeadStoreElimination.cpp

238

How and when can this happen?

[junbuml]

lib/Transforms/Scalar/DeadStoreElimination.cpp

238

If there is no information about LegalIntWidth extracted from datalayout, this could be 0. If we remove the target datalayout in input IR, this will be 0.

[• dberlin]

The first seems plausible, but datalayout is not optional anymore, IIRC, so
the second should be impossible.

[qcolombet]

include/llvm/Analysis/TargetTransformInfo.h

465

What about the MinSize attribute? (Oz)
Shouldn’t we just pass the Function (or its directly its list of attribute) and let the target checks whatever attribute it feels appropriate?

lib/Transforms/Scalar/DeadStoreElimination.cpp

238

Like Daniel said, DL are mandatory now. If that may still happen, (int would be an illegal type??) add a comment on when this is the case and add a test case for that!

241

Add a comment why this is not profitable. Something along the line of “this is going to be only one store”.

492

Add a comment with ASCII art like the other cases to explain what we handle here.

1069

Make a method out of this to break the nested indentation.

test/Transforms/DeadStoreElimination/SplitMemintrinsic.ll

2

I would prefer two different tests:

1. One that checks that dse does what is expected.
2. One that checks that given such input (statically available, not produced by opt), the backend does what is expected.

79

Use opt -instnamer

[junbuml]

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

lib/Transforms/Scalar/DeadStoreElimination.cpp

238

As far as I check, I didn't encounter any complain when injecting an IR without "target datalayout" into opt. Also there are many test cases without datalayout. It seems also possible to assign empty string like target datalayout="". Did the mandatory mean in IRs generated from the frontend?

If DL.getLargestLegalIntTypeSizeInBits() returns 0, I think we should bail out with the assumption that we don't have proper information about backend.

[qcolombet]

+Mehdi, who set the mandatory data layout.

[mehdi_amini]

lib/Transforms/Scalar/DeadStoreElimination.cpp

238

Having DL.getLargestLegalIntTypeSizeInBits() returning 0 would mean that someone specifically asked for not having int types supported at all.
Handling this case means that LLVM acknowledges that it aims at supporting this case. Is it possible/desirable to support this?
Otherwise an assertion would be more appropriate IMO.

[junbuml]

+Mehdi, who set the mandatory data layout.

Can you please clarify about the mandatory? The reason I'm asking is because I can still see many test cases without datalayout.

Having DL.getLargestLegalIntTypeSizeInBits() returning 0 would mean that someone specifically asked for not having int types supported at all. Handling this case means that LLVM acknowledges that it aims at supporting this case. Is it possible/desirable to support this? Otherwise an assertion would be more appropriate IMO.

If having DL.getLargestLegalIntTypeSizeInBits() returning 0 is undesirable, I think we should assert in getLargestLegalIntTypeSizeInBits().

[junbuml]

http://llvm.org/docs/doxygen/html/Module_8cpp_source.html#l00375
"const DataLayout &Module::getDataLayout() const { return DL; }"
It returns a reference, so it is guaranteed to not be null.
"No data layout in the Textual IR means "use the default data layout" for the triple."

Thanks for clarifying this. So, we are guaranteed to DL even without datalayout in the textual IR. However, this doesn't mean that we can always get the non-zero from DL.getLargestLegalIntTypeSizeInBits(). As I test, we can use an empty datalayout in IR like : target datalayout="".

Wouldn't DL.getLargestLegalIntTypeSizeInBits() == 0 imply that you can have icmp or select? Hence almost nothing in llvm would work?

Although we can make DL.getLargestLegalIntTypeSizeInBits() return 0, I also doubt when this is meaningful. If this doesn't make sense, I will add assert in getLargestLegalIntTypeSizeInBits(). Can anyone give us any feedback if there is any situation where we need to consider getLargestLegalIntTypeSizeInBits() == 0 ? As far as I test, I didn't see any unit test failure with the assert in getLargestLegalIntTypeSizeInBits() == 0.

[junbuml]

Hi Mehdi,

Do you expect DL.getLargestLegalIntTypeSizeInBits() always return non-zero?
However, using the test case added in this patch, we can easily make
DL.getLargestLegalIntTypeSizeInBits() return 0 whenever we remove
datalayout in the IR below. Please correct me if I miss something here.

; RUN: opt < %s -basicaa -dse -mtriple=arm64-linux-gnu -S

; target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"

define void @test_32_8to15(i64* nocapture %P, i64 %n64) #0 {
entry:
%0 = bitcast i64* %P to i8*
call void @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 32, i32 8, i1 false)
%arrayidx1 = getelementptr inbounds i64, i64* %P, i64 1 store i64 %n64,
i64* %arrayidx1 ret void }

Thanks,
Jun

[junbuml]

• Bail out if DL.getLargestLegalIntTypeSizeInBits() returns 0, based on the assumption that we don't have proper information about backend.
• For getMaxStoresPerMemset(), pass Function as a parameter to allow targets to check whatever desirable attribute. The current default behavior is adoppted from shouldLowerMemFuncForSize() that is used when lowering memset in backend.
• Split the test case into two : one that check output of DSE and one that check stores lowered in backend.
• Add extra comments as Quentin pointed.

Please take a look.

Thanks,
Jun

[qcolombet]

Couple additional comments.

include/llvm/Analysis/TargetTransformInfo.h

465

Is nullptr permitted for F?
If not, then use a reference.

include/llvm/Target/TargetLowering.h

966 ↗

(On Diff #59390)

Same question, nullptr OK or not?

lib/CodeGen/TargetLoweringBase.cpp

1648 ↗

(On Diff #59390)

What the comment says is correct. However, I wonder if we want to have this difference here.
I would have expected something simpler like return F->optForSize() || F->optForMinSize() for all OS.

test/Transforms/DeadStoreElimination/SplitMemintrinsic.ll

8

Don’t hard code %0.
Use a regexp.

[junbuml]

Addressed Quentin's comments. Thanks Quentin for your review!

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// performed.
   unsigned getMaxPrefetchIterationsAhead() const;
 
   /// \return The maximum interleave factor that any transform should try to
   /// perform for this target. This number depends on the level of parallelism
   /// and the number of execution units in the CPU.
   unsigned getMaxInterleaveFactor(unsigned VF) const;
 
+  /// \rreturn The maximum number of store operations permitted to replace a
+  /// call to llvm.memset.
+  unsigned getMaxStoresPerMemset(Function &F) const;
+
   /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc.
   int getArithmeticInstrCost(
       unsigned Opcode, Type *Ty, OperandValueKind Opd1Info = OK_AnyValue,
       OperandValueKind Opd2Info = OK_AnyValue,
       OperandValueProperties Opd1PropInfo = OP_None,
       OperandValueProperties Opd2PropInfo = OP_None) const;
 
   /// \return The cost of a shuffle instruction of kind Kind and of type Tp.
virtual int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                             Type *Ty) = 0;
   virtual unsigned getNumberOfRegisters(bool Vector) = 0;
   virtual unsigned getRegisterBitWidth(bool Vector) = 0;
   virtual unsigned getCacheLineSize() = 0;
   virtual unsigned getPrefetchDistance() = 0;
   virtual unsigned getMinPrefetchStride() = 0;
   virtual unsigned getMaxPrefetchIterationsAhead() = 0;
   virtual unsigned getMaxInterleaveFactor(unsigned VF) = 0;
+  virtual unsigned getMaxStoresPerMemset(Function &F) = 0;
   virtual unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) = 0;
   virtual int getShuffleCost(ShuffleKind Kind, Type *Tp, int Index,
                              Type *SubTp) = 0;
   virtual int getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) = 0;
unsigned getMinPrefetchStride() override {
     return Impl.getMinPrefetchStride();
   }
   unsigned getMaxPrefetchIterationsAhead() override {
     return Impl.getMaxPrefetchIterationsAhead();
   }
   unsigned getMaxInterleaveFactor(unsigned VF) override {
     return Impl.getMaxInterleaveFactor(VF);
   }
+  unsigned getMaxStoresPerMemset(Function &F) override {
+    return Impl.getMaxStoresPerMemset(F);
+  }
   unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) override {
     return Impl.getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
                                        Opd1PropInfo, Opd2PropInfo);
   }

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   unsigned getPrefetchDistance() { return 0; }
 
   unsigned getMinPrefetchStride() { return 1; }
 
   unsigned getMaxPrefetchIterationsAhead() { return UINT_MAX; }
 
   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 
+  unsigned getMaxStoresPerMemset(Function &F) { return 0; }
+
   unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty,
                                   TTI::OperandValueKind Opd1Info,
                                   TTI::OperandValueKind Opd2Info,
                                   TTI::OperandValueProperties Opd1PropInfo,
                                   TTI::OperandValueProperties Opd2PropInfo) {
     return 1;
   }
 

include/llvm/CodeGen/BasicTTIImpl.h

public:
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector) { return Vector ? 0 : 1; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }
 
   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 
+  unsigned getMaxStoresPerMemset(Function &F) {
+    bool OptSize = F.optForMinSize() || F.optForMinSize();
+    return getTLI()->getMaxStoresPerMemset(OptSize);
+  }
+
   unsigned getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None) {
     // Check if any of the operands are vector operands.
     const TargetLoweringBase *TLI = getTLI();

lib/Analysis/TargetTransformInfo.cpp

 unsigned TargetTransformInfo::getMaxPrefetchIterationsAhead() const {
   return TTIImpl->getMaxPrefetchIterationsAhead();
 }
 
 unsigned TargetTransformInfo::getMaxInterleaveFactor(unsigned VF) const {
   return TTIImpl->getMaxInterleaveFactor(VF);
 }
 
+unsigned TargetTransformInfo::getMaxStoresPerMemset(Function &F) const {
+  return TTIImpl->getMaxStoresPerMemset(F);
+}
+
 int TargetTransformInfo::getArithmeticInstrCost(
     unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
     OperandValueKind Opd2Info, OperandValueProperties Opd1PropInfo,
     OperandValueProperties Opd2PropInfo) const {
   int Cost = TTIImpl->getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
                                              Opd1PropInfo, Opd2PropInfo);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;

lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
static bool isRemovable(Instruction *I) {
   }
 
   if (auto CS = CallSite(I))
     return CS.getInstruction()->use_empty();
 
   return false;
 }
 
+static unsigned getExpectedNumStores(unsigned SizeInBytes,
+                                     unsigned MaxIntSizeInBytes) {
+  // Since we don't have perfect knowledge here, assume that the maximum GPR
+  // width is the same size as the largest legal integer size.
+  unsigned NumWideStores = (SizeInBytes / MaxIntSizeInBytes);
+  // Conservatively assume the remaining bytes as a byte at a time.
+  unsigned NumNarrowStores = (SizeInBytes % MaxIntSizeInBytes);
+  return NumWideStores + NumNarrowStores;
+}
+
+/// Return true if splitting memset into two parts is profitable in terms of
+/// the number of stores when lowered from the memset.
+static bool isSplittingProfitable(Instruction *EarlierStore,
+                                  int64_t NewLengthPart1,
+                                  int64_t NewLengthPart2, const DataLayout &DL,
+                                  const TargetTransformInfo *TTI) {
+  // FIXME: Split only memset for now. Supporting memcpy/memmove is also
+  // possible.
+  MemSetInst *MSI = dyn_cast<MemSetInst>(EarlierStore);
+  if (!MSI)
+    return false;
+
+  unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
+  // Return false if we don't have information about the legal integer size.
+  if (MaxIntSize == 0)
+    return false;
+
+  unsigned OrigLength = cast<ConstantInt>(MSI->getLength())->getZExtValue();
+  // Return false if the memset size is equal to the largest integer size
+  // because it's going to be only one store, or if the memset size is
+  // smaller than the largest integer size because in this case, the total
+  // nubmer of narrow stores could be different depending on backend.
+  if (OrigLength <= MaxIntSize)
+    return false;
+
+  // Check if the existing memset is small enough to be lowered to stores later.
+  unsigned NumStoresInOrigMemset = getExpectedNumStores(OrigLength, MaxIntSize);
+  if (TTI->getMaxStoresPerMemset(*(MSI->getParent()->getParent())) <
+      NumStoresInOrigMemset)
+    return false;
+
+  // Make sure that each part is also larger than the largest integer size.
+  if (NewLengthPart1 < MaxIntSize || NewLengthPart2 < MaxIntSize)
+    return false;
+
+  // The expected number of stores after splitting should be less than the
+  // expected number of stores from the original memset.
+  return NumStoresInOrigMemset >
+         (getExpectedNumStores(NewLengthPart1, MaxIntSize) +
+          getExpectedNumStores(NewLengthPart2, MaxIntSize));
+}
+
+static bool tryToSplitStore(Instruction *EarlierStore, int64_t LaterOffset,
+                            int64_t EarlierOffset, MemoryLocation &EarlierLoc,
+                            MemoryLocation &LaterLoc, const DataLayout &DL,
+                            const TargetTransformInfo *TTI) {
+
+  int64_t NewLengthPart1 = LaterOffset - EarlierOffset;
+  int64_t NewLengthPart2 = int64_t(EarlierOffset + EarlierLoc.Size) -
+                           int64_t(LaterOffset + LaterLoc.Size);
+
+  if (!isSplittingProfitable(EarlierStore, NewLengthPart1, NewLengthPart2, DL,
+                             TTI))
+    return false;
+
+  MemIntrinsic *DepIntrinsic = cast<MemIntrinsic>(EarlierStore);
+  unsigned DepWriteAlign = DepIntrinsic->getAlignment();
+  int64_t NewWriteOffset = int64_t(LaterOffset + LaterLoc.Size);
+
+  if (!((llvm::isPowerOf2_64(NewWriteOffset) &&
+         DepWriteAlign <= NewWriteOffset) ||
+        ((DepWriteAlign != 0) && NewWriteOffset % DepWriteAlign == 0)))
+    return false;
+
+  DEBUG(dbgs() << "DSE: Split MemIntrinsic :\n  " << *EarlierStore << "\n");
+  DEBUG(dbgs() << "into :\n");
+
+  Value *DepWriteLength = DepIntrinsic->getLength();
+  Value *NewLengthPart1Val =
+      ConstantInt::get(DepWriteLength->getType(), NewLengthPart1);
+  Value *NewLengthPart2Val =
+      ConstantInt::get(DepWriteLength->getType(), NewLengthPart2);
+
+  DepIntrinsic->setLength(NewLengthPart1Val);
+  DEBUG(dbgs() << "  " << *DepIntrinsic << "\n");
+
+  int64_t OffsetMoved = NewWriteOffset - EarlierOffset;
+  Value *Indices[1] = {
+      ConstantInt::get(DepWriteLength->getType(), OffsetMoved)};
+  GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
+      DepIntrinsic->getRawDest(), Indices, "", EarlierStore);
+  MemSetInst *DepIntrinsic2 = dyn_cast<MemSetInst>(DepIntrinsic->clone());
+  DepIntrinsic2->setDest(NewDestGEP);
+  DepIntrinsic2->setLength(NewLengthPart2Val);
+  DepIntrinsic2->insertAfter(DepIntrinsic);
+  DEBUG(dbgs() << "  " << *DepIntrinsic2 << "\n");
+  return true;
+}
 
 /// 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;
 
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
   return MemoryLocation::UnknownSize;
 }
 
 namespace {
 enum OverwriteResult {
   OverwriteBegin,
   OverwriteComplete,
   OverwriteEnd,
+  OverwritePartial,
   OverwriteUnknown
 };
 }
 
 /// 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
static OverwriteResult isOverwrite(const MemoryLocation &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.
+  // 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;
   }
+
+  // Finally, we need to check if the later store partially overwrites the
+  // earlier in the middle.
+  //      |------earlier------|
+  //        |--   later --|
+  //
+  // In this case we may want to split the earlier just to write to addresses
+  // which are not covered by later.
+  if (LaterOff > EarlierOff &&
+      int64_t(LaterOff + Later.Size) < int64_t(EarlierOff + Earlier.Size)) {
+    return OverwritePartial;
+  }
+
   // Otherwise, they don't completely overlap.
   return OverwriteUnknown;
 }
 
 /// 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:
 ///
if (DeadStackObjects.empty())
       break;
   }
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
+                                const TargetLibraryInfo *TLI,
+                                const TargetTransformInfo *TTI) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 
   // Do a top-down walk on the BB.
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     Instruction *Inst = &*BBI++;
 
     // Handle 'free' calls specially.
while (InstDep.isDef() || InstDep.isClobber()) {
               Value *Indices[1] = {
                   ConstantInt::get(DepWriteLength->getType(), OffsetMoved)};
               GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
                   DepIntrinsic->getRawDest(), Indices, "", DepWrite);
               DepIntrinsic->setDest(NewDestGEP);
             }
             MadeChange = true;
           }
+        } else if (OR == OverwritePartial) {
+          if (tryToSplitStore(DepWrite, InstWriteOffset, DepWriteOffset, DepLoc,
+                              Loc, DL, TTI))
+            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:
       //   store -> P
       //   store -> Q
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
   if (BB.getTerminator()->getNumSuccessors() == 0)
     MadeChange |= handleEndBlock(BB, AA, MD, TLI);
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
+                                const TargetLibraryInfo *TLI,
+                                const TargetTransformInfo *TTI) {
   bool MadeChange = false;
   for (BasicBlock &BB : F)
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
     if (DT->isReachableFromEntry(&BB))
-      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
+      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI, TTI);
   return MadeChange;
 }
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis *AA = &AM.getResult<AAManager>(F);
   DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F);
   const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
+  const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(F);
 
-  if (!eliminateDeadStores(F, AA, MD, DT, TLI))
+  if (!eliminateDeadStores(F, AA, MD, DT, TLI, TTI))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }
 
if (skipFunction(F))
       return false;
 
     DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     MemoryDependenceResults *MD =
         &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
     const TargetLibraryInfo *TLI =
         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+    const TargetTransformInfo *TTI =
+        &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
-    return eliminateDeadStores(F, AA, MD, DT, TLI);
+    return eliminateDeadStores(F, AA, MD, DT, TLI, TTI);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<MemoryDependenceWrapperPass>();
   }
 
   static char ID; // Pass identification, replacement for typeid
 };
 
 char DSELegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
                     false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() {
   return new DSELegacyPass();
 }

test/CodeGen/AArch64/aarch64-small-memset-lowering.ll

+; RUN: llc -mtriple=arm64-linux-gnu < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+define void @test_32_8to15(i64* nocapture %P, i64 %n64) {
+; CHECK-LABEL: test_32_8to15
+; CHECK: stp xzr, xzr, [x0, #16]
+; CHECK: stp xzr, x1, [x0]
+entry:
+  %Base = bitcast i64* %P to i8*
+  %Base2 = getelementptr inbounds i8, i8* %Base, i64 16
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 8, i32 8, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %Base2, i8 0, i64 16, i32 8, i1 false)
+  %arrayidx1 = getelementptr inbounds i64, i64* %P, i64 1
+  store i64 %n64, i64* %arrayidx1
+  ret void
+}
+
+define void @test_32_8to23(i64* nocapture %P, i64 %n64) {
+; CHECK-LABEL: test_32_8to23
+; CHECK: stp [[REG:x[0-9]+]], xzr, [x0, #16]
+; CHECK: stp xzr, [[REG]], [x0]
+entry:
+  %Base = bitcast i64* %P to i8*
+  %Base2 = getelementptr inbounds i8, i8* %Base, i64 24
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 8, i32 8, i1 false)
+  call void @llvm.memset.p0i8.i64(i8* %Base2, i8 0, i64 8, i32 8, i1 false)
+  %arrayidx2 = getelementptr inbounds i8, i8* %Base, i64 8
+  call void @llvm.memset.p0i8.i64(i8* %arrayidx2, i8 1, i64 16, i32 8, i1 false)
+  ret void
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)

test/Transforms/DeadStoreElimination/SplitMemintrinsic.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+define void @test_32_8to15(i64* nocapture %P, i64 %n64) {
+; CHECK:  [[BASE2:%[0-9]+]] = getelementptr inbounds i8, i8* %Base, i64 16
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 8, i32 8, i1 false)
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* [[BASE2]], i8 0, i64 16, i32 8, i1 false)
+entry:
+  %Base = bitcast i64* %P to i8*
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 32, i32 8, i1 false)
+  %arrayidx1 = getelementptr inbounds i64, i64* %P, i64  1
+  store i64 %n64, i64* %arrayidx1
+  ret void
+}
+
+define void @test_32_8to23(i64* nocapture %P, i64 %n64) {
+; CHECK-LABEL: test_32_8to23
+; CHECK:  [[BASE2:%[0-9]+]] = getelementptr inbounds i8, i8* %Base, i64 24
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 8, i32 8, i1 false)
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* [[BASE2]], i8 0, i64 8, i32 8, i1 false)
+entry:
+  %Base = bitcast i64* %P to i8*
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 32, i32 8, i1 false)
+  %arrayidx2 = getelementptr inbounds i8, i8* %Base, i64 8
+  call void @llvm.memset.p0i8.i64(i8* %arrayidx2, i8 1, i64 16, i32 8, i1 false)
+  ret void
+}
+
+define void @test_32_4x8(i64* nocapture %P, i64 %n64) {
+; The memset should be completely removed by later overlapped stores.
+; CHECK-LABEL: @test_32_4x8(
+; CHECK-NOT: call void @llvm.memset.p0i8.i64
+entry:
+  %Base = bitcast i64* %P to i8*
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 32, i32 8, i1 false)
+  ; P[2]
+  %arrayidx2 = getelementptr inbounds i64, i64* %P, i64 2
+  store i64 %n64, i64* %arrayidx2
+  ; P[3]
+  %arrayidx3 = getelementptr inbounds i64, i64* %P, i64  3
+  store i64 %n64, i64* %arrayidx3
+  ; P[1]
+  %arrayidx1 = getelementptr inbounds i64, i64* %P, i64  1
+  store i64 %n64, i64* %arrayidx1
+  ; P[0]
+  %arrayidx0 = getelementptr inbounds i64, i64* %P, i64  0
+  store i64 %n64, i64* %arrayidx0
+  ret void
+}
+
+define void @test_32_8to11(i64* nocapture %P, i32 %n32) {
+; Splitting memset may be unprofitable as the laster store could cause
+; fractions if split.
+; CHECK-LABEL: test_32_8to11
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 32, i32 8, i1 false)
+entry:
+  %Base = bitcast i64* %P to i8*
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 32, i32 8, i1 false)
+  %arrayidx1 = getelementptr inbounds i64, i64* %P, i64  1
+  %arrayidx1_32 = bitcast i64* %arrayidx1 to i32*
+  store i32 %n32, i32* %arrayidx1_32
+  ret void
+}
+
+define void @test_34_8to9(i64* nocapture %P, i16 %n16) {
+; This should not be split due to the alignment in the 2nd memset if split.
+; CHECK-LABEL: test_34_8to9
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 34, i32 8, i1 false)
+entry:
+  %Base = bitcast i64* %P to i8*
+  call void @llvm.memset.p0i8.i64(i8* %Base, i8 0, i64 34, i32 8, i1 false)
+  %arrayidx1 = getelementptr inbounds i64, i64* %P, i64  1
+  %arrayidx1_16 = bitcast i64* %arrayidx1 to i16*
+  store i16 %n16, i16* %arrayidx1_16
+  ret void
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
+