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