diff options
Diffstat (limited to 'lib/Transforms/Scalar/DeadStoreElimination.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/DeadStoreElimination.cpp | 847 |
1 files changed, 501 insertions, 346 deletions
diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp index c8fd9d9..867a06a 100644 --- a/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -19,17 +19,20 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/Function.h" +#include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Pass.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" using namespace llvm; STATISTIC(NumFastStores, "Number of stores deleted"); @@ -37,58 +40,107 @@ STATISTIC(NumFastOther , "Number of other instrs removed"); namespace { struct DSE : public FunctionPass { - TargetData *TD; + AliasAnalysis *AA; + MemoryDependenceAnalysis *MD; static char ID; // Pass identification, replacement for typeid - DSE() : FunctionPass(ID) {} + DSE() : FunctionPass(ID), AA(0), MD(0) { + initializeDSEPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnFunction(Function &F) { - bool Changed = false; - + AA = &getAnalysis<AliasAnalysis>(); + MD = &getAnalysis<MemoryDependenceAnalysis>(); DominatorTree &DT = getAnalysis<DominatorTree>(); + bool Changed = false; for (Function::iterator I = F.begin(), E = F.end(); I != E; ++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); + + AA = 0; MD = 0; return Changed; } bool runOnBasicBlock(BasicBlock &BB); - bool handleFreeWithNonTrivialDependency(const CallInst *F, - MemDepResult Dep); + bool HandleFree(CallInst *F); bool handleEndBlock(BasicBlock &BB); - bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize, - BasicBlock::iterator &BBI, - SmallPtrSet<Value*, 64> &deadPointers); - void DeleteDeadInstruction(Instruction *I, - SmallPtrSet<Value*, 64> *deadPointers = 0); - + void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, + SmallPtrSet<Value*, 16> &DeadStackObjects); - // getAnalysisUsage - We require post dominance frontiers (aka Control - // Dependence Graph) virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired<DominatorTree>(); AU.addRequired<AliasAnalysis>(); AU.addRequired<MemoryDependenceAnalysis>(); + AU.addPreserved<AliasAnalysis>(); AU.addPreserved<DominatorTree>(); AU.addPreserved<MemoryDependenceAnalysis>(); } - - unsigned getPointerSize(Value *V) const; }; } char DSE::ID = 0; -INITIALIZE_PASS(DSE, "dse", "Dead Store Elimination", false, false); +INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } -/// doesClobberMemory - Does this instruction clobber (write without reading) -/// some memory? -static bool doesClobberMemory(Instruction *I) { +//===----------------------------------------------------------------------===// +// Helper functions +//===----------------------------------------------------------------------===// + +/// DeleteDeadInstruction - Delete this instruction. Before we do, go through +/// and zero out all the operands of this instruction. If any of them become +/// dead, delete them and the computation tree that feeds them. +/// +/// If ValueSet is non-null, remove any deleted instructions from it as well. +/// +static void DeleteDeadInstruction(Instruction *I, + MemoryDependenceAnalysis &MD, + SmallPtrSet<Value*, 16> *ValueSet = 0) { + SmallVector<Instruction*, 32> NowDeadInsts; + + NowDeadInsts.push_back(I); + --NumFastOther; + + // Before we touch this instruction, remove it from memdep! + do { + Instruction *DeadInst = NowDeadInsts.pop_back_val(); + ++NumFastOther; + + // This instruction is dead, zap it, in stages. Start by removing it from + // MemDep, which needs to know the operands and needs it to be in the + // function. + MD.removeInstruction(DeadInst); + + for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { + Value *Op = DeadInst->getOperand(op); + DeadInst->setOperand(op, 0); + + // If this operand just became dead, add it to the NowDeadInsts list. + if (!Op->use_empty()) continue; + + if (Instruction *OpI = dyn_cast<Instruction>(Op)) + if (isInstructionTriviallyDead(OpI)) + NowDeadInsts.push_back(OpI); + } + + DeadInst->eraseFromParent(); + + if (ValueSet) ValueSet->erase(DeadInst); + } while (!NowDeadInsts.empty()); +} + + +/// hasMemoryWrite - Does this instruction write some memory? This only returns +/// true for things that we can analyze with other helpers below. +static bool hasMemoryWrite(Instruction *I) { if (isa<StoreInst>(I)) return true; if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { @@ -106,146 +158,296 @@ static bool doesClobberMemory(Instruction *I) { 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<IntrinsicInst>(I)) - return II->getIntrinsicID() != Intrinsic::lifetime_end; +/// getLocForWrite - Return a Location stored to by the specified instruction. +static AliasAnalysis::Location +getLocForWrite(Instruction *Inst, AliasAnalysis &AA) { + if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) + return AA.getLocation(SI); + + if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { + // memcpy/memmove/memset. + AliasAnalysis::Location Loc = AA.getLocationForDest(MI); + // If we don't have target data around, an unknown size in Location means + // that we should use the size of the pointee type. This isn't valid for + // memset/memcpy, which writes more than an i8. + if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) + return AliasAnalysis::Location(); + return Loc; + } + + IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); + if (II == 0) return AliasAnalysis::Location(); + + switch (II->getIntrinsicID()) { + default: return AliasAnalysis::Location(); // Unhandled intrinsic. + case Intrinsic::init_trampoline: + // If we don't have target data around, an unknown size in Location means + // that we should use the size of the pointee type. This isn't valid for + // init.trampoline, which writes more than an i8. + if (AA.getTargetData() == 0) return AliasAnalysis::Location(); + + // FIXME: We don't know the size of the trampoline, so we can't really + // handle it here. + return AliasAnalysis::Location(II->getArgOperand(0)); + case Intrinsic::lifetime_end: { + uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); + return AliasAnalysis::Location(II->getArgOperand(1), Len); + } + } +} + +/// getLocForRead - Return the location read by the specified "hasMemoryWrite" +/// instruction if any. +static AliasAnalysis::Location +getLocForRead(Instruction *Inst, AliasAnalysis &AA) { + assert(hasMemoryWrite(Inst) && "Unknown instruction case"); + + // The only instructions that both read and write are the mem transfer + // instructions (memcpy/memmove). + if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) + return AA.getLocationForSource(MTI); + return AliasAnalysis::Location(); +} + + +/// isRemovable - If the value of this instruction and the memory it writes to +/// is unused, may we delete this instruction? +static bool isRemovable(Instruction *I) { + // Don't remove volatile stores. if (StoreInst *SI = dyn_cast<StoreInst>(I)) return !SI->isVolatile(); - return true; + + IntrinsicInst *II = cast<IntrinsicInst>(I); + switch (II->getIntrinsicID()) { + default: assert(0 && "doesn't pass 'hasMemoryWrite' predicate"); + case Intrinsic::lifetime_end: + // Never remove dead lifetime_end's, e.g. because it is followed by a + // free. + return false; + case Intrinsic::init_trampoline: + // Always safe to remove init_trampoline. + return true; + + case Intrinsic::memset: + case Intrinsic::memmove: + case Intrinsic::memcpy: + // Don't remove volatile memory intrinsics. + return !cast<MemIntrinsic>(II)->isVolatile(); + } } -/// getPointerOperand - Return the pointer that is being clobbered. -static Value *getPointerOperand(Instruction *I) { - assert(doesClobberMemory(I)); +/// getStoredPointerOperand - Return the pointer that is being written to. +static Value *getStoredPointerOperand(Instruction *I) { if (StoreInst *SI = dyn_cast<StoreInst>(I)) return SI->getPointerOperand(); if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) - return MI->getArgOperand(0); + return MI->getDest(); IntrinsicInst *II = cast<IntrinsicInst>(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 -/// instruction. If variable or unknown, returns -1. -static unsigned getStoreSize(Instruction *I, const TargetData *TD) { - assert(doesClobberMemory(I)); - if (StoreInst *SI = dyn_cast<StoreInst>(I)) { - if (!TD) return -1u; - return TD->getTypeStoreSize(SI->getOperand(0)->getType()); +static uint64_t getPointerSize(Value *V, AliasAnalysis &AA) { + const TargetData *TD = AA.getTargetData(); + if (TD == 0) + return AliasAnalysis::UnknownSize; + + if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { + // Get size information for the alloca + if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) + return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); + return AliasAnalysis::UnknownSize; } + + assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); + const PointerType *PT = cast<PointerType>(V->getType()); + return TD->getTypeAllocSize(PT->getElementType()); +} - Value *Len; - if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { - Len = MI->getLength(); - } else { - IntrinsicInst *II = cast<IntrinsicInst>(I); - switch (II->getIntrinsicID()) { - default: assert(false && "Unexpected intrinsic!"); - case Intrinsic::init_trampoline: - return -1u; - case Intrinsic::lifetime_end: - Len = II->getArgOperand(0); - break; +/// isObjectPointerWithTrustworthySize - Return true if the specified Value* is +/// pointing to an object with a pointer size we can trust. +static bool isObjectPointerWithTrustworthySize(const Value *V) { + if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) + return !AI->isArrayAllocation(); + if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) + return !GV->mayBeOverridden(); + if (const Argument *A = dyn_cast<Argument>(V)) + return A->hasByValAttr(); + return false; +} + +/// isCompleteOverwrite - Return true if a store to the 'Later' location +/// completely overwrites a store to the 'Earlier' location. +static bool isCompleteOverwrite(const AliasAnalysis::Location &Later, + const AliasAnalysis::Location &Earlier, + AliasAnalysis &AA) { + const Value *P1 = Earlier.Ptr->stripPointerCasts(); + const Value *P2 = Later.Ptr->stripPointerCasts(); + + // If the start pointers are the same, we just have to compare sizes to see if + // the later store was larger than the earlier store. + if (P1 == P2) { + // If we don't know the sizes of either access, then we can't do a + // comparison. + if (Later.Size == AliasAnalysis::UnknownSize || + Earlier.Size == AliasAnalysis::UnknownSize) { + // If we have no TargetData information around, then the size of the store + // is inferrable from the pointee type. If they are the same type, then + // we know that the store is safe. + if (AA.getTargetData() == 0) + return Later.Ptr->getType() == Earlier.Ptr->getType(); + return false; } + + // Make sure that the Later size is >= the Earlier size. + if (Later.Size < Earlier.Size) + return false; + return true; } - if (ConstantInt *LenCI = dyn_cast<ConstantInt>(Len)) - if (!LenCI->isAllOnesValue()) - return LenCI->getZExtValue(); - return -1u; + + // Otherwise, we have to have size information, and the later store has to be + // larger than the earlier one. + if (Later.Size == AliasAnalysis::UnknownSize || + Earlier.Size == AliasAnalysis::UnknownSize || + Later.Size <= Earlier.Size || AA.getTargetData() == 0) + return false; + + // Check to see if the later store is to the entire object (either a global, + // an alloca, or a byval argument). If so, then it clearly overwrites any + // other store to the same object. + const TargetData &TD = *AA.getTargetData(); + + const Value *UO1 = GetUnderlyingObject(P1, &TD), + *UO2 = GetUnderlyingObject(P2, &TD); + + // If we can't resolve the same pointers to the same object, then we can't + // analyze them at all. + if (UO1 != UO2) + return false; + + // If the "Later" store is to a recognizable object, get its size. + if (isObjectPointerWithTrustworthySize(UO2)) { + uint64_t ObjectSize = + TD.getTypeAllocSize(cast<PointerType>(UO2->getType())->getElementType()); + if (ObjectSize == Later.Size) + return true; + } + + // Okay, we have stores to two completely different pointers. Try to + // decompose the pointer into a "base + constant_offset" form. If the base + // pointers are equal, then we can reason about the two stores. + int64_t Off1 = 0, Off2 = 0; + const Value *BP1 = GetPointerBaseWithConstantOffset(P1, Off1, TD); + const Value *BP2 = GetPointerBaseWithConstantOffset(P2, Off2, TD); + + // If the base pointers still differ, we have two completely different stores. + if (BP1 != BP2) + return false; + + // Otherwise, we might have a situation like: + // store i16 -> P + 1 Byte + // store i32 -> P + // In this case, we see if the later store completely overlaps all bytes + // stored by the previous store. + if (Off1 < Off2 || // Earlier starts before Later. + Off1+Earlier.Size > Off2+Later.Size) // Earlier goes beyond Later. + return false; + // Otherwise, we have complete overlap. + return true; } -/// 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. +/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a +/// memory region into an identical pointer) then it doesn't actually make its +/// input dead in the traditional sense. Consider this case: +/// +/// memcpy(A <- B) +/// memcpy(A <- A) +/// +/// In this case, the second store to A does not make the first store to A dead. +/// The usual situation isn't an explicit A<-A store like this (which can be +/// trivially removed) but a case where two pointers may alias. /// -static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, - const TargetData *TD) { - const Type *I1Ty = getPointerOperand(I1)->getType(); - const Type *I2Ty = getPointerOperand(I2)->getType(); +/// This function detects when it is unsafe to remove a dependent instruction +/// because the DSE inducing instruction may be a self-read. +static bool isPossibleSelfRead(Instruction *Inst, + const AliasAnalysis::Location &InstStoreLoc, + Instruction *DepWrite, AliasAnalysis &AA) { + // Self reads can only happen for instructions that read memory. Get the + // location read. + AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); + if (InstReadLoc.Ptr == 0) return false; // Not a reading instruction. - // Exactly the same type, must have exactly the same size. - if (I1Ty == I2Ty) return true; + // If the read and written loc obviously don't alias, it isn't a read. + if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; - int I1Size = getStoreSize(I1, TD); - int I2Size = getStoreSize(I2, TD); + // Okay, 'Inst' may copy over itself. However, we can still remove a the + // DepWrite instruction if we can prove that it reads from the same location + // as Inst. This handles useful cases like: + // memcpy(A <- B) + // memcpy(A <- B) + // Here we don't know if A/B may alias, but we do know that B/B are must + // aliases, so removing the first memcpy is safe (assuming it writes <= # + // bytes as the second one. + AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); - return I1Size != -1 && I2Size != -1 && I1Size >= I2Size; + if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) + return false; + + // If DepWrite doesn't read memory or if we can't prove it is a must alias, + // then it can't be considered dead. + return true; } -bool DSE::runOnBasicBlock(BasicBlock &BB) { - MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); - TD = getAnalysisIfAvailable<TargetData>(); +//===----------------------------------------------------------------------===// +// DSE Pass +//===----------------------------------------------------------------------===// + +bool DSE::runOnBasicBlock(BasicBlock &BB) { 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, get its memory dependence. - if (!doesClobberMemory(Inst) && !isFreeCall(Inst)) - continue; - - 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 (const CallInst *F = isFreeCall(Inst)) { - MadeChange |= handleFreeWithNonTrivialDependency(F, InstDep); + // Handle 'free' calls specially. + if (CallInst *F = isFreeCall(Inst)) { + MadeChange |= HandleFree(F); continue; } - // If not a definite must-alias dependency, ignore it. - if (!InstDep.isDef()) + // If we find something that writes memory, get its memory dependence. + if (!hasMemoryWrite(Inst)) 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 (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; - MadeChange = true; - // DeleteDeadInstruction can delete the current instruction in loop - // cases, reset BBI. - BBI = Inst; - if (BBI != BB.begin()) - --BBI; - continue; - } - } + MemDepResult InstDep = MD->getDependency(Inst); - if (!isElidable(Inst)) + // Ignore non-local store liveness. + // FIXME: cross-block DSE would be fun. :) + if (InstDep.isNonLocal() || + // Ignore self dependence, which happens in the entry block of the + // function. + InstDep.getInst() == 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 (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { if (SI->getPointerOperand() == DepLoad->getPointerOperand() && - SI->getOperand(0) == DepLoad) { + SI->getOperand(0) == DepLoad && !SI->isVolatile()) { + DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " + << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); + // DeleteDeadInstruction can delete the current instruction. Save BBI // in case we need it. WeakVH NextInst(BBI); - DeleteDeadInstruction(SI); + DeleteDeadInstruction(SI, *MD); if (NextInst == 0) // Next instruction deleted. BBI = BB.begin(); @@ -258,24 +460,63 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { } } - // If this is a lifetime end marker, we can throw away the store. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(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(Inst); + // Figure out what location is being stored to. + AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); + + // If we didn't get a useful location, fail. + if (Loc.Ptr == 0) + continue; + + while (!InstDep.isNonLocal()) { + // Get the memory clobbered by the instruction we depend on. MemDep will + // skip any instructions that 'Loc' clearly doesn't interact with. If we + // end up depending on a may- or must-aliased load, then we can't optimize + // away the store and we bail out. However, if we depend on on something + // that overwrites the memory location we *can* potentially optimize it. + // + // Find out what memory location the dependant instruction stores. + Instruction *DepWrite = InstDep.getInst(); + AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); + // If we didn't get a useful location, or if it isn't a size, bail out. + if (DepLoc.Ptr == 0) + break; + + // If we find a write that is a) removable (i.e., non-volatile), b) is + // completely obliterated by the store to 'Loc', and c) which we know that + // 'Inst' doesn't load from, then we can remove it. + if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, *AA) && + !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { + DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " + << *DepWrite << "\n KILLER: " << *Inst << '\n'); - if (NextInst == 0) // Next instruction deleted. - BBI = BB.begin(); - else if (BBI != BB.begin()) // Revisit this instruction if possible. - --BBI; + // Delete the store and now-dead instructions that feed it. + DeleteDeadInstruction(DepWrite, *MD); ++NumFastStores; MadeChange = true; - continue; + + // DeleteDeadInstruction can delete the current instruction in loop + // cases, reset BBI. + BBI = Inst; + if (BBI != BB.begin()) + --BBI; + break; } + + // If this is a may-aliased store that is clobbering the store value, we + // can keep searching past it for another must-aliased pointer that stores + // to the same location. For example, in: + // store -> P + // store -> Q + // store -> P + // we can remove the first store to P even though we don't know if P and Q + // alias. + if (DepWrite == &BB.front()) break; + + // Can't look past this instruction if it might read 'Loc'. + if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) + break; + + InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); } } @@ -287,26 +528,36 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) { return MadeChange; } -/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose -/// dependency is a store to a field of that structure. -bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F, - MemDepResult Dep) { - AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); - - Instruction *Dependency = Dep.getInst(); - if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency)) - return false; +/// HandleFree - Handle frees of entire structures whose dependency is a store +/// to a field of that structure. +bool DSE::HandleFree(CallInst *F) { + MemDepResult Dep = MD->getDependency(F); + do { + if (Dep.isNonLocal()) return false; + + Instruction *Dependency = Dep.getInst(); + if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) + return false; - Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); + Value *DepPointer = + GetUnderlyingObject(getStoredPointerOperand(Dependency)); - // Check for aliasing. - if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) != - AliasAnalysis::MustAlias) - return false; + // Check for aliasing. + if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) + return false; + + // DCE instructions only used to calculate that store + DeleteDeadInstruction(Dependency, *MD); + ++NumFastStores; + + // Inst's old Dependency is now deleted. Compute the next dependency, + // which may also be dead, as in + // s[0] = 0; + // s[1] = 0; // This has just been deleted. + // free(s); + Dep = MD->getDependency(F); + } while (!Dep.isNonLocal()); - // DCE instructions only used to calculate that store - DeleteDeadInstruction(Dependency); - ++NumFastStores; return true; } @@ -317,259 +568,163 @@ bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F, /// store i32 1, i32* %A /// ret void bool DSE::handleEndBlock(BasicBlock &BB) { - AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); - bool MadeChange = false; - // Pointers alloca'd in this function are dead in the end block - SmallPtrSet<Value*, 64> deadPointers; + // Keep track of all of the stack objects that are dead at the end of the + // function. + SmallPtrSet<Value*, 16> DeadStackObjects; // Find all of the alloca'd pointers in the entry block. BasicBlock *Entry = BB.getParent()->begin(); for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) - deadPointers.insert(AI); + DeadStackObjects.insert(AI); // Treat byval arguments the same, stores to them are dead at the end of the // function. for (Function::arg_iterator AI = BB.getParent()->arg_begin(), AE = BB.getParent()->arg_end(); AI != AE; ++AI) if (AI->hasByValAttr()) - deadPointers.insert(AI); + DeadStackObjects.insert(AI); // Scan the basic block backwards for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ --BBI; - // If we find a store whose pointer is dead. - if (doesClobberMemory(BBI)) { - if (isElidable(BBI)) { - // See through pointer-to-pointer bitcasts - 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(Dead, &deadPointers); - ++NumFastStores; - MadeChange = true; - continue; - } - } - - // Because a memcpy or memmove is also a load, we can't skip it if we - // didn't remove it. - if (!isa<MemTransferInst>(BBI)) + // If we find a store, check to see if it points into a dead stack value. + if (hasMemoryWrite(BBI) && isRemovable(BBI)) { + // See through pointer-to-pointer bitcasts + Value *Pointer = GetUnderlyingObject(getStoredPointerOperand(BBI)); + + // Stores to stack values are valid candidates for removal. + if (DeadStackObjects.count(Pointer)) { + Instruction *Dead = BBI++; + + DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " + << *Dead << "\n Object: " << *Pointer << '\n'); + + // DCE instructions only used to calculate that store. + DeleteDeadInstruction(Dead, *MD, &DeadStackObjects); + ++NumFastStores; + MadeChange = true; continue; + } } - Value *killPointer = 0; - uint64_t killPointerSize = ~0UL; + // Remove any dead non-memory-mutating instructions. + if (isInstructionTriviallyDead(BBI)) { + Instruction *Inst = BBI++; + DeleteDeadInstruction(Inst, *MD, &DeadStackObjects); + ++NumFastOther; + MadeChange = true; + continue; + } - // If we encounter a use of the pointer, it is no longer considered dead - if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { - // 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; - DeleteDeadInstruction(L, &deadPointers); - ++NumFastOther; - MadeChange = true; - continue; - } - - killPointer = L->getPointerOperand(); - } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { - killPointer = V->getOperand(0); - } else if (isa<MemTransferInst>(BBI) && - isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) { - killPointer = cast<MemTransferInst>(BBI)->getSource(); - killPointerSize = cast<ConstantInt>( - cast<MemTransferInst>(BBI)->getLength())->getZExtValue(); - } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { - deadPointers.erase(A); - - // Dead alloca's can be DCE'd when we reach them - if (A->use_empty()) { - ++BBI; - DeleteDeadInstruction(A, &deadPointers); - ++NumFastOther; - MadeChange = true; - } - + if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { + DeadStackObjects.erase(A); continue; - } else if (CallSite CS = cast<Value>(BBI)) { - // If this call does not access memory, it can't - // be undeadifying any of our pointers. - if (AA.doesNotAccessMemory(CS)) + } + + if (CallSite CS = cast<Value>(BBI)) { + // If this call does not access memory, it can't be loading any of our + // pointers. + if (AA->doesNotAccessMemory(CS)) continue; - unsigned modRef = 0; - unsigned other = 0; + unsigned NumModRef = 0, NumOther = 0; - // Remove any pointers made undead by the call from the dead set - std::vector<Value*> dead; - for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), - E = deadPointers.end(); I != E; ++I) { - // HACK: if we detect that our AA is imprecise, it's not - // worth it to scan the rest of the deadPointers set. Just - // assume that the AA will return ModRef for everything, and - // go ahead and bail. - if (modRef >= 16 && other == 0) { - deadPointers.clear(); + // If the call might load from any of our allocas, then any store above + // the call is live. + SmallVector<Value*, 8> LiveAllocas; + for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), + E = DeadStackObjects.end(); I != E; ++I) { + // If we detect that our AA is imprecise, it's not worth it to scan the + // rest of the DeadPointers set. Just assume that the AA will return + // ModRef for everything, and go ahead and bail out. + if (NumModRef >= 16 && NumOther == 0) return MadeChange; - } - - // See if the call site touches it - AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, - getPointerSize(*I)); + + // See if the call site touches it. + AliasAnalysis::ModRefResult A = + AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA)); if (A == AliasAnalysis::ModRef) - ++modRef; + ++NumModRef; else - ++other; + ++NumOther; if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) - dead.push_back(*I); + LiveAllocas.push_back(*I); } - - for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); - I != E; ++I) - deadPointers.erase(*I); - continue; - } else if (isInstructionTriviallyDead(BBI)) { - // For any non-memory-affecting non-terminators, DCE them as we reach them - Instruction *Inst = BBI; - ++BBI; - DeleteDeadInstruction(Inst, &deadPointers); - ++NumFastOther; - MadeChange = true; + for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(), + E = LiveAllocas.end(); I != E; ++I) + DeadStackObjects.erase(*I); + + // If all of the allocas were clobbered by the call then we're not going + // to find anything else to process. + if (DeadStackObjects.empty()) + return MadeChange; + continue; } - if (!killPointer) + AliasAnalysis::Location LoadedLoc; + + // If we encounter a use of the pointer, it is no longer considered dead + if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { + LoadedLoc = AA->getLocation(L); + } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { + LoadedLoc = AA->getLocation(V); + } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { + LoadedLoc = AA->getLocationForSource(MTI); + } else { + // Not a loading instruction. continue; + } - killPointer = killPointer->getUnderlyingObject(); + // Remove any allocas from the DeadPointer set that are loaded, as this + // makes any stores above the access live. + RemoveAccessedObjects(LoadedLoc, DeadStackObjects); - // Deal with undead pointers - MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, - deadPointers); + // If all of the allocas were clobbered by the access then we're not going + // to find anything else to process. + if (DeadStackObjects.empty()) + break; } return MadeChange; } -/// 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, - BasicBlock::iterator &BBI, - SmallPtrSet<Value*, 64> &deadPointers) { - AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); - - // If the kill pointer can be easily reduced to an alloca, - // don't bother doing extraneous AA queries. - if (deadPointers.count(killPointer)) { - deadPointers.erase(killPointer); - return false; - } - - // A global can't be in the dead pointer set. - if (isa<GlobalValue>(killPointer)) - return false; - - bool MadeChange = false; +/// RemoveAccessedObjects - Check to see if the specified location may alias any +/// of the stack objects in the DeadStackObjects set. If so, they become live +/// because the location is being loaded. +void DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, + SmallPtrSet<Value*, 16> &DeadStackObjects) { + const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); + + // A constant can't be in the dead pointer set. + if (isa<Constant>(UnderlyingPointer)) + return; - SmallVector<Value*, 16> undead; + // If the kill pointer can be easily reduced to an alloca, don't bother doing + // extraneous AA queries. + if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { + DeadStackObjects.erase(const_cast<Value*>(UnderlyingPointer)); + return; + } - for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), - E = deadPointers.end(); I != E; ++I) { - // See if this pointer could alias it - AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I), - killPointer, killPointerSize); - - // If it must-alias and a store, we can delete it - if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { - StoreInst *S = cast<StoreInst>(BBI); - - // Remove it! - ++BBI; - DeleteDeadInstruction(S, &deadPointers); - ++NumFastStores; - MadeChange = true; - - continue; - - // Otherwise, it is undead - } else if (A != AliasAnalysis::NoAlias) - undead.push_back(*I); + SmallVector<Value*, 16> NowLive; + for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), + E = DeadStackObjects.end(); I != E; ++I) { + // See if the loaded location could alias the stack location. + AliasAnalysis::Location StackLoc(*I, getPointerSize(*I, *AA)); + if (!AA->isNoAlias(StackLoc, LoadedLoc)) + NowLive.push_back(*I); } - for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); + for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end(); I != E; ++I) - deadPointers.erase(*I); - - return MadeChange; + DeadStackObjects.erase(*I); } -/// DeleteDeadInstruction - Delete this instruction. Before we do, go through -/// and zero out all the operands of this instruction. If any of them become -/// dead, delete them and the computation tree that feeds them. -/// -/// If ValueSet is non-null, remove any deleted instructions from it as well. -/// -void DSE::DeleteDeadInstruction(Instruction *I, - SmallPtrSet<Value*, 64> *ValueSet) { - SmallVector<Instruction*, 32> NowDeadInsts; - - NowDeadInsts.push_back(I); - --NumFastOther; - - // Before we touch this instruction, remove it from memdep! - MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); - do { - Instruction *DeadInst = NowDeadInsts.pop_back_val(); - - ++NumFastOther; - - // This instruction is dead, zap it, in stages. Start by removing it from - // MemDep, which needs to know the operands and needs it to be in the - // function. - MDA.removeInstruction(DeadInst); - - for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { - Value *Op = DeadInst->getOperand(op); - DeadInst->setOperand(op, 0); - - // If this operand just became dead, add it to the NowDeadInsts list. - if (!Op->use_empty()) continue; - - if (Instruction *OpI = dyn_cast<Instruction>(Op)) - if (isInstructionTriviallyDead(OpI)) - NowDeadInsts.push_back(OpI); - } - - DeadInst->eraseFromParent(); - - if (ValueSet) ValueSet->erase(DeadInst); - } while (!NowDeadInsts.empty()); -} - -unsigned DSE::getPointerSize(Value *V) const { - if (TD) { - if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { - // Get size information for the alloca - if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) - return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); - } else { - assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); - const PointerType *PT = cast<PointerType>(V->getType()); - return TD->getTypeAllocSize(PT->getElementType()); - } - } - return ~0U; -} |
