1 //===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements SlotIndex and related classes. The purpose of SlotIndex 10 // is to describe a position at which a register can become live, or cease to 11 // be live. 12 // 13 // SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which 14 // is held is LiveIntervals and provides the real numbering. This allows 15 // LiveIntervals to perform largely transparent renumbering. 16 //===----------------------------------------------------------------------===// 17 18 #ifndef LLVM_CODEGEN_SLOTINDEXES_H 19 #define LLVM_CODEGEN_SLOTINDEXES_H 20 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/IntervalMap.h" 23 #include "llvm/ADT/PointerIntPair.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/ADT/ilist.h" 26 #include "llvm/CodeGen/MachineBasicBlock.h" 27 #include "llvm/CodeGen/MachineFunction.h" 28 #include "llvm/CodeGen/MachineFunctionPass.h" 29 #include "llvm/CodeGen/MachineInstr.h" 30 #include "llvm/CodeGen/MachineInstrBundle.h" 31 #include "llvm/Support/Allocator.h" 32 #include <algorithm> 33 #include <cassert> 34 #include <iterator> 35 #include <utility> 36 37 namespace llvm { 38 39 class raw_ostream; 40 41 /// This class represents an entry in the slot index list held in the 42 /// SlotIndexes pass. It should not be used directly. See the 43 /// SlotIndex & SlotIndexes classes for the public interface to this 44 /// information. 45 class IndexListEntry : public ilist_node<IndexListEntry> { 46 MachineInstr *mi; 47 unsigned index; 48 49 public: 50 IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} 51 52 MachineInstr* getInstr() const { return mi; } 53 void setInstr(MachineInstr *mi) { 54 this->mi = mi; 55 } 56 57 unsigned getIndex() const { return index; } 58 void setIndex(unsigned index) { 59 this->index = index; 60 } 61 62 #ifdef EXPENSIVE_CHECKS 63 // When EXPENSIVE_CHECKS is defined, "erased" index list entries will 64 // actually be moved to a "graveyard" list, and have their pointers 65 // poisoned, so that dangling SlotIndex access can be reliably detected. 66 void setPoison() { 67 intptr_t tmp = reinterpret_cast<intptr_t>(mi); 68 assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); 69 tmp |= 0x1; 70 mi = reinterpret_cast<MachineInstr*>(tmp); 71 } 72 73 bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; } 74 #endif // EXPENSIVE_CHECKS 75 }; 76 77 template <> 78 struct ilist_alloc_traits<IndexListEntry> 79 : public ilist_noalloc_traits<IndexListEntry> {}; 80 81 /// SlotIndex - An opaque wrapper around machine indexes. 82 class SlotIndex { 83 friend class SlotIndexes; 84 85 enum Slot { 86 /// Basic block boundary. Used for live ranges entering and leaving a 87 /// block without being live in the layout neighbor. Also used as the 88 /// def slot of PHI-defs. 89 Slot_Block, 90 91 /// Early-clobber register use/def slot. A live range defined at 92 /// Slot_EarlyClobber interferes with normal live ranges killed at 93 /// Slot_Register. Also used as the kill slot for live ranges tied to an 94 /// early-clobber def. 95 Slot_EarlyClobber, 96 97 /// Normal register use/def slot. Normal instructions kill and define 98 /// register live ranges at this slot. 99 Slot_Register, 100 101 /// Dead def kill point. Kill slot for a live range that is defined by 102 /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't 103 /// used anywhere. 104 Slot_Dead, 105 106 Slot_Count 107 }; 108 109 PointerIntPair<IndexListEntry*, 2, unsigned> lie; 110 111 SlotIndex(IndexListEntry *entry, unsigned slot) 112 : lie(entry, slot) {} 113 114 IndexListEntry* listEntry() const { 115 assert(isValid() && "Attempt to compare reserved index."); 116 #ifdef EXPENSIVE_CHECKS 117 assert(!lie.getPointer()->isPoisoned() && 118 "Attempt to access deleted list-entry."); 119 #endif // EXPENSIVE_CHECKS 120 return lie.getPointer(); 121 } 122 123 unsigned getIndex() const { 124 return listEntry()->getIndex() | getSlot(); 125 } 126 127 /// Returns the slot for this SlotIndex. 128 Slot getSlot() const { 129 return static_cast<Slot>(lie.getInt()); 130 } 131 132 public: 133 enum { 134 /// The default distance between instructions as returned by distance(). 135 /// This may vary as instructions are inserted and removed. 136 InstrDist = 4 * Slot_Count 137 }; 138 139 /// Construct an invalid index. 140 SlotIndex() = default; 141 142 // Construct a new slot index from the given one, and set the slot. 143 SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) { 144 assert(lie.getPointer() != nullptr && 145 "Attempt to construct index with 0 pointer."); 146 } 147 148 /// Returns true if this is a valid index. Invalid indices do 149 /// not point into an index table, and cannot be compared. 150 bool isValid() const { 151 return lie.getPointer(); 152 } 153 154 /// Return true for a valid index. 155 explicit operator bool() const { return isValid(); } 156 157 /// Print this index to the given raw_ostream. 158 void print(raw_ostream &os) const; 159 160 /// Dump this index to stderr. 161 void dump() const; 162 163 /// Compare two SlotIndex objects for equality. 164 bool operator==(SlotIndex other) const { 165 return lie == other.lie; 166 } 167 /// Compare two SlotIndex objects for inequality. 168 bool operator!=(SlotIndex other) const { 169 return lie != other.lie; 170 } 171 172 /// Compare two SlotIndex objects. Return true if the first index 173 /// is strictly lower than the second. 174 bool operator<(SlotIndex other) const { 175 return getIndex() < other.getIndex(); 176 } 177 /// Compare two SlotIndex objects. Return true if the first index 178 /// is lower than, or equal to, 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 the second. 185 bool operator>(SlotIndex other) const { 186 return getIndex() > other.getIndex(); 187 } 188 189 /// Compare two SlotIndex objects. Return true if the first index 190 /// is greater than, or equal to, the second. 191 bool operator>=(SlotIndex other) const { 192 return getIndex() >= other.getIndex(); 193 } 194 195 /// isSameInstr - Return true if A and B refer to the same instruction. 196 static bool isSameInstr(SlotIndex A, SlotIndex B) { 197 return A.lie.getPointer() == B.lie.getPointer(); 198 } 199 200 /// isEarlierInstr - Return true if A refers to an instruction earlier than 201 /// B. This is equivalent to A < B && !isSameInstr(A, B). 202 static bool isEarlierInstr(SlotIndex A, SlotIndex B) { 203 return A.listEntry()->getIndex() < B.listEntry()->getIndex(); 204 } 205 206 /// Return true if A refers to the same instruction as B or an earlier one. 207 /// This is equivalent to !isEarlierInstr(B, A). 208 static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B) { 209 return !isEarlierInstr(B, A); 210 } 211 212 /// Return the distance from this index to the given one. 213 int distance(SlotIndex other) const { 214 return other.getIndex() - getIndex(); 215 } 216 217 /// Return the scaled distance from this index to the given one, where all 218 /// slots on the same instruction have zero distance. 219 int getInstrDistance(SlotIndex other) const { 220 return (other.listEntry()->getIndex() - listEntry()->getIndex()) 221 / Slot_Count; 222 } 223 224 /// isBlock - Returns true if this is a block boundary slot. 225 bool isBlock() const { return getSlot() == Slot_Block; } 226 227 /// isEarlyClobber - Returns true if this is an early-clobber slot. 228 bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; } 229 230 /// isRegister - Returns true if this is a normal register use/def slot. 231 /// Note that early-clobber slots may also be used for uses and defs. 232 bool isRegister() const { return getSlot() == Slot_Register; } 233 234 /// isDead - Returns true if this is a dead def kill slot. 235 bool isDead() const { return getSlot() == Slot_Dead; } 236 237 /// Returns the base index for associated with this index. The base index 238 /// is the one associated with the Slot_Block slot for the instruction 239 /// pointed to by this index. 240 SlotIndex getBaseIndex() const { 241 return SlotIndex(listEntry(), Slot_Block); 242 } 243 244 /// Returns the boundary index for associated with this index. The boundary 245 /// index is the one associated with the Slot_Block slot for the instruction 246 /// pointed to by this index. 247 SlotIndex getBoundaryIndex() const { 248 return SlotIndex(listEntry(), Slot_Dead); 249 } 250 251 /// Returns the register use/def slot in the current instruction for a 252 /// normal or early-clobber def. 253 SlotIndex getRegSlot(bool EC = false) const { 254 return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register); 255 } 256 257 /// Returns the dead def kill slot for the current instruction. 258 SlotIndex getDeadSlot() const { 259 return SlotIndex(listEntry(), Slot_Dead); 260 } 261 262 /// Returns the next slot in the index list. This could be either the 263 /// next slot for the instruction pointed to by this index or, if this 264 /// index is a STORE, the first slot for the next instruction. 265 /// WARNING: This method is considerably more expensive than the methods 266 /// that return specific slots (getUseIndex(), etc). If you can - please 267 /// use one of those methods. 268 SlotIndex getNextSlot() const { 269 Slot s = getSlot(); 270 if (s == Slot_Dead) { 271 return SlotIndex(&*++listEntry()->getIterator(), Slot_Block); 272 } 273 return SlotIndex(listEntry(), s + 1); 274 } 275 276 /// Returns the next index. This is the index corresponding to the this 277 /// index's slot, but for the next instruction. 278 SlotIndex getNextIndex() const { 279 return SlotIndex(&*++listEntry()->getIterator(), getSlot()); 280 } 281 282 /// Returns the previous slot in the index list. This could be either the 283 /// previous slot for the instruction pointed to by this index or, if this 284 /// index is a Slot_Block, the last slot for the previous instruction. 285 /// WARNING: This method is considerably more expensive than the methods 286 /// that return specific slots (getUseIndex(), etc). If you can - please 287 /// use one of those methods. 288 SlotIndex getPrevSlot() const { 289 Slot s = getSlot(); 290 if (s == Slot_Block) { 291 return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead); 292 } 293 return SlotIndex(listEntry(), s - 1); 294 } 295 296 /// Returns the previous index. This is the index corresponding to this 297 /// index's slot, but for the previous instruction. 298 SlotIndex getPrevIndex() const { 299 return SlotIndex(&*--listEntry()->getIterator(), getSlot()); 300 } 301 }; 302 303 inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) { 304 li.print(os); 305 return os; 306 } 307 308 using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>; 309 310 /// SlotIndexes pass. 311 /// 312 /// This pass assigns indexes to each instruction. 313 class SlotIndexes : public MachineFunctionPass { 314 private: 315 // IndexListEntry allocator. 316 BumpPtrAllocator ileAllocator; 317 318 using IndexList = ilist<IndexListEntry>; 319 IndexList indexList; 320 321 MachineFunction *mf = nullptr; 322 323 using Mi2IndexMap = DenseMap<const MachineInstr *, SlotIndex>; 324 Mi2IndexMap mi2iMap; 325 326 /// MBBRanges - Map MBB number to (start, stop) indexes. 327 SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges; 328 329 /// Idx2MBBMap - Sorted list of pairs of index of first instruction 330 /// and MBB id. 331 SmallVector<IdxMBBPair, 8> idx2MBBMap; 332 333 IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { 334 IndexListEntry *entry = 335 static_cast<IndexListEntry *>(ileAllocator.Allocate( 336 sizeof(IndexListEntry), alignof(IndexListEntry))); 337 338 new (entry) IndexListEntry(mi, index); 339 340 return entry; 341 } 342 343 /// Renumber locally after inserting curItr. 344 void renumberIndexes(IndexList::iterator curItr); 345 346 public: 347 static char ID; 348 349 SlotIndexes(); 350 351 ~SlotIndexes() override; 352 353 void getAnalysisUsage(AnalysisUsage &au) const override; 354 void releaseMemory() override; 355 356 bool runOnMachineFunction(MachineFunction &fn) override; 357 358 /// Dump the indexes. 359 void dump() const; 360 361 /// Repair indexes after adding and removing instructions. 362 void repairIndexesInRange(MachineBasicBlock *MBB, 363 MachineBasicBlock::iterator Begin, 364 MachineBasicBlock::iterator End); 365 366 /// Returns the zero index for this analysis. 367 SlotIndex getZeroIndex() { 368 assert(indexList.front().getIndex() == 0 && "First index is not 0?"); 369 return SlotIndex(&indexList.front(), 0); 370 } 371 372 /// Returns the base index of the last slot in this analysis. 373 SlotIndex getLastIndex() { 374 return SlotIndex(&indexList.back(), 0); 375 } 376 377 /// Returns true if the given machine instr is mapped to an index, 378 /// otherwise returns false. 379 bool hasIndex(const MachineInstr &instr) const { 380 return mi2iMap.count(&instr); 381 } 382 383 /// Returns the base index for the given instruction. 384 SlotIndex getInstructionIndex(const MachineInstr &MI, 385 bool IgnoreBundle = false) const { 386 // Instructions inside a bundle have the same number as the bundle itself. 387 auto BundleStart = getBundleStart(MI.getIterator()); 388 auto BundleEnd = getBundleEnd(MI.getIterator()); 389 // Use the first non-debug instruction in the bundle to get SlotIndex. 390 const MachineInstr &BundleNonDebug = 391 IgnoreBundle ? MI 392 : *skipDebugInstructionsForward(BundleStart, BundleEnd); 393 assert(!BundleNonDebug.isDebugInstr() && 394 "Could not use a debug instruction to query mi2iMap."); 395 Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleNonDebug); 396 assert(itr != mi2iMap.end() && "Instruction not found in maps."); 397 return itr->second; 398 } 399 400 /// Returns the instruction for the given index, or null if the given 401 /// index has no instruction associated with it. 402 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 403 return index.isValid() ? index.listEntry()->getInstr() : nullptr; 404 } 405 406 /// Returns the next non-null index, if one exists. 407 /// Otherwise returns getLastIndex(). 408 SlotIndex getNextNonNullIndex(SlotIndex Index) { 409 IndexList::iterator I = Index.listEntry()->getIterator(); 410 IndexList::iterator E = indexList.end(); 411 while (++I != E) 412 if (I->getInstr()) 413 return SlotIndex(&*I, Index.getSlot()); 414 // We reached the end of the function. 415 return getLastIndex(); 416 } 417 418 /// getIndexBefore - Returns the index of the last indexed instruction 419 /// before MI, or the start index of its basic block. 420 /// MI is not required to have an index. 421 SlotIndex getIndexBefore(const MachineInstr &MI) const { 422 const MachineBasicBlock *MBB = MI.getParent(); 423 assert(MBB && "MI must be inserted in a basic block"); 424 MachineBasicBlock::const_iterator I = MI, B = MBB->begin(); 425 while (true) { 426 if (I == B) 427 return getMBBStartIdx(MBB); 428 --I; 429 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I); 430 if (MapItr != mi2iMap.end()) 431 return MapItr->second; 432 } 433 } 434 435 /// getIndexAfter - Returns the index of the first indexed instruction 436 /// after MI, or the end index of its basic block. 437 /// MI is not required to have an index. 438 SlotIndex getIndexAfter(const MachineInstr &MI) const { 439 const MachineBasicBlock *MBB = MI.getParent(); 440 assert(MBB && "MI must be inserted in a basic block"); 441 MachineBasicBlock::const_iterator I = MI, E = MBB->end(); 442 while (true) { 443 ++I; 444 if (I == E) 445 return getMBBEndIdx(MBB); 446 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I); 447 if (MapItr != mi2iMap.end()) 448 return MapItr->second; 449 } 450 } 451 452 /// Return the (start,end) range of the given basic block number. 453 const std::pair<SlotIndex, SlotIndex> & 454 getMBBRange(unsigned Num) const { 455 return MBBRanges[Num]; 456 } 457 458 /// Return the (start,end) range of the given basic block. 459 const std::pair<SlotIndex, SlotIndex> & 460 getMBBRange(const MachineBasicBlock *MBB) const { 461 return getMBBRange(MBB->getNumber()); 462 } 463 464 /// Returns the first index in the given basic block number. 465 SlotIndex getMBBStartIdx(unsigned Num) const { 466 return getMBBRange(Num).first; 467 } 468 469 /// Returns the first index in the given basic block. 470 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 471 return getMBBRange(mbb).first; 472 } 473 474 /// Returns the last index in the given basic block number. 475 SlotIndex getMBBEndIdx(unsigned Num) const { 476 return getMBBRange(Num).second; 477 } 478 479 /// Returns the last index in the given basic block. 480 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 481 return getMBBRange(mbb).second; 482 } 483 484 /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block 485 /// begin and basic block) 486 using MBBIndexIterator = SmallVectorImpl<IdxMBBPair>::const_iterator; 487 488 /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or 489 /// equal to \p To. 490 MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const { 491 return std::partition_point( 492 I, idx2MBBMap.end(), 493 [=](const IdxMBBPair &IM) { return IM.first < To; }); 494 } 495 496 /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex 497 /// that is greater or equal to \p Idx. 498 MBBIndexIterator findMBBIndex(SlotIndex Idx) const { 499 return advanceMBBIndex(idx2MBBMap.begin(), Idx); 500 } 501 502 /// Returns an iterator for the begin of the idx2MBBMap. 503 MBBIndexIterator MBBIndexBegin() const { 504 return idx2MBBMap.begin(); 505 } 506 507 /// Return an iterator for the end of the idx2MBBMap. 508 MBBIndexIterator MBBIndexEnd() const { 509 return idx2MBBMap.end(); 510 } 511 512 /// Returns the basic block which the given index falls in. 513 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 514 if (MachineInstr *MI = getInstructionFromIndex(index)) 515 return MI->getParent(); 516 517 MBBIndexIterator I = findMBBIndex(index); 518 // Take the pair containing the index 519 MBBIndexIterator J = 520 ((I != MBBIndexEnd() && I->first > index) || 521 (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I; 522 523 assert(J != MBBIndexEnd() && J->first <= index && 524 index < getMBBEndIdx(J->second) && 525 "index does not correspond to an MBB"); 526 return J->second; 527 } 528 529 /// Insert the given machine instruction into the mapping. Returns the 530 /// assigned index. 531 /// If Late is set and there are null indexes between mi's neighboring 532 /// instructions, create the new index after the null indexes instead of 533 /// before them. 534 SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) { 535 assert(!MI.isInsideBundle() && 536 "Instructions inside bundles should use bundle start's slot."); 537 assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed."); 538 // Numbering debug instructions could cause code generation to be 539 // affected by debug information. 540 assert(!MI.isDebugInstr() && "Cannot number debug instructions."); 541 542 assert(MI.getParent() != nullptr && "Instr must be added to function."); 543 544 // Get the entries where MI should be inserted. 545 IndexList::iterator prevItr, nextItr; 546 if (Late) { 547 // Insert MI's index immediately before the following instruction. 548 nextItr = getIndexAfter(MI).listEntry()->getIterator(); 549 prevItr = std::prev(nextItr); 550 } else { 551 // Insert MI's index immediately after the preceding instruction. 552 prevItr = getIndexBefore(MI).listEntry()->getIterator(); 553 nextItr = std::next(prevItr); 554 } 555 556 // Get a number for the new instr, or 0 if there's no room currently. 557 // In the latter case we'll force a renumber later. 558 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; 559 unsigned newNumber = prevItr->getIndex() + dist; 560 561 // Insert a new list entry for MI. 562 IndexList::iterator newItr = 563 indexList.insert(nextItr, createEntry(&MI, newNumber)); 564 565 // Renumber locally if we need to. 566 if (dist == 0) 567 renumberIndexes(newItr); 568 569 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); 570 mi2iMap.insert(std::make_pair(&MI, newIndex)); 571 return newIndex; 572 } 573 574 /// Removes machine instruction (bundle) \p MI from the mapping. 575 /// This should be called before MachineInstr::eraseFromParent() is used to 576 /// remove a whole bundle or an unbundled instruction. 577 /// If \p AllowBundled is set then this can be used on a bundled 578 /// instruction; however, this exists to support handleMoveIntoBundle, 579 /// and in general removeSingleMachineInstrFromMaps should be used instead. 580 void removeMachineInstrFromMaps(MachineInstr &MI, 581 bool AllowBundled = false); 582 583 /// Removes a single machine instruction \p MI from the mapping. 584 /// This should be called before MachineInstr::eraseFromBundle() is used to 585 /// remove a single instruction (out of a bundle). 586 void removeSingleMachineInstrFromMaps(MachineInstr &MI); 587 588 /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in 589 /// maps used by register allocator. \returns the index where the new 590 /// instruction was inserted. 591 SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) { 592 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI); 593 if (mi2iItr == mi2iMap.end()) 594 return SlotIndex(); 595 SlotIndex replaceBaseIndex = mi2iItr->second; 596 IndexListEntry *miEntry(replaceBaseIndex.listEntry()); 597 assert(miEntry->getInstr() == &MI && 598 "Mismatched instruction in index tables."); 599 miEntry->setInstr(&NewMI); 600 mi2iMap.erase(mi2iItr); 601 mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex)); 602 return replaceBaseIndex; 603 } 604 605 /// Add the given MachineBasicBlock into the maps. 606 /// If it contains any instructions then they must already be in the maps. 607 /// This is used after a block has been split by moving some suffix of its 608 /// instructions into a newly created block. 609 void insertMBBInMaps(MachineBasicBlock *mbb) { 610 assert(mbb != &mbb->getParent()->front() && 611 "Can't insert a new block at the beginning of a function."); 612 auto prevMBB = std::prev(MachineFunction::iterator(mbb)); 613 614 // Create a new entry to be used for the start of mbb and the end of 615 // prevMBB. 616 IndexListEntry *startEntry = createEntry(nullptr, 0); 617 IndexListEntry *endEntry = getMBBEndIdx(&*prevMBB).listEntry(); 618 IndexListEntry *insEntry = 619 mbb->empty() ? endEntry 620 : getInstructionIndex(mbb->front()).listEntry(); 621 IndexList::iterator newItr = 622 indexList.insert(insEntry->getIterator(), startEntry); 623 624 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); 625 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block); 626 627 MBBRanges[prevMBB->getNumber()].second = startIdx; 628 629 assert(unsigned(mbb->getNumber()) == MBBRanges.size() && 630 "Blocks must be added in order"); 631 MBBRanges.push_back(std::make_pair(startIdx, endIdx)); 632 idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); 633 634 renumberIndexes(newItr); 635 llvm::sort(idx2MBBMap, less_first()); 636 } 637 }; 638 639 // Specialize IntervalMapInfo for half-open slot index intervals. 640 template <> 641 struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> { 642 }; 643 644 } // end namespace llvm 645 646 #endif // LLVM_CODEGEN_SLOTINDEXES_H 647