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 purpose 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/ADT/DenseMap.h" 23 #include "llvm/ADT/IntervalMap.h" 24 #include "llvm/ADT/PointerIntPair.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/ilist.h" 27 #include "llvm/CodeGen/MachineFunction.h" 28 #include "llvm/CodeGen/MachineFunctionPass.h" 29 #include "llvm/CodeGen/MachineInstrBundle.h" 30 #include "llvm/Support/Allocator.h" 31 32 namespace llvm { 33 34 /// This class represents an entry in the slot index list held in the 35 /// SlotIndexes pass. It should not be used directly. See the 36 /// SlotIndex & SlotIndexes classes for the public interface to this 37 /// information. 38 class IndexListEntry : public ilist_node<IndexListEntry> { 39 MachineInstr *mi; 40 unsigned index; 41 42 public: 43 44 IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} 45 46 MachineInstr* getInstr() const { return mi; } 47 void setInstr(MachineInstr *mi) { 48 this->mi = mi; 49 } 50 51 unsigned getIndex() const { return index; } 52 void setIndex(unsigned index) { 53 this->index = index; 54 } 55 56 #ifdef EXPENSIVE_CHECKS 57 // When EXPENSIVE_CHECKS is defined, "erased" index list entries will 58 // actually be moved to a "graveyard" list, and have their pointers 59 // poisoned, so that dangling SlotIndex access can be reliably detected. 60 void setPoison() { 61 intptr_t tmp = reinterpret_cast<intptr_t>(mi); 62 assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); 63 tmp |= 0x1; 64 mi = reinterpret_cast<MachineInstr*>(tmp); 65 } 66 67 bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; } 68 #endif // EXPENSIVE_CHECKS 69 }; 70 71 template <> 72 struct ilist_traits<IndexListEntry> : public ilist_default_traits<IndexListEntry> { 73 private: 74 mutable ilist_half_node<IndexListEntry> Sentinel; 75 public: 76 IndexListEntry *createSentinel() const { 77 return static_cast<IndexListEntry*>(&Sentinel); 78 } 79 void destroySentinel(IndexListEntry *) const {} 80 81 IndexListEntry *provideInitialHead() const { return createSentinel(); } 82 IndexListEntry *ensureHead(IndexListEntry*) const { return createSentinel(); } 83 static void noteHead(IndexListEntry*, IndexListEntry*) {} 84 void deleteNode(IndexListEntry *N) {} 85 86 private: 87 void createNode(const IndexListEntry &); 88 }; 89 90 /// SlotIndex - An opaque wrapper around machine indexes. 91 class SlotIndex { 92 friend class SlotIndexes; 93 94 enum Slot { 95 /// Basic block boundary. Used for live ranges entering and leaving a 96 /// block without being live in the layout neighbor. Also used as the 97 /// def slot of PHI-defs. 98 Slot_Block, 99 100 /// Early-clobber register use/def slot. A live range defined at 101 /// Slot_EarlyClobber interferes with normal live ranges killed at 102 /// Slot_Register. Also used as the kill slot for live ranges tied to an 103 /// early-clobber def. 104 Slot_EarlyClobber, 105 106 /// Normal register use/def slot. Normal instructions kill and define 107 /// register live ranges at this slot. 108 Slot_Register, 109 110 /// Dead def kill point. Kill slot for a live range that is defined by 111 /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't 112 /// used anywhere. 113 Slot_Dead, 114 115 Slot_Count 116 }; 117 118 PointerIntPair<IndexListEntry*, 2, unsigned> lie; 119 120 SlotIndex(IndexListEntry *entry, unsigned slot) 121 : lie(entry, slot) {} 122 123 IndexListEntry* listEntry() const { 124 assert(isValid() && "Attempt to compare reserved index."); 125 #ifdef EXPENSIVE_CHECKS 126 assert(!lie.getPointer()->isPoisoned() && 127 "Attempt to access deleted list-entry."); 128 #endif // EXPENSIVE_CHECKS 129 return lie.getPointer(); 130 } 131 132 unsigned getIndex() const { 133 return listEntry()->getIndex() | getSlot(); 134 } 135 136 /// Returns the slot for this SlotIndex. 137 Slot getSlot() const { 138 return static_cast<Slot>(lie.getInt()); 139 } 140 141 public: 142 enum { 143 /// The default distance between instructions as returned by distance(). 144 /// This may vary as instructions are inserted and removed. 145 InstrDist = 4 * Slot_Count 146 }; 147 148 /// Construct an invalid index. 149 SlotIndex() : lie(nullptr, 0) {} 150 151 // Construct a new slot index from the given one, and set the slot. 152 SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) { 153 assert(lie.getPointer() != nullptr && 154 "Attempt to construct index with 0 pointer."); 155 } 156 157 /// Returns true if this is a valid index. Invalid indices do 158 /// not point into an index table, and cannot be compared. 159 bool isValid() const { 160 return lie.getPointer(); 161 } 162 163 /// Return true for a valid index. 164 explicit operator bool() const { return isValid(); } 165 166 /// Print this index to the given raw_ostream. 167 void print(raw_ostream &os) const; 168 169 /// Dump this index to stderr. 170 void dump() const; 171 172 /// Compare two SlotIndex objects for equality. 173 bool operator==(SlotIndex other) const { 174 return lie == other.lie; 175 } 176 /// Compare two SlotIndex objects for inequality. 177 bool operator!=(SlotIndex other) const { 178 return lie != other.lie; 179 } 180 181 /// Compare two SlotIndex objects. Return true if the first index 182 /// is strictly lower than the second. 183 bool operator<(SlotIndex other) const { 184 return getIndex() < other.getIndex(); 185 } 186 /// Compare two SlotIndex objects. Return true if the first index 187 /// is lower than, or equal to, the second. 188 bool operator<=(SlotIndex other) const { 189 return getIndex() <= other.getIndex(); 190 } 191 192 /// Compare two SlotIndex objects. Return true if the first index 193 /// is greater than the second. 194 bool operator>(SlotIndex other) const { 195 return getIndex() > other.getIndex(); 196 } 197 198 /// Compare two SlotIndex objects. Return true if the first index 199 /// is greater than, or equal to, the second. 200 bool operator>=(SlotIndex other) const { 201 return getIndex() >= other.getIndex(); 202 } 203 204 /// isSameInstr - Return true if A and B refer to the same instruction. 205 static bool isSameInstr(SlotIndex A, SlotIndex B) { 206 return A.lie.getPointer() == B.lie.getPointer(); 207 } 208 209 /// isEarlierInstr - Return true if A refers to an instruction earlier than 210 /// B. This is equivalent to A < B && !isSameInstr(A, B). 211 static bool isEarlierInstr(SlotIndex A, SlotIndex B) { 212 return A.listEntry()->getIndex() < B.listEntry()->getIndex(); 213 } 214 215 /// Return true if A refers to the same instruction as B or an earlier one. 216 /// This is equivalent to !isEarlierInstr(B, A). 217 static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B) { 218 return !isEarlierInstr(B, A); 219 } 220 221 /// Return the distance from this index to the given one. 222 int distance(SlotIndex other) const { 223 return other.getIndex() - getIndex(); 224 } 225 226 /// Return the scaled distance from this index to the given one, where all 227 /// slots on the same instruction have zero distance. 228 int getInstrDistance(SlotIndex other) const { 229 return (other.listEntry()->getIndex() - listEntry()->getIndex()) 230 / Slot_Count; 231 } 232 233 /// isBlock - Returns true if this is a block boundary slot. 234 bool isBlock() const { return getSlot() == Slot_Block; } 235 236 /// isEarlyClobber - Returns true if this is an early-clobber slot. 237 bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; } 238 239 /// isRegister - Returns true if this is a normal register use/def slot. 240 /// Note that early-clobber slots may also be used for uses and defs. 241 bool isRegister() const { return getSlot() == Slot_Register; } 242 243 /// isDead - Returns true if this is a dead def kill slot. 244 bool isDead() const { return getSlot() == Slot_Dead; } 245 246 /// Returns the base index for associated with this index. The base index 247 /// is the one associated with the Slot_Block slot for the instruction 248 /// pointed to by this index. 249 SlotIndex getBaseIndex() const { 250 return SlotIndex(listEntry(), Slot_Block); 251 } 252 253 /// Returns the boundary index for associated with this index. The boundary 254 /// index is the one associated with the Slot_Block slot for the instruction 255 /// pointed to by this index. 256 SlotIndex getBoundaryIndex() const { 257 return SlotIndex(listEntry(), Slot_Dead); 258 } 259 260 /// Returns the register use/def slot in the current instruction for a 261 /// normal or early-clobber def. 262 SlotIndex getRegSlot(bool EC = false) const { 263 return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register); 264 } 265 266 /// Returns the dead def kill slot for the current instruction. 267 SlotIndex getDeadSlot() const { 268 return SlotIndex(listEntry(), Slot_Dead); 269 } 270 271 /// Returns the next slot in the index list. This could be either the 272 /// next slot for the instruction pointed to by this index or, if this 273 /// index is a STORE, the first slot for the next instruction. 274 /// WARNING: This method is considerably more expensive than the methods 275 /// that return specific slots (getUseIndex(), etc). If you can - please 276 /// use one of those methods. 277 SlotIndex getNextSlot() const { 278 Slot s = getSlot(); 279 if (s == Slot_Dead) { 280 return SlotIndex(&*++listEntry()->getIterator(), Slot_Block); 281 } 282 return SlotIndex(listEntry(), s + 1); 283 } 284 285 /// Returns the next index. This is the index corresponding to the this 286 /// index's slot, but for the next instruction. 287 SlotIndex getNextIndex() const { 288 return SlotIndex(&*++listEntry()->getIterator(), getSlot()); 289 } 290 291 /// Returns the previous slot in the index list. This could be either the 292 /// previous slot for the instruction pointed to by this index or, if this 293 /// index is a Slot_Block, the last slot for the previous instruction. 294 /// WARNING: This method is considerably more expensive than the methods 295 /// that return specific slots (getUseIndex(), etc). If you can - please 296 /// use one of those methods. 297 SlotIndex getPrevSlot() const { 298 Slot s = getSlot(); 299 if (s == Slot_Block) { 300 return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead); 301 } 302 return SlotIndex(listEntry(), s - 1); 303 } 304 305 /// Returns the previous index. This is the index corresponding to this 306 /// index's slot, but for the previous instruction. 307 SlotIndex getPrevIndex() const { 308 return SlotIndex(&*--listEntry()->getIterator(), getSlot()); 309 } 310 }; 311 312 template <> struct isPodLike<SlotIndex> { static const bool value = true; }; 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 // IndexListEntry allocator. 341 BumpPtrAllocator ileAllocator; 342 343 typedef ilist<IndexListEntry> IndexList; 344 IndexList indexList; 345 346 #ifdef EXPENSIVE_CHECKS 347 IndexList graveyardList; 348 #endif // EXPENSIVE_CHECKS 349 350 MachineFunction *mf; 351 352 typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap; 353 Mi2IndexMap mi2iMap; 354 355 /// MBBRanges - Map MBB number to (start, stop) indexes. 356 SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges; 357 358 /// Idx2MBBMap - Sorted list of pairs of index of first instruction 359 /// and MBB id. 360 SmallVector<IdxMBBPair, 8> idx2MBBMap; 361 362 IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { 363 IndexListEntry *entry = 364 static_cast<IndexListEntry*>( 365 ileAllocator.Allocate(sizeof(IndexListEntry), 366 alignOf<IndexListEntry>())); 367 368 new (entry) IndexListEntry(mi, index); 369 370 return entry; 371 } 372 373 /// Renumber locally after inserting curItr. 374 void renumberIndexes(IndexList::iterator curItr); 375 376 public: 377 static char ID; 378 379 SlotIndexes() : MachineFunctionPass(ID) { 380 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 381 } 382 383 ~SlotIndexes() override { 384 // The indexList's nodes are all allocated in the BumpPtrAllocator. 385 indexList.clearAndLeakNodesUnsafely(); 386 } 387 388 void getAnalysisUsage(AnalysisUsage &au) const override; 389 void releaseMemory() override; 390 391 bool runOnMachineFunction(MachineFunction &fn) override; 392 393 /// Dump the indexes. 394 void dump() const; 395 396 /// Renumber the index list, providing space for new instructions. 397 void renumberIndexes(); 398 399 /// Repair indexes after adding and removing instructions. 400 void repairIndexesInRange(MachineBasicBlock *MBB, 401 MachineBasicBlock::iterator Begin, 402 MachineBasicBlock::iterator End); 403 404 /// Returns the zero index for this analysis. 405 SlotIndex getZeroIndex() { 406 assert(indexList.front().getIndex() == 0 && "First index is not 0?"); 407 return SlotIndex(&indexList.front(), 0); 408 } 409 410 /// Returns the base index of the last slot in this analysis. 411 SlotIndex getLastIndex() { 412 return SlotIndex(&indexList.back(), 0); 413 } 414 415 /// Returns true if the given machine instr is mapped to an index, 416 /// otherwise returns false. 417 bool hasIndex(const MachineInstr &instr) const { 418 return mi2iMap.count(&instr); 419 } 420 421 /// Returns the base index for the given instruction. 422 SlotIndex getInstructionIndex(const MachineInstr &MI) const { 423 // Instructions inside a bundle have the same number as the bundle itself. 424 Mi2IndexMap::const_iterator itr = mi2iMap.find(&getBundleStart(MI)); 425 assert(itr != mi2iMap.end() && "Instruction not found in maps."); 426 return itr->second; 427 } 428 429 /// Returns the instruction for the given index, or null if the given 430 /// index has no instruction associated with it. 431 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 432 return index.isValid() ? index.listEntry()->getInstr() : nullptr; 433 } 434 435 /// Returns the next non-null index, if one exists. 436 /// Otherwise returns getLastIndex(). 437 SlotIndex getNextNonNullIndex(SlotIndex Index) { 438 IndexList::iterator I = Index.listEntry()->getIterator(); 439 IndexList::iterator E = indexList.end(); 440 while (++I != E) 441 if (I->getInstr()) 442 return SlotIndex(&*I, Index.getSlot()); 443 // We reached the end of the function. 444 return getLastIndex(); 445 } 446 447 /// getIndexBefore - Returns the index of the last indexed instruction 448 /// before MI, or the start index of its basic block. 449 /// MI is not required to have an index. 450 SlotIndex getIndexBefore(const MachineInstr &MI) const { 451 const MachineBasicBlock *MBB = MI.getParent(); 452 assert(MBB && "MI must be inserted inna basic block"); 453 MachineBasicBlock::const_iterator I = MI, B = MBB->begin(); 454 for (;;) { 455 if (I == B) 456 return getMBBStartIdx(MBB); 457 --I; 458 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I); 459 if (MapItr != mi2iMap.end()) 460 return MapItr->second; 461 } 462 } 463 464 /// getIndexAfter - Returns the index of the first indexed instruction 465 /// after MI, or the end index of its basic block. 466 /// MI is not required to have an index. 467 SlotIndex getIndexAfter(const MachineInstr &MI) const { 468 const MachineBasicBlock *MBB = MI.getParent(); 469 assert(MBB && "MI must be inserted inna basic block"); 470 MachineBasicBlock::const_iterator I = MI, E = MBB->end(); 471 for (;;) { 472 ++I; 473 if (I == E) 474 return getMBBEndIdx(MBB); 475 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I); 476 if (MapItr != mi2iMap.end()) 477 return MapItr->second; 478 } 479 } 480 481 /// Return the (start,end) range of the given basic block number. 482 const std::pair<SlotIndex, SlotIndex> & 483 getMBBRange(unsigned Num) const { 484 return MBBRanges[Num]; 485 } 486 487 /// Return the (start,end) range of the given basic block. 488 const std::pair<SlotIndex, SlotIndex> & 489 getMBBRange(const MachineBasicBlock *MBB) const { 490 return getMBBRange(MBB->getNumber()); 491 } 492 493 /// Returns the first index in the given basic block number. 494 SlotIndex getMBBStartIdx(unsigned Num) const { 495 return getMBBRange(Num).first; 496 } 497 498 /// Returns the first index in the given basic block. 499 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 500 return getMBBRange(mbb).first; 501 } 502 503 /// Returns the last index in the given basic block number. 504 SlotIndex getMBBEndIdx(unsigned Num) const { 505 return getMBBRange(Num).second; 506 } 507 508 /// Returns the last index in the given basic block. 509 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 510 return getMBBRange(mbb).second; 511 } 512 513 /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block 514 /// begin and basic block) 515 typedef SmallVectorImpl<IdxMBBPair>::const_iterator MBBIndexIterator; 516 /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or 517 /// equal to \p To. 518 MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const { 519 return std::lower_bound(I, idx2MBBMap.end(), To); 520 } 521 /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex 522 /// that is greater or equal to \p Idx. 523 MBBIndexIterator findMBBIndex(SlotIndex Idx) const { 524 return advanceMBBIndex(idx2MBBMap.begin(), Idx); 525 } 526 /// Returns an iterator for the begin of the idx2MBBMap. 527 MBBIndexIterator MBBIndexBegin() const { 528 return idx2MBBMap.begin(); 529 } 530 /// Return an iterator for the end of the idx2MBBMap. 531 MBBIndexIterator MBBIndexEnd() const { 532 return idx2MBBMap.end(); 533 } 534 535 /// Returns the basic block which the given index falls in. 536 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 537 if (MachineInstr *MI = getInstructionFromIndex(index)) 538 return MI->getParent(); 539 540 MBBIndexIterator I = findMBBIndex(index); 541 // Take the pair containing the index 542 MBBIndexIterator J = 543 ((I != MBBIndexEnd() && I->first > index) || 544 (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I; 545 546 assert(J != MBBIndexEnd() && J->first <= index && 547 index < getMBBEndIdx(J->second) && 548 "index does not correspond to an MBB"); 549 return J->second; 550 } 551 552 /// Returns the MBB covering the given range, or null if the range covers 553 /// more than one basic block. 554 MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { 555 556 assert(start < end && "Backwards ranges not allowed."); 557 MBBIndexIterator itr = findMBBIndex(start); 558 if (itr == MBBIndexEnd()) { 559 itr = std::prev(itr); 560 return itr->second; 561 } 562 563 // Check that we don't cross the boundary into this block. 564 if (itr->first < end) 565 return nullptr; 566 567 itr = std::prev(itr); 568 569 if (itr->first <= start) 570 return itr->second; 571 572 return nullptr; 573 } 574 575 /// Insert the given machine instruction into the mapping. Returns the 576 /// assigned index. 577 /// If Late is set and there are null indexes between mi's neighboring 578 /// instructions, create the new index after the null indexes instead of 579 /// before them. 580 SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) { 581 assert(!MI.isInsideBundle() && 582 "Instructions inside bundles should use bundle start's slot."); 583 assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed."); 584 // Numbering DBG_VALUE instructions could cause code generation to be 585 // affected by debug information. 586 assert(!MI.isDebugValue() && "Cannot number DBG_VALUE instructions."); 587 588 assert(MI.getParent() != nullptr && "Instr must be added to function."); 589 590 // Get the entries where MI should be inserted. 591 IndexList::iterator prevItr, nextItr; 592 if (Late) { 593 // Insert MI's index immediately before the following instruction. 594 nextItr = getIndexAfter(MI).listEntry()->getIterator(); 595 prevItr = std::prev(nextItr); 596 } else { 597 // Insert MI's index immediately after the preceding instruction. 598 prevItr = getIndexBefore(MI).listEntry()->getIterator(); 599 nextItr = std::next(prevItr); 600 } 601 602 // Get a number for the new instr, or 0 if there's no room currently. 603 // In the latter case we'll force a renumber later. 604 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; 605 unsigned newNumber = prevItr->getIndex() + dist; 606 607 // Insert a new list entry for MI. 608 IndexList::iterator newItr = 609 indexList.insert(nextItr, createEntry(&MI, newNumber)); 610 611 // Renumber locally if we need to. 612 if (dist == 0) 613 renumberIndexes(newItr); 614 615 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); 616 mi2iMap.insert(std::make_pair(&MI, newIndex)); 617 return newIndex; 618 } 619 620 /// Remove the given machine instruction from the mapping. 621 void removeMachineInstrFromMaps(MachineInstr &MI) { 622 // remove index -> MachineInstr and 623 // MachineInstr -> index mappings 624 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI); 625 if (mi2iItr != mi2iMap.end()) { 626 IndexListEntry *miEntry(mi2iItr->second.listEntry()); 627 assert(miEntry->getInstr() == &MI && "Instruction indexes broken."); 628 // FIXME: Eventually we want to actually delete these indexes. 629 miEntry->setInstr(nullptr); 630 mi2iMap.erase(mi2iItr); 631 } 632 } 633 634 /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in 635 /// maps used by register allocator. 636 void replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) { 637 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI); 638 if (mi2iItr == mi2iMap.end()) 639 return; 640 SlotIndex replaceBaseIndex = mi2iItr->second; 641 IndexListEntry *miEntry(replaceBaseIndex.listEntry()); 642 assert(miEntry->getInstr() == &MI && 643 "Mismatched instruction in index tables."); 644 miEntry->setInstr(&NewMI); 645 mi2iMap.erase(mi2iItr); 646 mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex)); 647 } 648 649 /// Add the given MachineBasicBlock into the maps. 650 void insertMBBInMaps(MachineBasicBlock *mbb) { 651 MachineFunction::iterator nextMBB = 652 std::next(MachineFunction::iterator(mbb)); 653 654 IndexListEntry *startEntry = nullptr; 655 IndexListEntry *endEntry = nullptr; 656 IndexList::iterator newItr; 657 if (nextMBB == mbb->getParent()->end()) { 658 startEntry = &indexList.back(); 659 endEntry = createEntry(nullptr, 0); 660 newItr = indexList.insertAfter(startEntry->getIterator(), endEntry); 661 } else { 662 startEntry = createEntry(nullptr, 0); 663 endEntry = getMBBStartIdx(&*nextMBB).listEntry(); 664 newItr = indexList.insert(endEntry->getIterator(), startEntry); 665 } 666 667 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); 668 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block); 669 670 MachineFunction::iterator prevMBB(mbb); 671 assert(prevMBB != mbb->getParent()->end() && 672 "Can't insert a new block at the beginning of a function."); 673 --prevMBB; 674 MBBRanges[prevMBB->getNumber()].second = startIdx; 675 676 assert(unsigned(mbb->getNumber()) == MBBRanges.size() && 677 "Blocks must be added in order"); 678 MBBRanges.push_back(std::make_pair(startIdx, endIdx)); 679 idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); 680 681 renumberIndexes(newItr); 682 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 683 } 684 685 /// \brief Free the resources that were required to maintain a SlotIndex. 686 /// 687 /// Once an index is no longer needed (for instance because the instruction 688 /// at that index has been moved), the resources required to maintain the 689 /// index can be relinquished to reduce memory use and improve renumbering 690 /// performance. Any remaining SlotIndex objects that point to the same 691 /// index are left 'dangling' (much the same as a dangling pointer to a 692 /// freed object) and should not be accessed, except to destruct them. 693 /// 694 /// Like dangling pointers, access to dangling SlotIndexes can cause 695 /// painful-to-track-down bugs, especially if the memory for the index 696 /// previously pointed to has been re-used. To detect dangling SlotIndex 697 /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to 698 /// be retained in a graveyard instead of being freed. Operations on indexes 699 /// in the graveyard will trigger an assertion. 700 void eraseIndex(SlotIndex index) { 701 IndexListEntry *entry = index.listEntry(); 702 #ifdef EXPENSIVE_CHECKS 703 indexList.remove(entry); 704 graveyardList.push_back(entry); 705 entry->setPoison(); 706 #else 707 indexList.erase(entry); 708 #endif 709 } 710 }; 711 712 // Specialize IntervalMapInfo for half-open slot index intervals. 713 template <> 714 struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> { 715 }; 716 717 } // end namespace llvm 718 719 #endif // LLVM_CODEGEN_SLOTINDEXES_H 720
