//
//===----------------------------------------------------------------------===//
//
-// 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/ADT/DenseMap.h"
+#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/Support/Allocator.h"
namespace llvm {
/// SlotIndexes pass. It should not be used directly. See the
/// SlotIndex & SlotIndexes classes for the public interface to this
/// information.
- class IndexListEntry {
- private:
-
- IndexListEntry *next, *prev;
+ class IndexListEntry : public ilist_node<IndexListEntry> {
MachineInstr *mi;
unsigned index;
public:
- IndexListEntry(MachineInstr *mi, unsigned index)
- : mi(mi), index(index) {}
+ IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {}
MachineInstr* getInstr() const { return mi; }
- void setInstr(MachineInstr *mi) { this->mi = mi; }
+ void setInstr(MachineInstr *mi) {
+ this->mi = mi;
+ }
unsigned getIndex() const { return index; }
- void setIndex(unsigned index) { this->index = index; }
-
- IndexListEntry* getNext() { return next; }
- const IndexListEntry* getNext() const { return next; }
- void setNext(IndexListEntry *next) { this->next = next; }
-
- IndexListEntry* getPrev() { return prev; }
- const IndexListEntry* getPrev() const { return prev; }
- void setPrev(IndexListEntry *prev) { this->prev = prev; }
+ void setIndex(unsigned index) {
+ this->index = index;
+ }
+
};
- // Specialize PointerLikeTypeTraits for IndexListEntry.
template <>
- class PointerLikeTypeTraits<IndexListEntry*> {
+ struct ilist_traits<IndexListEntry> : public ilist_default_traits<IndexListEntry> {
+ private:
+ mutable ilist_half_node<IndexListEntry> Sentinel;
public:
- static inline void* getAsVoidPointer(IndexListEntry *p) {
- return p;
- }
- static inline IndexListEntry* getFromVoidPointer(void *p) {
- return static_cast<IndexListEntry*>(p);
+ IndexListEntry *createSentinel() const {
+ return static_cast<IndexListEntry*>(&Sentinel);
}
- 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 class DenseMapInfo<SlotIndex>;
- private:
+ 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,
- // FIXME: Is there any way to statically allocate these things and have
- // them 8-byte aligned?
- static std::auto_ptr<IndexListEntry> emptyKeyPtr, tombstoneKeyPtr;
- static const unsigned PHI_BIT = 1 << 2;
+ /// 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,
- PointerIntPair<IndexListEntry*, 3, unsigned> lie;
+ /// Normal register use/def slot. Normal instructions kill and define
+ /// register live ranges at this slot.
+ Slot_Register,
- SlotIndex(IndexListEntry *entry, unsigned phiAndSlot)
- : lie(entry, phiAndSlot) {
- assert(entry != 0 && "Attempt to construct index with 0 pointer.");
- }
+ /// 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
+ };
- IndexListEntry& entry() const {
- assert(lie.getPointer() != 0 && "Use of invalid index.");
- return *lie.getPointer();
+ PointerIntPair<IndexListEntry*, 2, unsigned> lie;
+
+ 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();
}
- static inline unsigned getHashValue(const SlotIndex &v) {
- IndexListEntry *ptrVal = &v.entry();
- return (unsigned((intptr_t)ptrVal) >> 4) ^
- (unsigned((intptr_t)ptrVal) >> 9);
+ /// Returns the slot for this SlotIndex.
+ Slot getSlot() const {
+ return static_cast<Slot>(lie.getInt());
}
public:
+ enum {
+ /// The default distance between instructions as returned by distance().
+ /// This may vary as instructions are inserted and removed.
+ InstrDist = 4 * Slot_Count
+ };
- // 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() {
- // FIXME: How do we guarantee these numbers don't get allocated to
- // legit indexes?
- if (emptyKeyPtr.get() == 0)
- emptyKeyPtr.reset(new IndexListEntry(0, ~0U & ~3U));
-
- return SlotIndex(emptyKeyPtr.get(), 0);
- }
-
- static inline SlotIndex getTombstoneKey() {
- // FIXME: How do we guarantee these numbers don't get allocated to
- // legit indexes?
- if (tombstoneKeyPtr.get() == 0)
- tombstoneKeyPtr.reset(new IndexListEntry(0, ~0U & ~7U));
-
- return SlotIndex(tombstoneKeyPtr.get(), 0);
- }
-
/// Construct an invalid index.
- SlotIndex() : lie(&getEmptyKey().entry(), 0) {}
+ 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.
- 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) {
+ // 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.");
}
/// 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;
/// 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 {
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<Slot>(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.
/// 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());
}
};
- /// DenseMapInfo specialization for SlotIndex.
- template <>
- struct DenseMapInfo<SlotIndex> {
- 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);
- }
- static inline bool isPod() { return false; }
- };
+ template <> struct isPodLike<SlotIndex> { static const bool value = true; };
+
inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
li.print(os);
class SlotIndexes : public MachineFunctionPass {
private:
+ typedef ilist<IndexListEntry> IndexList;
+ IndexList indexList;
+
MachineFunction *mf;
- IndexListEntry *indexListHead;
- unsigned functionSize;
typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
Mi2IndexMap mi2iMap;
- /// MBB2IdxMap - The indexes of the first and last instructions in the
- /// specified basic block.
- typedef DenseMap<const MachineBasicBlock*,
- std::pair<SlotIndex, SlotIndex> > MBB2IdxMap;
- MBB2IdxMap mbb2IdxMap;
+ /// MBBRanges - Map MBB number to (start, stop) indexes.
+ SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges;
/// Idx2MBBMap - Sorted list of pairs of index of first instruction
/// and MBB id.
- std::vector<IdxMBBPair> idx2MBBMap;
-
- typedef DenseMap<const MachineBasicBlock*, SlotIndex> TerminatorGapsMap;
- TerminatorGapsMap terminatorGaps;
+ SmallVector<IdxMBBPair, 8> idx2MBBMap;
// IndexListEntry allocator.
BumpPtrAllocator ileAllocator;
IndexListEntry *entry =
static_cast<IndexListEntry*>(
ileAllocator.Allocate(sizeof(IndexListEntry),
- alignof<IndexListEntry>()));
+ alignOf<IndexListEntry>()));
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);
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 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;
}
/// 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 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<SlotIndex, SlotIndex> &
+ getMBBRange(unsigned Num) const {
+ return MBBRanges[Num];
+ }
- return nextNonNull;
+ /// Return the (start,end) range of the given basic block.
+ const std::pair<SlotIndex, SlotIndex> &
+ 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.
- 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<IdxMBBPair>::const_iterator I =
+ if (MachineInstr *MI = getInstructionFromIndex(index))
+ return MI->getParent();
+ SmallVectorImpl<IdxMBBPair>::const_iterator I =
std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
// Take the pair containing the index
- std::vector<IdxMBBPair>::const_iterator J =
+ SmallVectorImpl<IdxMBBPair>::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<MachineBasicBlock*> &mbbs) const {
- std::vector<IdxMBBPair>::const_iterator itr =
+ SmallVectorImpl<IdxMBBPair>::const_iterator itr =
std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
bool resVal = false;
return resVal;
}
- /// Return a list of MBBs that can be reach via any branches or
- /// fall-throughs.
- bool findReachableMBBs(SlotIndex start, SlotIndex end,
- SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
- std::vector<IdxMBBPair>::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<IdxMBBPair>::const_iterator itr =
+ SmallVectorImpl<IdxMBBPair>::const_iterator itr =
std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
if (itr == idx2MBBMap.end()) {
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 preceding 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.
// 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);
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);
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<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> {
+ };
+
}
-#endif // LLVM_CODEGEN_LIVEINDEX_H
+#endif // LLVM_CODEGEN_SLOTINDEXES_H