DeadStoreElimination.cpp [plain text]
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
#define DEBUG_TYPE "dse"
STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
STATISTIC(NumFastStores, "Number of stores deleted");
STATISTIC(NumFastOther , "Number of other instrs removed");
namespace {
struct DSE : public FunctionPass {
AliasAnalysis *AA;
MemoryDependenceAnalysis *MD;
DominatorTree *DT;
const TargetLibraryInfo *TLI;
static char ID; DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) {
initializeDSEPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override {
if (skipOptnoneFunction(F))
return false;
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
MD = &getAnalysis<MemoryDependenceAnalysis>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
bool Changed = false;
for (BasicBlock &I : F)
if (DT->isReachableFromEntry(&I))
Changed |= runOnBasicBlock(I);
AA = nullptr; MD = nullptr; DT = nullptr;
return Changed;
}
bool runOnBasicBlock(BasicBlock &BB);
bool MemoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI);
bool HandleFree(CallInst *F);
bool handleEndBlock(BasicBlock &BB);
void RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
SmallSetVector<Value *, 16> &DeadStackObjects,
const DataLayout &DL);
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<MemoryDependenceAnalysis>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
};
}
char DSE::ID = 0;
INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
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,
SmallSetVector<Value*, 16> *ValueSet = nullptr) {
SmallVector<Instruction*, 32> NowDeadInsts;
NowDeadInsts.push_back(I);
--NumFastOther;
do {
Instruction *DeadInst = NowDeadInsts.pop_back_val();
++NumFastOther;
MD.removeInstruction(DeadInst);
for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
Value *Op = DeadInst->getOperand(op);
DeadInst->setOperand(op, nullptr);
if (!Op->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(Op))
if (isInstructionTriviallyDead(OpI, &TLI))
NowDeadInsts.push_back(OpI);
}
DeadInst->eraseFromParent();
if (ValueSet) ValueSet->remove(DeadInst);
} while (!NowDeadInsts.empty());
}
static bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo &TLI) {
if (isa<StoreInst>(I))
return true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default:
return false;
case Intrinsic::memset:
case Intrinsic::memmove:
case Intrinsic::memcpy:
case Intrinsic::init_trampoline:
case Intrinsic::lifetime_end:
return true;
}
}
if (auto CS = CallSite(I)) {
if (Function *F = CS.getCalledFunction()) {
if (TLI.has(LibFunc::strcpy) &&
F->getName() == TLI.getName(LibFunc::strcpy)) {
return true;
}
if (TLI.has(LibFunc::strncpy) &&
F->getName() == TLI.getName(LibFunc::strncpy)) {
return true;
}
if (TLI.has(LibFunc::strcat) &&
F->getName() == TLI.getName(LibFunc::strcat)) {
return true;
}
if (TLI.has(LibFunc::strncat) &&
F->getName() == TLI.getName(LibFunc::strncat)) {
return true;
}
}
}
return false;
}
static MemoryLocation getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
return MemoryLocation::get(SI);
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) {
MemoryLocation Loc = MemoryLocation::getForDest(MI);
return Loc;
}
IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
if (!II)
return MemoryLocation();
switch (II->getIntrinsicID()) {
default:
return MemoryLocation(); case Intrinsic::init_trampoline:
return MemoryLocation(II->getArgOperand(0));
case Intrinsic::lifetime_end: {
uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
return MemoryLocation(II->getArgOperand(1), Len);
}
}
}
static MemoryLocation getLocForRead(Instruction *Inst,
const TargetLibraryInfo &TLI) {
assert(hasMemoryWrite(Inst, TLI) && "Unknown instruction case");
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst))
return MemoryLocation::getForSource(MTI);
return MemoryLocation();
}
static bool isRemovable(Instruction *I) {
if (StoreInst *SI = dyn_cast<StoreInst>(I))
return SI->isUnordered();
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate");
case Intrinsic::lifetime_end:
return false;
case Intrinsic::init_trampoline:
return true;
case Intrinsic::memset:
case Intrinsic::memmove:
case Intrinsic::memcpy:
return !cast<MemIntrinsic>(II)->isVolatile();
}
}
if (auto CS = CallSite(I))
return CS.getInstruction()->use_empty();
return false;
}
static bool isShortenable(Instruction *I) {
if (isa<StoreInst>(I))
return false;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: return false;
case Intrinsic::memset:
case Intrinsic::memcpy:
return true;
}
}
return false;
}
static Value *getStoredPointerOperand(Instruction *I) {
if (StoreInst *SI = dyn_cast<StoreInst>(I))
return SI->getPointerOperand();
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
return MI->getDest();
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: llvm_unreachable("Unexpected intrinsic!");
case Intrinsic::init_trampoline:
return II->getArgOperand(0);
}
}
CallSite CS(I);
return CS.getArgument(0);
}
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
const TargetLibraryInfo &TLI) {
uint64_t Size;
if (getObjectSize(V, Size, DL, &TLI))
return Size;
return MemoryLocation::UnknownSize;
}
namespace {
enum OverwriteResult
{
OverwriteComplete,
OverwriteEnd,
OverwriteUnknown
};
}
static OverwriteResult isOverwrite(const MemoryLocation &Later,
const MemoryLocation &Earlier,
const DataLayout &DL,
const TargetLibraryInfo &TLI,
int64_t &EarlierOff, int64_t &LaterOff) {
const Value *P1 = Earlier.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();
if (P1 == P2) {
if (Later.Size == MemoryLocation::UnknownSize ||
Earlier.Size == MemoryLocation::UnknownSize)
return OverwriteUnknown;
if (Later.Size >= Earlier.Size)
return OverwriteComplete;
}
if (Later.Size == MemoryLocation::UnknownSize ||
Earlier.Size == MemoryLocation::UnknownSize)
return OverwriteUnknown;
const Value *UO1 = GetUnderlyingObject(P1, DL),
*UO2 = GetUnderlyingObject(P2, DL);
if (UO1 != UO2)
return OverwriteUnknown;
uint64_t ObjectSize = getPointerSize(UO2, DL, TLI);
if (ObjectSize != MemoryLocation::UnknownSize)
if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size)
return OverwriteComplete;
EarlierOff = 0;
LaterOff = 0;
const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
if (BP1 != BP2)
return OverwriteUnknown;
if (EarlierOff >= LaterOff &&
Later.Size >= Earlier.Size &&
uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
return OverwriteComplete;
if (LaterOff > EarlierOff &&
LaterOff < int64_t(EarlierOff + Earlier.Size) &&
int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size))
return OverwriteEnd;
return OverwriteUnknown;
}
static bool isPossibleSelfRead(Instruction *Inst,
const MemoryLocation &InstStoreLoc,
Instruction *DepWrite,
const TargetLibraryInfo &TLI,
AliasAnalysis &AA) {
MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
if (!InstReadLoc.Ptr) return false;
if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false;
MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
return false;
return true;
}
bool DSE::runOnBasicBlock(BasicBlock &BB) {
const DataLayout &DL = BB.getModule()->getDataLayout();
bool MadeChange = false;
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
Instruction *Inst = &*BBI++;
if (CallInst *F = isFreeCall(Inst, TLI)) {
MadeChange |= HandleFree(F);
continue;
}
if (!hasMemoryWrite(Inst, *TLI))
continue;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
auto RemoveDeadInstAndUpdateBBI = [&](Instruction *DeadInst) {
WeakVH NextInst(&*BBI);
DeleteDeadInstruction(DeadInst, *MD, *TLI);
if (!NextInst) BBI = BB.begin();
else if (BBI != BB.begin()) --BBI;
++NumRedundantStores;
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;
}
}
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;
}
}
}
MemDepResult InstDep = MD->getDependency(Inst);
if (!InstDep.isDef() && !InstDep.isClobber())
continue;
MemoryLocation Loc = getLocForWrite(Inst, *AA);
if (!Loc.Ptr)
continue;
while (InstDep.isDef() || InstDep.isClobber()) {
Instruction *DepWrite = InstDep.getInst();
MemoryLocation DepLoc = getLocForWrite(DepWrite, *AA);
if (!DepLoc.Ptr)
break;
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);
++NumFastStores;
MadeChange = true;
BBI = Inst->getIterator();
if (BBI != BB.begin())
--BBI;
break;
} else if (OR == OverwriteEnd && isShortenable(DepWrite)) {
MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite);
unsigned DepWriteAlign = DepIntrinsic->getAlignment();
if (llvm::isPowerOf2_64(InstWriteOffset) ||
((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) {
DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW END: "
<< *DepWrite << "\n KILLER (offset "
<< InstWriteOffset << ", "
<< DepLoc.Size << ")"
<< *Inst << '\n');
Value* DepWriteLength = DepIntrinsic->getLength();
Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(),
InstWriteOffset -
DepWriteOffset);
DepIntrinsic->setLength(TrimmedLength);
MadeChange = true;
}
}
}
if (DepWrite == &BB.front()) break;
if (AA->getModRefInfo(DepWrite, Loc) & MRI_Ref)
break;
InstDep = MD->getPointerDependencyFrom(Loc, false,
DepWrite->getIterator(), &BB);
}
}
if (BB.getTerminator()->getNumSuccessors() == 0)
MadeChange |= handleEndBlock(BB);
return MadeChange;
}
bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI,
Instruction *SecondI) {
SmallVector<BasicBlock *, 16> WorkList;
SmallPtrSet<BasicBlock *, 8> Visited;
BasicBlock::iterator FirstBBI(FirstI);
++FirstBBI;
BasicBlock::iterator SecondBBI(SecondI);
BasicBlock *FirstBB = FirstI->getParent();
BasicBlock *SecondBB = SecondI->getParent();
MemoryLocation MemLoc = MemoryLocation::get(SecondI);
WorkList.push_back(SecondBB);
bool isFirstBlock = true;
while (!WorkList.empty()) {
BasicBlock *B = WorkList.pop_back_val();
BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
BasicBlock::iterator EI;
if (isFirstBlock) {
assert(B == SecondBB && "first block is not the store block");
EI = SecondBBI;
isFirstBlock = false;
} else {
EI = B->end();
}
for (; BI != EI; ++BI) {
Instruction *I = &*BI;
if (I->mayWriteToMemory() && I != SecondI) {
auto Res = AA->getModRefInfo(I, MemLoc);
if (Res != MRI_NoModRef)
return false;
}
}
if (B != FirstBB) {
assert(B != &FirstBB->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;
}
static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
BasicBlock *BB, DominatorTree *DT) {
for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
BasicBlock *Pred = *I;
if (Pred == BB) continue;
TerminatorInst *PredTI = Pred->getTerminator();
if (PredTI->getNumSuccessors() != 1)
continue;
if (DT->isReachableFromEntry(Pred))
Blocks.push_back(Pred);
}
}
bool DSE::HandleFree(CallInst *F) {
bool MadeChange = false;
MemoryLocation Loc = MemoryLocation(F->getOperand(0));
SmallVector<BasicBlock *, 16> Blocks;
Blocks.push_back(F->getParent());
const DataLayout &DL = F->getModule()->getDataLayout();
while (!Blocks.empty()) {
BasicBlock *BB = Blocks.pop_back_val();
Instruction *InstPt = BB->getTerminator();
if (BB == F->getParent()) InstPt = F;
MemDepResult Dep =
MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
while (Dep.isDef() || Dep.isClobber()) {
Instruction *Dependency = Dep.getInst();
if (!hasMemoryWrite(Dependency, *TLI) || !isRemovable(Dependency))
break;
Value *DepPointer =
GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);
if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
break;
auto Next = ++Dependency->getIterator();
DeleteDeadInstruction(Dependency, *MD, *TLI);
++NumFastStores;
MadeChange = true;
Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB);
}
if (Dep.isNonLocal())
FindUnconditionalPreds(Blocks, BB, DT);
}
return MadeChange;
}
bool DSE::handleEndBlock(BasicBlock &BB) {
bool MadeChange = false;
SmallSetVector<Value*, 16> DeadStackObjects;
BasicBlock &Entry = BB.getParent()->front();
for (Instruction &I : Entry) {
if (isa<AllocaInst>(&I))
DeadStackObjects.insert(&I);
else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
DeadStackObjects.insert(&I);
}
for (Argument &AI : BB.getParent()->args())
if (AI.hasByValOrInAllocaAttr())
DeadStackObjects.insert(&AI);
const DataLayout &DL = BB.getModule()->getDataLayout();
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
--BBI;
if (hasMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
SmallVector<Value *, 4> Pointers;
GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);
bool AllDead = true;
for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
E = Pointers.end(); I != E; ++I)
if (!DeadStackObjects.count(*I)) {
AllDead = false;
break;
}
if (AllDead) {
Instruction *Dead = &*BBI++;
DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: ";
for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(),
E = Pointers.end(); I != E; ++I) {
dbgs() << **I;
if (std::next(I) != E)
dbgs() << ", ";
}
dbgs() << '\n');
DeleteDeadInstruction(Dead, *MD, *TLI, &DeadStackObjects);
++NumFastStores;
MadeChange = true;
continue;
}
}
if (isInstructionTriviallyDead(&*BBI, TLI)) {
Instruction *Inst = &*BBI++;
DeleteDeadInstruction(Inst, *MD, *TLI, &DeadStackObjects);
++NumFastOther;
MadeChange = true;
continue;
}
if (isa<AllocaInst>(BBI)) {
DeadStackObjects.remove(&*BBI);
continue;
}
if (auto CS = CallSite(&*BBI)) {
if (isAllocLikeFn(&*BBI, TLI))
DeadStackObjects.remove(&*BBI);
if (AA->doesNotAccessMemory(CS))
continue;
DeadStackObjects.remove_if([&](Value *I) {
ModRefInfo A = AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI));
return A == MRI_ModRef || A == MRI_Ref;
});
if (DeadStackObjects.empty())
break;
continue;
}
MemoryLocation LoadedLoc;
if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
if (!L->isUnordered()) break;
LoadedLoc = MemoryLocation::get(L);
} else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
LoadedLoc = MemoryLocation::get(V);
} else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
LoadedLoc = MemoryLocation::getForSource(MTI);
} else if (!BBI->mayReadFromMemory()) {
continue;
} else {
break;
}
RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL);
if (DeadStackObjects.empty())
break;
}
return MadeChange;
}
void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc,
SmallSetVector<Value *, 16> &DeadStackObjects,
const DataLayout &DL) {
const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);
if (isa<Constant>(UnderlyingPointer))
return;
if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
return;
}
DeadStackObjects.remove_if([&](Value *I) {
MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI));
return !AA->isNoAlias(StackLoc, LoadedLoc);
});
}