X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FDeadStoreElimination.cpp;h=a7b3e7524fa2bf1a4c514cdac03910d6a36d82ba;hb=40ef630a4626365faeef8696f611e18d1a69f63a;hp=8217a44c6f4b40f49847d688044fbf1f86627361;hpb=39f372e23e49cecb8db2eb7120eb331173e50c74;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index 8217a44c6f4..a7b3e7524fa 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -29,14 +29,15 @@ #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/Local.h" -#include "llvm/Support/Compiler.h" using namespace llvm; STATISTIC(NumFastStores, "Number of stores deleted"); STATISTIC(NumFastOther , "Number of other instrs removed"); namespace { - struct VISIBILITY_HIDDEN DSE : public FunctionPass { + struct DSE : public FunctionPass { + TargetData *TD; + static char ID; // Pass identification, replacement for typeid DSE() : FunctionPass(&ID) {} @@ -47,12 +48,10 @@ namespace { return Changed; } - typedef MemoryDependenceAnalysis::DepResultTy DepResultTy; - bool runOnBasicBlock(BasicBlock &BB); - bool handleFreeWithNonTrivialDependency(FreeInst *F, DepResultTy Dep); + 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, @@ -64,7 +63,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); - AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addPreserved(); @@ -81,97 +79,79 @@ FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } bool DSE::runOnBasicBlock(BasicBlock &BB) { MemoryDependenceAnalysis& MD = getAnalysis(); - TargetData &TD = getAnalysis(); + TD = getAnalysisIfAvailable(); - // Record the last-seen store to this pointer - DenseMap lastStore; - bool MadeChange = false; - // Do a top-down walk on the BB + // 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 its memory dependence. if (!isa(Inst) && !isa(Inst)) continue; - - Value* pointer = 0; - if (StoreInst* S = dyn_cast(Inst)) { - if (S->isVolatile()) + + // Don't molest volatile stores or do queries that will return "clobber". + if (StoreInst *SI = dyn_cast(Inst)) + if (SI->isVolatile()) continue; - pointer = S->getPointerOperand(); - } else { - pointer = cast(Inst)->getPointerOperand(); - } - pointer = pointer->stripPointerCasts(); - StoreInst *&last = lastStore[pointer]; - - // ... to a pointer that has been stored to before... - if (last) { - DepResultTy dep = MD.getDependency(Inst); - bool deletedStore = false; + MemDepResult InstDep = MD.getDependency(Inst); - // ... and no other memory dependencies are between them.... - while (dep.getInt() == MemoryDependenceAnalysis::Normal && - isa(dep.getPointer())) { - if (dep.getPointer() != last || - TD.getTypeStoreSize(last->getOperand(0)->getType()) > - TD.getTypeStoreSize(Inst->getOperand(0)->getType())) { - dep = MD.getDependency(Inst, dep.getPointer()); - continue; - } - + // 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; + } + + 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 && + 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 (!isa(BB.begin())) + + // DeleteDeadInstruction can delete the current instruction in loop + // cases, reset BBI. + BBI = Inst; + 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))) { - // FIXME: Don't do dep query if Parents don't match and other stuff! - DepResultTy dep = MD.getDependency(S); - DominatorTree& DT = getAnalysis(); + // 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 can delete the current instruction. Save BBI + // in case we need it. + WeakVH NextInst(BBI); - if (!S->isVolatile() && S->getParent() == L->getParent() && - S->getPointerOperand() == L->getPointerOperand() && - (dep.getInt() == MemoryDependenceAnalysis::None || - dep.getInt() == MemoryDependenceAnalysis::NonLocal || - DT.dominates(dep.getPointer(), L))) { - - DeleteDeadInstruction(S); - if (!isa(BB.begin())) - --BBI; - NumFastStores++; - MadeChange = true; - } else - // Update our most-recent-store map. - last = S; - } else - // Update our most-recent-store map. - last = S; + DeleteDeadInstruction(SI); + + if (NextInst == 0) // Next instruction deleted. + BBI = BB.begin(); + else if (BBI != BB.begin()) // Revisit this instruction if possible. + --BBI; + NumFastStores++; + MadeChange = true; + continue; + } } } @@ -185,33 +165,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, DepResultTy dep) { - TargetData &TD = getAnalysis(); +bool DSE::handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep) { AliasAnalysis &AA = getAnalysis(); - if (dep.getInt() == MemoryDependenceAnalysis::None || - dep.getInt() == MemoryDependenceAnalysis::NonLocal) + StoreInst *Dependency = dyn_cast_or_null(Dep.getInst()); + if (!Dependency || Dependency->isVolatile()) return false; - StoreInst* dependency = dyn_cast(dep.getPointer()); - if (!dependency) - return false; - else if (dependency->isVolatile()) - return false; - - Value* depPointer = dependency->getPointerOperand(); - const Type* depType = dependency->getOperand(0)->getType(); - unsigned depPointerSize = TD.getTypeStoreSize(depType); + Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject(); - // Check for aliasing - AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, - depPointer, depPointerSize); - - 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; } @@ -223,7 +192,6 @@ bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, DepResultTy dep) { /// store i32 1, i32* %A /// ret void bool DSE::handleEndBlock(BasicBlock &BB) { - TargetData &TD = getAnalysis(); AliasAnalysis &AA = getAnalysis(); bool MadeChange = false; @@ -344,14 +312,16 @@ bool DSE::handleEndBlock(BasicBlock &BB) { // Get size information for the alloca unsigned pointerSize = ~0U; - if (AllocaInst* A = dyn_cast(*I)) { - if (ConstantInt* C = dyn_cast(A->getArraySize())) - pointerSize = C->getZExtValue() * - TD.getABITypeSize(A->getAllocatedType()); - } else { - const PointerType* PT = cast( - cast(*I)->getType()); - pointerSize = TD.getABITypeSize(PT->getElementType()); + if (TD) { + if (AllocaInst* A = dyn_cast(*I)) { + if (ConstantInt* C = dyn_cast(A->getArraySize())) + pointerSize = C->getZExtValue() * + TD->getTypeAllocSize(A->getAllocatedType()); + } else { + const PointerType* PT = cast( + cast(*I)->getType()); + pointerSize = TD->getTypeAllocSize(PT->getElementType()); + } } // See if the call site touches it @@ -399,7 +369,6 @@ bool DSE::handleEndBlock(BasicBlock &BB) { bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, BasicBlock::iterator &BBI, SmallPtrSet& deadPointers) { - TargetData &TD = getAnalysis(); AliasAnalysis &AA = getAnalysis(); // If the kill pointer can be easily reduced to an alloca, @@ -421,13 +390,15 @@ bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, E = deadPointers.end(); I != E; ++I) { // Get size information for the alloca. unsigned pointerSize = ~0U; - if (AllocaInst* A = dyn_cast(*I)) { - if (ConstantInt* C = dyn_cast(A->getArraySize())) - pointerSize = C->getZExtValue() * - TD.getABITypeSize(A->getAllocatedType()); - } else { - const PointerType* PT = cast(cast(*I)->getType()); - pointerSize = TD.getABITypeSize(PT->getElementType()); + if (TD) { + if (AllocaInst* A = dyn_cast(*I)) { + if (ConstantInt* C = dyn_cast(A->getArraySize())) + pointerSize = C->getZExtValue() * + TD->getTypeAllocSize(A->getAllocatedType()); + } else { + const PointerType* PT = cast(cast(*I)->getType()); + pointerSize = TD->getTypeAllocSize(PT->getElementType()); + } } // See if this pointer could alias it