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