//===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- 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 SlotIndex and related classes. The purpuse 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. //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_SLOTINDEXES_H #define LLVM_CODEGEN_SLOTINDEXES_H #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/Allocator.h" namespace llvm { /// 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 { static const unsigned EMPTY_KEY_INDEX = ~0U & ~3U, TOMBSTONE_KEY_INDEX = ~0U & ~7U; IndexListEntry *next, *prev; 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); } 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; } // This function returns the index list entry that is to be used for empty // SlotIndex keys. static IndexListEntry* getEmptyKeyEntry(); // 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 { public: static inline void* getAsVoidPointer(IndexListEntry *p) { return p; } static inline IndexListEntry* getFromVoidPointer(void *p) { return static_cast(p); } enum { NumLowBitsAvailable = 3 }; }; /// SlotIndex - An opaque wrapper around machine indexes. class SlotIndex { friend class SlotIndexes; friend struct DenseMapInfo; private: static const unsigned PHI_BIT = 1 << 2; PointerIntPair lie; SlotIndex(IndexListEntry *entry, unsigned phiAndSlot) : lie(entry, phiAndSlot) { assert(entry != 0 && "Attempt to construct index with 0 pointer."); } IndexListEntry& entry() const { return *lie.getPointer(); } 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); } 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 }; static inline SlotIndex getEmptyKey() { return SlotIndex(IndexListEntry::getEmptyKeyEntry(), 0); } static inline SlotIndex getTombstoneKey() { return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0); } /// 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 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 && "Attempt to construct index with 0 pointer."); } /// Returns true if this is a valid index. Invalid indicies do /// not point into an index table, and cannot be compared. bool isValid() const { IndexListEntry *entry = lie.getPointer(); return ((entry!= 0) && (entry->isValid())); } /// Print this index to the given raw_ostream. void print(raw_ostream &os) const; /// Dump this index to stderr. void dump() const; /// Compare two SlotIndex objects for equality. bool operator==(SlotIndex other) const { return getIndex() == other.getIndex(); } /// Compare two SlotIndex objects for inequality. bool operator!=(SlotIndex other) const { return getIndex() != other.getIndex(); } /// Compare two SlotIndex objects. Return true if the first index /// is strictly lower than the second. bool operator<(SlotIndex other) const { return getIndex() < other.getIndex(); } /// Compare two SlotIndex objects. Return true if the first index /// is lower than, or equal to, the second. bool operator<=(SlotIndex other) const { return getIndex() <= other.getIndex(); } /// Compare two SlotIndex objects. Return true if the first index /// is greater than the second. bool operator>(SlotIndex other) const { return getIndex() > other.getIndex(); } /// Compare two SlotIndex objects. Return true if the first index /// is greater than, or equal to, the second. bool operator>=(SlotIndex other) const { return getIndex() >= other.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); } /// Returns the state of the PHI bit. bool isPHI() const { return lie.getInt() & PHI_BIT; } /// 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. SlotIndex getBaseIndex() const { return getLoadIndex(); } /// Returns the boundary index for associated with this index. The boundary /// index is the one associated with the LOAD slot for the instruction /// pointed to by this index. SlotIndex getBoundaryIndex() const { return getStoreIndex(); } /// 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 index of the DEF slot for the instruction pointed to by /// this index. SlotIndex getDefIndex() const { return SlotIndex(&entry(), SlotIndex::DEF); } /// 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. /// 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 getNextSlot() const { Slot s = getSlot(); if (s == SlotIndex::STORE) { return SlotIndex(entry().getNext(), SlotIndex::LOAD); } return SlotIndex(&entry(), 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()); } /// 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. /// 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); } return SlotIndex(&entry(), 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()); } }; /// 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; } typedef std::pair IdxMBBPair; inline bool operator<(SlotIndex V, const IdxMBBPair &IM) { return V < IM.first; } inline bool operator<(const IdxMBBPair &IM, SlotIndex V) { return IM.first < V; } struct Idx2MBBCompare { bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { return LHS.first < RHS.first; } }; /// SlotIndexes pass. /// /// This pass assigns indexes to each instruction. class SlotIndexes : public MachineFunctionPass { private: 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; /// 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; IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { IndexListEntry *entry = static_cast( ileAllocator.Allocate(sizeof(IndexListEntry), 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); } public: static char ID; SlotIndexes() : MachineFunctionPass(&ID), indexListHead(0) {} virtual void getAnalysisUsage(AnalysisUsage &au) const; virtual void releaseMemory(); virtual bool runOnMachineFunction(MachineFunction &fn); /// Dump the indexes. void dump() const; /// Renumber the index list, providing space for new instructions. void renumberIndexes(); /// Returns the zero index for this analysis. SlotIndex getZeroIndex() { assert(front()->getIndex() == 0 && "First index is not 0?"); return SlotIndex(front(), 0); } /// Returns the base index of the last slot in this analysis. SlotIndex getLastIndex() { return SlotIndex(back(), 0); } /// Returns the invalid index marker for this analysis. SlotIndex getInvalidIndex() { return getZeroIndex(); } /// 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 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()); } /// Returns the base index for the given instruction. SlotIndex getInstructionIndex(const MachineInstr *instr) const { Mi2IndexMap::const_iterator itr = mi2iMap.find(instr); assert(itr != mi2iMap.end() && "Instruction not found in maps."); return itr->second; } /// 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(); } /// Returns the next non-null index. SlotIndex getNextNonNullIndex(SlotIndex index) { SlotIndex nextNonNull = index.getNextIndex(); while (&nextNonNull.entry() != getTail() && getInstructionFromIndex(nextNonNull) == 0) { nextNonNull = nextNonNull.getNextIndex(); } return nextNonNull; } /// 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; } /// 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 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 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); // 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; assert(J != idx2MBBMap.end() && 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); return itr->second; } // Check that we don't cross the boundary into this block. if (itr->first < end) return 0; itr = prior(itr); if (itr->first <= start) return itr->second; return 0; } /// Insert the given machine instruction into the mapping. Returns the /// assigned index. SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool *deferredRenumber = 0) { 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; // Get previous index, considering that not all instructions are indexed. IndexListEntry *prevEntry; for (;;) { // If mi is at the mbb beginning, get the prev index from the mbb. if (miItr == mbb->begin()) { prevEntry = &mbbRangeItr->second.first.entry(); break; } // Otherwise rewind until we find a mapped instruction. Mi2IndexMap::const_iterator itr = mi2iMap.find(--miItr); if (itr != mi2iMap.end()) { prevEntry = &itr->second.entry(); break; } } // 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; } // 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); } // Renumber if we need to. if (needRenumber) { if (deferredRenumber == 0) renumberIndexes(); else *deferredRenumber = true; } 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()); assert(miEntry->getInstr() == mi && "Instruction indexes broken."); // FIXME: Eventually we want to actually delete these indexes. miEntry->setInstr(0); mi2iMap.erase(mi2iItr); } } /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in /// maps used by register allocator. void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) { Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); if (mi2iItr == mi2iMap.end()) return; SlotIndex replaceBaseIndex = mi2iItr->second; IndexListEntry *miEntry(&replaceBaseIndex.entry()); assert(miEntry->getInstr() == mi && "Mismatched instruction in index tables."); miEntry->setInstr(newMI); mi2iMap.erase(mi2iItr); 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 *terminatorEntry = createEntry(0, 0); IndexListEntry *nextEntry = 0; if (nextMBB == mbb->getParent()->end()) { nextEntry = getTail(); } else { nextEntry = &getMBBStartIdx(nextMBB).entry(); } insert(nextEntry, startEntry); insert(nextEntry, terminatorEntry); SlotIndex startIdx(startEntry, SlotIndex::LOAD); SlotIndex terminatorIdx(terminatorEntry, SlotIndex::PHI_BIT); SlotIndex endIdx(nextEntry, SlotIndex::LOAD); terminatorGaps.insert( std::make_pair(mbb, terminatorIdx)); mbb2IdxMap.insert( std::make_pair(mbb, std::make_pair(startIdx, endIdx))); idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); if (MachineFunction::iterator(mbb) != mbb->getParent()->begin()) { // Have to update the end index of the previous block. MachineBasicBlock *priorMBB = llvm::prior(MachineFunction::iterator(mbb)); mbb2IdxMap[priorMBB].second = startIdx; } renumberIndexes(); std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); } }; } #endif // LLVM_CODEGEN_LIVEINDEX_H