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