LLVM 24.0.0git
SlotIndexes.h
Go to the documentation of this file.
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"
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; }
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
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(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
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 {
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
320
321 /// MBBRanges - Map analysis block number to (start, stop) indexes.
323
324 /// Idx2MBBMap - Sorted list of pairs of index of first instruction
325 /// and MBB id.
327
328 // For legacy pass manager.
329 SlotIndexes() = default;
330
331 IndexListEntry *getMIEntry(const MachineInstr &MI) const {
332 unsigned Handle = MI.SlotIndexHandle;
333 if (Handle == 0)
334 return nullptr;
335 assert(Handle <= MIEntries.size() && "Stale slot index handle.");
336 IndexListEntry *Entry = MIEntries[Handle - 1];
337 assert(Entry->getInstr() == &MI && "Stale slot index handle.");
338 return Entry;
339 }
340
341 void setMIEntry(MachineInstr &MI, IndexListEntry *Entry) {
342 MIEntries.push_back(Entry);
343 MI.SlotIndexHandle = MIEntries.size();
344 }
345
346 LLVM_ABI void clear();
347
348 LLVM_ABI void analyze(MachineFunction &MF);
349
350 IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
351 IndexListEntry *entry =
352 static_cast<IndexListEntry *>(ileAllocator.Allocate(
353 sizeof(IndexListEntry), alignof(IndexListEntry)));
354
355 new (entry) IndexListEntry(mi, index);
356
357 return entry;
358 }
359
360 /// Renumber locally after inserting curItr.
361 LLVM_ABI void renumberIndexes(IndexList::iterator curItr);
362
363 public:
364 SlotIndexes(SlotIndexes &&) = default;
365
366 SlotIndexes(MachineFunction &MF) { analyze(MF); }
367
369
371 clear();
372 analyze(MF);
373 }
374
375 LLVM_ABI void print(raw_ostream &OS) const;
376
377 /// Dump the indexes.
378 LLVM_ABI void dump() const;
379
380 /// Repair indexes after adding and removing instructions.
384
385 /// Returns the zero index for this analysis.
387 assert(indexList.front().getIndex() == 0 && "First index is not 0?");
388 return SlotIndex(&indexList.front(), 0);
389 }
390
391 /// Returns the base index of the last slot in this analysis.
393 return SlotIndex(&indexList.back(), 0);
394 }
395
396 /// Returns true if the given machine instr is mapped to an index,
397 /// otherwise returns false.
398 bool hasIndex(const MachineInstr &instr) const {
399 return instr.SlotIndexHandle != 0;
400 }
401
402 /// Returns the base index for the given instruction.
404 bool IgnoreBundle = false) const {
405 // Instructions inside a bundle have the same number as the bundle itself.
406 auto BundleStart = getBundleStart(MI.getIterator());
407 auto BundleEnd = getBundleEnd(MI.getIterator());
408 // Use the first non-debug instruction in the bundle to get SlotIndex.
409 const MachineInstr &BundleNonDebug =
410 IgnoreBundle ? MI
411 : *skipDebugInstructionsForward(BundleStart, BundleEnd);
412 assert(!BundleNonDebug.isDebugInstr() &&
413 "Could not use a debug instruction to query the index.");
414 IndexListEntry *Entry = getMIEntry(BundleNonDebug);
415 assert(Entry && "Instruction not found in maps.");
416 return SlotIndex(Entry, SlotIndex::Slot_Block);
417 }
418
419 /// Returns the instruction for the given index, or null if the given
420 /// index has no instruction associated with it.
422 IndexListEntry *Entry = index.linkedEntry();
423 MachineInstr *MI = Entry->getInstr();
424 assert((!MI || getMIEntry(*MI) == Entry) &&
425 "Index refers to an instruction indexed elsewhere.");
426 return MI;
427 }
428
429 /// Returns true if \p Idx refers to an entry created to mark a basic block
430 /// boundary. Such entries never have an instruction attached.
432
433 /// Returns true if \p Idx refers to an instruction that has been erased.
434 bool isStaleIndex(SlotIndex Idx) const {
435 return !getInstructionFromIndex(Idx) && !isBlockBoundaryIndex(Idx);
436 }
437
438 /// Returns the register slot of the closest instruction preceding a stale
439 /// \p Idx, or the start index of its basic block if there is none. Returns
440 /// \p Idx unchanged if it is not stale.
442
443 /// Returns the next non-null index, if one exists.
444 /// Otherwise returns getLastIndex().
446 IndexList::iterator I = Index.linkedEntry()->getIterator();
447 IndexList::iterator E = indexList.end();
448 while (++I != E)
449 if (I->getInstr())
450 return SlotIndex(&*I, Index.getSlot());
451 // We reached the end of the function.
452 return getLastIndex();
453 }
454
455 /// getIndexBefore - Returns the index of the last indexed instruction
456 /// before MI, or the start index of its basic block.
457 /// MI is not required to have an index.
459 const MachineBasicBlock *MBB = MI.getParent();
460 assert(MBB && "MI must be inserted in a basic block");
462 while (true) {
463 if (I == B)
464 return getMBBStartIdx(MBB);
465 --I;
466 if (I->isDebugInstr())
467 continue;
468 if (IndexListEntry *Entry = getMIEntry(*I))
469 return SlotIndex(Entry, SlotIndex::Slot_Block);
470 }
471 }
472
473 /// getIndexAfter - Returns the index of the first indexed instruction
474 /// after MI, or the end index of its basic block.
475 /// MI is not required to have an index.
477 const MachineBasicBlock *MBB = MI.getParent();
478 assert(MBB && "MI must be inserted in a basic block");
480 while (true) {
481 ++I;
482 if (I == E)
483 return getMBBEndIdx(MBB);
484 if (I->isDebugInstr())
485 continue;
486 if (IndexListEntry *Entry = getMIEntry(*I))
487 return SlotIndex(Entry, SlotIndex::Slot_Block);
488 }
489 }
490
491 /// Return the (start,end) range of the given basic block.
492 const std::pair<SlotIndex, SlotIndex> &
494 return MBBRanges[MBB->getAnalysisNumber()];
495 }
496
497 /// Returns the first index in the given basic block.
499 return getMBBRange(mbb).first;
500 }
501
502 /// Returns the index past the last valid index in the given basic block.
504 return getMBBRange(mbb).second;
505 }
506
507 /// Returns the last valid index in the given basic block.
508 /// This index corresponds to the dead slot of the last non-debug
509 /// instruction and can be used to find live-out ranges of the block. Note
510 /// that getMBBEndIdx returns the start index of the next block, which is
511 /// also used as the start index for segments with phi-def values. If the
512 /// basic block doesn't contain any non-debug instructions, this returns
513 /// the same as getMBBStartIdx.getDeadSlot().
517
518 /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
519 /// begin and basic block)
521
522 /// Get an iterator pointing to the first IdxMBBPair with SlotIndex greater
523 /// than or equal to \p Idx. If \p Start is provided, only search the range
524 /// from \p Start to the end of the function.
526 SlotIndex Idx) const {
527 return std::lower_bound(
528 Start, MBBIndexEnd(), Idx,
529 [](const IdxMBBPair &IM, SlotIndex Idx) { return IM.first < Idx; });
530 }
534
535 /// Get an iterator pointing to the first IdxMBBPair with SlotIndex greater
536 /// than \p Idx.
538 return std::upper_bound(
539 MBBIndexBegin(), MBBIndexEnd(), Idx,
540 [](SlotIndex Idx, const IdxMBBPair &IM) { return Idx < IM.first; });
541 }
542
543 /// Returns an iterator for the begin of the idx2MBBMap.
545 return idx2MBBMap.begin();
546 }
547
548 /// Return an iterator for the end of the idx2MBBMap.
550 return idx2MBBMap.end();
551 }
552
553 /// Returns the basic block which the given index falls in.
556 return MI->getParent();
557
558 MBBIndexIterator I = std::prev(getMBBUpperBound(index));
559 assert(I != MBBIndexEnd() && I->first <= index &&
560 index < getMBBEndIdx(I->second) &&
561 "index does not correspond to an MBB");
562 return I->second;
563 }
564
565 /// Insert the given machine instruction into the mapping. Returns the
566 /// assigned index.
567 /// If Late is set and there are null indexes between mi's neighboring
568 /// instructions, create the new index after the null indexes instead of
569 /// before them.
571 assert(!MI.isInsideBundle() &&
572 "Instructions inside bundles should use bundle start's slot.");
573 assert(!hasIndex(MI) && "Instr already indexed.");
574 // Numbering debug instructions could cause code generation to be
575 // affected by debug information.
576 assert(!MI.isDebugInstr() && "Cannot number debug instructions.");
577
578 assert(MI.getParent() != nullptr && "Instr must be added to function.");
579
580 // Get the entries where MI should be inserted.
581 IndexList::iterator prevItr, nextItr;
582 if (Late) {
583 // Insert MI's index immediately before the following instruction.
584 nextItr = getIndexAfter(MI).listEntry()->getIterator();
585 prevItr = std::prev(nextItr);
586 } else {
587 // Insert MI's index immediately after the preceding instruction.
588 prevItr = getIndexBefore(MI).listEntry()->getIterator();
589 nextItr = std::next(prevItr);
590 }
591
592 // Get a number for the new instr, or 0 if there's no room currently.
593 // In the latter case we'll force a renumber later.
594 unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
595 unsigned newNumber = prevItr->getIndex() + dist;
596
597 // Insert a new list entry for MI.
598 IndexList::iterator newItr =
599 indexList.insert(nextItr, *createEntry(&MI, newNumber));
600
601 // Renumber locally if we need to.
602 if (dist == 0)
603 renumberIndexes(newItr);
604
605 setMIEntry(MI, &*newItr);
606 return SlotIndex(&*newItr, SlotIndex::Slot_Block);
607 }
608
609 /// Removes machine instruction (bundle) \p MI from the mapping.
610 /// This should be called before MachineInstr::eraseFromParent() is used to
611 /// remove a whole bundle or an unbundled instruction.
612 /// If \p AllowBundled is set then this can be used on a bundled
613 /// instruction; however, this exists to support handleMoveIntoBundle,
614 /// and in general removeSingleMachineInstrFromMaps should be used instead.
616 bool AllowBundled = false);
617
618 /// Removes a single machine instruction \p MI from the mapping.
619 /// This should be called before MachineInstr::eraseFromBundle() is used to
620 /// remove a single instruction (out of a bundle).
622
623 /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
624 /// maps used by register allocator. \returns the index where the new
625 /// instruction was inserted.
627 IndexListEntry *miEntry = getMIEntry(MI);
628 if (!miEntry)
629 return SlotIndex();
630 assert(!getMIEntry(NewMI) && "Instr already indexed.");
631 miEntry->setInstr(&NewMI);
632 NewMI.SlotIndexHandle = MI.SlotIndexHandle;
633 MI.SlotIndexHandle = 0;
634 return SlotIndex(miEntry, SlotIndex::Slot_Block);
635 }
636
637 /// Add the given MachineBasicBlock into the maps.
638 /// If it contains any instructions then they must already be in the maps.
639 /// This is used after a block has been split by moving some suffix of its
640 /// instructions into a newly created block.
642 assert(mbb != &mbb->getParent()->front() &&
643 "Can't insert a new block at the beginning of a function.");
644 auto prevMBB = std::prev(MachineFunction::iterator(mbb));
645
646 // Create a new entry to be used for the start of mbb and the end of
647 // prevMBB.
648 IndexListEntry *startEntry = createEntry(nullptr, 0);
649 IndexListEntry *endEntry = getMBBEndIdx(&*prevMBB).listEntry();
650 // Debug and pseudo probe instructions have no index.
652 IndexListEntry *insEntry =
653 FirstIndexed == mbb->end()
654 ? endEntry
655 : getInstructionIndex(*FirstIndexed).listEntry();
656 IndexList::iterator newItr =
657 indexList.insert(insEntry->getIterator(), *startEntry);
658
659 SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
660 SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
661
662 MBBRanges[prevMBB->getAnalysisNumber()].second = startIdx;
663
664 assert(unsigned(mbb->getAnalysisNumber()) == MBBRanges.size() &&
665 "Blocks must be added in order");
666 MBBRanges.push_back(std::make_pair(startIdx, endIdx));
667
668 renumberIndexes(newItr);
669 auto InsertPt =
670 llvm::partition_point(idx2MBBMap, [=](const IdxMBBPair &IM) {
671 return IM.first < startIdx;
672 });
673 idx2MBBMap.insert(InsertPt, IdxMBBPair(startIdx, mbb));
674 }
675
676 /// Inverse of insertMBBInMaps: merge \p MBB's slot range into its layout
677 /// predecessor and drop it from the maps. Call before erasing \p MBB and
678 /// after its instructions have been removed from the maps.
680
681 /// Renumber all indexes using the default instruction distance.
682 LLVM_ABI void packIndexes();
683
684 /// Erase index list entries left behind by deleted instructions, then
685 /// renumber. Erased entries are unlinked, so nothing may hold one.
686 /// Returns the number erased.
687 LLVM_ABI unsigned compactIndexes();
688 };
689
690 // Specialize IntervalMapInfo for half-open slot index intervals.
691 template <>
693 };
694
695 class SlotIndexesAnalysis : public AnalysisInfoMixin<SlotIndexesAnalysis> {
697 LLVM_ABI static AnalysisKey Key;
698
699 public:
702 };
703
705 : public RequiredPassInfoMixin<SlotIndexesPrinterPass> {
706 raw_ostream &OS;
707
708 public:
709 explicit SlotIndexesPrinterPass(raw_ostream &OS) : OS(OS) {}
712 };
713
715 SlotIndexes SI;
716
717 public:
718 static char ID;
719
721
722 void getAnalysisUsage(AnalysisUsage &au) const override;
723 void releaseMemory() override { SI.clear(); }
724
726 SI.analyze(fn);
727 return false;
728 }
729
730 SlotIndexes &getSI() { return SI; }
731 };
732
733} // end namespace llvm
734
735#endif // LLVM_CODEGEN_SLOTINDEXES_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseMap class.
IRTranslator LLVM IR MI
This file implements a coalescing interval map for small objects.
#define I(x, y, z)
Definition MD5.cpp:57
This file defines the PointerIntPair class.
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
This class represents an entry in the slot index list held in the SlotIndexes pass.
Definition SlotIndexes.h:47
IndexListEntry(MachineInstr *mi, unsigned index)
Definition SlotIndexes.h:53
void setInstr(MachineInstr *mi)
Definition SlotIndexes.h:59
bool isErased() const
Definition SlotIndexes.h:55
MachineInstr * getInstr() const
Definition SlotIndexes.h:58
void setIndex(unsigned index)
Definition SlotIndexes.h:64
unsigned getIndex() const
Definition SlotIndexes.h:63
MachineInstrBundleIterator< const MachineInstr > const_iterator
int getAnalysisNumber() const
For analyses, blocks have a more stable number.
LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineInstrBundleIterator< MachineInstr > iterator
BasicBlockListType::iterator iterator
const MachineBasicBlock & front() const
Representation of each machine instruction.
bool isDebugInstr() const
PointerIntPair - This class implements a pair of a pointer and small integer.
PointerTy getPointer() const
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:70
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
SlotIndex getNextIndex() const
Returns the next index.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
SlotIndex()=default
Construct an invalid index.
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
bool operator>=(SlotIndex other) const
Compare two SlotIndex objects.
int distance(SlotIndex other) const
Return the distance from this index to the given one.
bool operator>(SlotIndex other) const
Compare two SlotIndex objects.
@ InstrDist
The default distance between instructions as returned by distance().
bool isValid() const
Returns true if this is a valid index.
bool isRegister() const
isRegister - Returns true if this is a normal register use/def slot.
bool operator!=(SlotIndex other) const
Compare two SlotIndex objects for inequality.
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
LLVM_ABI void dump() const
Dump this index to stderr.
SlotIndex(const SlotIndex &li, Slot s)
SlotIndex getPrevIndex() const
Returns the previous index.
LLVM_ABI void print(raw_ostream &os) const
Print this index to the given raw_ostream.
SlotIndex getNextSlot() const
Returns the next slot in the index list.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
bool operator<(SlotIndex other) const
Compare two SlotIndex objects.
bool operator<=(SlotIndex other) const
Compare two SlotIndex objects.
int getApproxInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
friend class SlotIndexes
Definition SlotIndexes.h:71
bool operator==(SlotIndex other) const
Compare two SlotIndex objects for equality.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &)
SlotIndexesPrinterPass(raw_ostream &OS)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
bool runOnMachineFunction(MachineFunction &fn) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void getAnalysisUsage(AnalysisUsage &au) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
SlotIndexes pass.
LLVM_ABI bool isBlockBoundaryIndex(SlotIndex Idx) const
Returns true if Idx refers to an entry created to mark a basic block boundary.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
SlotIndex getMBBLastIdx(const MachineBasicBlock *MBB) const
Returns the last valid index in the given basic block.
SlotIndexes(SlotIndexes &&)=default
LLVM_ABI void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
LLVM_ABI SlotIndex canonicalizeIndex(SlotIndex Idx) const
Returns the register slot of the closest instruction preceding a stale Idx, or the start index of its...
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
LLVM_ABI void dump() const
Dump the indexes.
LLVM_ABI void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
LLVM_ABI unsigned compactIndexes()
Erase index list entries left behind by deleted instructions, then renumber.
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
MBBIndexIterator getMBBLowerBound(MBBIndexIterator Start, SlotIndex Idx) const
Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than or equal to Idx.
void reanalyze(MachineFunction &MF)
LLVM_ABI void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
MBBIndexIterator getMBBLowerBound(SlotIndex Idx) const
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator
Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block)
MBBIndexIterator getMBBUpperBound(SlotIndex Idx) const
Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than Idx.
SlotIndexes(MachineFunction &MF)
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getIndexAfter(const MachineInstr &MI) const
getIndexAfter - Returns the index of the first indexed instruction after MI, or the end index of its ...
LLVM_ABI ~SlotIndexes()
bool isStaleIndex(SlotIndex Idx) const
Returns true if Idx refers to an instruction that has been erased.
LLVM_ABI void packIndexes()
Renumber all indexes using the default instruction distance.
LLVM_ABI void removeMBBFromMaps(MachineBasicBlock &MBB)
Inverse of insertMBBInMaps: merge MBB's slot range into its layout predecessor and drop it from the m...
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
LLVM_ABI void print(raw_ostream &OS) const
SlotIndex getIndexBefore(const MachineInstr &MI) const
getIndexBefore - Returns the index of the last indexed instruction before MI, or the start index of i...
SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in maps used by register allocat...
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the index past the last valid index in the given basic block.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(const MachineBasicBlock *MBB) const
Return the (start,end) range of the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
friend class SlotIndexesWrapperPass
typename SuperClass::const_iterator const_iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
self_iterator getIterator()
Definition ilist_node.h:123
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
A simple intrusive list implementation.
ilist_select_iterator_type< OptionsT, false, false > iterator
This is an optimization pass for GlobalISel generic memory operations.
MachineBasicBlock::instr_iterator getBundleStart(MachineBasicBlock::instr_iterator I)
Returns an iterator to the first instruction in the bundle containing I.
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition STLExtras.h:2145
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
std::pair< SlotIndex, MachineBasicBlock * > IdxMBBPair
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
A CRTP mix-in for passes that should not be skipped.