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