X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSlotIndexes.h;h=7b621bee259ffe3f9110787bece4e2b35be64617;hb=c75c50f45b3d6d1d61ce6b411d12cedaadd71d5b;hp=3c56d0d67dd91111210c528352401983df399f93;hpb=1ca6531e2e8e1b3a4f6c48888568450ecf614004;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 3c56d0d67dd..7b621bee259 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -7,26 +7,26 @@ // //===----------------------------------------------------------------------===// // -// This file implements SlotIndex and related classes. The purpuse of SlotIndex +// This file implements SlotIndex and related classes. The purpose of SlotIndex // is to describe a position at which a register can become live, or cease to // be live. // // SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which // is held is LiveIntervals and provides the real numbering. This allows -// LiveIntervals to perform largely transparent renumbering. The SlotIndex -// class does hold a PHI bit, which determines whether the index relates to a -// PHI use or def point, or an actual instruction. See the SlotIndex class -// description for futher information. +// LiveIntervals to perform largely transparent renumbering. //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_SLOTINDEXES_H #define LLVM_CODEGEN_SLOTINDEXES_H -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IntervalMap.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ilist.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/Support/Allocator.h" namespace llvm { @@ -35,162 +35,135 @@ namespace llvm { /// SlotIndexes pass. It should not be used directly. See the /// SlotIndex & SlotIndexes classes for the public interface to this /// information. - class IndexListEntry { - static const unsigned EMPTY_KEY_INDEX = ~0U & ~3U, - TOMBSTONE_KEY_INDEX = ~0U & ~7U; - - IndexListEntry *next, *prev; + class IndexListEntry : public ilist_node { MachineInstr *mi; unsigned index; - protected: - - typedef enum { EMPTY_KEY, TOMBSTONE_KEY } ReservedEntryType; - - // This constructor is only to be used by getEmptyKeyEntry - // & getTombstoneKeyEntry. It sets index to the given - // value and mi to zero. - IndexListEntry(ReservedEntryType r) : mi(0) { - switch(r) { - case EMPTY_KEY: index = EMPTY_KEY_INDEX; break; - case TOMBSTONE_KEY: index = TOMBSTONE_KEY_INDEX; break; - default: assert(false && "Invalid value for constructor."); - } - next = this; - prev = this; - } - public: - IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to create invalid index. " - "Available indexes may have been exhausted?."); - } - - bool isValid() const { - return (index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX); - } + IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} MachineInstr* getInstr() const { return mi; } void setInstr(MachineInstr *mi) { - assert(isValid() && "Attempt to modify reserved index."); this->mi = mi; } unsigned getIndex() const { return index; } void setIndex(unsigned index) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to set index to invalid value."); - assert(isValid() && "Attempt to reset reserved index value."); this->index = index; } - - IndexListEntry* getNext() { return next; } - const IndexListEntry* getNext() const { return next; } - void setNext(IndexListEntry *next) { - assert(isValid() && "Attempt to modify reserved index."); - this->next = next; - } - IndexListEntry* getPrev() { return prev; } - const IndexListEntry* getPrev() const { return prev; } - void setPrev(IndexListEntry *prev) { - assert(isValid() && "Attempt to modify reserved index."); - this->prev = prev; +#ifdef EXPENSIVE_CHECKS + // When EXPENSIVE_CHECKS is defined, "erased" index list entries will + // actually be moved to a "graveyard" list, and have their pointers + // poisoned, so that dangling SlotIndex access can be reliably detected. + void setPoison() { + intptr_t tmp = reinterpret_cast(mi); + assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); + tmp |= 0x1; + mi = reinterpret_cast(tmp); } - // This function returns the index list entry that is to be used for empty - // SlotIndex keys. - static IndexListEntry* getEmptyKeyEntry(); + bool isPoisoned() const { return (reinterpret_cast(mi) & 0x1) == 0x1; } +#endif // EXPENSIVE_CHECKS - // This function returns the index list entry that is to be used for - // tombstone SlotIndex keys. - static IndexListEntry* getTombstoneKeyEntry(); }; - // Specialize PointerLikeTypeTraits for IndexListEntry. template <> - class PointerLikeTypeTraits { + struct ilist_traits : public ilist_default_traits { + private: + mutable ilist_half_node Sentinel; public: - static inline void* getAsVoidPointer(IndexListEntry *p) { - return p; + IndexListEntry *createSentinel() const { + return static_cast(&Sentinel); } - static inline IndexListEntry* getFromVoidPointer(void *p) { - return static_cast(p); - } - enum { NumLowBitsAvailable = 3 }; + void destroySentinel(IndexListEntry *) const {} + + IndexListEntry *provideInitialHead() const { return createSentinel(); } + IndexListEntry *ensureHead(IndexListEntry*) const { return createSentinel(); } + static void noteHead(IndexListEntry*, IndexListEntry*) {} + void deleteNode(IndexListEntry *N) {} + + private: + void createNode(const IndexListEntry &); }; /// SlotIndex - An opaque wrapper around machine indexes. class SlotIndex { friend class SlotIndexes; - friend struct DenseMapInfo; - private: - static const unsigned PHI_BIT = 1 << 2; + enum Slot { + /// Basic block boundary. Used for live ranges entering and leaving a + /// block without being live in the layout neighbor. Also used as the + /// def slot of PHI-defs. + Slot_Block, - PointerIntPair lie; + /// Early-clobber register use/def slot. A live range defined at + /// Slot_EarlyCLobber interferes with normal live ranges killed at + /// Slot_Register. Also used as the kill slot for live ranges tied to an + /// early-clobber def. + Slot_EarlyClobber, - SlotIndex(IndexListEntry *entry, unsigned phiAndSlot) - : lie(entry, phiAndSlot) { - assert(entry != 0 && "Attempt to construct index with 0 pointer."); - } + /// Normal register use/def slot. Normal instructions kill and define + /// register live ranges at this slot. + Slot_Register, - IndexListEntry& entry() const { - return *lie.getPointer(); - } + /// Dead def kill point. Kill slot for a live range that is defined by + /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't + /// used anywhere. + Slot_Dead, - int getIndex() const { - return entry().getIndex() | getSlot(); - } - - static inline unsigned getHashValue(const SlotIndex &v) { - IndexListEntry *ptrVal = &v.entry(); - return (unsigned((intptr_t)ptrVal) >> 4) ^ - (unsigned((intptr_t)ptrVal) >> 9); - } + Slot_Count + }; - public: + PointerIntPair lie; - // FIXME: Ugh. This is public because LiveIntervalAnalysis is still using it - // for some spill weight stuff. Fix that, then make this private. - enum Slot { LOAD, USE, DEF, STORE, NUM }; + SlotIndex(IndexListEntry *entry, unsigned slot) + : lie(entry, slot) {} - static inline SlotIndex getEmptyKey() { - return SlotIndex(IndexListEntry::getEmptyKeyEntry(), 0); + IndexListEntry* listEntry() const { + assert(isValid() && "Attempt to compare reserved index."); +#ifdef EXPENSIVE_CHECKS + assert(!lie.getPointer()->isPoisoned() && + "Attempt to access deleted list-entry."); +#endif // EXPENSIVE_CHECKS + return lie.getPointer(); } - static inline SlotIndex getTombstoneKey() { - return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0); + unsigned getIndex() const { + return listEntry()->getIndex() | getSlot(); } - - /// Construct an invalid index. - SlotIndex() : lie(IndexListEntry::getEmptyKeyEntry(), 0) {} - // Construct a new slot index from the given one, set the phi flag on the - // new index to the value of the phi parameter. - SlotIndex(const SlotIndex &li, bool phi) - : lie(&li.entry(), phi ? PHI_BIT | li.getSlot() : (unsigned)li.getSlot()){ - assert(lie.getPointer() != 0 && - "Attempt to construct index with 0 pointer."); + /// Returns the slot for this SlotIndex. + Slot getSlot() const { + return static_cast(lie.getInt()); } - // Construct a new slot index from the given one, set the phi flag on the - // new index to the value of the phi parameter, and the slot to the new slot. - SlotIndex(const SlotIndex &li, bool phi, Slot s) - : lie(&li.entry(), phi ? PHI_BIT | s : (unsigned)s) { - assert(lie.getPointer() != 0 && + public: + enum { + /// The default distance between instructions as returned by distance(). + /// This may vary as instructions are inserted and removed. + InstrDist = 4 * Slot_Count + }; + + /// Construct an invalid index. + SlotIndex() : lie(nullptr, 0) {} + + // Construct a new slot index from the given one, and set the slot. + SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) { + assert(lie.getPointer() != nullptr && "Attempt to construct index with 0 pointer."); } - /// Returns true if this is a valid index. Invalid indicies do + /// Returns true if this is a valid index. Invalid indices do /// not point into an index table, and cannot be compared. bool isValid() const { - IndexListEntry *entry = lie.getPointer(); - return ((entry!= 0) && (entry->isValid())); + return lie.getPointer(); } + /// Return true for a valid index. + explicit operator bool() const { return isValid(); } + /// Print this index to the given raw_ostream. void print(raw_ostream &os) const; @@ -199,13 +172,13 @@ namespace llvm { /// Compare two SlotIndex objects for equality. bool operator==(SlotIndex other) const { - return getIndex() == other.getIndex(); + return lie == other.lie; } /// Compare two SlotIndex objects for inequality. bool operator!=(SlotIndex other) const { - return getIndex() != other.getIndex(); + return lie != other.lie; } - + /// Compare two SlotIndex objects. Return true if the first index /// is strictly lower than the second. bool operator<(SlotIndex other) const { @@ -229,59 +202,67 @@ namespace llvm { return getIndex() >= other.getIndex(); } + /// isSameInstr - Return true if A and B refer to the same instruction. + static bool isSameInstr(SlotIndex A, SlotIndex B) { + return A.lie.getPointer() == B.lie.getPointer(); + } + + /// isEarlierInstr - Return true if A refers to an instruction earlier than + /// B. This is equivalent to A < B && !isSameInstr(A, B). + static bool isEarlierInstr(SlotIndex A, SlotIndex B) { + return A.listEntry()->getIndex() < B.listEntry()->getIndex(); + } + /// Return the distance from this index to the given one. int distance(SlotIndex other) const { return other.getIndex() - getIndex(); } - /// Returns the slot for this SlotIndex. - Slot getSlot() const { - return static_cast(lie.getInt() & ~PHI_BIT); + /// Return the scaled distance from this index to the given one, where all + /// slots on the same instruction have zero distance. + int getInstrDistance(SlotIndex other) const { + return (other.listEntry()->getIndex() - listEntry()->getIndex()) + / Slot_Count; } - /// Returns the state of the PHI bit. - bool isPHI() const { - return lie.getInt() & PHI_BIT; - } + /// isBlock - Returns true if this is a block boundary slot. + bool isBlock() const { return getSlot() == Slot_Block; } + + /// isEarlyClobber - Returns true if this is an early-clobber slot. + bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; } + + /// isRegister - Returns true if this is a normal register use/def slot. + /// Note that early-clobber slots may also be used for uses and defs. + bool isRegister() const { return getSlot() == Slot_Register; } + + /// isDead - Returns true if this is a dead def kill slot. + bool isDead() const { return getSlot() == Slot_Dead; } /// Returns the base index for associated with this index. The base index - /// is the one associated with the LOAD slot for the instruction pointed to - /// by this index. + /// is the one associated with the Slot_Block slot for the instruction + /// pointed to by this index. SlotIndex getBaseIndex() const { - return getLoadIndex(); + return SlotIndex(listEntry(), Slot_Block); } /// Returns the boundary index for associated with this index. The boundary - /// index is the one associated with the LOAD slot for the instruction + /// index is the one associated with the Slot_Block slot for the instruction /// pointed to by this index. SlotIndex getBoundaryIndex() const { - return getStoreIndex(); + return SlotIndex(listEntry(), Slot_Dead); } - /// Returns the index of the LOAD slot for the instruction pointed to by - /// this index. - SlotIndex getLoadIndex() const { - return SlotIndex(&entry(), SlotIndex::LOAD); - } - - /// Returns the index of the USE slot for the instruction pointed to by - /// this index. - SlotIndex getUseIndex() const { - return SlotIndex(&entry(), SlotIndex::USE); + /// Returns the register use/def slot in the current instruction for a + /// normal or early-clobber def. + SlotIndex getRegSlot(bool EC = false) const { + return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register); } - /// Returns the index of the DEF slot for the instruction pointed to by - /// this index. - SlotIndex getDefIndex() const { - return SlotIndex(&entry(), SlotIndex::DEF); + /// Returns the dead def kill slot for the current instruction. + SlotIndex getDeadSlot() const { + return SlotIndex(listEntry(), Slot_Dead); } - /// Returns the index of the STORE slot for the instruction pointed to by - /// this index. - SlotIndex getStoreIndex() const { - return SlotIndex(&entry(), SlotIndex::STORE); - } - /// Returns the next slot in the index list. This could be either the /// next slot for the instruction pointed to by this index or, if this /// index is a STORE, the first slot for the next instruction. @@ -290,60 +271,42 @@ namespace llvm { /// use one of those methods. SlotIndex getNextSlot() const { Slot s = getSlot(); - if (s == SlotIndex::STORE) { - return SlotIndex(entry().getNext(), SlotIndex::LOAD); + if (s == Slot_Dead) { + return SlotIndex(&*++listEntry()->getIterator(), Slot_Block); } - return SlotIndex(&entry(), s + 1); + return SlotIndex(listEntry(), s + 1); } /// Returns the next index. This is the index corresponding to the this /// index's slot, but for the next instruction. SlotIndex getNextIndex() const { - return SlotIndex(entry().getNext(), getSlot()); + return SlotIndex(&*++listEntry()->getIterator(), getSlot()); } /// Returns the previous slot in the index list. This could be either the /// previous slot for the instruction pointed to by this index or, if this - /// index is a LOAD, the last slot for the previous instruction. + /// index is a Slot_Block, the last slot for the previous instruction. /// WARNING: This method is considerably more expensive than the methods /// that return specific slots (getUseIndex(), etc). If you can - please /// use one of those methods. SlotIndex getPrevSlot() const { Slot s = getSlot(); - if (s == SlotIndex::LOAD) { - return SlotIndex(entry().getPrev(), SlotIndex::STORE); + if (s == Slot_Block) { + return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead); } - return SlotIndex(&entry(), s - 1); + return SlotIndex(listEntry(), s - 1); } /// Returns the previous index. This is the index corresponding to this /// index's slot, but for the previous instruction. SlotIndex getPrevIndex() const { - return SlotIndex(entry().getPrev(), getSlot()); + return SlotIndex(&*--listEntry()->getIterator(), getSlot()); } }; - /// DenseMapInfo specialization for SlotIndex. - template <> - struct DenseMapInfo { - static inline SlotIndex getEmptyKey() { - return SlotIndex::getEmptyKey(); - } - static inline SlotIndex getTombstoneKey() { - return SlotIndex::getTombstoneKey(); - } - static inline unsigned getHashValue(const SlotIndex &v) { - return SlotIndex::getHashValue(v); - } - static inline bool isEqual(const SlotIndex &LHS, const SlotIndex &RHS) { - return (LHS == RHS); - } - }; - template <> struct isPodLike { static const bool value = true; }; - inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) { li.print(os); return os; @@ -370,116 +333,58 @@ namespace llvm { /// This pass assigns indexes to each instruction. class SlotIndexes : public MachineFunctionPass { private: + // IndexListEntry allocator. + BumpPtrAllocator ileAllocator; + + typedef ilist IndexList; + IndexList indexList; + +#ifdef EXPENSIVE_CHECKS + IndexList graveyardList; +#endif // EXPENSIVE_CHECKS MachineFunction *mf; - IndexListEntry *indexListHead; - unsigned functionSize; typedef DenseMap Mi2IndexMap; Mi2IndexMap mi2iMap; - /// MBB2IdxMap - The indexes of the first and last instructions in the - /// specified basic block. - typedef DenseMap > MBB2IdxMap; - MBB2IdxMap mbb2IdxMap; + /// MBBRanges - Map MBB number to (start, stop) indexes. + SmallVector, 8> MBBRanges; /// Idx2MBBMap - Sorted list of pairs of index of first instruction /// and MBB id. - std::vector idx2MBBMap; - - typedef DenseMap TerminatorGapsMap; - TerminatorGapsMap terminatorGaps; - - // IndexListEntry allocator. - BumpPtrAllocator ileAllocator; + SmallVector idx2MBBMap; IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { IndexListEntry *entry = static_cast( ileAllocator.Allocate(sizeof(IndexListEntry), - alignof())); + alignOf())); new (entry) IndexListEntry(mi, index); return entry; } - void initList() { - assert(indexListHead == 0 && "Zero entry non-null at initialisation."); - indexListHead = createEntry(0, ~0U); - indexListHead->setNext(0); - indexListHead->setPrev(indexListHead); - } - - void clearList() { - indexListHead = 0; - ileAllocator.Reset(); - } - - IndexListEntry* getTail() { - assert(indexListHead != 0 && "Call to getTail on uninitialized list."); - return indexListHead->getPrev(); - } - - const IndexListEntry* getTail() const { - assert(indexListHead != 0 && "Call to getTail on uninitialized list."); - return indexListHead->getPrev(); - } - - // Returns true if the index list is empty. - bool empty() const { return (indexListHead == getTail()); } - - IndexListEntry* front() { - assert(!empty() && "front() called on empty index list."); - return indexListHead; - } - - const IndexListEntry* front() const { - assert(!empty() && "front() called on empty index list."); - return indexListHead; - } + /// Renumber locally after inserting curItr. + void renumberIndexes(IndexList::iterator curItr); - IndexListEntry* back() { - assert(!empty() && "back() called on empty index list."); - return getTail()->getPrev(); - } - - const IndexListEntry* back() const { - assert(!empty() && "back() called on empty index list."); - return getTail()->getPrev(); - } + public: + static char ID; - /// Insert a new entry before itr. - void insert(IndexListEntry *itr, IndexListEntry *val) { - assert(itr != 0 && "itr should not be null."); - IndexListEntry *prev = itr->getPrev(); - val->setNext(itr); - val->setPrev(prev); - - if (itr != indexListHead) { - prev->setNext(val); - } - else { - indexListHead = val; - } - itr->setPrev(val); + SlotIndexes() : MachineFunctionPass(ID) { + initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); } - /// Push a new entry on to the end of the list. - void push_back(IndexListEntry *val) { - insert(getTail(), val); + ~SlotIndexes() { + // The indexList's nodes are all allocated in the BumpPtrAllocator. + indexList.clearAndLeakNodesUnsafely(); } - public: - static char ID; + void getAnalysisUsage(AnalysisUsage &au) const override; + void releaseMemory() override; - SlotIndexes() : MachineFunctionPass(&ID), indexListHead(0) {} - - virtual void getAnalysisUsage(AnalysisUsage &au) const; - virtual void releaseMemory(); - - virtual bool runOnMachineFunction(MachineFunction &fn); + bool runOnMachineFunction(MachineFunction &fn) override; /// Dump the indexes. void dump() const; @@ -487,40 +392,32 @@ namespace llvm { /// Renumber the index list, providing space for new instructions. void renumberIndexes(); + /// Repair indexes after adding and removing instructions. + void repairIndexesInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End); + /// Returns the zero index for this analysis. SlotIndex getZeroIndex() { - assert(front()->getIndex() == 0 && "First index is not 0?"); - return SlotIndex(front(), 0); - } - - /// Returns the invalid index marker for this analysis. - SlotIndex getInvalidIndex() { - return getZeroIndex(); + assert(indexList.front().getIndex() == 0 && "First index is not 0?"); + return SlotIndex(&indexList.front(), 0); } - /// Returns the distance between the highest and lowest indexes allocated - /// so far. - unsigned getIndexesLength() const { - assert(front()->getIndex() == 0 && - "Initial index isn't zero?"); - - return back()->getIndex(); - } - - /// Returns the number of instructions in the function. - unsigned getFunctionSize() const { - return functionSize; + /// Returns the base index of the last slot in this analysis. + SlotIndex getLastIndex() { + return SlotIndex(&indexList.back(), 0); } /// Returns true if the given machine instr is mapped to an index, /// otherwise returns false. bool hasIndex(const MachineInstr *instr) const { - return (mi2iMap.find(instr) != mi2iMap.end()); + return mi2iMap.count(instr); } /// Returns the base index for the given instruction. - SlotIndex getInstructionIndex(const MachineInstr *instr) const { - Mi2IndexMap::const_iterator itr = mi2iMap.find(instr); + SlotIndex getInstructionIndex(const MachineInstr *MI) const { + // Instructions inside a bundle have the same number as the bundle itself. + Mi2IndexMap::const_iterator itr = mi2iMap.find(getBundleStart(MI)); assert(itr != mi2iMap.end() && "Instruction not found in maps."); return itr->second; } @@ -528,216 +425,204 @@ namespace llvm { /// Returns the instruction for the given index, or null if the given /// index has no instruction associated with it. MachineInstr* getInstructionFromIndex(SlotIndex index) const { - return index.entry().getInstr(); + return index.isValid() ? index.listEntry()->getInstr() : nullptr; + } + + /// Returns the next non-null index, if one exists. + /// Otherwise returns getLastIndex(). + SlotIndex getNextNonNullIndex(SlotIndex Index) { + IndexList::iterator I = Index.listEntry()->getIterator(); + IndexList::iterator E = indexList.end(); + while (++I != E) + if (I->getInstr()) + return SlotIndex(&*I, Index.getSlot()); + // We reached the end of the function. + return getLastIndex(); + } + + /// getIndexBefore - Returns the index of the last indexed instruction + /// before MI, or the start index of its basic block. + /// MI is not required to have an index. + SlotIndex getIndexBefore(const MachineInstr *MI) const { + const MachineBasicBlock *MBB = MI->getParent(); + assert(MBB && "MI must be inserted inna basic block"); + MachineBasicBlock::const_iterator I = MI, B = MBB->begin(); + for (;;) { + if (I == B) + return getMBBStartIdx(MBB); + --I; + Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); + if (MapItr != mi2iMap.end()) + return MapItr->second; + } } - /// Returns the next non-null index. - SlotIndex getNextNonNullIndex(SlotIndex index) { - SlotIndex nextNonNull = index.getNextIndex(); - - while (&nextNonNull.entry() != getTail() && - getInstructionFromIndex(nextNonNull) == 0) { - nextNonNull = nextNonNull.getNextIndex(); + /// getIndexAfter - Returns the index of the first indexed instruction + /// after MI, or the end index of its basic block. + /// MI is not required to have an index. + SlotIndex getIndexAfter(const MachineInstr *MI) const { + const MachineBasicBlock *MBB = MI->getParent(); + assert(MBB && "MI must be inserted inna basic block"); + MachineBasicBlock::const_iterator I = MI, E = MBB->end(); + for (;;) { + ++I; + if (I == E) + return getMBBEndIdx(MBB); + Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); + if (MapItr != mi2iMap.end()) + return MapItr->second; } + } + + /// Return the (start,end) range of the given basic block number. + const std::pair & + getMBBRange(unsigned Num) const { + return MBBRanges[Num]; + } - return nextNonNull; + /// Return the (start,end) range of the given basic block. + const std::pair & + getMBBRange(const MachineBasicBlock *MBB) const { + return getMBBRange(MBB->getNumber()); + } + + /// Returns the first index in the given basic block number. + SlotIndex getMBBStartIdx(unsigned Num) const { + return getMBBRange(Num).first; } /// Returns the first index in the given basic block. SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { - MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb); - assert(itr != mbb2IdxMap.end() && "MBB not found in maps."); - return itr->second.first; + return getMBBRange(mbb).first; + } + + /// Returns the last index in the given basic block number. + SlotIndex getMBBEndIdx(unsigned Num) const { + return getMBBRange(Num).second; } /// Returns the last index in the given basic block. SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { - MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb); - assert(itr != mbb2IdxMap.end() && "MBB not found in maps."); - return itr->second.second; + return getMBBRange(mbb).second; } - /// Returns the terminator gap for the given index. - SlotIndex getTerminatorGap(const MachineBasicBlock *mbb) { - TerminatorGapsMap::iterator itr = terminatorGaps.find(mbb); - assert(itr != terminatorGaps.end() && - "All MBBs should have terminator gaps in their indexes."); - return itr->second; + /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block + /// begin and basic block) + typedef SmallVectorImpl::const_iterator MBBIndexIterator; + /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or + /// equal to \p To. + MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const { + return std::lower_bound(I, idx2MBBMap.end(), To); + } + /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex + /// that is greater or equal to \p Idx. + MBBIndexIterator findMBBIndex(SlotIndex Idx) const { + return advanceMBBIndex(idx2MBBMap.begin(), Idx); + } + /// Returns an iterator for the begin of the idx2MBBMap. + MBBIndexIterator MBBIndexBegin() const { + return idx2MBBMap.begin(); + } + /// Return an iterator for the end of the idx2MBBMap. + MBBIndexIterator MBBIndexEnd() const { + return idx2MBBMap.end(); } /// Returns the basic block which the given index falls in. MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { - std::vector::const_iterator I = - std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index); + if (MachineInstr *MI = getInstructionFromIndex(index)) + return MI->getParent(); + + MBBIndexIterator I = findMBBIndex(index); // Take the pair containing the index - std::vector::const_iterator J = - ((I != idx2MBBMap.end() && I->first > index) || - (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I; + MBBIndexIterator J = + ((I != MBBIndexEnd() && I->first > index) || + (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I; - assert(J != idx2MBBMap.end() && J->first <= index && + assert(J != MBBIndexEnd() && J->first <= index && index < getMBBEndIdx(J->second) && "index does not correspond to an MBB"); return J->second; } - bool findLiveInMBBs(SlotIndex start, SlotIndex end, - SmallVectorImpl &mbbs) const { - std::vector::const_iterator itr = - std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); - bool resVal = false; - - while (itr != idx2MBBMap.end()) { - if (itr->first >= end) - break; - mbbs.push_back(itr->second); - resVal = true; - ++itr; - } - return resVal; - } - - /// Return a list of MBBs that can be reach via any branches or - /// fall-throughs. - bool findReachableMBBs(SlotIndex start, SlotIndex end, - SmallVectorImpl &mbbs) const { - std::vector::const_iterator itr = - std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); - - bool resVal = false; - while (itr != idx2MBBMap.end()) { - if (itr->first > end) - break; - MachineBasicBlock *mbb = itr->second; - if (getMBBEndIdx(mbb) > end) - break; - for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(), - se = mbb->succ_end(); si != se; ++si) - mbbs.push_back(*si); - resVal = true; - ++itr; - } - return resVal; - } - /// Returns the MBB covering the given range, or null if the range covers /// more than one basic block. MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { assert(start < end && "Backwards ranges not allowed."); - - std::vector::const_iterator itr = - std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); - - if (itr == idx2MBBMap.end()) { - itr = prior(itr); + MBBIndexIterator itr = findMBBIndex(start); + if (itr == MBBIndexEnd()) { + itr = std::prev(itr); return itr->second; } // Check that we don't cross the boundary into this block. if (itr->first < end) - return 0; + return nullptr; - itr = prior(itr); + itr = std::prev(itr); if (itr->first <= start) return itr->second; - return 0; + return nullptr; } /// Insert the given machine instruction into the mapping. Returns the /// assigned index. - SlotIndex insertMachineInstrInMaps(MachineInstr *mi, - bool *deferredRenumber = 0) { + /// If Late is set and there are null indexes between mi's neighboring + /// instructions, create the new index after the null indexes instead of + /// before them. + SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool Late = false) { + assert(!mi->isInsideBundle() && + "Instructions inside bundles should use bundle start's slot."); assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed."); - - MachineBasicBlock *mbb = mi->getParent(); - - assert(mbb != 0 && "Instr must be added to function."); - - MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb); - - assert(mbbRangeItr != mbb2IdxMap.end() && - "Instruction's parent MBB has not been added to SlotIndexes."); - - MachineBasicBlock::iterator miItr(mi); - bool needRenumber = false; - IndexListEntry *newEntry; - - IndexListEntry *prevEntry; - if (miItr == mbb->begin()) { - // If mi is at the mbb beginning, get the prev index from the mbb. - prevEntry = &mbbRangeItr->second.first.entry(); + // Numbering DBG_VALUE instructions could cause code generation to be + // affected by debug information. + assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions."); + + assert(mi->getParent() != nullptr && "Instr must be added to function."); + + // Get the entries where mi should be inserted. + IndexList::iterator prevItr, nextItr; + if (Late) { + // Insert mi's index immediately before the following instruction. + nextItr = getIndexAfter(mi).listEntry()->getIterator(); + prevItr = std::prev(nextItr); } else { - // Otherwise get it from the previous instr. - MachineBasicBlock::iterator pItr(prior(miItr)); - prevEntry = &getInstructionIndex(pItr).entry(); + // Insert mi's index immediately after the preceding instruction. + prevItr = getIndexBefore(mi).listEntry()->getIterator(); + nextItr = std::next(prevItr); } - // Get next entry from previous entry. - IndexListEntry *nextEntry = prevEntry->getNext(); - // Get a number for the new instr, or 0 if there's no room currently. // In the latter case we'll force a renumber later. - unsigned dist = nextEntry->getIndex() - prevEntry->getIndex(); - unsigned newNumber = dist > SlotIndex::NUM ? - prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0; - - if (newNumber == 0) { - needRenumber = true; - } + unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; + unsigned newNumber = prevItr->getIndex() + dist; // Insert a new list entry for mi. - newEntry = createEntry(mi, newNumber); - insert(nextEntry, newEntry); - - SlotIndex newIndex(newEntry, SlotIndex::LOAD); - mi2iMap.insert(std::make_pair(mi, newIndex)); - - if (miItr == mbb->end()) { - // If this is the last instr in the MBB then we need to fix up the bb - // range: - mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE); - } + IndexList::iterator newItr = + indexList.insert(nextItr, createEntry(mi, newNumber)); - // Renumber if we need to. - if (needRenumber) { - if (deferredRenumber == 0) - renumberIndexes(); - else - *deferredRenumber = true; - } + // Renumber locally if we need to. + if (dist == 0) + renumberIndexes(newItr); + SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); + mi2iMap.insert(std::make_pair(mi, newIndex)); return newIndex; } - /// Add all instructions in the vector to the index list. This method will - /// defer renumbering until all instrs have been added, and should be - /// preferred when adding multiple instrs. - void insertMachineInstrsInMaps(SmallVectorImpl &mis) { - bool renumber = false; - - for (SmallVectorImpl::iterator - miItr = mis.begin(), miEnd = mis.end(); - miItr != miEnd; ++miItr) { - insertMachineInstrInMaps(*miItr, &renumber); - } - - if (renumber) - renumberIndexes(); - } - - /// Remove the given machine instruction from the mapping. void removeMachineInstrFromMaps(MachineInstr *mi) { // remove index -> MachineInstr and // MachineInstr -> index mappings Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); if (mi2iItr != mi2iMap.end()) { - IndexListEntry *miEntry(&mi2iItr->second.entry()); + IndexListEntry *miEntry(mi2iItr->second.listEntry()); assert(miEntry->getInstr() == mi && "Instruction indexes broken."); // FIXME: Eventually we want to actually delete these indexes. - miEntry->setInstr(0); + miEntry->setInstr(nullptr); mi2iMap.erase(mi2iItr); } } @@ -749,7 +634,7 @@ namespace llvm { if (mi2iItr == mi2iMap.end()) return; SlotIndex replaceBaseIndex = mi2iItr->second; - IndexListEntry *miEntry(&replaceBaseIndex.entry()); + IndexListEntry *miEntry(replaceBaseIndex.listEntry()); assert(miEntry->getInstr() == mi && "Mismatched instruction in index tables."); miEntry->setInstr(newMI); @@ -757,9 +642,76 @@ namespace llvm { mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex)); } + /// Add the given MachineBasicBlock into the maps. + void insertMBBInMaps(MachineBasicBlock *mbb) { + MachineFunction::iterator nextMBB = + std::next(MachineFunction::iterator(mbb)); + + IndexListEntry *startEntry = nullptr; + IndexListEntry *endEntry = nullptr; + IndexList::iterator newItr; + if (nextMBB == mbb->getParent()->end()) { + startEntry = &indexList.back(); + endEntry = createEntry(nullptr, 0); + newItr = indexList.insertAfter(startEntry->getIterator(), endEntry); + } else { + startEntry = createEntry(nullptr, 0); + endEntry = getMBBStartIdx(&*nextMBB).listEntry(); + newItr = indexList.insert(endEntry->getIterator(), startEntry); + } + + SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); + SlotIndex endIdx(endEntry, SlotIndex::Slot_Block); + + MachineFunction::iterator prevMBB(mbb); + assert(prevMBB != mbb->getParent()->end() && + "Can't insert a new block at the beginning of a function."); + --prevMBB; + MBBRanges[prevMBB->getNumber()].second = startIdx; + + assert(unsigned(mbb->getNumber()) == MBBRanges.size() && + "Blocks must be added in order"); + MBBRanges.push_back(std::make_pair(startIdx, endIdx)); + idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); + + renumberIndexes(newItr); + std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); + } + + /// \brief Free the resources that were required to maintain a SlotIndex. + /// + /// Once an index is no longer needed (for instance because the instruction + /// at that index has been moved), the resources required to maintain the + /// index can be relinquished to reduce memory use and improve renumbering + /// performance. Any remaining SlotIndex objects that point to the same + /// index are left 'dangling' (much the same as a dangling pointer to a + /// freed object) and should not be accessed, except to destruct them. + /// + /// Like dangling pointers, access to dangling SlotIndexes can cause + /// painful-to-track-down bugs, especially if the memory for the index + /// previously pointed to has been re-used. To detect dangling SlotIndex + /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to + /// be retained in a graveyard instead of being freed. Operations on indexes + /// in the graveyard will trigger an assertion. + void eraseIndex(SlotIndex index) { + IndexListEntry *entry = index.listEntry(); +#ifdef EXPENSIVE_CHECKS + indexList.remove(entry); + graveyardList.push_back(entry); + entry->setPoison(); +#else + indexList.erase(entry); +#endif + } + }; + // Specialize IntervalMapInfo for half-open slot index intervals. + template <> + struct IntervalMapInfo : IntervalMapHalfOpenInfo { + }; + } -#endif // LLVM_CODEGEN_LIVEINDEX_H +#endif // LLVM_CODEGEN_SLOTINDEXES_H