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