[DSE] Merge stores when the later store only writes to memory locations the early store also wrote to.

[spatel]

Summary

This fixes PR31777.

If both stores' values are ConstantInt, we merge the two stores
(shifting the smaller store appropriately) and replace the earlier (and
larger) store with an updated constant.

In the future we should also support vectors of integers. And maybe
float/double if we can.

[filcab]

Added a test where we need to merge the same byte several times.

[junbuml]

test/Transforms/DeadStoreElimination/merge-stores.ll

6 ↗

(On Diff #90879)

I think the current code should handle this.

[filcab]

test/Transforms/DeadStoreElimination/merge-stores.ll

6 ↗

(On Diff #90879)

This specific test is about making sure we still do the current optimization (remove a store that's later shadowed by other stores). The code I added doesn't fire on this one (and it shouldn't). I can probably move it to the combine-partial-overwrites.ll test to make it consistent, though.

Some of the tests there got changed due to this patch.

[filcab]

Removed unneeded tests and disabled the new optimization in the old tests.

[RKSimon]

lib/Transforms/Scalar/DeadStoreElimination.cpp

301 ↗

(On Diff #91053)

As a NFC pre-commit please can you update these to match the style guide (OW_Begin ..... OW_Unknown)

test/Transforms/DeadStoreElimination/merge-stores.ll

6 ↗

(On Diff #90879)

Commit test with current codegen? Is it feasible to use update_test_checks.py here?

[filcab]

Added a big endian version of the test
Did the OW_... change in trunk, rebases
Used update_test_checks.py for the tests. A new run won't change the output.

[davide]

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

[filcab]

In D30703#714535, @davide wrote:

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

Thanks! I've looked at D29866 and it seems like it *might* deal with partial store merging/elimination in the future. But it's in a TODO, for now. So I think we could go ahead with this and, when PDSE grows that functionality, then remove it from here (or even just replace DSE with PDSE and we're done :-) ).
Thank you,
Filipe

[• dberlin]

In D30703#716674, @filcab wrote:

In D30703#714535, @davide wrote:

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

Thanks! I've looked at D29866 and it seems like it *might* deal with partial store merging/elimination in the future. But it's in a TODO, for now. So I think we could go ahead with this and, when PDSE grows that functionality, then remove it from here (or even just replace DSE with PDSE and we're done :-) ).
Thank you,
Filipe

Just FYI, i expect we're going to add it prior to first commit.
It's not that hard.

(i don't have an opinion on this patch)

[filcab]

Ping!

[sanjoy]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1192 ↗

(On Diff #93500)

You also need to copy over the atomicity of the previous store (which can only be unordered).

[filcab]

Address Sanjoy's comment and add Synchscope and atomic settings from the original store.

[RKSimon]

What is happening with this patch? Is PDSE likely to land anytime soon (e.g. for the 5.000 release?) and support this case?

[filcab]

@sanjoy: Are you ok with the changes I made?

Thank you,
Filipe

[sanjoy]

Some comments inline.

lib/Transforms/Scalar/DeadStoreElimination.cpp

307 ↗

(On Diff #99024)

Update doc.

446 ↗

(On Diff #99024)

Can LaterOff - EarlierOff sign overflow (in artificial but legal cases)?

452 ↗

(On Diff #99024)

Shouldn't this be FullEarlierWithPartialLater?

In a second change, I'd suggest changing the naming scheme to:

OW_Begin - OW_Prefix
OW_Complete - OW_Complete
OW_End - OW_Suffix
OW_PartialEarlierWithFullLater - OW_Partial
OW_Unknown - OW_Unknown

1178 ↗

(On Diff #99024)

I'd call this LShiftAmount.

1196 ↗

(On Diff #99024)

I'm not sure if copyMetadata is correct here. Someone could be using metadata to track "the value I'm storing here is positive" which may no longer be true after the rewrite. I think you should copy whitelisted metadata types (like !tbaa).

1200 ↗

(On Diff #99024)

Why is this needed? store instructions should not have users (and a WeakTrackingVH on a store is most likely doing the wrong thing).

[filcab]

Address Sanjoy's review comments

[filcab]

Hi @sanjoy. Can you take a look at the revised changes?

Thank you,
Filipe

lib/Transforms/Scalar/DeadStoreElimination.cpp

446 ↗

(On Diff #99024)

Probably yes. Redoing the math.

1 - Make sure LaterOff is between EarlierOff and EarlierOff + Earlier.Size. We know that addition won't overflow (if it does, the bug is in GetPointerBaseWithConstantOffset), so we'll know we can subtract EarlierOff from LaterOff later without problems, since they're ordered that way and the difference will be smaller than Earlier.Size.

452 ↗

(On Diff #99024)

Partial earlier store gets overwritten by a latter store (and the latter store doesn't write outside the "full" earlier store).

It's a weird way to phrase it, but I don't think changing it to your suggestion makes much sense (but I think I know what you mean).
I do think your renaming proposal for the whole enum makes sense, so I'll do that one.

1200 ↗

(On Diff #99024)

Removed.

[RKSimon]

ping?

[filcab]

Update for newer SynchScope API.
@sanjoy: Any thoughts?

Thank you,
Filipe

[sanjoy]

LGTM

lib/Transforms/Scalar/DeadStoreElimination.cpp

1213 ↗

(On Diff #108928)

s|////|//|

446 ↗

(On Diff #104882)

latter is correct, but I'd s/latter/later/ since that's what the source says.

[rnk]

We're seeing null derefs on some code in Chromium after this patch:

ninja -v -d keeprsp -C out\clang_tot obj/third_party/angle/libANGLE/Caps.obj
ninja.exe -v -d keeprsp -C out\clang_tot obj/third_party/angle/libANGLE/Caps.obj -j 46 -l 48
ninja: Entering directory `out\clang_tot'
[1 processes, 1/1 @ 0.2/s : 4.732s ] ../../third_party/llvm-build/Release+Asserts/bin/clang-cl.exe /nologo /showIncludes  @obj/third_party/angle/libANGLE/Caps.obj.rsp /c ../../third_party/angle/src/libANGLE/Caps.cpp /Foobj/third_party/angle/libANGLE/Caps.obj /Fd"obj/third_party/angle/libANGLE_cc.pdb"
FAILED: obj/third_party/angle/libANGLE/Caps.obj
../../third_party/llvm-build/Release+Asserts/bin/clang-cl.exe /nologo /showIncludes  @obj/third_party/angle/libANGLE/Caps.obj.rsp /c ../../third_party/angle/src/libANGLE/Caps.cpp /Foobj/third_party/angle/libANGLE/Caps.obj /Fd"obj/third_party/angle/libANGLE_cc.pdb"
Assertion failed: Val && "isa<> used on a null pointer", file C:\src\chromium3\src\third_party\llvm\include\llvm/Support/Casting.h, line 106
Wrote crash dump file "c:\src\Temp\clang-cl.exe-d4113f.dmp"
#0 0x00007ff6f6338775 HandleAbort c:\src\chromium3\src\third_party\llvm\lib\support\windows\signals.inc:411:0
#1 0x00007ff6f7b99769 raise minkernel\crts\ucrt\src\appcrt\misc\signal.cpp:516:0
#2 0x00007ff6f7b86df8 abort minkernel\crts\ucrt\src\appcrt\startup\abort.cpp:71:0
#3 0x00007ff6f7b86532 common_assert_to_stderr<wchar_t> minkernel\crts\ucrt\src\appcrt\startup\assert.cpp:149:0
#4 0x00007ff6f7b865ce _wassert minkernel\crts\ucrt\src\appcrt\startup\assert.cpp:404:0
#5 0x00007ff6f5ed6de3 llvm::GEPOperator::hasAllZeroIndices(void)const  c:\src\chromium3\src\third_party\llvm\include\llvm\ir\operator.h:456:0
#6 0x00007ff6f5ed32fe `anonymous namespace'::stripPointerCastsAndOffsets<1> c:\src\chromium3\src\third_party\llvm\lib\ir\value.cpp:483:0
#7 0x00007ff6f61bd100 isOverwrite c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:326:0
#8 0x00007ff6f61b9bd6 eliminateDeadStores c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1131:0
#9 0x00007ff6f61ba7d7 eliminateDeadStores c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1265:0
#10 0x00007ff6f61bf55c `anonymous namespace'::DSELegacyPass::runOnFunction c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1308:0
#11 0x00007ff6f5ee35fd llvm::FPPassManager::runOnFunction(class llvm::Function &) c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1514:0
#12 0x00007ff6f5bdae07 `anonymous namespace'::CGPassManager::RunPassOnSCC c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:149:0
#13 0x00007ff6f5bdab93 `anonymous namespace'::CGPassManager::RunAllPassesOnSCC c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:418:0
#14 0x00007ff6f5bdba59 `anonymous namespace'::CGPassManager::runOnModule c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:474:0
#15 0x00007ff6f5ee3a3e `anonymous namespace'::MPPassManager::runOnModule c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1591:0
#16 0x00007ff6f5ee2ef1 llvm::legacy::PassManagerImpl::run(class llvm::Module &) c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1695:0
#17 0x00007ff6f653810c `anonymous namespace'::EmitAssemblyHelper::EmitAssembly c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\backendutil.cpp:788:0
#18 0x00007ff6f653a140 clang::EmitBackendOutput(class clang::DiagnosticsEngine &,class clang::HeaderSearchOptions const &,class clang::CodeGenOptions const &,class clang::TargetOptions const &,class clang::LangOptions const &,class llvm::DataLayout const &,class llvm::Module *,enum clang::BackendAction,class std::unique_ptr<class llvm::raw_pwrite_stream,struct std::default_delete<class llvm::raw_pwrite_stream> >) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\backendutil.cpp:1148:0
#19 0x00007ff6f7cc3a31 clang::BackendConsumer::HandleTranslationUnit(class clang::ASTContext &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\codegenaction.cpp:265:0
#20 0x00007ff6f68c6cbc clang::MultiplexConsumer::HandleTranslationUnit(class clang::ASTContext &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\multiplexconsumer.cpp:305:0
#21 0x00007ff6f6f224d6 clang::ParseAST(class clang::Sema &,bool,bool) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\parse\parseast.cpp:162:0
#22 0x00007ff6f688654d clang::ASTFrontendAction::ExecuteAction(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\frontendaction.cpp:1005:0
#23 0x00007ff6f7cc30fb clang::CodeGenAction::ExecuteAction(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\codegenaction.cpp:992:0
#24 0x00007ff6f68863db clang::FrontendAction::Execute(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\frontendaction.cpp:906:0
#25 0x00007ff6f6873b65 clang::CompilerInstance::ExecuteAction(class clang::FrontendAction &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\compilerinstance.cpp:981:0
#26 0x00007ff6f68f7bfd clang::ExecuteCompilerInvocation(class clang::CompilerInstance *) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontendtool\executecompilerinvocation.cpp:252:0
#27 0x00007ff6f4fc5ff4 cc1_main(class llvm::ArrayRef<char const *>,char const *,void *) c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\cc1_main.cpp:221:0
#28 0x00007ff6f4fc1d40 ExecuteCC1Tool c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\driver.cpp:313:0
#29 0x00007ff6f4fc3b3a main c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\driver.cpp:387:0
#30 0x00007ff6f7b6349d __scrt_common_main_seh f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl:283:0
#31 0x00007ff855298364 (C:\WINDOWS\System32\KERNEL32.DLL+0x8364)
#32 0x00007ff855e870d1 (C:\WINDOWS\SYSTEM32\ntdll.dll+0x670d1)
clang-cl.exe: error: clang frontend command failed due to signal (use -v to see invocation

I'll try to get a repro, but heads up.

[RKSimon]

Reopening as it was reverted at rL310123 due to PR34074

[RKSimon]

PR34074

[spatel]

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

1219–1221

I think @filcab is unable to get back to this patch currently and D29866 is not progressing.

I don't have a full understanding of DSE, but I'll propose a one-word fix to this patch (and an additional test case). It should avoid the bug that caused the patch to be reverted ( https://bugs.llvm.org/show_bug.cgi?id=34074 ).

This 'continue' should be a 'break'. We killed 'Inst' above, so 'InstDep' is no longer valid. Therefore, we can't carry on in the inner loop; we need to break back out to the outer loop and really 'start over' as the comment already says. :)

[spatel]

Commandeering so I can post the updated patch here.

[spatel]

Patch updated:

1. Break from the inner loop after we successfully merge (kill) the earlier and later stores.
2. Add test reduced from PR34074 that was crashing.

[filcab]

In D30703#880203, @spatel wrote:

Patch updated:

1. Break from the inner loop after we successfully merge (kill) the earlier and later stores.
2. Add test reduced from PR34074 that was crashing.

Thanks for comandeering and fixing it, Sanjay!
Your fix looks good on my end.

[RKSimon]

LGTM - cheers

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

 #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"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <map>
 using namespace llvm;
 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
 STATISTIC(NumFastStores, "Number of stores deleted");
 STATISTIC(NumFastOther , "Number of other instrs removed");
 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
+STATISTIC(NumModifiedStores, "Number of stores modified");
 
 static cl::opt<bool>
 EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial-overwrite tracking in DSE"));
 
+static cl::opt<bool>
+EnablePartialStoreMerging("enable-dse-partial-store-merging",
+  cl::init(true), cl::Hidden,
+  cl::desc("Enable partial store merging in DSE"));
+
 
 //===----------------------------------------------------------------------===//
 // Helper functions
 //===----------------------------------------------------------------------===//
 typedef std::map<int64_t, int64_t> OverlapIntervalsTy;
 typedef DenseMap<Instruction *, OverlapIntervalsTy> InstOverlapIntervalsTy;
 
 /// Delete this instruction.  Before we do, go through and zero out all the
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 { OW_Begin, OW_Complete, OW_End, OW_Unknown };
+enum OverwriteResult {
+  OW_Begin,
+  OW_Complete,
+  OW_End,
+  OW_PartialEarlierWithFullLater,
+  OW_Unknown
+};
 }
 
 /// Return 'OW_Complete' if a store to the 'Later' location completely
 /// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
 /// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
-/// beginning of the 'Earlier' location is overwritten by 'Later', or
-/// 'OW_Unknown' if nothing can be determined.
+/// beginning of the 'Earlier' location is overwritten by 'Later'.
+/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
+/// overwritten by a latter (smaller) store which doesn't write outside the big
+/// store's memory locations. Returns 'OW_Unknown' 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,
                                    Instruction *DepWrite,
                                    InstOverlapIntervalsTy &IOL) {
   // If we don't know the sizes of either access, then we can't do a comparison.
if (ILI->second <= EarlierOff &&
                       int64_t(EarlierOff + Earlier.Size) <<
                       ") Composite Later [" <<
                       ILI->second << ", " << ILI->first << ")\n");
       ++NumCompletePartials;
       return OW_Complete;
     }
   }
 
+  // Check for an earlier store which writes to all the memory locations that
+  // the later store writes to.
+  if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
+      int64_t(EarlierOff + Earlier.Size) > LaterOff &&
+      uint64_t(LaterOff - EarlierOff) + Later.Size <= Earlier.Size) {
+    DEBUG(dbgs() << "DSE: Partial overwrite an earlier load [" << EarlierOff
+                 << ", " << int64_t(EarlierOff + Earlier.Size)
+                 << ") by a later store [" << LaterOff << ", "
+                 << int64_t(LaterOff + Later.Size) << ")\n");
+    // TODO: Maybe come up with a better name?
+    return OW_PartialEarlierWithFullLater;
+  }
+
   // 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
while (InstDep.isDef() || InstDep.isClobber()) {
         }
         if (!IsStoreDeadOnUnwind)
           break;
       }
 
       // If we find a write that is a) removable (i.e., non-volatile), b) is
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.
+      // Also try to merge two stores if a later one only touches memory written
+      // to by the earlier one.
       if (isRemovable(DepWrite) &&
           !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
         int64_t InstWriteOffset, DepWriteOffset;
         OverwriteResult OR =
             isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset,
                         DepWrite, IOL);
         if (OR == OW_Complete) {
           DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
while (InstDep.isDef() || InstDep.isClobber()) {
           assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
                                                     "when partial-overwrite "
                                                     "tracking is enabled");
           int64_t EarlierSize = DepLoc.Size;
           int64_t LaterSize = Loc.Size;
           bool IsOverwriteEnd = (OR == OW_End);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
+        } else if (EnablePartialStoreMerging &&
+                   OR == OW_PartialEarlierWithFullLater) {
+          auto *Earlier = dyn_cast<StoreInst>(DepWrite);
+          auto *Later = dyn_cast<StoreInst>(Inst);
+          if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
+              Later && isa<ConstantInt>(Later->getValueOperand())) {
+            // If the store we find is:
+            //   a) partially overwritten by the store to 'Loc'
+            //   b) the later store is fully contained in the earlier one and
+            //   c) they both have a constant value
+            // Merge the two stores, replacing the earlier store's value with a
+            // merge of both values.
+            // TODO: Deal with other constant types (vectors, etc), and probably
+            // some mem intrinsics (if needed)
+
+            APInt EarlierValue =
+                cast<ConstantInt>(Earlier->getValueOperand())->getValue();
+            APInt LaterValue =
+                cast<ConstantInt>(Later->getValueOperand())->getValue();
+            unsigned LaterBits = LaterValue.getBitWidth();
+            assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth());
+            LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
+
+            // Offset of the smaller store inside the larger store
+            unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
+            unsigned LShiftAmount =
+                DL.isBigEndian()
+                    ? EarlierValue.getBitWidth() - BitOffsetDiff - LaterBits
+                    : BitOffsetDiff;
+            APInt Mask =
+                APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
+                                  LShiftAmount + LaterBits);
+            // Clear the bits we'll be replacing, then OR with the smaller
+            // store, shifted appropriately.
+            APInt Merged =
+                (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
+            DEBUG(dbgs() << "DSE: Merge Stores:\n  Earlier: " << *DepWrite
+                         << "\n  Later: " << *Inst
+                         << "\n  Merged Value: " << Merged << '\n');
+
+            auto *SI = new StoreInst(
+                ConstantInt::get(Earlier->getValueOperand()->getType(), Merged),
+                Earlier->getPointerOperand(), false, Earlier->getAlignment(),
+                Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
+
+            unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
+                                   LLVMContext::MD_alias_scope,
+                                   LLVMContext::MD_noalias,
+                                   LLVMContext::MD_nontemporal};
+            SI->copyMetadata(*DepWrite, MDToKeep);
+            ++NumModifiedStores;
+
+            // Remove earlier, wider, store
+            size_t Idx = InstrOrdering.lookup(DepWrite);
+            InstrOrdering.erase(DepWrite);
+            InstrOrdering.insert(std::make_pair(SI, Idx));
+
+            // Delete the old stores and now-dead instructions that feed them.
+            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering);
+            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
+                                  &InstrOrdering);
+            MadeChange = true;
+
+            // We erased DepWrite and Inst (Loc); start over.
+            break;
+          }
         }
       }
 
       // 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

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

-; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+; RUN: opt < %s -basicaa -dse -enable-dse-partial-store-merging=false -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 ; Ensure that the dead store is deleted in this case.  It is wholely
 ; overwritten by the second store.
 define void @test1(i32 *%V) {
         %V2 = bitcast i32* %V to i8*            ; <i8*> [#uses=1]
         store i8 0, i8* %V2
         store i32 1234567, i32* %V

llvm/trunk/test/Transforms/DeadStoreElimination/combined-partial-overwrites.ll

-; RUN: opt -S -dse < %s | FileCheck %s
+; RUN: opt -S -dse -enable-dse-partial-store-merging=false < %s | FileCheck %s
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-bgq-linux"
 
 %"struct.std::complex" = type { { float, float } }
 
 define void @_Z4testSt7complexIfE(%"struct.std::complex"* noalias nocapture sret %agg.result, i64 %c.coerce) {
 entry:
 ; CHECK-LABEL: @_Z4testSt7complexIfE

llvm/trunk/test/Transforms/DeadStoreElimination/merge-stores-big-endian.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -dse -enable-dse-partial-store-merging -S < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-i128:128-n32:64-S128"
+
+define void @byte_by_byte_replacement(i32 *%ptr) {
+; CHECK-LABEL: @byte_by_byte_replacement(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 151653132, i32* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  ;; This store's value should be modified as it should be better to use one
+  ;; larger store than several smaller ones.
+  ;; store will turn into 0x090A0B0C == 151653132
+  store i32 305419896, i32* %ptr  ; 0x12345678
+  %bptr = bitcast i32* %ptr to i8*
+  %bptr1 = getelementptr inbounds i8, i8* %bptr, i64 1
+  %bptr2 = getelementptr inbounds i8, i8* %bptr, i64 2
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+
+  ;; We should be able to merge these four stores with the i32 above
+  ; value (and bytes) stored before  ; 0x12345678
+  store i8 9, i8* %bptr              ;   09
+  store i8 10, i8* %bptr1            ;     0A
+  store i8 11, i8* %bptr2            ;       0B
+  store i8 12, i8* %bptr3            ;         0C
+  ;                                    0x090A0B0C
+
+  ret void
+}
+
+define void @word_replacement(i64 *%ptr) {
+; CHECK-LABEL: @word_replacement(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 72638273700655232, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 72623859790382856, i64* %ptr  ; 0x0102030405060708
+
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %wptr3 = getelementptr inbounds i16, i16* %wptr, i64 3
+
+  ;; We should be able to merge these two stores with the i64 one above
+  ; value (and bytes) stored before  ; 0x0102030405060708
+  store i16  4128, i16* %wptr1       ;       1020
+  store i16 28800, i16* %wptr3       ;               7080
+  ;                                    0x0102102005067080
+
+  ret void
+}
+
+
+define void @differently_sized_replacements(i64 *%ptr) {
+; CHECK-LABEL: @differently_sized_replacements(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 289077004501059343, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr6 = getelementptr inbounds i8, i8* %bptr, i64 6
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (and bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr6    ;               07
+  store i16     1541, i16* %wptr2    ;           0605
+  store i32 67305985, i32* %dptr     ;   04030201
+  ;                                    0x040302010605070f
+  ret void
+}
+
+
+define void @multiple_replacements_to_same_byte(i64 *%ptr) {
+; CHECK-LABEL: @multiple_replacements_to_same_byte(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 289077004602248719, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (and bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr3    ;         07
+  store i16     1541, i16* %wptr1    ;       0605
+  store i32 67305985, i32* %dptr     ;   04030201
+  ;                                    0x040302010c0d0e0f
+  ret void
+}
+
+define void @merged_merges(i64 *%ptr) {
+; CHECK-LABEL: @merged_merges(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 289081428418563599, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i32 67305985, i32* %dptr     ;   04030201
+  store i16     1541, i16* %wptr1    ;       0605
+  store i8         7, i8*  %bptr3    ;         07
+  ;                                    0x040306070c0d0e0f
+  ret void
+}
+
+define signext i8 @shouldnt_merge_since_theres_a_full_overlap(i64 *%ptr) {
+; CHECK-LABEL: @shouldnt_merge_since_theres_a_full_overlap(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[BPTR:%.*]] = bitcast i64* [[PTR:%.*]] to i8*
+; CHECK-NEXT:    [[BPTRM1:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 -1
+; CHECK-NEXT:    [[BPTR3:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 3
+; CHECK-NEXT:    [[DPTR:%.*]] = bitcast i8* [[BPTRM1]] to i32*
+; CHECK-NEXT:    [[QPTR:%.*]] = bitcast i8* [[BPTR3]] to i64*
+; CHECK-NEXT:    store i32 1234, i32* [[DPTR]], align 1
+; CHECK-NEXT:    store i64 5678, i64* [[QPTR]], align 1
+; CHECK-NEXT:    ret i8 0
+;
+entry:
+
+  store i64 0, i64* %ptr
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptrm1 = getelementptr inbounds i8, i8* %bptr, i64 -1
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %dptr = bitcast i8* %bptrm1 to i32*
+  %qptr = bitcast i8* %bptr3 to i64*
+
+  store i32 1234, i32* %dptr, align 1
+  store i64 5678, i64* %qptr, align 1
+
+  ret i8 0
+}
+
+;; Test case from PR31777
+%union.U = type { i64 }
+
+define void @foo(%union.U* nocapture %u) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I:%.*]] = getelementptr inbounds [[UNION_U:%.*]], %union.U* [[U:%.*]], i64 0, i32 0
+; CHECK-NEXT:    store i64 11821949021847552, i64* [[I]], align 8
+; CHECK-NEXT:    ret void
+;
+entry:
+  %i = getelementptr inbounds %union.U, %union.U* %u, i64 0, i32 0
+  store i64 0, i64* %i, align 8
+  %s = bitcast %union.U* %u to i16*
+  store i16 42, i16* %s, align 8
+  ret void
+}

llvm/trunk/test/Transforms/DeadStoreElimination/merge-stores.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -dse -enable-dse-partial-store-merging -S < %s | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64"
+
+define void @byte_by_byte_replacement(i32 *%ptr) {
+; CHECK-LABEL: @byte_by_byte_replacement(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 202050057, i32* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  ;; This store's value should be modified as it should be better to use one
+  ;; larger store than several smaller ones.
+  ;; store will turn into 0x0C0B0A09 == 202050057
+  store i32 305419896, i32* %ptr  ; 0x12345678
+  %bptr = bitcast i32* %ptr to i8*
+  %bptr1 = getelementptr inbounds i8, i8* %bptr, i64 1
+  %bptr2 = getelementptr inbounds i8, i8* %bptr, i64 2
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+
+  ;; We should be able to merge these four stores with the i32 above
+  ; value (and bytes) stored before  ; 0x12345678
+  store i8 9, i8* %bptr              ;         09
+  store i8 10, i8* %bptr1            ;       0A
+  store i8 11, i8* %bptr2            ;     0B
+  store i8 12, i8* %bptr3            ;   0C
+  ;                                    0x0C0B0A09
+  ret void
+}
+
+define void @word_replacement(i64 *%ptr) {
+; CHECK-LABEL: @word_replacement(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 8106482645252179720, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 72623859790382856, i64* %ptr  ; 0x0102030405060708
+
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %wptr3 = getelementptr inbounds i16, i16* %wptr, i64 3
+
+  ;; We should be able to merge these two stores with the i64 one above
+  ; value (not bytes) stored before  ; 0x0102030405060708
+  store i16  4128, i16* %wptr1       ;           1020
+  store i16 28800, i16* %wptr3       ;   7080
+  ;                                    0x7080030410200708
+  ret void
+}
+
+
+define void @differently_sized_replacements(i64 *%ptr) {
+; CHECK-LABEL: @differently_sized_replacements(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 578437695752307201, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr6 = getelementptr inbounds i8, i8* %bptr, i64 6
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr6    ;     07
+  store i16     1541, i16* %wptr2    ;       0605
+  store i32 67305985, i32* %dptr     ;           04030201
+  ;                                    0x0807060504030201
+  ret void
+}
+
+
+define void @multiple_replacements_to_same_byte(i64 *%ptr) {
+; CHECK-LABEL: @multiple_replacements_to_same_byte(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 579005069522043393, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr3    ;           07
+  store i16     1541, i16* %wptr1    ;           0605
+  store i32 67305985, i32* %dptr     ;           04030201
+  ;                                    0x08090a0b04030201
+  ret void
+}
+
+define void @merged_merges(i64 *%ptr) {
+; CHECK-LABEL: @merged_merges(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 579005069572506113, i64* [[PTR:%.*]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 0x08090a0b0c0d0e0f
+  store i32 67305985, i32* %dptr     ;           04030201
+  store i16     1541, i16* %wptr1    ;           0605
+  store i8         7, i8*  %bptr3    ;           07
+  ;                                    0x08090a0b07050201
+  ret void
+}
+
+define signext i8 @shouldnt_merge_since_theres_a_full_overlap(i64 *%ptr) {
+; CHECK-LABEL: @shouldnt_merge_since_theres_a_full_overlap(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[BPTR:%.*]] = bitcast i64* [[PTR:%.*]] to i8*
+; CHECK-NEXT:    [[BPTRM1:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 -1
+; CHECK-NEXT:    [[BPTR3:%.*]] = getelementptr inbounds i8, i8* [[BPTR]], i64 3
+; CHECK-NEXT:    [[DPTR:%.*]] = bitcast i8* [[BPTRM1]] to i32*
+; CHECK-NEXT:    [[QPTR:%.*]] = bitcast i8* [[BPTR3]] to i64*
+; CHECK-NEXT:    store i32 1234, i32* [[DPTR]], align 1
+; CHECK-NEXT:    store i64 5678, i64* [[QPTR]], align 1
+; CHECK-NEXT:    ret i8 0
+;
+entry:
+
+  ; Also check that alias.scope metadata doesn't get dropped
+  store i64 0, i64* %ptr, !alias.scope !32
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptrm1 = getelementptr inbounds i8, i8* %bptr, i64 -1
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %dptr = bitcast i8* %bptrm1 to i32*
+  %qptr = bitcast i8* %bptr3 to i64*
+
+  store i32 1234, i32* %dptr, align 1
+  store i64 5678, i64* %qptr, align 1
+
+  ret i8 0
+}
+
+;; Test case from PR31777
+%union.U = type { i64 }
+
+define void @foo(%union.U* nocapture %u) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I:%.*]] = getelementptr inbounds [[UNION_U:%.*]], %union.U* [[U:%.*]], i64 0, i32 0
+; CHECK-NEXT:    store i64 42, i64* [[I]], align 8
+; CHECK-NEXT:    ret void
+;
+entry:
+  %i = getelementptr inbounds %union.U, %union.U* %u, i64 0, i32 0
+  store i64 0, i64* %i, align 8, !dbg !22, !tbaa !26, !noalias !30, !nontemporal !29
+  %s = bitcast %union.U* %u to i16*
+  store i16 42, i16* %s, align 8
+  ret void
+}
+
+; Don't crash by operating on stale data if we merge (kill) the last 2 stores.
+
+define void @PR34074(i32* %x, i64* %y) {
+; CHECK-LABEL: @PR34074(
+; CHECK-NEXT:    store i64 42, i64* %y
+; CHECK-NEXT:    store i32 4, i32* %x
+; CHECK-NEXT:    ret void
+;
+  store i64 42, i64* %y          ; independent store
+  %xbc = bitcast i32* %x to i8*
+  store i32 0, i32* %x           ; big store of constant
+  store i8 4, i8* %xbc           ; small store with mergeable constant
+  ret void
+}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 5.0.0 (trunk 306512)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "me.cpp", directory: "/compiler-explorer")
+!2 = !{}
+!7 = distinct !DISubprogram(name: "foo", linkageName: "foo(U*)", scope: !1, file: !1, line: 9, type: !8, isLocal: false, isDefinition: true, scopeLine: 9, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !20)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10}
+!10 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64)
+!11 = distinct !DICompositeType(tag: DW_TAG_union_type, name: "U", file: !1, line: 4, size: 64, elements: !12, identifier: "typeinfo name for U")
+!12 = !{!13, !17}
+!13 = !DIDerivedType(tag: DW_TAG_member, name: "i", scope: !11, file: !1, line: 5, baseType: !14, size: 64)
+!14 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint64_t", file: !15, line: 55, baseType: !16)
+!15 = !DIFile(filename: "/usr/include/stdint.h", directory: "/compiler-explorer")
+!16 = !DIBasicType(name: "long unsigned int", size: 64, encoding: DW_ATE_unsigned)
+!17 = !DIDerivedType(tag: DW_TAG_member, name: "s", scope: !11, file: !1, line: 6, baseType: !18, size: 16)
+!18 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint16_t", file: !15, line: 49, baseType: !19)
+!19 = !DIBasicType(name: "unsigned short", size: 16, encoding: DW_ATE_unsigned)
+!20 = !{!21}
+!21 = !DILocalVariable(name: "u", arg: 1, scope: !7, file: !1, line: 9, type: !10)
+!22 = !DILocation(line: 10, column: 8, scope: !7)
+
+!26 = !{!27, !27, i64 0}
+!27 = !{!"omnipotent char", !28, i64 0}
+!28 = !{!"Simple C++ TBAA"}
+
+!29 = !{i32 1}
+
+; Domains and scopes which might alias
+!30 = !{!30}
+!31 = !{!31, !30}
+
+!32 = !{!32}
+!33 = !{!33, !32}