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