TargetData *TD;
static char ID; // Pass identification, replacement for typeid
- DSE() : FunctionPass(&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)
- Changed |= runOnBasicBlock(*I);
+ // Only check non-dead blocks. Dead blocks may have strange pointer
+ // cycles that will confuse alias analysis.
+ if (DT.isReachableFromEntry(I))
+ Changed |= runOnBasicBlock(*I);
return Changed;
}
bool runOnBasicBlock(BasicBlock &BB);
- bool handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep);
+ bool handleFreeWithNonTrivialDependency(const CallInst *F,
+ MemDepResult Dep);
bool handleEndBlock(BasicBlock &BB);
- bool RemoveUndeadPointers(Value* Ptr, uint64_t killPointerSize,
- BasicBlock::iterator& BBI,
- SmallPtrSet<Value*, 64>& deadPointers);
+ bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
+ BasicBlock::iterator &BBI,
+ SmallPtrSet<Value*, 64> &deadPointers);
void DeleteDeadInstruction(Instruction *I,
SmallPtrSet<Value*, 64> *deadPointers = 0);
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");
+INITIALIZE_PASS(DSE, "dse", "Dead Store Elimination", false, false);
FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
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::lifetime_end: return true;
+ default:
+ return false;
+ case Intrinsic::memset:
+ case Intrinsic::memmove:
+ case Intrinsic::memcpy:
+ case Intrinsic::init_trampoline:
+ case Intrinsic::lifetime_end:
+ return true;
}
}
return false;
}
-/// isElidable - If the memory this instruction and the memory it writes to is
+/// isElidable - If the value of this instruction and the memory it writes to is
/// unused, may we delete this instrtction?
static bool isElidable(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);
- assert(cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::lifetime_end);
- return cast<IntrinsicInst>(I)->getOperand(2);
+ return MI->getArgOperand(0);
+
+ IntrinsicInst *II = cast<IntrinsicInst>(I);
+ switch (II->getIntrinsicID()) {
+ default: assert(false && "Unexpected intrinsic!");
+ case Intrinsic::init_trampoline:
+ return II->getArgOperand(0);
+ case Intrinsic::lifetime_end:
+ return II->getArgOperand(1);
+ }
}
/// getStoreSize - Return the length in bytes of the write by the clobbering
assert(doesClobberMemory(I));
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
if (!TD) return -1u;
- const PointerType *PTy =
- cast<PointerType>(SI->getPointerOperand()->getType());
- return TD->getTypeStoreSize(PTy->getElementType());
+ return TD->getTypeStoreSize(SI->getOperand(0)->getType());
}
Value *Len;
Len = MI->getLength();
} else {
IntrinsicInst *II = cast<IntrinsicInst>(I);
- assert(II->getIntrinsicID() == Intrinsic::lifetime_end);
- Len = II->getOperand(0);
+ switch (II->getIntrinsicID()) {
+ default: assert(false && "Unexpected intrinsic!");
+ case Intrinsic::init_trampoline:
+ return -1u;
+ case Intrinsic::lifetime_end:
+ Len = II->getArgOperand(0);
+ break;
+ }
}
if (ConstantInt *LenCI = dyn_cast<ConstantInt>(Len))
if (!LenCI->isAllOnesValue())
}
bool DSE::runOnBasicBlock(BasicBlock &BB) {
- MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+ MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
TD = getAnalysisIfAvailable<TargetData>();
bool MadeChange = false;
if (InstDep.isNonLocal()) continue;
// Handle frees whose dependencies are non-trivial.
- if (isFreeCall(Inst)) {
- MadeChange |= handleFreeWithNonTrivialDependency(Inst, InstDep);
+ if (const CallInst *F = isFreeCall(Inst)) {
+ MadeChange |= handleFreeWithNonTrivialDependency(F, InstDep);
continue;
}
isElidable(DepStore)) {
// Delete the store and now-dead instructions that feed it.
DeleteDeadInstruction(DepStore);
- NumFastStores++;
+ ++NumFastStores;
MadeChange = true;
// DeleteDeadInstruction can delete the current instruction in loop
BBI = BB.begin();
else if (BBI != BB.begin()) // Revisit this instruction if possible.
--BBI;
- NumFastStores++;
+ ++NumFastStores;
MadeChange = true;
continue;
}
BBI = BB.begin();
else if (BBI != BB.begin()) // Revisit this instruction if possible.
--BBI;
- NumFastStores++;
+ ++NumFastStores;
MadeChange = true;
continue;
}
/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
/// dependency is a store to a field of that structure.
-bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) {
+bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F,
+ MemDepResult Dep) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Instruction *Dependency = Dep.getInst();
Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
// Check for aliasing.
- if (AA.alias(F->getOperand(1), 1, DepPointer, 1) !=
+ if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) !=
AliasAnalysis::MustAlias)
return false;
// DCE instructions only used to calculate that store
DeleteDeadInstruction(Dependency);
- NumFastStores++;
+ ++NumFastStores;
return true;
}
if (deadPointers.count(pointerOperand)) {
// DCE instructions only used to calculate that store.
Instruction *Dead = BBI;
- BBI++;
+ ++BBI;
DeleteDeadInstruction(Dead, &deadPointers);
- NumFastStores++;
+ ++NumFastStores;
MadeChange = true;
continue;
}
continue;
}
- Value* killPointer = 0;
+ Value *killPointer = 0;
uint64_t killPointerSize = ~0UL;
// If we encounter a use of the pointer, it is no longer considered dead
// However, if this load is unused and not volatile, we can go ahead and
// remove it, and not have to worry about it making our pointer undead!
if (L->use_empty() && !L->isVolatile()) {
- BBI++;
+ ++BBI;
DeleteDeadInstruction(L, &deadPointers);
- NumFastOther++;
+ ++NumFastOther;
MadeChange = true;
continue;
}
killPointer = L->getPointerOperand();
- } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) {
+ } 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)) {
+ } else if (AllocaInst
*A = dyn_cast<AllocaInst>(BBI)) {
deadPointers.erase(A);
// Dead alloca's can be DCE'd when we reach them
if (A->use_empty()) {
- BBI++;
+ ++BBI;
DeleteDeadInstruction(A, &deadPointers);
- NumFastOther++;
+ ++NumFastOther;
MadeChange = true;
}
continue;
- } else if (CallSite::get(BBI).getInstruction() != 0) {
+ } else if (CallSite CS = cast<Value>(BBI)) {
// If this call does not access memory, it can't
// be undeadifying any of our pointers.
- CallSite CS = CallSite::get(BBI);
if (AA.doesNotAccessMemory(CS))
continue;
deadPointers.clear();
return MadeChange;
}
-
- // Get size information for the alloca
- unsigned pointerSize = ~0U;
- if (TD) {
- if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
- if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
- pointerSize = C->getZExtValue() *
- TD->getTypeAllocSize(A->getAllocatedType());
- } else {
- const PointerType* PT = cast<PointerType>(
- cast<Argument>(*I)->getType());
- pointerSize = TD->getTypeAllocSize(PT->getElementType());
- }
- }
-
+
// See if the call site touches it
- AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize);
+ AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I,
+ getPointerSize(*I));
if (A == AliasAnalysis::ModRef)
- modRef++;
+ ++modRef;
else
- other++;
+ ++other;
if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
dead.push_back(*I);
} else if (isInstructionTriviallyDead(BBI)) {
// For any non-memory-affecting non-terminators, DCE them as we reach them
Instruction *Inst = BBI;
- BBI++;
+ ++BBI;
DeleteDeadInstruction(Inst, &deadPointers);
- NumFastOther++;
+ ++NumFastOther;
MadeChange = true;
continue;
}
/// RemoveUndeadPointers - check for uses of a pointer that make it
/// undead when scanning for dead stores to alloca's.
-bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize,
+bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
BasicBlock::iterator &BBI,
- SmallPtrSet<Value*, 64>& deadPointers) {
+ SmallPtrSet<Value*, 64> &deadPointers) {
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
-
+
// If the kill pointer can be easily reduced to an alloca,
// don't bother doing extraneous AA queries.
if (deadPointers.count(killPointer)) {
bool MadeChange = false;
SmallVector<Value*, 16> undead;
-
+
for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
- E = deadPointers.end(); I != E; ++I) {
- // Get size information for the alloca.
- unsigned pointerSize = ~0U;
- if (TD) {
- if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
- if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
- pointerSize = C->getZExtValue() *
- TD->getTypeAllocSize(A->getAllocatedType());
- } else {
- const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType());
- pointerSize = TD->getTypeAllocSize(PT->getElementType());
- }
- }
-
+ E = deadPointers.end(); I != E; ++I) {
// See if this pointer could alias it
- AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize,
+ AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I),
killPointer, killPointerSize);
// If it must-alias and a store, we can delete it
if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
- StoreInst* S = cast<StoreInst>(BBI);
+ StoreInst *S = cast<StoreInst>(BBI);
// Remove it!
- BBI++;
+ ++BBI;
DeleteDeadInstruction(S, &deadPointers);
- NumFastStores++;
+ ++NumFastStores;
MadeChange = true;
continue;
// Before we touch this instruction, remove it from memdep!
MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
- while (!NowDeadInsts.empty()) {
- Instruction *DeadInst = NowDeadInsts.back();
- NowDeadInsts.pop_back();
+ do {
+ Instruction *DeadInst = NowDeadInsts.pop_back_val();
++NumFastOther;
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)) {
+ // Get size information for the alloca
+ 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;
}
projects / oota-llvm.git / blobdiff