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/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.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/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
#define DEBUG_TYPE "dse"
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<AliasAnalysis>();
MD = &getAnalysis<MemoryDependenceAnalysis>();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
TLI = AA->getTargetLibraryInfo();
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
if (DT->isReachableFromEntry(I))
Changed |= runOnBasicBlock(*I);
AA = nullptr; MD = nullptr; DT = nullptr;
return Changed;
}
bool runOnBasicBlock(BasicBlock &BB);
bool HandleFree(CallInst *F);
bool handleEndBlock(BasicBlock &BB);
void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc,
SmallSetVector<Value*, 16> &DeadStackObjects);
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<MemoryDependenceAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
};
}
char DSE::ID = 0;
INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
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 (CallSite CS = I) {
if (Function *F = CS.getCalledFunction()) {
if (TLI && TLI->has(LibFunc::strcpy) &&
F->getName() == TLI->getName(LibFunc::strcpy)) {
return true;
}
if (TLI && TLI->has(LibFunc::strncpy) &&
F->getName() == TLI->getName(LibFunc::strncpy)) {
return true;
}
if (TLI && TLI->has(LibFunc::strcat) &&
F->getName() == TLI->getName(LibFunc::strcat)) {
return true;
}
if (TLI && TLI->has(LibFunc::strncat) &&
F->getName() == TLI->getName(LibFunc::strncat)) {
return true;
}
}
}
return false;
}
static AliasAnalysis::Location
getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
const DataLayout *DL = AA.getDataLayout();
if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
return AA.getLocation(SI);
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) {
AliasAnalysis::Location Loc = AA.getLocationForDest(MI);
if (Loc.Size == AliasAnalysis::UnknownSize && DL == nullptr)
return AliasAnalysis::Location();
return Loc;
}
IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
if (!II) return AliasAnalysis::Location();
switch (II->getIntrinsicID()) {
default: return AliasAnalysis::Location(); case Intrinsic::init_trampoline:
if (!DL) return AliasAnalysis::Location();
return AliasAnalysis::Location(II->getArgOperand(0));
case Intrinsic::lifetime_end: {
uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
return AliasAnalysis::Location(II->getArgOperand(1), Len);
}
}
}
static AliasAnalysis::Location
getLocForRead(Instruction *Inst, AliasAnalysis &AA) {
assert(hasMemoryWrite(Inst, AA.getTargetLibraryInfo()) &&
"Unknown instruction case");
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst))
return AA.getLocationForSource(MTI);
return AliasAnalysis::Location();
}
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 (CallSite CS = 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, AliasAnalysis &AA) {
uint64_t Size;
if (getObjectSize(V, Size, AA.getDataLayout(), AA.getTargetLibraryInfo()))
return Size;
return AliasAnalysis::UnknownSize;
}
namespace {
enum OverwriteResult
{
OverwriteComplete,
OverwriteEnd,
OverwriteUnknown
};
}
static OverwriteResult isOverwrite(const AliasAnalysis::Location &Later,
const AliasAnalysis::Location &Earlier,
AliasAnalysis &AA,
int64_t &EarlierOff,
int64_t &LaterOff) {
const DataLayout *DL = AA.getDataLayout();
const Value *P1 = Earlier.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();
if (P1 == P2) {
if (Later.Size == AliasAnalysis::UnknownSize ||
Earlier.Size == AliasAnalysis::UnknownSize) {
if (DL == nullptr && Later.Ptr->getType() == Earlier.Ptr->getType())
return OverwriteComplete;
return OverwriteUnknown;
}
if (Later.Size >= Earlier.Size)
return OverwriteComplete;
}
if (Later.Size == AliasAnalysis::UnknownSize ||
Earlier.Size == AliasAnalysis::UnknownSize || DL == nullptr)
return OverwriteUnknown;
const Value *UO1 = GetUnderlyingObject(P1, DL),
*UO2 = GetUnderlyingObject(P2, DL);
if (UO1 != UO2)
return OverwriteUnknown;
uint64_t ObjectSize = getPointerSize(UO2, AA);
if (ObjectSize != AliasAnalysis::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 AliasAnalysis::Location &InstStoreLoc,
Instruction *DepWrite, AliasAnalysis &AA) {
AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA);
if (!InstReadLoc.Ptr) return false;
if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false;
AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA);
if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
return false;
return true;
}
bool DSE::runOnBasicBlock(BasicBlock &BB) {
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;
MemDepResult InstDep = MD->getDependency(Inst);
if (!InstDep.isDef() && !InstDep.isClobber())
continue;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
SI->getOperand(0) == DepLoad && isRemovable(SI)) {
DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n "
<< "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n');
WeakVH NextInst(BBI);
DeleteDeadInstruction(SI, *MD, TLI);
if (!NextInst) BBI = BB.begin();
else if (BBI != BB.begin()) --BBI;
++NumFastStores;
MadeChange = true;
continue;
}
}
}
AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA);
if (!Loc.Ptr)
continue;
while (InstDep.isDef() || InstDep.isClobber()) {
Instruction *DepWrite = InstDep.getInst();
AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA);
if (!DepLoc.Ptr)
break;
if (isRemovable(DepWrite) &&
!isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) {
int64_t InstWriteOffset, DepWriteOffset;
OverwriteResult OR = isOverwrite(Loc, DepLoc, *AA,
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;
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) & AliasAnalysis::Ref)
break;
InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB);
}
}
if (BB.getTerminator()->getNumSuccessors() == 0)
MadeChange |= handleEndBlock(BB);
return MadeChange;
}
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;
AliasAnalysis::Location Loc = AliasAnalysis::Location(F->getOperand(0));
SmallVector<BasicBlock *, 16> Blocks;
Blocks.push_back(F->getParent());
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, BB);
while (Dep.isDef() || Dep.isClobber()) {
Instruction *Dependency = Dep.getInst();
if (!hasMemoryWrite(Dependency, TLI) || !isRemovable(Dependency))
break;
Value *DepPointer =
GetUnderlyingObject(getStoredPointerOperand(Dependency));
if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
break;
Instruction *Next = std::next(BasicBlock::iterator(Dependency));
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()->begin();
for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) {
if (isa<AllocaInst>(I))
DeadStackObjects.insert(I);
else if (isAllocLikeFn(I, TLI) && !PointerMayBeCaptured(I, true, true))
DeadStackObjects.insert(I);
}
for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
AE = BB.getParent()->arg_end(); AI != AE; ++AI)
if (AI->hasByValOrInAllocaAttr())
DeadStackObjects.insert(AI);
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
--BBI;
if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) {
SmallVector<Value *, 4> Pointers;
GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers);
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 (CallSite CS = cast<Value>(BBI)) {
if (isAllocLikeFn(BBI, TLI))
DeadStackObjects.remove(BBI);
if (AA->doesNotAccessMemory(CS))
continue;
DeadStackObjects.remove_if([&](Value *I) {
AliasAnalysis::ModRefResult A =
AA->getModRefInfo(CS, I, getPointerSize(I, *AA));
return A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref;
});
if (DeadStackObjects.empty())
break;
continue;
}
AliasAnalysis::Location LoadedLoc;
if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
if (!L->isUnordered()) break;
LoadedLoc = AA->getLocation(L);
} else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
LoadedLoc = AA->getLocation(V);
} else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
LoadedLoc = AA->getLocationForSource(MTI);
} else if (!BBI->mayReadFromMemory()) {
continue;
} else {
break;
}
RemoveAccessedObjects(LoadedLoc, DeadStackObjects);
if (DeadStackObjects.empty())
break;
}
return MadeChange;
}
void DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc,
SmallSetVector<Value*, 16> &DeadStackObjects) {
const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr);
if (isa<Constant>(UnderlyingPointer))
return;
if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer));
return;
}
DeadStackObjects.remove_if([&](Value *I) {
AliasAnalysis::Location StackLoc(I, getPointerSize(I, *AA));
return !AA->isNoAlias(StackLoc, LoadedLoc);
});
}