X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FDeadStoreElimination.cpp;h=09c01d314124e65ff3c7767db50d7f99eeb93ee9;hb=040056fd11693ffc41ce9b777281c71705d0dc1f;hp=c66db5e27217199c93d16177012ba276519e84c2;hpb=e3f749b166be81544d364756032421e8c834a079;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index c66db5e2721..09c01d31412 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -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; }; } @@ -85,9 +93,14 @@ static bool doesClobberMemory(Instruction *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; + default: + return false; + case Intrinsic::memset: + case Intrinsic::memmove: + case Intrinsic::memcpy: + case Intrinsic::init_trampoline: + case Intrinsic::lifetime_end: + return true; } } return false; @@ -111,14 +124,13 @@ static Value *getPointerOperand(Instruction *I) { return SI->getPointerOperand(); if (MemIntrinsic *MI = dyn_cast(I)) return MI->getOperand(1); - IntrinsicInst *II = cast(I); - switch (II->getIntrinsicID()) { - default: - assert(false && "Unexpected intrinsic!"); - case Intrinsic::init_trampoline: - return II->getOperand(1); - case Intrinsic::lifetime_end: - return II->getOperand(2); + + 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); } } @@ -135,14 +147,13 @@ static unsigned getStoreSize(Instruction *I, const TargetData *TD) { if (MemIntrinsic *MI = dyn_cast(I)) { Len = MI->getLength(); } else { - IntrinsicInst *II = cast(I); - switch (II->getIntrinsicID()) { - default: - assert(false && "Unexpected intrinsic!"); - case Intrinsic::init_trampoline: - return -1u; - case Intrinsic::lifetime_end: - Len = II->getOperand(1); + 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)) @@ -170,7 +181,7 @@ static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, } bool DSE::runOnBasicBlock(BasicBlock &BB) { - MemoryDependenceAnalysis& MD = getAnalysis(); + MemoryDependenceAnalysis &MD = getAnalysis(); TD = getAnalysisIfAvailable(); bool MadeChange = false; @@ -352,7 +363,7 @@ bool DSE::handleEndBlock(BasicBlock &BB) { 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 @@ -368,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(); killPointerSize = cast( cast(BBI)->getLength())->getZExtValue(); - } else if (AllocaInst* A = dyn_cast(BBI)) { + } else if (AllocaInst *A = dyn_cast(BBI)) { deadPointers.erase(A); // Dead alloca's can be DCE'd when we reach them @@ -409,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++; @@ -466,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)) { @@ -485,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; @@ -544,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; @@ -570,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; }