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