Index: llvm/include/llvm/ADT/ilist.h =================================================================== --- llvm/include/llvm/ADT/ilist.h +++ llvm/include/llvm/ADT/ilist.h @@ -66,9 +66,8 @@ void addNodeToList(NodeTy *) {} void removeNodeFromList(NodeTy *) {} - /// Callback before transferring nodes to this list. - /// - /// \pre \c this!=&OldList + /// Callback before transferring nodes to this list. The nodes may already be + /// in this same list. template void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, Iterator /*last*/) { @@ -287,8 +286,8 @@ if (position == last) return; - if (this != &L2) // Notify traits we moved the nodes... - this->transferNodesFromList(L2, first, last); + // Notify traits we moved the nodes... + this->transferNodesFromList(L2, first, last); base_list_type::splice(position, L2, first, last); } Index: llvm/include/llvm/Analysis/AliasAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/AliasAnalysis.h +++ llvm/include/llvm/Analysis/AliasAnalysis.h @@ -645,19 +645,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; /// The default value for MaxUsesToExplore argument. It's relatively small to /// keep the cost of analysis reasonable for clients like BasicAliasAnalysis, @@ -53,14 +52,12 @@ /// 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. /// MaxUsesToExplore specifies how many uses should the analysis explore for /// one value before giving up due too "too many uses". bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI = false, - OrderedBasicBlock *OBB = nullptr, unsigned MaxUsesToExplore = DefaultMaxUsesToExplore); /// This callback is used in conjunction with PointerMayBeCaptured. In 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/CodeGen/MachineFunction.h =================================================================== --- llvm/include/llvm/CodeGen/MachineFunction.h +++ llvm/include/llvm/CodeGen/MachineFunction.h @@ -86,7 +86,7 @@ template void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator) { - llvm_unreachable("Never transfer between lists"); + assert(this == &OldList && "never transfer MBBs between functions"); } }; Index: llvm/include/llvm/IR/BasicBlock.h =================================================================== --- llvm/include/llvm/IR/BasicBlock.h +++ llvm/include/llvm/IR/BasicBlock.h @@ -389,7 +389,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 getBasicBlockBits().BlockAddressRefCount != 0; + } /// Update all phi nodes in this basic block's successors to refer to basic /// block \p New instead of to it. @@ -416,16 +418,61 @@ Optional getIrrLoopHeaderWeight() const; + /// Returns true if the Order field of child Instructions is valid. + bool isInstrOrderValid() const { + return getBasicBlockBits().InstrOrderValid; + } + + /// Mark instruction ordering invalid. Done on every instruction insert. + void invalidateOrders() { + validateInstrOrdering(); + BasicBlockBits Bits = getBasicBlockBits(); + Bits.InstrOrderValid = false; + setBasicBlockBits(Bits); + } + + /// Renumber instructions and mark the ordering as valid. + void renumberInstructions(); + + /// Returns false if the instruction ordering is incorrect in an debug build. + /// Always returns true when assertions are disabled. The method does not + /// assert internally so that we get better location info. + void validateInstrOrdering() const; + private: + /// Bitfield to help interpret the bits in Value::SubclassData. + struct BasicBlockBits { + unsigned short BlockAddressRefCount : 15; + unsigned short InstrOrderValid : 1; + }; + + /// Safely reinterpret the subclass data bits to a more useful form. + BasicBlockBits getBasicBlockBits() const { + static_assert(sizeof(BasicBlockBits) == sizeof(unsigned short), + "too many bits for Value::SubclassData"); + unsigned short ValueData = getSubclassDataFromValue(); + BasicBlockBits AsBits; + memcpy(&AsBits, &ValueData, sizeof(AsBits)); + return AsBits; + } + + /// Reinterpret our subclass bits and store them back into Value. + void setBasicBlockBits(BasicBlockBits AsBits) { + unsigned short D; + memcpy(&D, &AsBits, sizeof(D)); + Value::setValueSubclassData(D); + } + /// Increment the internal refcount of the number of BlockAddresses /// referencing this BasicBlock by \p Amt. /// /// 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 && - "Refcount wrap-around"); + BasicBlockBits Bits = getBasicBlockBits(); + Bits.BlockAddressRefCount += Amt; + setBasicBlockBits(Bits); + assert(Bits.BlockAddressRefCount < 255 && "Refcount wrap-around"); } /// Shadow Value::setValueSubclassData with a private forwarding method so @@ -442,6 +489,12 @@ /// This assumes that \p It is not at the end of a block. BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It); +#ifdef NDEBUG +/// In release builds, this is a no-op. For !NDEBUG builds, the checks are +/// implemented in the .cpp file to avoid circular header deps. +inline void Instruction::validateInstrOrdering() const {} +#endif + } // end namespace llvm #endif // LLVM_IR_BASICBLOCK_H 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. //===--------------------------------------------------------------------===// @@ -714,6 +725,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/lib/Analysis/AliasAnalysis.cpp =================================================================== --- llvm/lib/Analysis/AliasAnalysis.cpp +++ llvm/lib/Analysis/AliasAnalysis.cpp @@ -542,16 +542,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; @@ -567,8 +565,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 @@ -67,7 +67,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/Constants.h" #include "llvm/IR/Dominators.h" @@ -61,8 +60,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; } @@ -75,9 +74,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. // @@ -87,7 +84,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 @@ -138,7 +135,6 @@ return true; } - OrderedBasicBlock *OrderedBB; const Instruction *BeforeHere; const DominatorTree *DT; @@ -181,31 +177,23 @@ /// 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, unsigned MaxUsesToExplore) { 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, MaxUsesToExplore); - 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, MaxUsesToExplore); - - if (UseNewOBB) - delete OBB; return CB.Captured; } Index: llvm/lib/Analysis/InstructionPrecedenceTracking.cpp =================================================================== --- llvm/lib/Analysis/InstructionPrecedenceTracking.cpp +++ llvm/lib/Analysis/InstructionPrecedenceTracking.cpp @@ -103,18 +103,14 @@ const BasicBlock *BB) { if (isSpecialInstruction(Inst)) FirstSpecialInsts.erase(BB); - OI.invalidateBlock(BB); } void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) { if (isSpecialInstruction(Inst)) FirstSpecialInsts.erase(Inst->getParent()); - OI.invalidateBlock(Inst->getParent()); } void InstructionPrecedenceTracking::clear() { - for (auto It : FirstSpecialInsts) - OI.invalidateBlock(It.first); FirstSpecialInsts.clear(); #ifndef NDEBUG // The map should be valid after clearing (at least empty). 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" @@ -488,12 +487,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 { @@ -683,7 +676,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,88 +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"); - assert(A->getParent() == BB && "Instruction supposed to be in the block!"); - assert(B->getParent() == BB && "Instruction supposed to be in the block!"); - - // 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!"); - assert(A->getParent() == BB && "Instructions must be in the tracked 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/CodeGen/MachineBasicBlock.cpp =================================================================== --- llvm/lib/CodeGen/MachineBasicBlock.cpp +++ llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -133,8 +133,12 @@ instr_iterator First, instr_iterator Last) { assert(Parent->getParent() == FromList.Parent->getParent() && - "MachineInstr parent mismatch!"); - assert(this != &FromList && "Called without a real transfer..."); + "cannot transfer MachineInstrs between MachineFunctions"); + + // If it's within the same BB, there's nothing to do. + if (this == &FromList) + return; + assert(Parent != FromList.Parent && "Two lists have the same parent?"); // If splicing between two blocks within the same function, just update the 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::invalidateParentIListOrdering(BasicBlock *BB) { + BB->invalidateOrders(); +} + // Explicit instantiation of SymbolTableListTraits since some of the methods // are not in the public header file... template class llvm::SymbolTableListTraits; @@ -62,6 +66,8 @@ } BasicBlock::~BasicBlock() { + validateInstrOrdering(); + // If the address of the block is taken and it is being deleted (e.g. because // it is dead), this means that there is either a dangling constant expr // hanging off the block, or an undefined use of the block (source code @@ -492,3 +498,29 @@ ++It; return It; } + +void BasicBlock::renumberInstructions() { + unsigned Order = 0; + for (Instruction &I : *this) + I.Order = Order++; + + // Set the bit to indicate that the instruction order valid and cached. + BasicBlockBits Bits = getBasicBlockBits(); + Bits.InstrOrderValid = true; + setBasicBlockBits(Bits); +} + +#ifndef NDEBUG +/// In asserts builds, this checks the numbering. In non-asserts builds, it +/// is defined as an inline function returning true in BasicBlock.h. +void BasicBlock::validateInstrOrdering() const { + if (!isInstrOrderValid()) + return; + const Instruction *Prev = nullptr; + for (const Instruction &I : *this) { + assert((!Prev || Prev->comesBefore(&I)) && + "cached instruction ordering is incorrect"); + Prev = &I; + } +} +#endif Index: llvm/lib/IR/Instruction.cpp =================================================================== --- llvm/lib/IR/Instruction.cpp +++ llvm/lib/IR/Instruction.cpp @@ -98,6 +98,15 @@ BB.getInstList().splice(I, getParent()->getInstList(), getIterator()); } +bool Instruction::comesBefore(const Instruction *Other) const { + assert(Parent && Other->Parent && + "instructions without BB parents have no order"); + 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 invalidateParentIListOrdering(ParentClass *Parent) {} +template <> void invalidateParentIListOrdering(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); + invalidateParentIListOrdering(Owner); if (V->hasName()) if (ValueSymbolTable *ST = getSymTab(Owner)) ST->reinsertValue(V); @@ -82,9 +88,15 @@ template void SymbolTableListTraits::transferNodesFromList( SymbolTableListTraits &L2, iterator first, iterator last) { - // We only have to do work here if transferring instructions between BBs - ItemParentClass *NewIP = getListOwner(), *OldIP = L2.getListOwner(); - assert(NewIP != OldIP && "Expected different list owners"); + // Transfering nodes, even within the same BB, invalidates the ordering. The + // list that we removed the nodes from still has a valid ordering. + ItemParentClass *NewIP = getListOwner(); + invalidateParentIListOrdering(NewIP); + + // Nothing else needs to be done if we're reording nodes within the same list. + ItemParentClass *OldIP = L2.getListOwner(); + if (NewIP == OldIP) + return; // We only have to update symbol table entries if we are transferring the // instructions to a different symtab object... Index: llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -1073,8 +1073,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" @@ -488,7 +487,6 @@ } void Vectorizer::reorder(Instruction *I) { - OrderedBasicBlock OBB(I->getParent()); SmallPtrSet InstructionsToMove; SmallVector Worklist; @@ -506,7 +504,7 @@ if (IM->getParent() != I->getParent()) continue; - if (!OBB.dominates(IM, I)) { + if (!IM->comesBefore(I)) { InstructionsToMove.insert(IM); Worklist.push_back(IM); } @@ -622,8 +620,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; @@ -633,14 +629,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); @@ -659,12 +655,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), @@ -690,7 +686,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 @@ -22,7 +22,6 @@ LoopInfoTest.cpp MemoryBuiltinsTest.cpp MemorySSATest.cpp - OrderedBasicBlockTest.cpp OrderedInstructionsTest.cpp PhiValuesTest.cpp ProfileSummaryInfoTest.cpp Index: llvm/unittests/Analysis/CaptureTrackingTest.cpp =================================================================== --- llvm/unittests/Analysis/CaptureTrackingTest.cpp +++ llvm/unittests/Analysis/CaptureTrackingTest.cpp @@ -8,7 +8,6 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CaptureTracking.h" -#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" @@ -63,14 +62,13 @@ BasicBlock *EntryBB = &F->getEntryBlock(); DominatorTree DT(*F); - OrderedBasicBlock OBB(EntryBB); Instruction *Ret = EntryBB->getTerminator(); ASSERT_TRUE(isa(Ret)); - ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false, - &OBB, FalseMaxUsesLimit)); + ASSERT_FALSE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false, + FalseMaxUsesLimit)); ASSERT_TRUE(PointerMayBeCapturedBefore(Arg, true, true, Ret, &DT, false, - &OBB, TrueMaxUsesLimit)); + TrueMaxUsesLimit)); }; Test("test_few_uses", 6, 4); 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,130 @@ 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(BB.isInstrOrderValid()); + EXPECT_FALSE(Add->comesBefore(Add)); + EXPECT_TRUE(BB.isInstrOrderValid()); + EXPECT_FALSE(Add->comesBefore(Add)); + BB.invalidateOrders(); + EXPECT_FALSE(BB.isInstrOrderValid()); + EXPECT_TRUE(Add->comesBefore(Ret)); + EXPECT_TRUE(BB.isInstrOrderValid()); + 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)); +} + +class InstrOrderInvalidationTest : public ::testing::Test { +protected: + void SetUp() override { + M.reset(new Module("MyModule", Ctx)); + Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing); + FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false); + Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M); + BB = BasicBlock::Create(Ctx, "entry", F); + + IRBuilder<> Builder(BB); + I1 = Builder.CreateCall(Nop); + I2 = Builder.CreateCall(Nop); + I3 = Builder.CreateCall(Nop); + Ret = Builder.CreateRetVoid(); + } + + LLVMContext Ctx; + std::unique_ptr M; + Function *Nop = nullptr; + BasicBlock *BB = nullptr; + Instruction *I1 = nullptr; + Instruction *I2 = nullptr; + Instruction *I3 = nullptr; + Instruction *Ret = nullptr; +}; + +TEST_F(InstrOrderInvalidationTest, InsertInvalidation) { + EXPECT_FALSE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I2)); + EXPECT_TRUE(BB->isInstrOrderValid()); + EXPECT_TRUE(I2->comesBefore(I3)); + EXPECT_TRUE(I3->comesBefore(Ret)); + EXPECT_TRUE(BB->isInstrOrderValid()); + + // Invalidate orders. + IRBuilder<> Builder(BB, I2->getIterator()); + Instruction *I1a = Builder.CreateCall(Nop); + EXPECT_FALSE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I1a)); + EXPECT_TRUE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1a->comesBefore(I2)); + EXPECT_TRUE(I2->comesBefore(I3)); + EXPECT_TRUE(I3->comesBefore(Ret)); + EXPECT_TRUE(BB->isInstrOrderValid()); +} + +TEST_F(InstrOrderInvalidationTest, SpliceInvalidation) { + EXPECT_TRUE(I1->comesBefore(I2)); + EXPECT_TRUE(I2->comesBefore(I3)); + EXPECT_TRUE(I3->comesBefore(Ret)); + EXPECT_TRUE(BB->isInstrOrderValid()); + + // Use Instruction::moveBefore, which uses splice. + I2->moveBefore(I1); + EXPECT_FALSE(BB->isInstrOrderValid()); + + EXPECT_TRUE(I2->comesBefore(I1)); + EXPECT_TRUE(I1->comesBefore(I3)); + EXPECT_TRUE(I3->comesBefore(Ret)); + EXPECT_TRUE(BB->isInstrOrderValid()); +} + +TEST_F(InstrOrderInvalidationTest, RemoveNoInvalidation) { + // Cache the instruction order. + EXPECT_FALSE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I2)); + EXPECT_TRUE(BB->isInstrOrderValid()); + + // Removing does not invalidate instruction order. + I2->removeFromParent(); + I2->deleteValue(); + I2 = nullptr; + EXPECT_TRUE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I3)); + EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator()); +} + +TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) { + // Cache the instruction order. + EXPECT_FALSE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I2)); + EXPECT_TRUE(BB->isInstrOrderValid()); + + // Removing does not invalidate instruction order. + I2->eraseFromParent(); + I2 = nullptr; + EXPECT_TRUE(BB->isInstrOrderValid()); + EXPECT_TRUE(I1->comesBefore(I3)); + EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator()); +} + } // End anonymous namespace. } // End llvm namespace.