Index: llvm/include/llvm/Analysis/AliasAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/AliasAnalysis.h +++ llvm/include/llvm/Analysis/AliasAnalysis.h @@ -670,19 +670,16 @@ /// Return information about whether a particular call site modifies /// or reads the specified memory location \p MemLoc before instruction \p I - /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up - /// instruction ordering queries inside the BasicBlock containing \p I. + /// in a BasicBlock. /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being /// set. ModRefInfo callCapturesBefore(const Instruction *I, - const MemoryLocation &MemLoc, DominatorTree *DT, - OrderedBasicBlock *OBB = nullptr); + const MemoryLocation &MemLoc, DominatorTree *DT); /// A convenience wrapper to synthesize a memory location. ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, - LocationSize Size, DominatorTree *DT, - OrderedBasicBlock *OBB = nullptr) { - return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB); + LocationSize Size, DominatorTree *DT) { + return callCapturesBefore(I, MemoryLocation(P, Size), DT); } /// @} Index: llvm/include/llvm/Analysis/CaptureTracking.h =================================================================== --- llvm/include/llvm/Analysis/CaptureTracking.h +++ llvm/include/llvm/Analysis/CaptureTracking.h @@ -20,7 +20,6 @@ class Use; class Instruction; class DominatorTree; - class OrderedBasicBlock; /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can @@ -42,12 +41,11 @@ /// it or not. The boolean StoreCaptures specified whether storing the value /// (or part of it) into memory anywhere automatically counts as capturing it /// or not. Captures by the provided instruction are considered if the - /// final parameter is true. An ordered basic block in \p OBB could be used - /// to speed up capture-tracker queries. + /// final parameter is true. bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - const DominatorTree *DT, bool IncludeI = false, - OrderedBasicBlock *OBB = nullptr); + const DominatorTree *DT, + bool IncludeI = false); /// This callback is used in conjunction with PointerMayBeCaptured. In /// addition to the interface here, you'll need to provide your own getters Index: llvm/include/llvm/Analysis/OrderedBasicBlock.h =================================================================== --- llvm/include/llvm/Analysis/OrderedBasicBlock.h +++ /dev/null @@ -1,67 +0,0 @@ -//===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the OrderedBasicBlock class. OrderedBasicBlock maintains -// an interface where clients can query if one instruction comes before another -// in a BasicBlock. Since BasicBlock currently lacks a reliable way to query -// relative position between instructions one can use OrderedBasicBlock to do -// such queries. OrderedBasicBlock is lazily built on a source BasicBlock and -// maintains an internal Instruction -> Position map. A OrderedBasicBlock -// instance should be discarded whenever the source BasicBlock changes. -// -// It's currently used by the CaptureTracker in order to find relative -// positions of a pair of instructions inside a BasicBlock. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H -#define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/IR/BasicBlock.h" - -namespace llvm { - -class Instruction; -class BasicBlock; - -class OrderedBasicBlock { -private: - /// Map a instruction to its position in a BasicBlock. - SmallDenseMap NumberedInsts; - - /// Keep track of last instruction inserted into \p NumberedInsts. - /// It speeds up queries for uncached instructions by providing a start point - /// for new queries in OrderedBasicBlock::comesBefore. - BasicBlock::const_iterator LastInstFound; - - /// The position/number to tag the next instruction to be found. - unsigned NextInstPos; - - /// The source BasicBlock to map. - const BasicBlock *BB; - - /// Given no cached results, find if \p A comes before \p B in \p BB. - /// Cache and number out instruction while walking \p BB. - bool comesBefore(const Instruction *A, const Instruction *B); - -public: - OrderedBasicBlock(const BasicBlock *BasicB); - - /// Find out whether \p A dominates \p B, meaning whether \p A - /// comes before \p B in \p BB. This is a simplification that considers - /// cached instruction positions and ignores other basic blocks, being - /// only relevant to compare relative instructions positions inside \p BB. - /// Returns false for A == B. - bool dominates(const Instruction *A, const Instruction *B); -}; - -} // End llvm namespace - -#endif Index: llvm/include/llvm/Analysis/OrderedInstructions.h =================================================================== --- llvm/include/llvm/Analysis/OrderedInstructions.h +++ llvm/include/llvm/Analysis/OrderedInstructions.h @@ -10,10 +10,9 @@ // This file defines an efficient way to check for dominance relation between 2 // instructions. // -// This interface dispatches to appropriate dominance check given 2 -// instructions, i.e. in case the instructions are in the same basic block, -// OrderedBasicBlock (with instruction numbering and caching) are used. -// Otherwise, dominator tree is used. +// FIXME: This is really just a convenience wrapper to check dominance between +// two arbitrary instructions in different basic blocks. We should fold it into +// DominatorTree, which is the more widely used interface. // //===----------------------------------------------------------------------===// @@ -21,17 +20,12 @@ #define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H #include "llvm/ADT/DenseMap.h" -#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Operator.h" namespace llvm { class OrderedInstructions { - /// Used to check dominance for instructions in same basic block. - mutable DenseMap> - OBBMap; - /// The dominator tree of the parent function. DominatorTree *DT; @@ -52,12 +46,6 @@ /// or if the first instruction comes before the second in the same basic /// block. bool dfsBefore(const Instruction *, const Instruction *) const; - - /// Invalidate the OrderedBasicBlock cache when its basic block changes. - /// i.e. If an instruction is deleted or added to the basic block, the user - /// should call this function to invalidate the OrderedBasicBlock cache for - /// this basic block. - void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); } }; } // end namespace llvm Index: llvm/include/llvm/IR/BasicBlock.h =================================================================== --- llvm/include/llvm/IR/BasicBlock.h +++ llvm/include/llvm/IR/BasicBlock.h @@ -384,7 +384,9 @@ /// Returns true if there are any uses of this basic block other than /// direct branches, switches, etc. to it. - bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; } + bool hasAddressTaken() const { + return (getSubclassDataFromValue() >> 1) != 0; + } /// Update all phi nodes in this basic block's successors to refer to basic /// block \p New instead of to it. @@ -411,6 +413,19 @@ Optional getIrrLoopHeaderWeight() const; + /// Returns true if the Order field of child Instructions is valid. + bool isInstrOrderValid() { + return getSubclassDataFromValue() & 1; + } + + /// Mark instruction ordering invalid. Done on every instruction insert. + void invalidateOrders() { + setValueSubclassData(getSubclassDataFromValue() & ~1U); + } + + /// Renumber instructions and mark the ordering as valid. + void renumberInstructions(); + private: /// Increment the internal refcount of the number of BlockAddresses /// referencing this BasicBlock by \p Amt. @@ -418,8 +433,8 @@ /// This is almost always 0, sometimes one possibly, but almost never 2, and /// inconceivably 3 or more. void AdjustBlockAddressRefCount(int Amt) { - setValueSubclassData(getSubclassDataFromValue()+Amt); - assert((int)(signed char)getSubclassDataFromValue() >= 0 && + setValueSubclassData(getSubclassDataFromValue() + (Amt << 1)); + assert((int)(signed char)(getSubclassDataFromValue() >> 1) >= 0 && "Refcount wrap-around"); } Index: llvm/include/llvm/IR/Instruction.h =================================================================== --- llvm/include/llvm/IR/Instruction.h +++ llvm/include/llvm/IR/Instruction.h @@ -46,6 +46,10 @@ BasicBlock *Parent; DebugLoc DbgLoc; // 'dbg' Metadata cache. + /// Relative order of this instruction in its parent basic block. Used for + /// O(1) local dominance checks between instructions. + mutable unsigned Order = 0; + enum { /// This is a bit stored in the SubClassData field which indicates whether /// this instruction has metadata attached to it or not. @@ -118,6 +122,13 @@ /// the basic block that MovePos lives in, right after MovePos. void moveAfter(Instruction *MovePos); + /// Given an instruction Other in the same basic block as this instruction, + /// return true if this instruction comes before Other. In this worst case, + /// this takes linear time in the number of instructions in the block. The + /// results are cached, so in common cases when the block remains unmodified, + /// it takes constant time. + bool comesBefore(const Instruction *Other) const; + //===--------------------------------------------------------------------===// // Subclass classification. //===--------------------------------------------------------------------===// @@ -691,6 +702,7 @@ private: friend class SymbolTableListTraits; + friend class BasicBlock; // For renumbering. // Shadow Value::setValueSubclassData with a private forwarding method so that // subclasses cannot accidentally use it. Index: llvm/include/llvm/IR/SymbolTableListTraits.h =================================================================== --- llvm/include/llvm/IR/SymbolTableListTraits.h +++ llvm/include/llvm/IR/SymbolTableListTraits.h @@ -58,7 +58,10 @@ DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalIFunc, Module) #undef DEFINE_SYMBOL_TABLE_PARENT_TYPE -template class SymbolTableList; +template class SymbolTableListTraits; +template > +class SymbolTableList; // ValueSubClass - The type of objects that I hold, e.g. Instruction. // ItemParentClass - The type of object that owns the list, e.g. BasicBlock. @@ -73,7 +76,7 @@ public: SymbolTableListTraits() = default; -private: +protected: /// getListOwner - Return the object that owns this list. If this is a list /// of instructions, it returns the BasicBlock that owns them. ItemParentClass *getListOwner() { @@ -109,9 +112,9 @@ /// When nodes are inserted into and removed from this list, the associated /// symbol table will be automatically updated. Similarly, parent links get /// updated automatically. -template +template class SymbolTableList - : public iplist_impl, SymbolTableListTraits> {}; + : public iplist_impl, TraitsT> {}; } // end namespace llvm Index: llvm/lib/Analysis/AliasAnalysis.cpp =================================================================== --- llvm/lib/Analysis/AliasAnalysis.cpp +++ llvm/lib/Analysis/AliasAnalysis.cpp @@ -539,16 +539,14 @@ /// Return information about whether a particular call site modifies /// or reads the specified memory location \p MemLoc before instruction \p I -/// in a BasicBlock. An ordered basic block \p OBB can be used to speed up -/// instruction-ordering queries inside the BasicBlock containing \p I. +/// in a BasicBlock. /// FIXME: this is really just shoring-up a deficiency in alias analysis. /// BasicAA isn't willing to spend linear time determining whether an alloca /// was captured before or after this particular call, while we are. However, /// with a smarter AA in place, this test is just wasting compile time. ModRefInfo AAResults::callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, - DominatorTree *DT, - OrderedBasicBlock *OBB) { + DominatorTree *DT) { if (!DT) return ModRefInfo::ModRef; @@ -564,8 +562,7 @@ if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true, /* StoreCaptures */ true, I, DT, - /* include Object */ true, - /* OrderedBasicBlock */ OBB)) + /* include Object */ true)) return ModRefInfo::ModRef; unsigned ArgNo = 0; Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -65,7 +65,6 @@ ObjCARCAnalysisUtils.cpp ObjCARCInstKind.cpp OptimizationRemarkEmitter.cpp - OrderedBasicBlock.cpp OrderedInstructions.cpp PHITransAddr.cpp PhiValues.cpp Index: llvm/lib/Analysis/CaptureTracking.cpp =================================================================== --- llvm/lib/Analysis/CaptureTracking.cpp +++ llvm/lib/Analysis/CaptureTracking.cpp @@ -21,7 +21,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" @@ -62,8 +61,8 @@ struct CapturesBefore : public CaptureTracker { CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT, - bool IncludeI, OrderedBasicBlock *IC) - : OrderedBB(IC), BeforeHere(I), DT(DT), + bool IncludeI) + : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {} void tooManyUses() override { Captured = true; } @@ -76,9 +75,7 @@ return true; // Compute the case where both instructions are inside the same basic - // block. Since instructions in the same BB as BeforeHere are numbered in - // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable' - // which are very expensive for large basic blocks. + // block. if (BB == BeforeHere->getParent()) { // 'I' dominates 'BeforeHere' => not safe to prune. // @@ -88,7 +85,7 @@ // UseBB == BB, avoid pruning. if (isa(BeforeHere) || isa(I) || I == BeforeHere) return false; - if (!OrderedBB->dominates(BeforeHere, I)) + if (!BeforeHere->comesBefore(I)) return false; // 'BeforeHere' comes before 'I', it's safe to prune if we also @@ -139,7 +136,6 @@ return true; } - OrderedBasicBlock *OrderedBB; const Instruction *BeforeHere; const DominatorTree *DT; @@ -181,29 +177,21 @@ /// returning the value (or part of it) from the function counts as capturing /// it or not. The boolean StoreCaptures specified whether storing the value /// (or part of it) into memory anywhere automatically counts as capturing it -/// or not. A ordered basic block \p OBB can be used in order to speed up -/// queries about relative order among instructions in the same basic block. +/// or not. bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, - const DominatorTree *DT, bool IncludeI, - OrderedBasicBlock *OBB) { + const DominatorTree *DT, bool IncludeI) { assert(!isa(V) && "It doesn't make sense to ask whether a global is captured."); - bool UseNewOBB = OBB == nullptr; if (!DT) return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); - if (UseNewOBB) - OBB = new OrderedBasicBlock(I->getParent()); // TODO: See comment in PointerMayBeCaptured regarding what could be done // with StoreCaptures. - CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB); + CapturesBefore CB(ReturnCaptures, I, DT, IncludeI); PointerMayBeCaptured(V, &CB); - - if (UseNewOBB) - delete OBB; return CB.Captured; } Index: llvm/lib/Analysis/InstructionPrecedenceTracking.cpp =================================================================== --- llvm/lib/Analysis/InstructionPrecedenceTracking.cpp +++ llvm/lib/Analysis/InstructionPrecedenceTracking.cpp @@ -57,14 +57,11 @@ } void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) { - OI.invalidateBlock(BB); FirstSpecialInsts.erase(BB); KnownBlocks.erase(BB); } void InstructionPrecedenceTracking::clear() { - for (auto It : FirstSpecialInsts) - OI.invalidateBlock(It.first); FirstSpecialInsts.clear(); KnownBlocks.clear(); } Index: llvm/lib/Analysis/MemoryDependenceAnalysis.cpp =================================================================== --- llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -24,7 +24,6 @@ #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" -#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/PHITransAddr.h" #include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -489,12 +488,6 @@ const DataLayout &DL = BB->getModule()->getDataLayout(); - // Create a numbered basic block to lazily compute and cache instruction - // positions inside a BB. This is used to provide fast queries for relative - // position between two instructions in a BB and can be used by - // AliasAnalysis::callCapturesBefore. - OrderedBasicBlock OBB(BB); - // Return "true" if and only if the instruction I is either a non-simple // load or a non-simple store. auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool { @@ -684,7 +677,7 @@ ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc); // If necessary, perform additional analysis. if (isModAndRefSet(MR)) - MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB); + MR = AA.callCapturesBefore(Inst, MemLoc, &DT); switch (clearMust(MR)) { case ModRefInfo::NoModRef: // If the call has no effect on the queried pointer, just ignore it. Index: llvm/lib/Analysis/OrderedBasicBlock.cpp =================================================================== --- llvm/lib/Analysis/OrderedBasicBlock.cpp +++ /dev/null @@ -1,85 +0,0 @@ -//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the OrderedBasicBlock class. OrderedBasicBlock -// maintains an interface where clients can query if one instruction comes -// before another in a BasicBlock. Since BasicBlock currently lacks a reliable -// way to query relative position between instructions one can use -// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a -// source BasicBlock and maintains an internal Instruction -> Position map. A -// OrderedBasicBlock instance should be discarded whenever the source -// BasicBlock changes. -// -// It's currently used by the CaptureTracker in order to find relative -// positions of a pair of instructions inside a BasicBlock. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/OrderedBasicBlock.h" -#include "llvm/IR/Instruction.h" -using namespace llvm; - -OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB) - : NextInstPos(0), BB(BasicB) { - LastInstFound = BB->end(); -} - -/// Given no cached results, find if \p A comes before \p B in \p BB. -/// Cache and number out instruction while walking \p BB. -bool OrderedBasicBlock::comesBefore(const Instruction *A, - const Instruction *B) { - const Instruction *Inst = nullptr; - assert(!(LastInstFound == BB->end() && NextInstPos != 0) && - "Instruction supposed to be in NumberedInsts"); - - // Start the search with the instruction found in the last lookup round. - auto II = BB->begin(); - auto IE = BB->end(); - if (LastInstFound != IE) - II = std::next(LastInstFound); - - // Number all instructions up to the point where we find 'A' or 'B'. - for (; II != IE; ++II) { - Inst = cast(II); - NumberedInsts[Inst] = NextInstPos++; - if (Inst == A || Inst == B) - break; - } - - assert(II != IE && "Instruction not found?"); - assert((Inst == A || Inst == B) && "Should find A or B"); - LastInstFound = II; - return Inst != B; -} - -/// Find out whether \p A dominates \p B, meaning whether \p A -/// comes before \p B in \p BB. This is a simplification that considers -/// cached instruction positions and ignores other basic blocks, being -/// only relevant to compare relative instructions positions inside \p BB. -bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) { - assert(A->getParent() == B->getParent() && - "Instructions must be in the same basic block!"); - - // First we lookup the instructions. If they don't exist, lookup will give us - // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA - // exists and NB doesn't, it means NA must come before NB because we would - // have numbered NB as well if it didn't. The same is true for NB. If it - // exists, but NA does not, NA must come after it. If neither exist, we need - // to number the block and cache the results (by calling comesBefore). - auto NAI = NumberedInsts.find(A); - auto NBI = NumberedInsts.find(B); - if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end()) - return NAI->second < NBI->second; - if (NAI != NumberedInsts.end()) - return true; - if (NBI != NumberedInsts.end()) - return false; - - return comesBefore(A, B); -} Index: llvm/lib/Analysis/OrderedInstructions.cpp =================================================================== --- llvm/lib/Analysis/OrderedInstructions.cpp +++ llvm/lib/Analysis/OrderedInstructions.cpp @@ -19,16 +19,11 @@ assert(InstA->getParent() == InstB->getParent() && "Instructions must be in the same basic block"); - const BasicBlock *IBB = InstA->getParent(); - auto OBB = OBBMap.find(IBB); - if (OBB == OBBMap.end()) - OBB = OBBMap.insert({IBB, make_unique(IBB)}).first; - return OBB->second->dominates(InstA, InstB); + return InstA->comesBefore(InstB); } -/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation -/// if the instructions are in the same basic block, Otherwise, use dominator -/// tree. +/// Given 2 instructions, check for dominance relation if the instructions are +/// in the same basic block. Otherwise, use dominator tree. bool OrderedInstructions::dominates(const Instruction *InstA, const Instruction *InstB) const { // Use ordered basic block to do dominance check in case the 2 instructions Index: llvm/lib/IR/BasicBlock.cpp =================================================================== --- llvm/lib/IR/BasicBlock.cpp +++ llvm/lib/IR/BasicBlock.cpp @@ -34,6 +34,10 @@ return getType()->getContext(); } +template <> void llvm::notifyParentOfInsertions(BasicBlock *BB) { + BB->invalidateOrders(); +} + // Explicit instantiation of SymbolTableListTraits since some of the methods // are not in the public header file... template class llvm::SymbolTableListTraits; @@ -485,3 +489,13 @@ ++It; return It; } + +void BasicBlock::renumberInstructions() { + unsigned Order = 0; + for (Instruction &I : *this) + I.Order = Order++; + + // Set the low bit in the subclass data to mark the instruction ordering as + // valid. + setValueSubclassData(getSubclassDataFromValue() | 1U); +} Index: llvm/lib/IR/Instruction.cpp =================================================================== --- llvm/lib/IR/Instruction.cpp +++ llvm/lib/IR/Instruction.cpp @@ -98,6 +98,13 @@ BB.getInstList().splice(I, getParent()->getInstList(), getIterator()); } +bool Instruction::comesBefore(const Instruction *Other) const { + assert(Parent == Other->Parent && "cross-BB instruction order comparison"); + if (!Parent->isInstrOrderValid()) + Parent->renumberInstructions(); + return Order < Other->Order; +} + void Instruction::setHasNoUnsignedWrap(bool b) { cast(this)->setHasNoUnsignedWrap(b); } Index: llvm/lib/IR/SymbolTableListTraitsImpl.h =================================================================== --- llvm/lib/IR/SymbolTableListTraitsImpl.h +++ llvm/lib/IR/SymbolTableListTraitsImpl.h @@ -21,6 +21,11 @@ namespace llvm { +/// Notify basic blocks when an instruction is inserted. +template +inline void notifyParentOfInsertions(ParentClass *Parent) {} +template <> void notifyParentOfInsertions(BasicBlock *BB); + /// setSymTabObject - This is called when (f.e.) the parent of a basic block /// changes. This requires us to remove all the instruction symtab entries from /// the current function and reinsert them into the new function. @@ -65,6 +70,7 @@ assert(!V->getParent() && "Value already in a container!!"); ItemParentClass *Owner = getListOwner(); V->setParent(Owner); + notifyParentOfInsertions(Owner); if (V->hasName()) if (ValueSymbolTable *ST = getSymTab(Owner)) ST->reinsertValue(V); Index: llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -1072,8 +1072,7 @@ 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. + // FIXME: Don't maintain our own ordering. Use Instruction::comesBefore. size_t LastThrowingInstIndex = 0; DenseMap InstrOrdering; size_t InstrIndex = 1; Index: llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp =================================================================== --- llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp +++ llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp @@ -50,7 +50,6 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/MemoryLocation.h" -#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Transforms/Utils/Local.h" @@ -470,7 +469,6 @@ } void Vectorizer::reorder(Instruction *I) { - OrderedBasicBlock OBB(I->getParent()); SmallPtrSet InstructionsToMove; SmallVector Worklist; @@ -488,7 +486,7 @@ if (IM->getParent() != I->getParent()) continue; - if (!OBB.dominates(IM, I)) { + if (!IM->comesBefore(I)) { InstructionsToMove.insert(IM); Worklist.push_back(IM); } @@ -604,8 +602,6 @@ } } - OrderedBasicBlock OBB(Chain[0]->getParent()); - // Loop until we find an instruction in ChainInstrs that we can't vectorize. unsigned ChainInstrIdx = 0; Instruction *BarrierMemoryInstr = nullptr; @@ -615,14 +611,14 @@ // If a barrier memory instruction was found, chain instructions that follow // will not be added to the valid prefix. - if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr)) + if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(ChainInstr)) break; // Check (in BB order) if any instruction prevents ChainInstr from being // vectorized. Find and store the first such "conflicting" instruction. for (Instruction *MemInstr : MemoryInstrs) { // If a barrier memory instruction was found, do not check past it. - if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr)) + if (BarrierMemoryInstr && BarrierMemoryInstr->comesBefore(MemInstr)) break; auto *MemLoad = dyn_cast(MemInstr); @@ -641,12 +637,12 @@ // vectorize it (the vectorized load is inserted at the location of the // first load in the chain). if (isa(MemInstr) && ChainLoad && - (IsInvariantLoad(ChainLoad) || OBB.dominates(ChainLoad, MemInstr))) + (IsInvariantLoad(ChainLoad) || ChainLoad->comesBefore(MemInstr))) continue; // Same case, but in reverse. if (MemLoad && isa(ChainInstr) && - (IsInvariantLoad(MemLoad) || OBB.dominates(MemLoad, ChainInstr))) + (IsInvariantLoad(MemLoad) || MemLoad->comesBefore(ChainInstr))) continue; if (!AA.isNoAlias(MemoryLocation::get(MemInstr), @@ -672,7 +668,7 @@ // the basic block. if (IsLoadChain && BarrierMemoryInstr) { // The BarrierMemoryInstr is a store that precedes ChainInstr. - assert(OBB.dominates(BarrierMemoryInstr, ChainInstr)); + assert(BarrierMemoryInstr->comesBefore(ChainInstr)); break; } } Index: llvm/unittests/Analysis/CMakeLists.txt =================================================================== --- llvm/unittests/Analysis/CMakeLists.txt +++ llvm/unittests/Analysis/CMakeLists.txt @@ -19,7 +19,6 @@ LoopInfoTest.cpp MemoryBuiltinsTest.cpp MemorySSATest.cpp - OrderedBasicBlockTest.cpp OrderedInstructionsTest.cpp PhiValuesTest.cpp ProfileSummaryInfoTest.cpp Index: llvm/unittests/Analysis/OrderedBasicBlockTest.cpp =================================================================== --- llvm/unittests/Analysis/OrderedBasicBlockTest.cpp +++ /dev/null @@ -1,58 +0,0 @@ -//===- OrderedBasicBlockTest.cpp - OrderedBasicBlock unit tests -----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/OrderedBasicBlock.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/DataTypes.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -namespace llvm { -namespace { - -class OrderedBasicBlockTest : public testing::Test { -protected: - LLVMContext C; - - std::unique_ptr makeLLVMModule() { - const char *ModuleString = R"(define i32 @f(i32 %x) { - %add = add i32 %x, 42 - ret i32 %add - })"; - SMDiagnostic Err; - auto foo = parseAssemblyString(ModuleString, Err, C); - return foo; - } -}; - -TEST_F(OrderedBasicBlockTest, Basic) { - auto M = makeLLVMModule(); - Function *F = M->getFunction("f"); - BasicBlock::iterator I = F->front().begin(); - Instruction *Add = &*I++; - Instruction *Ret = &*I++; - - OrderedBasicBlock OBB(&F->front()); - // Intentionally duplicated to verify cached and uncached are the same. - EXPECT_FALSE(OBB.dominates(Add, Add)); - EXPECT_FALSE(OBB.dominates(Add, Add)); - EXPECT_TRUE(OBB.dominates(Add, Ret)); - EXPECT_TRUE(OBB.dominates(Add, Ret)); - EXPECT_FALSE(OBB.dominates(Ret, Add)); - EXPECT_FALSE(OBB.dominates(Ret, Add)); - EXPECT_FALSE(OBB.dominates(Ret, Ret)); - EXPECT_FALSE(OBB.dominates(Ret, Ret)); -} - -} // end anonymous namespace -} // end namespace llvm Index: llvm/unittests/IR/BasicBlockTest.cpp =================================================================== --- llvm/unittests/IR/BasicBlockTest.cpp +++ llvm/unittests/IR/BasicBlockTest.cpp @@ -9,11 +9,13 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/AsmParser/Parser.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/NoFolder.h" +#include "llvm/Support/SourceMgr.h" #include "gmock/gmock-matchers.h" #include "gtest/gtest.h" #include @@ -128,5 +130,35 @@ delete V; } +TEST(BasicBlockTest, ComesBefore) { + const char *ModuleString = R"(define i32 @f(i32 %x) { + %add = add i32 %x, 42 + ret i32 %add + })"; + LLVMContext Ctx; + SMDiagnostic Err; + auto M = parseAssemblyString(ModuleString, Err, Ctx); + ASSERT_TRUE(M.get()); + + Function *F = M->getFunction("f"); + BasicBlock &BB = F->front(); + BasicBlock::iterator I = BB.begin(); + Instruction *Add = &*I++; + Instruction *Ret = &*I++; + + // Intentionally duplicated to verify cached and uncached are the same. + EXPECT_FALSE(Add->comesBefore(Add)); + EXPECT_FALSE(Add->comesBefore(Add)); + BB.invalidateOrders(); + EXPECT_TRUE(Add->comesBefore(Ret)); + EXPECT_TRUE(Add->comesBefore(Ret)); + BB.invalidateOrders(); + EXPECT_FALSE(Ret->comesBefore(Add)); + EXPECT_FALSE(Ret->comesBefore(Add)); + BB.invalidateOrders(); + EXPECT_FALSE(Ret->comesBefore(Ret)); + EXPECT_FALSE(Ret->comesBefore(Ret)); +} + } // End anonymous namespace. } // End llvm namespace.