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