X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSlotIndexes.h;h=0457e43e6b7b0b5145321ef405bc3db900c0322f;hb=23d59c2fb847f1869b72bcbda67052ac6b2aaee9;hp=294827dc65e6b51a35f4d37f895bdb45b8afa821;hpb=d71153577f41e3fed279599253dfaf38ca4243d5;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 294827dc65e..0457e43e6b7 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -7,151 +7,70 @@ // //===----------------------------------------------------------------------===// // -// 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/MachineInstrBundle.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/ilist.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/Support/Allocator.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/ManagedStatic.h" namespace llvm { - class EmptyIndexListEntry; - class TombstoneIndexListEntry; - /// This class represents an entry in the slot index list held in the /// SlotIndexes pass. It should not be used directly. See the /// SlotIndex & SlotIndexes classes for the public interface to this /// information. - class IndexListEntry { - private: - - static const unsigned EMPTY_KEY_INDEX = ~0U & ~3U, - TOMBSTONE_KEY_INDEX = ~0U & ~7U; - - // The following statics are thread safe. They're read only, and you - // can't step from them to any other list entries. - static ManagedStatic emptyKeyEntry; - static ManagedStatic tombstoneKeyEntry; - - 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) { - if (index == EMPTY_KEY_INDEX || index == TOMBSTONE_KEY_INDEX) { - llvm_report_error("Attempt to create invalid index. " - "Available indexes may have been exhausted?."); - } - } + IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} MachineInstr* getInstr() const { return mi; } void setInstr(MachineInstr *mi) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "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(this->index != EMPTY_KEY_INDEX && - this->index != TOMBSTONE_KEY_INDEX && - "Attempt to reset reserved index value."); this->index = index; } - - IndexListEntry* getNext() { return next; } - const IndexListEntry* getNext() const { return next; } - void setNext(IndexListEntry *next) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to modify reserved index."); - this->next = next; - } - - IndexListEntry* getPrev() { return prev; } - const IndexListEntry* getPrev() const { return prev; } - void setPrev(IndexListEntry *prev) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to modify reserved index."); - this->prev = prev; - } - - // This function returns the index list entry that is to be used for empty - // SlotIndex keys. - inline static IndexListEntry* getEmptyKeyEntry(); - - // This function returns the index list entry that is to be used for - // tombstone SlotIndex keys. - inline static IndexListEntry* getTombstoneKeyEntry(); - }; - class EmptyIndexListEntry : public IndexListEntry { - public: - EmptyIndexListEntry() : IndexListEntry(EMPTY_KEY) {} - }; - - class TombstoneIndexListEntry : public IndexListEntry { - public: - TombstoneIndexListEntry() : IndexListEntry(TOMBSTONE_KEY) {} }; - inline IndexListEntry* IndexListEntry::getEmptyKeyEntry() { - return &*emptyKeyEntry; - } - - inline IndexListEntry* IndexListEntry::getTombstoneKeyEntry() { - return &*tombstoneKeyEntry; - } - - // 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. @@ -159,59 +78,74 @@ namespace llvm { 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, + + /// 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, + + Slot_Count + }; + + PointerIntPair lie; - IndexListEntry& entry() const { - return *lie.getPointer(); + SlotIndex(IndexListEntry *entry, unsigned slot) + : lie(entry, slot) {} + + IndexListEntry* listEntry() const { + assert(isValid() && "Attempt to compare reserved index."); + return lie.getPointer(); } int getIndex() const { - return entry().getIndex() | getSlot(); + return listEntry()->getIndex() | getSlot(); + } + + /// Returns the slot for this SlotIndex. + Slot getSlot() const { + return static_cast(lie.getInt()); } static inline unsigned getHashValue(const SlotIndex &v) { - IndexListEntry *ptrVal = &v.entry(); - return (unsigned((intptr_t)ptrVal) >> 4) ^ - (unsigned((intptr_t)ptrVal) >> 9); + void *ptrVal = v.lie.getOpaqueValue(); + return (unsigned((intptr_t)ptrVal)) ^ (unsigned((intptr_t)ptrVal) >> 9); } public: - - // 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 }; + enum { + /// The default distance between instructions as returned by distance(). + /// This may vary as instructions are inserted and removed. + InstrDist = 4 * Slot_Count + }; static inline SlotIndex getEmptyKey() { - return SlotIndex(IndexListEntry::getEmptyKeyEntry(), 0); + return SlotIndex(0, 1); } static inline SlotIndex getTombstoneKey() { - return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0); + return SlotIndex(0, 2); } - - /// 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."); - } + /// Construct an invalid index. + SlotIndex() : lie(0, 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, and the slot to the new slot. - SlotIndex(const SlotIndex &li, bool phi, Slot s) - : lie(&li.entry(), phi ? PHI_BIT & s : (unsigned)s) { + // 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() != 0 && "Attempt to construct index with 0 pointer."); } @@ -219,9 +153,12 @@ namespace llvm { /// Returns true if this is a valid index. Invalid indicies do /// not point into an index table, and cannot be compared. bool isValid() const { - return (lie.getPointer() != 0) && (lie.getPointer()->getIndex() != 0); + return lie.getPointer(); } + /// Return true for a valid index. + operator bool() const { return isValid(); } + /// Print this index to the given raw_ostream. void print(raw_ostream &os) const; @@ -230,13 +167,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 { @@ -260,59 +197,60 @@ 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); - } + /// isBlock - Returns true if this is a block boundary slot. + bool isBlock() const { return getSlot() == Slot_Block; } - /// Returns the state of the PHI bit. - bool isPHI() const { - return lie.getInt() & PHI_BIT; - } + /// 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. @@ -321,36 +259,36 @@ 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()->getNextNode(), 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()->getNextNode(), 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()->getPrevNode(), 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()->getPrevNode(), getSlot()); } }; @@ -370,9 +308,11 @@ namespace llvm { static inline bool isEqual(const SlotIndex &LHS, const SlotIndex &RHS) { return (LHS == RHS); } - static inline bool isPod() { return false; } }; + template <> struct isPodLike { static const bool value = true; }; + + inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) { li.print(os); return os; @@ -400,25 +340,21 @@ namespace llvm { class SlotIndexes : public MachineFunctionPass { private: + typedef ilist IndexList; + IndexList indexList; + 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; + SmallVector idx2MBBMap; // IndexListEntry allocator. BumpPtrAllocator ileAllocator; @@ -427,86 +363,25 @@ namespace llvm { 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; - } - - 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(); - } - - /// 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); - } - - /// Push a new entry on to the end of the list. - void push_back(IndexListEntry *val) { - insert(getTail(), val); - } + /// Renumber locally after inserting curItr. + void renumberIndexes(IndexList::iterator curItr); public: static char ID; - SlotIndexes() : MachineFunctionPass(&ID), indexListHead(0) {} + SlotIndexes() : MachineFunctionPass(ID) { + initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); + } virtual void getAnalysisUsage(AnalysisUsage &au) const; - virtual void releaseMemory(); + virtual void releaseMemory(); virtual bool runOnMachineFunction(MachineFunction &fn); @@ -514,26 +389,25 @@ namespace llvm { void dump() const; /// Renumber the index list, providing space for new instructions. - void renumber(); + void renumberIndexes(); /// Returns the zero index for this analysis. SlotIndex getZeroIndex() { - assert(front()->getIndex() == 0 && "First index is not 0?"); - return SlotIndex(front(), 0); + assert(indexList.front().getIndex() == 0 && "First index is not 0?"); + return SlotIndex(&indexList.front(), 0); } - /// Returns the invalid index marker for this analysis. - SlotIndex getInvalidIndex() { - return getZeroIndex(); + /// Returns the base index of the last slot in this analysis. + SlotIndex getLastIndex() { + return SlotIndex(&indexList.back(), 0); } /// Returns the distance between the highest and lowest indexes allocated /// so far. unsigned getIndexesLength() const { - assert(front()->getIndex() == 0 && + assert(indexList.front().getIndex() == 0 && "Initial index isn't zero?"); - - return back()->getIndex(); + return indexList.back().getIndex(); } /// Returns the number of instructions in the function. @@ -544,12 +418,13 @@ namespace llvm { /// 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; } @@ -557,61 +432,103 @@ 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() : 0; } /// Returns the next non-null index. SlotIndex getNextNonNullIndex(SlotIndex index) { - SlotIndex nextNonNull = index.getNextIndex(); + IndexList::iterator itr(index.listEntry()); + ++itr; + while (itr != indexList.end() && itr->getInstr() == 0) { ++itr; } + return SlotIndex(itr, index.getSlot()); + } + + /// getIndexBefore - Returns the index of the last indexed instruction + /// before MI, or the 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; + } + } - 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 the (start,end) range of the given basic block. + const std::pair & + getMBBRange(const MachineBasicBlock *MBB) const { + return getMBBRange(MBB->getNumber()); + } - return nextNonNull; + /// 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. - 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; + /// Returns the last index in the given basic block number. + SlotIndex getMBBEndIdx(unsigned Num) const { + return getMBBRange(Num).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; + /// Returns the last index in the given basic block. + SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { + return getMBBRange(mbb).second; } /// Returns the basic block which the given index falls in. MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { - std::vector::const_iterator I = + if (MachineInstr *MI = getInstructionFromIndex(index)) + return MI->getParent(); + SmallVectorImpl::const_iterator I = std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index); // Take the pair containing the index - std::vector::const_iterator J = + SmallVectorImpl::const_iterator J = ((I != idx2MBBMap.end() && I->first > index) || (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I; assert(J != idx2MBBMap.end() && J->first <= index && - index <= getMBBEndIdx(J->second) && + 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 = + SmallVectorImpl::const_iterator itr = std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); bool resVal = false; @@ -625,36 +542,13 @@ namespace llvm { 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 = + SmallVectorImpl::const_iterator itr = std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); if (itr == idx2MBBMap.end()) { @@ -674,97 +568,49 @@ namespace llvm { return 0; } - /// Returns true if there is a gap in the numbering before the given index. - bool hasGapBeforeInstr(SlotIndex index) { - index = index.getBaseIndex(); - SlotIndex prevIndex = index.getPrevIndex(); - - if (prevIndex == getZeroIndex()) - return false; - - if (getInstructionFromIndex(prevIndex) == 0) - return true; - - if (prevIndex.distance(index) >= 2 * SlotIndex::NUM) - return true; - - return false; - } - - /// Returns true if there is a gap in the numbering after the given index. - bool hasGapAfterInstr(SlotIndex index) const { - // Not implemented yet. - assert(false && - "SlotIndexes::hasGapAfterInstr(SlotIndex) not implemented yet."); - return false; - } - - /// findGapBeforeInstr - Find an empty instruction slot before the - /// specified index. If "Furthest" is true, find one that's furthest - /// away from the index (but before any index that's occupied). - // FIXME: This whole method should go away in future. It should - // always be possible to insert code between existing indices. - SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) { - if (index == getZeroIndex()) - return getInvalidIndex(); - - index = index.getBaseIndex(); - SlotIndex prevIndex = index.getPrevIndex(); - - if (prevIndex == getZeroIndex()) - return getInvalidIndex(); - - // Try to reuse existing index objects with null-instrs. - if (getInstructionFromIndex(prevIndex) == 0) { - if (furthest) { - while (getInstructionFromIndex(prevIndex) == 0 && - prevIndex != getZeroIndex()) { - prevIndex = prevIndex.getPrevIndex(); - } - - prevIndex = prevIndex.getNextIndex(); - } - - assert(getInstructionFromIndex(prevIndex) == 0 && "Index list is broken."); - - return prevIndex; + /// Insert the given machine instruction into the mapping. Returns the + /// assigned index. + /// 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."); + // 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() != 0 && "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(); + prevItr = prior(nextItr); + } else { + // Insert mi's index immediately after the preceeding instruction. + prevItr = getIndexBefore(mi).listEntry(); + nextItr = llvm::next(prevItr); } - int dist = prevIndex.distance(index); - - // Double check that the spacing between this instruction and - // the last is sane. - assert(dist >= SlotIndex::NUM && - "Distance between indexes too small."); - - // If there's no gap return an invalid index. - if (dist < 2*SlotIndex::NUM) { - return getInvalidIndex(); - } + // 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 = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; + unsigned newNumber = prevItr->getIndex() + dist; - // Otherwise insert new index entries into the list using the - // gap in the numbering. - IndexListEntry *newEntry = - createEntry(0, prevIndex.entry().getIndex() + SlotIndex::NUM); + // Insert a new list entry for mi. + IndexList::iterator newItr = + indexList.insert(nextItr, createEntry(mi, newNumber)); - insert(&index.entry(), newEntry); + // Renumber locally if we need to. + if (dist == 0) + renumberIndexes(newItr); - // And return a pointer to the entry at the start of the gap. - return index.getPrevIndex(); - } - - /// Insert the given machine instruction into the mapping at the given - /// index. - void insertMachineInstrInMaps(MachineInstr *mi, SlotIndex index) { - index = index.getBaseIndex(); - IndexListEntry *miEntry = &index.entry(); - assert(miEntry->getInstr() == 0 && "Index already in use."); - miEntry->setInstr(mi); - - assert(mi2iMap.find(mi) == mi2iMap.end() && - "MachineInstr already has an index."); - - mi2iMap.insert(std::make_pair(mi, index)); + SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); + mi2iMap.insert(std::make_pair(mi, newIndex)); + return newIndex; } /// Remove the given machine instruction from the mapping. @@ -773,7 +619,7 @@ namespace llvm { // 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); @@ -788,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); @@ -796,9 +642,53 @@ namespace llvm { mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex)); } + /// Add the given MachineBasicBlock into the maps. + void insertMBBInMaps(MachineBasicBlock *mbb) { + MachineFunction::iterator nextMBB = + llvm::next(MachineFunction::iterator(mbb)); + IndexListEntry *startEntry = createEntry(0, 0); + IndexListEntry *stopEntry = createEntry(0, 0); + IndexListEntry *nextEntry = 0; + + if (nextMBB == mbb->getParent()->end()) { + nextEntry = indexList.end(); + } else { + nextEntry = getMBBStartIdx(nextMBB).listEntry(); + } + + indexList.insert(nextEntry, startEntry); + indexList.insert(nextEntry, stopEntry); + + SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); + SlotIndex endIdx(nextEntry, SlotIndex::Slot_Block); + + 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(); + std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); + } + }; + // Specialize IntervalMapInfo for half-open slot index intervals. + template struct IntervalMapInfo; + template <> struct IntervalMapInfo { + static inline bool startLess(const SlotIndex &x, const SlotIndex &a) { + return x < a; + } + static inline bool stopLess(const SlotIndex &b, const SlotIndex &x) { + return b <= x; + } + static inline bool adjacent(const SlotIndex &a, const SlotIndex &b) { + return a == b; + } + }; + } -#endif // LLVM_CODEGEN_LIVEINDEX_H +#endif // LLVM_CODEGEN_SLOTINDEXES_H