Index: llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -70,6 +70,7 @@ deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering, SmallSetVector *ValueSet = nullptr) { SmallVector NowDeadInsts; @@ -102,15 +103,14 @@ 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; } @@ -590,7 +590,8 @@ static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL) { + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -622,7 +623,7 @@ // 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; @@ -678,7 +679,8 @@ static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL) { + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -737,7 +739,7 @@ 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; @@ -748,7 +750,7 @@ 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; @@ -947,7 +949,8 @@ AliasAnalysis *AA, MemoryDependenceResults *MD, const DataLayout &DL, const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL) { + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { // Must be a store instruction. StoreInst *SI = dyn_cast(Inst); if (!SI) @@ -962,7 +965,7 @@ 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; } @@ -980,7 +983,7 @@ 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; } @@ -994,6 +997,12 @@ 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 InstrOrdering; + size_t InstrIndex = 1; + // A map of interval maps representing partially-overwritten value parts. InstOverlapIntervalsTy IOL; @@ -1001,7 +1010,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, 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; @@ -1010,12 +1019,19 @@ 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; } @@ -1049,6 +1065,31 @@ 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) { + // 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. @@ -1063,7 +1104,7 @@ << *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; @@ -1109,7 +1150,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, IOL); + MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering); return MadeChange; } @@ -1123,6 +1164,7 @@ // cycles that will confuse alias analysis. if (DT->isReachableFromEntry(&BB)) MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI); + return MadeChange; } Index: llvm/trunk/test/Analysis/GlobalsModRef/func-memattributes.ll =================================================================== --- llvm/trunk/test/Analysis/GlobalsModRef/func-memattributes.ll +++ llvm/trunk/test/Analysis/GlobalsModRef/func-memattributes.ll @@ -2,30 +2,30 @@ @X = internal global i32 4 -define void @test0() { +define i32 @test0() { ; CHECK-LABEL: @test0 ; CHECK: store i32 0, i32* @X -; CHECK-NEXT: call void @func_readonly() #0 +; CHECK-NEXT: call i32 @func_readonly() #0 ; CHECK-NEXT: store i32 1, i32* @X store i32 0, i32* @X - call void @func_readonly() #0 + %x = call i32 @func_readonly() #0 store i32 1, i32* @X - ret void + ret i32 %x } -define void @test1() { +define i32 @test1() { ; CHECK-LABEL: @test1 ; CHECK-NOT: store -; CHECK: call void @func_read_argmem_only() #1 +; CHECK: call i32 @func_read_argmem_only() #1 ; CHECK-NEXT: store i32 3, i32* @X store i32 2, i32* @X - call void @func_read_argmem_only() #1 + %x = call i32 @func_read_argmem_only() #1 store i32 3, i32* @X - ret void + ret i32 %x } -declare void @func_readonly() #0 -declare void @func_read_argmem_only() #1 +declare i32 @func_readonly() #0 +declare i32 @func_read_argmem_only() #1 -attributes #0 = { readonly } -attributes #1 = { readonly argmemonly } +attributes #0 = { readonly nounwind } +attributes #1 = { readonly argmemonly nounwind } Index: llvm/trunk/test/Transforms/DeadStoreElimination/free.ll =================================================================== --- llvm/trunk/test/Transforms/DeadStoreElimination/free.ll +++ llvm/trunk/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: llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll =================================================================== --- llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll +++ llvm/trunk/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 +}