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