From 2b85de438326f9d27bc96dc934ec98b98abdb337 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Fri, 29 Mar 2019 00:22:26 +0000 Subject: [PATCH] Revert Recommit "[DSE] Preserve basic block ordering using OrderedBasicBlock." Another buildbot failure http://lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/20402 clang-9: /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/llvm/include/llvm/ADT/DenseMap.h:1228: llvm::DenseMapIterator::value_type* llvm::DenseMapIterator::operator->() const [with KeyT = const llvm::Instruction*; ValueT = unsigned int; KeyInfoT = llvm::DenseMapInfo; Bucket = llvm::detail::DenseMapPair; bool IsConst = false; llvm::DenseMapIterator::pointer = llvm::detail::DenseMapPair*; llvm::DenseMapIterator::value_type = llvm::detail::DenseMapPair]: Assertion `isHandleInSync() && "invalid iterator access!"' failed. 0. Program arguments: /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/stage1.install/bin/clang-9 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name ArchiveCommandLine.cpp -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu skylake-avx512 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -coverage-notes-file /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/sandbox/build/MultiSource/Benchmarks/7zip/Output/ArchiveCommandLine.llvm.gcno -resource-dir /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/stage1.install/lib/clang/9.0.0 -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/sandbox/build/MultiSource/Benchmarks/7zip -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/include -I ../../../include -D _GNU_SOURCE -D __STDC_LIMIT_MACROS -D NDEBUG -D BREAK_HANDLER -D UNICODE -D _UNICODE -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip/C -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip/CPP/myWindows -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip/CPP/include_windows -I /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip/CPP -I . -D _FILE_OFFSET_BITS=64 -D _LARGEFILE_SOURCE -D NDEBUG -D _REENTRANT -D ENV_UNIX -D _7ZIP_LARGE_PAGES -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/x86_64-linux-gnu/c++/5.4.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/x86_64-linux-gnu/c++/5.4.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/backward -internal-isystem /usr/local/include -internal-isystem /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/stage1.install/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -std=gnu++98 -fdeprecated-macro -fdebug-compilation-dir /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/sandbox/build/MultiSource/Benchmarks/7zip -ferror-limit 19 -fmessage-length 0 -pthread -fobjc-runtime=gcc -fcxx-exceptions -fexceptions -fdiagnostics-show-option -vectorize-loops -vectorize-slp -o Output/ArchiveCommandLine.llvm.o -x c++ /home/ssglocal/clang-cmake-x86_64-sde-avx512-linux/clang-cmake-x86_64-sde-avx512-linux/test/test-suite/MultiSource/Benchmarks/7zip/CPP/7zip/UI/Common/ArchiveCommandLine.cpp -faddrsig This reverts r357222 (git commit 64cccfcc72c44ea62f441b782d2177a90912769a) llvm-svn: 357227 --- llvm/include/llvm/Analysis/OrderedBasicBlock.h | 8 --- llvm/lib/Analysis/OrderedBasicBlock.cpp | 24 -------- .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 69 ++++++++++++---------- 3 files changed, 39 insertions(+), 62 deletions(-) diff --git a/llvm/include/llvm/Analysis/OrderedBasicBlock.h b/llvm/include/llvm/Analysis/OrderedBasicBlock.h index ae64c01..6823f68 100644 --- a/llvm/include/llvm/Analysis/OrderedBasicBlock.h +++ b/llvm/include/llvm/Analysis/OrderedBasicBlock.h @@ -59,14 +59,6 @@ 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 401f818..3cc6319 100644 --- a/llvm/lib/Analysis/OrderedBasicBlock.cpp +++ b/llvm/lib/Analysis/OrderedBasicBlock.cpp @@ -85,27 +85,3 @@ 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(); - NextInstPos = 0; - } 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 fc9b4d1..863ee83 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,7 +56,6 @@ #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 @@ -98,7 +97,8 @@ using InstOverlapIntervalsTy = DenseMap; static void deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI, MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, - InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB, + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering, 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,7 +656,8 @@ static void findUnconditionalPreds(SmallVectorImpl &Blocks, static bool handleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL, OrderedBasicBlock &OBB) { + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -690,7 +691,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, OBB); + deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL, InstrOrdering); ++NumFastStores; MadeChange = true; @@ -745,10 +746,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, - OrderedBasicBlock &OBB) { + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -808,8 +809,7 @@ static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, << '\n'); // DCE instructions only used to calculate that store. - deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, OBB, - &DeadStackObjects); + deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects); ++NumFastStores; MadeChange = true; continue; @@ -820,8 +820,7 @@ 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, OBB, - &DeadStackObjects); + deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, InstrOrdering, &DeadStackObjects); ++NumFastOther; MadeChange = true; continue; @@ -1026,7 +1025,7 @@ static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI, const DataLayout &DL, const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, - OrderedBasicBlock &OBB) { + DenseMap *InstrOrdering) { // Must be a store instruction. StoreInst *SI = dyn_cast(Inst); if (!SI) @@ -1042,7 +1041,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, OBB); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering); ++NumRedundantStores; return true; } @@ -1060,7 +1059,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, OBB); + deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering); ++NumRedundantStores; return true; } @@ -1074,8 +1073,11 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, const DataLayout &DL = BB.getModule()->getDataLayout(); bool MadeChange = false; - OrderedBasicBlock OBB(&BB); - Instruction *LastThrowing = nullptr; + // 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; // A map of interval maps representing partially-overwritten value parts. InstOverlapIntervalsTy IOL; @@ -1084,7 +1086,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, OBB); + MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, &InstrOrdering); // Increment BBI after handleFree has potentially deleted instructions. // This ensures we maintain a valid iterator. ++BBI; @@ -1093,8 +1095,10 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, Instruction *Inst = &*BBI++; + size_t CurInstNumber = InstrIndex++; + InstrOrdering.insert(std::make_pair(Inst, CurInstNumber)); if (Inst->mayThrow()) { - LastThrowing = Inst; + LastThrowingInstIndex = CurInstNumber; continue; } @@ -1103,13 +1107,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, OBB)) { + if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) { MadeChange = true; continue; } // If we find something that writes memory, get its memory dependence. - MemDepResult InstDep = MD->getDependency(Inst, &OBB); + MemDepResult InstDep = MD->getDependency(Inst); // Ignore any store where we can't find a local dependence. // FIXME: cross-block DSE would be fun. :) @@ -1154,7 +1158,9 @@ 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. - if (LastThrowing && OBB.dominates(DepWrite, LastThrowing)) { + size_t DepIndex = InstrOrdering.lookup(DepWrite); + assert(DepIndex && "Unexpected instruction"); + if (DepIndex <= LastThrowingInstIndex) { const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL); bool IsStoreDeadOnUnwind = isa(Underlying); if (!IsStoreDeadOnUnwind) { @@ -1185,12 +1191,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, OBB); + deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, &InstrOrdering); ++NumFastStores; MadeChange = true; // We erased DepWrite; start over. - InstDep = MD->getDependency(Inst, &OBB); + InstDep = MD->getDependency(Inst); continue; } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) || ((OR == OW_Begin && @@ -1258,11 +1264,14 @@ static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, ++NumModifiedStores; // Remove earlier, wider, store - OBB.replaceInstruction(DepWrite, SI); + size_t Idx = InstrOrdering.lookup(DepWrite); + InstrOrdering.erase(DepWrite); + InstrOrdering.insert(std::make_pair(SI, Idx)); // Delete the old stores and now-dead instructions that feed them. - deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, OBB); - deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, OBB); + deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering); + deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL, + &InstrOrdering); MadeChange = true; // We erased DepWrite and Inst (Loc); start over. @@ -1297,7 +1306,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, OBB); + MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering); return MadeChange; } -- 2.7.4