From c0bfd37d385c93711ef3a349599dba20e6b101ef Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Thu, 28 Mar 2019 20:02:33 +0000 Subject: [PATCH] [DSE] Preserve basic block ordering using OrderedBasicBlock. By extending OrderedBB to allow removing and replacing cached instructions, we can preserve OrderedBBs in DSE easily. This eliminates one source of quadratic compile time in DSE. Fixes PR38829. Reviewers: rnk, efriedma, hfinkel Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D59789 llvm-svn: 357208 --- llvm/include/llvm/Analysis/OrderedBasicBlock.h | 8 +++ llvm/lib/Analysis/OrderedBasicBlock.cpp | 23 ++++++++ .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 69 ++++++++++------------ 3 files changed, 61 insertions(+), 39 deletions(-) diff --git a/llvm/include/llvm/Analysis/OrderedBasicBlock.h b/llvm/include/llvm/Analysis/OrderedBasicBlock.h index 6823f68..ae64c01 100644 --- a/llvm/include/llvm/Analysis/OrderedBasicBlock.h +++ b/llvm/include/llvm/Analysis/OrderedBasicBlock.h @@ -59,6 +59,14 @@ public: /// 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 diff --git a/llvm/lib/Analysis/OrderedBasicBlock.cpp b/llvm/lib/Analysis/OrderedBasicBlock.cpp index 3cc6319..ad80a66 100644 --- a/llvm/lib/Analysis/OrderedBasicBlock.cpp +++ b/llvm/lib/Analysis/OrderedBasicBlock.cpp @@ -85,3 +85,26 @@ bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) { 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); +} diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp index 863ee83..fc9b4d1 100644 --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/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 @@ using InstOverlapIntervalsTy = DenseMap; 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 @@ deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, } 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 void findUnconditionalPreds(SmallVectorImpl &Blocks, 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 @@ static bool handleFree(CallInst *F, AliasAnalysis *AA, // 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 @@ static void removeAccessedObjects(const MemoryLocation &LoadedLoc, /// 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 @@ static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, << '\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 @@ static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, 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 @@ static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, 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 @@ static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, 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 @@ static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, // 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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, << "\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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, ++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 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, // 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; } -- 2.7.4