Home | History | Annotate | Download | only in CodeGen
      1 //===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements SlotIndex and related classes. The purpose of SlotIndex
     11 // is to describe a position at which a register can become live, or cease to
     12 // be live.
     13 //
     14 // SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which
     15 // is held is LiveIntervals and provides the real numbering. This allows
     16 // LiveIntervals to perform largely transparent renumbering.
     17 //===----------------------------------------------------------------------===//
     18 
     19 #ifndef LLVM_CODEGEN_SLOTINDEXES_H
     20 #define LLVM_CODEGEN_SLOTINDEXES_H
     21 
     22 #include "llvm/ADT/DenseMap.h"
     23 #include "llvm/ADT/IntervalMap.h"
     24 #include "llvm/ADT/PointerIntPair.h"
     25 #include "llvm/ADT/SmallVector.h"
     26 #include "llvm/ADT/ilist.h"
     27 #include "llvm/CodeGen/MachineFunction.h"
     28 #include "llvm/CodeGen/MachineFunctionPass.h"
     29 #include "llvm/CodeGen/MachineInstrBundle.h"
     30 #include "llvm/Support/Allocator.h"
     31 
     32 namespace llvm {
     33 
     34   /// This class represents an entry in the slot index list held in the
     35   /// SlotIndexes pass. It should not be used directly. See the
     36   /// SlotIndex & SlotIndexes classes for the public interface to this
     37   /// information.
     38   class IndexListEntry : public ilist_node<IndexListEntry> {
     39     MachineInstr *mi;
     40     unsigned index;
     41 
     42   public:
     43 
     44     IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {}
     45 
     46     MachineInstr* getInstr() const { return mi; }
     47     void setInstr(MachineInstr *mi) {
     48       this->mi = mi;
     49     }
     50 
     51     unsigned getIndex() const { return index; }
     52     void setIndex(unsigned index) {
     53       this->index = index;
     54     }
     55 
     56 #ifdef EXPENSIVE_CHECKS
     57     // When EXPENSIVE_CHECKS is defined, "erased" index list entries will
     58     // actually be moved to a "graveyard" list, and have their pointers
     59     // poisoned, so that dangling SlotIndex access can be reliably detected.
     60     void setPoison() {
     61       intptr_t tmp = reinterpret_cast<intptr_t>(mi);
     62       assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?");
     63       tmp |= 0x1;
     64       mi = reinterpret_cast<MachineInstr*>(tmp);
     65     }
     66 
     67     bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; }
     68 #endif // EXPENSIVE_CHECKS
     69 
     70   };
     71 
     72   template <>
     73   struct ilist_traits<IndexListEntry> : public ilist_default_traits<IndexListEntry> {
     74   private:
     75     mutable ilist_half_node<IndexListEntry> Sentinel;
     76   public:
     77     IndexListEntry *createSentinel() const {
     78       return static_cast<IndexListEntry*>(&Sentinel);
     79     }
     80     void destroySentinel(IndexListEntry *) const {}
     81 
     82     IndexListEntry *provideInitialHead() const { return createSentinel(); }
     83     IndexListEntry *ensureHead(IndexListEntry*) const { return createSentinel(); }
     84     static void noteHead(IndexListEntry*, IndexListEntry*) {}
     85     void deleteNode(IndexListEntry *N) {}
     86 
     87   private:
     88     void createNode(const IndexListEntry &);
     89   };
     90 
     91   /// SlotIndex - An opaque wrapper around machine indexes.
     92   class SlotIndex {
     93     friend class SlotIndexes;
     94 
     95     enum Slot {
     96       /// Basic block boundary.  Used for live ranges entering and leaving a
     97       /// block without being live in the layout neighbor.  Also used as the
     98       /// def slot of PHI-defs.
     99       Slot_Block,
    100 
    101       /// Early-clobber register use/def slot.  A live range defined at
    102       /// Slot_EarlyCLobber interferes with normal live ranges killed at
    103       /// Slot_Register.  Also used as the kill slot for live ranges tied to an
    104       /// early-clobber def.
    105       Slot_EarlyClobber,
    106 
    107       /// Normal register use/def slot.  Normal instructions kill and define
    108       /// register live ranges at this slot.
    109       Slot_Register,
    110 
    111       /// Dead def kill point.  Kill slot for a live range that is defined by
    112       /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't
    113       /// used anywhere.
    114       Slot_Dead,
    115 
    116       Slot_Count
    117     };
    118 
    119     PointerIntPair<IndexListEntry*, 2, unsigned> lie;
    120 
    121     SlotIndex(IndexListEntry *entry, unsigned slot)
    122       : lie(entry, slot) {}
    123 
    124     IndexListEntry* listEntry() const {
    125       assert(isValid() && "Attempt to compare reserved index.");
    126 #ifdef EXPENSIVE_CHECKS
    127       assert(!lie.getPointer()->isPoisoned() &&
    128              "Attempt to access deleted list-entry.");
    129 #endif // EXPENSIVE_CHECKS
    130       return lie.getPointer();
    131     }
    132 
    133     unsigned getIndex() const {
    134       return listEntry()->getIndex() | getSlot();
    135     }
    136 
    137     /// Returns the slot for this SlotIndex.
    138     Slot getSlot() const {
    139       return static_cast<Slot>(lie.getInt());
    140     }
    141 
    142   public:
    143     enum {
    144       /// The default distance between instructions as returned by distance().
    145       /// This may vary as instructions are inserted and removed.
    146       InstrDist = 4 * Slot_Count
    147     };
    148 
    149     /// Construct an invalid index.
    150     SlotIndex() : lie(nullptr, 0) {}
    151 
    152     // Construct a new slot index from the given one, and set the slot.
    153     SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) {
    154       assert(lie.getPointer() != nullptr &&
    155              "Attempt to construct index with 0 pointer.");
    156     }
    157 
    158     /// Returns true if this is a valid index. Invalid indicies do
    159     /// not point into an index table, and cannot be compared.
    160     bool isValid() const {
    161       return lie.getPointer();
    162     }
    163 
    164     /// Return true for a valid index.
    165     LLVM_EXPLICIT operator bool() const { return isValid(); }
    166 
    167     /// Print this index to the given raw_ostream.
    168     void print(raw_ostream &os) const;
    169 
    170     /// Dump this index to stderr.
    171     void dump() const;
    172 
    173     /// Compare two SlotIndex objects for equality.
    174     bool operator==(SlotIndex other) const {
    175       return lie == other.lie;
    176     }
    177     /// Compare two SlotIndex objects for inequality.
    178     bool operator!=(SlotIndex other) const {
    179       return lie != other.lie;
    180     }
    181 
    182     /// Compare two SlotIndex objects. Return true if the first index
    183     /// is strictly lower than the second.
    184     bool operator<(SlotIndex other) const {
    185       return getIndex() < other.getIndex();
    186     }
    187     /// Compare two SlotIndex objects. Return true if the first index
    188     /// is lower than, or equal to, the second.
    189     bool operator<=(SlotIndex other) const {
    190       return getIndex() <= other.getIndex();
    191     }
    192 
    193     /// Compare two SlotIndex objects. Return true if the first index
    194     /// is greater than the second.
    195     bool operator>(SlotIndex other) const {
    196       return getIndex() > other.getIndex();
    197     }
    198 
    199     /// Compare two SlotIndex objects. Return true if the first index
    200     /// is greater than, or equal to, the second.
    201     bool operator>=(SlotIndex other) const {
    202       return getIndex() >= other.getIndex();
    203     }
    204 
    205     /// isSameInstr - Return true if A and B refer to the same instruction.
    206     static bool isSameInstr(SlotIndex A, SlotIndex B) {
    207       return A.lie.getPointer() == B.lie.getPointer();
    208     }
    209 
    210     /// isEarlierInstr - Return true if A refers to an instruction earlier than
    211     /// B. This is equivalent to A < B && !isSameInstr(A, B).
    212     static bool isEarlierInstr(SlotIndex A, SlotIndex B) {
    213       return A.listEntry()->getIndex() < B.listEntry()->getIndex();
    214     }
    215 
    216     /// Return the distance from this index to the given one.
    217     int distance(SlotIndex other) const {
    218       return other.getIndex() - getIndex();
    219     }
    220 
    221     /// Return the scaled distance from this index to the given one, where all
    222     /// slots on the same instruction have zero distance.
    223     int getInstrDistance(SlotIndex other) const {
    224       return (other.listEntry()->getIndex() - listEntry()->getIndex())
    225         / Slot_Count;
    226     }
    227 
    228     /// isBlock - Returns true if this is a block boundary slot.
    229     bool isBlock() const { return getSlot() == Slot_Block; }
    230 
    231     /// isEarlyClobber - Returns true if this is an early-clobber slot.
    232     bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; }
    233 
    234     /// isRegister - Returns true if this is a normal register use/def slot.
    235     /// Note that early-clobber slots may also be used for uses and defs.
    236     bool isRegister() const { return getSlot() == Slot_Register; }
    237 
    238     /// isDead - Returns true if this is a dead def kill slot.
    239     bool isDead() const { return getSlot() == Slot_Dead; }
    240 
    241     /// Returns the base index for associated with this index. The base index
    242     /// is the one associated with the Slot_Block slot for the instruction
    243     /// pointed to by this index.
    244     SlotIndex getBaseIndex() const {
    245       return SlotIndex(listEntry(), Slot_Block);
    246     }
    247 
    248     /// Returns the boundary index for associated with this index. The boundary
    249     /// index is the one associated with the Slot_Block slot for the instruction
    250     /// pointed to by this index.
    251     SlotIndex getBoundaryIndex() const {
    252       return SlotIndex(listEntry(), Slot_Dead);
    253     }
    254 
    255     /// Returns the register use/def slot in the current instruction for a
    256     /// normal or early-clobber def.
    257     SlotIndex getRegSlot(bool EC = false) const {
    258       return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
    259     }
    260 
    261     /// Returns the dead def kill slot for the current instruction.
    262     SlotIndex getDeadSlot() const {
    263       return SlotIndex(listEntry(), Slot_Dead);
    264     }
    265 
    266     /// Returns the next slot in the index list. This could be either the
    267     /// next slot for the instruction pointed to by this index or, if this
    268     /// index is a STORE, the first slot for the next instruction.
    269     /// WARNING: This method is considerably more expensive than the methods
    270     /// that return specific slots (getUseIndex(), etc). If you can - please
    271     /// use one of those methods.
    272     SlotIndex getNextSlot() const {
    273       Slot s = getSlot();
    274       if (s == Slot_Dead) {
    275         return SlotIndex(listEntry()->getNextNode(), Slot_Block);
    276       }
    277       return SlotIndex(listEntry(), s + 1);
    278     }
    279 
    280     /// Returns the next index. This is the index corresponding to the this
    281     /// index's slot, but for the next instruction.
    282     SlotIndex getNextIndex() const {
    283       return SlotIndex(listEntry()->getNextNode(), getSlot());
    284     }
    285 
    286     /// Returns the previous slot in the index list. This could be either the
    287     /// previous slot for the instruction pointed to by this index or, if this
    288     /// index is a Slot_Block, the last slot for the previous instruction.
    289     /// WARNING: This method is considerably more expensive than the methods
    290     /// that return specific slots (getUseIndex(), etc). If you can - please
    291     /// use one of those methods.
    292     SlotIndex getPrevSlot() const {
    293       Slot s = getSlot();
    294       if (s == Slot_Block) {
    295         return SlotIndex(listEntry()->getPrevNode(), Slot_Dead);
    296       }
    297       return SlotIndex(listEntry(), s - 1);
    298     }
    299 
    300     /// Returns the previous index. This is the index corresponding to this
    301     /// index's slot, but for the previous instruction.
    302     SlotIndex getPrevIndex() const {
    303       return SlotIndex(listEntry()->getPrevNode(), getSlot());
    304     }
    305 
    306   };
    307 
    308   template <> struct isPodLike<SlotIndex> { static const bool value = true; };
    309 
    310   inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
    311     li.print(os);
    312     return os;
    313   }
    314 
    315   typedef std::pair<SlotIndex, MachineBasicBlock*> IdxMBBPair;
    316 
    317   inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
    318     return V < IM.first;
    319   }
    320 
    321   inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
    322     return IM.first < V;
    323   }
    324 
    325   struct Idx2MBBCompare {
    326     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
    327       return LHS.first < RHS.first;
    328     }
    329   };
    330 
    331   /// SlotIndexes pass.
    332   ///
    333   /// This pass assigns indexes to each instruction.
    334   class SlotIndexes : public MachineFunctionPass {
    335   private:
    336 
    337     typedef ilist<IndexListEntry> IndexList;
    338     IndexList indexList;
    339 
    340 #ifdef EXPENSIVE_CHECKS
    341     IndexList graveyardList;
    342 #endif // EXPENSIVE_CHECKS
    343 
    344     MachineFunction *mf;
    345 
    346     typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
    347     Mi2IndexMap mi2iMap;
    348 
    349     /// MBBRanges - Map MBB number to (start, stop) indexes.
    350     SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges;
    351 
    352     /// Idx2MBBMap - Sorted list of pairs of index of first instruction
    353     /// and MBB id.
    354     SmallVector<IdxMBBPair, 8> idx2MBBMap;
    355 
    356     // IndexListEntry allocator.
    357     BumpPtrAllocator ileAllocator;
    358 
    359     IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
    360       IndexListEntry *entry =
    361         static_cast<IndexListEntry*>(
    362           ileAllocator.Allocate(sizeof(IndexListEntry),
    363           alignOf<IndexListEntry>()));
    364 
    365       new (entry) IndexListEntry(mi, index);
    366 
    367       return entry;
    368     }
    369 
    370     /// Renumber locally after inserting curItr.
    371     void renumberIndexes(IndexList::iterator curItr);
    372 
    373   public:
    374     static char ID;
    375 
    376     SlotIndexes() : MachineFunctionPass(ID) {
    377       initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
    378     }
    379 
    380     void getAnalysisUsage(AnalysisUsage &au) const override;
    381     void releaseMemory() override;
    382 
    383     bool runOnMachineFunction(MachineFunction &fn) override;
    384 
    385     /// Dump the indexes.
    386     void dump() const;
    387 
    388     /// Renumber the index list, providing space for new instructions.
    389     void renumberIndexes();
    390 
    391     /// Repair indexes after adding and removing instructions.
    392     void repairIndexesInRange(MachineBasicBlock *MBB,
    393                               MachineBasicBlock::iterator Begin,
    394                               MachineBasicBlock::iterator End);
    395 
    396     /// Returns the zero index for this analysis.
    397     SlotIndex getZeroIndex() {
    398       assert(indexList.front().getIndex() == 0 && "First index is not 0?");
    399       return SlotIndex(&indexList.front(), 0);
    400     }
    401 
    402     /// Returns the base index of the last slot in this analysis.
    403     SlotIndex getLastIndex() {
    404       return SlotIndex(&indexList.back(), 0);
    405     }
    406 
    407     /// Returns true if the given machine instr is mapped to an index,
    408     /// otherwise returns false.
    409     bool hasIndex(const MachineInstr *instr) const {
    410       return mi2iMap.count(instr);
    411     }
    412 
    413     /// Returns the base index for the given instruction.
    414     SlotIndex getInstructionIndex(const MachineInstr *MI) const {
    415       // Instructions inside a bundle have the same number as the bundle itself.
    416       Mi2IndexMap::const_iterator itr = mi2iMap.find(getBundleStart(MI));
    417       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
    418       return itr->second;
    419     }
    420 
    421     /// Returns the instruction for the given index, or null if the given
    422     /// index has no instruction associated with it.
    423     MachineInstr* getInstructionFromIndex(SlotIndex index) const {
    424       return index.isValid() ? index.listEntry()->getInstr() : nullptr;
    425     }
    426 
    427     /// Returns the next non-null index, if one exists.
    428     /// Otherwise returns getLastIndex().
    429     SlotIndex getNextNonNullIndex(SlotIndex Index) {
    430       IndexList::iterator I = Index.listEntry();
    431       IndexList::iterator E = indexList.end();
    432       while (++I != E)
    433         if (I->getInstr())
    434           return SlotIndex(I, Index.getSlot());
    435       // We reached the end of the function.
    436       return getLastIndex();
    437     }
    438 
    439     /// getIndexBefore - Returns the index of the last indexed instruction
    440     /// before MI, or the start index of its basic block.
    441     /// MI is not required to have an index.
    442     SlotIndex getIndexBefore(const MachineInstr *MI) const {
    443       const MachineBasicBlock *MBB = MI->getParent();
    444       assert(MBB && "MI must be inserted inna basic block");
    445       MachineBasicBlock::const_iterator I = MI, B = MBB->begin();
    446       for (;;) {
    447         if (I == B)
    448           return getMBBStartIdx(MBB);
    449         --I;
    450         Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I);
    451         if (MapItr != mi2iMap.end())
    452           return MapItr->second;
    453       }
    454     }
    455 
    456     /// getIndexAfter - Returns the index of the first indexed instruction
    457     /// after MI, or the end index of its basic block.
    458     /// MI is not required to have an index.
    459     SlotIndex getIndexAfter(const MachineInstr *MI) const {
    460       const MachineBasicBlock *MBB = MI->getParent();
    461       assert(MBB && "MI must be inserted inna basic block");
    462       MachineBasicBlock::const_iterator I = MI, E = MBB->end();
    463       for (;;) {
    464         ++I;
    465         if (I == E)
    466           return getMBBEndIdx(MBB);
    467         Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I);
    468         if (MapItr != mi2iMap.end())
    469           return MapItr->second;
    470       }
    471     }
    472 
    473     /// Return the (start,end) range of the given basic block number.
    474     const std::pair<SlotIndex, SlotIndex> &
    475     getMBBRange(unsigned Num) const {
    476       return MBBRanges[Num];
    477     }
    478 
    479     /// Return the (start,end) range of the given basic block.
    480     const std::pair<SlotIndex, SlotIndex> &
    481     getMBBRange(const MachineBasicBlock *MBB) const {
    482       return getMBBRange(MBB->getNumber());
    483     }
    484 
    485     /// Returns the first index in the given basic block number.
    486     SlotIndex getMBBStartIdx(unsigned Num) const {
    487       return getMBBRange(Num).first;
    488     }
    489 
    490     /// Returns the first index in the given basic block.
    491     SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
    492       return getMBBRange(mbb).first;
    493     }
    494 
    495     /// Returns the last index in the given basic block number.
    496     SlotIndex getMBBEndIdx(unsigned Num) const {
    497       return getMBBRange(Num).second;
    498     }
    499 
    500     /// Returns the last index in the given basic block.
    501     SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
    502       return getMBBRange(mbb).second;
    503     }
    504 
    505     /// Returns the basic block which the given index falls in.
    506     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
    507       if (MachineInstr *MI = getInstructionFromIndex(index))
    508         return MI->getParent();
    509       SmallVectorImpl<IdxMBBPair>::const_iterator I =
    510         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
    511       // Take the pair containing the index
    512       SmallVectorImpl<IdxMBBPair>::const_iterator J =
    513         ((I != idx2MBBMap.end() && I->first > index) ||
    514          (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
    515 
    516       assert(J != idx2MBBMap.end() && J->first <= index &&
    517              index < getMBBEndIdx(J->second) &&
    518              "index does not correspond to an MBB");
    519       return J->second;
    520     }
    521 
    522     bool findLiveInMBBs(SlotIndex start, SlotIndex end,
    523                         SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
    524       SmallVectorImpl<IdxMBBPair>::const_iterator itr =
    525         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
    526       bool resVal = false;
    527 
    528       while (itr != idx2MBBMap.end()) {
    529         if (itr->first >= end)
    530           break;
    531         mbbs.push_back(itr->second);
    532         resVal = true;
    533         ++itr;
    534       }
    535       return resVal;
    536     }
    537 
    538     /// Returns the MBB covering the given range, or null if the range covers
    539     /// more than one basic block.
    540     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
    541 
    542       assert(start < end && "Backwards ranges not allowed.");
    543 
    544       SmallVectorImpl<IdxMBBPair>::const_iterator itr =
    545         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
    546 
    547       if (itr == idx2MBBMap.end()) {
    548         itr = std::prev(itr);
    549         return itr->second;
    550       }
    551 
    552       // Check that we don't cross the boundary into this block.
    553       if (itr->first < end)
    554         return nullptr;
    555 
    556       itr = std::prev(itr);
    557 
    558       if (itr->first <= start)
    559         return itr->second;
    560 
    561       return nullptr;
    562     }
    563 
    564     /// Insert the given machine instruction into the mapping. Returns the
    565     /// assigned index.
    566     /// If Late is set and there are null indexes between mi's neighboring
    567     /// instructions, create the new index after the null indexes instead of
    568     /// before them.
    569     SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool Late = false) {
    570       assert(!mi->isInsideBundle() &&
    571              "Instructions inside bundles should use bundle start's slot.");
    572       assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed.");
    573       // Numbering DBG_VALUE instructions could cause code generation to be
    574       // affected by debug information.
    575       assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions.");
    576 
    577       assert(mi->getParent() != nullptr && "Instr must be added to function.");
    578 
    579       // Get the entries where mi should be inserted.
    580       IndexList::iterator prevItr, nextItr;
    581       if (Late) {
    582         // Insert mi's index immediately before the following instruction.
    583         nextItr = getIndexAfter(mi).listEntry();
    584         prevItr = std::prev(nextItr);
    585       } else {
    586         // Insert mi's index immediately after the preceding instruction.
    587         prevItr = getIndexBefore(mi).listEntry();
    588         nextItr = std::next(prevItr);
    589       }
    590 
    591       // Get a number for the new instr, or 0 if there's no room currently.
    592       // In the latter case we'll force a renumber later.
    593       unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
    594       unsigned newNumber = prevItr->getIndex() + dist;
    595 
    596       // Insert a new list entry for mi.
    597       IndexList::iterator newItr =
    598         indexList.insert(nextItr, createEntry(mi, newNumber));
    599 
    600       // Renumber locally if we need to.
    601       if (dist == 0)
    602         renumberIndexes(newItr);
    603 
    604       SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
    605       mi2iMap.insert(std::make_pair(mi, newIndex));
    606       return newIndex;
    607     }
    608 
    609     /// Remove the given machine instruction from the mapping.
    610     void removeMachineInstrFromMaps(MachineInstr *mi) {
    611       // remove index -> MachineInstr and
    612       // MachineInstr -> index mappings
    613       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
    614       if (mi2iItr != mi2iMap.end()) {
    615         IndexListEntry *miEntry(mi2iItr->second.listEntry());
    616         assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
    617         // FIXME: Eventually we want to actually delete these indexes.
    618         miEntry->setInstr(nullptr);
    619         mi2iMap.erase(mi2iItr);
    620       }
    621     }
    622 
    623     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
    624     /// maps used by register allocator.
    625     void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
    626       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
    627       if (mi2iItr == mi2iMap.end())
    628         return;
    629       SlotIndex replaceBaseIndex = mi2iItr->second;
    630       IndexListEntry *miEntry(replaceBaseIndex.listEntry());
    631       assert(miEntry->getInstr() == mi &&
    632              "Mismatched instruction in index tables.");
    633       miEntry->setInstr(newMI);
    634       mi2iMap.erase(mi2iItr);
    635       mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
    636     }
    637 
    638     /// Add the given MachineBasicBlock into the maps.
    639     void insertMBBInMaps(MachineBasicBlock *mbb) {
    640       MachineFunction::iterator nextMBB =
    641         std::next(MachineFunction::iterator(mbb));
    642 
    643       IndexListEntry *startEntry = nullptr;
    644       IndexListEntry *endEntry = nullptr;
    645       IndexList::iterator newItr;
    646       if (nextMBB == mbb->getParent()->end()) {
    647         startEntry = &indexList.back();
    648         endEntry = createEntry(nullptr, 0);
    649         newItr = indexList.insertAfter(startEntry, endEntry);
    650       } else {
    651         startEntry = createEntry(nullptr, 0);
    652         endEntry = getMBBStartIdx(nextMBB).listEntry();
    653         newItr = indexList.insert(endEntry, startEntry);
    654       }
    655 
    656       SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
    657       SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
    658 
    659       MachineFunction::iterator prevMBB(mbb);
    660       assert(prevMBB != mbb->getParent()->end() &&
    661              "Can't insert a new block at the beginning of a function.");
    662       --prevMBB;
    663       MBBRanges[prevMBB->getNumber()].second = startIdx;
    664 
    665       assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
    666              "Blocks must be added in order");
    667       MBBRanges.push_back(std::make_pair(startIdx, endIdx));
    668       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
    669 
    670       renumberIndexes(newItr);
    671       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
    672     }
    673 
    674     /// \brief Free the resources that were required to maintain a SlotIndex.
    675     ///
    676     /// Once an index is no longer needed (for instance because the instruction
    677     /// at that index has been moved), the resources required to maintain the
    678     /// index can be relinquished to reduce memory use and improve renumbering
    679     /// performance. Any remaining SlotIndex objects that point to the same
    680     /// index are left 'dangling' (much the same as a dangling pointer to a
    681     /// freed object) and should not be accessed, except to destruct them.
    682     ///
    683     /// Like dangling pointers, access to dangling SlotIndexes can cause
    684     /// painful-to-track-down bugs, especially if the memory for the index
    685     /// previously pointed to has been re-used. To detect dangling SlotIndex
    686     /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to
    687     /// be retained in a graveyard instead of being freed. Operations on indexes
    688     /// in the graveyard will trigger an assertion.
    689     void eraseIndex(SlotIndex index) {
    690       IndexListEntry *entry = index.listEntry();
    691 #ifdef EXPENSIVE_CHECKS
    692       indexList.remove(entry);
    693       graveyardList.push_back(entry);
    694       entry->setPoison();
    695 #else
    696       indexList.erase(entry);
    697 #endif
    698     }
    699 
    700   };
    701 
    702 
    703   // Specialize IntervalMapInfo for half-open slot index intervals.
    704   template <>
    705   struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> {
    706   };
    707 
    708 }
    709 
    710 #endif // LLVM_CODEGEN_SLOTINDEXES_H
    711