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
 474     virtual void getAnalysisUsage(AnalysisUsage &au) const;
 475     virtual void releaseMemory();
 476
 477     virtual bool runOnMachineFunction(MachineFunction &fn);
 478
 479     /// Dump the indexes.
 480     void dump() const;
 481
 482     /// Renumber the index list, providing space for new instructions.
 483     void renumberIndexes();
 484
 485     /// Returns the zero index for this analysis.
 486     SlotIndex getZeroIndex() {
 487       assert(front()->getIndex() == 0 && "First index is not 0?");
 488       return SlotIndex(front(), 0);
 489     }
 490
 491     /// Returns the base index of the last slot in this analysis.
 492     SlotIndex getLastIndex() {
 493       return SlotIndex(back(), 0);
 494     }
 495
 496     /// Returns the invalid index marker for this analysis.
 497     SlotIndex getInvalidIndex() {
 498       return getZeroIndex();
 499     }
 500
 501     /// Returns the distance between the highest and lowest indexes allocated
 502     /// so far.
 503     unsigned getIndexesLength() const {
 504       assert(front()->getIndex() == 0 &&
 505              "Initial index isn't zero?");
 506
 507       return back()->getIndex();
 508     }
 509
 510     /// Returns the number of instructions in the function.
 511     unsigned getFunctionSize() const {
 512       return functionSize;
 513     }
 514
 515     /// Returns true if the given machine instr is mapped to an index,
 516     /// otherwise returns false.
 517     bool hasIndex(const MachineInstr *instr) const {
 518       return (mi2iMap.find(instr) != mi2iMap.end());
 519     }
 520
 521     /// Returns the base index for the given instruction.
 522     SlotIndex getInstructionIndex(const MachineInstr *instr) const {
 523       Mi2IndexMap::const_iterator itr = mi2iMap.find(instr);
 524       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
 525       return itr->second;
 526     }
 527
 528     /// Returns the instruction for the given index, or null if the given
 529     /// index has no instruction associated with it.
 530     MachineInstr* getInstructionFromIndex(SlotIndex index) const {
 531       return index.entry().getInstr();
 532     }
 533
 534     /// Returns the next non-null index.
 535     SlotIndex getNextNonNullIndex(SlotIndex index) {
 536       SlotIndex nextNonNull = index.getNextIndex();
 537
 538       while (&nextNonNull.entry() != getTail() &&
 539              getInstructionFromIndex(nextNonNull) == 0) {
 540         nextNonNull = nextNonNull.getNextIndex();
 541       }
 542
 543       return nextNonNull;
 544     }
 545
 546     /// Returns the first index in the given basic block.
 547     SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
 548       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 549       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 550       return itr->second.first;
 551     }
 552
 553     /// Returns the last index in the given basic block.
 554     SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
 555       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 556       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 557       return itr->second.second;
 558     }
 559
 560     /// Returns the basic block which the given index falls in.
 561     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
 562       std::vector<IdxMBBPair>::const_iterator I =
 563         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
 564       // Take the pair containing the index
 565       std::vector<IdxMBBPair>::const_iterator J =
 566         ((I != idx2MBBMap.end() && I->first > index) ||
 567          (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
 568
 569       assert(J != idx2MBBMap.end() && J->first <= index &&
 570              index < getMBBEndIdx(J->second) &&
 571              "index does not correspond to an MBB");
 572       return J->second;
 573     }
 574
 575     bool findLiveInMBBs(SlotIndex start, SlotIndex end,
 576                         SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 577       std::vector<IdxMBBPair>::const_iterator itr =
 578         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 579       bool resVal = false;
 580
 581       while (itr != idx2MBBMap.end()) {
 582         if (itr->first >= end)
 583           break;
 584         mbbs.push_back(itr->second);
 585         resVal = true;
 586         ++itr;
 587       }
 588       return resVal;
 589     }
 590
 591     /// Return a list of MBBs that can be reach via any branches or
 592     /// fall-throughs.
 593     bool findReachableMBBs(SlotIndex start, SlotIndex end,
 594                            SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 595       std::vector<IdxMBBPair>::const_iterator itr =
 596         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 597
 598       bool resVal = false;
 599       while (itr != idx2MBBMap.end()) {
 600         if (itr->first > end)
 601           break;
 602         MachineBasicBlock *mbb = itr->second;
 603         if (getMBBEndIdx(mbb) > end)
 604           break;
 605         for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(),
 606              se = mbb->succ_end(); si != se; ++si)
 607           mbbs.push_back(*si);
 608         resVal = true;
 609         ++itr;
 610       }
 611       return resVal;
 612     }
 613
 614     /// Returns the MBB covering the given range, or null if the range covers
 615     /// more than one basic block.
 616     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
 617
 618       assert(start < end && "Backwards ranges not allowed.");
 619
 620       std::vector<IdxMBBPair>::const_iterator itr =
 621         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 622
 623       if (itr == idx2MBBMap.end()) {
 624         itr = prior(itr);
 625         return itr->second;
 626       }
 627
 628       // Check that we don't cross the boundary into this block.
 629       if (itr->first < end)
 630         return 0;
 631
 632       itr = prior(itr);
 633
 634       if (itr->first <= start)
 635         return itr->second;
 636
 637       return 0;
 638     }
 639
 640     /// Insert the given machine instruction into the mapping. Returns the
 641     /// assigned index.
 642     SlotIndex insertMachineInstrInMaps(MachineInstr *mi,
 643                                         bool *deferredRenumber = 0) {
 644       assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed.");
 645
 646       MachineBasicBlock *mbb = mi->getParent();
 647
 648       assert(mbb != 0 && "Instr must be added to function.");
 649
 650       MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb);
 651
 652       assert(mbbRangeItr != mbb2IdxMap.end() &&
 653              "Instruction's parent MBB has not been added to SlotIndexes.");
 654
 655       MachineBasicBlock::iterator miItr(mi);
 656       bool needRenumber = false;
 657       IndexListEntry *newEntry;
 658       // Get previous index, considering that not all instructions are indexed.
 659       IndexListEntry *prevEntry;
 660       for (;;) {
 661         // If mi is at the mbb beginning, get the prev index from the mbb.
 662         if (miItr == mbb->begin()) {
 663           prevEntry = &mbbRangeItr->second.first.entry();
 664           break;
 665         }
 666         // Otherwise rewind until we find a mapped instruction.
 667         Mi2IndexMap::const_iterator itr = mi2iMap.find(--miItr);
 668         if (itr != mi2iMap.end()) {
 669           prevEntry = &itr->second.entry();
 670           break;
 671         }
 672       }
 673
 674       // Get next entry from previous entry.
 675       IndexListEntry *nextEntry = prevEntry->getNext();
 676
 677       // Get a number for the new instr, or 0 if there's no room currently.
 678       // In the latter case we'll force a renumber later.
 679       unsigned dist = nextEntry->getIndex() - prevEntry->getIndex();
 680       unsigned newNumber = dist > SlotIndex::NUM ?
 681         prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0;
 682
 683       if (newNumber == 0) {
 684         needRenumber = true;
 685       }
 686
 687       // Insert a new list entry for mi.
 688       newEntry = createEntry(mi, newNumber);
 689       insert(nextEntry, newEntry);
 690
 691       SlotIndex newIndex(newEntry, SlotIndex::LOAD);
 692       mi2iMap.insert(std::make_pair(mi, newIndex));
 693
 694       if (miItr == mbb->end()) {
 695         // If this is the last instr in the MBB then we need to fix up the bb
 696         // range:
 697         mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE);
 698       }
 699
 700       // Renumber if we need to.
 701       if (needRenumber) {
 702         if (deferredRenumber == 0)
 703           renumberIndexes();
 704         else
 705           *deferredRenumber = true;
 706       }
 707
 708       return newIndex;
 709     }
 710
 711     /// Add all instructions in the vector to the index list. This method will
 712     /// defer renumbering until all instrs have been added, and should be
 713     /// preferred when adding multiple instrs.
 714     void insertMachineInstrsInMaps(SmallVectorImpl<MachineInstr*> &mis) {
 715       bool renumber = false;
 716
 717       for (SmallVectorImpl<MachineInstr*>::iterator
 718            miItr = mis.begin(), miEnd = mis.end();
 719            miItr != miEnd; ++miItr) {
 720         insertMachineInstrInMaps(*miItr, &renumber);
 721       }
 722
 723       if (renumber)
 724         renumberIndexes();
 725     }
 726
 727
 728     /// Remove the given machine instruction from the mapping.
 729     void removeMachineInstrFromMaps(MachineInstr *mi) {
 730       // remove index -> MachineInstr and
 731       // MachineInstr -> index mappings
 732       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 733       if (mi2iItr != mi2iMap.end()) {
 734         IndexListEntry *miEntry(&mi2iItr->second.entry());
 735         assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
 736         // FIXME: Eventually we want to actually delete these indexes.
 737         miEntry->setInstr(0);
 738         mi2iMap.erase(mi2iItr);
 739       }
 740     }
 741
 742     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
 743     /// maps used by register allocator.
 744     void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
 745       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 746       if (mi2iItr == mi2iMap.end())
 747         return;
 748       SlotIndex replaceBaseIndex = mi2iItr->second;
 749       IndexListEntry *miEntry(&replaceBaseIndex.entry());
 750       assert(miEntry->getInstr() == mi &&
 751              "Mismatched instruction in index tables.");
 752       miEntry->setInstr(newMI);
 753       mi2iMap.erase(mi2iItr);
 754       mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
 755     }
 756
 757     /// Add the given MachineBasicBlock into the maps.
 758     void insertMBBInMaps(MachineBasicBlock *mbb) {
 759       MachineFunction::iterator nextMBB =
 760         llvm::next(MachineFunction::iterator(mbb));
 761       IndexListEntry *startEntry = createEntry(0, 0);
 762       IndexListEntry *nextEntry = 0;
 763
 764       if (nextMBB == mbb->getParent()->end()) {
 765         nextEntry = getTail();
 766       } else {
 767         nextEntry = &getMBBStartIdx(nextMBB).entry();
 768       }
 769
 770       insert(nextEntry, startEntry);
 771
 772       SlotIndex startIdx(startEntry, SlotIndex::LOAD);
 773       SlotIndex endIdx(nextEntry, SlotIndex::LOAD);
 774
 775       mbb2IdxMap.insert(
 776         std::make_pair(mbb, std::make_pair(startIdx, endIdx)));
 777
 778       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 779
 780       if (MachineFunction::iterator(mbb) != mbb->getParent()->begin()) {
 781         // Have to update the end index of the previous block.
 782         MachineBasicBlock *priorMBB =
 783           llvm::prior(MachineFunction::iterator(mbb));
 784         mbb2IdxMap[priorMBB].second = startIdx;
 785       }
 786
 787       renumberIndexes();
 788       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 789
 790     }
 791
 792   };
 793
 794
 795 }
 796
 797 #endif // LLVM_CODEGEN_LIVEINDEX_H