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