Index: llvm/trunk/include/llvm/Analysis/OrderedBasicBlock.h =================================================================== --- llvm/trunk/include/llvm/Analysis/OrderedBasicBlock.h +++ llvm/trunk/include/llvm/Analysis/OrderedBasicBlock.h @@ -59,6 +59,14 @@ /// only relevant to compare relative instructions positions inside \p BB. /// Returns false for A == B. bool dominates(const Instruction *A, const Instruction *B); + + /// Remove \p from the ordering, if it is present. + void eraseInstruction(const Instruction *I); + + /// Replace \p Old with \p New in the ordering. \p New is assigned the + /// numbering of \p Old, so it must be inserted at the same position in the + /// IR. + void replaceInstruction(const Instruction *Old, const Instruction *New); }; } // End llvm namespace Index: llvm/trunk/lib/Analysis/OrderedBasicBlock.cpp =================================================================== --- llvm/trunk/lib/Analysis/OrderedBasicBlock.cpp +++ llvm/trunk/lib/Analysis/OrderedBasicBlock.cpp @@ -85,3 +85,26 @@ return comesBefore(A, B); } + +void OrderedBasicBlock::eraseInstruction(const Instruction *I) { + if (LastInstFound != BB->end() && I == &*LastInstFound) { + if (LastInstFound == BB->begin()) + LastInstFound = BB->end(); + else + LastInstFound--; + } + + NumberedInsts.erase(I); +} + +void OrderedBasicBlock::replaceInstruction(const Instruction *Old, + const Instruction *New) { + auto OI = NumberedInsts.find(Old); + if (OI == NumberedInsts.end()) + return; + + NumberedInsts[New] = OI->second; + if (LastInstFound != BB->end() && Old == &*LastInstFound) + LastInstFound = New->getIterator(); + NumberedInsts.erase(Old); +} Index: llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -28,8 +28,8 @@ #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" @@ -56,6 +56,7 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" #include #include #include @@ -97,8 +98,7 @@ static void deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, - InstOverlapIntervalsTy &IOL, - DenseMap *InstrOrdering, + InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB, SmallSetVector *ValueSet = nullptr) { SmallVector NowDeadInsts; @@ -135,8 +135,8 @@ } if (ValueSet) ValueSet->remove(DeadInst); - InstrOrdering->erase(DeadInst); IOL.erase(DeadInst); + OBB.eraseInstruction(DeadInst); if (NewIter == DeadInst->getIterator()) NewIter = DeadInst->eraseFromParent(); @@ -656,8 +656,7 @@ static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL, - DenseMap *InstrOrdering) { + InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -691,7 +690,7 @@ // DCE instructions only used to calculate that store. BasicBlock::iterator BBI(Dependency); - deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, InstrOrdering); + deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, OBB); ++NumFastStores; MadeChange = true; @@ -746,10 +745,10 @@ /// store i32 1, i32* %A /// ret void static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, - MemoryDependenceResults *MD, - const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL, - DenseMap *InstrOrdering) { + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, + InstOverlapIntervalsTy &IOL, + OrderedBasicBlock &OBB) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -809,7 +808,8 @@ << '\n'); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects); + deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB, + &DeadStackObjects); ++NumFastStores; MadeChange = true; continue; @@ -820,7 +820,8 @@ if (isInstructionTriviallyDead(&*BBI, TLI)) { LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: " << *&*BBI << '\n'); - deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects); + deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, OBB, + &DeadStackObjects); ++NumFastOther; MadeChange = true; continue; @@ -1025,7 +1026,7 @@ const DataLayout &DL, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, - DenseMap *InstrOrdering) { + OrderedBasicBlock &OBB) { // Must be a store instruction. StoreInst *SI = dyn_cast(Inst); if (!SI) @@ -1041,7 +1042,7 @@ dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); - deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB); ++NumRedundantStores; return true; } @@ -1059,7 +1060,7 @@ dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: " << *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n'); - deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, OBB); ++NumRedundantStores; return true; } @@ -1073,11 +1074,8 @@ const DataLayout &DL = BB.getModule()->getDataLayout(); bool MadeChange = false; - // FIXME: Maybe change this to use some abstraction like OrderedBasicBlock? - // The current OrderedBasicBlock can't deal with mutation at the moment. - size_t LastThrowingInstIndex = 0; - DenseMap InstrOrdering; - size_t InstrIndex = 1; + OrderedBasicBlock OBB(&BB); + Instruction *LastThrowing = nullptr; // A map of interval maps representing partially-overwritten value parts. InstOverlapIntervalsTy IOL; @@ -1086,7 +1084,7 @@ for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { // Handle 'free' calls specially. if (CallInst *F = isFreeCall(&*BBI, TLI)) { - MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, &InstrOrdering); + MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, OBB); // Increment BBI after handleFree has potentially deleted instructions. // This ensures we maintain a valid iterator. ++BBI; @@ -1095,10 +1093,8 @@ Instruction *Inst = &*BBI++; - size_t CurInstNumber = InstrIndex++; - InstrOrdering.insert(std::make_pair(Inst, CurInstNumber)); if (Inst->mayThrow()) { - LastThrowingInstIndex = CurInstNumber; + LastThrowing = Inst; continue; } @@ -1107,13 +1103,13 @@ continue; // eliminateNoopStore will update in iterator, if necessary. - if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) { + if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, OBB)) { MadeChange = true; continue; } // If we find something that writes memory, get its memory dependence. - MemDepResult InstDep = MD->getDependency(Inst); + MemDepResult InstDep = MD->getDependency(Inst, &OBB); // Ignore any store where we can't find a local dependence. // FIXME: cross-block DSE would be fun. :) @@ -1158,9 +1154,7 @@ // If the underlying object is a non-escaping memory allocation, any store // to it is dead along the unwind edge. Otherwise, we need to preserve // the store. - size_t DepIndex = InstrOrdering.lookup(DepWrite); - assert(DepIndex && "Unexpected instruction"); - if (DepIndex <= LastThrowingInstIndex) { + if (LastThrowing && OBB.dominates(DepWrite, LastThrowing)) { const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL); bool IsStoreDeadOnUnwind = isa(Underlying); if (!IsStoreDeadOnUnwind) { @@ -1191,12 +1185,12 @@ << "\n KILLER: " << *Inst << '\n'); // Delete the store and now-dead instructions that feed it. - deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, &InstrOrdering); + deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB); ++NumFastStores; MadeChange = true; // We erased DepWrite; start over. - InstDep = MD->getDependency(Inst); + InstDep = MD->getDependency(Inst, &OBB); continue; } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) || ((OR == OW_Begin && @@ -1264,14 +1258,11 @@ ++NumModifiedStores; // Remove earlier, wider, store - size_t Idx = InstrOrdering.lookup(DepWrite); - InstrOrdering.erase(DepWrite); - InstrOrdering.insert(std::make_pair(SI, Idx)); + OBB.replaceInstruction(DepWrite, SI); // Delete the old stores and now-dead instructions that feed them. - deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering); - deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, - &InstrOrdering); + deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB); + deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB); MadeChange = true; // We erased DepWrite and Inst (Loc); start over. @@ -1306,7 +1297,7 @@ // If this block ends in a return, unwind, or unreachable, all allocas are // dead at its end, which means stores to them are also dead. if (BB.getTerminator()->getNumSuccessors() == 0) - MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering); + MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, OBB); return MadeChange; }