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