Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -55,11 +55,11 @@ /// 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) { +static void recursivelyDeleteInstructions(Instruction *I, + MemoryDependenceResults &MD, + const TargetLibraryInfo &TLI) { SmallVector NowDeadInsts; + assert(isInstructionTriviallyDead(I, &TLI)); NowDeadInsts.push_back(I); --NumFastOther; @@ -87,11 +87,32 @@ } DeadInst->eraseFromParent(); - - if (ValueSet) ValueSet->remove(DeadInst); } while (!NowDeadInsts.empty()); } +static void deleteDeadInstruction(Instruction *DeadInst, + MemoryDependenceResults &MD, + const TargetLibraryInfo &TLI, + SmallSetVector *ValueSet, + 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); + 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) { @@ -502,7 +523,8 @@ /// to a field of that structure. static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + SmallVectorImpl &DeadInstList) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -532,7 +554,7 @@ auto Next = ++Dependency->getIterator(); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dependency, *MD, *TLI); + deleteDeadInstruction(Dependency, *MD, *TLI, nullptr, DeadInstList); ++NumFastStores; MadeChange = true; @@ -586,8 +608,9 @@ /// store i32 1, i32* %A /// ret void static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, - MemoryDependenceResults *MD, - const TargetLibraryInfo *TLI) { + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, + SmallVectorImpl &DeadInstList) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -647,7 +670,7 @@ dbgs() << '\n'); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects); + deleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects, DeadInstList); ++NumFastStores; MadeChange = true; continue; @@ -657,7 +680,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, DeadInstList); ++NumFastOther; MadeChange = true; continue; @@ -731,202 +754,216 @@ return MadeChange; } -static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, - MemoryDependenceResults *MD, DominatorTree *DT, - const TargetLibraryInfo *TLI) { - const DataLayout &DL = BB.getModule()->getDataLayout(); - bool MadeChange = false; - - // Do a top-down walk on the BB. - for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { - Instruction *Inst = &*BBI++; - - // Handle 'free' calls specially. - if (CallInst *F = isFreeCall(Inst, TLI)) { - MadeChange |= handleFree(F, AA, MD, DT, TLI); - continue; +static bool eliminateNoopStore(Instruction *Inst, MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, AliasAnalysis *AA, + const DataLayout &DL, + 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, DeadInstList); + ++NumRedundantStores; + return true; + } } - // If we find something that writes memory, get its memory dependence. - 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)) { + // Remove null stores into the calloc'ed objects + Constant *StoredConstant = dyn_cast(SI->getValueOperand()); - auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) { - // deleteDeadInstruction can delete the current instruction. Save BBI - // in case we need it. - WeakVH NextInst(&*BBI); + if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) { + Instruction *UnderlyingPointer = dyn_cast( + GetUnderlyingObject(SI->getPointerOperand(), DL)); - deleteDeadInstruction(DeadInst, *MD, *TLI); + 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'); - if (!NextInst) // Next instruction deleted. - BBI = BB.begin(); - else if (BBI != BB.begin()) // Revisit this instruction if possible. - --BBI; + deleteDeadInstruction(SI, *MD, *TLI, nullptr, DeadInstList); ++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; - } + return true; } + } + } + return false; +} - // Remove null stores into the calloc'ed objects - Constant *StoredConstant = dyn_cast(SI->getValueOperand()); +static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, DominatorTree *DT, + const TargetLibraryInfo *TLI) { + const DataLayout &DL = BB.getModule()->getDataLayout(); + bool MadeChange = false; - if (StoredConstant && StoredConstant->isNullValue() && - isRemovable(SI)) { - Instruction *UnderlyingPointer = dyn_cast( - GetUnderlyingObject(SI->getPointerOperand(), DL)); + bool Change; + do { + Change = false; + SmallVector DeadInstList; - 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'); + // 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++; - RemoveDeadInstAndUpdateBBI(SI); - continue; - } + // Handle 'free' calls specially. + if (CallInst *F = isFreeCall(Inst, TLI)) { + Change |= handleFree(F, AA, MD, DT, TLI, DeadInstList); + continue; } - } - MemDepResult InstDep = MD->getDependency(Inst); + // If we find something that writes memory, get its memory dependence. + if (!hasMemoryWrite(Inst, *TLI)) + continue; - // Ignore any store where we can't find a local dependence. - // FIXME: cross-block DSE would be fun. :) - if (!InstDep.isDef() && !InstDep.isClobber()) - continue; + if (eliminateNoopStore(Inst, MD, TLI, AA, DL, DeadInstList)) { + Change = true; + continue; + } - // Figure out what location is being stored to. - MemoryLocation Loc = getLocForWrite(Inst, *AA); + MemDepResult InstDep = MD->getDependency(Inst); - // If we didn't get a useful location, fail. - if (!Loc.Ptr) - continue; + // Figure out what location is being stored to. + MemoryLocation Loc = getLocForWrite(Inst, *AA); - while (InstDep.isDef() || InstDep.isClobber()) { - // Get the memory clobbered by the instruction we depend on. MemDep will - // skip any instructions that 'Loc' clearly doesn't interact with. If we - // end up depending on a may- or must-aliased load, then we can't optimize - // away the store and we bail out. However, if we depend on something - // that overwrites the memory location we *can* potentially optimize it. - // - // 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; + // If we didn't get a useful location, fail. + if (!Loc.Ptr) + continue; - // 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); - 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, *MD, *TLI); - ++NumFastStores; - MadeChange = true; - - // deleteDeadInstruction can delete the current instruction in loop - // cases, reset BBI. - BBI = Inst->getIterator(); - auto BBBegin = BB.begin(); - while (BBI != BBBegin && isa(*(--BBI))) - ; + while (InstDep.isDef() || InstDep.isClobber()) { + // Get the memory clobbered by the instruction we depend on. MemDep + // will + // skip any instructions that 'Loc' clearly doesn't interact with. If + // we + // end up depending on a may- or must-aliased load, then we can't + // optimize + // away the store and we bail out. However, if we depend on something + // that overwrites the memory location we *can* potentially optimize it. + // + // 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; - } else if ((OR == OverwriteEnd && isShortenableAtTheEnd(DepWrite)) || - ((OR == OverwriteBegin && - isShortenableAtTheBeginning(DepWrite)))) { - // TODO: base this on the target vector size so that if the earlier - // store was too small to get vector writes anyway then its likely - // a good idea to shorten it - // Power of 2 vector writes are probably always a bad idea to optimize - // as any store/memset/memcpy is likely using vector instructions so - // shortening it to not vector size is likely to be slower - MemIntrinsic *DepIntrinsic = cast(DepWrite); - unsigned DepWriteAlign = DepIntrinsic->getAlignment(); - bool IsOverwriteEnd = (OR == OverwriteEnd); - if (!IsOverwriteEnd) - InstWriteOffset = int64_t(InstWriteOffset + Loc.Size); - - if ((llvm::isPowerOf2_64(InstWriteOffset) && - DepWriteAlign <= InstWriteOffset) || - ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) { - - DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW " - << (IsOverwriteEnd ? "END" : "BEGIN") << ": " - << *DepWrite << "\n KILLER (offset " - << InstWriteOffset << ", " << DepLoc.Size << ")" - << *Inst << '\n'); - - int64_t NewLength = - IsOverwriteEnd - ? InstWriteOffset - DepWriteOffset - : DepLoc.Size - (InstWriteOffset - DepWriteOffset); - - Value *DepWriteLength = DepIntrinsic->getLength(); - Value *TrimmedLength = - ConstantInt::get(DepWriteLength->getType(), NewLength); - DepIntrinsic->setLength(TrimmedLength); - - if (!IsOverwriteEnd) { - int64_t OffsetMoved = (InstWriteOffset - DepWriteOffset); - Value *Indices[1] = { - ConstantInt::get(DepWriteLength->getType(), OffsetMoved)}; - GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds( - DepIntrinsic->getRawDest(), Indices, "", DepWrite); - DepIntrinsic->setDest(NewDestGEP); + + // 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); + if (OR == OverwriteComplete) { + DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DepWrite + << "\n KILLER: " << *Inst << '\n'); + + deleteDeadInstruction(DepWrite, *MD, *TLI, nullptr, DeadInstList); + ++NumFastStores; + Change = true; + + // Eliminating a store could make this store a no-op. + if (eliminateNoopStore(Inst, MD, TLI, AA, DL, DeadInstList)) + break; + + // We erased DepWrite; start over. + InstDep = MD->getDependency(Inst); + continue; + } else if ((OR == OverwriteEnd && isShortenableAtTheEnd(DepWrite)) || + ((OR == OverwriteBegin && + isShortenableAtTheBeginning(DepWrite)))) { + // TODO: base this on the target vector size so that if the earlier + // store was too small to get vector writes anyway then its likely + // a good idea to shorten it + // Power of 2 vector writes are probably always a bad idea to + // optimize + // as any store/memset/memcpy is likely using vector instructions so + // shortening it to not vector size is likely to be slower + MemIntrinsic *DepIntrinsic = cast(DepWrite); + unsigned DepWriteAlign = DepIntrinsic->getAlignment(); + bool IsOverwriteEnd = (OR == OverwriteEnd); + if (!IsOverwriteEnd) + InstWriteOffset = int64_t(InstWriteOffset + Loc.Size); + + if ((llvm::isPowerOf2_64(InstWriteOffset) && + DepWriteAlign <= InstWriteOffset) || + ((DepWriteAlign != 0) && + InstWriteOffset % DepWriteAlign == 0)) { + + DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW " + << (IsOverwriteEnd ? "END" : "BEGIN") << ": " + << *DepWrite << "\n KILLER (offset " + << InstWriteOffset << ", " << DepLoc.Size << ")" + << *Inst << '\n'); + + int64_t NewLength = + IsOverwriteEnd + ? InstWriteOffset - DepWriteOffset + : DepLoc.Size - (InstWriteOffset - DepWriteOffset); + + Value *DepWriteLength = DepIntrinsic->getLength(); + Value *TrimmedLength = + ConstantInt::get(DepWriteLength->getType(), NewLength); + DepIntrinsic->setLength(TrimmedLength); + + if (!IsOverwriteEnd) { + int64_t OffsetMoved = (InstWriteOffset - DepWriteOffset); + Value *Indices[1] = { + ConstantInt::get(DepWriteLength->getType(), OffsetMoved)}; + GetElementPtrInst *NewDestGEP = + GetElementPtrInst::CreateInBounds( + DepIntrinsic->getRawDest(), Indices, "", DepWrite); + DepIntrinsic->setDest(NewDestGEP); + } + Change = true; } - MadeChange = true; } } - } - // If this is a may-aliased store that is clobbering the store value, we - // can keep searching past it for another must-aliased pointer that stores - // to the same location. For example, in: - // store -> P - // store -> Q - // store -> P - // we can remove the first store to P even though we don't know if P and Q - // alias. - if (DepWrite == &BB.front()) break; - - // Can't look past this instruction if it might read 'Loc'. - if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref) - break; + // If this is a may-aliased store that is clobbering the store value, we + // can keep searching past it for another must-aliased pointer that + // stores + // to the same location. For example, in: + // store -> P + // store -> Q + // store -> P + // we can remove the first store to P even though we don't know if P and + // Q + // alias. + if (DepWrite == &BB.front()) + break; + + // Can't look past this instruction if it might read 'Loc'. + if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref) + break; - InstDep = MD->getPointerDependencyFrom(Loc, false, - DepWrite->getIterator(), &BB); + InstDep = MD->getPointerDependencyFrom(Loc, false, + DepWrite->getIterator(), &BB); + } } - } - // 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); + // 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) + Change |= 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); + } + MadeChange |= Change; + } while (Change); return MadeChange; }