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