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 purpuse 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/MachineBasicBlock.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFunctionPass.h"
  25 #include "llvm/ADT/PointerIntPair.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/Support/Allocator.h"
  29
  30 namespace llvm {
  31
  32   /// This class represents an entry in the slot index list held in the
  33   /// SlotIndexes pass. It should not be used directly. See the
  34   /// SlotIndex & SlotIndexes classes for the public interface to this
  35   /// information.
  36   class IndexListEntry {
  37     static const unsigned EMPTY_KEY_INDEX = ~0U & ~3U,
  38                           TOMBSTONE_KEY_INDEX = ~0U & ~7U;
  39
  40     IndexListEntry *next, *prev;
  41     MachineInstr *mi;
  42     unsigned index;
  43
  44   protected:
  45
  46     typedef enum { EMPTY_KEY, TOMBSTONE_KEY } ReservedEntryType;
  47
  48     // This constructor is only to be used by getEmptyKeyEntry
  49     // & getTombstoneKeyEntry. It sets index to the given
  50     // value and mi to zero.
  51     IndexListEntry(ReservedEntryType r) : mi(0) {
  52       switch(r) {
  53         case EMPTY_KEY: index = EMPTY_KEY_INDEX; break;
  54         case TOMBSTONE_KEY: index = TOMBSTONE_KEY_INDEX; break;
  55         default: assert(false && "Invalid value for constructor.");
  56       }
  57       next = this;
  58       prev = this;
  59     }
  60
  61   public:
  62
  63     IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {
  64       assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX &&
  65              "Attempt to create invalid index. "
  66              "Available indexes may have been exhausted?.");
  67     }
  68
  69     bool isValid() const {
  70       return (index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX);
  71     }
  72
  73     MachineInstr* getInstr() const { return mi; }
  74     void setInstr(MachineInstr *mi) {
  75       assert(isValid() && "Attempt to modify reserved index.");
  76       this->mi = mi;
  77     }
  78
  79     unsigned getIndex() const { return index; }
  80     void setIndex(unsigned index) {
  81       assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX &&
  82              "Attempt to set index to invalid value.");
  83       assert(isValid() && "Attempt to reset reserved index value.");
  84       this->index = index;
  85     }
  86
  87     IndexListEntry* getNext() { return next; }
  88     const IndexListEntry* getNext() const { return next; }
  89     void setNext(IndexListEntry *next) {
  90       assert(isValid() && "Attempt to modify reserved index.");
  91       this->next = next;
  92     }
  93
  94     IndexListEntry* getPrev() { return prev; }
  95     const IndexListEntry* getPrev() const { return prev; }
  96     void setPrev(IndexListEntry *prev) {
  97       assert(isValid() && "Attempt to modify reserved index.");
  98       this->prev = prev;
  99     }
 100
 101     // This function returns the index list entry that is to be used for empty
 102     // SlotIndex keys.
 103     static IndexListEntry* getEmptyKeyEntry();
 104
 105     // This function returns the index list entry that is to be used for
 106     // tombstone SlotIndex keys.
 107     static IndexListEntry* getTombstoneKeyEntry();
 108   };
 109
 110   // Specialize PointerLikeTypeTraits for IndexListEntry.
 111   template <>
 112   class PointerLikeTypeTraits<IndexListEntry*> {
 113   public:
 114     static inline void* getAsVoidPointer(IndexListEntry *p) {
 115       return p;
 116     }
 117     static inline IndexListEntry* getFromVoidPointer(void *p) {
 118       return static_cast<IndexListEntry*>(p);
 119     }
 120     enum { NumLowBitsAvailable = 3 };
 121   };
 122
 123   /// SlotIndex - An opaque wrapper around machine indexes.
 124   class SlotIndex {
 125     friend class SlotIndexes;
 126     friend struct DenseMapInfo<SlotIndex>;
 127
 128     enum Slot { LOAD, USE, DEF, STORE, NUM };
 129
 130     PointerIntPair<IndexListEntry*, 2, unsigned> lie;
 131
 132     SlotIndex(IndexListEntry *entry, unsigned slot)
 133       : lie(entry, slot) {
 134       assert(entry != 0 && "Attempt to construct index with 0 pointer.");
 135     }
 136
 137     IndexListEntry& entry() const {
 138       return *lie.getPointer();
 139     }
 140
 141     int getIndex() const {
 142       return entry().getIndex() | getSlot();
 143     }
 144
 145     /// Returns the slot for this SlotIndex.
 146     Slot getSlot() const {
 147       return static_cast<Slot>(lie.getInt());
 148     }
 149
 150     static inline unsigned getHashValue(const SlotIndex &v) {
 151       IndexListEntry *ptrVal = &v.entry();
 152       return (unsigned((intptr_t)ptrVal) >> 4) ^
 153              (unsigned((intptr_t)ptrVal) >> 9);
 154     }
 155
 156   public:
 157     static inline SlotIndex getEmptyKey() {
 158       return SlotIndex(IndexListEntry::getEmptyKeyEntry(), 0);
 159     }
 160
 161     static inline SlotIndex getTombstoneKey() {
 162       return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0);
 163     }
 164
 165     /// Construct an invalid index.
 166     SlotIndex() : lie(IndexListEntry::getEmptyKeyEntry(), 0) {}
 167
 168     // Construct a new slot index from the given one, and set the slot.
 169     SlotIndex(const SlotIndex &li, Slot s)
 170       : lie(&li.entry(), unsigned(s)) {
 171       assert(lie.getPointer() != 0 &&
 172              "Attempt to construct index with 0 pointer.");
 173     }
 174
 175     /// Returns true if this is a valid index. Invalid indicies do
 176     /// not point into an index table, and cannot be compared.
 177     bool isValid() const {
 178       IndexListEntry *entry = lie.getPointer();
 179       return ((entry!= 0) && (entry->isValid()));
 180     }
 181
 182     /// Print this index to the given raw_ostream.
 183     void print(raw_ostream &os) const;
 184
 185     /// Dump this index to stderr.
 186     void dump() const;
 187
 188     /// Compare two SlotIndex objects for equality.
 189     bool operator==(SlotIndex other) const {
 190       return getIndex() == other.getIndex();
 191     }
 192     /// Compare two SlotIndex objects for inequality.
 193     bool operator!=(SlotIndex other) const {
 194       return getIndex() != other.getIndex();
 195     }
 196
 197     /// Compare two SlotIndex objects. Return true if the first index
 198     /// is strictly lower than the second.
 199     bool operator<(SlotIndex other) const {
 200       return getIndex() < other.getIndex();
 201     }
 202     /// Compare two SlotIndex objects. Return true if the first index
 203     /// is lower than, or equal to, the second.
 204     bool operator<=(SlotIndex other) const {
 205       return getIndex() <= other.getIndex();
 206     }
 207
 208     /// Compare two SlotIndex objects. Return true if the first index
 209     /// is greater than the second.
 210     bool operator>(SlotIndex other) const {
 211       return getIndex() > other.getIndex();
 212     }
 213
 214     /// Compare two SlotIndex objects. Return true if the first index
 215     /// is greater than, or equal to, the second.
 216     bool operator>=(SlotIndex other) const {
 217       return getIndex() >= other.getIndex();
 218     }
 219
 220     /// Return the distance from this index to the given one.
 221     int distance(SlotIndex other) const {
 222       return other.getIndex() - getIndex();
 223     }
 224
 225     /// isLoad - Return true if this is a LOAD slot.
 226     bool isLoad() const {
 227       return getSlot() == LOAD;
 228     }
 229
 230     /// isDef - Return true if this is a DEF slot.
 231     bool isDef() const {
 232       return getSlot() == DEF;
 233     }
 234
 235     /// isUse - Return true if this is a USE slot.
 236     bool isUse() const {
 237       return getSlot() == USE;
 238     }
 239
 240     /// isStore - Return true if this is a STORE slot.
 241     bool isStore() const {
 242       return getSlot() == STORE;
 243     }
 244
 245     /// Returns the base index for associated with this index. The base index
 246     /// is the one associated with the LOAD slot for the instruction pointed to
 247     /// by this index.
 248     SlotIndex getBaseIndex() const {
 249       return getLoadIndex();
 250     }
 251
 252     /// Returns the boundary index for associated with this index. The boundary
 253     /// index is the one associated with the LOAD slot for the instruction
 254     /// pointed to by this index.
 255     SlotIndex getBoundaryIndex() const {
 256       return getStoreIndex();
 257     }
 258
 259     /// Returns the index of the LOAD slot for the instruction pointed to by
 260     /// this index.
 261     SlotIndex getLoadIndex() const {
 262       return SlotIndex(&entry(), SlotIndex::LOAD);
 263     }
 264
 265     /// Returns the index of the USE slot for the instruction pointed to by
 266     /// this index.
 267     SlotIndex getUseIndex() const {
 268       return SlotIndex(&entry(), SlotIndex::USE);
 269     }
 270
 271     /// Returns the index of the DEF slot for the instruction pointed to by
 272     /// this index.
 273     SlotIndex getDefIndex() const {
 274       return SlotIndex(&entry(), SlotIndex::DEF);
 275     }
 276
 277     /// Returns the index of the STORE slot for the instruction pointed to by
 278     /// this index.
 279     SlotIndex getStoreIndex() const {
 280       return SlotIndex(&entry(), SlotIndex::STORE);
 281     }
 282
 283     /// Returns the next slot in the index list. This could be either the
 284     /// next slot for the instruction pointed to by this index or, if this
 285     /// index is a STORE, the first slot for the next instruction.
 286     /// WARNING: This method is considerably more expensive than the methods
 287     /// that return specific slots (getUseIndex(), etc). If you can - please
 288     /// use one of those methods.
 289     SlotIndex getNextSlot() const {
 290       Slot s = getSlot();
 291       if (s == SlotIndex::STORE) {
 292         return SlotIndex(entry().getNext(), SlotIndex::LOAD);
 293       }
 294       return SlotIndex(&entry(), s + 1);
 295     }
 296
 297     /// Returns the next index. This is the index corresponding to the this
 298     /// index's slot, but for the next instruction.
 299     SlotIndex getNextIndex() const {
 300       return SlotIndex(entry().getNext(), getSlot());
 301     }
 302
 303     /// Returns the previous slot in the index list. This could be either the
 304     /// previous slot for the instruction pointed to by this index or, if this
 305     /// index is a LOAD, the last slot for the previous instruction.
 306     /// WARNING: This method is considerably more expensive than the methods
 307     /// that return specific slots (getUseIndex(), etc). If you can - please
 308     /// use one of those methods.
 309     SlotIndex getPrevSlot() const {
 310       Slot s = getSlot();
 311       if (s == SlotIndex::LOAD) {
 312         return SlotIndex(entry().getPrev(), SlotIndex::STORE);
 313       }
 314       return SlotIndex(&entry(), s - 1);
 315     }
 316
 317     /// Returns the previous index. This is the index corresponding to this
 318     /// index's slot, but for the previous instruction.
 319     SlotIndex getPrevIndex() const {
 320       return SlotIndex(entry().getPrev(), getSlot());
 321     }
 322
 323   };
 324
 325   /// DenseMapInfo specialization for SlotIndex.
 326   template <>
 327   struct DenseMapInfo<SlotIndex> {
 328     static inline SlotIndex getEmptyKey() {
 329       return SlotIndex::getEmptyKey();
 330     }
 331     static inline SlotIndex getTombstoneKey() {
 332       return SlotIndex::getTombstoneKey();
 333     }
 334     static inline unsigned getHashValue(const SlotIndex &v) {
 335       return SlotIndex::getHashValue(v);
 336     }
 337     static inline bool isEqual(const SlotIndex &LHS, const SlotIndex &RHS) {
 338       return (LHS == RHS);
 339     }
 340   };
 341
 342   template <> struct isPodLike<SlotIndex> { static const bool value = true; };
 343
 344
 345   inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
 346     li.print(os);
 347     return os;
 348   }
 349
 350   typedef std::pair<SlotIndex, MachineBasicBlock*> IdxMBBPair;
 351
 352   inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
 353     return V < IM.first;
 354   }
 355
 356   inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
 357     return IM.first < V;
 358   }
 359
 360   struct Idx2MBBCompare {
 361     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
 362       return LHS.first < RHS.first;
 363     }
 364   };
 365
 366   /// SlotIndexes pass.
 367   ///
 368   /// This pass assigns indexes to each instruction.
 369   class SlotIndexes : public MachineFunctionPass {
 370   private:
 371
 372     MachineFunction *mf;
 373     IndexListEntry *indexListHead;
 374     unsigned functionSize;
 375
 376     typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
 377     Mi2IndexMap mi2iMap;
 378
 379     /// MBB2IdxMap - The indexes of the first and last instructions in the
 380     /// specified basic block.
 381     typedef DenseMap<const MachineBasicBlock*,
 382                      std::pair<SlotIndex, SlotIndex> > MBB2IdxMap;
 383     MBB2IdxMap mbb2IdxMap;
 384
 385     /// Idx2MBBMap - Sorted list of pairs of index of first instruction
 386     /// and MBB id.
 387     std::vector<IdxMBBPair> idx2MBBMap;
 388
 389     // IndexListEntry allocator.
 390     BumpPtrAllocator ileAllocator;
 391
 392     IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
 393       IndexListEntry *entry =
 394         static_cast<IndexListEntry*>(
 395           ileAllocator.Allocate(sizeof(IndexListEntry),
 396           alignOf<IndexListEntry>()));
 397
 398       new (entry) IndexListEntry(mi, index);
 399
 400       return entry;
 401     }
 402
 403     void initList() {
 404       assert(indexListHead == 0 && "Zero entry non-null at initialisation.");
 405       indexListHead = createEntry(0, ~0U);
 406       indexListHead->setNext(0);
 407       indexListHead->setPrev(indexListHead);
 408     }
 409
 410     void clearList() {
 411       indexListHead = 0;
 412       ileAllocator.Reset();
 413     }
 414
 415     IndexListEntry* getTail() {
 416       assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
 417       return indexListHead->getPrev();
 418     }
 419
 420     const IndexListEntry* getTail() const {
 421       assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
 422       return indexListHead->getPrev();
 423     }
 424
 425     // Returns true if the index list is empty.
 426     bool empty() const { return (indexListHead == getTail()); }
 427
 428     IndexListEntry* front() {
 429       assert(!empty() && "front() called on empty index list.");
 430       return indexListHead;
 431     }
 432
 433     const IndexListEntry* front() const {
 434       assert(!empty() && "front() called on empty index list.");
 435       return indexListHead;
 436     }
 437
 438     IndexListEntry* back() {
 439       assert(!empty() && "back() called on empty index list.");
 440       return getTail()->getPrev();
 441     }
 442
 443     const IndexListEntry* back() const {
 444       assert(!empty() && "back() called on empty index list.");
 445       return getTail()->getPrev();
 446     }
 447
 448     /// Insert a new entry before itr.
 449     void insert(IndexListEntry *itr, IndexListEntry *val) {
 450       assert(itr != 0 && "itr should not be null.");
 451       IndexListEntry *prev = itr->getPrev();
 452       val->setNext(itr);
 453       val->setPrev(prev);
 454
 455       if (itr != indexListHead) {
 456         prev->setNext(val);
 457       }
 458       else {
 459         indexListHead = val;
 460       }
 461       itr->setPrev(val);
 462     }
 463
 464     /// Push a new entry on to the end of the list.
 465     void push_back(IndexListEntry *val) {
 466       insert(getTail(), val);
 467     }
 468
 469   public:
 470     static char ID;
 471
 472     SlotIndexes() : MachineFunctionPass(ID), indexListHead(0) {
 473       initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 474     }
 475
 476     virtual void getAnalysisUsage(AnalysisUsage &au) const;
 477     virtual void releaseMemory();
 478
 479     virtual bool runOnMachineFunction(MachineFunction &fn);
 480
 481     /// Dump the indexes.
 482     void dump() const;
 483
 484     /// Renumber the index list, providing space for new instructions.
 485     void renumberIndexes();
 486
 487     /// Returns the zero index for this analysis.
 488     SlotIndex getZeroIndex() {
 489       assert(front()->getIndex() == 0 && "First index is not 0?");
 490       return SlotIndex(front(), 0);
 491     }
 492
 493     /// Returns the base index of the last slot in this analysis.
 494     SlotIndex getLastIndex() {
 495       return SlotIndex(back(), 0);
 496     }
 497
 498     /// Returns the invalid index marker for this analysis.
 499     SlotIndex getInvalidIndex() {
 500       return getZeroIndex();
 501     }
 502
 503     /// Returns the distance between the highest and lowest indexes allocated
 504     /// so far.
 505     unsigned getIndexesLength() const {
 506       assert(front()->getIndex() == 0 &&
 507              "Initial index isn't zero?");
 508
 509       return back()->getIndex();
 510     }
 511
 512     /// Returns the number of instructions in the function.
 513     unsigned getFunctionSize() const {
 514       return functionSize;
 515     }
 516
 517     /// Returns true if the given machine instr is mapped to an index,
 518     /// otherwise returns false.
 519     bool hasIndex(const MachineInstr *instr) const {
 520       return (mi2iMap.find(instr) != mi2iMap.end());
 521     }
 522
 523     /// Returns the base index for the given instruction.
 524     SlotIndex getInstructionIndex(const MachineInstr *instr) const {
 525       Mi2IndexMap::const_iterator itr = mi2iMap.find(instr);
 526       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
 527       return itr->second;
 528     }
 529
 530     /// Returns the instruction for the given index, or null if the given
 531     /// index has no instruction associated with it.
 532     MachineInstr* getInstructionFromIndex(SlotIndex index) const {
 533       return index.entry().getInstr();
 534     }
 535
 536     /// Returns the next non-null index.
 537     SlotIndex getNextNonNullIndex(SlotIndex index) {
 538       SlotIndex nextNonNull = index.getNextIndex();
 539
 540       while (&nextNonNull.entry() != getTail() &&
 541              getInstructionFromIndex(nextNonNull) == 0) {
 542         nextNonNull = nextNonNull.getNextIndex();
 543       }
 544
 545       return nextNonNull;
 546     }
 547
 548     /// Returns the first index in the given basic block.
 549     SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
 550       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 551       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 552       return itr->second.first;
 553     }
 554
 555     /// Returns the last index in the given basic block.
 556     SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
 557       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 558       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 559       return itr->second.second;
 560     }
 561
 562     /// Returns the basic block which the given index falls in.
 563     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
 564       std::vector<IdxMBBPair>::const_iterator I =
 565         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
 566       // Take the pair containing the index
 567       std::vector<IdxMBBPair>::const_iterator J =
 568         ((I != idx2MBBMap.end() && I->first > index) ||
 569          (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
 570
 571       assert(J != idx2MBBMap.end() && J->first <= index &&
 572              index < getMBBEndIdx(J->second) &&
 573              "index does not correspond to an MBB");
 574       return J->second;
 575     }
 576
 577     bool findLiveInMBBs(SlotIndex start, SlotIndex end,
 578                         SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 579       std::vector<IdxMBBPair>::const_iterator itr =
 580         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 581       bool resVal = false;
 582
 583       while (itr != idx2MBBMap.end()) {
 584         if (itr->first >= end)
 585           break;
 586         mbbs.push_back(itr->second);
 587         resVal = true;
 588         ++itr;
 589       }
 590       return resVal;
 591     }
 592
 593     /// Returns the MBB covering the given range, or null if the range covers
 594     /// more than one basic block.
 595     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
 596
 597       assert(start < end && "Backwards ranges not allowed.");
 598
 599       std::vector<IdxMBBPair>::const_iterator itr =
 600         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 601
 602       if (itr == idx2MBBMap.end()) {
 603         itr = prior(itr);
 604         return itr->second;
 605       }
 606
 607       // Check that we don't cross the boundary into this block.
 608       if (itr->first < end)
 609         return 0;
 610
 611       itr = prior(itr);
 612
 613       if (itr->first <= start)
 614         return itr->second;
 615
 616       return 0;
 617     }
 618
 619     /// Insert the given machine instruction into the mapping. Returns the
 620     /// assigned index.
 621     SlotIndex insertMachineInstrInMaps(MachineInstr *mi,
 622                                         bool *deferredRenumber = 0) {
 623       assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed.");
 624
 625       MachineBasicBlock *mbb = mi->getParent();
 626
 627       assert(mbb != 0 && "Instr must be added to function.");
 628
 629       MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb);
 630
 631       assert(mbbRangeItr != mbb2IdxMap.end() &&
 632              "Instruction's parent MBB has not been added to SlotIndexes.");
 633
 634       MachineBasicBlock::iterator miItr(mi);
 635       bool needRenumber = false;
 636       IndexListEntry *newEntry;
 637       // Get previous index, considering that not all instructions are indexed.
 638       IndexListEntry *prevEntry;
 639       for (;;) {
 640         // If mi is at the mbb beginning, get the prev index from the mbb.
 641         if (miItr == mbb->begin()) {
 642           prevEntry = &mbbRangeItr->second.first.entry();
 643           break;
 644         }
 645         // Otherwise rewind until we find a mapped instruction.
 646         Mi2IndexMap::const_iterator itr = mi2iMap.find(--miItr);
 647         if (itr != mi2iMap.end()) {
 648           prevEntry = &itr->second.entry();
 649           break;
 650         }
 651       }
 652
 653       // Get next entry from previous entry.
 654       IndexListEntry *nextEntry = prevEntry->getNext();
 655
 656       // Get a number for the new instr, or 0 if there's no room currently.
 657       // In the latter case we'll force a renumber later.
 658       unsigned dist = nextEntry->getIndex() - prevEntry->getIndex();
 659       unsigned newNumber = dist > SlotIndex::NUM ?
 660         prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0;
 661
 662       if (newNumber == 0) {
 663         needRenumber = true;
 664       }
 665
 666       // Insert a new list entry for mi.
 667       newEntry = createEntry(mi, newNumber);
 668       insert(nextEntry, newEntry);
 669
 670       SlotIndex newIndex(newEntry, SlotIndex::LOAD);
 671       mi2iMap.insert(std::make_pair(mi, newIndex));
 672
 673       if (miItr == mbb->end()) {
 674         // If this is the last instr in the MBB then we need to fix up the bb
 675         // range:
 676         mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE);
 677       }
 678
 679       // Renumber if we need to.
 680       if (needRenumber) {
 681         if (deferredRenumber == 0)
 682           renumberIndexes();
 683         else
 684           *deferredRenumber = true;
 685       }
 686
 687       return newIndex;
 688     }
 689
 690     /// Add all instructions in the vector to the index list. This method will
 691     /// defer renumbering until all instrs have been added, and should be
 692     /// preferred when adding multiple instrs.
 693     void insertMachineInstrsInMaps(SmallVectorImpl<MachineInstr*> &mis) {
 694       bool renumber = false;
 695
 696       for (SmallVectorImpl<MachineInstr*>::iterator
 697            miItr = mis.begin(), miEnd = mis.end();
 698            miItr != miEnd; ++miItr) {
 699         insertMachineInstrInMaps(*miItr, &renumber);
 700       }
 701
 702       if (renumber)
 703         renumberIndexes();
 704     }
 705
 706
 707     /// Remove the given machine instruction from the mapping.
 708     void removeMachineInstrFromMaps(MachineInstr *mi) {
 709       // remove index -> MachineInstr and
 710       // MachineInstr -> index mappings
 711       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 712       if (mi2iItr != mi2iMap.end()) {
 713         IndexListEntry *miEntry(&mi2iItr->second.entry());
 714         assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
 715         // FIXME: Eventually we want to actually delete these indexes.
 716         miEntry->setInstr(0);
 717         mi2iMap.erase(mi2iItr);
 718       }
 719     }
 720
 721     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
 722     /// maps used by register allocator.
 723     void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
 724       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 725       if (mi2iItr == mi2iMap.end())
 726         return;
 727       SlotIndex replaceBaseIndex = mi2iItr->second;
 728       IndexListEntry *miEntry(&replaceBaseIndex.entry());
 729       assert(miEntry->getInstr() == mi &&
 730              "Mismatched instruction in index tables.");
 731       miEntry->setInstr(newMI);
 732       mi2iMap.erase(mi2iItr);
 733       mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
 734     }
 735
 736     /// Add the given MachineBasicBlock into the maps.
 737     void insertMBBInMaps(MachineBasicBlock *mbb) {
 738       MachineFunction::iterator nextMBB =
 739         llvm::next(MachineFunction::iterator(mbb));
 740       IndexListEntry *startEntry = createEntry(0, 0);
 741       IndexListEntry *nextEntry = 0;
 742
 743       if (nextMBB == mbb->getParent()->end()) {
 744         nextEntry = getTail();
 745       } else {
 746         nextEntry = &getMBBStartIdx(nextMBB).entry();
 747       }
 748
 749       insert(nextEntry, startEntry);
 750
 751       SlotIndex startIdx(startEntry, SlotIndex::LOAD);
 752       SlotIndex endIdx(nextEntry, SlotIndex::LOAD);
 753
 754       mbb2IdxMap.insert(
 755         std::make_pair(mbb, std::make_pair(startIdx, endIdx)));
 756
 757       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 758
 759       if (MachineFunction::iterator(mbb) != mbb->getParent()->begin()) {
 760         // Have to update the end index of the previous block.
 761         MachineBasicBlock *priorMBB =
 762           llvm::prior(MachineFunction::iterator(mbb));
 763         mbb2IdxMap[priorMBB].second = startIdx;
 764       }
 765
 766       renumberIndexes();
 767       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 768
 769     }
 770
 771   };
 772
 773
 774 }
 775
 776 #endif // LLVM_CODEGEN_LIVEINDEX_H