From 5e600e67b11c55c204b3eec00798badc96ed720b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 6 Dec 2008 00:53:22 +0000 Subject: [PATCH] Reimplement the inner loop of DSE. It now uniformly uses getDependence(), doesn't do its own local caching, and is slightly more aggressive about free/store dse (see testcase). This eliminates the last external client of MemDep::getDependenceFrom(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60619 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/DeadStoreElimination.cpp | 128 +++++++++---------------- test/Transforms/DeadStoreElimination/free.ll | 7 ++ 2 files changed, 51 insertions(+), 84 deletions(-) diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index fa6f10b6b99..92431c3fe31 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -50,7 +50,7 @@ namespace { bool runOnBasicBlock(BasicBlock &BB); bool handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep); bool handleEndBlock(BasicBlock &BB); - bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, + bool RemoveUndeadPointers(Value* Ptr, uint64_t killPointerSize, BasicBlock::iterator& BBI, SmallPtrSet& deadPointers); void DeleteDeadInstruction(Instruction *I, @@ -81,93 +81,60 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { MemoryDependenceAnalysis& MD = getAnalysis(); TargetData &TD = getAnalysis(); - // Record the last-seen store to this pointer - DenseMap lastStore; - bool MadeChange = false; // Do a top-down walk on the BB for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { Instruction *Inst = BBI++; - // If we find a store or a free... + // If we find a store or a free, get it's memory dependence. if (!isa(Inst) && !isa(Inst)) continue; - Value* pointer = 0; - if (StoreInst* S = dyn_cast(Inst)) { - if (S->isVolatile()) - continue; - pointer = S->getPointerOperand(); - } else { - pointer = cast(Inst)->getPointerOperand(); + MemDepResult InstDep = MD.getDependency(Inst); + + // Ignore non-local stores. + // FIXME: cross-block DSE would be fun. :) + if (InstDep.isNonLocal()) continue; + + // Handle frees whose dependencies are non-trivial. + if (FreeInst *FI = dyn_cast(Inst)) { + MadeChange |= handleFreeWithNonTrivialDependency(FI, InstDep); + continue; } - - pointer = pointer->stripPointerCasts(); - StoreInst *&last = lastStore[pointer]; - - // ... to a pointer that has been stored to before... - if (last) { - MemDepResult dep = MD.getDependency(Inst); - bool deletedStore = false; - // ... and no other memory dependencies are between them.... - while (StoreInst *DepStore = dyn_cast_or_null(dep.getInst())) { - if (DepStore != last || - TD.getTypeStoreSize(last->getOperand(0)->getType()) > - TD.getTypeStoreSize(Inst->getOperand(0)->getType())) { - dep = MD.getDependencyFrom(Inst, DepStore, DepStore->getParent()); - continue; - } - + StoreInst *SI = cast(Inst); + + // If not a definite must-alias dependency, ignore it. + if (!InstDep.isDef()) + continue; + + // If this is a store-store dependence, then the previous store is dead so + // long as this store is at least as big as it. + if (StoreInst *DepStore = dyn_cast(InstDep.getInst())) + if (TD.getTypeStoreSize(DepStore->getOperand(0)->getType()) <= + TD.getTypeStoreSize(SI->getOperand(0)->getType())) { // Delete the store and now-dead instructions that feed it. - DeleteDeadInstruction(last); + DeleteDeadInstruction(DepStore); NumFastStores++; - deletedStore = true; MadeChange = true; - break; - } - - // If we deleted a store, reinvestigate this instruction. - if (deletedStore) { + if (BBI != BB.begin()) --BBI; continue; } - } - // Handle frees whose dependencies are non-trivial. - if (FreeInst* F = dyn_cast(Inst)) { - MadeChange |= handleFreeWithNonTrivialDependency(F, MD.getDependency(F)); - - // No known stores after the free. - last = 0; - } else { - StoreInst* S = cast(Inst); - - // If we're storing the same value back to a pointer that we just - // loaded from, then the store can be removed; - if (LoadInst* L = dyn_cast(S->getOperand(0))) { - if (!S->isVolatile() && S->getParent() == L->getParent() && - S->getPointerOperand() == L->getPointerOperand()) { - MemDepResult dep = MD.getDependency(S); - if (dep.isDef() && dep.getInst() == L) { - DeleteDeadInstruction(S); - if (BBI != BB.begin()) - --BBI; - NumFastStores++; - MadeChange = true; - } else { - // Update our most-recent-store map. - last = S; - } - } else { - // Update our most-recent-store map. - last = S; - } - } else { - // Update our most-recent-store map. - last = S; + // If we're storing the same value back to a pointer that we just + // loaded from, then the store can be removed. + if (LoadInst *DepLoad = dyn_cast(InstDep.getInst())) { + if (SI->getPointerOperand() == DepLoad->getPointerOperand() && + SI->getOperand(0) == DepLoad) { + DeleteDeadInstruction(SI); + if (BBI != BB.begin()) + --BBI; + NumFastStores++; + MadeChange = true; + continue; } } } @@ -182,29 +149,22 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose /// dependency is a store to a field of that structure. -bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, MemDepResult dep) { - TargetData &TD = getAnalysis(); +bool DSE::handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep) { AliasAnalysis &AA = getAnalysis(); - StoreInst* dependency = dyn_cast_or_null(dep.getInst()); - if (!dependency) - return false; - else if (dependency->isVolatile()) + StoreInst *Dependency = dyn_cast_or_null(Dep.getInst()); + if (!Dependency || Dependency->isVolatile()) return false; - Value* depPointer = dependency->getPointerOperand(); - const Type* depType = dependency->getOperand(0)->getType(); - unsigned depPointerSize = TD.getTypeStoreSize(depType); - - // Check for aliasing - AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, - depPointer, depPointerSize); + Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject(); - if (A != AliasAnalysis::MustAlias) + // Check for aliasing. + if (AA.alias(F->getPointerOperand(), 1, DepPointer, 1) != + AliasAnalysis::MustAlias) return false; // DCE instructions only used to calculate that store - DeleteDeadInstruction(dependency); + DeleteDeadInstruction(Dependency); NumFastStores++; return true; } diff --git a/test/Transforms/DeadStoreElimination/free.ll b/test/Transforms/DeadStoreElimination/free.ll index e0611d310b8..246de9386cc 100644 --- a/test/Transforms/DeadStoreElimination/free.ll +++ b/test/Transforms/DeadStoreElimination/free.ll @@ -6,3 +6,10 @@ define void @test(i32* %Q, i32* %P) { free i32* %P ret void } + +define void @test2({i32, i32}* %P) { + %Q = getelementptr {i32, i32} *%P, i32 0, i32 1 + store i32 4, i32* %Q + free {i32,i32}* %P + ret void +} -- 2.11.0