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     // IndexListEntry allocator.
 409     BumpPtrAllocator ileAllocator;
 410
 411     IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
 412       IndexListEntry *entry =
 413         static_cast<IndexListEntry*>(
 414           ileAllocator.Allocate(sizeof(IndexListEntry),
 415           alignof<IndexListEntry>()));
 416
 417       new (entry) IndexListEntry(mi, index);
 418
 419       return entry;
 420     }
 421
 422     void initList() {
 423       assert(indexListHead == 0 && "Zero entry non-null at initialisation.");
 424       indexListHead = createEntry(0, ~0U);
 425       indexListHead->setNext(0);
 426       indexListHead->setPrev(indexListHead);
 427     }
 428
 429     void clearList() {
 430       indexListHead = 0;
 431       ileAllocator.Reset();
 432     }
 433
 434     IndexListEntry* getTail() {
 435       assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
 436       return indexListHead->getPrev();
 437     }
 438
 439     const IndexListEntry* getTail() const {
 440       assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
 441       return indexListHead->getPrev();
 442     }
 443
 444     // Returns true if the index list is empty.
 445     bool empty() const { return (indexListHead == getTail()); }
 446
 447     IndexListEntry* front() {
 448       assert(!empty() && "front() called on empty index list.");
 449       return indexListHead;
 450     }
 451
 452     const IndexListEntry* front() const {
 453       assert(!empty() && "front() called on empty index list.");
 454       return indexListHead;
 455     }
 456
 457     IndexListEntry* back() {
 458       assert(!empty() && "back() called on empty index list.");
 459       return getTail()->getPrev();
 460     }
 461
 462     const IndexListEntry* back() const {
 463       assert(!empty() && "back() called on empty index list.");
 464       return getTail()->getPrev();
 465     }
 466
 467     /// Insert a new entry before itr.
 468     void insert(IndexListEntry *itr, IndexListEntry *val) {
 469       assert(itr != 0 && "itr should not be null.");
 470       IndexListEntry *prev = itr->getPrev();
 471       val->setNext(itr);
 472       val->setPrev(prev);
 473
 474       if (itr != indexListHead) {
 475         prev->setNext(val);
 476       }
 477       else {
 478         indexListHead = val;
 479       }
 480       itr->setPrev(val);
 481     }
 482
 483     /// Push a new entry on to the end of the list.
 484     void push_back(IndexListEntry *val) {
 485       insert(getTail(), val);
 486     }
 487
 488   public:
 489     static char ID;
 490
 491     SlotIndexes() : MachineFunctionPass(ID), indexListHead(0) {}
 492
 493     virtual void getAnalysisUsage(AnalysisUsage &au) const;
 494     virtual void releaseMemory();
 495
 496     virtual bool runOnMachineFunction(MachineFunction &fn);
 497
 498     /// Dump the indexes.
 499     void dump() const;
 500
 501     /// Renumber the index list, providing space for new instructions.
 502     void renumberIndexes();
 503
 504     /// Returns the zero index for this analysis.
 505     SlotIndex getZeroIndex() {
 506       assert(front()->getIndex() == 0 && "First index is not 0?");
 507       return SlotIndex(front(), 0);
 508     }
 509
 510     /// Returns the base index of the last slot in this analysis.
 511     SlotIndex getLastIndex() {
 512       return SlotIndex(back(), 0);
 513     }
 514
 515     /// Returns the invalid index marker for this analysis.
 516     SlotIndex getInvalidIndex() {
 517       return getZeroIndex();
 518     }
 519
 520     /// Returns the distance between the highest and lowest indexes allocated
 521     /// so far.
 522     unsigned getIndexesLength() const {
 523       assert(front()->getIndex() == 0 &&
 524              "Initial index isn't zero?");
 525
 526       return back()->getIndex();
 527     }
 528
 529     /// Returns the number of instructions in the function.
 530     unsigned getFunctionSize() const {
 531       return functionSize;
 532     }
 533
 534     /// Returns true if the given machine instr is mapped to an index,
 535     /// otherwise returns false.
 536     bool hasIndex(const MachineInstr *instr) const {
 537       return (mi2iMap.find(instr) != mi2iMap.end());
 538     }
 539
 540     /// Returns the base index for the given instruction.
 541     SlotIndex getInstructionIndex(const MachineInstr *instr) const {
 542       Mi2IndexMap::const_iterator itr = mi2iMap.find(instr);
 543       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
 544       return itr->second;
 545     }
 546
 547     /// Returns the instruction for the given index, or null if the given
 548     /// index has no instruction associated with it.
 549     MachineInstr* getInstructionFromIndex(SlotIndex index) const {
 550       return index.entry().getInstr();
 551     }
 552
 553     /// Returns the next non-null index.
 554     SlotIndex getNextNonNullIndex(SlotIndex index) {
 555       SlotIndex nextNonNull = index.getNextIndex();
 556
 557       while (&nextNonNull.entry() != getTail() &&
 558              getInstructionFromIndex(nextNonNull) == 0) {
 559         nextNonNull = nextNonNull.getNextIndex();
 560       }
 561
 562       return nextNonNull;
 563     }
 564
 565     /// Returns the first index in the given basic block.
 566     SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
 567       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 568       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 569       return itr->second.first;
 570     }
 571
 572     /// Returns the last index in the given basic block.
 573     SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
 574       MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
 575       assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
 576       return itr->second.second;
 577     }
 578
 579     /// Returns the basic block which the given index falls in.
 580     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
 581       std::vector<IdxMBBPair>::const_iterator I =
 582         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
 583       // Take the pair containing the index
 584       std::vector<IdxMBBPair>::const_iterator J =
 585         ((I != idx2MBBMap.end() && I->first > index) ||
 586          (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
 587
 588       assert(J != idx2MBBMap.end() && J->first <= index &&
 589              index < getMBBEndIdx(J->second) &&
 590              "index does not correspond to an MBB");
 591       return J->second;
 592     }
 593
 594     bool findLiveInMBBs(SlotIndex start, SlotIndex end,
 595                         SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 596       std::vector<IdxMBBPair>::const_iterator itr =
 597         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 598       bool resVal = false;
 599
 600       while (itr != idx2MBBMap.end()) {
 601         if (itr->first >= end)
 602           break;
 603         mbbs.push_back(itr->second);
 604         resVal = true;
 605         ++itr;
 606       }
 607       return resVal;
 608     }
 609
 610     /// Return a list of MBBs that can be reach via any branches or
 611     /// fall-throughs.
 612     bool findReachableMBBs(SlotIndex start, SlotIndex end,
 613                            SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
 614       std::vector<IdxMBBPair>::const_iterator itr =
 615         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 616
 617       bool resVal = false;
 618       while (itr != idx2MBBMap.end()) {
 619         if (itr->first > end)
 620           break;
 621         MachineBasicBlock *mbb = itr->second;
 622         if (getMBBEndIdx(mbb) > end)
 623           break;
 624         for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(),
 625              se = mbb->succ_end(); si != se; ++si)
 626           mbbs.push_back(*si);
 627         resVal = true;
 628         ++itr;
 629       }
 630       return resVal;
 631     }
 632
 633     /// Returns the MBB covering the given range, or null if the range covers
 634     /// more than one basic block.
 635     MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
 636
 637       assert(start < end && "Backwards ranges not allowed.");
 638
 639       std::vector<IdxMBBPair>::const_iterator itr =
 640         std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
 641
 642       if (itr == idx2MBBMap.end()) {
 643         itr = prior(itr);
 644         return itr->second;
 645       }
 646
 647       // Check that we don't cross the boundary into this block.
 648       if (itr->first < end)
 649         return 0;
 650
 651       itr = prior(itr);
 652
 653       if (itr->first <= start)
 654         return itr->second;
 655
 656       return 0;
 657     }
 658
 659     /// Insert the given machine instruction into the mapping. Returns the
 660     /// assigned index.
 661     SlotIndex insertMachineInstrInMaps(MachineInstr *mi,
 662                                         bool *deferredRenumber = 0) {
 663       assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed.");
 664
 665       MachineBasicBlock *mbb = mi->getParent();
 666
 667       assert(mbb != 0 && "Instr must be added to function.");
 668
 669       MBB2IdxMap::iterator mbbRangeItr = mbb2IdxMap.find(mbb);
 670
 671       assert(mbbRangeItr != mbb2IdxMap.end() &&
 672              "Instruction's parent MBB has not been added to SlotIndexes.");
 673
 674       MachineBasicBlock::iterator miItr(mi);
 675       bool needRenumber = false;
 676       IndexListEntry *newEntry;
 677       // Get previous index, considering that not all instructions are indexed.
 678       IndexListEntry *prevEntry;
 679       for (;;) {
 680         // If mi is at the mbb beginning, get the prev index from the mbb.
 681         if (miItr == mbb->begin()) {
 682           prevEntry = &mbbRangeItr->second.first.entry();
 683           break;
 684         }
 685         // Otherwise rewind until we find a mapped instruction.
 686         Mi2IndexMap::const_iterator itr = mi2iMap.find(--miItr);
 687         if (itr != mi2iMap.end()) {
 688           prevEntry = &itr->second.entry();
 689           break;
 690         }
 691       }
 692
 693       // Get next entry from previous entry.
 694       IndexListEntry *nextEntry = prevEntry->getNext();
 695
 696       // Get a number for the new instr, or 0 if there's no room currently.
 697       // In the latter case we'll force a renumber later.
 698       unsigned dist = nextEntry->getIndex() - prevEntry->getIndex();
 699       unsigned newNumber = dist > SlotIndex::NUM ?
 700         prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0;
 701
 702       if (newNumber == 0) {
 703         needRenumber = true;
 704       }
 705
 706       // Insert a new list entry for mi.
 707       newEntry = createEntry(mi, newNumber);
 708       insert(nextEntry, newEntry);
 709
 710       SlotIndex newIndex(newEntry, SlotIndex::LOAD);
 711       mi2iMap.insert(std::make_pair(mi, newIndex));
 712
 713       if (miItr == mbb->end()) {
 714         // If this is the last instr in the MBB then we need to fix up the bb
 715         // range:
 716         mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE);
 717       }
 718
 719       // Renumber if we need to.
 720       if (needRenumber) {
 721         if (deferredRenumber == 0)
 722           renumberIndexes();
 723         else
 724           *deferredRenumber = true;
 725       }
 726
 727       return newIndex;
 728     }
 729
 730     /// Add all instructions in the vector to the index list. This method will
 731     /// defer renumbering until all instrs have been added, and should be
 732     /// preferred when adding multiple instrs.
 733     void insertMachineInstrsInMaps(SmallVectorImpl<MachineInstr*> &mis) {
 734       bool renumber = false;
 735
 736       for (SmallVectorImpl<MachineInstr*>::iterator
 737            miItr = mis.begin(), miEnd = mis.end();
 738            miItr != miEnd; ++miItr) {
 739         insertMachineInstrInMaps(*miItr, &renumber);
 740       }
 741
 742       if (renumber)
 743         renumberIndexes();
 744     }
 745
 746
 747     /// Remove the given machine instruction from the mapping.
 748     void removeMachineInstrFromMaps(MachineInstr *mi) {
 749       // remove index -> MachineInstr and
 750       // MachineInstr -> index mappings
 751       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 752       if (mi2iItr != mi2iMap.end()) {
 753         IndexListEntry *miEntry(&mi2iItr->second.entry());
 754         assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
 755         // FIXME: Eventually we want to actually delete these indexes.
 756         miEntry->setInstr(0);
 757         mi2iMap.erase(mi2iItr);
 758       }
 759     }
 760
 761     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
 762     /// maps used by register allocator.
 763     void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
 764       Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
 765       if (mi2iItr == mi2iMap.end())
 766         return;
 767       SlotIndex replaceBaseIndex = mi2iItr->second;
 768       IndexListEntry *miEntry(&replaceBaseIndex.entry());
 769       assert(miEntry->getInstr() == mi &&
 770              "Mismatched instruction in index tables.");
 771       miEntry->setInstr(newMI);
 772       mi2iMap.erase(mi2iItr);
 773       mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
 774     }
 775
 776     /// Add the given MachineBasicBlock into the maps.
 777     void insertMBBInMaps(MachineBasicBlock *mbb) {
 778       MachineFunction::iterator nextMBB =
 779         llvm::next(MachineFunction::iterator(mbb));
 780       IndexListEntry *startEntry = createEntry(0, 0);
 781       IndexListEntry *nextEntry = 0;
 782
 783       if (nextMBB == mbb->getParent()->end()) {
 784         nextEntry = getTail();
 785       } else {
 786         nextEntry = &getMBBStartIdx(nextMBB).entry();
 787       }
 788
 789       insert(nextEntry, startEntry);
 790
 791       SlotIndex startIdx(startEntry, SlotIndex::LOAD);
 792       SlotIndex endIdx(nextEntry, SlotIndex::LOAD);
 793
 794       mbb2IdxMap.insert(
 795         std::make_pair(mbb, std::make_pair(startIdx, endIdx)));
 796
 797       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 798
 799       if (MachineFunction::iterator(mbb) != mbb->getParent()->begin()) {
 800         // Have to update the end index of the previous block.
 801         MachineBasicBlock *priorMBB =
 802           llvm::prior(MachineFunction::iterator(mbb));
 803         mbb2IdxMap[priorMBB].second = startIdx;
 804       }
 805
 806       renumberIndexes();
 807       std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
 808
 809     }
 810
 811   };
 812
 813
 814 }
 815
 816 #endif // LLVM_CODEGEN_LIVEINDEX_H