X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FDeadStoreElimination.cpp;h=c8fd9d9fa5561b487f0b0f95cd9c7f4f5f539e25;hb=9ccaf53ada99c63737547c0235baeb8454b04e80;hp=a85cf7b28b54a28e524e346cbed2443885353865;hpb=58571d663c8c7d57fae1054d21686d8c8a7c8a7a;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index a85cf7b28b5..c8fd9d9fa55 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -40,21 +40,28 @@ namespace { TargetData *TD; static char ID; // Pass identification, replacement for typeid - DSE() : FunctionPass(&ID) {} + DSE() : FunctionPass(ID) {} 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 handleFreeWithNonTrivialDependency(const CallInst *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); @@ -67,14 +74,15 @@ namespace { AU.addRequired(); AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); } + + unsigned getPointerSize(Value *V) const; }; } char DSE::ID = 0; -static RegisterPass X("dse", "Dead Store Elimination"); +INITIALIZE_PASS(DSE, "dse", "Dead Store Elimination", false, false); FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } @@ -85,15 +93,20 @@ 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::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; } -/// isElidable - If the memory this instruction and the memory it writes to is +/// 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)); @@ -110,9 +123,16 @@ static Value *getPointerOperand(Instruction *I) { if (StoreInst *SI = dyn_cast(I)) return SI->getPointerOperand(); if (MemIntrinsic *MI = dyn_cast(I)) - return MI->getOperand(1); - assert(cast(I)->getIntrinsicID() == Intrinsic::lifetime_end); - return cast(I)->getOperand(2); + return MI->getArgOperand(0); + + IntrinsicInst *II = cast(I); + switch (II->getIntrinsicID()) { + default: assert(false && "Unexpected intrinsic!"); + case Intrinsic::init_trampoline: + return II->getArgOperand(0); + case Intrinsic::lifetime_end: + return II->getArgOperand(1); + } } /// getStoreSize - Return the length in bytes of the write by the clobbering @@ -121,9 +141,7 @@ static unsigned getStoreSize(Instruction *I, const TargetData *TD) { assert(doesClobberMemory(I)); if (StoreInst *SI = dyn_cast(I)) { if (!TD) return -1u; - const PointerType *PTy = - cast(SI->getPointerOperand()->getType()); - return TD->getTypeStoreSize(PTy->getElementType()); + return TD->getTypeStoreSize(SI->getOperand(0)->getType()); } Value *Len; @@ -131,8 +149,14 @@ static unsigned getStoreSize(Instruction *I, const TargetData *TD) { Len = MI->getLength(); } else { IntrinsicInst *II = cast(I); - assert(II->getIntrinsicID() == Intrinsic::lifetime_end); - Len = II->getOperand(0); + switch (II->getIntrinsicID()) { + default: assert(false && "Unexpected intrinsic!"); + case Intrinsic::init_trampoline: + return -1u; + case Intrinsic::lifetime_end: + Len = II->getArgOperand(0); + break; + } } if (ConstantInt *LenCI = dyn_cast(Len)) if (!LenCI->isAllOnesValue()) @@ -159,7 +183,7 @@ static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, } bool DSE::runOnBasicBlock(BasicBlock &BB) { - MemoryDependenceAnalysis& MD = getAnalysis(); + MemoryDependenceAnalysis &MD = getAnalysis(); TD = getAnalysisIfAvailable(); bool MadeChange = false; @@ -179,8 +203,8 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { if (InstDep.isNonLocal()) continue; // Handle frees whose dependencies are non-trivial. - if (isFreeCall(Inst)) { - MadeChange |= handleFreeWithNonTrivialDependency(Inst, InstDep); + if (const CallInst *F = isFreeCall(Inst)) { + MadeChange |= handleFreeWithNonTrivialDependency(F, InstDep); continue; } @@ -196,7 +220,7 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { isElidable(DepStore)) { // Delete the store and now-dead instructions that feed it. DeleteDeadInstruction(DepStore); - NumFastStores++; + ++NumFastStores; MadeChange = true; // DeleteDeadInstruction can delete the current instruction in loop @@ -227,7 +251,7 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { BBI = BB.begin(); else if (BBI != BB.begin()) // Revisit this instruction if possible. --BBI; - NumFastStores++; + ++NumFastStores; MadeChange = true; continue; } @@ -248,7 +272,7 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { BBI = BB.begin(); else if (BBI != BB.begin()) // Revisit this instruction if possible. --BBI; - NumFastStores++; + ++NumFastStores; MadeChange = true; continue; } @@ -265,7 +289,8 @@ 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(Instruction *F, MemDepResult Dep) { +bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F, + MemDepResult Dep) { AliasAnalysis &AA = getAnalysis(); Instruction *Dependency = Dep.getInst(); @@ -275,13 +300,13 @@ bool DSE::handleFreeWithNonTrivialDependency(Instruction *F, MemDepResult Dep) { Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); // Check for aliasing. - if (AA.alias(F->getOperand(1), 1, DepPointer, 1) != + if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) != AliasAnalysis::MustAlias) return false; // DCE instructions only used to calculate that store DeleteDeadInstruction(Dependency); - NumFastStores++; + ++NumFastStores; return true; } @@ -327,9 +352,9 @@ bool DSE::handleEndBlock(BasicBlock &BB) { if (deadPointers.count(pointerOperand)) { // DCE instructions only used to calculate that store. Instruction *Dead = BBI; - BBI++; + ++BBI; DeleteDeadInstruction(Dead, &deadPointers); - NumFastStores++; + ++NumFastStores; MadeChange = true; continue; } @@ -341,7 +366,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 @@ -349,37 +374,36 @@ bool DSE::handleEndBlock(BasicBlock &BB) { // However, if this load is unused and not volatile, we can go ahead and // remove it, and not have to worry about it making our pointer undead! if (L->use_empty() && !L->isVolatile()) { - BBI++; + ++BBI; DeleteDeadInstruction(L, &deadPointers); - NumFastOther++; + ++NumFastOther; MadeChange = true; continue; } 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 if (A->use_empty()) { - BBI++; + ++BBI; DeleteDeadInstruction(A, &deadPointers); - NumFastOther++; + ++NumFastOther; MadeChange = true; } continue; - } else if (CallSite::get(BBI).getInstruction() != 0) { + } else if (CallSite CS = cast(BBI)) { // If this call does not access memory, it can't // be undeadifying any of our pointers. - CallSite CS = CallSite::get(BBI); if (AA.doesNotAccessMemory(CS)) continue; @@ -398,28 +422,15 @@ 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++; + ++modRef; else - other++; + ++other; if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) dead.push_back(*I); @@ -433,9 +444,9 @@ bool DSE::handleEndBlock(BasicBlock &BB) { } else if (isInstructionTriviallyDead(BBI)) { // For any non-memory-affecting non-terminators, DCE them as we reach them Instruction *Inst = BBI; - BBI++; + ++BBI; DeleteDeadInstruction(Inst, &deadPointers); - NumFastOther++; + ++NumFastOther; MadeChange = true; continue; } @@ -455,11 +466,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)) { @@ -474,34 +485,21 @@ 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++; + ++NumFastStores; MadeChange = true; continue; @@ -533,9 +531,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; @@ -559,5 +556,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; }