diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -892,6 +892,8 @@
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
+  SetVector<Instruction *> ToRemove;
+
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
            const LoopInfo &LI)
@@ -1699,42 +1701,54 @@
     return {EarlierAccess};
   }
 
-  // Delete dead memory defs
-  void deleteDeadInstruction(Instruction *SI) {
-    MemorySSAUpdater Updater(&MSSA);
-    SmallVector<Instruction *, 32> NowDeadInsts;
-    NowDeadInsts.push_back(SI);
-    --NumFastOther;
+  /// Deletes the dead instruction \p DeadInst and queue's any of it's operands
+  /// for removal, if they become dead.
+  void deleteSingleInstruction(Instruction *DeadInst,
+                               MemorySSAUpdater &Updater) {
+    ++NumFastOther;
 
-    while (!NowDeadInsts.empty()) {
-      Instruction *DeadInst = NowDeadInsts.pop_back_val();
-      ++NumFastOther;
+    // Try to preserve debug information attached to the dead instruction.
+    salvageDebugInfo(*DeadInst);
+    salvageKnowledge(DeadInst);
 
-      // Try to preserve debug information attached to the dead instruction.
-      salvageDebugInfo(*DeadInst);
-      salvageKnowledge(DeadInst);
+    // Remove the Instruction from MSSA.
+    if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
+      if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
+        SkipStores.insert(MD);
+      }
+      Updater.removeMemoryAccess(MA);
+    }
 
-      // Remove the Instruction from MSSA.
-      if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
-        if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
-          SkipStores.insert(MD);
-        }
-        Updater.removeMemoryAccess(MA);
+    auto Iter = IOLs.find(DeadInst->getParent());
+    if (Iter != IOLs.end())
+      Iter->second.erase(DeadInst);
+    // Remove its operands
+    for (Use &O : DeadInst->operands())
+      if (Instruction *OpI = dyn_cast<Instruction>(O)) {
+        O = nullptr;
+        if (isInstructionTriviallyDead(OpI, &TLI))
+          ToRemove.insert(OpI);
       }
 
-      auto I = IOLs.find(DeadInst->getParent());
-      if (I != IOLs.end())
-        I->second.erase(DeadInst);
-      // Remove its operands
-      for (Use &O : DeadInst->operands())
-        if (Instruction *OpI = dyn_cast<Instruction>(O)) {
-          O = nullptr;
-          if (isInstructionTriviallyDead(OpI, &TLI))
-            NowDeadInsts.push_back(OpI);
-        }
+    DeadInst->eraseFromParent();
+  }
 
-      DeadInst->eraseFromParent();
-    }
+  /// Delete all instructions in ToRemove and any of their operands, if they
+  /// become dead.
+  void deleteRemainingInsts() {
+    --NumFastOther;
+
+    MemorySSAUpdater Updater(&MSSA);
+    for (unsigned I = 0; I != ToRemove.size(); ++I)
+      deleteSingleInstruction(ToRemove[I], Updater);
+    ToRemove.clear();
+  }
+
+  // Delete dead memory defs
+  void deleteDeadInstruction(Instruction *SI) {
+    MemorySSAUpdater Updater(&MSSA);
+    --NumFastOther;
+    deleteSingleInstruction(SI, Updater);
   }
 
   // Check for any extra throws between SI and NI that block DSE.  This only
@@ -1813,6 +1827,9 @@
         LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
                              "of the function\n");
         deleteDeadInstruction(DefI);
+        // Remove the instructions that become dead after removing DefI, because
+        // it may enable further removal of unused memory instructions.
+        deleteRemainingInsts();
         ++NumFastStores;
         MadeChange = true;
       }
@@ -2060,6 +2077,7 @@
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
+  State.deleteRemainingInsts();
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }