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