DeadStoreElimination.cpp [plain text]
#define DEBUG_TYPE "dse"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
using namespace llvm;
STATISTIC(NumFastStores, "Number of stores deleted");
STATISTIC(NumFastOther , "Number of other instrs removed");
namespace {
struct DSE : public FunctionPass {
AliasAnalysis *AA;
MemoryDependenceAnalysis *MD;
DominatorTree *DT;
static char ID; DSE() : FunctionPass(ID), AA(0), MD(0), DT(0) {
initializeDSEPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnFunction(Function &F) {
AA = &getAnalysis<AliasAnalysis>();
MD = &getAnalysis<MemoryDependenceAnalysis>();
DT = &getAnalysis<DominatorTree>();
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
if (DT->isReachableFromEntry(I))
Changed |= runOnBasicBlock(*I);
AA = 0; MD = 0; DT = 0;
return Changed;
}
bool runOnBasicBlock(BasicBlock &BB);
bool HandleFree(CallInst *F);
bool handleEndBlock(BasicBlock &BB);
void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc,
SmallPtrSet<Value*, 16> &DeadStackObjects);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<DominatorTree>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<MemoryDependenceAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
};
}
char DSE::ID = 0;
INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
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,
SmallPtrSet<Value*, 16> *ValueSet = 0) {
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, 0);
if (!Op->use_empty()) continue;
if (Instruction *OpI = dyn_cast<Instruction>(Op))
if (isInstructionTriviallyDead(OpI))
NowDeadInsts.push_back(OpI);
}
DeadInst->eraseFromParent();
if (ValueSet) ValueSet->erase(DeadInst);
} while (!NowDeadInsts.empty());
}
static bool hasMemoryWrite(Instruction *I) {
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;
}
}
return false;
}
static AliasAnalysis::Location
getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
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 && AA.getTargetData() == 0)
return AliasAnalysis::Location();
return Loc;
}
IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
if (II == 0) return AliasAnalysis::Location();
switch (II->getIntrinsicID()) {
default: return AliasAnalysis::Location(); case Intrinsic::init_trampoline:
if (AA.getTargetData() == 0) 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) && "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();
IntrinsicInst *II = 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();
}
}
static bool isShortenable(Instruction *I) {
if (isa<StoreInst>(I))
return false;
IntrinsicInst *II = cast<IntrinsicInst>(I);
switch (II->getIntrinsicID()) {
default: return false;
case Intrinsic::memset:
case Intrinsic::memcpy:
return true;
}
}
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();
IntrinsicInst *II = cast<IntrinsicInst>(I);
switch (II->getIntrinsicID()) {
default: llvm_unreachable("Unexpected intrinsic!");
case Intrinsic::init_trampoline:
return II->getArgOperand(0);
}
}
static uint64_t getPointerSize(const Value *V, AliasAnalysis &AA) {
const TargetData *TD = AA.getTargetData();
if (const CallInst *CI = extractMallocCall(V)) {
if (const ConstantInt *C = dyn_cast<ConstantInt>(CI->getArgOperand(0)))
return C->getZExtValue();
}
if (TD == 0)
return AliasAnalysis::UnknownSize;
if (const AllocaInst *A = dyn_cast<AllocaInst>(V)) {
if (const ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize()))
return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType());
}
if (const Argument *A = dyn_cast<Argument>(V)) {
if (A->hasByValAttr())
if (PointerType *PT = dyn_cast<PointerType>(A->getType()))
return TD->getTypeAllocSize(PT->getElementType());
}
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
if (!GV->mayBeOverridden())
return TD->getTypeAllocSize(GV->getType()->getElementType());
}
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 Value *P1 = Earlier.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();
if (P1 == P2) {
if (Later.Size == AliasAnalysis::UnknownSize ||
Earlier.Size == AliasAnalysis::UnknownSize) {
if (AA.getTargetData() == 0 &&
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 ||
AA.getTargetData() == 0)
return OverwriteUnknown;
const TargetData &TD = *AA.getTargetData();
const Value *UO1 = GetUnderlyingObject(P1, &TD),
*UO2 = GetUnderlyingObject(P2, &TD);
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, TD);
const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD);
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 == 0) 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)) {
MadeChange |= HandleFree(F);
continue;
}
if (!hasMemoryWrite(Inst))
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);
if (NextInst == 0) BBI = BB.begin();
else if (BBI != BB.begin()) --BBI;
++NumFastStores;
MadeChange = true;
continue;
}
}
}
AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA);
if (Loc.Ptr == 0)
continue;
while (InstDep.isDef() || InstDep.isClobber()) {
Instruction *DepWrite = InstDep.getInst();
AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA);
if (DepLoc.Ptr == 0)
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);
++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) || !isRemovable(Dependency))
break;
Value *DepPointer =
GetUnderlyingObject(getStoredPointerOperand(Dependency));
if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
break;
Instruction *Next = llvm::next(BasicBlock::iterator(Dependency));
DeleteDeadInstruction(Dependency, *MD);
++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;
SmallPtrSet<Value*, 16> DeadStackObjects;
BasicBlock *Entry = BB.getParent()->begin();
for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) {
if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
DeadStackObjects.insert(AI);
if (CallInst *CI = extractMallocCall(I))
if (!PointerMayBeCaptured(CI, true, true))
DeadStackObjects.insert(CI);
}
for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
AE = BB.getParent()->arg_end(); AI != AE; ++AI)
if (AI->hasByValAttr())
DeadStackObjects.insert(AI);
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
--BBI;
if (hasMemoryWrite(BBI) && isRemovable(BBI)) {
Value *Pointer = GetUnderlyingObject(getStoredPointerOperand(BBI));
if (DeadStackObjects.count(Pointer)) {
Instruction *Dead = BBI++;
DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Object: " << *Pointer << '\n');
DeleteDeadInstruction(Dead, *MD, &DeadStackObjects);
++NumFastStores;
MadeChange = true;
continue;
}
}
if (isInstructionTriviallyDead(BBI)) {
Instruction *Inst = BBI++;
DeleteDeadInstruction(Inst, *MD, &DeadStackObjects);
++NumFastOther;
MadeChange = true;
continue;
}
if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
DeadStackObjects.erase(A);
continue;
}
if (CallInst *CI = extractMallocCall(BBI)) {
DeadStackObjects.erase(CI);
continue;
}
if (CallSite CS = cast<Value>(BBI)) {
if (AA->doesNotAccessMemory(CS))
continue;
SmallVector<Value*, 8> LiveAllocas;
for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(),
E = DeadStackObjects.end(); I != E; ++I) {
AliasAnalysis::ModRefResult A =
AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA));
if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
LiveAllocas.push_back(*I);
}
for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(),
E = LiveAllocas.end(); I != E; ++I)
DeadStackObjects.erase(*I);
if (DeadStackObjects.empty())
return MadeChange;
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,
SmallPtrSet<Value*, 16> &DeadStackObjects) {
const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr);
if (isa<Constant>(UnderlyingPointer))
return;
if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
DeadStackObjects.erase(const_cast<Value*>(UnderlyingPointer));
return;
}
SmallVector<Value*, 16> NowLive;
for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(),
E = DeadStackObjects.end(); I != E; ++I) {
AliasAnalysis::Location StackLoc(*I, getPointerSize(*I, *AA));
if (!AA->isNoAlias(StackLoc, LoadedLoc))
NowLive.push_back(*I);
}
for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end();
I != E; ++I)
DeadStackObjects.erase(*I);
}