DeadStoreElimination.cpp [plain text]
#define DEBUG_TYPE "dse"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
STATISTIC(NumFastStores, "Number of stores deleted");
STATISTIC(NumFastOther , "Number of other instrs removed");
namespace {
struct DSE : public FunctionPass {
TargetData *TD;
static char ID; DSE() : FunctionPass(&ID) {}
virtual bool runOnFunction(Function &F) {
bool Changed = false;
DominatorTree &DT = getAnalysis<DominatorTree>();
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
if (DT.isReachableFromEntry(I))
Changed |= runOnBasicBlock(*I);
return Changed;
}
bool runOnBasicBlock(BasicBlock &BB);
bool handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep);
bool handleEndBlock(BasicBlock &BB);
bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
BasicBlock::iterator &BBI,
SmallPtrSet<Value*, 64> &deadPointers);
void DeleteDeadInstruction(Instruction *I,
SmallPtrSet<Value*, 64> *deadPointers = 0);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<DominatorTree>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<MemoryDependenceAnalysis>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
unsigned getPointerSize(Value *V) const;
};
}
char DSE::ID = 0;
static RegisterPass<DSE> X("dse", "Dead Store Elimination");
FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
static bool doesClobberMemory(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 bool isElidable(Instruction *I) {
assert(doesClobberMemory(I));
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
return II->getIntrinsicID() != Intrinsic::lifetime_end;
if (StoreInst *SI = dyn_cast<StoreInst>(I))
return !SI->isVolatile();
return true;
}
static Value *getPointerOperand(Instruction *I) {
assert(doesClobberMemory(I));
if (StoreInst *SI = dyn_cast<StoreInst>(I))
return SI->getPointerOperand();
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
return MI->getOperand(1);
switch (cast<IntrinsicInst>(I)->getIntrinsicID()) {
default: assert(false && "Unexpected intrinsic!");
case Intrinsic::init_trampoline:
return I->getOperand(1);
case Intrinsic::lifetime_end:
return I->getOperand(2);
}
}
static unsigned getStoreSize(Instruction *I, const TargetData *TD) {
assert(doesClobberMemory(I));
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
if (!TD) return -1u;
return TD->getTypeStoreSize(SI->getOperand(0)->getType());
}
Value *Len;
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
Len = MI->getLength();
} else {
switch (cast<IntrinsicInst>(I)->getIntrinsicID()) {
default: assert(false && "Unexpected intrinsic!");
case Intrinsic::init_trampoline:
return -1u;
case Intrinsic::lifetime_end:
Len = I->getOperand(1);
break;
}
}
if (ConstantInt *LenCI = dyn_cast<ConstantInt>(Len))
if (!LenCI->isAllOnesValue())
return LenCI->getZExtValue();
return -1u;
}
static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2,
const TargetData *TD) {
const Type *I1Ty = getPointerOperand(I1)->getType();
const Type *I2Ty = getPointerOperand(I2)->getType();
if (I1Ty == I2Ty) return true;
int I1Size = getStoreSize(I1, TD);
int I2Size = getStoreSize(I2, TD);
return I1Size != -1 && I2Size != -1 && I1Size >= I2Size;
}
bool DSE::runOnBasicBlock(BasicBlock &BB) {
MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
TD = getAnalysisIfAvailable<TargetData>();
bool MadeChange = false;
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
Instruction *Inst = BBI++;
if (!doesClobberMemory(Inst) && !isFreeCall(Inst))
continue;
MemDepResult InstDep = MD.getDependency(Inst);
if (InstDep.isNonLocal()) continue;
if (isFreeCall(Inst)) {
MadeChange |= handleFreeWithNonTrivialDependency(Inst, InstDep);
continue;
}
if (!InstDep.isDef())
continue;
if (doesClobberMemory(InstDep.getInst())) {
Instruction *DepStore = InstDep.getInst();
if (isStoreAtLeastAsWideAs(Inst, DepStore, TD) &&
isElidable(DepStore)) {
DeleteDeadInstruction(DepStore);
NumFastStores++;
MadeChange = true;
BBI = Inst;
if (BBI != BB.begin())
--BBI;
continue;
}
}
if (!isElidable(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) {
WeakVH NextInst(BBI);
DeleteDeadInstruction(SI);
if (NextInst == 0) BBI = BB.begin();
else if (BBI != BB.begin()) --BBI;
NumFastStores++;
MadeChange = true;
continue;
}
}
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(InstDep.getInst())) {
if (II->getIntrinsicID() == Intrinsic::lifetime_end) {
WeakVH NextInst(BBI);
DeleteDeadInstruction(Inst);
if (NextInst == 0) BBI = BB.begin();
else if (BBI != BB.begin()) --BBI;
NumFastStores++;
MadeChange = true;
continue;
}
}
}
if (BB.getTerminator()->getNumSuccessors() == 0)
MadeChange |= handleEndBlock(BB);
return MadeChange;
}
bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Instruction *Dependency = Dep.getInst();
if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency))
return false;
Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
if (AA.alias(F->getOperand(1), 1, DepPointer, 1) !=
AliasAnalysis::MustAlias)
return false;
DeleteDeadInstruction(Dependency);
NumFastStores++;
return true;
}
bool DSE::handleEndBlock(BasicBlock &BB) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
bool MadeChange = false;
SmallPtrSet<Value*, 64> deadPointers;
BasicBlock *Entry = BB.getParent()->begin();
for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
deadPointers.insert(AI);
for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
AE = BB.getParent()->arg_end(); AI != AE; ++AI)
if (AI->hasByValAttr())
deadPointers.insert(AI);
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
--BBI;
if (doesClobberMemory(BBI)) {
if (isElidable(BBI)) {
Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject();
if (deadPointers.count(pointerOperand)) {
Instruction *Dead = BBI;
BBI++;
DeleteDeadInstruction(Dead, &deadPointers);
NumFastStores++;
MadeChange = true;
continue;
}
}
if (!isa<MemTransferInst>(BBI))
continue;
}
Value *killPointer = 0;
uint64_t killPointerSize = ~0UL;
if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
if (L->use_empty() && !L->isVolatile()) {
BBI++;
DeleteDeadInstruction(L, &deadPointers);
NumFastOther++;
MadeChange = true;
continue;
}
killPointer = L->getPointerOperand();
} else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
killPointer = V->getOperand(0);
} else if (isa<MemTransferInst>(BBI) &&
isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) {
killPointer = cast<MemTransferInst>(BBI)->getSource();
killPointerSize = cast<ConstantInt>(
cast<MemTransferInst>(BBI)->getLength())->getZExtValue();
} else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
deadPointers.erase(A);
if (A->use_empty()) {
BBI++;
DeleteDeadInstruction(A, &deadPointers);
NumFastOther++;
MadeChange = true;
}
continue;
} else if (CallSite::get(BBI).getInstruction() != 0) {
CallSite CS = CallSite::get(BBI);
if (AA.doesNotAccessMemory(CS))
continue;
unsigned modRef = 0;
unsigned other = 0;
std::vector<Value*> dead;
for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
E = deadPointers.end(); I != E; ++I) {
if (modRef >= 16 && other == 0) {
deadPointers.clear();
return MadeChange;
}
AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I,
getPointerSize(*I));
if (A == AliasAnalysis::ModRef)
modRef++;
else
other++;
if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
dead.push_back(*I);
}
for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
I != E; ++I)
deadPointers.erase(*I);
continue;
} else if (isInstructionTriviallyDead(BBI)) {
Instruction *Inst = BBI;
BBI++;
DeleteDeadInstruction(Inst, &deadPointers);
NumFastOther++;
MadeChange = true;
continue;
}
if (!killPointer)
continue;
killPointer = killPointer->getUnderlyingObject();
MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
deadPointers);
}
return MadeChange;
}
bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
BasicBlock::iterator &BBI,
SmallPtrSet<Value*, 64> &deadPointers) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
if (deadPointers.count(killPointer)) {
deadPointers.erase(killPointer);
return false;
}
if (isa<GlobalValue>(killPointer))
return false;
bool MadeChange = false;
SmallVector<Value*, 16> undead;
for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
E = deadPointers.end(); I != E; ++I) {
AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I),
killPointer, killPointerSize);
if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
StoreInst *S = cast<StoreInst>(BBI);
++BBI;
DeleteDeadInstruction(S, &deadPointers);
NumFastStores++;
MadeChange = true;
continue;
} else if (A != AliasAnalysis::NoAlias)
undead.push_back(*I);
}
for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end();
I != E; ++I)
deadPointers.erase(*I);
return MadeChange;
}
void DSE::DeleteDeadInstruction(Instruction *I,
SmallPtrSet<Value*, 64> *ValueSet) {
SmallVector<Instruction*, 32> NowDeadInsts;
NowDeadInsts.push_back(I);
--NumFastOther;
MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
do {
Instruction *DeadInst = NowDeadInsts.pop_back_val();
++NumFastOther;
MDA.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());
}
unsigned DSE::getPointerSize(Value *V) const {
if (TD) {
if (AllocaInst *A = dyn_cast<AllocaInst>(V)) {
if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize()))
return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType());
} else {
assert(isa<Argument>(V) && "Expected AllocaInst or Argument!");
const PointerType *PT = cast<PointerType>(V->getType());
return TD->getTypeAllocSize(PT->getElementType());
}
}
return ~0U;
}