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