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     /// Return a list of MBBs that can be reach via any branches or
 594     /// fall-throughs.
 595     bool findReachableMBBs(SlotIndex start, SlotIndex end,
 596                            SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 597       std::vector<IdxMBBPair>::const_iterator itr =
 598         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 599
 600       bool resVal = false;
 601       while (itr != idx2MBBMap.end()) {
 602         if (itr->first > end)
 603           break;
 604         MachineBasicBlock *mbb = itr->second;
 605         if (getMBBEndIdx(mbb) > end)
 606           break;
 607         for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(),
 608              se = mbb->succ_end(); si != se; ++si)
 609           mbbs.push_back(*si);
 610         resVal = true;
 611         ++itr;
 612       }
 613       return resVal;
 614     }
 615
 616     /// Returns the MBB covering the given range, or null if the range covers
 617     /// more than one basic block.
 618     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
 619
 620       assert(start < end && "Backwards ranges not allowed.");
 621
 622       std::vector<IdxMBBPair>::const_iterator itr =
 623         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 624
 625       if (itr == idx2MBBMap.end()) {
 626         itr = prior(itr);
 627         return itr->second;
 628       }
 629
 630       // Check that we don't cross the boundary into this block.
 631       if (itr->first < end)
 632         return 0;
 633
 634       itr = prior(itr);
 635
 636       if (itr->first <= start)
 637         return itr->second;
 638
 639       return 0;
 640     }
 641
 642     /// Insert the given machine instruction into the mapping. Returns the
 643     /// assigned index.
 644     SlotIndex insertMachineInstrInMaps(MachineInstr *mi,
 645                                         bool *deferredRenumber = 0) {
 646       assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed.");
 647
 648       MachineBasicBlock *mbb = mi->getParent();
 649
 650       assert(mbb != 0 && "Instr must be added to function.");
 651
 652       MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb);
 653
 654       assert(mbbRangeItr != mbb2IdxMap.end() &&
 655              "Instruction's parent MBB has not been added to SlotIndexes.");
 656
 657       MachineBasicBlock::iterator miItr(mi);
 658       bool needRenumber = false;
 659       IndexListEntry *newEntry;
 660       // Get previous index, considering that not all instructions are indexed.
 661       IndexListEntry *prevEntry;
 662       for (;;) {
 663         // If mi is at the mbb beginning, get the prev index from the mbb.
 664         if (miItr == mbb->begin()) {
 665           prevEntry = &mbbRangeItr->second.first.entry();
 666           break;
 667         }
 668         // Otherwise rewind until we find a mapped instruction.
 669         Mi2IndexMap::const_iterator itr = mi2iMap.find(--miItr);
 670         if (itr != mi2iMap.end()) {
 671           prevEntry = &itr->second.entry();
 672           break;
 673         }
 674       }
 675
 676       // Get next entry from previous entry.
 677       IndexListEntry *nextEntry = prevEntry->getNext();
 678
 679       // Get a number for the new instr, or 0 if there's no room currently.
 680       // In the latter case we'll force a renumber later.
 681       unsigned dist = nextEntry->getIndex() - prevEntry->getIndex();
 682       unsigned newNumber = dist > SlotIndex::NUM ?
 683         prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0;
 684
 685       if (newNumber == 0) {
 686         needRenumber = true;
 687       }
 688
 689       // Insert a new list entry for mi.
 690       newEntry = createEntry(mi, newNumber);
 691       insert(nextEntry, newEntry);
 692
 693       SlotIndex newIndex(newEntry, SlotIndex::LOAD);
 694       mi2iMap.insert(std::make_pair(mi, newIndex));
 695
 696       if (miItr == mbb->end()) {
 697         // If this is the last instr in the MBB then we need to fix up the bb
 698         // range:
 699         mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE);
 700       }
 701
 702       // Renumber if we need to.
 703       if (needRenumber) {
 704         if (deferredRenumber == 0)
 705           renumberIndexes();
 706         else
 707           *deferredRenumber = true;
 708       }
 709
 710       return newIndex;
 711     }
 712
 713     /// Add all instructions in the vector to the index list. This method will
 714     /// defer renumbering until all instrs have been added, and should be
 715     /// preferred when adding multiple instrs.
 716     void insertMachineInstrsInMaps(SmallVectorImpl<MachineInstr*> &mis) {
 717       bool renumber = false;
 718
 719       for (SmallVectorImpl<MachineInstr*>::iterator
 720            miItr = mis.begin(), miEnd = mis.end();
 721            miItr != miEnd; ++miItr) {
 722         insertMachineInstrInMaps(*miItr, &renumber);
 723       }
 724
 725       if (renumber)
 726         renumberIndexes();
 727     }
 728
 729
 730     /// Remove the given machine instruction from the mapping.
 731     void removeMachineInstrFromMaps(MachineInstr *mi) {
 732       // remove index -> MachineInstr and
 733       // MachineInstr -> index mappings
 734       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 735       if (mi2iItr != mi2iMap.end()) {
 736         IndexListEntry *miEntry(&mi2iItr->second.entry());
 737         assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
 738         // FIXME: Eventually we want to actually delete these indexes.
 739         miEntry->setInstr(0);
 740         mi2iMap.erase(mi2iItr);
 741       }
 742     }
 743
 744     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
 745     /// maps used by register allocator.
 746     void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
 747       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 748       if (mi2iItr == mi2iMap.end())
 749         return;
 750       SlotIndex replaceBaseIndex = mi2iItr->second;
 751       IndexListEntry *miEntry(&replaceBaseIndex.entry());
 752       assert(miEntry->getInstr() == mi &&
 753              "Mismatched instruction in index tables.");
 754       miEntry->setInstr(newMI);
 755       mi2iMap.erase(mi2iItr);
 756       mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
 757     }
 758
 759     /// Add the given MachineBasicBlock into the maps.
 760     void insertMBBInMaps(MachineBasicBlock *mbb) {
 761       MachineFunction::iterator nextMBB =
 762         llvm::next(MachineFunction::iterator(mbb));
 763       IndexListEntry *startEntry = createEntry(0, 0);
 764       IndexListEntry *nextEntry = 0;
 765
 766       if (nextMBB == mbb->getParent()->end()) {
 767         nextEntry = getTail();
 768       } else {
 769         nextEntry = &getMBBStartIdx(nextMBB).entry();
 770       }
 771
 772       insert(nextEntry, startEntry);
 773
 774       SlotIndex startIdx(startEntry, SlotIndex::LOAD);
 775       SlotIndex endIdx(nextEntry, SlotIndex::LOAD);
 776
 777       mbb2IdxMap.insert(
 778         std::make_pair(mbb, std::make_pair(startIdx, endIdx)));
 779
 780       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 781
 782       if (MachineFunction::iterator(mbb) != mbb->getParent()->begin()) {
 783         // Have to update the end index of the previous block.
 784         MachineBasicBlock *priorMBB =
 785           llvm::prior(MachineFunction::iterator(mbb));
 786         mbb2IdxMap[priorMBB].second = startIdx;
 787       }
 788
 789       renumberIndexes();
 790       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 791
 792     }
 793
 794   };
 795
 796
 797 }
 798
 799 #endif // LLVM_CODEGEN_LIVEINDEX_H