Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -51,16 +51,14 @@ // 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 *ValueSet = nullptr) { +recursivelyDeleteInstructions(Instruction *I, + MemoryDependenceResults &MD, + const TargetLibraryInfo &TLI) { SmallVector NowDeadInsts; + assert(isInstructionTriviallyDead(I, &TLI)); + NowDeadInsts.push_back(I); --NumFastOther; @@ -87,11 +85,33 @@ } DeadInst->eraseFromParent(); - - if (ValueSet) ValueSet->remove(DeadInst); } while (!NowDeadInsts.empty()); } +static void +deleteDeadInstruction(Instruction *DeadInst, MemoryDependenceResults &MD, + const TargetLibraryInfo &TLI, + SmallSetVector *ValueSet, + DenseMap *InstrOrdering, + SmallVectorImpl &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(Op)) + if (isInstructionTriviallyDead(I, &TLI)) + DeadInstList.push_back(WeakVH(I)); + } + MD.removeInstruction(DeadInst); + if (ValueSet) ValueSet->remove(DeadInst); + if (InstrOrdering) InstrOrdering->erase(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) { @@ -516,7 +536,9 @@ /// 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, + SmallVectorImpl &DeadInstList) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -546,7 +568,7 @@ auto Next = ++Dependency->getIterator(); // DCE instructions only used to calculate that store - deleteDeadInstruction(Dependency, *MD, *TLI); + deleteDeadInstruction(Dependency, *MD, *TLI, nullptr, InstrOrdering, DeadInstList); ++NumFastStores; MadeChange = true; @@ -601,7 +623,8 @@ /// ret void static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + SmallVectorImpl &DeadInstList) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -661,7 +684,7 @@ dbgs() << '\n'); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects); + deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects, nullptr, DeadInstList); ++NumFastStores; MadeChange = true; continue; @@ -671,7 +694,7 @@ // Remove any dead non-memory-mutating instructions. if (isInstructionTriviallyDead(&*BBI, TLI)) { Instruction *Inst = &*BBI++; - deleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects); + deleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects, nullptr, DeadInstList); ++NumFastOther; MadeChange = true; continue; @@ -745,19 +768,83 @@ return MadeChange; } +static bool eliminateNoopStore(Instruction *Inst, + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, + AliasAnalysis *AA, + const DataLayout &DL, + DenseMap *InstrOrdering, + SmallVectorImpl &DeadInstList) { + // 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(Inst)) { + if (LoadInst *DepLoad = dyn_cast(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, *MD, *TLI, nullptr, InstrOrdering, DeadInstList); + ++NumRedundantStores; + return true; + } + } + + // Remove null stores into the calloc'ed objects + Constant *StoredConstant = dyn_cast(SI->getValueOperand()); + + if (StoredConstant && StoredConstant->isNullValue() && + isRemovable(SI)) { + Instruction *UnderlyingPointer = dyn_cast( + 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, *MD, *TLI, nullptr, InstrOrdering, DeadInstList); + ++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; + SmallVector DeadInstList; + + Instruction *LastThrowingInst = nullptr; + size_t LastThrowingInstIndex = 0; + DenseMap InstrOrdering; + size_t InstrIndex = 1; + // 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++; + size_t CurInstNumber = InstrIndex++; + InstrOrdering.insert(std::make_pair(Inst, CurInstNumber)); + if (Inst->mayThrow()) { + LastThrowingInst = Inst; + LastThrowingInstIndex = CurInstNumber; + continue; + } + // Handle 'free' calls specially. if (CallInst *F = isFreeCall(Inst, TLI)) { - MadeChange |= handleFree(F, AA, MD, DT, TLI); + MadeChange |= handleFree(F, AA, MD, DT, TLI, &InstrOrdering, DeadInstList); continue; } @@ -765,65 +852,13 @@ 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(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(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'); - - RemoveDeadInstAndUpdateBBI(SI); - continue; - } - } - - // Remove null stores into the calloc'ed objects - Constant *StoredConstant = dyn_cast(SI->getValueOperand()); - - if (StoredConstant && StoredConstant->isNullValue() && - isRemovable(SI)) { - Instruction *UnderlyingPointer = dyn_cast( - 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'); - - RemoveDeadInstAndUpdateBBI(SI); - continue; - } - } + if (eliminateNoopStore(Inst, MD, TLI, AA, DL, &InstrOrdering, DeadInstList)) { + MadeChange = true; + continue; } MemDepResult InstDep = MD->getDependency(Inst); - // Ignore any store where we can't find a local dependence. - // FIXME: cross-block DSE would be fun. :) - if (!InstDep.isDef() && !InstDep.isClobber()) - continue; - // Figure out what location is being stored to. MemoryLocation Loc = getLocForWrite(Inst, *AA); @@ -845,6 +880,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. @@ -857,17 +913,17 @@ 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, &InstrOrdering, DeadInstList); ++NumFastStores; MadeChange = true; - // deleteDeadInstruction can delete the current instruction in loop - // cases, reset BBI. - BBI = Inst->getIterator(); - if (BBI != BB.begin()) - --BBI; - break; + // Eliminating a store could make this store a no-op. + if (eliminateNoopStore(Inst, MD, TLI, AA, DL, &InstrOrdering, DeadInstList)) + break; + + // We erased DepWrite; start over. + InstDep = MD->getDependency(Inst); + continue; } else if ((OR == OverwriteEnd && isShortenableAtTheEnd(DepWrite)) || ((OR == OverwriteBegin && isShortenableAtTheBeginning(DepWrite)))) { @@ -938,7 +994,13 @@ // 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, DeadInstList); + + // Erase dead instructions we put off erasing. + for (WeakVH &VH: DeadInstList) { + if (Instruction *I = cast_or_null(VH)) + recursivelyDeleteInstructions(I, *MD, *TLI); + } return MadeChange; } @@ -952,6 +1014,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 +}