[DSE] Avoid iterator invalidation bugs.

[mcrosier]

Summary

This patch is the (rewritten) mechanical part of D21007 to avoid problems with iterator invalidation.

The test committed with http://reviews.llvm.org/rL273141 is removed because this patch no longer performs any type of back tracking, which is what was causing the codegen differences with and without debug information.

No correctness issues across SPEC2000, SPEC2006, and llvm-test-suite. In fact, there were no codegen changes across this suite of benchmarks. However, codegen changes are possible because we no longer backtrack when the current instruction is deleted.

Chad

FWIW, I'm in the process of trying to port DSE to use MemorySSA and I thought pushing this change sooner rather than later would simplify my life. Sorry to hijack your change, Eli.

[mcrosier]

-Fix a few comments that wrapped due to clang-format.

[eli.friedman]

It's no problem that you're stealing some of my changes. :)

Instead of adding an outer loop, you could solve the rL273141 testcase by only delaying the erasure of PHI nodes rather than the erasure of all operands. I think that wouldn't introduce any invalidation problems because we only visit reachable blocks. That said, the outer loop actually catches more cases: if you switch up the stores a little, you can come up with a testcase which current DSE can't handle, but this version can. Actually, you could even end up with cases where erasing a store in one block allows erasing a store in a different block... but iterating the whole DSE pass might be too expensive to be worthwhile.

Looks fine otherwise.

lib/Transforms/Scalar/DeadStoreElimination.cpp

557

handleFree might need some changes to avoid iterator invalidation issues: I think you can end up with a problem with a block that branches to itself? You can't do that without tripping over https://llvm.org/bugs/show_bug.cgi?id=28014, I guess, so not really important, but a FIXME would be nice. (I think I was planning to do something in my version; I forget why I didn't.)

[Henric]

I've addressed the regressed test by added an outer loop around the kernel code in eliminateDeadStores that reevaluates the block until there is no change (as was suggested in D21076)

If the extra compilation time does not turn out to be a problem, then I think it's a good improvement. The code that is now encapsulated in eliminateNoopStore could already do that (reevaluate the block) so you could probably already create a rather bad test case if you really wanted.

I remember someone suggested in mail to the review list that it might be possible to remove stores if you process them in the right order. But I never understood how, at least not in the general case where you don't know the address origin of a load. For example if the use comes from an input param to the function, two examples:

load -> r1
store *r1 -> g1
load -> r2
store *r2 -> g2
...
store -> g1
store -> g2

compared to

load -> r2
store *r2 -> g2
load -> r1
store *r1 -> g1
...
store -> g1
store -> g2

[mcrosier]

In D21613#464843, @eli.friedman wrote:

It's no problem that you're stealing some of my changes. :)

Thanks! :D

Instead of adding an outer loop, you could solve the rL273141 testcase by only delaying the erasure of PHI nodes rather than the erasure of all operands.

I'm not sure I follow. Test case for reference:

define i16 @S0() !dbg !17 {
bb1:
  store i32 4, i32* @g_31, align 1, !dbg !20
  %_tmp16.i.i = load volatile i16*, i16** @g_30, align 1, !dbg !28
  %_tmp17.i.i = load i16, i16* %_tmp16.i.i, align 1, !dbg !28
  store i16 %_tmp17.i.i, i16* @g_118, align 1, !dbg !20
  store i32 0, i32* @g_31, align 1, !dbg !31
  tail call void @llvm.dbg.value(metadata i32 0, i64 0, metadata !40, metadata !41), !dbg !42
  store i16 0, i16* @g_118, align 1, !dbg !43
  br label %bb2.i, !dbg !44

bb2.i:
  br label %bb2.i, !dbg !44
}

IIUC, the first store (store i32 4, i32* @g_31) is clobbered by the 3rd store (store i32 0, i32* @g_31), but DSE is unable to realize this because of an aliasing load (%_tmp17.i.i = load i16, i16* %_tmp16.i.i). The second store (and the loads that alias with the third store) is/are removed when DSE realizes the fourth store (store i16 0, i16* @g_118) clobbers the second. We fail to catch the rL273141 test case because this change doesn't do any type of back tracking like what is currently done.

Did I miss something, @eli.friedman/@Henric? I'm not sure how deleting non-phi nodes resolves this issue, Eli.

FWIW, I'd prefer to *not* have the outer loop, but I'm not sure I can resolve rL273141's test case in another way. My long term goal is to have DSE use MemorySSA and eventually revive rL255247, which was reverted due to compile-time issues; I don't think having the outer loop is inline with my current goals.

One might also argue that regressing rL273141's test case is acceptable, if we're fixing/avoiding iterator invalidation issues. Obviously, I'd like the best of both worlds, but I may need some direction on how to achieve that goal.

[eli.friedman]

Oh, I see what you mean about the rL273141 testcase; I thought the stores in the testcase were ordered differently. You run into the issue I was describing if you reorder the last two stores, like this:

store i32 4, i32* @g_31, align 1, !dbg !20
%_tmp16.i.i = load volatile i16*, i16** @g_30, align 1, !dbg !28
%_tmp17.i.i = load i16, i16* %_tmp16.i.i, align 1, !dbg !28
store i16 %_tmp17.i.i, i16* @g_118, align 1, !dbg !20
store i16 0, i16* @g_118, align 1, !dbg !43
store i32 0, i32* @g_31, align 1, !dbg !31

---

The primary point of rL273141 is that DSE shouldn't change behavior based on the presence of debug info... so as long as you're not breaking that invariant, it should be fine to modify/delete the testcase as necessary.

[mcrosier]

In D21613#465710, @eli.friedman wrote:

Oh, I see what you mean about the rL273141 testcase; I thought the stores in the testcase were ordered differently. You run into the issue I was describing if you reorder the last two stores, like this:

store i32 4, i32* @g_31, align 1, !dbg !20
%_tmp16.i.i = load volatile i16*, i16** @g_30, align 1, !dbg !28
%_tmp17.i.i = load i16, i16* %_tmp16.i.i, align 1, !dbg !28
store i16 %_tmp17.i.i, i16* @g_118, align 1, !dbg !20
store i16 0, i16* @g_118, align 1, !dbg !43
store i32 0, i32* @g_31, align 1, !dbg !31

---

Yes, I believe we'll miss this case if we defer the deletion of aliasing loads/stores. Let me see if I can take your suggested approach of deleting non-phi nodes, @eli.friedman. Also, can you please explain why the phi nodes must stick around (at least in the short term)? I don't follow..

Alternatively, I'm wondering if we could use @dberlin's suggestion from D21076 and utilize the iterator that is returned by BB->eraseFromParent() to address the iterator problem.

The primary point of rL273141 is that DSE shouldn't change behavior based on the presence of debug info... so as long as you're not breaking that invariant, it should be fine to modify/delete the testcase as necessary.

AFAICT, this implementation won't suffer from this problem, so I'm thinking it would be okay to drop the test.

[eli.friedman]

" can you please explain why the phi nodes must stick around (at least in the short term)? I don't follow.."

Err, the PHI nodes don't need to stick around; you just need to make sure you don't delete the instruction the iterator is pointing at, and the operand of a phi node could be that instruction. There are other ways around the issue, I guess... you could even pass a pointer to the iterator to deleteDeadInstruction and make it update the iterator, I guess, instead of postponing deleting it.

[mcrosier]

In D21613#466632, @eli.friedman wrote:

" can you please explain why the phi nodes must stick around (at least in the short term)? I don't follow.."

Err, the PHI nodes don't need to stick around; you just need to make sure you don't delete the instruction the iterator is pointing at, and the operand of a phi node could be that instruction. There are other ways around the issue, I guess... you could even pass a pointer to the iterator to deleteDeadInstruction and make it update the iterator, I guess, instead of postponing deleting it.

Okay, my understanding of the problem appears to be the same as yours; I must have just misinterpreted one of your earlier comments.

[eli.friedman]

lib/Transforms/Scalar/DeadStoreElimination.cpp

59

Maybe it would make sense to pass in a BasicBlock::iterator* and make this function update it, rather than returning a BasicBlock::iterator?

91

Wrong indentation.

756–757

handleFree can invalidate BBI, I think?

[mcrosier]

-Address Eli's comments.

lib/Transforms/Scalar/DeadStoreElimination.cpp

59

Sure.

756–757

How so? IIUC, deleting the 'free' instruction would invalidate the iterator, but I'm not convinced that can happen. Some care is needed to make sure we pass a valid iterator to MD-getPointerDependencyFrom(), but I believe I've handled that correctly.

[mcrosier]

Ping.

[eli.friedman]

Sorry about the delay; I thought I had sent review comments, but apparently they were saved/unsent.

lib/Transforms/Scalar/DeadStoreElimination.cpp

756–757

BBI doesn't point at the free instruction here.

841

I don't follow how Inst could ever be killed by deleteDeadInstruction... an instruction which writes to memory can't be trivially dead.

[mcrosier]

Address Eli's feedback.

[mcrosier]

lib/Transforms/Scalar/DeadStoreElimination.cpp

756–757

Ah, right. Should be fixed now.

839–840

Fixed.

[eli.friedman]

LGTM.

lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===----------------------------------------------------------------------===//
 // Helper functions
 //===----------------------------------------------------------------------===//
 
 /// Delete this instruction.  Before we do, go through and zero out all the
 /// operands of this instruction.  If any of them become dead, delete them and
 /// the computation tree that feeds them.
 /// If ValueSet is non-null, remove any deleted instructions from it as well.
-static void
-deleteDeadInstruction(Instruction *I, MemoryDependenceResults &MD,
-                      const TargetLibraryInfo &TLI,
-                      SmallSetVector<Value *, 16> *ValueSet = nullptr) {
+static void recursivelyDeleteInstructions(Instruction *I,
+                                          MemoryDependenceResults &MD,
+                                          const TargetLibraryInfo &TLI) {
   SmallVector<Instruction*, 32> NowDeadInsts;
+  assert(isInstructionTriviallyDead(I, &TLI));
 
   NowDeadInsts.push_back(I);
   --NumFastOther;
 
   // Before we touch this instruction, remove it from memdep!
   do {
     Instruction *DeadInst = NowDeadInsts.pop_back_val();
     ++NumFastOther;
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
       if (!Op->use_empty()) continue;
 
       if (Instruction *OpI = dyn_cast<Instruction>(Op))
         if (isInstructionTriviallyDead(OpI, &TLI))
           NowDeadInsts.push_back(OpI);
     }
 
     DeadInst->eraseFromParent();
-
-    if (ValueSet) ValueSet->remove(DeadInst);
   } while (!NowDeadInsts.empty());
 }
 
+static void deleteDeadInstruction(Instruction *DeadInst,
+                                  MemoryDependenceResults &MD,
+                                  const TargetLibraryInfo &TLI,
+                                  SmallSetVector<Value *, 16> *ValueSet,
+                                  SmallVectorImpl<WeakVH> &DeadInstList) {
+  // Keep track of dead operands, so we can erase them later.
+  //
+  // Note that we can't erase the instructions immediately because it would
+  // mess up our basic block iterators.
+  for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
+    Value *Op = DeadInst->getOperand(op);
+    DeadInst->setOperand(op, nullptr);
+    if (Op->use_empty())
+      if (Instruction *I = dyn_cast<Instruction>(Op))
+        if (isInstructionTriviallyDead(I, &TLI))
+          DeadInstList.push_back(WeakVH(I));
+  }
+  MD.removeInstruction(DeadInst);
+  if (ValueSet)
+    ValueSet->remove(DeadInst);
+  DeadInst->eraseFromParent();
+}
+
 /// Does this instruction write some memory?  This only returns true for things
 /// that we can analyze with other helpers below.
 static bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
   if (isa<StoreInst>(I))
     return true;
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
if (DT->isReachableFromEntry(Pred))
       Blocks.push_back(Pred);
   }
 }
 
 /// Handle frees of entire structures whose dependency is a store
 /// to a field of that structure.
 static bool handleFree(CallInst *F, AliasAnalysis *AA,
                        MemoryDependenceResults *MD, DominatorTree *DT,
-                       const TargetLibraryInfo *TLI) {
+                       const TargetLibraryInfo *TLI,
+                       SmallVectorImpl<WeakVH> &DeadInstList) {
   bool MadeChange = false;
 
   MemoryLocation Loc = MemoryLocation(F->getOperand(0));
   SmallVector<BasicBlock *, 16> Blocks;
   Blocks.push_back(F->getParent());
   const DataLayout &DL = F->getModule()->getDataLayout();
 
   while (!Blocks.empty()) {
while (Dep.isDef() || Dep.isClobber()) {
 
       // Check for aliasing.
       if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
         break;
 
       auto Next = ++Dependency->getIterator();
 
       // DCE instructions only used to calculate that store.
-      deleteDeadInstruction(Dependency, *MD, *TLI);
+      deleteDeadInstruction(Dependency, *MD, *TLI, nullptr, DeadInstList);
       ++NumFastStores;
       MadeChange = true;
 
       // Inst's old Dependency is now deleted. Compute the next dependency,
       // which may also be dead, as in
       //    s[0] = 0;
       //    s[1] = 0; // This has just been deleted.
       //    free(s);

 
 /// Remove dead stores to stack-allocated locations in the function end block.
 /// Ex:
 /// %A = alloca i32
 /// ...
 /// store i32 1, i32* %A
 /// ret void
 static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
-                             MemoryDependenceResults *MD,
-                             const TargetLibraryInfo *TLI) {
+                           const TargetLibraryInfo *TLI,
+                           SmallVectorImpl<WeakVH> &DeadInstList) {
   bool MadeChange = false;
 
   // Keep track of all of the stack objects that are dead at the end of the
   // function.
   SmallSetVector<Value*, 16> DeadStackObjects;
 
   // Find all of the alloca'd pointers in the entry block.
   BasicBlock &Entry = BB.getParent()->front();
if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
                    E = Pointers.end(); I != E; ++I) {
                 dbgs() << **I;
                 if (std::next(I) != E)
                   dbgs() << ", ";
               }
               dbgs() << '\n');
 
         // DCE instructions only used to calculate that store.
-        deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
+        deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects, DeadInstList);
         ++NumFastStores;
         MadeChange = true;
         continue;
       }
     }
 
     // Remove any dead non-memory-mutating instructions.
     if (isInstructionTriviallyDead(&*BBI, TLI)) {
       Instruction *Inst = &*BBI++;
-      deleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
+      deleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects, DeadInstList);
       ++NumFastOther;
       MadeChange = true;
       continue;
     }
 
     if (isa<AllocaInst>(BBI)) {
       // Remove allocas from the list of dead stack objects; there can't be
       // any references before the definition.
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
     // If all of the allocas were clobbered by the access then we're not going
     // to find anything else to process.
     if (DeadStackObjects.empty())
       break;
   }
 
   return MadeChange;
 }
 
-static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
-                                MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
-  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.
-    if (CallInst *F = isFreeCall(Inst, TLI)) {
-      MadeChange |= handleFree(F, AA, MD, DT, TLI);
-      continue;
-    }
-
-    // If we find something that writes memory, get its memory dependence.
-    if (!hasMemoryWrite(Inst, *TLI))
-      continue;
-
-    // If we're storing the same value back to a pointer that we just
-    // loaded from, then the store can be removed.
-    if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
-
-      auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) {
-        // deleteDeadInstruction can delete the current instruction.  Save BBI
-        // in case we need it.
-        WeakVH NextInst(&*BBI);
-
-        deleteDeadInstruction(DeadInst, *MD, *TLI);
-
-        if (!NextInst) // Next instruction deleted.
-          BBI = BB.begin();
-        else if (BBI != BB.begin()) // Revisit this instruction if possible.
-          --BBI;
-        ++NumRedundantStores;
-        MadeChange = true;
-      };
-
-      if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
-        if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
-            isRemovable(SI) &&
-            memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
+static bool eliminateNoopStore(Instruction *Inst, MemoryDependenceResults *MD,
+                               const TargetLibraryInfo *TLI, AliasAnalysis *AA,
+                               const DataLayout &DL,
+                               SmallVectorImpl<WeakVH> &DeadInstList) {
+          isRemovable(SI) && memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
 
-          DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
-                       << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
 
-          RemoveDeadInstAndUpdateBBI(SI);
-          continue;
-        }
-      }
+        deleteDeadInstruction(SI, *MD, *TLI, nullptr, DeadInstList);
+        ++NumRedundantStores;
+        return true;
 
-      // Remove null stores into the calloc'ed objects
-      Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
 
-      if (StoredConstant && StoredConstant->isNullValue() &&
-          isRemovable(SI)) {
-        Instruction *UnderlyingPointer = dyn_cast<Instruction>(
-            GetUnderlyingObject(SI->getPointerOperand(), DL));
+    if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
 
-        if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
-            memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
-          DEBUG(dbgs()
-                << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
-                << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
-          RemoveDeadInstAndUpdateBBI(SI);
-          continue;
-        }
-      }
-    }
+        deleteDeadInstruction(SI, *MD, *TLI, nullptr, DeadInstList);
+        ++NumRedundantStores;
+        return true;
+  return false;
+}
 
-    MemDepResult InstDep = MD->getDependency(Inst);
+static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
+                                MemoryDependenceResults *MD, DominatorTree *DT,
+                                const TargetLibraryInfo *TLI) {
+  const DataLayout &DL = BB.getModule()->getDataLayout();
+  bool MadeChange = false;
+
+  bool Change;
+  do {
+    Change = false;
+    SmallVector<WeakVH, 8> DeadInstList;
+
+    // Do a top-down walk on the BB.
+    for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE;) {
+      // This pointer stays valid because we never erase any instruction
+      // later in the same block.
+      Instruction *Inst = &*BBI++;
+
+      // Handle 'free' calls specially.
+      if (CallInst *F = isFreeCall(Inst, TLI)) {
+        Change |= handleFree(F, AA, MD, DT, TLI, DeadInstList);
+        continue;
+      }
+
+      // If we find something that writes memory, get its memory dependence.
+      if (!hasMemoryWrite(Inst, *TLI))
+        continue;
 
-    // Ignore any store where we can't find a local dependence.
-    // FIXME: cross-block DSE would be fun. :)
-    if (!InstDep.isDef() && !InstDep.isClobber())
+      if (eliminateNoopStore(Inst, MD, TLI, AA, DL, DeadInstList)) {
+        Change = true;
         continue;
+      }
+
+      MemDepResult InstDep = MD->getDependency(Inst);
 
       // Figure out what location is being stored to.
       MemoryLocation Loc = getLocForWrite(Inst, *AA);
 
       // If we didn't get a useful location, fail.
       if (!Loc.Ptr)
         continue;
 
       while (InstDep.isDef() || InstDep.isClobber()) {
-      // Get the memory clobbered by the instruction we depend on.  MemDep will
-      // skip any instructions that 'Loc' clearly doesn't interact with.  If we
-      // end up depending on a may- or must-aliased load, then we can't optimize
+        // Get the memory clobbered by the instruction we depend on.  MemDep
+        // will
+        // skip any instructions that 'Loc' clearly doesn't interact with.  If
+        // we
+        // end up depending on a may- or must-aliased load, then we can't
+        // optimize
         // away the store and we bail out.  However, if we depend on something
         // that overwrites the memory location we *can* potentially optimize it.
         //
         // Find out what memory location the dependent instruction stores.
         Instruction *DepWrite = InstDep.getInst();
         MemoryLocation DepLoc = getLocForWrite(DepWrite, *AA);
         // If we didn't get a useful location, or if it isn't a size, bail out.
         if (!DepLoc.Ptr)
           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
+        // completely obliterated by the store to 'Loc', and c) which we know
+        // that
         // 'Inst' doesn't load from, then we can remove it.
         if (isRemovable(DepWrite) &&
             !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
           int64_t InstWriteOffset, DepWriteOffset;
-        OverwriteResult OR =
-            isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
+          OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI,
+                                           DepWriteOffset, InstWriteOffset);
           if (OR == OverwriteComplete) {
-          DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
-                << *DepWrite << "\n  KILLER: " << *Inst << '\n');
+            DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
+                         << "\n  KILLER: " << *Inst << '\n');
 
-          // Delete the store and now-dead instructions that feed it.
-          deleteDeadInstruction(DepWrite, *MD, *TLI);
+            deleteDeadInstruction(DepWrite, *MD, *TLI, nullptr, DeadInstList);
             ++NumFastStores;
-          MadeChange = true;
+            Change = true;
 
-          // deleteDeadInstruction can delete the current instruction in loop
-          // cases, reset BBI.
-          BBI = Inst->getIterator();
-          auto BBBegin = BB.begin();
-          while (BBI != BBBegin && isa<DbgInfoIntrinsic>(*(--BBI)))
-            ;
+            // Eliminating a store could make this store a no-op.
+            if (eliminateNoopStore(Inst, MD, TLI, AA, DL, DeadInstList))
               break;
+
+            // We erased DepWrite; start over.
+            InstDep = MD->getDependency(Inst);
+            continue;
           } 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
+            // 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);
             unsigned DepWriteAlign = DepIntrinsic->getAlignment();
             bool IsOverwriteEnd = (OR == OverwriteEnd);
             if (!IsOverwriteEnd)
               InstWriteOffset = int64_t(InstWriteOffset + Loc.Size);
 
             if ((llvm::isPowerOf2_64(InstWriteOffset) &&
                  DepWriteAlign <= InstWriteOffset) ||
-              ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) {
+                ((DepWriteAlign != 0) &&
+                 InstWriteOffset % DepWriteAlign == 0)) {
 
               DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "
                            << (IsOverwriteEnd ? "END" : "BEGIN") << ": "
                            << *DepWrite << "\n  KILLER (offset "
                            << InstWriteOffset << ", " << DepLoc.Size << ")"
                            << *Inst << '\n');
 
               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(
+                GetElementPtrInst *NewDestGEP =
+                    GetElementPtrInst::CreateInBounds(
                         DepIntrinsic->getRawDest(), Indices, "", DepWrite);
                 DepIntrinsic->setDest(NewDestGEP);
               }
-            MadeChange = true;
+              Change = 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
+        // can keep searching past it for another must-aliased pointer that
+        // stores
         // to the same location.  For example, in:
         //   store -> P
         //   store -> Q
         //   store -> P
-      // we can remove the first store to P even though we don't know if P and Q
+        // we can remove the first store to P even though we don't know if P and
+        // Q
         // alias.
-      if (DepWrite == &BB.front()) break;
+        if (DepWrite == &BB.front())
+          break;
 
         // Can't look past this instruction if it might read 'Loc'.
         if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref)
           break;
 
         InstDep = MD->getPointerDependencyFrom(Loc, false,
                                                DepWrite->getIterator(), &BB);
       }
     }
 
     // If this block ends in a return, unwind, or unreachable, all allocas are
     // dead at its end, which means stores to them are also dead.
     if (BB.getTerminator()->getNumSuccessors() == 0)
-    MadeChange |= handleEndBlock(BB, AA, MD, TLI);
+      Change |= handleEndBlock(BB, AA, MD, TLI, DeadInstList);
+
+    // Erase dead instructions we put off erasing.
+    for (WeakVH &VH : DeadInstList) {
+      if (Instruction *I = cast_or_null<Instruction>(VH))
+        recursivelyDeleteInstructions(I, *MD, *TLI);
+    }
 
+    MadeChange |= Change;
+  } while (Change);
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   bool MadeChange = false;
   for (BasicBlock &BB : F)