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. IndexListEntry(ReservedEntryType r)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 IndexListEntry(MachineInstr * mi,unsigned index)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 isValid()72 bool isValid() const { 73 return (index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX); 74 } 75 getInstr()76 MachineInstr* getInstr() const { return mi; } setInstr(MachineInstr * mi)77 void setInstr(MachineInstr *mi) { 78 assert(isValid() && "Attempt to modify reserved index."); 79 this->mi = mi; 80 } 81 getIndex()82 unsigned getIndex() const { return index; } setIndex(unsigned 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 getNext()90 IndexListEntry* getNext() { return next; } getNext()91 const IndexListEntry* getNext() const { return next; } setNext(IndexListEntry * next)92 void setNext(IndexListEntry *next) { 93 assert(isValid() && "Attempt to modify reserved index."); 94 this->next = next; 95 } 96 getPrev()97 IndexListEntry* getPrev() { return prev; } getPrev()98 const IndexListEntry* getPrev() const { return prev; } setPrev(IndexListEntry * 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: getAsVoidPointer(IndexListEntry * p)117 static inline void* getAsVoidPointer(IndexListEntry *p) { 118 return p; 119 } getFromVoidPointer(void * p)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 alignofLLVM<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 834