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 indices 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 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()->getIterator(), 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()->getIterator(), 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()->getIterator(), 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()->getIterator(), 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 // IndexListEntry allocator. 337 BumpPtrAllocator ileAllocator; 338 339 typedef ilist<IndexListEntry> IndexList; 340 IndexList indexList; 341 342 #ifdef EXPENSIVE_CHECKS 343 IndexList graveyardList; 344 #endif // EXPENSIVE_CHECKS 345 346 MachineFunction *mf; 347 348 typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap; 349 Mi2IndexMap mi2iMap; 350 351 /// MBBRanges - Map MBB number to (start, stop) indexes. 352 SmallVector<std::pair<SlotIndex, SlotIndex>, 8> MBBRanges; 353 354 /// Idx2MBBMap - Sorted list of pairs of index of first instruction 355 /// and MBB id. 356 SmallVector<IdxMBBPair, 8> idx2MBBMap; 357 358 IndexListEntry* createEntry(MachineInstr *mi, unsigned index) { 359 IndexListEntry *entry = 360 static_cast<IndexListEntry*>( 361 ileAllocator.Allocate(sizeof(IndexListEntry), 362 alignOf<IndexListEntry>())); 363 364 new (entry) IndexListEntry(mi, index); 365 366 return entry; 367 } 368 369 /// Renumber locally after inserting curItr. 370 void renumberIndexes(IndexList::iterator curItr); 371 372 public: 373 static char ID; 374 375 SlotIndexes() : MachineFunctionPass(ID) { 376 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 377 } 378 379 ~SlotIndexes() { 380 // The indexList's nodes are all allocated in the BumpPtrAllocator. 381 indexList.clearAndLeakNodesUnsafely(); 382 } 383 384 void getAnalysisUsage(AnalysisUsage &au) const override; 385 void releaseMemory() override; 386 387 bool runOnMachineFunction(MachineFunction &fn) override; 388 389 /// Dump the indexes. 390 void dump() const; 391 392 /// Renumber the index list, providing space for new instructions. 393 void renumberIndexes(); 394 395 /// Repair indexes after adding and removing instructions. 396 void repairIndexesInRange(MachineBasicBlock *MBB, 397 MachineBasicBlock::iterator Begin, 398 MachineBasicBlock::iterator End); 399 400 /// Returns the zero index for this analysis. 401 SlotIndex getZeroIndex() { 402 assert(indexList.front().getIndex() == 0 && "First index is not 0?"); 403 return SlotIndex(&indexList.front(), 0); 404 } 405 406 /// Returns the base index of the last slot in this analysis. 407 SlotIndex getLastIndex() { 408 return SlotIndex(&indexList.back(), 0); 409 } 410 411 /// Returns true if the given machine instr is mapped to an index, 412 /// otherwise returns false. 413 bool hasIndex(const MachineInstr *instr) const { 414 return mi2iMap.count(instr); 415 } 416 417 /// Returns the base index for the given instruction. 418 SlotIndex getInstructionIndex(const MachineInstr *MI) const { 419 // Instructions inside a bundle have the same number as the bundle itself. 420 Mi2IndexMap::const_iterator itr = mi2iMap.find(getBundleStart(MI)); 421 assert(itr != mi2iMap.end() && "Instruction not found in maps."); 422 return itr->second; 423 } 424 425 /// Returns the instruction for the given index, or null if the given 426 /// index has no instruction associated with it. 427 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 428 return index.isValid() ? index.listEntry()->getInstr() : nullptr; 429 } 430 431 /// Returns the next non-null index, if one exists. 432 /// Otherwise returns getLastIndex(). 433 SlotIndex getNextNonNullIndex(SlotIndex Index) { 434 IndexList::iterator I = Index.listEntry()->getIterator(); 435 IndexList::iterator E = indexList.end(); 436 while (++I != E) 437 if (I->getInstr()) 438 return SlotIndex(&*I, Index.getSlot()); 439 // We reached the end of the function. 440 return getLastIndex(); 441 } 442 443 /// getIndexBefore - Returns the index of the last indexed instruction 444 /// before MI, or the start index of its basic block. 445 /// MI is not required to have an index. 446 SlotIndex getIndexBefore(const MachineInstr *MI) const { 447 const MachineBasicBlock *MBB = MI->getParent(); 448 assert(MBB && "MI must be inserted inna basic block"); 449 MachineBasicBlock::const_iterator I = MI, B = MBB->begin(); 450 for (;;) { 451 if (I == B) 452 return getMBBStartIdx(MBB); 453 --I; 454 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); 455 if (MapItr != mi2iMap.end()) 456 return MapItr->second; 457 } 458 } 459 460 /// getIndexAfter - Returns the index of the first indexed instruction 461 /// after MI, or the end index of its basic block. 462 /// MI is not required to have an index. 463 SlotIndex getIndexAfter(const MachineInstr *MI) const { 464 const MachineBasicBlock *MBB = MI->getParent(); 465 assert(MBB && "MI must be inserted inna basic block"); 466 MachineBasicBlock::const_iterator I = MI, E = MBB->end(); 467 for (;;) { 468 ++I; 469 if (I == E) 470 return getMBBEndIdx(MBB); 471 Mi2IndexMap::const_iterator MapItr = mi2iMap.find(I); 472 if (MapItr != mi2iMap.end()) 473 return MapItr->second; 474 } 475 } 476 477 /// Return the (start,end) range of the given basic block number. 478 const std::pair<SlotIndex, SlotIndex> & 479 getMBBRange(unsigned Num) const { 480 return MBBRanges[Num]; 481 } 482 483 /// Return the (start,end) range of the given basic block. 484 const std::pair<SlotIndex, SlotIndex> & 485 getMBBRange(const MachineBasicBlock *MBB) const { 486 return getMBBRange(MBB->getNumber()); 487 } 488 489 /// Returns the first index in the given basic block number. 490 SlotIndex getMBBStartIdx(unsigned Num) const { 491 return getMBBRange(Num).first; 492 } 493 494 /// Returns the first index in the given basic block. 495 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 496 return getMBBRange(mbb).first; 497 } 498 499 /// Returns the last index in the given basic block number. 500 SlotIndex getMBBEndIdx(unsigned Num) const { 501 return getMBBRange(Num).second; 502 } 503 504 /// Returns the last index in the given basic block. 505 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 506 return getMBBRange(mbb).second; 507 } 508 509 /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block 510 /// begin and basic block) 511 typedef SmallVectorImpl<IdxMBBPair>::const_iterator MBBIndexIterator; 512 /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or 513 /// equal to \p To. 514 MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const { 515 return std::lower_bound(I, idx2MBBMap.end(), To); 516 } 517 /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex 518 /// that is greater or equal to \p Idx. 519 MBBIndexIterator findMBBIndex(SlotIndex Idx) const { 520 return advanceMBBIndex(idx2MBBMap.begin(), Idx); 521 } 522 /// Returns an iterator for the begin of the idx2MBBMap. 523 MBBIndexIterator MBBIndexBegin() const { 524 return idx2MBBMap.begin(); 525 } 526 /// Return an iterator for the end of the idx2MBBMap. 527 MBBIndexIterator MBBIndexEnd() const { 528 return idx2MBBMap.end(); 529 } 530 531 /// Returns the basic block which the given index falls in. 532 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 533 if (MachineInstr *MI = getInstructionFromIndex(index)) 534 return MI->getParent(); 535 536 MBBIndexIterator I = findMBBIndex(index); 537 // Take the pair containing the index 538 MBBIndexIterator J = 539 ((I != MBBIndexEnd() && I->first > index) || 540 (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I; 541 542 assert(J != MBBIndexEnd() && J->first <= index && 543 index < getMBBEndIdx(J->second) && 544 "index does not correspond to an MBB"); 545 return J->second; 546 } 547 548 /// Returns the MBB covering the given range, or null if the range covers 549 /// more than one basic block. 550 MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { 551 552 assert(start < end && "Backwards ranges not allowed."); 553 MBBIndexIterator itr = findMBBIndex(start); 554 if (itr == MBBIndexEnd()) { 555 itr = std::prev(itr); 556 return itr->second; 557 } 558 559 // Check that we don't cross the boundary into this block. 560 if (itr->first < end) 561 return nullptr; 562 563 itr = std::prev(itr); 564 565 if (itr->first <= start) 566 return itr->second; 567 568 return nullptr; 569 } 570 571 /// Insert the given machine instruction into the mapping. Returns the 572 /// assigned index. 573 /// If Late is set and there are null indexes between mi's neighboring 574 /// instructions, create the new index after the null indexes instead of 575 /// before them. 576 SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool Late = false) { 577 assert(!mi->isInsideBundle() && 578 "Instructions inside bundles should use bundle start's slot."); 579 assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed."); 580 // Numbering DBG_VALUE instructions could cause code generation to be 581 // affected by debug information. 582 assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions."); 583 584 assert(mi->getParent() != nullptr && "Instr must be added to function."); 585 586 // Get the entries where mi should be inserted. 587 IndexList::iterator prevItr, nextItr; 588 if (Late) { 589 // Insert mi's index immediately before the following instruction. 590 nextItr = getIndexAfter(mi).listEntry()->getIterator(); 591 prevItr = std::prev(nextItr); 592 } else { 593 // Insert mi's index immediately after the preceding instruction. 594 prevItr = getIndexBefore(mi).listEntry()->getIterator(); 595 nextItr = std::next(prevItr); 596 } 597 598 // Get a number for the new instr, or 0 if there's no room currently. 599 // In the latter case we'll force a renumber later. 600 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u; 601 unsigned newNumber = prevItr->getIndex() + dist; 602 603 // Insert a new list entry for mi. 604 IndexList::iterator newItr = 605 indexList.insert(nextItr, createEntry(mi, newNumber)); 606 607 // Renumber locally if we need to. 608 if (dist == 0) 609 renumberIndexes(newItr); 610 611 SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block); 612 mi2iMap.insert(std::make_pair(mi, newIndex)); 613 return newIndex; 614 } 615 616 /// Remove the given machine instruction from the mapping. 617 void removeMachineInstrFromMaps(MachineInstr *mi) { 618 // remove index -> MachineInstr and 619 // MachineInstr -> index mappings 620 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); 621 if (mi2iItr != mi2iMap.end()) { 622 IndexListEntry *miEntry(mi2iItr->second.listEntry()); 623 assert(miEntry->getInstr() == mi && "Instruction indexes broken."); 624 // FIXME: Eventually we want to actually delete these indexes. 625 miEntry->setInstr(nullptr); 626 mi2iMap.erase(mi2iItr); 627 } 628 } 629 630 /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in 631 /// maps used by register allocator. 632 void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) { 633 Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi); 634 if (mi2iItr == mi2iMap.end()) 635 return; 636 SlotIndex replaceBaseIndex = mi2iItr->second; 637 IndexListEntry *miEntry(replaceBaseIndex.listEntry()); 638 assert(miEntry->getInstr() == mi && 639 "Mismatched instruction in index tables."); 640 miEntry->setInstr(newMI); 641 mi2iMap.erase(mi2iItr); 642 mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex)); 643 } 644 645 /// Add the given MachineBasicBlock into the maps. 646 void insertMBBInMaps(MachineBasicBlock *mbb) { 647 MachineFunction::iterator nextMBB = 648 std::next(MachineFunction::iterator(mbb)); 649 650 IndexListEntry *startEntry = nullptr; 651 IndexListEntry *endEntry = nullptr; 652 IndexList::iterator newItr; 653 if (nextMBB == mbb->getParent()->end()) { 654 startEntry = &indexList.back(); 655 endEntry = createEntry(nullptr, 0); 656 newItr = indexList.insertAfter(startEntry->getIterator(), endEntry); 657 } else { 658 startEntry = createEntry(nullptr, 0); 659 endEntry = getMBBStartIdx(&*nextMBB).listEntry(); 660 newItr = indexList.insert(endEntry->getIterator(), startEntry); 661 } 662 663 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); 664 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block); 665 666 MachineFunction::iterator prevMBB(mbb); 667 assert(prevMBB != mbb->getParent()->end() && 668 "Can't insert a new block at the beginning of a function."); 669 --prevMBB; 670 MBBRanges[prevMBB->getNumber()].second = startIdx; 671 672 assert(unsigned(mbb->getNumber()) == MBBRanges.size() && 673 "Blocks must be added in order"); 674 MBBRanges.push_back(std::make_pair(startIdx, endIdx)); 675 idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); 676 677 renumberIndexes(newItr); 678 std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); 679 } 680 681 /// \brief Free the resources that were required to maintain a SlotIndex. 682 /// 683 /// Once an index is no longer needed (for instance because the instruction 684 /// at that index has been moved), the resources required to maintain the 685 /// index can be relinquished to reduce memory use and improve renumbering 686 /// performance. Any remaining SlotIndex objects that point to the same 687 /// index are left 'dangling' (much the same as a dangling pointer to a 688 /// freed object) and should not be accessed, except to destruct them. 689 /// 690 /// Like dangling pointers, access to dangling SlotIndexes can cause 691 /// painful-to-track-down bugs, especially if the memory for the index 692 /// previously pointed to has been re-used. To detect dangling SlotIndex 693 /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to 694 /// be retained in a graveyard instead of being freed. Operations on indexes 695 /// in the graveyard will trigger an assertion. 696 void eraseIndex(SlotIndex index) { 697 IndexListEntry *entry = index.listEntry(); 698 #ifdef EXPENSIVE_CHECKS 699 indexList.remove(entry); 700 graveyardList.push_back(entry); 701 entry->setPoison(); 702 #else 703 indexList.erase(entry); 704 #endif 705 } 706 707 }; 708 709 710 // Specialize IntervalMapInfo for half-open slot index intervals. 711 template <> 712 struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> { 713 }; 714 715 } 716 717 #endif // LLVM_CODEGEN_SLOTINDEXES_H 718
