LLVM  15.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  SlotIndex(IndexListEntry *entry, unsigned slot)
112  : lie(entry, slot) {}
113 
114  IndexListEntry* listEntry() const {
115  assert(isValid() && "Attempt to compare reserved index.");
116 #ifdef EXPENSIVE_CHECKS
117  assert(!lie.getPointer()->isPoisoned() &&
118  "Attempt to access deleted list-entry.");
119 #endif // EXPENSIVE_CHECKS
120  return lie.getPointer();
121  }
122 
123  unsigned getIndex() const {
124  return listEntry()->getIndex() | getSlot();
125  }
126 
127  /// Returns the slot for this SlotIndex.
128  Slot getSlot() const {
129  return static_cast<Slot>(lie.getInt());
130  }
131 
132  public:
133  enum {
134  /// The default distance between instructions as returned by distance().
135  /// This may vary as instructions are inserted and removed.
136  InstrDist = 4 * Slot_Count
137  };
138 
139  /// Construct an invalid index.
140  SlotIndex() = default;
141 
142  // Construct a new slot index from the given one, and set the slot.
143  SlotIndex(const SlotIndex &li, Slot s) : lie(li.listEntry(), unsigned(s)) {
144  assert(lie.getPointer() != nullptr &&
145  "Attempt to construct index with 0 pointer.");
146  }
147 
148  /// Returns true if this is a valid index. Invalid indices do
149  /// not point into an index table, and cannot be compared.
150  bool isValid() const {
151  return lie.getPointer();
152  }
153 
154  /// Return true for a valid index.
155  explicit operator bool() const { return isValid(); }
156 
157  /// Print this index to the given raw_ostream.
158  void print(raw_ostream &os) const;
159 
160  /// Dump this index to stderr.
161  void dump() const;
162 
163  /// Compare two SlotIndex objects for equality.
164  bool operator==(SlotIndex other) const {
165  return lie == other.lie;
166  }
167  /// Compare two SlotIndex objects for inequality.
168  bool operator!=(SlotIndex other) const {
169  return lie != other.lie;
170  }
171 
172  /// Compare two SlotIndex objects. Return true if the first index
173  /// is strictly lower than the second.
174  bool operator<(SlotIndex other) const {
175  return getIndex() < other.getIndex();
176  }
177  /// Compare two SlotIndex objects. Return true if the first index
178  /// is lower than, or equal to, the second.
179  bool operator<=(SlotIndex other) const {
180  return getIndex() <= other.getIndex();
181  }
182 
183  /// Compare two SlotIndex objects. Return true if the first index
184  /// is greater than the second.
185  bool operator>(SlotIndex other) const {
186  return getIndex() > other.getIndex();
187  }
188 
189  /// Compare two SlotIndex objects. Return true if the first index
190  /// is greater than, or equal to, the second.
191  bool operator>=(SlotIndex other) const {
192  return getIndex() >= other.getIndex();
193  }
194 
195  /// isSameInstr - Return true if A and B refer to the same instruction.
197  return A.lie.getPointer() == B.lie.getPointer();
198  }
199 
200  /// isEarlierInstr - Return true if A refers to an instruction earlier than
201  /// B. This is equivalent to A < B && !isSameInstr(A, B).
203  return A.listEntry()->getIndex() < B.listEntry()->getIndex();
204  }
205 
206  /// Return true if A refers to the same instruction as B or an earlier one.
207  /// This is equivalent to !isEarlierInstr(B, A).
209  return !isEarlierInstr(B, A);
210  }
211 
212  /// Return the distance from this index to the given one.
213  int distance(SlotIndex other) const {
214  return other.getIndex() - getIndex();
215  }
216 
217  /// Return the scaled distance from this index to the given one, where all
218  /// slots on the same instruction have zero distance.
219  int getInstrDistance(SlotIndex other) const {
220  return (other.listEntry()->getIndex() - listEntry()->getIndex())
221  / Slot_Count;
222  }
223 
224  /// isBlock - Returns true if this is a block boundary slot.
225  bool isBlock() const { return getSlot() == Slot_Block; }
226 
227  /// isEarlyClobber - Returns true if this is an early-clobber slot.
228  bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; }
229 
230  /// isRegister - Returns true if this is a normal register use/def slot.
231  /// Note that early-clobber slots may also be used for uses and defs.
232  bool isRegister() const { return getSlot() == Slot_Register; }
233 
234  /// isDead - Returns true if this is a dead def kill slot.
235  bool isDead() const { return getSlot() == Slot_Dead; }
236 
237  /// Returns the base index for associated with this index. The base index
238  /// is the one associated with the Slot_Block slot for the instruction
239  /// pointed to by this index.
241  return SlotIndex(listEntry(), Slot_Block);
242  }
243 
244  /// Returns the boundary index for associated with this index. The boundary
245  /// index is the one associated with the Slot_Block slot for the instruction
246  /// pointed to by this index.
248  return SlotIndex(listEntry(), Slot_Dead);
249  }
250 
251  /// Returns the register use/def slot in the current instruction for a
252  /// normal or early-clobber def.
253  SlotIndex getRegSlot(bool EC = false) const {
254  return SlotIndex(listEntry(), EC ? Slot_EarlyClobber : Slot_Register);
255  }
256 
257  /// Returns the dead def kill slot for the current instruction.
259  return SlotIndex(listEntry(), Slot_Dead);
260  }
261 
262  /// Returns the next slot in the index list. This could be either the
263  /// next slot for the instruction pointed to by this index or, if this
264  /// index is a STORE, the first slot for the next instruction.
265  /// WARNING: This method is considerably more expensive than the methods
266  /// that return specific slots (getUseIndex(), etc). If you can - please
267  /// use one of those methods.
269  Slot s = getSlot();
270  if (s == Slot_Dead) {
271  return SlotIndex(&*++listEntry()->getIterator(), Slot_Block);
272  }
273  return SlotIndex(listEntry(), s + 1);
274  }
275 
276  /// Returns the next index. This is the index corresponding to the this
277  /// index's slot, but for the next instruction.
279  return SlotIndex(&*++listEntry()->getIterator(), getSlot());
280  }
281 
282  /// Returns the previous slot in the index list. This could be either the
283  /// previous slot for the instruction pointed to by this index or, if this
284  /// index is a Slot_Block, the last slot for the previous instruction.
285  /// WARNING: This method is considerably more expensive than the methods
286  /// that return specific slots (getUseIndex(), etc). If you can - please
287  /// use one of those methods.
289  Slot s = getSlot();
290  if (s == Slot_Block) {
291  return SlotIndex(&*--listEntry()->getIterator(), Slot_Dead);
292  }
293  return SlotIndex(listEntry(), s - 1);
294  }
295 
296  /// Returns the previous index. This is the index corresponding to this
297  /// index's slot, but for the previous instruction.
299  return SlotIndex(&*--listEntry()->getIterator(), getSlot());
300  }
301  };
302 
304  li.print(os);
305  return os;
306  }
307 
308  using IdxMBBPair = std::pair<SlotIndex, MachineBasicBlock *>;
309 
310  /// SlotIndexes pass.
311  ///
312  /// This pass assigns indexes to each instruction.
314  private:
315  // IndexListEntry allocator.
316  BumpPtrAllocator ileAllocator;
317 
319  IndexList indexList;
320 
321  MachineFunction *mf = nullptr;
322 
324  Mi2IndexMap mi2iMap;
325 
326  /// MBBRanges - Map MBB number to (start, stop) indexes.
328 
329  /// Idx2MBBMap - Sorted list of pairs of index of first instruction
330  /// and MBB id.
331  SmallVector<IdxMBBPair, 8> idx2MBBMap;
332 
333  IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
335  static_cast<IndexListEntry *>(ileAllocator.Allocate(
336  sizeof(IndexListEntry), alignof(IndexListEntry)));
337 
338  new (entry) IndexListEntry(mi, index);
339 
340  return entry;
341  }
342 
343  /// Renumber locally after inserting curItr.
344  void renumberIndexes(IndexList::iterator curItr);
345 
346  public:
347  static char ID;
348 
349  SlotIndexes();
350 
351  ~SlotIndexes() override;
352 
353  void getAnalysisUsage(AnalysisUsage &au) const override;
354  void releaseMemory() override;
355 
356  bool runOnMachineFunction(MachineFunction &fn) override;
357 
358  /// Dump the indexes.
359  void dump() const;
360 
361  /// Repair indexes after adding and removing instructions.
365 
366  /// Returns the zero index for this analysis.
368  assert(indexList.front().getIndex() == 0 && "First index is not 0?");
369  return SlotIndex(&indexList.front(), 0);
370  }
371 
372  /// Returns the base index of the last slot in this analysis.
374  return SlotIndex(&indexList.back(), 0);
375  }
376 
377  /// Returns true if the given machine instr is mapped to an index,
378  /// otherwise returns false.
379  bool hasIndex(const MachineInstr &instr) const {
380  return mi2iMap.count(&instr);
381  }
382 
383  /// Returns the base index for the given instruction.
385  bool IgnoreBundle = false) const {
386  // Instructions inside a bundle have the same number as the bundle itself.
387  auto BundleStart = getBundleStart(MI.getIterator());
388  auto BundleEnd = getBundleEnd(MI.getIterator());
389  // Use the first non-debug instruction in the bundle to get SlotIndex.
390  const MachineInstr &BundleNonDebug =
391  IgnoreBundle ? MI
392  : *skipDebugInstructionsForward(BundleStart, BundleEnd);
393  assert(!BundleNonDebug.isDebugInstr() &&
394  "Could not use a debug instruction to query mi2iMap.");
395  Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleNonDebug);
396  assert(itr != mi2iMap.end() && "Instruction not found in maps.");
397  return itr->second;
398  }
399 
400  /// Returns the instruction for the given index, or null if the given
401  /// index has no instruction associated with it.
403  return index.isValid() ? index.listEntry()->getInstr() : nullptr;
404  }
405 
406  /// Returns the next non-null index, if one exists.
407  /// Otherwise returns getLastIndex().
409  IndexList::iterator I = Index.listEntry()->getIterator();
410  IndexList::iterator E = indexList.end();
411  while (++I != E)
412  if (I->getInstr())
413  return SlotIndex(&*I, Index.getSlot());
414  // We reached the end of the function.
415  return getLastIndex();
416  }
417 
418  /// getIndexBefore - Returns the index of the last indexed instruction
419  /// before MI, or the start index of its basic block.
420  /// MI is not required to have an index.
422  const MachineBasicBlock *MBB = MI.getParent();
423  assert(MBB && "MI must be inserted in a basic block");
425  while (true) {
426  if (I == B)
427  return getMBBStartIdx(MBB);
428  --I;
429  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
430  if (MapItr != mi2iMap.end())
431  return MapItr->second;
432  }
433  }
434 
435  /// getIndexAfter - Returns the index of the first indexed instruction
436  /// after MI, or the end index of its basic block.
437  /// MI is not required to have an index.
439  const MachineBasicBlock *MBB = MI.getParent();
440  assert(MBB && "MI must be inserted in a basic block");
442  while (true) {
443  ++I;
444  if (I == E)
445  return getMBBEndIdx(MBB);
446  Mi2IndexMap::const_iterator MapItr = mi2iMap.find(&*I);
447  if (MapItr != mi2iMap.end())
448  return MapItr->second;
449  }
450  }
451 
452  /// Return the (start,end) range of the given basic block number.
453  const std::pair<SlotIndex, SlotIndex> &
454  getMBBRange(unsigned Num) const {
455  return MBBRanges[Num];
456  }
457 
458  /// Return the (start,end) range of the given basic block.
459  const std::pair<SlotIndex, SlotIndex> &
461  return getMBBRange(MBB->getNumber());
462  }
463 
464  /// Returns the first index in the given basic block number.
465  SlotIndex getMBBStartIdx(unsigned Num) const {
466  return getMBBRange(Num).first;
467  }
468 
469  /// Returns the first index in the given basic block.
471  return getMBBRange(mbb).first;
472  }
473 
474  /// Returns the last index in the given basic block number.
475  SlotIndex getMBBEndIdx(unsigned Num) const {
476  return getMBBRange(Num).second;
477  }
478 
479  /// Returns the last index in the given basic block.
481  return getMBBRange(mbb).second;
482  }
483 
484  /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
485  /// begin and basic block)
487 
488  /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
489  /// equal to \p To.
491  return std::partition_point(
492  I, idx2MBBMap.end(),
493  [=](const IdxMBBPair &IM) { return IM.first < To; });
494  }
495 
496  /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
497  /// that is greater or equal to \p Idx.
499  return advanceMBBIndex(idx2MBBMap.begin(), Idx);
500  }
501 
502  /// Returns an iterator for the begin of the idx2MBBMap.
504  return idx2MBBMap.begin();
505  }
506 
507  /// Return an iterator for the end of the idx2MBBMap.
509  return idx2MBBMap.end();
510  }
511 
512  /// Returns the basic block which the given index falls in.
515  return MI->getParent();
516 
518  // Take the pair containing the index
519  MBBIndexIterator J =
520  ((I != MBBIndexEnd() && I->first > index) ||
521  (I == MBBIndexEnd() && !idx2MBBMap.empty())) ? std::prev(I) : I;
522 
523  assert(J != MBBIndexEnd() && J->first <= index &&
524  index < getMBBEndIdx(J->second) &&
525  "index does not correspond to an MBB");
526  return J->second;
527  }
528 
529  /// Insert the given machine instruction into the mapping. Returns the
530  /// assigned index.
531  /// If Late is set and there are null indexes between mi's neighboring
532  /// instructions, create the new index after the null indexes instead of
533  /// before them.
535  assert(!MI.isInsideBundle() &&
536  "Instructions inside bundles should use bundle start's slot.");
537  assert(mi2iMap.find(&MI) == mi2iMap.end() && "Instr already indexed.");
538  // Numbering debug instructions could cause code generation to be
539  // affected by debug information.
540  assert(!MI.isDebugInstr() && "Cannot number debug instructions.");
541 
542  assert(MI.getParent() != nullptr && "Instr must be added to function.");
543 
544  // Get the entries where MI should be inserted.
545  IndexList::iterator prevItr, nextItr;
546  if (Late) {
547  // Insert MI's index immediately before the following instruction.
548  nextItr = getIndexAfter(MI).listEntry()->getIterator();
549  prevItr = std::prev(nextItr);
550  } else {
551  // Insert MI's index immediately after the preceding instruction.
552  prevItr = getIndexBefore(MI).listEntry()->getIterator();
553  nextItr = std::next(prevItr);
554  }
555 
556  // Get a number for the new instr, or 0 if there's no room currently.
557  // In the latter case we'll force a renumber later.
558  unsigned dist = ((nextItr->getIndex() - prevItr->getIndex())/2) & ~3u;
559  unsigned newNumber = prevItr->getIndex() + dist;
560 
561  // Insert a new list entry for MI.
562  IndexList::iterator newItr =
563  indexList.insert(nextItr, createEntry(&MI, newNumber));
564 
565  // Renumber locally if we need to.
566  if (dist == 0)
567  renumberIndexes(newItr);
568 
569  SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
570  mi2iMap.insert(std::make_pair(&MI, newIndex));
571  return newIndex;
572  }
573 
574  /// Removes machine instruction (bundle) \p MI from the mapping.
575  /// This should be called before MachineInstr::eraseFromParent() is used to
576  /// remove a whole bundle or an unbundled instruction.
577  /// If \p AllowBundled is set then this can be used on a bundled
578  /// instruction; however, this exists to support handleMoveIntoBundle,
579  /// and in general removeSingleMachineInstrFromMaps should be used instead.
581  bool AllowBundled = false);
582 
583  /// Removes a single machine instruction \p MI from the mapping.
584  /// This should be called before MachineInstr::eraseFromBundle() is used to
585  /// remove a single instruction (out of a bundle).
587 
588  /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
589  /// maps used by register allocator. \returns the index where the new
590  /// instruction was inserted.
592  Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
593  if (mi2iItr == mi2iMap.end())
594  return SlotIndex();
595  SlotIndex replaceBaseIndex = mi2iItr->second;
596  IndexListEntry *miEntry(replaceBaseIndex.listEntry());
597  assert(miEntry->getInstr() == &MI &&
598  "Mismatched instruction in index tables.");
599  miEntry->setInstr(&NewMI);
600  mi2iMap.erase(mi2iItr);
601  mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
602  return replaceBaseIndex;
603  }
604 
605  /// Add the given MachineBasicBlock into the maps.
606  /// If it contains any instructions then they must already be in the maps.
607  /// This is used after a block has been split by moving some suffix of its
608  /// instructions into a newly created block.
610  assert(mbb != &mbb->getParent()->front() &&
611  "Can't insert a new block at the beginning of a function.");
612  auto prevMBB = std::prev(MachineFunction::iterator(mbb));
613 
614  // Create a new entry to be used for the start of mbb and the end of
615  // prevMBB.
616  IndexListEntry *startEntry = createEntry(nullptr, 0);
617  IndexListEntry *endEntry = getMBBEndIdx(&*prevMBB).listEntry();
618  IndexListEntry *insEntry =
619  mbb->empty() ? endEntry
620  : getInstructionIndex(mbb->front()).listEntry();
621  IndexList::iterator newItr =
622  indexList.insert(insEntry->getIterator(), startEntry);
623 
624  SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
625  SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
626 
627  MBBRanges[prevMBB->getNumber()].second = startIdx;
628 
629  assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
630  "Blocks must be added in order");
631  MBBRanges.push_back(std::make_pair(startIdx, endIdx));
632  idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
633 
634  renumberIndexes(newItr);
635  llvm::sort(idx2MBBMap, less_first());
636  }
637  };
638 
639  // Specialize IntervalMapInfo for half-open slot index intervals.
640  template <>
642  };
643 
644 } // end namespace llvm
645 
646 #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:454
llvm::SlotIndex::dump
void dump() const
Dump this index to stderr.
Definition: SlotIndexes.cpp:277
llvm::SlotIndexes::insertMBBInMaps
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:609
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
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:17
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:208
llvm::SlotIndex::isValid
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:150
llvm::SlotIndex::operator==
bool operator==(SlotIndex other) const
Compare two SlotIndex objects for equality.
Definition: SlotIndexes.h:164
llvm::SlotIndex::getBoundaryIndex
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
Definition: SlotIndexes.h:247
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:1185
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:168
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:304
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:147
llvm::SlotIndex::isEarlyClobber
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
Definition: SlotIndexes.h:228
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:475
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:804
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
Definition: SlotIndexes.h:470
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:834
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:379
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:1344
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:202
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineInstr::isDebugInstr
bool isDebugInstr() const
Definition: MachineInstr.h:1224
llvm::SlotIndex::operator>=
bool operator>=(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:191
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:384
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
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:250
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::SlotIndex::getDeadSlot
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:258
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:313
llvm::SlotIndex::isRegister
bool isRegister() const
isRegister - Returns true if this is a normal register use/def slot.
Definition: SlotIndexes.h:232
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:402
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:498
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:421
llvm::SlotIndexes::insertMachineInstrInMaps
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:534
llvm::SlotIndexes::MBBIndexEnd
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
Definition: SlotIndexes.h:508
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:60
llvm::SlotIndex::getPrevIndex
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:298
llvm::SlotIndex::getBaseIndex
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:240
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:465
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:591
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:503
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:196
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:152
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:234
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:513
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:438
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:253
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::IntervalMapHalfOpenInfo
Definition: IntervalMap.h:167
llvm::SlotIndex::InstrDist
@ InstrDist
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:136
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:1228
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1078
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:490
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:373
A
* A
Definition: README_ALTIVEC.txt:89
llvm::SlotIndex::getNextIndex
SlotIndex getNextIndex() const
Returns the next index.
Definition: SlotIndexes.h:278
llvm::SlotIndex::print
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
Definition: SlotIndexes.cpp:268
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:268
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
llvm::ilist_node
Definition: ilist_node.h:149
llvm::SlotIndexes::getZeroIndex
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
Definition: SlotIndexes.h:367
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:1764
llvm::IdxMBBPair
std::pair< SlotIndex, MachineBasicBlock * > IdxMBBPair
Definition: SlotIndexes.h:308
llvm::SlotIndex::operator<=
bool operator<=(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:179
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::SlotIndex::SlotIndex
SlotIndex(const SlotIndex &li, Slot s)
Definition: SlotIndexes.h:143
llvm::SlotIndex::getPrevSlot
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:288
llvm::SlotIndexes::ID
static char ID
Definition: SlotIndexes.h:347
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:146
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:486
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:256
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1552
llvm::SlotIndexes::SlotIndexes
SlotIndexes()
Definition: SlotIndexes.cpp:23
llvm::SlotIndex::getInstrDistance
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:219
llvm::SlotIndex::operator>
bool operator>(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:185
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:408
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:460
llvm::IndexListEntry::getIndex
unsigned getIndex() const
Definition: SlotIndexes.h:57
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the last index in the given basic block.
Definition: SlotIndexes.h:480
llvm::SlotIndex::operator<
bool operator<(SlotIndex other) const
Compare two SlotIndex objects.
Definition: SlotIndexes.h:174
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:225
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:249
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::distance
int distance(SlotIndex other) const
Return the distance from this index to the given one.
Definition: SlotIndexes.h:213
llvm::SlotIndex::isDead
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:235
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::IndexListEntry::setIndex
void setIndex(unsigned index)
Definition: SlotIndexes.h:58
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:336