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