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