Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -59,7 +59,6 @@ //===----------------------------------------------------------------------===// // 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. @@ -67,6 +66,7 @@ static void deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, + DenseMap *InstrOrdering, SmallSetVector *ValueSet = nullptr) { SmallVector NowDeadInsts; @@ -99,13 +99,13 @@ NowDeadInsts.push_back(OpI); } + if (ValueSet) ValueSet->remove(DeadInst); + InstrOrdering->erase(DeadInst); if (NewIter == DeadInst->getIterator()) NewIter = DeadInst->eraseFromParent(); else DeadInst->eraseFromParent(); - - if (ValueSet) ValueSet->remove(DeadInst); } while (!NowDeadInsts.empty()); *BBI = NewIter; } @@ -587,7 +587,8 @@ /// to a field of that structure. static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + DenseMap *InstrOrdering) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -616,7 +617,7 @@ // DCE instructions only used to calculate that store. BasicBlock::iterator BBI(Dependency); - deleteDeadInstruction(Dependency, &BBI, *MD, *TLI); + deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, InstrOrdering); ++NumFastStores; MadeChange = true; @@ -671,7 +672,8 @@ /// ret void static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + DenseMap *InstrOrdering) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -730,7 +732,7 @@ dbgs() << '\n'); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dead, &BBI, *MD, *TLI, &DeadStackObjects); + deleteDeadInstruction(Dead, &BBI, *MD, *TLI, InstrOrdering, &DeadStackObjects); ++NumFastStores; MadeChange = true; continue; @@ -739,7 +741,7 @@ // Remove any dead non-memory-mutating instructions. if (isInstructionTriviallyDead(&*BBI, TLI)) { - deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, &DeadStackObjects); + deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, InstrOrdering, &DeadStackObjects); ++NumFastOther; MadeChange = true; continue; @@ -937,7 +939,8 @@ static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, AliasAnalysis *AA, MemoryDependenceResults *MD, const DataLayout &DL, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + DenseMap *InstrOrdering) { // Must be a store instruction. StoreInst *SI = dyn_cast(Inst); if (!SI) @@ -952,7 +955,7 @@ DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); - deleteDeadInstruction(SI, &BBI, *MD, *TLI); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, InstrOrdering); ++NumRedundantStores; return true; } @@ -970,7 +973,7 @@ dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: " << *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n'); - deleteDeadInstruction(SI, &BBI, *MD, *TLI); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, InstrOrdering); ++NumRedundantStores; return true; } @@ -984,6 +987,11 @@ const DataLayout &DL = BB.getModule()->getDataLayout(); bool MadeChange = false; + Instruction *LastThrowingInst = nullptr; + size_t LastThrowingInstIndex = 0; + DenseMap InstrOrdering; + size_t InstrIndex = 1; + // A map of interval maps representing partially-overwritten value parts. InstOverlapIntervalsTy IOL; @@ -991,7 +999,7 @@ 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); + MadeChange |= handleFree(F, AA, MD, DT, TLI, &InstrOrdering); // Increment BBI after handleFree has potentially deleted instructions. // This ensures we maintain a valid iterator. ++BBI; @@ -1000,12 +1008,20 @@ Instruction *Inst = &*BBI++; + size_t CurInstNumber = InstrIndex++; + InstrOrdering.insert(std::make_pair(Inst, CurInstNumber)); + if (Inst->mayThrow()) { + LastThrowingInst = Inst; + 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)) { + if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, &InstrOrdering)) { MadeChange = true; continue; } @@ -1039,6 +1055,27 @@ 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(Underlying); + if (!IsStoreDeadOnUnwind) { + IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) && + !PointerMayBeCapturedBefore(Underlying, true, true, LastThrowingInst, DT, 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. @@ -1053,7 +1090,7 @@ << *DepWrite << "\n KILLER: " << *Inst << '\n'); IOL.erase(DepWrite); // Delete the store and now-dead instructions that feed it. - deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI); + deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, &InstrOrdering); ++NumFastStores; MadeChange = true; @@ -1099,7 +1136,7 @@ // 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); + MadeChange |= handleEndBlock(BB, AA, MD, TLI, &InstrOrdering); return MadeChange; } @@ -1113,6 +1150,7 @@ // cycles that will confuse alias analysis. if (DT->isReachableFromEntry(&BB)) MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI); + return MadeChange; } Index: test/Transforms/DeadStoreElimination/free.ll =================================================================== --- test/Transforms/DeadStoreElimination/free.ll +++ test/Transforms/DeadStoreElimination/free.ll @@ -13,7 +13,7 @@ %DEAD = load i32, i32* %Q ; [#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 } @@ -25,7 +25,7 @@ %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 } @@ -37,7 +37,7 @@ 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 } Index: test/Transforms/DeadStoreElimination/simple.ll =================================================================== --- test/Transforms/DeadStoreElimination/simple.ll +++ test/Transforms/DeadStoreElimination/simple.ll @@ -498,3 +498,26 @@ 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 +}