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/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"
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;
static char ID; DSE() : FunctionPass(ID), AA(0), MD(0) {
initializeDSEPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnFunction(Function &F) {
AA = &getAnalysis<AliasAnalysis>();
MD = &getAnalysis<MemoryDependenceAnalysis>();
DominatorTree &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;
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->isVolatile();
IntrinsicInst *II = cast<IntrinsicInst>(I);
switch (II->getIntrinsicID()) {
default: assert(0 && "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 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: assert(false && "Unexpected intrinsic!");
case Intrinsic::init_trampoline:
return II->getArgOperand(0);
}
}
static uint64_t getPointerSize(Value *V, AliasAnalysis &AA) {
const TargetData *TD = AA.getTargetData();
if (TD == 0)
return AliasAnalysis::UnknownSize;
if (AllocaInst *A = dyn_cast<AllocaInst>(V)) {
if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize()))
return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType());
return AliasAnalysis::UnknownSize;
}
assert(isa<Argument>(V) && "Expected AllocaInst or Argument!");
const PointerType *PT = cast<PointerType>(V->getType());
return TD->getTypeAllocSize(PT->getElementType());
}
static bool isObjectPointerWithTrustworthySize(const Value *V) {
if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
return !AI->isArrayAllocation();
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
return !GV->mayBeOverridden();
if (const Argument *A = dyn_cast<Argument>(V))
return A->hasByValAttr();
return false;
}
static bool isCompleteOverwrite(const AliasAnalysis::Location &Later,
const AliasAnalysis::Location &Earlier,
AliasAnalysis &AA) {
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)
return Later.Ptr->getType() == Earlier.Ptr->getType();
return false;
}
if (Later.Size < Earlier.Size)
return false;
return true;
}
if (Later.Size == AliasAnalysis::UnknownSize ||
Earlier.Size == AliasAnalysis::UnknownSize ||
Later.Size <= Earlier.Size || AA.getTargetData() == 0)
return false;
const TargetData &TD = *AA.getTargetData();
const Value *UO1 = GetUnderlyingObject(P1, &TD),
*UO2 = GetUnderlyingObject(P2, &TD);
if (UO1 != UO2)
return false;
if (isObjectPointerWithTrustworthySize(UO2)) {
uint64_t ObjectSize =
TD.getTypeAllocSize(cast<PointerType>(UO2->getType())->getElementType());
if (ObjectSize == Later.Size)
return true;
}
int64_t EarlierOff = 0, LaterOff = 0;
const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, TD);
const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD);
if (BP1 != BP2)
return false;
if (EarlierOff >= LaterOff &&
uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
return true;
return false;
}
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.isNonLocal() ||
InstDep.getInst() == Inst)
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 && !SI->isVolatile()) {
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.isNonLocal()) {
Instruction *DepWrite = InstDep.getInst();
AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA);
if (DepLoc.Ptr == 0)
break;
if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, *AA) &&
!isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) {
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;
}
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;
}
bool DSE::HandleFree(CallInst *F) {
MemDepResult Dep = MD->getDependency(F);
do {
if (Dep.isNonLocal()) return false;
Instruction *Dependency = Dep.getInst();
if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency))
return false;
Value *DepPointer =
GetUnderlyingObject(getStoredPointerOperand(Dependency));
if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
return false;
DeleteDeadInstruction(Dependency, *MD);
++NumFastStores;
Dep = MD->getDependency(F);
} while (!Dep.isNonLocal());
return true;
}
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);
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 (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)) {
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 {
continue;
}
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);
}