Fix for a dangling point bug in DeadStoreElimination pass

[quic_aankit]

Summary

The patch makes sure that the LastThrowing pointer does not point to any instruction deleted by call to DeleteDeadInstruction.

While iterating through the instructions the pass maintains a pointer to the lastThrowing Instruction. A call to deleteDeadInstruction deletes a dead store and other instructions feeding the original dead instruction which also become dead. The instruction pointed by the lastThrowing pointer could also be deleted by the call to DeleteDeadInstruction and thus it becomes a dangling pointer. Because of this, we see an error in the next iteration.

In the patch, we maintain a list of throwing instructions encountered previously and use the last non deleted throwing instruction from the container.

[fhahn]

I think SetVector would be more suitable and lead to slightly simpler code (http://llvm.org/doxygen/classllvm_1_1SetVector.html)

Also, could you upload the patch with more context? (git show HEAD -U999999)

[quic_aankit]

Uploading patch with more context

[quic_aankit]

In D65326#1603693, @fhahn wrote:

I think SetVector would be more suitable and lead to slightly simpler code (http://llvm.org/doxygen/classllvm_1_1SetVector.html)

Also, could you upload the patch with more context? (git show HEAD -U999999)

Uploaded the patch with more context.

The main motivation to use MapVector is for searching the deletedInstruction in the list of lastThrowing Instructions (Line120). With SetVector this step will be expensive.

[quic_aankit]

@fhahn @efriedma @bcahoon Please review

[fhahn]

In D65326#1605875, @quic_aankit wrote:

In D65326#1603693, @fhahn wrote:

I think SetVector would be more suitable and lead to slightly simpler code (http://llvm.org/doxygen/classllvm_1_1SetVector.html)

Also, could you upload the patch with more context? (git show HEAD -U999999)

Uploaded the patch with more context.

The main motivation to use MapVector is for searching the deletedInstruction in the list of lastThrowing Instructions (Line120). With SetVector this step will be expensive.

Right, the interface to SetVector is a bit unfortunate in that respect :( It's probably not worth generalizing that for now, especially if we can keep the logic to clean up the map in deleteDeadInstructions.

Some comments inline. Would it be possible to add a test where multiple entries are removed from the mapping in a single deleteDeadInstructions call? Not sure if that can be the case, IIUC that would require deleting a function that may throw with an argument that may throw as well, but can be removed once it is dead.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

118

LLVM convention is to have upper case names for variables (same below)

1164

I think we could move the code to pop the removed instructions from the map to deleteDeadInstructions. That would keep the logic to manage the map in one place and here we can simply use the last instruction in the map as LastThrowing I think.

1165

AFAIK we are looking for the last throwing instruction we encountered, but this will set it to the first? Shouldn't check the map in reverse insertion order?

Otherwise we remove the store between the @foo calls, which we would have to preserve, as @foo may throw.

declare i8* @_Znwj(i32) local_unnamed_addr

declare void @foo() readnone
; CHECK-LABEL: @test(
; CHECK-NEXT: store
; CHECK-NEXT: ret void
define void @test(i8** %ptr, i8* %p1, i8* %p2) {
  store i8* undef, i8** %ptr
  call void @foo()
  store i8* %p1, i8** %ptr
  call void @foo()
  store i8* %p2, i8** %ptr
  %call = call i8* @_Znwj(i32 1)
  store i8* %call, i8** %ptr
  store i8* undef, i8** %ptr
  ret void
}

[quic_aankit]

Hi fhahn, sorry for the delay. I've addressed your comments. However, I was unable to add a test where multiple entries are removed from the mapping in a single deleteDeadInstructions call. The method you suggested does not work because deleting a function that may throw is not a legal operation. In the testcase that I have since it is a new function call "_Znwj", we are able to remove the call.

[quic_aankit]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1164

I've moved the code up in deleteDeadInstructions. I had this here to be able to use inexpensive pop_back instead of the expensive erase. But I think your suggestion makes more sense.

1165

I'm sorry. This had to be a reverse iterator. I've corrected it in the new patch

[quic_aankit]

@fhahn Gentle reminder

[quic_aankit]

@fhahn Ping

[quic_aankit]

@fhahn Gentle reminder

[fhahn]

Sorry for the long delay! I had to go through the comments again.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

103

Please run clang-format before committing. I think this should be <Instruction *, bool>.

119

I think it would be better to not use erase, as you had originally, i.e. set ThrowableInst[DeadInst] = false. What I meant with my last comment was that we could pop false values from the back of ThrowableInst at the end of this function, until we reach one element that's true. Or do it at the place you had originally, just with the right reverse iterator.

llvm/test/Transforms/DeadStoreElimination/DeleteThrowableInst.ll

1

Can you please also add the test I mentioned in the comment?

[fhahn]

Reverse ping.

Are you still looking to submit this patch? If so, it would be great to not wait too long with responding, otherwise the reviewers will have to re-familiarize themselves with the patch and the comment history.

[quic_aankit]

In D65326#1763222, @fhahn wrote:

Reverse ping.

Are you still looking to submit this patch? If so, it would be great to not wait too long with responding, otherwise the reviewers will have to re-familiarize themselves with the patch and the comment history.

Sorry about it. Working on your comments right away.

[quic_aankit]

Hi @fhahn , I've updated the patch to address your comments

[fhahn]

LGTM with 2 optional nits, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

154

Shouldn't we increment It early, as we remove the element It refers to? It does not seem to cause any issue, but FWIW, it seems that for SPEC and the test-suite, we always do at most 1 iteration of the loop.

llvm/test/Transforms/DeadStoreElimination/DeleteThrowableInst.ll

26

It might be better to store a concrete value instead undef (here and other places in the test casE) to make to test case more robust against future changes.

[quic_aankit]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

154

I don't think that incrementing It after removing the element pointed by it should be an issue as we are not accessing the element in between. In the latest patch I've incremented It before removing the element.

[fhahn]

Thanks! Do you need someone to commit the patch?

[quic_aankit]

I'm trying to get access to commit the patch, but it would be great if you can get someone to commit it.

[fhahn]

In D65326#1771027, @quic_aankit wrote:

I'm trying to get access to commit the patch, but it would be great if you can get someone to commit it.

Sure thing, I can commit it on your behalf!

[quic_aankit]

Hi @fhahn , the commit caused a buildbot failure.
http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/20911
Can you please revert the patch for now while I investigate the issue?

[fhahn]

In D65326#1771415, @quic_aankit wrote:

Hi @fhahn , the commit caused a buildbot failure.
http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/20911
Can you please revert the patch for now while I investigate the issue?

Done in rG19071173fc2e

[quic_aankit]

Hi @fhahn, I've updated the patch to handle the failure with MSVC. Using iterator with pop_back was causing problems on windows.

[fhahn]

Committed as rG369a919514403196dcff7b6bdfa0668dcc733fee

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 // FIXME: This should eventually be extended to be a post-dominator tree
 // traversal.  Doing so would be pretty trivial.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"

 /// 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, BasicBlock::iterator *BBI,
                       MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
                       InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+                      MapVector<Instruction*, bool> &ThrowableInst,
                       SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
   SmallVector<Instruction*, 32> NowDeadInsts;
 
   NowDeadInsts.push_back(I);
   --NumFastOther;
 
   // Keeping the iterator straight is a pain, so we let this routine tell the
   // caller what the next instruction is after we're done mucking about.
   BasicBlock::iterator NewIter = *BBI;
 
   // Before we touch this instruction, remove it from memdep!
   do {
     Instruction *DeadInst = NowDeadInsts.pop_back_val();
+    // Mark the DeadInst as dead in the list of throwable instructions.
+    auto It = ThrowableInst.find(DeadInst);
+    if (It != ThrowableInst.end())
+      ThrowableInst.erase(It);
     ++NumFastOther;
 
     // Try to preserve debug information attached to the dead instruction.
     salvageDebugInfo(*DeadInst);
 
     // This instruction is dead, zap it, in stages.  Start by removing it from
     // MemDep, which needs to know the operands and needs it to be in the
     // function.
do {
 
     if (NewIter == DeadInst->getIterator())
       NewIter = DeadInst->eraseFromParent();
     else
       DeadInst->eraseFromParent();
   } while (!NowDeadInsts.empty());
   *BBI = NewIter;
 }
 
 /// Does this instruction write some memory?  This only returns true for things
 /// that we can analyze with other helpers below.
 static bool hasAnalyzableMemoryWrite(Instruction *I,
                                      const TargetLibraryInfo &TLI) {
   if (isa<StoreInst>(I))
     return true;
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
static void findUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
   }
 }
 
 /// 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,
-                       InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB) {
+                       InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB,
+                       MapVector<Instruction*, bool> &ThrowableInst) {
   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()) {
         break;
 
       LLVM_DEBUG(
           dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
                  << *Dependency << '\n');
 
       // DCE instructions only used to calculate that store.
       BasicBlock::iterator BBI(Dependency);
-      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB);
+      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB,
+                            ThrowableInst);
       ++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);

 /// %A = alloca i32
 /// ...
 /// store i32 1, i32* %A
 /// ret void
 static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
                            MemoryDependenceResults *MD,
                            const TargetLibraryInfo *TLI,
                            InstOverlapIntervalsTy &IOL,
-                           OrderedBasicBlock &OBB) {
+                           OrderedBasicBlock &OBB,
+                           MapVector<Instruction*, bool> &ThrowableInst) {
   bool MadeChange = false;
 
   // Keep track of all of the stack objects that are dead at the end of the
   // function.
   SmallSetVector<const Value*, 16> DeadStackObjects;
 
   // Find all of the alloca'd pointers in the entry block.
   BasicBlock &Entry = BB.getParent()->front();
if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
                         I != E; ++I) {
                      dbgs() << **I;
                      if (std::next(I) != E)
                        dbgs() << ", ";
                    } dbgs()
                    << '\n');
 
         // DCE instructions only used to calculate that store.
-        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB,
+        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
                               &DeadStackObjects);
         ++NumFastStores;
         MadeChange = true;
         continue;
       }
     }
 
     // Remove any dead non-memory-mutating instructions.
     if (isInstructionTriviallyDead(&*BBI, TLI)) {
       LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
                         << *&*BBI << '\n');
-      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB,
+      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst,
                             &DeadStackObjects);
       ++NumFastOther;
       MadeChange = true;
       continue;
     }
 
     if (isa<AllocaInst>(BBI)) {
       // Remove allocas from the list of dead stack objects; there can't be
static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
   return Changed;
 }
 
 static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
                                AliasAnalysis *AA, MemoryDependenceResults *MD,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI,
                                InstOverlapIntervalsTy &IOL,
-                               OrderedBasicBlock &OBB) {
+                               OrderedBasicBlock &OBB,
+                               MapVector<Instruction*, bool> &ThrowableInst) {
   // Must be a store instruction.
   StoreInst *SI = dyn_cast<StoreInst>(Inst);
   if (!SI)
     return false;
 
   // If we're storing the same value back to a pointer that we just loaded from,
   // then the store can be removed.
   if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
     if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
         isRemovable(SI) && memoryIsNotModifiedBetween(DepLoad, SI, AA)) {
 
       LLVM_DEBUG(
           dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
                  << *DepLoad << "\n  STORE: " << *SI << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
       ++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 (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
         memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) {
       LLVM_DEBUG(
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB, ThrowableInst);
       ++NumRedundantStores;
       return true;
     }
   }
   return false;
 }
 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 
   OrderedBasicBlock OBB(&BB);
-  Instruction *LastThrowing = nullptr;
+  MapVector<Instruction *, bool> ThrowableInst;
 
   // A map of interval maps representing partially-overwritten value parts.
   InstOverlapIntervalsTy IOL;
 
   // Do a top-down walk on the BB.
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     // Handle 'free' calls specially.
     if (CallInst *F = isFreeCall(&*BBI, TLI)) {
-      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB);
+      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB, ThrowableInst);
       // Increment BBI after handleFree has potentially deleted instructions.
       // This ensures we maintain a valid iterator.
       ++BBI;
       continue;
     }
 
     Instruction *Inst = &*BBI++;
 
     if (Inst->mayThrow()) {
-      LastThrowing = Inst;
+      ThrowableInst[Inst] = true;
       continue;
     }
 
     // Check to see if Inst writes to memory.  If not, continue.
     if (!hasAnalyzableMemoryWrite(Inst, *TLI))
       continue;
 
     // eliminateNoopStore will update in iterator, if necessary.
-    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB)) {
+    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB,
+        ThrowableInst)) {
       MadeChange = true;
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
     MemDepResult InstDep = MD->getDependency(Inst, &OBB);
 
     // Ignore any store where we can't find a local dependence.
while (InstDep.isDef() || InstDep.isClobber()) {
       Instruction *DepWrite = InstDep.getInst();
       if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
         break;
       MemoryLocation DepLoc = getLocForWrite(DepWrite);
       // If we didn't get a useful location, or if it isn't a size, bail out.
       if (!DepLoc.Ptr)
         break;
 
+      // Iterate over the throwable instruction list to find the last throwable
+      // instruction not removed by call to deleteDeadInstruction.
+      Instruction *LastThrowing = nullptr;
+      if (!ThrowableInst.empty())
+        LastThrowing = ThrowableInst.back().first;
+
       // Make sure we don't look past a call which might throw. This is an
       // issue because MemoryDependenceAnalysis works in the wrong direction:
       // it finds instructions which dominate the current instruction, rather than
       // instructions which are post-dominated by the current instruction.
       //
       // If the underlying object is a non-escaping memory allocation, any store
       // to it is dead along the unwind edge. Otherwise, we need to preserve
       // the store.
while (InstDep.isDef() || InstDep.isClobber()) {
         OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
                                          InstWriteOffset, DepWrite, IOL, *AA,
                                          BB.getParent());
         if (OR == OW_Complete) {
           LLVM_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, &BBI, *MD, *TLI, IOL, OBB);
+          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+                                ThrowableInst);
           ++NumFastStores;
           MadeChange = true;
 
           // We erased DepWrite; start over.
           InstDep = MD->getDependency(Inst, &OBB);
           continue;
         } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
                    ((OR == OW_Begin &&
while (InstDep.isDef() || InstDep.isClobber()) {
                                    LLVMContext::MD_nontemporal};
             SI->copyMetadata(*DepWrite, MDToKeep);
             ++NumModifiedStores;
 
             // Remove earlier, wider, store
             OBB.replaceInstruction(DepWrite, SI);
 
             // Delete the old stores and now-dead instructions that feed them.
-            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB);
-            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB);
+            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB,
+                                  ThrowableInst);
+            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB,
+                                  ThrowableInst);
             MadeChange = true;
 
             // We erased DepWrite and Inst (Loc); start over.
             break;
           }
         }
       }
 
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
   }
 
   if (EnablePartialOverwriteTracking)
     MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL);
 
   // 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, IOL, OBB);
+    MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, OBB, ThrowableInst);
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   bool MadeChange = false;

llvm/test/Transforms/DeadStoreElimination/DeleteThrowableInst.ll

+; RUN: opt < %s -basicaa -dse -S | FileCheck %s
+
+declare i8* @_Znwj(i32) local_unnamed_addr
+
+; CHECK-LABEL: @test(
+; CHECK-NEXT: store
+; CHECK-NEXT: ret void
+define void @test(i8** %ptr) {
+  store i8* undef, i8** %ptr
+  %call = call i8* @_Znwj(i32 1)
+  store i8* %call, i8** %ptr
+  store i8* undef, i8** %ptr
+  ret void
+}