X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FDeadStoreElimination.cpp;h=09c01d314124e65ff3c7767db50d7f99eeb93ee9;hb=040056fd11693ffc41ce9b777281c71705d0dc1f;hp=c10d236cda60789ab937c4bea88a19561feaa36a;hpb=046e78ce55a7c3d82b7b6758d2d77f2d99f970bf;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index c10d236cda6..09c01d31412 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -26,7 +26,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/MallocHelper.h" +#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/Local.h" @@ -44,17 +44,23 @@ namespace { virtual bool runOnFunction(Function &F) { bool Changed = false; + + DominatorTree &DT = getAnalysis(); + 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 handleEndBlock(BasicBlock &BB); - bool RemoveUndeadPointers(Value* Ptr, uint64_t killPointerSize, - BasicBlock::iterator& BBI, - SmallPtrSet& deadPointers); + bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize, + BasicBlock::iterator &BBI, + SmallPtrSet &deadPointers); void DeleteDeadInstruction(Instruction *I, SmallPtrSet *deadPointers = 0); @@ -70,6 +76,8 @@ namespace { AU.addPreserved(); AU.addPreserved(); } + + unsigned getPointerSize(Value *V) const; }; } @@ -78,8 +86,102 @@ static RegisterPass X("dse", "Dead Store Elimination"); FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } +/// doesClobberMemory - Does this instruction clobber (write without reading) +/// some memory? +static bool doesClobberMemory(Instruction *I) { + if (isa(I)) + return true; + if (IntrinsicInst *II = dyn_cast(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; +} + +/// 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 (IntrinsicInst *II = dyn_cast(I)) + return II->getIntrinsicID() != Intrinsic::lifetime_end; + if (StoreInst *SI = dyn_cast(I)) + return !SI->isVolatile(); + return true; +} + +/// getPointerOperand - Return the pointer that is being clobbered. +static Value *getPointerOperand(Instruction *I) { + assert(doesClobberMemory(I)); + if (StoreInst *SI = dyn_cast(I)) + return SI->getPointerOperand(); + if (MemIntrinsic *MI = dyn_cast(I)) + return MI->getOperand(1); + + switch (cast(I)->getIntrinsicID()) { + default: assert(false && "Unexpected intrinsic!"); + case Intrinsic::init_trampoline: + return I->getOperand(1); + case Intrinsic::lifetime_end: + return I->getOperand(2); + } +} + +/// getStoreSize - Return the length in bytes of the write by the clobbering +/// instruction. If variable or unknown, returns -1. +static unsigned getStoreSize(Instruction *I, const TargetData *TD) { + assert(doesClobberMemory(I)); + if (StoreInst *SI = dyn_cast(I)) { + if (!TD) return -1u; + return TD->getTypeStoreSize(SI->getOperand(0)->getType()); + } + + Value *Len; + if (MemIntrinsic *MI = dyn_cast(I)) { + Len = MI->getLength(); + } else { + switch (cast(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(Len)) + if (!LenCI->isAllOnesValue()) + return LenCI->getZExtValue(); + return -1u; +} + +/// isStoreAtLeastAsWideAs - Return true if the size of the store in I1 is +/// greater than or equal to the store in I2. This returns false if we don't +/// know. +/// +static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, + const TargetData *TD) { + const Type *I1Ty = getPointerOperand(I1)->getType(); + const Type *I2Ty = getPointerOperand(I2)->getType(); + + // Exactly the same type, must have exactly the same size. + 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 &MD = getAnalysis(); TD = getAnalysisIfAvailable(); bool MadeChange = false; @@ -89,14 +191,9 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { Instruction *Inst = BBI++; // If we find a store or a free, get its memory dependence. - if (!isa(Inst) && !isFreeCall(Inst)) + if (!doesClobberMemory(Inst) && !isFreeCall(Inst)) continue; - // Don't molest volatile stores or do queries that will return "clobber". - if (StoreInst *SI = dyn_cast(Inst)) - if (SI->isVolatile()) - continue; - MemDepResult InstDep = MD.getDependency(Inst); // Ignore non-local stores. @@ -109,18 +206,16 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { 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())) { + if (doesClobberMemory(InstDep.getInst())) { + Instruction *DepStore = InstDep.getInst(); + if (isStoreAtLeastAsWideAs(Inst, DepStore, TD) && + isElidable(DepStore)) { // Delete the store and now-dead instructions that feed it. DeleteDeadInstruction(DepStore); NumFastStores++; @@ -133,17 +228,43 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { --BBI; continue; } + } + + if (!isElidable(Inst)) + continue; // 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) { + if (StoreInst *SI = dyn_cast(Inst)) { + 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); + + 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; + } + } + } + + // If this is a lifetime end marker, we can throw away the store. + if (IntrinsicInst *II = dyn_cast(InstDep.getInst())) { + if (II->getIntrinsicID() == Intrinsic::lifetime_end) { + // Delete the store and now-dead instructions that feed it. // DeleteDeadInstruction can delete the current instruction. Save BBI // in case we need it. WeakVH NextInst(BBI); - DeleteDeadInstruction(SI); + DeleteDeadInstruction(Inst); if (NextInst == 0) // Next instruction deleted. BBI = BB.begin(); @@ -169,11 +290,11 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) { AliasAnalysis &AA = getAnalysis(); - StoreInst *Dependency = dyn_cast_or_null(Dep.getInst()); - if (!Dependency || Dependency->isVolatile()) + Instruction *Dependency = Dep.getInst(); + if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency)) return false; - Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject(); + Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); // Check for aliasing. if (AA.alias(F->getOperand(1), 1, DepPointer, 1) != @@ -218,42 +339,31 @@ bool DSE::handleEndBlock(BasicBlock &BB) { --BBI; // If we find a store whose pointer is dead. - if (StoreInst* S = dyn_cast(BBI)) { - if (!S->isVolatile()) { + if (doesClobberMemory(BBI)) { + if (isElidable(BBI)) { // See through pointer-to-pointer bitcasts - Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); + Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject(); // Alloca'd pointers or byval arguments (which are functionally like // alloca's) are valid candidates for removal. if (deadPointers.count(pointerOperand)) { // DCE instructions only used to calculate that store. + Instruction *Dead = BBI; BBI++; - DeleteDeadInstruction(S, &deadPointers); + DeleteDeadInstruction(Dead, &deadPointers); NumFastStores++; MadeChange = true; + continue; } } - continue; - } - - // We can also remove memcpy's to local variables at the end of a function. - if (MemCpyInst *M = dyn_cast(BBI)) { - Value *dest = M->getDest()->getUnderlyingObject(); - - if (deadPointers.count(dest)) { - BBI++; - DeleteDeadInstruction(M, &deadPointers); - NumFastOther++; - MadeChange = true; + // Because a memcpy or memmove is also a load, we can't skip it if we + // didn't remove it. + if (!isa(BBI)) continue; - } - - // Because a memcpy is also a load, we can't skip it if we didn't remove - // it. } - Value* killPointer = 0; + Value *killPointer = 0; uint64_t killPointerSize = ~0UL; // If we encounter a use of the pointer, it is no longer considered dead @@ -269,14 +379,14 @@ bool DSE::handleEndBlock(BasicBlock &BB) { } killPointer = L->getPointerOperand(); - } else if (VAArgInst* V = dyn_cast(BBI)) { + } else if (VAArgInst *V = dyn_cast(BBI)) { killPointer = V->getOperand(0); - } else if (isa(BBI) && - isa(cast(BBI)->getLength())) { - killPointer = cast(BBI)->getSource(); + } else if (isa(BBI) && + isa(cast(BBI)->getLength())) { + killPointer = cast(BBI)->getSource(); killPointerSize = cast( - cast(BBI)->getLength())->getZExtValue(); - } else if (AllocaInst* A = dyn_cast(BBI)) { + cast(BBI)->getLength())->getZExtValue(); + } else if (AllocaInst *A = dyn_cast(BBI)) { deadPointers.erase(A); // Dead alloca's can be DCE'd when we reach them @@ -310,23 +420,10 @@ bool DSE::handleEndBlock(BasicBlock &BB) { deadPointers.clear(); return MadeChange; } - - // Get size information for the alloca - unsigned pointerSize = ~0U; - 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 - AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); + AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, + getPointerSize(*I)); if (A == AliasAnalysis::ModRef) modRef++; @@ -367,11 +464,11 @@ bool DSE::handleEndBlock(BasicBlock &BB) { /// 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& deadPointers) { + SmallPtrSet &deadPointers) { AliasAnalysis &AA = getAnalysis(); - + // If the kill pointer can be easily reduced to an alloca, // don't bother doing extraneous AA queries. if (deadPointers.count(killPointer)) { @@ -386,32 +483,19 @@ bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, bool MadeChange = false; SmallVector undead; - + for (SmallPtrSet::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(*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()); - } - } - + 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(BBI) && A == AliasAnalysis::MustAlias) { - StoreInst* S = cast(BBI); + StoreInst *S = cast(BBI); // Remove it! - BBI++; + ++BBI; DeleteDeadInstruction(S, &deadPointers); NumFastStores++; MadeChange = true; @@ -445,9 +529,8 @@ void DSE::DeleteDeadInstruction(Instruction *I, // Before we touch this instruction, remove it from memdep! MemoryDependenceAnalysis &MDA = getAnalysis(); - while (!NowDeadInsts.empty()) { - Instruction *DeadInst = NowDeadInsts.back(); - NowDeadInsts.pop_back(); + do { + Instruction *DeadInst = NowDeadInsts.pop_back_val(); ++NumFastOther; @@ -471,5 +554,20 @@ void DSE::DeleteDeadInstruction(Instruction *I, DeadInst->eraseFromParent(); if (ValueSet) ValueSet->erase(DeadInst); + } while (!NowDeadInsts.empty()); +} + +unsigned DSE::getPointerSize(Value *V) const { + if (TD) { + if (AllocaInst *A = dyn_cast(V)) { + // Get size information for the alloca + if (ConstantInt *C = dyn_cast(A->getArraySize())) + return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); + } else { + assert(isa(V) && "Expected AllocaInst or Argument!"); + const PointerType *PT = cast(V->getType()); + return TD->getTypeAllocSize(PT->getElementType()); + } } + return ~0U; }