diff options
author | Nick Lewycky <nicholas@mxc.ca> | 2011-11-05 10:48:42 +0000 |
---|---|---|
committer | Nick Lewycky <nicholas@mxc.ca> | 2011-11-05 10:48:42 +0000 |
commit | 336b88dac8054d6ed6cda6d6198b7d4bb026b3e1 (patch) | |
tree | 4e80528d8c3de8610e00ce96e8dc26b972fb4a06 /lib/Transforms/Scalar/DeadStoreElimination.cpp | |
parent | c09b770c13594ce6fd91820b31f934aadddc1bcd (diff) | |
download | external_llvm-336b88dac8054d6ed6cda6d6198b7d4bb026b3e1.zip external_llvm-336b88dac8054d6ed6cda6d6198b7d4bb026b3e1.tar.gz external_llvm-336b88dac8054d6ed6cda6d6198b7d4bb026b3e1.tar.bz2 |
Do simple cross-block DSE when we encounter a free statement. Fixes PR11240.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143808 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Scalar/DeadStoreElimination.cpp')
-rw-r--r-- | lib/Transforms/Scalar/DeadStoreElimination.cpp | 81 |
1 files changed, 56 insertions, 25 deletions
diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index c0738a9..f114418 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -34,6 +34,7 @@ #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"); @@ -43,25 +44,26 @@ namespace { struct DSE : public FunctionPass { AliasAnalysis *AA; MemoryDependenceAnalysis *MD; + DominatorTree *DT; static char ID; // Pass identification, replacement for typeid - DSE() : FunctionPass(ID), AA(0), MD(0) { + DSE() : FunctionPass(ID), AA(0), MD(0), DT(0) { initializeDSEPass(*PassRegistry::getPassRegistry()); } virtual bool runOnFunction(Function &F) { AA = &getAnalysis<AliasAnalysis>(); MD = &getAnalysis<MemoryDependenceAnalysis>(); - DominatorTree &DT = getAnalysis<DominatorTree>(); + DT = &getAnalysis<DominatorTree>(); bool Changed = false; for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) // Only check non-dead blocks. Dead blocks may have strange pointer // cycles that will confuse alias analysis. - if (DT.isReachableFromEntry(I)) + if (DT->isReachableFromEntry(I)) Changed |= runOnBasicBlock(*I); - AA = 0; MD = 0; + AA = 0; MD = 0; DT = 0; return Changed; } @@ -549,37 +551,66 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { return MadeChange; } +/// Find all blocks that will unconditionally lead to the block BB and append +/// them to F. +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; + TerminatorInst *PredTI = Pred->getTerminator(); + if (PredTI->getNumSuccessors() != 1) + continue; + + if (DT->isReachableFromEntry(Pred)) + Blocks.push_back(Pred); + } +} + /// HandleFree - Handle frees of entire structures whose dependency is a store /// to a field of that structure. bool DSE::HandleFree(CallInst *F) { bool MadeChange = false; - MemDepResult Dep = MD->getDependency(F); + 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; - while (Dep.isDef() || Dep.isClobber()) { - Instruction *Dependency = Dep.getInst(); - if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) - return MadeChange; + Value *DepPointer = + GetUnderlyingObject(getStoredPointerOperand(Dependency)); - Value *DepPointer = - GetUnderlyingObject(getStoredPointerOperand(Dependency)); + // Check for aliasing. + if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) + break; - // Check for aliasing. - if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) - return MadeChange; + Instruction *Next = llvm::next(BasicBlock::iterator(Dependency)); - // DCE instructions only used to calculate that store - DeleteDeadInstruction(Dependency, *MD); - ++NumFastStores; - MadeChange = true; + // DCE instructions only used to calculate that store + DeleteDeadInstruction(Dependency, *MD); + ++NumFastStores; + MadeChange = true; - // Inst's old Dependency is now deleted. Compute the next dependency, - // which may also be dead, as in - // s[0] = 0; - // s[1] = 0; // This has just been deleted. - // free(s); - Dep = MD->getDependency(F); - }; + // Inst's old Dependency is now deleted. Compute the next dependency, + // which may also be dead, as in + // s[0] = 0; + // s[1] = 0; // This has just been deleted. + // free(s); + Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB); + } + + if (Dep.isNonLocal()) + FindUnconditionalPreds(Blocks, BB, DT); + } return MadeChange; } |