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