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