LLVM  6.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  const MachineInstr &BundleStart = *getBundleStart(MI.getIterator());
417  Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleStart);
418  assert(itr != mi2iMap.end() && "Instruction not found in maps.");
419  return itr->second;
420  }
421 
422  /// Returns the instruction for the given index, or null if the given
423  /// index has no instruction associated with it.
425  return index.isValid() ? index.listEntry()->getInstr() : nullptr;
426  }
427 
428  /// Returns the next non-null index, if one exists.
429  /// Otherwise returns getLastIndex().
431  IndexList::iterator I = Index.listEntry()->getIterator();
432  IndexList::iterator E = indexList.end();
433  while (++I != E)
434  if (I->getInstr())
435  return SlotIndex(&*I, Index.getSlot());
436  // We reached the end of the function.
437  return getLastIndex();
438  }
439 
440  /// getIndexBefore - Returns the index of the last indexed instruction
441  /// before MI, or the start index of its basic block.
442  /// MI is not required to have an index.
444  const MachineBasicBlock *MBB = MI.getParent();
445  assert(MBB && "MI must be inserted inna basic block");
447  while (true) {
448  if (I == B)
449  return getMBBStartIdx(MBB);
450  --I;
451  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
452  if (MapItr != mi2iMap.end())
453  return MapItr->second;
454  }
455  }
456 
457  /// getIndexAfter - Returns the index of the first indexed instruction
458  /// after MI, or the end index of its basic block.
459  /// MI is not required to have an index.
461  const MachineBasicBlock *MBB = MI.getParent();
462  assert(MBB && "MI must be inserted inna basic block");
464  while (true) {
465  ++I;
466  if (I == E)
467  return getMBBEndIdx(MBB);
468  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
469  if (MapItr != mi2iMap.end())
470  return MapItr->second;
471  }
472  }
473 
474  /// Return the (start,end) range of the given basic block number.
475  const std::pair<SlotIndex, SlotIndex> &
476  getMBBRange(unsigned Num) const {
477  return MBBRanges[Num];
478  }
479 
480  /// Return the (start,end) range of the given basic block.
481  const std::pair<SlotIndex, SlotIndex> &
482  getMBBRange(const MachineBasicBlock *MBB) const {
483  return getMBBRange(MBB->getNumber());
484  }
485 
486  /// Returns the first index in the given basic block number.
487  SlotIndex getMBBStartIdx(unsigned Num) const {
488  return getMBBRange(Num).first;
489  }
490 
491  /// Returns the first index in the given basic block.
493  return getMBBRange(mbb).first;
494  }
495 
496  /// Returns the last index in the given basic block number.
497  SlotIndex getMBBEndIdx(unsigned Num) const {
498  return getMBBRange(Num).second;
499  }
500 
501  /// Returns the last index in the given basic block.
503  return getMBBRange(mbb).second;
504  }
505 
506  /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
507  /// begin and basic block)
509 
510  /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
511  /// equal to \p To.
513  return std::lower_bound(I, idx2MBBMap.end(), To);
514  }
515 
516  /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
517  /// that is greater or equal to \p Idx.
519  return advanceMBBIndex(idx2MBBMap.begin(), Idx);
520  }
521 
522  /// Returns an iterator for the begin of the idx2MBBMap.
524  return idx2MBBMap.begin();
525  }
526 
527  /// Return an iterator for the end of the idx2MBBMap.
529  return idx2MBBMap.end();
530  }
531 
532  /// Returns the basic block which the given index falls in.
534  if (MachineInstr *MI = getInstructionFromIndex(index))
535  return MI->getParent();
536 
537  MBBIndexIterator I = findMBBIndex(index);
538  // Take the pair containing the index
539  MBBIndexIterator J =
540  ((I != MBBIndexEnd() && I->first > index) ||
541  (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I;
542 
543  assert(J != MBBIndexEnd() && J->first <= index &&
544  index < getMBBEndIdx(J->second) &&
545  "index does not correspond to an MBB");
546  return J->second;
547  }
548 
549  /// Returns the MBB covering the given range, or null if the range covers
550  /// more than one basic block.
552 
553  assert(start < end && "Backwards ranges not allowed.");
554  MBBIndexIterator itr = findMBBIndex(start);
555  if (itr == MBBIndexEnd()) {
556  itr = std::prev(itr);
557  return itr->second;
558  }
559 
560  // Check that we don't cross the boundary into this block.
561  if (itr->first < end)
562  return nullptr;
563 
564  itr = std::prev(itr);
565 
566  if (itr->first <= start)
567  return itr->second;
568 
569  return nullptr;
570  }
571 
572  /// Insert the given machine instruction into the mapping. Returns the
573  /// assigned index.
574  /// If Late is set and there are null indexes between mi's neighboring
575  /// instructions, create the new index after the null indexes instead of
576  /// before them.
578  assert(!MI.isInsideBundle() &&
579  "Instructions inside bundles should use bundle start's slot.");
580  assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed.");
581  // Numbering DBG_VALUE instructions could cause code generation to be
582  // affected by debug information.
583  assert(!MI.isDebugValue() && "Cannot number DBG_VALUE instructions.");
584 
585  assert(MI.getParent() != nullptr && "Instr must be added to function.");
586 
587  // Get the entries where MI should be inserted.
588  IndexList::iterator prevItr, nextItr;
589  if (Late) {
590  // Insert MI's index immediately before the following instruction.
591  nextItr = getIndexAfter(MI).listEntry()->getIterator();
592  prevItr = std::prev(nextItr);
593  } else {
594  // Insert MI's index immediately after the preceding instruction.
595  prevItr = getIndexBefore(MI).listEntry()->getIterator();
596  nextItr = std::next(prevItr);
597  }
598 
599  // Get a number for the new instr, or 0 if there's no room currently.
600  // In the latter case we'll force a renumber later.
601  unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
602  unsigned newNumber = prevItr->getIndex() + dist;
603 
604  // Insert a new list entry for MI.
605  IndexList::iterator newItr =
606  indexList.insert(nextItr, createEntry(&MI, newNumber));
607 
608  // Renumber locally if we need to.
609  if (dist == 0)
610  renumberIndexes(newItr);
611 
612  SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
613  mi2iMap.insert(std::make_pair(&MI, newIndex));
614  return newIndex;
615  }
616 
617  /// Removes machine instruction (bundle) \p MI from the mapping.
618  /// This should be called before MachineInstr::eraseFromParent() is used to
619  /// remove a whole bundle or an unbundled instruction.
620  void removeMachineInstrFromMaps(MachineInstr &MI);
621 
622  /// Removes a single machine instruction \p MI from the mapping.
623  /// This should be called before MachineInstr::eraseFromBundle() is used to
624  /// remove a single instruction (out of a bundle).
625  void removeSingleMachineInstrFromMaps(MachineInstr &MI);
626 
627  /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
628  /// maps used by register allocator. \returns the index where the new
629  /// instruction was inserted.
631  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
632  if (mi2iItr == mi2iMap.end())
633  return SlotIndex();
634  SlotIndex replaceBaseIndex = mi2iItr->second;
635  IndexListEntry *miEntry(replaceBaseIndex.listEntry());
636  assert(miEntry->getInstr() == &MI &&
637  "Mismatched instruction in index tables.");
638  miEntry->setInstr(&NewMI);
639  mi2iMap.erase(mi2iItr);
640  mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
641  return replaceBaseIndex;
642  }
643 
644  /// Add the given MachineBasicBlock into the maps.
646  MachineFunction::iterator nextMBB =
647  std::next(MachineFunction::iterator(mbb));
648 
649  IndexListEntry *startEntry = nullptr;
650  IndexListEntry *endEntry = nullptr;
651  IndexList::iterator newItr;
652  if (nextMBB == mbb->getParent()->end()) {
653  startEntry = &indexList.back();
654  endEntry = createEntry(nullptr, 0);
655  newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
656  } else {
657  startEntry = createEntry(nullptr, 0);
658  endEntry = getMBBStartIdx(&*nextMBB).listEntry();
659  newItr = indexList.insert(endEntry->getIterator(), startEntry);
660  }
661 
662  SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
663  SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
664 
665  MachineFunction::iterator prevMBB(mbb);
666  assert(prevMBB != mbb->getParent()->end() &&
667  "Can't insert a new block at the beginning of a function.");
668  --prevMBB;
669  MBBRanges[prevMBB->getNumber()].second = startIdx;
670 
671  assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
672  "Blocks must be added in order");
673  MBBRanges.push_back(std::make_pair(startIdx, endIdx));
674  idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
675 
676  renumberIndexes(newItr);
677  std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
678  }
679 
680  /// \brief Free the resources that were required to maintain a SlotIndex.
681  ///
682  /// Once an index is no longer needed (for instance because the instruction
683  /// at that index has been moved), the resources required to maintain the
684  /// index can be relinquished to reduce memory use and improve renumbering
685  /// performance. Any remaining SlotIndex objects that point to the same
686  /// index are left 'dangling' (much the same as a dangling pointer to a
687  /// freed object) and should not be accessed, except to destruct them.
688  ///
689  /// Like dangling pointers, access to dangling SlotIndexes can cause
690  /// painful-to-track-down bugs, especially if the memory for the index
691  /// previously pointed to has been re-used. To detect dangling SlotIndex
692  /// bugs, build with EXPENSIVE_CHECKS=1. This will cause "erased" indexes to
693  /// be retained in a graveyard instead of being freed. Operations on indexes
694  /// in the graveyard will trigger an assertion.
695  void eraseIndex(SlotIndex index) {
696  IndexListEntry *entry = index.listEntry();
697 #ifdef EXPENSIVE_CHECKS
698  indexList.remove(entry);
699  graveyardList.push_back(entry);
700  entry->setPoison();
701 #else
702  indexList.erase(entry);
703 #endif
704  }
705  };
706 
707  // Specialize IntervalMapInfo for half-open slot index intervals.
708  template <>
710  };
711 
712 } // end namespace llvm
713 
714 #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:244
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:512
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:280
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:551
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:300
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
Definition: SlotIndexes.h:528
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:191
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:508
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:430
void eraseIndex(SlotIndex index)
Free the resources that were required to maintain a SlotIndex.
Definition: SlotIndexes.h:695
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:533
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:460
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:904
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
Definition: SlotIndexes.h:492
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:235
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:146
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:577
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:424
bool erase(const KeyT &Val)
Definition: DenseMap.h:268
void initializeSlotIndexesPass(PassRegistry &)
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the last index in the given basic block.
Definition: SlotIndexes.h:502
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:645
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:138
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
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:212
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:443
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:487
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
static const unsigned End
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
Definition: SlotIndexes.h:523
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:497
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:403
bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const
Definition: SlotIndexes.h:323
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
bool isDebugValue() const
Definition: MachineInstr.h:816
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool operator>(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:187
void push_back(pointer val)
Definition: ilist.h:326
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
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
bool operator>=(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:193
Representation of each machine instruction.
Definition: MachineInstr.h:59
pointer remove(iterator &IT)
Definition: ilist.h:264
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:120
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
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:482
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
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:79
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:518
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
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:141
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:476
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:293
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
IRTranslator LLVM IR MI
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:250
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:630