include/llvm/CodeGen/SlotIndexes.h

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