this->index = index;
}
+#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<intptr_t>(mi);
+ assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?");
+ tmp |= 0x1;
+ mi = reinterpret_cast<MachineInstr*>(tmp);
+ }
+
+ bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; }
+#endif // EXPENSIVE_CHECKS
+
};
template <>
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();
}
- int getIndex() const {
+ unsigned getIndex() const {
return listEntry()->getIndex() | getSlot();
}
};
/// Construct an invalid index.
- SlotIndex() : lie(0, 0) {}
+ 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() != 0 &&
+ 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 {
return lie.getPointer();
}
/// Return true for a valid index.
- operator bool() const { return isValid(); }
+ explicit operator bool() const { return isValid(); }
/// Print this index to the given raw_ostream.
void print(raw_ostream &os) const;
return other.getIndex() - getIndex();
}
+ /// 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;
+ }
+
/// isBlock - Returns true if this is a block boundary slot.
bool isBlock() const { return getSlot() == Slot_Block; }
SlotIndex getNextSlot() const {
Slot s = getSlot();
if (s == Slot_Dead) {
- return SlotIndex(listEntry()->getNextNode(), Slot_Block);
+ return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
}
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(listEntry()->getNextNode(), getSlot());
+ return SlotIndex(&*++listEntry()->getIterator(), getSlot());
}
/// Returns the previous slot in the index list. This could be either the
SlotIndex getPrevSlot() const {
Slot s = getSlot();
if (s == Slot_Block) {
- return SlotIndex(listEntry()->getPrevNode(), Slot_Dead);
+ return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
}
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(listEntry()->getPrevNode(), getSlot());
+ return SlotIndex(&*--listEntry()->getIterator(), getSlot());
}
};
template <> struct isPodLike<SlotIndex> { static const bool value = true; };
-
inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
li.print(os);
return os;
/// This pass assigns indexes to each instruction.
class SlotIndexes : public MachineFunctionPass {
private:
+ // IndexListEntry allocator.
+ BumpPtrAllocator ileAllocator;
typedef ilist<IndexListEntry> IndexList;
IndexList indexList;
+#ifdef EXPENSIVE_CHECKS
+ IndexList graveyardList;
+#endif // EXPENSIVE_CHECKS
+
MachineFunction *mf;
typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
/// and MBB id.
SmallVector<IdxMBBPair, 8> idx2MBBMap;
- // IndexListEntry allocator.
- BumpPtrAllocator ileAllocator;
-
IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
IndexListEntry *entry =
static_cast<IndexListEntry*>(
initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
}
- virtual void getAnalysisUsage(AnalysisUsage &au) const;
- virtual void releaseMemory();
+ ~SlotIndexes() {
+ // The indexList's nodes are all allocated in the BumpPtrAllocator.
+ indexList.clearAndLeakNodesUnsafely();
+ }
+
+ void getAnalysisUsage(AnalysisUsage &au) const override;
+ void releaseMemory() override;
- virtual bool runOnMachineFunction(MachineFunction &fn);
+ bool runOnMachineFunction(MachineFunction &fn) override;
/// Dump the indexes.
void dump() const;
/// 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(indexList.front().getIndex() == 0 && "First index is not 0?");
/// 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.isValid() ? index.listEntry()->getInstr() : 0;
+ return index.isValid() ? index.listEntry()->getInstr() : nullptr;
}
- /// Returns the next non-null index.
- SlotIndex getNextNonNullIndex(SlotIndex index) {
- IndexList::iterator itr(index.listEntry());
- ++itr;
- while (itr != indexList.end() && itr->getInstr() == 0) { ++itr; }
- return SlotIndex(itr, index.getSlot());
+ /// 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
return getMBBRange(mbb).second;
}
+ /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
+ /// begin and basic block)
+ typedef SmallVectorImpl<IdxMBBPair>::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 {
if (MachineInstr *MI = getInstructionFromIndex(index))
return MI->getParent();
- SmallVectorImpl<IdxMBBPair>::const_iterator I =
- std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
+
+ MBBIndexIterator I = findMBBIndex(index);
// Take the pair containing the index
- SmallVectorImpl<IdxMBBPair>::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<MachineBasicBlock*> &mbbs) const {
- SmallVectorImpl<IdxMBBPair>::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;
- }
-
/// 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.");
-
- SmallVectorImpl<IdxMBBPair>::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
// affected by debug information.
assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions.");
- assert(mi->getParent() != 0 && "Instr must be added to function.");
+ 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();
- prevItr = prior(nextItr);
+ nextItr = getIndexAfter(mi).listEntry()->getIterator();
+ prevItr = std::prev(nextItr);
} else {
// Insert mi's index immediately after the preceding instruction.
- prevItr = getIndexBefore(mi).listEntry();
- nextItr = llvm::next(prevItr);
+ prevItr = getIndexBefore(mi).listEntry()->getIterator();
+ nextItr = std::next(prevItr);
}
// Get a number for the new instr, or 0 if there's no room currently.
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);
}
}
/// 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;
+ std::next(MachineFunction::iterator(mbb));
+ IndexListEntry *startEntry = nullptr;
+ IndexListEntry *endEntry = nullptr;
+ IndexList::iterator newItr;
if (nextMBB == mbb->getParent()->end()) {
- nextEntry = indexList.end();
+ startEntry = &indexList.back();
+ endEntry = createEntry(nullptr, 0);
+ newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
} else {
- nextEntry = getMBBStartIdx(nextMBB).listEntry();
+ startEntry = createEntry(nullptr, 0);
+ endEntry = getMBBStartIdx(&*nextMBB).listEntry();
+ newItr = indexList.insert(endEntry->getIterator(), startEntry);
}
- indexList.insert(nextEntry, startEntry);
- indexList.insert(nextEntry, stopEntry);
-
SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
- SlotIndex endIdx(nextEntry, 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();
+ 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
+ }
+
};
projects / oota-llvm.git / blobdiff