LLVM  13.0.0git
LiveInterval.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/LiveInterval.h - Interval 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 the LiveRange and LiveInterval classes. Given some
10 // numbering of each the machine instructions an interval [i, j) is said to be a
11 // live range for register v if there is no instruction with number j' >= j
12 // such that v is live at j' and there is no instruction with number i' < i such
13 // that v is live at i'. In this implementation ranges can have holes,
14 // i.e. a range might look like [1,20), [50,65), [1000,1001). Each
15 // individual segment is represented as an instance of LiveRange::Segment,
16 // and the whole range is represented as an instance of LiveRange.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
21 #define LLVM_CODEGEN_LIVEINTERVAL_H
22 
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/IntEqClasses.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/CodeGen/Register.h"
30 #include "llvm/MC/LaneBitmask.h"
31 #include "llvm/Support/Allocator.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <cstddef>
36 #include <functional>
37 #include <memory>
38 #include <set>
39 #include <tuple>
40 #include <utility>
41 
42 namespace llvm {
43 
44  class CoalescerPair;
45  class LiveIntervals;
46  class MachineRegisterInfo;
47  class raw_ostream;
48 
49  /// VNInfo - Value Number Information.
50  /// This class holds information about a machine level values, including
51  /// definition and use points.
52  ///
53  class VNInfo {
54  public:
56 
57  /// The ID number of this value.
58  unsigned id;
59 
60  /// The index of the defining instruction.
62 
63  /// VNInfo constructor.
64  VNInfo(unsigned i, SlotIndex d) : id(i), def(d) {}
65 
66  /// VNInfo constructor, copies values from orig, except for the value number.
67  VNInfo(unsigned i, const VNInfo &orig) : id(i), def(orig.def) {}
68 
69  /// Copy from the parameter into this VNInfo.
70  void copyFrom(VNInfo &src) {
71  def = src.def;
72  }
73 
74  /// Returns true if this value is defined by a PHI instruction (or was,
75  /// PHI instructions may have been eliminated).
76  /// PHI-defs begin at a block boundary, all other defs begin at register or
77  /// EC slots.
78  bool isPHIDef() const { return def.isBlock(); }
79 
80  /// Returns true if this value is unused.
81  bool isUnused() const { return !def.isValid(); }
82 
83  /// Mark this value as unused.
84  void markUnused() { def = SlotIndex(); }
85  };
86 
87  /// Result of a LiveRange query. This class hides the implementation details
88  /// of live ranges, and it should be used as the primary interface for
89  /// examining live ranges around instructions.
91  VNInfo *const EarlyVal;
92  VNInfo *const LateVal;
93  const SlotIndex EndPoint;
94  const bool Kill;
95 
96  public:
97  LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint,
98  bool Kill)
99  : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill)
100  {}
101 
102  /// Return the value that is live-in to the instruction. This is the value
103  /// that will be read by the instruction's use operands. Return NULL if no
104  /// value is live-in.
105  VNInfo *valueIn() const {
106  return EarlyVal;
107  }
108 
109  /// Return true if the live-in value is killed by this instruction. This
110  /// means that either the live range ends at the instruction, or it changes
111  /// value.
112  bool isKill() const {
113  return Kill;
114  }
115 
116  /// Return true if this instruction has a dead def.
117  bool isDeadDef() const {
118  return EndPoint.isDead();
119  }
120 
121  /// Return the value leaving the instruction, if any. This can be a
122  /// live-through value, or a live def. A dead def returns NULL.
123  VNInfo *valueOut() const {
124  return isDeadDef() ? nullptr : LateVal;
125  }
126 
127  /// Returns the value alive at the end of the instruction, if any. This can
128  /// be a live-through value, a live def or a dead def.
130  return LateVal;
131  }
132 
133  /// Return the value defined by this instruction, if any. This includes
134  /// dead defs, it is the value created by the instruction's def operands.
135  VNInfo *valueDefined() const {
136  return EarlyVal == LateVal ? nullptr : LateVal;
137  }
138 
139  /// Return the end point of the last live range segment to interact with
140  /// the instruction, if any.
141  ///
142  /// The end point is an invalid SlotIndex only if the live range doesn't
143  /// intersect the instruction at all.
144  ///
145  /// The end point may be at or past the end of the instruction's basic
146  /// block. That means the value was live out of the block.
147  SlotIndex endPoint() const {
148  return EndPoint;
149  }
150  };
151 
152  /// This class represents the liveness of a register, stack slot, etc.
153  /// It manages an ordered list of Segment objects.
154  /// The Segments are organized in a static single assignment form: At places
155  /// where a new value is defined or different values reach a CFG join a new
156  /// segment with a new value number is used.
157  class LiveRange {
158  public:
159  /// This represents a simple continuous liveness interval for a value.
160  /// The start point is inclusive, the end point exclusive. These intervals
161  /// are rendered as [start,end).
162  struct Segment {
163  SlotIndex start; // Start point of the interval (inclusive)
164  SlotIndex end; // End point of the interval (exclusive)
165  VNInfo *valno = nullptr; // identifier for the value contained in this
166  // segment.
167 
168  Segment() = default;
169 
171  : start(S), end(E), valno(V) {
172  assert(S < E && "Cannot create empty or backwards segment");
173  }
174 
175  /// Return true if the index is covered by this segment.
176  bool contains(SlotIndex I) const {
177  return start <= I && I < end;
178  }
179 
180  /// Return true if the given interval, [S, E), is covered by this segment.
182  assert((S < E) && "Backwards interval?");
183  return (start <= S && S < end) && (start < E && E <= end);
184  }
185 
186  bool operator<(const Segment &Other) const {
187  return std::tie(start, end) < std::tie(Other.start, Other.end);
188  }
189  bool operator==(const Segment &Other) const {
190  return start == Other.start && end == Other.end;
191  }
192 
193  bool operator!=(const Segment &Other) const {
194  return !(*this == Other);
195  }
196 
197  void dump() const;
198  };
199 
202 
203  Segments segments; // the liveness segments
204  VNInfoList valnos; // value#'s
205 
206  // The segment set is used temporarily to accelerate initial computation
207  // of live ranges of physical registers in computeRegUnitRange.
208  // After that the set is flushed to the segment vector and deleted.
209  using SegmentSet = std::set<Segment>;
210  std::unique_ptr<SegmentSet> segmentSet;
211 
214 
215  iterator begin() { return segments.begin(); }
216  iterator end() { return segments.end(); }
217 
218  const_iterator begin() const { return segments.begin(); }
219  const_iterator end() const { return segments.end(); }
220 
223 
224  vni_iterator vni_begin() { return valnos.begin(); }
225  vni_iterator vni_end() { return valnos.end(); }
226 
227  const_vni_iterator vni_begin() const { return valnos.begin(); }
228  const_vni_iterator vni_end() const { return valnos.end(); }
229 
230  /// Constructs a new LiveRange object.
231  LiveRange(bool UseSegmentSet = false)
232  : segmentSet(UseSegmentSet ? std::make_unique<SegmentSet>()
233  : nullptr) {}
234 
235  /// Constructs a new LiveRange object by copying segments and valnos from
236  /// another LiveRange.
238  assert(Other.segmentSet == nullptr &&
239  "Copying of LiveRanges with active SegmentSets is not supported");
241  }
242 
243  /// Copies values numbers and live segments from \p Other into this range.
245  if (this == &Other)
246  return;
247 
248  assert(Other.segmentSet == nullptr &&
249  "Copying of LiveRanges with active SegmentSets is not supported");
250  // Duplicate valnos.
251  for (const VNInfo *VNI : Other.valnos)
253  // Now we can copy segments and remap their valnos.
254  for (const Segment &S : Other.segments)
255  segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
256  }
257 
258  /// advanceTo - Advance the specified iterator to point to the Segment
259  /// containing the specified position, or end() if the position is past the
260  /// end of the range. If no Segment contains this position, but the
261  /// position is in a hole, this method returns an iterator pointing to the
262  /// Segment immediately after the hole.
264  assert(I != end());
265  if (Pos >= endIndex())
266  return end();
267  while (I->end <= Pos) ++I;
268  return I;
269  }
270 
272  assert(I != end());
273  if (Pos >= endIndex())
274  return end();
275  while (I->end <= Pos) ++I;
276  return I;
277  }
278 
279  /// find - Return an iterator pointing to the first segment that ends after
280  /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
281  /// when searching large ranges.
282  ///
283  /// If Pos is contained in a Segment, that segment is returned.
284  /// If Pos is in a hole, the following Segment is returned.
285  /// If Pos is beyond endIndex, end() is returned.
286  iterator find(SlotIndex Pos);
287 
289  return const_cast<LiveRange*>(this)->find(Pos);
290  }
291 
292  void clear() {
293  valnos.clear();
294  segments.clear();
295  }
296 
297  size_t size() const {
298  return segments.size();
299  }
300 
301  bool hasAtLeastOneValue() const { return !valnos.empty(); }
302 
303  bool containsOneValue() const { return valnos.size() == 1; }
304 
305  unsigned getNumValNums() const { return (unsigned)valnos.size(); }
306 
307  /// getValNumInfo - Returns pointer to the specified val#.
308  ///
309  inline VNInfo *getValNumInfo(unsigned ValNo) {
310  return valnos[ValNo];
311  }
312  inline const VNInfo *getValNumInfo(unsigned ValNo) const {
313  return valnos[ValNo];
314  }
315 
316  /// containsValue - Returns true if VNI belongs to this range.
317  bool containsValue(const VNInfo *VNI) const {
318  return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
319  }
320 
321  /// getNextValue - Create a new value number and return it. MIIdx specifies
322  /// the instruction that defines the value number.
323  VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
324  VNInfo *VNI =
325  new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
326  valnos.push_back(VNI);
327  return VNI;
328  }
329 
330  /// createDeadDef - Make sure the range has a value defined at Def.
331  /// If one already exists, return it. Otherwise allocate a new value and
332  /// add liveness for a dead def.
334 
335  /// Create a def of value @p VNI. Return @p VNI. If there already exists
336  /// a definition at VNI->def, the value defined there must be @p VNI.
337  VNInfo *createDeadDef(VNInfo *VNI);
338 
339  /// Create a copy of the given value. The new value will be identical except
340  /// for the Value number.
342  VNInfo::Allocator &VNInfoAllocator) {
343  VNInfo *VNI =
344  new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
345  valnos.push_back(VNI);
346  return VNI;
347  }
348 
349  /// RenumberValues - Renumber all values in order of appearance and remove
350  /// unused values.
351  void RenumberValues();
352 
353  /// MergeValueNumberInto - This method is called when two value numbers
354  /// are found to be equivalent. This eliminates V1, replacing all
355  /// segments with the V1 value number with the V2 value number. This can
356  /// cause merging of V1/V2 values numbers and compaction of the value space.
358 
359  /// Merge all of the live segments of a specific val# in RHS into this live
360  /// range as the specified value number. The segments in RHS are allowed
361  /// to overlap with segments in the current range, it will replace the
362  /// value numbers of the overlaped live segments with the specified value
363  /// number.
364  void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo);
365 
366  /// MergeValueInAsValue - Merge all of the segments of a specific val#
367  /// in RHS into this live range as the specified value number.
368  /// The segments in RHS are allowed to overlap with segments in the
369  /// current range, but only if the overlapping segments have the
370  /// specified value number.
371  void MergeValueInAsValue(const LiveRange &RHS,
372  const VNInfo *RHSValNo, VNInfo *LHSValNo);
373 
374  bool empty() const { return segments.empty(); }
375 
376  /// beginIndex - Return the lowest numbered slot covered.
378  assert(!empty() && "Call to beginIndex() on empty range.");
379  return segments.front().start;
380  }
381 
382  /// endNumber - return the maximum point of the range of the whole,
383  /// exclusive.
384  SlotIndex endIndex() const {
385  assert(!empty() && "Call to endIndex() on empty range.");
386  return segments.back().end;
387  }
388 
389  bool expiredAt(SlotIndex index) const {
390  return index >= endIndex();
391  }
392 
393  bool liveAt(SlotIndex index) const {
395  return r != end() && r->start <= index;
396  }
397 
398  /// Return the segment that contains the specified index, or null if there
399  /// is none.
402  return I == end() ? nullptr : &*I;
403  }
404 
405  /// Return the live segment that contains the specified index, or null if
406  /// there is none.
409  return I == end() ? nullptr : &*I;
410  }
411 
412  /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
415  return I == end() ? nullptr : I->valno;
416  }
417 
418  /// getVNInfoBefore - Return the VNInfo that is live up to but not
419  /// necessarilly including Idx, or NULL. Use this to find the reaching def
420  /// used by an instruction at this SlotIndex position.
423  return I == end() ? nullptr : I->valno;
424  }
425 
426  /// Return an iterator to the segment that contains the specified index, or
427  /// end() if there is none.
429  iterator I = find(Idx);
430  return I != end() && I->start <= Idx ? I : end();
431  }
432 
434  const_iterator I = find(Idx);
435  return I != end() && I->start <= Idx ? I : end();
436  }
437 
438  /// overlaps - Return true if the intersection of the two live ranges is
439  /// not empty.
440  bool overlaps(const LiveRange &other) const {
441  if (other.empty())
442  return false;
443  return overlapsFrom(other, other.begin());
444  }
445 
446  /// overlaps - Return true if the two ranges have overlapping segments
447  /// that are not coalescable according to CP.
448  ///
449  /// Overlapping segments where one range is defined by a coalescable
450  /// copy are allowed.
451  bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
452  const SlotIndexes&) const;
453 
454  /// overlaps - Return true if the live range overlaps an interval specified
455  /// by [Start, End).
456  bool overlaps(SlotIndex Start, SlotIndex End) const;
457 
458  /// overlapsFrom - Return true if the intersection of the two live ranges
459  /// is not empty. The specified iterator is a hint that we can begin
460  /// scanning the Other range starting at I.
461  bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const;
462 
463  /// Returns true if all segments of the @p Other live range are completely
464  /// covered by this live range.
465  /// Adjacent live ranges do not affect the covering:the liverange
466  /// [1,5](5,10] covers (3,7].
467  bool covers(const LiveRange &Other) const;
468 
469  /// Add the specified Segment to this range, merging segments as
470  /// appropriate. This returns an iterator to the inserted segment (which
471  /// may have grown since it was inserted).
472  iterator addSegment(Segment S);
473 
474  /// Attempt to extend a value defined after @p StartIdx to include @p Use.
475  /// Both @p StartIdx and @p Use should be in the same basic block. In case
476  /// of subranges, an extension could be prevented by an explicit "undef"
477  /// caused by a <def,read-undef> on a non-overlapping lane. The list of
478  /// location of such "undefs" should be provided in @p Undefs.
479  /// The return value is a pair: the first element is VNInfo of the value
480  /// that was extended (possibly nullptr), the second is a boolean value
481  /// indicating whether an "undef" was encountered.
482  /// If this range is live before @p Use in the basic block that starts at
483  /// @p StartIdx, and there is no intervening "undef", extend it to be live
484  /// up to @p Use, and return the pair {value, false}. If there is no
485  /// segment before @p Use and there is no "undef" between @p StartIdx and
486  /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
487  /// return {nullptr, true}.
488  std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
489  SlotIndex StartIdx, SlotIndex Kill);
490 
491  /// Simplified version of the above "extendInBlock", which assumes that
492  /// no register lanes are undefined by <def,read-undef> operands.
493  /// If this range is live before @p Use in the basic block that starts
494  /// at @p StartIdx, extend it to be live up to @p Use, and return the
495  /// value. If there is no segment before @p Use, return nullptr.
497 
498  /// join - Join two live ranges (this, and other) together. This applies
499  /// mappings to the value numbers in the LHS/RHS ranges as specified. If
500  /// the ranges are not joinable, this aborts.
501  void join(LiveRange &Other,
502  const int *ValNoAssignments,
503  const int *RHSValNoAssignments,
504  SmallVectorImpl<VNInfo *> &NewVNInfo);
505 
506  /// True iff this segment is a single segment that lies between the
507  /// specified boundaries, exclusively. Vregs live across a backedge are not
508  /// considered local. The boundaries are expected to lie within an extended
509  /// basic block, so vregs that are not live out should contain no holes.
510  bool isLocal(SlotIndex Start, SlotIndex End) const {
511  return beginIndex() > Start.getBaseIndex() &&
512  endIndex() < End.getBoundaryIndex();
513  }
514 
515  /// Remove the specified segment from this range. Note that the segment
516  /// must be a single Segment in its entirety.
517  void removeSegment(SlotIndex Start, SlotIndex End,
518  bool RemoveDeadValNo = false);
519 
520  void removeSegment(Segment S, bool RemoveDeadValNo = false) {
521  removeSegment(S.start, S.end, RemoveDeadValNo);
522  }
523 
524  /// Remove segment pointed to by iterator @p I from this range. This does
525  /// not remove dead value numbers.
527  return segments.erase(I);
528  }
529 
530  /// Query Liveness at Idx.
531  /// The sub-instruction slot of Idx doesn't matter, only the instruction
532  /// it refers to is considered.
534  // Find the segment that enters the instruction.
536  const_iterator E = end();
537  if (I == E)
538  return LiveQueryResult(nullptr, nullptr, SlotIndex(), false);
539 
540  // Is this an instruction live-in segment?
541  // If Idx is the start index of a basic block, include live-in segments
542  // that start at Idx.getBaseIndex().
543  VNInfo *EarlyVal = nullptr;
544  VNInfo *LateVal = nullptr;
545  SlotIndex EndPoint;
546  bool Kill = false;
547  if (I->start <= Idx.getBaseIndex()) {
548  EarlyVal = I->valno;
549  EndPoint = I->end;
550  // Move to the potentially live-out segment.
551  if (SlotIndex::isSameInstr(Idx, I->end)) {
552  Kill = true;
553  if (++I == E)
554  return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
555  }
556  // Special case: A PHIDef value can have its def in the middle of a
557  // segment if the value happens to be live out of the layout
558  // predecessor.
559  // Such a value is not live-in.
560  if (EarlyVal->def == Idx.getBaseIndex())
561  EarlyVal = nullptr;
562  }
563  // I now points to the segment that may be live-through, or defined by
564  // this instr. Ignore segments starting after the current instr.
565  if (!SlotIndex::isEarlierInstr(Idx, I->start)) {
566  LateVal = I->valno;
567  EndPoint = I->end;
568  }
569  return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
570  }
571 
572  /// removeValNo - Remove all the segments defined by the specified value#.
573  /// Also remove the value# from value# list.
574  void removeValNo(VNInfo *ValNo);
575 
576  /// Returns true if the live range is zero length, i.e. no live segments
577  /// span instructions. It doesn't pay to spill such a range.
578  bool isZeroLength(SlotIndexes *Indexes) const {
579  for (const Segment &S : segments)
580  if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
581  S.end.getBaseIndex())
582  return false;
583  return true;
584  }
585 
586  // Returns true if any segment in the live range contains any of the
587  // provided slot indexes. Slots which occur in holes between
588  // segments will not cause the function to return true.
589  bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
590 
591  bool operator<(const LiveRange& other) const {
592  const SlotIndex &thisIndex = beginIndex();
593  const SlotIndex &otherIndex = other.beginIndex();
594  return thisIndex < otherIndex;
595  }
596 
597  /// Returns true if there is an explicit "undef" between @p Begin
598  /// @p End.
600  SlotIndex End) const {
601  return llvm::any_of(Undefs, [Begin, End](SlotIndex Idx) -> bool {
602  return Begin <= Idx && Idx < End;
603  });
604  }
605 
606  /// Flush segment set into the regular segment vector.
607  /// The method is to be called after the live range
608  /// has been created, if use of the segment set was
609  /// activated in the constructor of the live range.
610  void flushSegmentSet();
611 
612  /// Stores indexes from the input index sequence R at which this LiveRange
613  /// is live to the output O iterator.
614  /// R is a range of _ascending sorted_ _random_ access iterators
615  /// to the input indexes. Indexes stored at O are ascending sorted so it
616  /// can be used directly in the subsequent search (for example for
617  /// subranges). Returns true if found at least one index.
618  template <typename Range, typename OutputIt>
619  bool findIndexesLiveAt(Range &&R, OutputIt O) const {
621  auto Idx = R.begin(), EndIdx = R.end();
622  auto Seg = segments.begin(), EndSeg = segments.end();
623  bool Found = false;
624  while (Idx != EndIdx && Seg != EndSeg) {
625  // if the Seg is lower find first segment that is above Idx using binary
626  // search
627  if (Seg->end <= *Idx) {
628  Seg = std::upper_bound(
629  ++Seg, EndSeg, *Idx,
630  [=](std::remove_reference_t<decltype(*Idx)> V,
631  const std::remove_reference_t<decltype(*Seg)> &S) {
632  return V < S.end;
633  });
634  if (Seg == EndSeg)
635  break;
636  }
637  auto NotLessStart = std::lower_bound(Idx, EndIdx, Seg->start);
638  if (NotLessStart == EndIdx)
639  break;
640  auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end);
641  if (NotLessEnd != NotLessStart) {
642  Found = true;
643  O = std::copy(NotLessStart, NotLessEnd, O);
644  }
645  Idx = NotLessEnd;
646  ++Seg;
647  }
648  return Found;
649  }
650 
651  void print(raw_ostream &OS) const;
652  void dump() const;
653 
654  /// Walk the range and assert if any invariants fail to hold.
655  ///
656  /// Note that this is a no-op when asserts are disabled.
657 #ifdef NDEBUG
658  void verify() const {}
659 #else
660  void verify() const;
661 #endif
662 
663  protected:
664  /// Append a segment to the list of segments.
665  void append(const LiveRange::Segment S);
666 
667  private:
668  friend class LiveRangeUpdater;
669  void addSegmentToSet(Segment S);
670  void markValNoForDeletion(VNInfo *V);
671  };
672 
673  inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
674  LR.print(OS);
675  return OS;
676  }
677 
678  /// LiveInterval - This class represents the liveness of a register,
679  /// or stack slot.
680  class LiveInterval : public LiveRange {
681  public:
682  using super = LiveRange;
683 
684  /// A live range for subregisters. The LaneMask specifies which parts of the
685  /// super register are covered by the interval.
686  /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
687  class SubRange : public LiveRange {
688  public:
689  SubRange *Next = nullptr;
691 
692  /// Constructs a new SubRange object.
694 
695  /// Constructs a new SubRange object by copying liveness from @p Other.
699 
700  void print(raw_ostream &OS) const;
701  void dump() const;
702  };
703 
704  private:
705  SubRange *SubRanges = nullptr; ///< Single linked list of subregister live
706  /// ranges.
707  const Register Reg; // the register or stack slot of this interval.
708  float Weight = 0.0; // weight of this interval
709 
710  public:
711  Register reg() const { return Reg; }
712  float weight() const { return Weight; }
713  void incrementWeight(float Inc) { Weight += Inc; }
714  void setWeight(float Value) { Weight = Value; }
715 
716  LiveInterval(unsigned Reg, float Weight) : Reg(Reg), Weight(Weight) {}
717 
719  clearSubRanges();
720  }
721 
722  template<typename T>
724  T *P;
725 
726  public:
728 
730  P = P->Next;
731  return *this;
732  }
734  SingleLinkedListIterator res = *this;
735  ++*this;
736  return res;
737  }
738  bool operator!=(const SingleLinkedListIterator<T> &Other) const {
739  return P != Other.operator->();
740  }
741  bool operator==(const SingleLinkedListIterator<T> &Other) const {
742  return P == Other.operator->();
743  }
744  T &operator*() const {
745  return *P;
746  }
747  T *operator->() const {
748  return P;
749  }
750  };
751 
754 
756  return subrange_iterator(SubRanges);
757  }
759  return subrange_iterator(nullptr);
760  }
761 
763  return const_subrange_iterator(SubRanges);
764  }
766  return const_subrange_iterator(nullptr);
767  }
768 
771  }
772 
775  }
776 
777  /// Creates a new empty subregister live range. The range is added at the
778  /// beginning of the subrange list; subrange iterators stay valid.
780  LaneBitmask LaneMask) {
781  SubRange *Range = new (Allocator) SubRange(LaneMask);
782  appendSubRange(Range);
783  return Range;
784  }
785 
786  /// Like createSubRange() but the new range is filled with a copy of the
787  /// liveness information in @p CopyFrom.
789  LaneBitmask LaneMask,
790  const LiveRange &CopyFrom) {
791  SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
792  appendSubRange(Range);
793  return Range;
794  }
795 
796  /// Returns true if subregister liveness information is available.
797  bool hasSubRanges() const {
798  return SubRanges != nullptr;
799  }
800 
801  /// Removes all subregister liveness information.
802  void clearSubRanges();
803 
804  /// Removes all subranges without any segments (subranges without segments
805  /// are not considered valid and should only exist temporarily).
806  void removeEmptySubRanges();
807 
808  /// getSize - Returns the sum of sizes of all the LiveRange's.
809  ///
810  unsigned getSize() const;
811 
812  /// isSpillable - Can this interval be spilled?
813  bool isSpillable() const { return Weight != huge_valf; }
814 
815  /// markNotSpillable - Mark interval as not spillable
816  void markNotSpillable() { Weight = huge_valf; }
817 
818  /// For a given lane mask @p LaneMask, compute indexes at which the
819  /// lane is marked undefined by subregister <def,read-undef> definitions.
821  LaneBitmask LaneMask,
822  const MachineRegisterInfo &MRI,
823  const SlotIndexes &Indexes) const;
824 
825  /// Refines the subranges to support \p LaneMask. This may only be called
826  /// for LI.hasSubrange()==true. Subregister ranges are split or created
827  /// until \p LaneMask can be matched exactly. \p Mod is executed on the
828  /// matching subranges.
829  ///
830  /// Example:
831  /// Given an interval with subranges with lanemasks L0F00, L00F0 and
832  /// L000F, refining for mask L0018. Will split the L00F0 lane into
833  /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
834  /// function will be applied to the L0010 and L0008 subranges.
835  ///
836  /// \p Indexes and \p TRI are required to clean up the VNIs that
837  /// don't define the related lane masks after they get shrunk. E.g.,
838  /// when L000F gets split into L0007 and L0008 maybe only a subset
839  /// of the VNIs that defined L000F defines L0007.
840  ///
841  /// The clean up of the VNIs need to look at the actual instructions
842  /// to decide what is or is not live at a definition point. If the
843  /// update of the subranges occurs while the IR does not reflect these
844  /// changes, \p ComposeSubRegIdx can be used to specify how the
845  /// definition are going to be rewritten.
846  /// E.g., let say we want to merge:
847  /// V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32>
848  /// We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32>
849  /// overlap, i.e., by choosing a class where we can find "offset + 1 == 3".
850  /// Put differently we align V2's sub3 with V1's sub1:
851  /// V2: sub0 sub1 sub2 sub3
852  /// V1: <offset> sub0 sub1
853  ///
854  /// This offset will look like a composed subregidx in the the class:
855  /// V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32>
856  /// => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32>
857  ///
858  /// Now if we didn't rewrite the uses and def of V1, all the checks for V1
859  /// need to account for this offset.
860  /// This happens during coalescing where we update the live-ranges while
861  /// still having the old IR around because updating the IR on-the-fly
862  /// would actually clobber some information on how the live-ranges that
863  /// are being updated look like.
865  std::function<void(LiveInterval::SubRange &)> Apply,
866  const SlotIndexes &Indexes,
867  const TargetRegisterInfo &TRI,
868  unsigned ComposeSubRegIdx = 0);
869 
870  bool operator<(const LiveInterval& other) const {
871  const SlotIndex &thisIndex = beginIndex();
872  const SlotIndex &otherIndex = other.beginIndex();
873  return std::tie(thisIndex, Reg) < std::tie(otherIndex, other.Reg);
874  }
875 
876  void print(raw_ostream &OS) const;
877  void dump() const;
878 
879  /// Walks the interval and assert if any invariants fail to hold.
880  ///
881  /// Note that this is a no-op when asserts are disabled.
882 #ifdef NDEBUG
883  void verify(const MachineRegisterInfo *MRI = nullptr) const {}
884 #else
885  void verify(const MachineRegisterInfo *MRI = nullptr) const;
886 #endif
887 
888  private:
889  /// Appends @p Range to SubRanges list.
890  void appendSubRange(SubRange *Range) {
891  Range->Next = SubRanges;
892  SubRanges = Range;
893  }
894 
895  /// Free memory held by SubRange.
896  void freeSubRange(SubRange *S);
897  };
898 
900  const LiveInterval::SubRange &SR) {
901  SR.print(OS);
902  return OS;
903  }
904 
905  inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
906  LI.print(OS);
907  return OS;
908  }
909 
910  raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);
911 
912  inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
913  return V < S.start;
914  }
915 
916  inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
917  return S.start < V;
918  }
919 
920  /// Helper class for performant LiveRange bulk updates.
921  ///
922  /// Calling LiveRange::addSegment() repeatedly can be expensive on large
923  /// live ranges because segments after the insertion point may need to be
924  /// shifted. The LiveRangeUpdater class can defer the shifting when adding
925  /// many segments in order.
926  ///
927  /// The LiveRange will be in an invalid state until flush() is called.
929  LiveRange *LR;
930  SlotIndex LastStart;
931  LiveRange::iterator WriteI;
932  LiveRange::iterator ReadI;
934  void mergeSpills();
935 
936  public:
937  /// Create a LiveRangeUpdater for adding segments to LR.
938  /// LR will temporarily be in an invalid state until flush() is called.
939  LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {}
940 
942 
943  /// Add a segment to LR and coalesce when possible, just like
944  /// LR.addSegment(). Segments should be added in increasing start order for
945  /// best performance.
946  void add(LiveRange::Segment);
947 
948  void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
949  add(LiveRange::Segment(Start, End, VNI));
950  }
951 
952  /// Return true if the LR is currently in an invalid state, and flush()
953  /// needs to be called.
954  bool isDirty() const { return LastStart.isValid(); }
955 
956  /// Flush the updater state to LR so it is valid and contains all added
957  /// segments.
958  void flush();
959 
960  /// Select a different destination live range.
962  if (LR != lr && isDirty())
963  flush();
964  LR = lr;
965  }
966 
967  /// Get the current destination live range.
968  LiveRange *getDest() const { return LR; }
969 
970  void dump() const;
971  void print(raw_ostream&) const;
972  };
973 
975  X.print(OS);
976  return OS;
977  }
978 
979  /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
980  /// LiveInterval into equivalence clases of connected components. A
981  /// LiveInterval that has multiple connected components can be broken into
982  /// multiple LiveIntervals.
983  ///
984  /// Given a LiveInterval that may have multiple connected components, run:
985  ///
986  /// unsigned numComps = ConEQ.Classify(LI);
987  /// if (numComps > 1) {
988  /// // allocate numComps-1 new LiveIntervals into LIS[1..]
989  /// ConEQ.Distribute(LIS);
990  /// }
991 
993  LiveIntervals &LIS;
994  IntEqClasses EqClass;
995 
996  public:
997  explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
998 
999  /// Classify the values in \p LR into connected components.
1000  /// Returns the number of connected components.
1001  unsigned Classify(const LiveRange &LR);
1002 
1003  /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
1004  /// the equivalence class assigned the VNI.
1005  unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
1006 
1007  /// Distribute values in \p LI into a separate LiveIntervals
1008  /// for each connected component. LIV must have an empty LiveInterval for
1009  /// each additional connected component. The first connected component is
1010  /// left in \p LI.
1011  void Distribute(LiveInterval &LI, LiveInterval *LIV[],
1013  };
1014 
1015 } // end namespace llvm
1016 
1017 #endif // LLVM_CODEGEN_LIVEINTERVAL_H
llvm::LiveRange::find
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
Definition: LiveInterval.cpp:350
llvm::LaneBitmask
Definition: LaneBitmask.h:39
i
i
Definition: README.txt:29
llvm::LiveQueryResult::valueDefined
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Definition: LiveInterval.h:135
llvm::LiveInterval::computeSubRangeUndefs
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
Definition: LiveInterval.cpp:976
llvm::LiveRange::join
void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
Definition: LiveInterval.cpp:641
llvm::LiveRange::FindSegmentContaining
const_iterator FindSegmentContaining(SlotIndex Idx) const
Definition: LiveInterval.h:433
MathExtras.h
llvm
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::LiveRange::Segment::containsInterval
bool containsInterval(SlotIndex S, SlotIndex E) const
Return true if the given interval, [S, E), is covered by this segment.
Definition: LiveInterval.h:181
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1605
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::LiveRange::flushSegmentSet
void flushSegmentSet()
Flush segment set into the regular segment vector.
Definition: LiveInterval.cpp:804
llvm::ConnectedVNInfoEqClasses::Distribute
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
Definition: LiveInterval.cpp:1360
llvm::LiveInterval::SingleLinkedListIterator::operator++
SingleLinkedListIterator< T > & operator++()
Definition: LiveInterval.h:729
llvm::LiveRange::isZeroLength
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:578
llvm::SlotIndex::isValid
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:151
llvm::LiveInterval::createSubRange
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
Definition: LiveInterval.h:779
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1592
llvm::LiveRange::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1010
llvm::LiveInterval::isSpillable
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:813
llvm::LiveQueryResult::valueOutOrDead
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
Definition: LiveInterval.h:129
llvm::SmallVector< Segment, 2 >
llvm::LiveInterval::weight
float weight() const
Definition: LiveInterval.h:712
llvm::LiveRange::advanceTo
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
Definition: LiveInterval.h:263
llvm::LiveRange::advanceTo
const_iterator advanceTo(const_iterator I, SlotIndex Pos) const
Definition: LiveInterval.h:271
llvm::LiveQueryResult::isDeadDef
bool isDeadDef() const
Return true if this instruction has a dead def.
Definition: LiveInterval.h:117
llvm::LiveInterval::SingleLinkedListIterator::operator++
SingleLinkedListIterator< T > operator++(int)
Definition: LiveInterval.h:733
Allocator.h
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
llvm::huge_valf
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition: MathExtras.cpp:28
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
IntEqClasses.h
llvm::LiveRange::Segment::start
SlotIndex start
Definition: LiveInterval.h:163
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:369
llvm::LiveRange::Segment::operator<
bool operator<(const Segment &Other) const
Definition: LiveInterval.h:186
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::LiveRange::vni_begin
vni_iterator vni_begin()
Definition: LiveInterval.h:224
STLExtras.h
llvm::LiveRange::findIndexesLiveAt
bool findIndexesLiveAt(Range &&R, OutputIt O) const
Stores indexes from the input index sequence R at which this LiveRange is live to the output O iterat...
Definition: LiveInterval.h:619
llvm::LiveInterval::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1045
llvm::LiveQueryResult
Result of a LiveRange query.
Definition: LiveInterval.h:90
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::LiveRange::assign
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
Definition: LiveInterval.h:244
llvm::LiveRange::createValueCopy
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
Definition: LiveInterval.h:341
llvm::LiveRange::extendInBlock
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
Definition: LiveInterval.cpp:564
llvm::LiveRange::removeSegment
iterator removeSegment(iterator I)
Remove segment pointed to by iterator I from this range.
Definition: LiveInterval.h:526
llvm::LiveRange::isLiveAtIndexes
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
Definition: LiveInterval.cpp:814
llvm::LiveRange::beginIndex
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:377
llvm::LiveInterval::SubRange::LaneMask
LaneBitmask LaneMask
Definition: LiveInterval.h:690
llvm::LiveInterval::SubRange::SubRange
SubRange(LaneBitmask LaneMask)
Constructs a new SubRange object.
Definition: LiveInterval.h:693
llvm::LiveRange::getValNumInfo
const VNInfo * getValNumInfo(unsigned ValNo) const
Definition: LiveInterval.h:312
llvm::LiveRangeUpdater::add
void add(SlotIndex Start, SlotIndex End, VNInfo *VNI)
Definition: LiveInterval.h:948
llvm::LiveRange::Segment::dump
void dump() const
Definition: LiveInterval.cpp:1005
llvm::LiveRange::liveAt
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:393
llvm::LiveRange::SegmentSet
std::set< Segment > SegmentSet
Definition: LiveInterval.h:209
llvm::LiveInterval::subrange_begin
subrange_iterator subrange_begin()
Definition: LiveInterval.h:755
llvm::LiveRange::begin
iterator begin()
Definition: LiveInterval.h:215
llvm::LiveRange::covers
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
Definition: LiveInterval.cpp:494
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveInterval::subrange_end
const_subrange_iterator subrange_end() const
Definition: LiveInterval.h:765
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::LiveInterval::SubRange::dump
void dump() const
Definition: LiveInterval.cpp:1059
llvm::LiveInterval::subranges
iterator_range< const_subrange_iterator > subranges() const
Definition: LiveInterval.h:773
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::LiveInterval::SingleLinkedListIterator::operator!=
bool operator!=(const SingleLinkedListIterator< T > &Other) const
Definition: LiveInterval.h:738
llvm::LiveInterval::getSize
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
Definition: LiveInterval.cpp:969
llvm::LiveRange::const_iterator
Segments::const_iterator const_iterator
Definition: LiveInterval.h:213
llvm::LiveInterval::dump
void dump() const
Definition: LiveInterval.cpp:1063
llvm::LiveRangeUpdater
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:928
llvm::ConnectedVNInfoEqClasses::ConnectedVNInfoEqClasses
ConnectedVNInfoEqClasses(LiveIntervals &lis)
Definition: LiveInterval.h:997
llvm::LiveInterval::clearSubRanges
void clearSubRanges()
Removes all subregister liveness information.
Definition: LiveInterval.cpp:872
llvm::LiveRange::valnos
VNInfoList valnos
Definition: LiveInterval.h:204
llvm::LiveRangeUpdater::isDirty
bool isDirty() const
Return true if the LR is currently in an invalid state, and flush() needs to be called.
Definition: LiveInterval.h:954
llvm::LiveInterval::const_subrange_iterator
SingleLinkedListIterator< const SubRange > const_subrange_iterator
Definition: LiveInterval.h:753
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::LiveRangeUpdater::~LiveRangeUpdater
~LiveRangeUpdater()
Definition: LiveInterval.h:941
llvm::LiveRange::size
size_t size() const
Definition: LiveInterval.h:297
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::LiveInterval::SingleLinkedListIterator::operator==
bool operator==(const SingleLinkedListIterator< T > &Other) const
Definition: LiveInterval.h:741
lr
Common register allocation spilling lr str lr
Definition: README.txt:6
llvm::LiveRange::overlapsFrom
bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const
overlapsFrom - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.cpp:404
llvm::LiveRangeUpdater::setDest
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:961
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::VNInfo::VNInfo
VNInfo(unsigned i, const VNInfo &orig)
VNInfo constructor, copies values from orig, except for the value number.
Definition: LiveInterval.h:67
llvm::LiveRange::end
const_iterator end() const
Definition: LiveInterval.h:219
llvm::LiveQueryResult::valueIn
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::LiveQueryResult::endPoint
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
Definition: LiveInterval.h:147
llvm::LiveInterval::subrange_end
subrange_iterator subrange_end()
Definition: LiveInterval.h:758
llvm::LiveQueryResult::valueOut
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
Definition: LiveInterval.h:123
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::LiveRange::append
void append(const LiveRange::Segment S)
Append a segment to the list of segments.
Definition: LiveInterval.cpp:558
llvm::LiveInterval::subrange_begin
const_subrange_iterator subrange_begin() const
Definition: LiveInterval.h:762
llvm::LiveQueryResult::LiveQueryResult
LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, bool Kill)
Definition: LiveInterval.h:97
llvm::LiveRange::Segment::contains
bool contains(SlotIndex I) const
Return true if the index is covered by this segment.
Definition: LiveInterval.h:176
llvm::LiveInterval::SubRange::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1040
llvm::LiveRange::dump
void dump() const
Definition: LiveInterval.cpp:1055
llvm::SlotIndex::getBaseIndex
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:241
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
llvm::LiveRange::RenumberValues
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
Definition: LiveInterval.cpp:531
llvm::LiveInterval::operator<
bool operator<(const LiveInterval &other) const
Definition: LiveInterval.h:870
llvm::LiveRangeUpdater::getDest
LiveRange * getDest() const
Get the current destination live range.
Definition: LiveInterval.h:968
llvm::LiveRange::getVNInfoBefore
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:421
llvm::LiveInterval::removeEmptySubRanges
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Definition: LiveInterval.cpp:853
llvm::LiveInterval::refineSubRanges
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
Definition: LiveInterval.cpp:930
llvm::LiveRangeUpdater::print
void print(raw_ostream &) const
Definition: LiveInterval.cpp:1139
llvm::LiveRange::hasAtLeastOneValue
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:301
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::LiveInterval::incrementWeight
void incrementWeight(float Inc)
Definition: LiveInterval.h:713
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::VNInfo::id
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::LiveRange::getNumValNums
unsigned getNumValNums() const
Definition: LiveInterval.h:305
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
llvm::LiveRange::operator<
bool operator<(const LiveRange &other) const
Definition: LiveInterval.h:591
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LiveRangeUpdater::dump
void dump() const
Definition: LiveInterval.cpp:1162
llvm::LiveRange::expiredAt
bool expiredAt(SlotIndex index) const
Definition: LiveInterval.h:389
llvm::LiveRange::overlaps
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:440
llvm::LiveRange::LiveRange
LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new LiveRange object by copying segments and valnos from another LiveRange.
Definition: LiveInterval.h:237
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::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:323
ArrayRef.h
llvm::LiveRange::isLocal
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries,...
Definition: LiveInterval.h:510
llvm::LiveRange::Query
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:533
llvm::LiveInterval::LiveInterval
LiveInterval(unsigned Reg, float Weight)
Definition: LiveInterval.h:716
llvm::LiveRange::containsValue
bool containsValue(const VNInfo *VNI) const
containsValue - Returns true if VNI belongs to this range.
Definition: LiveInterval.h:317
llvm::SmallVectorImpl< Segment >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ConnectedVNInfoEqClasses::Classify
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Definition: LiveInterval.cpp:1318
llvm::LiveRange::getSegmentContaining
Segment * getSegmentContaining(SlotIndex Idx)
Return the live segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:407
llvm::ConnectedVNInfoEqClasses::getEqClass
unsigned getEqClass(const VNInfo *VNI) const
getEqClass - Classify creates equivalence classes numbered 0..N.
Definition: LiveInterval.h:1005
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::LiveRange::containsOneValue
bool containsOneValue() const
Definition: LiveInterval.h:303
llvm::LiveRange::MergeValueNumberInto
VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
Definition: LiveInterval.cpp:749
llvm::LiveRange::FindSegmentContaining
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
Definition: LiveInterval.h:428
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1489
llvm::LiveRangeUpdater::flush
void flush()
Flush the updater state to LR so it is valid and contains all added segments.
Definition: LiveInterval.cpp:1286
llvm::LiveRange::Segment::Segment
Segment()=default
llvm::LiveInterval::SingleLinkedListIterator::operator->
T * operator->() const
Definition: LiveInterval.h:747
const_iterator
llvm::LiveRange::removeSegment
void removeSegment(Segment S, bool RemoveDeadValNo=false)
Definition: LiveInterval.h:520
llvm::LiveRange::Segment::operator==
bool operator==(const Segment &Other) const
Definition: LiveInterval.h:189
llvm::CoalescerPair
A helper class for register coalescers.
Definition: RegisterCoalescer.h:28
llvm::LiveInterval::SubRange::SubRange
SubRange(LaneBitmask LaneMask, const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new SubRange object by copying liveness from Other.
Definition: LiveInterval.h:696
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LiveRange::Segment::end
SlotIndex end
Definition: LiveInterval.h:164
llvm::LiveInterval::setWeight
void setWeight(float Value)
Definition: LiveInterval.h:714
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:687
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::LiveRange::endIndex
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:384
llvm::LiveRange::begin
const_iterator begin() const
Definition: LiveInterval.h:218
llvm::VNInfo::isPHIDef
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:78
llvm::HexagonISD::CP
@ CP
Definition: HexagonISelLowering.h:53
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::LiveRange::MergeSegmentsInAsValue
void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo)
Merge all of the live segments of a specific val# in RHS into this live range as the specified value ...
Definition: LiveInterval.cpp:724
llvm::LiveRange::iterator
Segments::iterator iterator
Definition: LiveInterval.h:212
std
Definition: BitVector.h:838
llvm::LiveInterval::SingleLinkedListIterator
Definition: LiveInterval.h:723
llvm::SlotIndex::getPrevSlot
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:289
llvm::LiveRange::vni_end
const_vni_iterator vni_end() const
Definition: LiveInterval.h:228
llvm::LiveInterval::SubRange::Next
SubRange * Next
Definition: LiveInterval.h:689
llvm::LiveRangeUpdater::add
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
Definition: LiveInterval.cpp:1179
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::is_sorted
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1553
llvm::LiveRange::getValNumInfo
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
Definition: LiveInterval.h:309
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveRange::getVNInfoAt
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:413
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::LiveRange::Segment::operator!=
bool operator!=(const Segment &Other) const
Definition: LiveInterval.h:193
llvm::VNInfo::copyFrom
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
Definition: LiveInterval.h:70
llvm::LiveRange::verify
void verify() const
Walk the range and assert if any invariants fail to hold.
Definition: LiveInterval.cpp:1069
llvm::LiveRangeUpdater::LiveRangeUpdater
LiveRangeUpdater(LiveRange *lr=nullptr)
Create a LiveRangeUpdater for adding segments to LR.
Definition: LiveInterval.h:939
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:583
llvm::SlotIndexes::getNextNonNullIndex
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:409
llvm::LiveInterval::markNotSpillable
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:816
llvm::LiveRange::Segment::Segment
Segment(SlotIndex S, SlotIndex E, VNInfo *V)
Definition: LiveInterval.h:170
llvm::LiveRange::MergeValueInAsValue
void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)
MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the...
Definition: LiveInterval.cpp:736
llvm::LiveRange::Segment::valno
VNInfo * valno
Definition: LiveInterval.h:165
llvm::SlotIndex::isBlock
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
Definition: SlotIndexes.h:226
SmallVector.h
llvm::LiveInterval::SingleLinkedListIterator::operator*
T & operator*() const
Definition: LiveInterval.h:744
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::SmallVectorImpl< Segment >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:562
P
#define P(N)
llvm::LiveRange::segments
Segments segments
Definition: LiveInterval.h:203
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:711
llvm::LiveRange::getSegmentContaining
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:400
llvm::LiveInterval::hasSubRanges
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:797
LaneBitmask.h
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::LiveRange::clear
void clear()
Definition: LiveInterval.h:292
llvm::LiveRange::LiveRange
LiveRange(bool UseSegmentSet=false)
Constructs a new LiveRange object.
Definition: LiveInterval.h:231
llvm::SmallVectorImpl< VNInfo * >
llvm::LiveRange::vni_begin
const_vni_iterator vni_begin() const
Definition: LiveInterval.h:227
Register.h
llvm::LiveRange::vni_iterator
VNInfoList::iterator vni_iterator
Definition: LiveInterval.h:221
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
llvm::IntEqClasses
Definition: IntEqClasses.h:27
llvm::LiveRange::removeValNo
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
Definition: LiveInterval.cpp:632
SlotIndexes.h
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418
llvm::LiveRange::vni_end
vni_iterator vni_end()
Definition: LiveInterval.h:225
llvm::LiveRange::const_vni_iterator
VNInfoList::const_iterator const_vni_iterator
Definition: LiveInterval.h:222
llvm::SlotIndex::isDead
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:236
llvm::LiveInterval::subrange_iterator
SingleLinkedListIterator< SubRange > subrange_iterator
Definition: LiveInterval.h:752
llvm::LiveInterval::~LiveInterval
~LiveInterval()
Definition: LiveInterval.h:718
llvm::LiveRange::segmentSet
std::unique_ptr< SegmentSet > segmentSet
Definition: LiveInterval.h:210
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::LiveRange::isUndefIn
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
Definition: LiveInterval.h:599
llvm::ConnectedVNInfoEqClasses
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:992
llvm::LiveRange::find
const_iterator find(SlotIndex Pos) const
Definition: LiveInterval.h:288
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::LiveQueryResult::isKill
bool isKill() const
Return true if the live-in value is killed by this instruction.
Definition: LiveInterval.h:112
llvm::LiveInterval::createSubRangeFrom
SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...
Definition: LiveInterval.h:788
llvm::VNInfo::VNInfo
VNInfo(unsigned i, SlotIndex d)
VNInfo constructor.
Definition: LiveInterval.h:64
llvm::LiveRange::end
iterator end()
Definition: LiveInterval.h:216
llvm::VNInfo::markUnused
void markUnused()
Mark this value as unused.
Definition: LiveInterval.h:84
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1168
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:769