X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSlotIndexes.h;h=f1f047b44ed2a34561c714a20c2d4b569868c6e2;hb=dfbc29a5a2197ff88c56448dd57fd4a4fcf16a1f;hp=6c7a2be2aff51783abd362ef6400ced9ca3c5bfd;hpb=d6ef7fac1a020c58ec61cad2325e5f6afd0bbee6;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 6c7a2be2aff..f1f047b44ed 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -22,35 +22,24 @@ #ifndef LLVM_CODEGEN_SLOTINDEXES_H #define LLVM_CODEGEN_SLOTINDEXES_H -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.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; MachineInstr *mi; unsigned index; @@ -75,16 +64,18 @@ namespace llvm { 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?."); - } + 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(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to modify reserved index."); + assert(isValid() && "Attempt to modify reserved index."); this->mi = mi; } @@ -92,55 +83,33 @@ namespace llvm { 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."); + 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(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to modify reserved index."); + 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(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to modify reserved index."); + 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. - inline static IndexListEntry* getEmptyKeyEntry(); + 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) {} + static IndexListEntry* getTombstoneKeyEntry(); }; - inline IndexListEntry* IndexListEntry::getEmptyKeyEntry() { - return &*emptyKeyEntry; - } - - inline IndexListEntry* IndexListEntry::getTombstoneKeyEntry() { - return &*tombstoneKeyEntry; - } - // Specialize PointerLikeTypeTraits for IndexListEntry. template <> class PointerLikeTypeTraits { @@ -157,7 +126,7 @@ namespace llvm { /// SlotIndex - An opaque wrapper around machine indexes. class SlotIndex { friend class SlotIndexes; - friend class DenseMapInfo; + friend struct DenseMapInfo; private: static const unsigned PHI_BIT = 1 << 2; @@ -203,7 +172,7 @@ namespace llvm { // 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()){ + : lie(&li.entry(), phi ? PHI_BIT | li.getSlot() : (unsigned)li.getSlot()){ assert(lie.getPointer() != 0 && "Attempt to construct index with 0 pointer."); } @@ -211,7 +180,7 @@ namespace llvm { // 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) { + : lie(&li.entry(), phi ? PHI_BIT | s : (unsigned)s) { assert(lie.getPointer() != 0 && "Attempt to construct index with 0 pointer."); } @@ -219,7 +188,8 @@ 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); + IndexListEntry *entry = lie.getPointer(); + return ((entry!= 0) && (entry->isValid())); } /// Print this index to the given raw_ostream. @@ -370,8 +340,10 @@ 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); @@ -514,7 +486,7 @@ 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() { @@ -604,7 +576,7 @@ namespace llvm { (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; } @@ -674,99 +646,94 @@ 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; + /// 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."); - if (getInstructionFromIndex(prevIndex) == 0) - return true; + MachineBasicBlock *mbb = mi->getParent(); - if (prevIndex.distance(index) >= 2 * SlotIndex::NUM) - return true; + assert(mbb != 0 && "Instr must be added to function."); - 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(); + MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb); - index = index.getBaseIndex(); - SlotIndex prevIndex = index.getPrevIndex(); + assert(mbbRangeItr != mbb2IdxMap.end() && + "Instruction's parent MBB has not been added to SlotIndexes."); - 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(); + 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; } - - assert(getInstructionFromIndex(prevIndex) == 0 && "Index list is broken."); - - return prevIndex; } - int dist = prevIndex.distance(index); + // Get next entry from previous entry. + IndexListEntry *nextEntry = prevEntry->getNext(); - // Double check that the spacing between this instruction and - // the last is sane. - assert(dist >= SlotIndex::NUM && - "Distance between indexes too small."); + // 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 there's no gap return an invalid index. - if (dist < 2*SlotIndex::NUM) { - return getInvalidIndex(); + if (newNumber == 0) { + needRenumber = true; } - // 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. + 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); + } - insert(&index.entry(), newEntry); + // Renumber if we need to. + if (needRenumber) { + if (deferredRenumber == 0) + renumberIndexes(); + else + *deferredRenumber = true; + } - // And return a pointer to the entry at the start of the gap. - return index.getPrevIndex(); + return newIndex; } - /// 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); + /// 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; - assert(mi2iMap.find(mi) == mi2iMap.end() && - "MachineInstr already has an index."); + for (SmallVectorImpl::iterator + miItr = mis.begin(), miEnd = mis.end(); + miItr != miEnd; ++miItr) { + insertMachineInstrInMaps(*miItr, &renumber); + } - mi2iMap.insert(std::make_pair(mi, index)); + if (renumber) + renumberIndexes(); } + /// Remove the given machine instruction from the mapping. void removeMachineInstrFromMaps(MachineInstr *mi) { // remove index -> MachineInstr and @@ -796,6 +763,47 @@ 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 *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()); + + } + };