LLVM  6.0.0svn
LiveInterval.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LiveRange and LiveInterval classes. Given some
11 // numbering of each the machine instructions an interval [i, j) is said to be a
12 // live range for register v if there is no instruction with number j' >= j
13 // such that v is live at j' and there is no instruction with number i' < i such
14 // that v is live at i'. In this implementation ranges can have holes,
15 // i.e. a range might look like [1,20), [50,65), [1000,1001). Each
16 // individual segment is represented as an instance of LiveRange::Segment,
17 // and the whole range is represented as an instance of LiveRange.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
22 #define LLVM_CODEGEN_LIVEINTERVAL_H
23 
24 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/ADT/IntEqClasses.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/SmallVector.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  void dump() const;
194  };
195 
198 
199  Segments segments; // the liveness segments
200  VNInfoList valnos; // value#'s
201 
202  // The segment set is used temporarily to accelerate initial computation
203  // of live ranges of physical registers in computeRegUnitRange.
204  // After that the set is flushed to the segment vector and deleted.
205  using SegmentSet = std::set<Segment>;
206  std::unique_ptr<SegmentSet> segmentSet;
207 
209  using const_iterator = Segments::const_iterator;
210 
211  iterator begin() { return segments.begin(); }
212  iterator end() { return segments.end(); }
213 
214  const_iterator begin() const { return segments.begin(); }
215  const_iterator end() const { return segments.end(); }
216 
219 
220  vni_iterator vni_begin() { return valnos.begin(); }
221  vni_iterator vni_end() { return valnos.end(); }
222 
223  const_vni_iterator vni_begin() const { return valnos.begin(); }
224  const_vni_iterator vni_end() const { return valnos.end(); }
225 
226  /// Constructs a new LiveRange object.
227  LiveRange(bool UseSegmentSet = false)
228  : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>()
229  : nullptr) {}
230 
231  /// Constructs a new LiveRange object by copying segments and valnos from
232  /// another LiveRange.
234  assert(Other.segmentSet == nullptr &&
235  "Copying of LiveRanges with active SegmentSets is not supported");
236  assign(Other, Allocator);
237  }
238 
239  /// Copies values numbers and live segments from \p Other into this range.
241  if (this == &Other)
242  return;
243 
244  assert(Other.segmentSet == nullptr &&
245  "Copying of LiveRanges with active SegmentSets is not supported");
246  // Duplicate valnos.
247  for (const VNInfo *VNI : Other.valnos)
248  createValueCopy(VNI, Allocator);
249  // Now we can copy segments and remap their valnos.
250  for (const Segment &S : Other.segments)
251  segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
252  }
253 
254  /// advanceTo - Advance the specified iterator to point to the Segment
255  /// containing the specified position, or end() if the position is past the
256  /// end of the range. If no Segment contains this position, but the
257  /// position is in a hole, this method returns an iterator pointing to the
258  /// Segment immediately after the hole.
260  assert(I != end());
261  if (Pos >= endIndex())
262  return end();
263  while (I->end <= Pos) ++I;
264  return I;
265  }
266 
268  assert(I != end());
269  if (Pos >= endIndex())
270  return end();
271  while (I->end <= Pos) ++I;
272  return I;
273  }
274 
275  /// find - Return an iterator pointing to the first segment that ends after
276  /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
277  /// when searching large ranges.
278  ///
279  /// If Pos is contained in a Segment, that segment is returned.
280  /// If Pos is in a hole, the following Segment is returned.
281  /// If Pos is beyond endIndex, end() is returned.
282  iterator find(SlotIndex Pos);
283 
285  return const_cast<LiveRange*>(this)->find(Pos);
286  }
287 
288  void clear() {
289  valnos.clear();
290  segments.clear();
291  }
292 
293  size_t size() const {
294  return segments.size();
295  }
296 
297  bool hasAtLeastOneValue() const { return !valnos.empty(); }
298 
299  bool containsOneValue() const { return valnos.size() == 1; }
300 
301  unsigned getNumValNums() const { return (unsigned)valnos.size(); }
302 
303  /// getValNumInfo - Returns pointer to the specified val#.
304  ///
305  inline VNInfo *getValNumInfo(unsigned ValNo) {
306  return valnos[ValNo];
307  }
308  inline const VNInfo *getValNumInfo(unsigned ValNo) const {
309  return valnos[ValNo];
310  }
311 
312  /// containsValue - Returns true if VNI belongs to this range.
313  bool containsValue(const VNInfo *VNI) const {
314  return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
315  }
316 
317  /// getNextValue - Create a new value number and return it. MIIdx specifies
318  /// the instruction that defines the value number.
320  VNInfo *VNI =
321  new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
322  valnos.push_back(VNI);
323  return VNI;
324  }
325 
326  /// createDeadDef - Make sure the range has a value defined at Def.
327  /// If one already exists, return it. Otherwise allocate a new value and
328  /// add liveness for a dead def.
329  VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator);
330 
331  /// Create a def of value @p VNI. Return @p VNI. If there already exists
332  /// a definition at VNI->def, the value defined there must be @p VNI.
333  VNInfo *createDeadDef(VNInfo *VNI);
334 
335  /// Create a copy of the given value. The new value will be identical except
336  /// for the Value number.
338  VNInfo::Allocator &VNInfoAllocator) {
339  VNInfo *VNI =
340  new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
341  valnos.push_back(VNI);
342  return VNI;
343  }
344 
345  /// RenumberValues - Renumber all values in order of appearance and remove
346  /// unused values.
347  void RenumberValues();
348 
349  /// MergeValueNumberInto - This method is called when two value numbers
350  /// are found to be equivalent. This eliminates V1, replacing all
351  /// segments with the V1 value number with the V2 value number. This can
352  /// cause merging of V1/V2 values numbers and compaction of the value space.
353  VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
354 
355  /// Merge all of the live segments of a specific val# in RHS into this live
356  /// range as the specified value number. The segments in RHS are allowed
357  /// to overlap with segments in the current range, it will replace the
358  /// value numbers of the overlaped live segments with the specified value
359  /// number.
360  void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo);
361 
362  /// MergeValueInAsValue - Merge all of the segments of a specific val#
363  /// in RHS into this live range as the specified value number.
364  /// The segments in RHS are allowed to overlap with segments in the
365  /// current range, but only if the overlapping segments have the
366  /// specified value number.
367  void MergeValueInAsValue(const LiveRange &RHS,
368  const VNInfo *RHSValNo, VNInfo *LHSValNo);
369 
370  bool empty() const { return segments.empty(); }
371 
372  /// beginIndex - Return the lowest numbered slot covered.
374  assert(!empty() && "Call to beginIndex() on empty range.");
375  return segments.front().start;
376  }
377 
378  /// endNumber - return the maximum point of the range of the whole,
379  /// exclusive.
380  SlotIndex endIndex() const {
381  assert(!empty() && "Call to endIndex() on empty range.");
382  return segments.back().end;
383  }
384 
385  bool expiredAt(SlotIndex index) const {
386  return index >= endIndex();
387  }
388 
389  bool liveAt(SlotIndex index) const {
390  const_iterator r = find(index);
391  return r != end() && r->start <= index;
392  }
393 
394  /// Return the segment that contains the specified index, or null if there
395  /// is none.
397  const_iterator I = FindSegmentContaining(Idx);
398  return I == end() ? nullptr : &*I;
399  }
400 
401  /// Return the live segment that contains the specified index, or null if
402  /// there is none.
404  iterator I = FindSegmentContaining(Idx);
405  return I == end() ? nullptr : &*I;
406  }
407 
408  /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
410  const_iterator I = FindSegmentContaining(Idx);
411  return I == end() ? nullptr : I->valno;
412  }
413 
414  /// getVNInfoBefore - Return the VNInfo that is live up to but not
415  /// necessarilly including Idx, or NULL. Use this to find the reaching def
416  /// used by an instruction at this SlotIndex position.
418  const_iterator I = FindSegmentContaining(Idx.getPrevSlot());
419  return I == end() ? nullptr : I->valno;
420  }
421 
422  /// Return an iterator to the segment that contains the specified index, or
423  /// end() if there is none.
425  iterator I = find(Idx);
426  return I != end() && I->start <= Idx ? I : end();
427  }
428 
430  const_iterator I = find(Idx);
431  return I != end() && I->start <= Idx ? I : end();
432  }
433 
434  /// overlaps - Return true if the intersection of the two live ranges is
435  /// not empty.
436  bool overlaps(const LiveRange &other) const {
437  if (other.empty())
438  return false;
439  return overlapsFrom(other, other.begin());
440  }
441 
442  /// overlaps - Return true if the two ranges have overlapping segments
443  /// that are not coalescable according to CP.
444  ///
445  /// Overlapping segments where one range is defined by a coalescable
446  /// copy are allowed.
447  bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
448  const SlotIndexes&) const;
449 
450  /// overlaps - Return true if the live range overlaps an interval specified
451  /// by [Start, End).
452  bool overlaps(SlotIndex Start, SlotIndex End) const;
453 
454  /// overlapsFrom - Return true if the intersection of the two live ranges
455  /// is not empty. The specified iterator is a hint that we can begin
456  /// scanning the Other range starting at I.
457  bool overlapsFrom(const LiveRange &Other, const_iterator I) const;
458 
459  /// Returns true if all segments of the @p Other live range are completely
460  /// covered by this live range.
461  /// Adjacent live ranges do not affect the covering:the liverange
462  /// [1,5](5,10] covers (3,7].
463  bool covers(const LiveRange &Other) const;
464 
465  /// Add the specified Segment to this range, merging segments as
466  /// appropriate. This returns an iterator to the inserted segment (which
467  /// may have grown since it was inserted).
468  iterator addSegment(Segment S);
469 
470  /// Attempt to extend a value defined after @p StartIdx to include @p Use.
471  /// Both @p StartIdx and @p Use should be in the same basic block. In case
472  /// of subranges, an extension could be prevented by an explicit "undef"
473  /// caused by a <def,read-undef> on a non-overlapping lane. The list of
474  /// location of such "undefs" should be provided in @p Undefs.
475  /// The return value is a pair: the first element is VNInfo of the value
476  /// that was extended (possibly nullptr), the second is a boolean value
477  /// indicating whether an "undef" was encountered.
478  /// If this range is live before @p Use in the basic block that starts at
479  /// @p StartIdx, and there is no intervening "undef", extend it to be live
480  /// up to @p Use, and return the pair {value, false}. If there is no
481  /// segment before @p Use and there is no "undef" between @p StartIdx and
482  /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
483  /// return {nullptr, true}.
484  std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
485  SlotIndex StartIdx, SlotIndex Use);
486 
487  /// Simplified version of the above "extendInBlock", which assumes that
488  /// no register lanes are undefined by <def,read-undef> operands.
489  /// If this range is live before @p Use in the basic block that starts
490  /// at @p StartIdx, extend it to be live up to @p Use, and return the
491  /// value. If there is no segment before @p Use, return nullptr.
492  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
493 
494  /// join - Join two live ranges (this, and other) together. This applies
495  /// mappings to the value numbers in the LHS/RHS ranges as specified. If
496  /// the ranges are not joinable, this aborts.
497  void join(LiveRange &Other,
498  const int *ValNoAssignments,
499  const int *RHSValNoAssignments,
500  SmallVectorImpl<VNInfo *> &NewVNInfo);
501 
502  /// True iff this segment is a single segment that lies between the
503  /// specified boundaries, exclusively. Vregs live across a backedge are not
504  /// considered local. The boundaries are expected to lie within an extended
505  /// basic block, so vregs that are not live out should contain no holes.
506  bool isLocal(SlotIndex Start, SlotIndex End) const {
507  return beginIndex() > Start.getBaseIndex() &&
508  endIndex() < End.getBoundaryIndex();
509  }
510 
511  /// Remove the specified segment from this range. Note that the segment
512  /// must be a single Segment in its entirety.
513  void removeSegment(SlotIndex Start, SlotIndex End,
514  bool RemoveDeadValNo = false);
515 
516  void removeSegment(Segment S, bool RemoveDeadValNo = false) {
517  removeSegment(S.start, S.end, RemoveDeadValNo);
518  }
519 
520  /// Remove segment pointed to by iterator @p I from this range. This does
521  /// not remove dead value numbers.
523  return segments.erase(I);
524  }
525 
526  /// Query Liveness at Idx.
527  /// The sub-instruction slot of Idx doesn't matter, only the instruction
528  /// it refers to is considered.
530  // Find the segment that enters the instruction.
531  const_iterator I = find(Idx.getBaseIndex());
532  const_iterator E = end();
533  if (I == E)
534  return LiveQueryResult(nullptr, nullptr, SlotIndex(), false);
535 
536  // Is this an instruction live-in segment?
537  // If Idx is the start index of a basic block, include live-in segments
538  // that start at Idx.getBaseIndex().
539  VNInfo *EarlyVal = nullptr;
540  VNInfo *LateVal = nullptr;
541  SlotIndex EndPoint;
542  bool Kill = false;
543  if (I->start <= Idx.getBaseIndex()) {
544  EarlyVal = I->valno;
545  EndPoint = I->end;
546  // Move to the potentially live-out segment.
547  if (SlotIndex::isSameInstr(Idx, I->end)) {
548  Kill = true;
549  if (++I == E)
550  return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
551  }
552  // Special case: A PHIDef value can have its def in the middle of a
553  // segment if the value happens to be live out of the layout
554  // predecessor.
555  // Such a value is not live-in.
556  if (EarlyVal->def == Idx.getBaseIndex())
557  EarlyVal = nullptr;
558  }
559  // I now points to the segment that may be live-through, or defined by
560  // this instr. Ignore segments starting after the current instr.
561  if (!SlotIndex::isEarlierInstr(Idx, I->start)) {
562  LateVal = I->valno;
563  EndPoint = I->end;
564  }
565  return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
566  }
567 
568  /// removeValNo - Remove all the segments defined by the specified value#.
569  /// Also remove the value# from value# list.
570  void removeValNo(VNInfo *ValNo);
571 
572  /// Returns true if the live range is zero length, i.e. no live segments
573  /// span instructions. It doesn't pay to spill such a range.
574  bool isZeroLength(SlotIndexes *Indexes) const {
575  for (const Segment &S : segments)
576  if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
577  S.end.getBaseIndex())
578  return false;
579  return true;
580  }
581 
582  // Returns true if any segment in the live range contains any of the
583  // provided slot indexes. Slots which occur in holes between
584  // segments will not cause the function to return true.
585  bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
586 
587  bool operator<(const LiveRange& other) const {
588  const SlotIndex &thisIndex = beginIndex();
589  const SlotIndex &otherIndex = other.beginIndex();
590  return thisIndex < otherIndex;
591  }
592 
593  /// Returns true if there is an explicit "undef" between @p Begin
594  /// @p End.
596  SlotIndex End) const {
597  return std::any_of(Undefs.begin(), Undefs.end(),
598  [Begin,End] (SlotIndex Idx) -> bool {
599  return Begin <= Idx && Idx < End;
600  });
601  }
602 
603  /// Flush segment set into the regular segment vector.
604  /// The method is to be called after the live range
605  /// has been created, if use of the segment set was
606  /// activated in the constructor of the live range.
607  void flushSegmentSet();
608 
609  void print(raw_ostream &OS) const;
610  void dump() const;
611 
612  /// \brief Walk the range and assert if any invariants fail to hold.
613  ///
614  /// Note that this is a no-op when asserts are disabled.
615 #ifdef NDEBUG
616  void verify() const {}
617 #else
618  void verify() const;
619 #endif
620 
621  protected:
622  /// Append a segment to the list of segments.
623  void append(const LiveRange::Segment S);
624 
625  private:
626  friend class LiveRangeUpdater;
627  void addSegmentToSet(Segment S);
628  void markValNoForDeletion(VNInfo *V);
629  };
630 
631  inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
632  LR.print(OS);
633  return OS;
634  }
635 
636  /// LiveInterval - This class represents the liveness of a register,
637  /// or stack slot.
638  class LiveInterval : public LiveRange {
639  public:
640  using super = LiveRange;
641 
642  /// A live range for subregisters. The LaneMask specifies which parts of the
643  /// super register are covered by the interval.
644  /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
645  class SubRange : public LiveRange {
646  public:
647  SubRange *Next = nullptr;
649 
650  /// Constructs a new SubRange object.
651  SubRange(LaneBitmask LaneMask) : LaneMask(LaneMask) {}
652 
653  /// Constructs a new SubRange object by copying liveness from @p Other.
654  SubRange(LaneBitmask LaneMask, const LiveRange &Other,
656  : LiveRange(Other, Allocator), LaneMask(LaneMask) {}
657 
658  void print(raw_ostream &OS) const;
659  void dump() const;
660  };
661 
662  private:
663  SubRange *SubRanges = nullptr; ///< Single linked list of subregister live
664  /// ranges.
665 
666  public:
667  const unsigned reg; // the register or stack slot of this interval.
668  float weight; // weight of this interval
669 
670  LiveInterval(unsigned Reg, float Weight) : reg(Reg), weight(Weight) {}
671 
673  clearSubRanges();
674  }
675 
676  template<typename T>
678  T *P;
679 
680  public:
682 
684  P = P->Next;
685  return *this;
686  }
688  SingleLinkedListIterator res = *this;
689  ++*this;
690  return res;
691  }
693  return P != Other.operator->();
694  }
696  return P == Other.operator->();
697  }
698  T &operator*() const {
699  return *P;
700  }
701  T *operator->() const {
702  return P;
703  }
704  };
705 
708 
710  return subrange_iterator(SubRanges);
711  }
713  return subrange_iterator(nullptr);
714  }
715 
717  return const_subrange_iterator(SubRanges);
718  }
720  return const_subrange_iterator(nullptr);
721  }
722 
724  return make_range(subrange_begin(), subrange_end());
725  }
726 
728  return make_range(subrange_begin(), subrange_end());
729  }
730 
731  /// Creates a new empty subregister live range. The range is added at the
732  /// beginning of the subrange list; subrange iterators stay valid.
734  LaneBitmask LaneMask) {
735  SubRange *Range = new (Allocator) SubRange(LaneMask);
736  appendSubRange(Range);
737  return Range;
738  }
739 
740  /// Like createSubRange() but the new range is filled with a copy of the
741  /// liveness information in @p CopyFrom.
743  LaneBitmask LaneMask,
744  const LiveRange &CopyFrom) {
745  SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
746  appendSubRange(Range);
747  return Range;
748  }
749 
750  /// Returns true if subregister liveness information is available.
751  bool hasSubRanges() const {
752  return SubRanges != nullptr;
753  }
754 
755  /// Removes all subregister liveness information.
756  void clearSubRanges();
757 
758  /// Removes all subranges without any segments (subranges without segments
759  /// are not considered valid and should only exist temporarily).
760  void removeEmptySubRanges();
761 
762  /// getSize - Returns the sum of sizes of all the LiveRange's.
763  ///
764  unsigned getSize() const;
765 
766  /// isSpillable - Can this interval be spilled?
767  bool isSpillable() const {
768  return weight != huge_valf;
769  }
770 
771  /// markNotSpillable - Mark interval as not spillable
773  weight = huge_valf;
774  }
775 
776  /// For a given lane mask @p LaneMask, compute indexes at which the
777  /// lane is marked undefined by subregister <def,read-undef> definitions.
778  void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
779  LaneBitmask LaneMask,
780  const MachineRegisterInfo &MRI,
781  const SlotIndexes &Indexes) const;
782 
783  /// Refines the subranges to support \p LaneMask. This may only be called
784  /// for LI.hasSubrange()==true. Subregister ranges are split or created
785  /// until \p LaneMask can be matched exactly. \p Mod is executed on the
786  /// matching subranges.
787  ///
788  /// Example:
789  /// Given an interval with subranges with lanemasks L0F00, L00F0 and
790  /// L000F, refining for mask L0018. Will split the L00F0 lane into
791  /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
792  /// function will be applied to the L0010 and L0008 subranges.
793  void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
795 
796  bool operator<(const LiveInterval& other) const {
797  const SlotIndex &thisIndex = beginIndex();
798  const SlotIndex &otherIndex = other.beginIndex();
799  return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
800  }
801 
802  void print(raw_ostream &OS) const;
803  void dump() const;
804 
805  /// \brief Walks the interval and assert if any invariants fail to hold.
806  ///
807  /// Note that this is a no-op when asserts are disabled.
808 #ifdef NDEBUG
809  void verify(const MachineRegisterInfo *MRI = nullptr) const {}
810 #else
811  void verify(const MachineRegisterInfo *MRI = nullptr) const;
812 #endif
813 
814  private:
815  /// Appends @p Range to SubRanges list.
816  void appendSubRange(SubRange *Range) {
817  Range->Next = SubRanges;
818  SubRanges = Range;
819  }
820 
821  /// Free memory held by SubRange.
822  void freeSubRange(SubRange *S);
823  };
824 
826  const LiveInterval::SubRange &SR) {
827  SR.print(OS);
828  return OS;
829  }
830 
831  inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
832  LI.print(OS);
833  return OS;
834  }
835 
837 
838  inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
839  return V < S.start;
840  }
841 
842  inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
843  return S.start < V;
844  }
845 
846  /// Helper class for performant LiveRange bulk updates.
847  ///
848  /// Calling LiveRange::addSegment() repeatedly can be expensive on large
849  /// live ranges because segments after the insertion point may need to be
850  /// shifted. The LiveRangeUpdater class can defer the shifting when adding
851  /// many segments in order.
852  ///
853  /// The LiveRange will be in an invalid state until flush() is called.
855  LiveRange *LR;
856  SlotIndex LastStart;
857  LiveRange::iterator WriteI;
858  LiveRange::iterator ReadI;
860  void mergeSpills();
861 
862  public:
863  /// Create a LiveRangeUpdater for adding segments to LR.
864  /// LR will temporarily be in an invalid state until flush() is called.
865  LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {}
866 
867  ~LiveRangeUpdater() { flush(); }
868 
869  /// Add a segment to LR and coalesce when possible, just like
870  /// LR.addSegment(). Segments should be added in increasing start order for
871  /// best performance.
872  void add(LiveRange::Segment);
873 
874  void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
875  add(LiveRange::Segment(Start, End, VNI));
876  }
877 
878  /// Return true if the LR is currently in an invalid state, and flush()
879  /// needs to be called.
880  bool isDirty() const { return LastStart.isValid(); }
881 
882  /// Flush the updater state to LR so it is valid and contains all added
883  /// segments.
884  void flush();
885 
886  /// Select a different destination live range.
887  void setDest(LiveRange *lr) {
888  if (LR != lr && isDirty())
889  flush();
890  LR = lr;
891  }
892 
893  /// Get the current destination live range.
894  LiveRange *getDest() const { return LR; }
895 
896  void dump() const;
897  void print(raw_ostream&) const;
898  };
899 
901  X.print(OS);
902  return OS;
903  }
904 
905  /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
906  /// LiveInterval into equivalence clases of connected components. A
907  /// LiveInterval that has multiple connected components can be broken into
908  /// multiple LiveIntervals.
909  ///
910  /// Given a LiveInterval that may have multiple connected components, run:
911  ///
912  /// unsigned numComps = ConEQ.Classify(LI);
913  /// if (numComps > 1) {
914  /// // allocate numComps-1 new LiveIntervals into LIS[1..]
915  /// ConEQ.Distribute(LIS);
916  /// }
917 
919  LiveIntervals &LIS;
920  IntEqClasses EqClass;
921 
922  public:
923  explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
924 
925  /// Classify the values in \p LR into connected components.
926  /// Returns the number of connected components.
927  unsigned Classify(const LiveRange &LR);
928 
929  /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
930  /// the equivalence class assigned the VNI.
931  unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
932 
933  /// Distribute values in \p LI into a separate LiveIntervals
934  /// for each connected component. LIV must have an empty LiveInterval for
935  /// each additional connected component. The first connected component is
936  /// left in \p LI.
937  void Distribute(LiveInterval &LI, LiveInterval *LIV[],
939  };
940 
941 } // end namespace llvm
942 
943 #endif // LLVM_CODEGEN_LIVEINTERVAL_H
std::set< Segment > SegmentSet
Definition: LiveInterval.h:205
bool empty() const
Definition: LiveInterval.h:370
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
void push_back(const T &Elt)
Definition: SmallVector.h:212
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
A common definition of LaneBitmask for use in TableGen and CodeGen.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
VNInfo(unsigned i, SlotIndex d)
VNInfo constructor.
Definition: LiveInterval.h:64
const unsigned reg
Definition: LiveInterval.h:667
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:329
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:242
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator begin() const
Definition: ArrayRef.h:137
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
const_subrange_iterator subrange_begin() const
Definition: LiveInterval.h:716
Segment * getSegmentContaining(SlotIndex Idx)
Return the live segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:403
VNInfoList::iterator vni_iterator
Definition: LiveInterval.h:217
Segments::iterator iterator
Definition: LiveInterval.h:208
SubRange(LaneBitmask LaneMask)
Constructs a new SubRange object.
Definition: LiveInterval.h:651
vni_iterator vni_begin()
Definition: LiveInterval.h:220
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
Definition: LiveInterval.h:595
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position...
Definition: LiveInterval.h:259
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:237
LiveRangeUpdater(LiveRange *lr=nullptr)
Create a LiveRangeUpdater for adding segments to LR.
Definition: LiveInterval.h:865
bool isDeadDef() const
Return true if this instruction has a dead def.
Definition: LiveInterval.h:117
LiveInterval(unsigned Reg, float Weight)
Definition: LiveInterval.h:670
A live range for subregisters.
Definition: LiveInterval.h:645
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
void markUnused()
Mark this value as unused.
Definition: LiveInterval.h:84
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:944
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:742
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
Definition: LiveInterval.h:123
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
const_iterator find(SlotIndex Pos) const
Definition: LiveInterval.h:284
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:204
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:465
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
Definition: SlotIndexes.h:227
bool operator<(const Segment &Other) const
Definition: LiveInterval.h:186
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
iterator end()
Definition: LiveInterval.h:212
A helper class for register coalescers.
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:723
Result of a LiveRange query.
Definition: LiveInterval.h:90
const_iterator end() const
Definition: LiveInterval.h:215
SingleLinkedListIterator< T > & operator++()
Definition: LiveInterval.h:683
Reg
All possible values of the reg field in the ModR/M byte.
std::string join(IteratorT Begin, IteratorT End, StringRef Separator)
Joins the strings in the range [Begin, End), adding Separator between the elements.
Definition: StringExtras.h:327
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:751
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
unsigned getEqClass(const VNInfo *VNI) const
getEqClass - Classify creates equivalence classes numbered 0..N.
Definition: LiveInterval.h:931
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:430
bool contains(SlotIndex I) const
Return true if the index is covered by this segment.
Definition: LiveInterval.h:176
SlotIndexes pass.
Definition: SlotIndexes.h:331
const_iterator advanceTo(const_iterator I, SlotIndex Pos) const
Definition: LiveInterval.h:267
LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, bool Kill)
Definition: LiveInterval.h:97
Segments segments
Definition: LiveInterval.h:199
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
bool operator<(const LiveRange &other) const
Definition: LiveInterval.h:587
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition: MathExtras.cpp:29
LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new LiveRange object by copying segments and valnos from another LiveRange.
Definition: LiveInterval.h:233
size_t size() const
Definition: LiveInterval.h:293
bool isKill() const
Return true if the live-in value is killed by this instruction.
Definition: LiveInterval.h:112
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:574
void print(raw_ostream &OS) const
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
Definition: LiveInterval.h:70
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:529
bool containsOneValue() const
Definition: LiveInterval.h:299
iterator_range< const_subrange_iterator > subranges() const
Definition: LiveInterval.h:727
BumpPtrAllocator Allocator
Definition: LiveInterval.h:55
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:378
#define P(N)
SubRange(LaneBitmask LaneMask, const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new SubRange object by copying liveness from Other.
Definition: LiveInterval.h:654
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:380
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
Definition: LiveInterval.h:733
void removeSegment(Segment S, bool RemoveDeadValNo=false)
Definition: LiveInterval.h:516
unsigned const MachineRegisterInfo * MRI
VNInfoList::const_iterator const_vni_iterator
Definition: LiveInterval.h:218
bool expiredAt(SlotIndex index) const
Definition: LiveInterval.h:385
void print(raw_ostream &OS) const
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:389
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
LiveRange(bool UseSegmentSet=false)
Constructs a new LiveRange object.
Definition: LiveInterval.h:227
bool containsValue(const VNInfo *VNI) const
containsValue - Returns true if VNI belongs to this range.
Definition: LiveInterval.h:313
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:887
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:820
void add(SlotIndex Start, SlotIndex End, VNInfo *VNI)
Definition: LiveInterval.h:874
bool operator<(const LiveInterval &other) const
Definition: LiveInterval.h:796
static const unsigned End
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
iterator removeSegment(iterator I)
Remove segment pointed to by iterator I from this range.
Definition: LiveInterval.h:522
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
void print(raw_ostream &) const
const_vni_iterator vni_begin() const
Definition: LiveInterval.h:223
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:834
VNInfo(unsigned i, const VNInfo &orig)
VNInfo constructor, copies values from orig, except for the value number.
Definition: LiveInterval.h:67
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction, if any.
Definition: LiveInterval.h:147
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
const_iterator FindSegmentContaining(SlotIndex Idx) const
Definition: LiveInterval.h:429
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
ConnectedVNInfoEqClasses(LiveIntervals &lis)
Definition: LiveInterval.h:923
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
Segments::const_iterator const_iterator
Definition: LiveInterval.h:209
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:918
bool isDirty() const
Return true if the LR is currently in an invalid state, and flush() needs to be called.
Definition: LiveInterval.h:880
const_iterator begin() const
Definition: LiveInterval.h:214
iterator end() const
Definition: ArrayRef.h:138
bool operator==(const SingleLinkedListIterator< T > &Other)
Definition: LiveInterval.h:695
std::unique_ptr< SegmentSet > segmentSet
Definition: LiveInterval.h:206
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:772
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx...
Definition: LiveInterval.h:417
A range adaptor for a pair of iterators.
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:297
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
Definition: LiveInterval.h:129
LiveRange * getDest() const
Get the current destination live range.
Definition: LiveInterval.h:894
typename SuperClass::iterator iterator
Definition: SmallVector.h:328
VNInfoList valnos
Definition: LiveInterval.h:200
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
Definition: LiveInterval.h:305
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
bool operator==(const Segment &Other) const
Definition: LiveInterval.h:189
unsigned getNumValNums() const
Definition: LiveInterval.h:301
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:436
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
Definition: LiveInterval.h:240
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
bool operator!=(const SingleLinkedListIterator< T > &Other)
Definition: LiveInterval.h:692
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:396
iterator begin()
Definition: LiveInterval.h:211
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:854
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:319
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:767
const VNInfo * getValNumInfo(unsigned ValNo) const
Definition: LiveInterval.h:308
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:373
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries, exclusively.
Definition: LiveInterval.h:506
const_subrange_iterator subrange_end() const
Definition: LiveInterval.h:719
SingleLinkedListIterator< T > operator++(int)
Definition: LiveInterval.h:687
Segment(SlotIndex S, SlotIndex E, VNInfo *V)
Definition: LiveInterval.h:170
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
subrange_iterator subrange_end()
Definition: LiveInterval.h:712
print Print MemDeps of function
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none...
Definition: LiveInterval.h:424
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Definition: LiveInterval.h:135
subrange_iterator subrange_begin()
Definition: LiveInterval.h:709
void print(raw_ostream &OS) const
const_vni_iterator vni_end() const
Definition: LiveInterval.h:224
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
vni_iterator vni_end()
Definition: LiveInterval.h:221
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
Definition: SlotIndexes.h:249
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
Definition: LiveInterval.h:337
bool containsInterval(SlotIndex S, SlotIndex E) const
Return true if the given interval, [S, E), is covered by this segment.
Definition: LiveInterval.h:181