X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSlotIndexes.h;h=984796af8644e6a77c93b526bc85d7718fe59c7b;hb=2c46deb1d07f4588ee70059cdd4c7145f81bc8e8;hp=0457e43e6b7b0b5145321ef405bc3db900c0322f;hpb=0b5ad0b9d902620b81268add3f554d73a6d92fc1;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 0457e43e6b7..984796af864 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -19,13 +19,14 @@ #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/DenseMap.h" +#include "llvm/ADT/IntervalMap.h" #include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/ilist.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ilist.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/Support/Allocator.h" namespace llvm { @@ -52,6 +53,20 @@ namespace llvm { 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(mi); + assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); + tmp |= 0x1; + mi = reinterpret_cast(tmp); + } + + bool isPoisoned() const { return (reinterpret_cast(mi) & 0x1) == 0x1; } +#endif // EXPENSIVE_CHECKS + }; template <> @@ -76,7 +91,6 @@ namespace llvm { /// SlotIndex - An opaque wrapper around machine indexes. class SlotIndex { friend class SlotIndexes; - friend struct DenseMapInfo; enum Slot { /// Basic block boundary. Used for live ranges entering and leaving a @@ -109,10 +123,14 @@ namespace llvm { 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(); } @@ -121,11 +139,6 @@ namespace llvm { return static_cast(lie.getInt()); } - static inline unsigned getHashValue(const SlotIndex &v) { - void *ptrVal = v.lie.getOpaqueValue(); - return (unsigned((intptr_t)ptrVal)) ^ (unsigned((intptr_t)ptrVal) >> 9); - } - public: enum { /// The default distance between instructions as returned by distance(). @@ -133,14 +146,6 @@ namespace llvm { InstrDist = 4 * Slot_Count }; - static inline SlotIndex getEmptyKey() { - return SlotIndex(0, 1); - } - - static inline SlotIndex getTombstoneKey() { - return SlotIndex(0, 2); - } - /// Construct an invalid index. SlotIndex() : lie(0, 0) {} @@ -157,7 +162,7 @@ namespace llvm { } /// Return true for a valid index. - operator bool() const { return isValid(); } + LLVM_EXPLICIT operator bool() const { return isValid(); } /// Print this index to the given raw_ostream. void print(raw_ostream &os) const; @@ -213,6 +218,13 @@ namespace llvm { 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; } @@ -293,26 +305,8 @@ namespace llvm { }; - /// 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; @@ -343,8 +337,11 @@ namespace llvm { typedef ilist IndexList; IndexList indexList; +#ifdef EXPENSIVE_CHECKS + IndexList graveyardList; +#endif // EXPENSIVE_CHECKS + MachineFunction *mf; - unsigned functionSize; typedef DenseMap Mi2IndexMap; Mi2IndexMap mi2iMap; @@ -391,6 +388,11 @@ namespace llvm { /// Renumber the index list, providing space for new instructions. void renumberIndexes(); + /// Repair indexes after adding and removing instructions. + void repairIndexesInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End); + /// Returns the zero index for this analysis. SlotIndex getZeroIndex() { assert(indexList.front().getIndex() == 0 && "First index is not 0?"); @@ -402,19 +404,6 @@ namespace llvm { return SlotIndex(&indexList.back(), 0); } - /// Returns the distance between the highest and lowest indexes allocated - /// so far. - unsigned getIndexesLength() const { - assert(indexList.front().getIndex() == 0 && - "Initial index isn't zero?"); - return indexList.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 { @@ -435,16 +424,20 @@ namespace llvm { return index.isValid() ? index.listEntry()->getInstr() : 0; } - /// 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(); + IndexList::iterator E = indexList.end(); + while (++I != E) + if (I->getInstr()) + return SlotIndex(I, Index.getSlot()); + // We reached the end of the function. + return getLastIndex(); } /// getIndexBefore - Returns the index of the last indexed instruction - /// before MI, or the the start index of its basic block. + /// 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(); @@ -590,7 +583,7 @@ namespace llvm { nextItr = getIndexAfter(mi).listEntry(); prevItr = prior(nextItr); } else { - // Insert mi's index immediately after the preceeding instruction. + // Insert mi's index immediately after the preceding instruction. prevItr = getIndexBefore(mi).listEntry(); nextItr = llvm::next(prevItr); } @@ -646,47 +639,70 @@ namespace llvm { 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; + IndexListEntry *startEntry = 0; + IndexListEntry *endEntry = 0; + IndexList::iterator newItr; if (nextMBB == mbb->getParent()->end()) { - nextEntry = indexList.end(); + startEntry = &indexList.back(); + endEntry = createEntry(0, 0); + newItr = indexList.insertAfter(startEntry, endEntry); } else { - nextEntry = getMBBStartIdx(nextMBB).listEntry(); + startEntry = createEntry(0, 0); + endEntry = getMBBStartIdx(nextMBB).listEntry(); + newItr = indexList.insert(endEntry, 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 + } + }; // 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; - } + template <> + struct IntervalMapInfo : IntervalMapHalfOpenInfo { }; }