DSE: Don't remove stores made live by a call which unwinds.

[eli.friedman]

Summary

Issue exposed by noalias or more aggressive alias analysis.

Fixes http://llvm.org/PR25422.

[hfinkel]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1076

Not clear that OrderedBasicBlock will help here directly. I think you really want two maps:

1. Instruction* -> unsigned (for ordering)
2. Instruction* -> Instruction* (or unsigned) (for the next call that might throw)

Why not just collect the maps above (where you currently set MayThrow), and then answer the question precisely? I think it is likely I'll see performance regressions from this if we over-approximate.

1083

Inst here should really be the first call that might throw, right?

[eli.friedman]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1076

Yes, I can do something like that. Not sure the second map is necessary: I think we just need the most recently seen unwinding call in the block?

1083

Yes; I would probably call it the most recently seen call that might throw.

[hfinkel]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1076

Ah, yes. You're right. Thanks!

[eli.friedman]

• [DSE] Precisely track instructions which may unwind.

[eli.friedman]

Updated. Unfortunately, the patch gets a lot more complicated because of the need to avoid iterator invalidation. On the plus side, I think I fixed a couple latent iterator invalidation bugs.

[mcrosier]

The mechanical changes to deal with the iterators LGTM. I'll defer to Hal or someone else to approve the changes to remove stores made live by a call which unwinds.

lib/Transforms/Scalar/DeadStoreElimination.cpp

117

Should we keep the comments from line 54?

1011

pre-increment InstrIndex.

1077

Space between 'assert' and right paren.

Perhaps, a clang-format?

[mcrosier]

Hi @eli.friedman,
I believe I've hijacked all I'm going to, so you might consider rebasing the patch on top of the fresh DSE updates. Hopefully, this patch is now fairly simple and thanks for your assistance.

Chad

[eli.friedman]

Rebase on top of trunk.

[• dberlin]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1004

Is this different from orderedbasicblock?

1076

(and fwiw, memdep does not consider maythrow, only aliasing. AFAIK, it will never return a maythrow call as a dep unless it thinks, conservatively, that it aliases the pointer. It mostly does think that when we don't have good call mod/ref info, but when we do, it happily does not return maythrow calls as deps)

1083

PointerMayBeCapturedBefore is an O(N) call, at best.
It even says " This routine can be expensive, so consider
/// caching the results. "

Can we really not do better?

[eli.friedman]

InstrOrdering is basically an OrderedBasicBlock, I guess... I think I'd need to modify the interface a bit for this exact use to deal with modifications.

lib/Transforms/Scalar/DeadStoreElimination.cpp

1083

We could try to cache the result, I guess... but I don't think we would end up hitting any such cache very often, considering that you can only reuse the cache for exactly the same inputs.

I could use PointerMayBeCaptured instead. Not quite as strong, but I guess the extra accuracy might not be that useful (and it's easier to cache, if necessary).

[eli.friedman]

Don't use PointerMayBeCapturedBefore. Add some comments.

[eli.friedman]

Ping.

[eli.friedman]

Ping.

lib/Transforms/Scalar/DeadStoreElimination.cpp

 /// 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,
+                      DenseMap<Instruction*, size_t> *InstrOrdering,
                       SmallSetVector<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.
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
       // If this operand just became dead, add it to the NowDeadInsts list.
       if (!Op->use_empty()) continue;
 
       if (Instruction *OpI = dyn_cast<Instruction>(Op))
         if (isInstructionTriviallyDead(OpI, &TLI))
           NowDeadInsts.push_back(OpI);
     }
 
+    if (ValueSet) ValueSet->remove(DeadInst);
+    InstrOrdering->erase(DeadInst);
+    IOL.erase(DeadInst);
 
     if (NewIter == DeadInst->getIterator())
       NewIter = DeadInst->eraseFromParent();
     else
       DeadInst->eraseFromParent();
-
-    IOL.erase(DeadInst);
-
-    if (ValueSet) ValueSet->remove(DeadInst);
   } 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 hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
   if (isa<StoreInst>(I))
     return true;
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
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) {
+                       InstOverlapIntervalsTy &IOL,
+                       DenseMap<Instruction*, size_t> *InstrOrdering) {
   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()) {
       if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
         break;
 
       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);
+      deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, InstrOrdering);
       ++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);

 /// Ex:
 /// %A = alloca i32
 /// ...
 /// store i32 1, i32* %A
 /// ret void
 static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
                              MemoryDependenceResults *MD,
                              const TargetLibraryInfo *TLI,
-                             InstOverlapIntervalsTy &IOL) {
+                             InstOverlapIntervalsTy &IOL,
+                             DenseMap<Instruction*, size_t> *InstrOrdering) {
   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, &BBI, *MD, *TLI, IOL, &DeadStackObjects);
+        deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects);
         ++NumFastStores;
         MadeChange = true;
         continue;
       }
     }
 
     // Remove any dead non-memory-mutating instructions.
     if (isInstructionTriviallyDead(&*BBI, TLI)) {
       DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
                    << *&*BBI << '\n');
-      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, &DeadStackObjects);
+      deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects);
       ++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.
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) {
+                               InstOverlapIntervalsTy &IOL,
+                               DenseMap<Instruction*, size_t> *InstrOrdering) {
   // 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)) {
 
       DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
                    << *DepLoad << "\n  STORE: " << *SI << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering);
       ++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)) {
       DEBUG(
           dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
                  << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n');
 
-      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL);
+      deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering);
       ++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;
 
+  // FIXME: Maybe change this to use some abstraction like OrderedBasicBlock?
+  // The current OrderedBasicBlock can't deal with mutation at the moment.
+  size_t LastThrowingInstIndex = 0;
+  DenseMap<Instruction*, size_t> InstrOrdering;
+  size_t InstrIndex = 1;
+
   // 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);
+      MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, &InstrOrdering);
       // Increment BBI after handleFree has potentially deleted instructions.
       // This ensures we maintain a valid iterator.
       ++BBI;
       continue;
     }
 
     Instruction *Inst = &*BBI++;
 
+    size_t CurInstNumber = InstrIndex++;
+    InstrOrdering.insert(std::make_pair(Inst, CurInstNumber));
+    if (Inst->mayThrow()) {
+      LastThrowingInstIndex = CurInstNumber;
+      continue;
+    }
+
     // Check to see if Inst writes to memory.  If not, continue.
     if (!hasMemoryWrite(Inst, *TLI))
       continue;
 
     // eliminateNoopStore will update in iterator, if necessary.
-    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL)) {
+    if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) {
       MadeChange = true;
       continue;
     }
 
     // If we find something that writes memory, get its memory dependence.
     MemDepResult InstDep = MD->getDependency(Inst);
 
     // Ignore any store where we can't find a local dependence.
while (InstDep.isDef() || InstDep.isClobber()) {
       //
       // 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;
 
+      // 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.
+      size_t DepIndex = InstrOrdering.lookup(DepWrite);
+      assert(DepIndex && "Unexpected instruction");
+      if (DepIndex <= LastThrowingInstIndex) {
+        const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
+        bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
+        if (!IsStoreDeadOnUnwind) {
+            // We're looking for a call to an allocation function
+            // where the allocation doesn't escape before the last
+            // throwing instruction; PointerMayBeCaptured
+            // reasonably fast approximation.
+            IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
+                !PointerMayBeCaptured(Underlying, false, true);
+        }
+        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.
       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 == OverwriteComplete) {
           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);
+          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, &InstrOrdering);
           ++NumFastStores;
           MadeChange = true;
 
           // We erased DepWrite; start over.
           InstDep = MD->getDependency(Inst);
           continue;
         } else if ((OR == OverwriteEnd && isShortenableAtTheEnd(DepWrite)) ||
                    ((OR == OverwriteBegin &&
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);
+    MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering);
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   bool MadeChange = false;
   for (BasicBlock &BB : F)
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
     if (DT->isReachableFromEntry(&BB))
       MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
+
   return MadeChange;
 }
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis *AA = &AM.getResult<AAManager>(F);

test/Transforms/DeadStoreElimination/free.ll

 ; RUN: opt < %s -basicaa -dse -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64"
 
 declare void @free(i8* nocapture)
 declare noalias i8* @malloc(i64)
 
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT: bitcast
 ; CHECK-NEXT: @free
 ; CHECK-NEXT: ret void
 define void @test(i32* %Q, i32* %P) {
         %DEAD = load i32, i32* %Q            ; <i32> [#uses=1]
         store i32 %DEAD, i32* %P
         %1 = bitcast i32* %P to i8*
-        tail call void @free(i8* %1)
+        tail call void @free(i8* %1) nounwind
         ret void
 }
 
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT: bitcast
 ; CHECK-NEXT: @free
 ; CHECK-NEXT: ret void
 define void @test2({i32, i32}* %P) {
   %Q = getelementptr {i32, i32}, {i32, i32} *%P, i32 0, i32 1
   store i32 4, i32* %Q
         %1 = bitcast {i32, i32}* %P to i8*
-        tail call void @free(i8* %1)
+        tail call void @free(i8* %1) nounwind
   ret void
 }
 
 ; CHECK-LABEL: @test3(
 ; CHECK-NOT: store
 ; CHECK: ret void
 define void @test3() {
   %m = call i8* @malloc(i64 24)
   store i8 0, i8* %m
   %m1 = getelementptr i8, i8* %m, i64 1
   store i8 1, i8* %m1
-  call void @free(i8* %m)
+  call void @free(i8* %m) nounwind
   ret void
 }
 
 ; PR11240
 ; CHECK-LABEL: @test4(
 ; CHECK-NOT: store
 ; CHECK: ret void
 define void @test4(i1 %x) nounwind {

test/Transforms/DeadStoreElimination/simple.ll

bb2:
   store i32 %v, i32* %p, align 4
   ; Might read and overwrite value at %p, but doesn't matter.
   call void @unknown_func()
   br i1 undef, label %bb1, label %bb3
 bb3:
   ret i32 0
 }
 
+; Don't remove redundant store: unknown_func could unwind
+; CHECK-LABEL: @test34(
+; CHECK: store i32 1
+; CHECK: store i32 0
+; CHECK: ret
+define void @test34(i32* noalias %p) {
+  store i32 1, i32* %p
+  call void @unknown_func()
+  store i32 0, i32* %p
+  ret void
+}
+
+; Remove redundant store even with an unwinding function in the same block
+; CHECK-LABEL: @test35(
+; CHECK: call void @unknown_func
+; CHECK-NEXT: store i32 0
+; CHECK-NEXT: ret void
+define void @test35(i32* noalias %p) {
+  call void @unknown_func()
+  store i32 1, i32* %p
+  store i32 0, i32* %p
+  ret void
+}