LLVM  9.0.0svn
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"
22 #include "llvm/ADT/IntervalMap.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/ilist.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/Allocator.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <iterator>
36 #include <utility>
37 
38 namespace llvm {
39 
40 class raw_ostream;
41 
42  /// This class represents an entry in the slot index list held in the
43  /// SlotIndexes pass. It should not be used directly. See the
44  /// SlotIndex & SlotIndexes classes for the public interface to this
45  /// information.
46  class IndexListEntry : public ilist_node<IndexListEntry> {
47  MachineInstr *mi;
48  unsigned index;
49 
50  public:
51  IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {}
52 
53  MachineInstr* getInstr() const { return mi; }
54  void setInstr(MachineInstr *mi) {
55  this->mi = mi;
56  }
57 
58  unsigned getIndex() const { return index; }
59  void setIndex(unsigned index) {
60  this->index = index;
61  }
62 
63 #ifdef EXPENSIVE_CHECKS
64  // When EXPENSIVE_CHECKS is defined, "erased" index list entries will
65  // actually be moved to a "graveyard" list, and have their pointers
66  // poisoned, so that dangling SlotIndex access can be reliably detected.
67  void setPoison() {
68  intptr_t tmp = reinterpret_cast<intptr_t>(mi);
69  assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?");
70  tmp |= 0x1;
71  mi = reinterpret_cast<MachineInstr*>(tmp);
72  }
73 
74  bool isPoisoned() const { return (reinterpret_cast<intptr_t>(mi) & 0x1) == 0x1; }
75 #endif // EXPENSIVE_CHECKS
76  };
77 
78  template <>
80  : public ilist_noalloc_traits<IndexListEntry> {};
81 
82  /// SlotIndex - An opaque wrapper around machine indexes.
83  class SlotIndex {
84  friend class SlotIndexes;
85 
86  enum Slot {
87  /// Basic block boundary. Used for live ranges entering and leaving a
88  /// block without being live in the layout neighbor. Also used as the
89  /// def slot of PHI-defs.
90  Slot_Block,
91 
92  /// Early-clobber register use/def slot. A live range defined at
93  /// Slot_EarlyClobber interferes with normal live ranges killed at
94  /// Slot_Register. Also used as the kill slot for live ranges tied to an
95  /// early-clobber def.
96  Slot_EarlyClobber,
97 
98  /// Normal register use/def slot. Normal instructions kill and define
99  /// register live ranges at this slot.
100  Slot_Register,
101 
102  /// Dead def kill point. Kill slot for a live range that is defined by
103  /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't
104  /// used anywhere.
105  Slot_Dead,
106 
107  Slot_Count
108  };
109 
111 
112  SlotIndex(IndexListEntry *entry, unsigned slot)
113  : lie(entry, slot) {}
114 
115  IndexListEntry* listEntry() const {
116  assert(isValid() && "Attempt to compare reserved index.");
117 #ifdef EXPENSIVE_CHECKS
118  assert(!lie.getPointer()->isPoisoned() &&
119  "Attempt to access deleted list-entry.");
120 #endif // EXPENSIVE_CHECKS
121  return lie.getPointer();
122  }
123 
124  unsigned getIndex() const {
125  return listEntry()->getIndex() | getSlot();
126  }
127 
128  /// Returns the slot for this SlotIndex.
129  Slot getSlot() const {
130  return static_cast<Slot>(lie.getInt());
131  }
132 
133  public:
134  enum {
135  /// The default distance between instructions as returned by distance().
136  /// This may vary as instructions are inserted and removed.
137  InstrDist = 4 * Slot_Count
138  };
139 
140  /// Construct an invalid index.
141  SlotIndex() = default;
142 
143  // Construct a new slot index from the given one, and set the slot.
144  SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) {
145  assert(lie.getPointer() != nullptr &&
146  "Attempt to construct index with 0 pointer.");
147  }
148 
149  /// Returns true if this is a valid index. Invalid indices do
150  /// not point into an index table, and cannot be compared.
151  bool isValid() const {
152  return lie.getPointer();
153  }
154 
155  /// Return true for a valid index.
156  explicit operator bool() const { return isValid(); }
157 
158  /// Print this index to the given raw_ostream.
159  void print(raw_ostream &os) const;
160 
161  /// Dump this index to stderr.
162  void dump() const;
163 
164  /// Compare two SlotIndex objects for equality.
165  bool operator==(SlotIndex other) const {
166  return lie == other.lie;
167  }
168  /// Compare two SlotIndex objects for inequality.
169  bool operator!=(SlotIndex other) const {
170  return lie != other.lie;
171  }
172 
173  /// Compare two SlotIndex objects. Return true if the first index
174  /// is strictly lower than the second.
175  bool operator<(SlotIndex other) const {
176  return getIndex() < other.getIndex();
177  }
178  /// Compare two SlotIndex objects. Return true if the first index
179  /// is lower than, or equal to, the second.
180  bool operator<=(SlotIndex other) const {
181  return getIndex() <= other.getIndex();
182  }
183 
184  /// Compare two SlotIndex objects. Return true if the first index
185  /// is greater than the second.
186  bool operator>(SlotIndex other) const {
187  return getIndex() > other.getIndex();
188  }
189 
190  /// Compare two SlotIndex objects. Return true if the first index
191  /// is greater than, or equal to, the second.
192  bool operator>=(SlotIndex other) const {
193  return getIndex() >= other.getIndex();
194  }
195 
196  /// isSameInstr - Return true if A and B refer to the same instruction.
198  return A.lie.getPointer() == B.lie.getPointer();
199  }
200 
201  /// isEarlierInstr - Return true if A refers to an instruction earlier than
202  /// B. This is equivalent to A < B && !isSameInstr(A, B).
204  return A.listEntry()->getIndex() < B.listEntry()->getIndex();
205  }
206 
207  /// Return true if A refers to the same instruction as B or an earlier one.
208  /// This is equivalent to !isEarlierInstr(B, A).
210  return !isEarlierInstr(B, A);
211  }
212 
213  /// Return the distance from this index to the given one.
214  int distance(SlotIndex other) const {
215  return other.getIndex() - getIndex();
216  }
217 
218  /// Return the scaled distance from this index to the given one, where all
219  /// slots on the same instruction have zero distance.
220  int getInstrDistance(SlotIndex other) const {
221  return (other.listEntry()->getIndex() - listEntry()->getIndex())
222  / Slot_Count;
223  }
224 
225  /// isBlock - Returns true if this is a block boundary slot.
226  bool isBlock() const { return getSlot() == Slot_Block; }
227 
228  /// isEarlyClobber - Returns true if this is an early-clobber slot.
229  bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; }
230 
231  /// isRegister - Returns true if this is a normal register use/def slot.
232  /// Note that early-clobber slots may also be used for uses and defs.
233  bool isRegister() const { return getSlot() == Slot_Register; }
234 
235  /// isDead - Returns true if this is a dead def kill slot.
236  bool isDead() const { return getSlot() == Slot_Dead; }
237 
238  /// Returns the base index for associated with this index. The base index
239  /// is the one associated with the Slot_Block slot for the instruction
240  /// pointed to by this index.
242  return SlotIndex(listEntry(), Slot_Block);
243  }
244 
245  /// Returns the boundary index for associated with this index. The boundary
246  /// index is the one associated with the Slot_Block slot for the instruction
247  /// pointed to by this index.
249  return SlotIndex(listEntry(), Slot_Dead);
250  }
251 
252  /// Returns the register use/def slot in the current instruction for a
253  /// normal or early-clobber def.
254  SlotIndex getRegSlot(bool EC = false) const {
255  return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
256  }
257 
258  /// Returns the dead def kill slot for the current instruction.
260  return SlotIndex(listEntry(), Slot_Dead);
261  }
262 
263  /// Returns the next slot in the index list. This could be either the
264  /// next slot for the instruction pointed to by this index or, if this
265  /// index is a STORE, the first slot for the next instruction.
266  /// WARNING: This method is considerably more expensive than the methods
267  /// that return specific slots (getUseIndex(), etc). If you can - please
268  /// use one of those methods.
270  Slot s = getSlot();
271  if (s == Slot_Dead) {
272  return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
273  }
274  return SlotIndex(listEntry(), s + 1);
275  }
276 
277  /// Returns the next index. This is the index corresponding to the this
278  /// index's slot, but for the next instruction.
280  return SlotIndex(&*++listEntry()->getIterator(), getSlot());
281  }
282 
283  /// Returns the previous slot in the index list. This could be either the
284  /// previous slot for the instruction pointed to by this index or, if this
285  /// index is a Slot_Block, the last slot for the previous instruction.
286  /// WARNING: This method is considerably more expensive than the methods
287  /// that return specific slots (getUseIndex(), etc). If you can - please
288  /// use one of those methods.
290  Slot s = getSlot();
291  if (s == Slot_Block) {
292  return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
293  }
294  return SlotIndex(listEntry(), s - 1);
295  }
296 
297  /// Returns the previous index. This is the index corresponding to this
298  /// index's slot, but for the previous instruction.
300  return SlotIndex(&*--listEntry()->getIterator(), getSlot());
301  }
302  };
303 
305  li.print(os);
306  return os;
307  }
308 
309  using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
310 
311  inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
312  return V < IM.first;
313  }
314 
315  inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
316  return IM.first < V;
317  }
318 
319  struct Idx2MBBCompare {
320  bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
321  return LHS.first < RHS.first;
322  }
323  };
324 
325  /// SlotIndexes pass.
326  ///
327  /// This pass assigns indexes to each instruction.
329  private:
330  // IndexListEntry allocator.
331  BumpPtrAllocator ileAllocator;
332 
334  IndexList indexList;
335 
336 #ifdef EXPENSIVE_CHECKS
337  IndexList graveyardList;
338 #endif // EXPENSIVE_CHECKS
339 
340  MachineFunction *mf;
341 
343  Mi2IndexMap mi2iMap;
344 
345  /// MBBRanges - Map MBB number to (start, stop) indexes.
347 
348  /// Idx2MBBMap - Sorted list of pairs of index of first instruction
349  /// and MBB id.
350  SmallVector<IdxMBBPair, 8> idx2MBBMap;
351 
352  IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
353  IndexListEntry *entry =
354  static_cast<IndexListEntry *>(ileAllocator.Allocate(
355  sizeof(IndexListEntry), alignof(IndexListEntry)));
356 
357  new (entry) IndexListEntry(mi, index);
358 
359  return entry;
360  }
361 
362  /// Renumber locally after inserting curItr.
363  void renumberIndexes(IndexList::iterator curItr);
364 
365  public:
366  static char ID;
367 
370  }
371 
372  ~SlotIndexes() override {
373  // The indexList's nodes are all allocated in the BumpPtrAllocator.
374  indexList.clearAndLeakNodesUnsafely();
375  }
376 
377  void getAnalysisUsage(AnalysisUsage &au) const override;
378  void releaseMemory() override;
379 
380  bool runOnMachineFunction(MachineFunction &fn) override;
381 
382  /// Dump the indexes.
383  void dump() const;
384 
385  /// Renumber the index list, providing space for new instructions.
386  void renumberIndexes();
387 
388  /// Repair indexes after adding and removing instructions.
389  void repairIndexesInRange(MachineBasicBlock *MBB,
392 
393  /// Returns the zero index for this analysis.
395  assert(indexList.front().getIndex() == 0 && "First index is not 0?");
396  return SlotIndex(&indexList.front(), 0);
397  }
398 
399  /// Returns the base index of the last slot in this analysis.
401  return SlotIndex(&indexList.back(), 0);
402  }
403 
404  /// Returns true if the given machine instr is mapped to an index,
405  /// otherwise returns false.
406  bool hasIndex(const MachineInstr &instr) const {
407  return mi2iMap.count(&instr);
408  }
409 
410  /// Returns the base index for the given instruction.
412  // Instructions inside a bundle have the same number as the bundle itself.
413  auto BundleStart = getBundleStart(MI.getIterator());
414  auto BundleEnd = getBundleEnd(MI.getIterator());
415  // Use the first non-debug instruction in the bundle to get SlotIndex.
416  const MachineInstr &BundleNonDebug =
417  *skipDebugInstructionsForward(BundleStart, BundleEnd);
418  assert(!BundleNonDebug.isDebugInstr() &&
419  "Could not use a debug instruction to query mi2iMap.");
420  Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleNonDebug);
421  assert(itr != mi2iMap.end() && "Instruction not found in maps.");
422  return itr->second;
423  }
424 
425  /// Returns the instruction for the given index, or null if the given
426  /// index has no instruction associated with it.
428  return index.isValid() ? index.listEntry()->getInstr() : nullptr;
429  }
430 
431  /// Returns the next non-null index, if one exists.
432  /// Otherwise returns getLastIndex().
434  IndexList::iterator I = Index.listEntry()->getIterator();
435  IndexList::iterator E = indexList.end();
436  while (++I != E)
437  if (I->getInstr())
438  return SlotIndex(&*I, Index.getSlot());
439  // We reached the end of the function.
440  return getLastIndex();
441  }
442 
443  /// getIndexBefore - Returns the index of the last indexed instruction
444  /// before MI, or the start index of its basic block.
445  /// MI is not required to have an index.
447  const MachineBasicBlock *MBB = MI.getParent();
448  assert(MBB && "MI must be inserted in a basic block");
450  while (true) {
451  if (I == B)
452  return getMBBStartIdx(MBB);
453  --I;
454  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
455  if (MapItr != mi2iMap.end())
456  return MapItr->second;
457  }
458  }
459 
460  /// getIndexAfter - Returns the index of the first indexed instruction
461  /// after MI, or the end index of its basic block.
462  /// MI is not required to have an index.
464  const MachineBasicBlock *MBB = MI.getParent();
465  assert(MBB && "MI must be inserted in a basic block");
467  while (true) {
468  ++I;
469  if (I == E)
470  return getMBBEndIdx(MBB);
471  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
472  if (MapItr != mi2iMap.end())
473  return MapItr->second;
474  }
475  }
476 
477  /// Return the (start,end) range of the given basic block number.
478  const std::pair<SlotIndex, SlotIndex> &
479  getMBBRange(unsigned Num) const {
480  return MBBRanges[Num];
481  }
482 
483  /// Return the (start,end) range of the given basic block.
484  const std::pair<SlotIndex, SlotIndex> &
485  getMBBRange(const MachineBasicBlock *MBB) const {
486  return getMBBRange(MBB->getNumber());
487  }
488 
489  /// Returns the first index in the given basic block number.
490  SlotIndex getMBBStartIdx(unsigned Num) const {
491  return getMBBRange(Num).first;
492  }
493 
494  /// Returns the first index in the given basic block.
496  return getMBBRange(mbb).first;
497  }
498 
499  /// Returns the last index in the given basic block number.
500  SlotIndex getMBBEndIdx(unsigned Num) const {
501  return getMBBRange(Num).second;
502  }
503 
504  /// Returns the last index in the given basic block.
506  return getMBBRange(mbb).second;
507  }
508 
509  /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
510  /// begin and basic block)
512 
513  /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
514  /// equal to \p To.
516  return std::lower_bound(I, idx2MBBMap.end(), To);
517  }
518 
519  /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
520  /// that is greater or equal to \p Idx.
522  return advanceMBBIndex(idx2MBBMap.begin(), Idx);
523  }
524 
525  /// Returns an iterator for the begin of the idx2MBBMap.
527  return idx2MBBMap.begin();
528  }
529 
530  /// Return an iterator for the end of the idx2MBBMap.
532  return idx2MBBMap.end();
533  }
534 
535  /// Returns the basic block which the given index falls in.
537  if (MachineInstr *MI = getInstructionFromIndex(index))
538  return MI->getParent();
539 
540  MBBIndexIterator I = findMBBIndex(index);
541  // Take the pair containing the index
542  MBBIndexIterator J =
543  ((I != MBBIndexEnd() && I->first > index) ||
544  (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I;
545 
546  assert(J != MBBIndexEnd() && J->first <= index &&
547  index < getMBBEndIdx(J->second) &&
548  "index does not correspond to an MBB");
549  return J->second;
550  }
551 
552  /// Returns the MBB covering the given range, or null if the range covers
553  /// more than one basic block.
555 
556  assert(start < end && "Backwards ranges not allowed.");
557  MBBIndexIterator itr = findMBBIndex(start);
558  if (itr == MBBIndexEnd()) {
559  itr = std::prev(itr);
560  return itr->second;
561  }
562 
563  // Check that we don't cross the boundary into this block.
564  if (itr->first < end)
565  return nullptr;
566 
567  itr = std::prev(itr);
568 
569  if (itr->first <= start)
570  return itr->second;
571 
572  return nullptr;
573  }
574 
575  /// Insert the given machine instruction into the mapping. Returns the
576  /// assigned index.
577  /// If Late is set and there are null indexes between mi's neighboring
578  /// instructions, create the new index after the null indexes instead of
579  /// before them.
581  assert(!MI.isInsideBundle() &&
582  "Instructions inside bundles should use bundle start's slot.");
583  assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed.");
584  // Numbering debug instructions could cause code generation to be
585  // affected by debug information.
586  assert(!MI.isDebugInstr() && "Cannot number debug instructions.");
587 
588  assert(MI.getParent() != nullptr && "Instr must be added to function.");
589 
590  // Get the entries where MI should be inserted.
591  IndexList::iterator prevItr, nextItr;
592  if (Late) {
593  // Insert MI's index immediately before the following instruction.
594  nextItr = getIndexAfter(MI).listEntry()->getIterator();
595  prevItr = std::prev(nextItr);
596  } else {
597  // Insert MI's index immediately after the preceding instruction.
598  prevItr = getIndexBefore(MI).listEntry()->getIterator();
599  nextItr = std::next(prevItr);
600  }
601 
602  // Get a number for the new instr, or 0 if there's no room currently.
603  // In the latter case we'll force a renumber later.
604  unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
605  unsigned newNumber = prevItr->getIndex() + dist;
606 
607  // Insert a new list entry for MI.
608  IndexList::iterator newItr =
609  indexList.insert(nextItr, createEntry(&MI, newNumber));
610 
611  // Renumber locally if we need to.
612  if (dist == 0)
613  renumberIndexes(newItr);
614 
615  SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
616  mi2iMap.insert(std::make_pair(&MI, newIndex));
617  return newIndex;
618  }
619 
620  /// Removes machine instruction (bundle) \p MI from the mapping.
621  /// This should be called before MachineInstr::eraseFromParent() is used to
622  /// remove a whole bundle or an unbundled instruction.
623  void removeMachineInstrFromMaps(MachineInstr &MI);
624 
625  /// Removes a single machine instruction \p MI from the mapping.
626  /// This should be called before MachineInstr::eraseFromBundle() is used to
627  /// remove a single instruction (out of a bundle).
628  void removeSingleMachineInstrFromMaps(MachineInstr &MI);
629 
630  /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
631  /// maps used by register allocator. \returns the index where the new
632  /// instruction was inserted.
634  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
635  if (mi2iItr == mi2iMap.end())
636  return SlotIndex();
637  SlotIndex replaceBaseIndex = mi2iItr->second;
638  IndexListEntry *miEntry(replaceBaseIndex.listEntry());
639  assert(miEntry->getInstr() == &MI &&
640  "Mismatched instruction in index tables.");
641  miEntry->setInstr(&NewMI);
642  mi2iMap.erase(mi2iItr);
643  mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
644  return replaceBaseIndex;
645  }
646 
647  /// Add the given MachineBasicBlock into the maps.
649  MachineFunction::iterator nextMBB =
650  std::next(MachineFunction::iterator(mbb));
651 
652  IndexListEntry *startEntry = nullptr;
653  IndexListEntry *endEntry = nullptr;
654  IndexList::iterator newItr;
655  if (nextMBB == mbb->getParent()->end()) {
656  startEntry = &indexList.back();
657  endEntry = createEntry(nullptr, 0);
658  newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
659  } else {
660  startEntry = createEntry(nullptr, 0);
661  endEntry = getMBBStartIdx(&*nextMBB).listEntry();
662  newItr = indexList.insert(endEntry->getIterator(), startEntry);
663  }
664 
665  SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
666  SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
667 
668  MachineFunction::iterator prevMBB(mbb);
669  assert(prevMBB != mbb->getParent()->end() &&
670  "Can't insert a new block at the beginning of a function.");
671  --prevMBB;
672  MBBRanges[prevMBB->getNumber()].second = startIdx;
673 
674  assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
675  "Blocks must be added in order");
676  MBBRanges.push_back(std::make_pair(startIdx, endIdx));
677  idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
678 
679  renumberIndexes(newItr);
680  llvm::sort(idx2MBBMap, Idx2MBBCompare());
681  }
682 
683  /// Free the resources that were required to maintain a SlotIndex.
684  ///
685  /// Once an index is no longer needed (for instance because the instruction
686  /// at that index has been moved), the resources required to maintain the
687  /// index can be relinquished to reduce memory use and improve renumbering
688  /// performance. Any remaining SlotIndex objects that point to the same
689  /// index are left 'dangling' (much the same as a dangling pointer to a
690  /// freed object) and should not be accessed, except to destruct them.
691  ///
692  /// Like dangling pointers, access to dangling SlotIndexes can cause
693  /// painful-to-track-down bugs, especially if the memory for the index
694  /// previously pointed to has been re-used. To detect dangling SlotIndex
695  /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to
696  /// be retained in a graveyard instead of being freed. Operations on indexes
697  /// in the graveyard will trigger an assertion.
698  void eraseIndex(SlotIndex index) {
699  IndexListEntry *entry = index.listEntry();
700 #ifdef EXPENSIVE_CHECKS
701  indexList.remove(entry);
702  graveyardList.push_back(entry);
703  entry->setPoison();
704 #else
705  indexList.erase(entry);
706 #endif
707  }
708  };
709 
710  // Specialize IntervalMapInfo for half-open slot index intervals.
711  template <>
713  };
714 
715 } // end namespace llvm
716 
717 #endif // LLVM_CODEGEN_SLOTINDEXES_H
bool isRegister() const
isRegister - Returns true if this is a normal register use/def slot.
Definition: SlotIndexes.h:233
~SlotIndexes() override
Definition: SlotIndexes.h:372
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:258
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:515
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:241
iterator erase(iterator where)
Definition: ilist.h:265
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
MachineBasicBlock * getMBBCoveringRange(SlotIndex start, SlotIndex end) const
Returns the MBB covering the given range, or null if the range covers more than one basic block...
Definition: SlotIndexes.h:554
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:299
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
Definition: SlotIndexes.h:531
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:236
bool operator<(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:175
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:151
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
Custom traits to do nothing on deletion.
Definition: ilist.h:56
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:203
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
Definition: SlotIndexes.h:400
bool operator<=(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:180
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
Definition: SlotIndexes.h:226
SlotIndex getNextIndex() const
Returns the next index.
Definition: SlotIndexes.h:279
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:259
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:411
SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator
Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block) ...
Definition: SlotIndexes.h:511
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:433
void eraseIndex(SlotIndex index)
Free the resources that were required to maintain a SlotIndex.
Definition: SlotIndexes.h:698
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:536
SlotIndexes pass.
Definition: SlotIndexes.h:328
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:254
MachineBasicBlock::instr_iterator getBundleStart(MachineBasicBlock::instr_iterator I)
Returns an iterator to the first instruction in the bundle containing I.
IntType getInt() const
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:463
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:269
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1281
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
Definition: SlotIndexes.h:495
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
bool isInsideBundle() const
Return true if MI is in a bundle (but not the first MI in a bundle).
Definition: MachineInstr.h:349
void setIndex(unsigned index)
Definition: SlotIndexes.h:59
BasicBlockListType::iterator iterator
bool operator==(SlotIndex other) const
Compare two SlotIndex objects for equality.
Definition: SlotIndexes.h:165
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:580
MachineInstr * getInstr() const
Definition: SlotIndexes.h:53
Use delete by default for iplist and ilist.
Definition: ilist.h:40
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:427
bool erase(const KeyT &Val)
Definition: DenseMap.h:298
void initializeSlotIndexesPass(PassRegistry &)
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the last index in the given basic block.
Definition: SlotIndexes.h:505
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
SlotIndex(const SlotIndex &li, Slot s)
Definition: SlotIndexes.h:144
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:648
PointerIntPair - This class implements a pair of a pointer and small integer.
bool operator!=(SlotIndex other) const
Compare two SlotIndex objects for inequality.
Definition: SlotIndexes.h:169
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:214
unsigned getIndex() const
Definition: SlotIndexes.h:58
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:446
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:406
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:490
Represent the analysis usage information of a pass.
int getInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
Definition: SlotIndexes.h:220
std::pair< SlotIndex, MachineBasicBlock * > IdxMBBPair
Definition: SlotIndexes.h:309
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
Definition: SlotIndexes.h:394
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
Definition: SlotIndexes.h:526
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
void setInstr(MachineInstr *mi)
Definition: SlotIndexes.h:54
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:500
size_t size() const
Definition: SmallVector.h:52
bool isDebugInstr() const
Definition: MachineInstr.h:998
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const
Definition: SlotIndexes.h:320
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:197
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool operator>(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:186
void push_back(pointer val)
Definition: ilist.h:311
IndexListEntry(MachineInstr *mi, unsigned index)
Definition: SlotIndexes.h:51
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
Definition: SlotIndexes.h:229
IterT skipDebugInstructionsForward(IterT It, IterT End)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator...
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
bool operator>=(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:192
Representation of each machine instruction.
Definition: MachineInstr.h:63
pointer remove(iterator &IT)
Definition: ilist.h:249
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
static char ID
Definition: SlotIndexes.h:366
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
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:209
This class represents an entry in the slot index list held in the SlotIndexes pass.
Definition: SlotIndexes.h:46
const std::pair< SlotIndex, SlotIndex > & getMBBRange(const MachineBasicBlock *MBB) const
Return the (start,end) range of the given basic block.
Definition: SlotIndexes.h:485
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:289
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
int distance(SlotIndex other) const
Return the distance from this index to the given one.
Definition: SlotIndexes.h:214
#define I(x, y, z)
Definition: MD5.cpp:58
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
iterator end()
Definition: DenseMap.h:108
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:521
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
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:171
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:479
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:325
void clearAndLeakNodesUnsafely()
Remove all nodes from the list like clear(), but do not call removeNodeFromList() or deleteNode()...
Definition: ilist.h:278
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
print Instructions which execute on loop entry
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:235
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
Definition: SlotIndexes.h:248
SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in maps used by register allocat...
Definition: SlotIndexes.h:633