Differential D13021 Diff 35478 llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

Changeset View

Standalone View

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

Show First 20 Lines • Show All 72 Lines • ▼ Show 20 Lines	bool runOnFunction(Function &F) override {
if (DT->isReachableFromEntry(I))		if (DT->isReachableFromEntry(I))
Changed \|= runOnBasicBlock(*I);		Changed \|= runOnBasicBlock(*I);

AA = nullptr; MD = nullptr; DT = nullptr;		AA = nullptr; MD = nullptr; DT = nullptr;
return Changed;		return Changed;
}		}

bool runOnBasicBlock(BasicBlock &BB);		bool runOnBasicBlock(BasicBlock &BB);
bool MemoryIsNotModifiedBetween(LoadInst LI, StoreInst SI);		bool MemoryIsNotModifiedBetween(Instruction FirstI, Instruction SecondI);
bool HandleFree(CallInst *F);		bool HandleFree(CallInst *F);
bool handleEndBlock(BasicBlock &BB);		bool handleEndBlock(BasicBlock &BB);
void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,		void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
SmallSetVector<Value *, 16> &DeadStackObjects,		SmallSetVector<Value *, 16> &DeadStackObjects,
const DataLayout &DL);		const DataLayout &DL);

void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();		AU.setPreservesCFG();
▲ Show 20 Lines • Show All 388 Lines • ▼ Show 20 Lines
}		}


//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
// DSE Pass		// DSE Pass
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

bool DSE::runOnBasicBlock(BasicBlock &BB) {		bool DSE::runOnBasicBlock(BasicBlock &BB) {
		const DataLayout &DL = BB.getModule()->getDataLayout();
bool MadeChange = false;		bool MadeChange = false;

// Do a top-down walk on the BB.		// Do a top-down walk on the BB.
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {		for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
Instruction *Inst = BBI++;		Instruction *Inst = BBI++;

// Handle 'free' calls specially.		// Handle 'free' calls specially.
if (CallInst *F = isFreeCall(Inst, TLI)) {		if (CallInst *F = isFreeCall(Inst, TLI)) {
MadeChange \|= HandleFree(F);		MadeChange \|= HandleFree(F);
continue;		continue;
}		}

// If we find something that writes memory, get its memory dependence.		// If we find something that writes memory, get its memory dependence.
if (!hasMemoryWrite(Inst, *TLI))		if (!hasMemoryWrite(Inst, *TLI))
continue;		continue;

// If we're storing the same value back to a pointer that we just		// If we're storing the same value back to a pointer that we just
// loaded from, then the store can be removed.		// loaded from, then the store can be removed.
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {		if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
isRemovable(SI) &&
MemoryIsNotModifiedBetween(DepLoad, SI)) {

DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n "
<< "LOAD: " << DepLoad << "\n STORE: " << SI << '\n');

		auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) {
// DeleteDeadInstruction can delete the current instruction. Save BBI		// DeleteDeadInstruction can delete the current instruction. Save BBI
// in case we need it.		// in case we need it.
WeakVH NextInst(BBI);		WeakVH NextInst(BBI);

DeleteDeadInstruction(SI, MD, TLI);		DeleteDeadInstruction(DeadInst, MD, TLI);

if (!NextInst) // Next instruction deleted.		if (!NextInst) // Next instruction deleted.
BBI = BB.begin();		BBI = BB.begin();
else if (BBI != BB.begin()) // Revisit this instruction if possible.		else if (BBI != BB.begin()) // Revisit this instruction if possible.
--BBI;		--BBI;
++NumRedundantStores;		++NumRedundantStores;
MadeChange = true;		MadeChange = true;
		};

		if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
		if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
		isRemovable(SI) &&
		MemoryIsNotModifiedBetween(DepLoad, SI)) {

		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<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)) {
		DEBUG(dbgs()
		<< "DSE: Remove null store to the calloc'ed object:\n DEAD: "
		<< Inst << "\n OBJECT: " << UnderlyingPointer << '\n');

		RemoveDeadInstAndUpdateBBI(SI);
continue;		continue;
}		}
}		}
}		}

MemDepResult InstDep = MD->getDependency(Inst);		MemDepResult InstDep = MD->getDependency(Inst);

// Ignore any store where we can't find a local dependence.		// Ignore any store where we can't find a local dependence.
Show All 23 Lines	while (InstDep.isDef() \|\| InstDep.isClobber()) {
break;		break;

// If we find a write that is a) removable (i.e., non-volatile), b) is		// 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		// completely obliterated by the store to 'Loc', and c) which we know that
// 'Inst' doesn't load from, then we can remove it.		// 'Inst' doesn't load from, then we can remove it.
if (isRemovable(DepWrite) &&		if (isRemovable(DepWrite) &&
!isPossibleSelfRead(Inst, Loc, DepWrite, TLI, AA)) {		!isPossibleSelfRead(Inst, Loc, DepWrite, TLI, AA)) {
int64_t InstWriteOffset, DepWriteOffset;		int64_t InstWriteOffset, DepWriteOffset;
const DataLayout &DL = BB.getModule()->getDataLayout();
OverwriteResult OR =		OverwriteResult OR =
isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);		isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset);
if (OR == OverwriteComplete) {		if (OR == OverwriteComplete) {
DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "		DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< DepWrite << "\n KILLER: " << Inst << '\n');		<< DepWrite << "\n KILLER: " << Inst << '\n');

// Delete the store and now-dead instructions that feed it.		// Delete the store and now-dead instructions that feed it.
DeleteDeadInstruction(DepWrite, MD, TLI);		DeleteDeadInstruction(DepWrite, MD, TLI);
▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines	bool DSE::runOnBasicBlock(BasicBlock &BB) {
// If this block ends in a return, unwind, or unreachable, all allocas are		// 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.		// dead at its end, which means stores to them are also dead.
if (BB.getTerminator()->getNumSuccessors() == 0)		if (BB.getTerminator()->getNumSuccessors() == 0)
MadeChange \|= handleEndBlock(BB);		MadeChange \|= handleEndBlock(BB);

return MadeChange;		return MadeChange;
}		}

/// Returns true if the memory which is accessed by the store instruction is not		/// Returns true if the memory which is accessed by the second instruction is not
/// modified between the load and the store instruction.		/// modified between the first and the second instruction.
/// Precondition: The store instruction must be dominated by the load		/// Precondition: Second instruction must be dominated by the first
/// instruction.		/// instruction.
bool DSE::MemoryIsNotModifiedBetween(LoadInst LI, StoreInst SI) {		bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
		Instruction *SecondI) {
SmallVector<BasicBlock *, 16> WorkList;		SmallVector<BasicBlock *, 16> WorkList;
SmallPtrSet<BasicBlock *, 8> Visited;		SmallPtrSet<BasicBlock *, 8> Visited;
BasicBlock::iterator LoadBBI(LI);		BasicBlock::iterator FirstBBI(FirstI);
++LoadBBI;		++FirstBBI;
BasicBlock::iterator StoreBBI(SI);		BasicBlock::iterator SecondBBI(SecondI);
BasicBlock *LoadBB = LI->getParent();		BasicBlock *FirstBB = FirstI->getParent();
BasicBlock *StoreBB = SI->getParent();		BasicBlock *SecondBB = SecondI->getParent();
MemoryLocation StoreLoc = MemoryLocation::get(SI);		MemoryLocation MemLoc = MemoryLocation::get(SecondI);

// Start checking the store-block.		// Start checking the store-block.
WorkList.push_back(StoreBB);		WorkList.push_back(SecondBB);
bool isFirstBlock = true;		bool isFirstBlock = true;

// Check all blocks going backward until we reach the load-block.		// Check all blocks going backward until we reach the load-block.
while (!WorkList.empty()) {		while (!WorkList.empty()) {
BasicBlock *B = WorkList.pop_back_val();		BasicBlock *B = WorkList.pop_back_val();

// Ignore instructions before LI if this is the LoadBB.		// Ignore instructions before LI if this is the FirstBB.
BasicBlock::iterator BI = (B == LoadBB ? LoadBBI : B->begin());		BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());

BasicBlock::iterator EI;		BasicBlock::iterator EI;
if (isFirstBlock) {		if (isFirstBlock) {
// Ignore instructions after SI if this is the first visit of StoreBB.		// Ignore instructions after SI if this is the first visit of SecondBB.
assert(B == StoreBB && "first block is not the store block");		assert(B == SecondBB && "first block is not the store block");
EI = StoreBBI;		EI = SecondBBI;
isFirstBlock = false;		isFirstBlock = false;
} else {		} else {
// It's not StoreBB or (in case of a loop) the second visit of StoreBB.		// It's not SecondBB or (in case of a loop) the second visit of SecondBB.
// In this case we also have to look at instructions after SI.		// In this case we also have to look at instructions after SI.
EI = B->end();		EI = B->end();
}		}
for (; BI != EI; ++BI) {		for (; BI != EI; ++BI) {
Instruction *I = BI;		Instruction *I = BI;
if (I->mayWriteToMemory() && I != SI) {		if (I->mayWriteToMemory() && I != SecondI) {
auto Res = AA->getModRefInfo(I, StoreLoc);		auto Res = AA->getModRefInfo(I, MemLoc);
if (Res != MRI_NoModRef)		if (Res != MRI_NoModRef)
return false;		return false;
}		}
}		}
if (B != LoadBB) {		if (B != FirstBB) {
assert(B != &LoadBB->getParent()->getEntryBlock() &&		assert(B != &FirstBB->getParent()->getEntryBlock() &&
"Should not hit the entry block because SI must be dominated by LI");		"Should not hit the entry block because SI must be dominated by LI");
for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {		for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
if (!Visited.insert(*PredI).second)		if (!Visited.insert(*PredI).second)
continue;		continue;
WorkList.push_back(*PredI);		WorkList.push_back(*PredI);
}		}
}		}
}		}
▲ Show 20 Lines • Show All 246 Lines • Show Last 20 Lines