#define DEBUG_TYPE "dse"
+STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
STATISTIC(NumFastStores, "Number of stores deleted");
STATISTIC(NumFastOther , "Number of other instrs removed");
AA = &getAnalysis<AliasAnalysis>();
MD = &getAnalysis<MemoryDependenceAnalysis>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- TLI = AA->getTargetLibraryInfo();
+ TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
}
bool runOnBasicBlock(BasicBlock &BB);
+ bool MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI);
bool HandleFree(CallInst *F);
bool handleEndBlock(BasicBlock &BB);
void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<MemoryDependenceAnalysis>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
};
-} // namespace
+}
char DSE::ID = 0;
INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
///
static void DeleteDeadInstruction(Instruction *I,
MemoryDependenceAnalysis &MD,
- const TargetLibraryInfo *TLI,
+ const TargetLibraryInfo &TLI,
SmallSetVector<Value*, 16> *ValueSet = nullptr) {
SmallVector<Instruction*, 32> NowDeadInsts;
if (!Op->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(Op))
- if (isInstructionTriviallyDead(OpI, TLI))
+ if (isInstructionTriviallyDead(OpI, &TLI))
NowDeadInsts.push_back(OpI);
}
/// hasMemoryWrite - 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) {
+static bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
if (isa<StoreInst>(I))
return true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
}
if (auto CS = CallSite(I)) {
if (Function *F = CS.getCalledFunction()) {
- if (TLI && TLI->has(LibFunc::strcpy) &&
- F->getName() == TLI->getName(LibFunc::strcpy)) {
+ if (TLI.has(LibFunc::strcpy) &&
+ F->getName() == TLI.getName(LibFunc::strcpy)) {
return true;
}
- if (TLI && TLI->has(LibFunc::strncpy) &&
- F->getName() == TLI->getName(LibFunc::strncpy)) {
+ if (TLI.has(LibFunc::strncpy) &&
+ F->getName() == TLI.getName(LibFunc::strncpy)) {
return true;
}
- if (TLI && TLI->has(LibFunc::strcat) &&
- F->getName() == TLI->getName(LibFunc::strcat)) {
+ if (TLI.has(LibFunc::strcat) &&
+ F->getName() == TLI.getName(LibFunc::strcat)) {
return true;
}
- if (TLI && TLI->has(LibFunc::strncat) &&
- F->getName() == TLI->getName(LibFunc::strncat)) {
+ if (TLI.has(LibFunc::strncat) &&
+ F->getName() == TLI.getName(LibFunc::strncat)) {
return true;
}
}
/// getLocForRead - Return the location read by the specified "hasMemoryWrite"
/// instruction if any.
-static MemoryLocation getLocForRead(Instruction *Inst, AliasAnalysis &AA) {
- assert(hasMemoryWrite(Inst, AA.getTargetLibraryInfo()) &&
- "Unknown instruction case");
+static MemoryLocation getLocForRead(Instruction *Inst,
+ const TargetLibraryInfo &TLI) {
+ assert(hasMemoryWrite(Inst, TLI) && "Unknown instruction case");
// The only instructions that both read and write are the mem transfer
// instructions (memcpy/memmove).
}
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
- const TargetLibraryInfo *TLI) {
+ const TargetLibraryInfo &TLI) {
uint64_t Size;
- if (getObjectSize(V, Size, DL, TLI))
+ if (getObjectSize(V, Size, DL, &TLI))
return Size;
return MemoryLocation::UnknownSize;
}
static OverwriteResult isOverwrite(const MemoryLocation &Later,
const MemoryLocation &Earlier,
const DataLayout &DL,
- const TargetLibraryInfo *TLI,
+ const TargetLibraryInfo &TLI,
int64_t &EarlierOff, int64_t &LaterOff) {
const Value *P1 = Earlier.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();
/// because the DSE inducing instruction may be a self-read.
static bool isPossibleSelfRead(Instruction *Inst,
const MemoryLocation &InstStoreLoc,
- Instruction *DepWrite, AliasAnalysis &AA) {
+ Instruction *DepWrite,
+ const TargetLibraryInfo &TLI,
+ AliasAnalysis &AA) {
// Self reads can only happen for instructions that read memory. Get the
// location read.
- MemoryLocation InstReadLoc = getLocForRead(Inst, AA);
+ MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
if (!InstReadLoc.Ptr) return false; // Not a reading instruction.
// If the read and written loc obviously don't alias, it isn't a read.
// Here we don't know if A/B may alias, but we do know that B/B are must
// aliases, so removing the first memcpy is safe (assuming it writes <= #
// bytes as the second one.
- MemoryLocation DepReadLoc = getLocForRead(DepWrite, AA);
+ MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
return false;
}
// If we find something that writes memory, get its memory dependence.
- if (!hasMemoryWrite(Inst, TLI))
- 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())
+ 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<StoreInst>(Inst)) {
- if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
+ if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
- SI->getOperand(0) == DepLoad && isRemovable(SI)) {
+ isRemovable(SI) &&
+ MemoryIsNotModifiedBetween(DepLoad, SI)) {
+
DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n "
<< "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n');
// in case we need it.
WeakVH NextInst(BBI);
- DeleteDeadInstruction(SI, *MD, TLI);
+ DeleteDeadInstruction(SI, *MD, *TLI);
if (!NextInst) // Next instruction deleted.
BBI = BB.begin();
else if (BBI != BB.begin()) // Revisit this instruction if possible.
--BBI;
- ++NumFastStores;
+ ++NumRedundantStores;
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);
// 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, *AA)) {
+ !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
int64_t InstWriteOffset, DepWriteOffset;
const DataLayout &DL = BB.getModule()->getDataLayout();
OverwriteResult OR =
- isOverwrite(Loc, DepLoc, DL, AA->getTargetLibraryInfo(),
- DepWriteOffset, InstWriteOffset);
+ 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);
+ DeleteDeadInstruction(DepWrite, *MD, *TLI);
++NumFastStores;
MadeChange = true;
if (DepWrite == &BB.front()) break;
// Can't look past this instruction if it might read 'Loc'.
- if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref)
+ if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref)
break;
InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB);
return MadeChange;
}
+/// Returns true if the memory which is accessed by the store instruction is not
+/// modified between the load and the store instruction.
+/// Precondition: The store instruction must be dominated by the load
+/// instruction.
+bool DSE::MemoryIsNotModifiedBetween(LoadInst *LI, StoreInst *SI) {
+ SmallVector<BasicBlock *, 16> WorkList;
+ SmallPtrSet<BasicBlock *, 8> Visited;
+ BasicBlock::iterator LoadBBI(LI);
+ ++LoadBBI;
+ BasicBlock::iterator StoreBBI(SI);
+ BasicBlock *LoadBB = LI->getParent();
+ BasicBlock *StoreBB = SI->getParent();
+ MemoryLocation StoreLoc = MemoryLocation::get(SI);
+
+ // Start checking the store-block.
+ WorkList.push_back(StoreBB);
+ bool isFirstBlock = true;
+
+ // Check all blocks going backward until we reach the load-block.
+ while (!WorkList.empty()) {
+ BasicBlock *B = WorkList.pop_back_val();
+
+ // Ignore instructions before LI if this is the LoadBB.
+ BasicBlock::iterator BI = (B == LoadBB ? LoadBBI : B->begin());
+
+ BasicBlock::iterator EI;
+ if (isFirstBlock) {
+ // Ignore instructions after SI if this is the first visit of StoreBB.
+ assert(B == StoreBB && "first block is not the store block");
+ EI = StoreBBI;
+ isFirstBlock = false;
+ } else {
+ // It's not StoreBB or (in case of a loop) the second visit of StoreBB.
+ // In this case we also have to look at instructions after SI.
+ EI = B->end();
+ }
+ for (; BI != EI; ++BI) {
+ Instruction *I = BI;
+ if (I->mayWriteToMemory() && I != SI) {
+ auto Res = AA->getModRefInfo(I, StoreLoc);
+ if (Res != MRI_NoModRef)
+ return false;
+ }
+ }
+ if (B != LoadBB) {
+ assert(B != &LoadBB->getParent()->getEntryBlock() &&
+ "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) {
+ if (!Visited.insert(*PredI).second)
+ continue;
+ WorkList.push_back(*PredI);
+ }
+ }
+ }
+ return true;
+}
+
/// Find all blocks that will unconditionally lead to the block BB and append
/// them to F.
static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
MemDepResult Dep = MD->getPointerDependencyFrom(Loc, false, InstPt, BB);
while (Dep.isDef() || Dep.isClobber()) {
Instruction *Dependency = Dep.getInst();
- if (!hasMemoryWrite(Dependency, TLI) || !isRemovable(Dependency))
+ if (!hasMemoryWrite(Dependency, *TLI) || !isRemovable(Dependency))
break;
Value *DepPointer =
Instruction *Next = std::next(BasicBlock::iterator(Dependency));
// DCE instructions only used to calculate that store
- DeleteDeadInstruction(Dependency, *MD, TLI);
+ DeleteDeadInstruction(Dependency, *MD, *TLI);
++NumFastStores;
MadeChange = true;
--BBI;
// If we find a store, check to see if it points into a dead stack value.
- if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) {
+ if (hasMemoryWrite(BBI, *TLI) && isRemovable(BBI)) {
// See through pointer-to-pointer bitcasts
SmallVector<Value *, 4> Pointers;
GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers, DL);
dbgs() << '\n');
// DCE instructions only used to calculate that store.
- DeleteDeadInstruction(Dead, *MD, TLI, &DeadStackObjects);
+ DeleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
++NumFastStores;
MadeChange = true;
continue;
// Remove any dead non-memory-mutating instructions.
if (isInstructionTriviallyDead(BBI, TLI)) {
Instruction *Inst = BBI++;
- DeleteDeadInstruction(Inst, *MD, TLI, &DeadStackObjects);
+ DeleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
++NumFastOther;
MadeChange = true;
continue;
// the call is live.
DeadStackObjects.remove_if([&](Value *I) {
// See if the call site touches the value.
- AliasAnalysis::ModRefResult A = AA->getModRefInfo(
- CS, I, getPointerSize(I, DL, AA->getTargetLibraryInfo()));
+ ModRefInfo A = AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI));
- return A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref;
+ return A == MRI_ModRef || A == MRI_Ref;
});
// If all of the allocas were clobbered by the call then we're not going
// Remove objects that could alias LoadedLoc.
DeadStackObjects.remove_if([&](Value *I) {
// See if the loaded location could alias the stack location.
- MemoryLocation StackLoc(I,
- getPointerSize(I, DL, AA->getTargetLibraryInfo()));
+ MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI));
return !AA->isNoAlias(StackLoc, LoadedLoc);
});
}