LLVM 24.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"
25#include "llvm/ADT/STLExtras.h"
30#include "llvm/MC/LaneBitmask.h"
34#include <algorithm>
35#include <cassert>
36#include <cstddef>
37#include <functional>
38#include <memory>
39#include <tuple>
40#include <utility>
41
42namespace llvm {
43
44 class CoalescerPair;
45 class LiveIntervals;
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 LLVM_ABI void print(raw_ostream &OS) const;
87 LLVM_ABI void dump() const;
88 };
89
90 inline raw_ostream &operator<<(raw_ostream &OS, const VNInfo &VNI) {
91 VNI.print(OS);
92 return OS;
93 }
94
95 /// Result of a LiveRange query. This class hides the implementation details
96 /// of live ranges, and it should be used as the primary interface for
97 /// examining live ranges around instructions.
99 VNInfo *const EarlyVal;
100 VNInfo *const LateVal;
101 const SlotIndex EndPoint;
102 const bool Kill;
103
104 public:
105 LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint,
106 bool Kill)
107 : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill)
108 {}
109
110 /// Return the value that is live-in to the instruction. This is the value
111 /// that will be read by the instruction's use operands. Return NULL if no
112 /// value is live-in.
113 VNInfo *valueIn() const {
114 return EarlyVal;
115 }
116
117 /// Return true if the live-in value is killed by this instruction. This
118 /// means that either the live range ends at the instruction, or it changes
119 /// value.
120 bool isKill() const {
121 return Kill;
122 }
123
124 /// Return true if this instruction has a dead def.
125 bool isDeadDef() const {
126 return EndPoint.isDead();
127 }
128
129 /// Return the value leaving the instruction, if any. This can be a
130 /// live-through value, or a live def. A dead def returns NULL.
131 VNInfo *valueOut() const {
132 return isDeadDef() ? nullptr : LateVal;
133 }
134
135 /// Returns the value alive at the end of the instruction, if any. This can
136 /// be a live-through value, a live def or a dead def.
138 return LateVal;
139 }
140
141 /// Return the value defined by this instruction, if any. This includes
142 /// dead defs, it is the value created by the instruction's def operands.
144 return EarlyVal == LateVal ? nullptr : LateVal;
145 }
146
147 /// Return the end point of the last live range segment to interact with
148 /// the instruction, if any.
149 ///
150 /// The end point is an invalid SlotIndex only if the live range doesn't
151 /// intersect the instruction at all.
152 ///
153 /// The end point may be at or past the end of the instruction's basic
154 /// block. That means the value was live out of the block.
156 return EndPoint;
157 }
158 };
159
160 /// This class represents the liveness of a register, stack slot, etc.
161 /// It manages an ordered list of Segment objects.
162 /// The Segments are organized in a static single assignment form: At places
163 /// where a new value is defined or different values reach a CFG join a new
164 /// segment with a new value number is used.
165 class LiveRange {
166 public:
167 /// This represents a simple continuous liveness interval for a value.
168 /// The start point is inclusive, the end point exclusive. These intervals
169 /// are rendered as [start,end).
170 struct Segment {
171 SlotIndex start; // Start point of the interval (inclusive)
172 SlotIndex end; // End point of the interval (exclusive)
173 VNInfo *valno = nullptr; // identifier for the value contained in this
174 // segment.
175
176 Segment() = default;
177
179 : start(S), end(E), valno(V) {
180 assert(S < E && "Cannot create empty or backwards segment");
181 }
182
183 /// Return true if the index is covered by this segment.
184 bool contains(SlotIndex I) const {
185 return start <= I && I < end;
186 }
187
188 /// Return true if the given interval, [S, E), is covered by this segment.
190 assert((S < E) && "Backwards interval?");
191 return (start <= S && S < end) && (start < E && E <= end);
192 }
193
194 bool operator<(const Segment &Other) const {
195 return std::tie(start, end) < std::tie(Other.start, Other.end);
196 }
197 bool operator==(const Segment &Other) const {
198 return start == Other.start && end == Other.end;
199 }
200
201 bool operator!=(const Segment &Other) const {
202 return !(*this == Other);
203 }
204
205 LLVM_ABI void dump() const;
206 };
207
210
211 Segments segments; // the liveness segments
212 VNInfoList valnos; // value#'s
213
216
217 iterator begin() { return segments.begin(); }
218 iterator end() { return segments.end(); }
219
220 const_iterator begin() const { return segments.begin(); }
221 const_iterator end() const { return segments.end(); }
222
225
226 vni_iterator vni_begin() { return valnos.begin(); }
227 vni_iterator vni_end() { return valnos.end(); }
228
229 const_vni_iterator vni_begin() const { return valnos.begin(); }
230 const_vni_iterator vni_end() const { return valnos.end(); }
231
235
239
240 /// Constructs a new LiveRange object.
241 LiveRange() = default;
242
243 /// Constructs a new LiveRange object by copying segments and valnos from
244 /// another LiveRange.
248
249 /// Copies values numbers and live segments from \p Other into this range.
251 if (this == &Other)
252 return;
253
254 // Duplicate valnos.
255 for (const VNInfo *VNI : Other.valnos)
257 // Now we can copy segments and remap their valnos.
258 for (const Segment &S : Other.segments)
259 segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
260 }
261
262 /// advanceTo - Advance the specified iterator to point to the Segment
263 /// containing the specified position, or end() if the position is past the
264 /// end of the range. If no Segment contains this position, but the
265 /// position is in a hole, this method returns an iterator pointing to the
266 /// Segment immediately after the hole.
268 assert(I != end());
269 if (Pos >= endIndex())
270 return end();
271 while (I->end <= Pos) ++I;
272 return I;
273 }
274
276 assert(I != end());
277 if (Pos >= endIndex())
278 return end();
279 while (I->end <= Pos) ++I;
280 return I;
281 }
282
283 /// find - Return an iterator pointing to the first segment that ends after
284 /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
285 /// when searching large ranges.
286 ///
287 /// If Pos is contained in a Segment, that segment is returned.
288 /// If Pos is in a hole, the following Segment is returned.
289 /// If Pos is beyond endIndex, end() is returned.
291
293 return const_cast<LiveRange*>(this)->find(Pos);
294 }
295
296 void clear() {
297 valnos.clear();
298 segments.clear();
299 }
300
301 size_t size() const {
302 return segments.size();
303 }
304
305 bool hasAtLeastOneValue() const { return !valnos.empty(); }
306
307 bool containsOneValue() const { return valnos.size() == 1; }
308
309 unsigned getNumValNums() const { return (unsigned)valnos.size(); }
310
311 /// getValNumInfo - Returns pointer to the specified val#.
312 ///
313 inline VNInfo *getValNumInfo(unsigned ValNo) {
314 return valnos[ValNo];
315 }
316 inline const VNInfo *getValNumInfo(unsigned ValNo) const {
317 return valnos[ValNo];
318 }
319
320 /// containsValue - Returns true if VNI belongs to this range.
321 bool containsValue(const VNInfo *VNI) const {
322 return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
323 }
324
325 /// getNextValue - Create a new value number and return it.
326 /// @p Def is the index of instruction that defines the value number.
328 VNInfo *VNI =
329 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), Def);
330 valnos.push_back(VNI);
331 return VNI;
332 }
333
334 /// createDeadDef - Make sure the range has a value defined at Def.
335 /// If one already exists, return it. Otherwise allocate a new value and
336 /// add liveness for a dead def.
338
339 /// Create a def of value @p VNI. Return @p VNI. If there already exists
340 /// a definition at VNI->def, the value defined there must be @p VNI.
342
343 /// Create a copy of the given value. The new value will be identical except
344 /// for the Value number.
346 VNInfo::Allocator &VNInfoAllocator) {
347 VNInfo *VNI =
348 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
349 valnos.push_back(VNI);
350 return VNI;
351 }
352
353 /// RenumberValues - Renumber all values in order of appearance and remove
354 /// unused values.
356
357 /// MergeValueNumberInto - This method is called when two value numbers
358 /// are found to be equivalent. This eliminates V1, replacing all
359 /// segments with the V1 value number with the V2 value number. This can
360 /// cause merging of V1/V2 values numbers and compaction of the value space.
362
363 /// Merge all of the live segments of a specific val# in RHS into this live
364 /// range as the specified value number. The segments in RHS are allowed
365 /// to overlap with segments in the current range, it will replace the
366 /// value numbers of the overlaped live segments with the specified value
367 /// number.
369 VNInfo *LHSValNo);
370
371 /// MergeValueInAsValue - Merge all of the segments of a specific val#
372 /// in RHS into this live range as the specified value number.
373 /// The segments in RHS are allowed to overlap with segments in the
374 /// current range, but only if the overlapping segments have the
375 /// specified value number.
377 const VNInfo *RHSValNo, VNInfo *LHSValNo);
378
379 bool empty() const { return segments.empty(); }
380
381 /// beginIndex - Return the lowest numbered slot covered.
383 assert(!empty() && "Call to beginIndex() on empty range.");
384 return segments.front().start;
385 }
386
387 /// endNumber - return the maximum point of the range of the whole,
388 /// exclusive.
390 assert(!empty() && "Call to endIndex() on empty range.");
391 return segments.back().end;
392 }
393
394 bool expiredAt(SlotIndex index) const {
395 return index >= endIndex();
396 }
397
398 bool liveAt(SlotIndex index) const {
399 const_iterator r = find(index);
400 return r != end() && r->start <= index;
401 }
402
403 /// Return the segment that contains the specified index, or null if there
404 /// is none.
407 return I == end() ? nullptr : &*I;
408 }
409
410 /// Return the live segment that contains the specified index, or null if
411 /// there is none.
414 return I == end() ? nullptr : &*I;
415 }
416
417 /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
420 return I == end() ? nullptr : I->valno;
421 }
422
423 /// getVNInfoBefore - Return the VNInfo that is live up to but not
424 /// necessarily including Idx, or NULL. Use this to find the reaching def
425 /// used by an instruction at this SlotIndex position.
427 const_iterator I = FindSegmentContaining(Idx.getPrevSlot());
428 return I == end() ? nullptr : I->valno;
429 }
430
431 /// Return an iterator to the segment that contains the specified index, or
432 /// end() if there is none.
434 iterator I = find(Idx);
435 return I != end() && I->start <= Idx ? I : end();
436 }
437
439 const_iterator I = find(Idx);
440 return I != end() && I->start <= Idx ? I : end();
441 }
442
443 /// overlaps - Return true if the intersection of the two live ranges is
444 /// not empty.
445 bool overlaps(const LiveRange &other) const {
446 if (empty() || other.empty())
447 return false;
448 return overlapsFrom(other, other.begin());
449 }
450
451 /// overlaps - Return true if the two ranges have overlapping segments
452 /// that are not coalescable according to CP.
453 ///
454 /// Overlapping segments where one range is defined by a coalescable
455 /// copy are allowed.
456 LLVM_ABI bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
457 const SlotIndexes &) const;
458
459 /// overlaps - Return true if the live range overlaps an interval specified
460 /// by [Start, End).
461 LLVM_ABI bool overlaps(SlotIndex Start, SlotIndex End) const;
462
463 /// overlapsFrom - Return true if the intersection of the two live ranges
464 /// is not empty. The specified iterator is a hint that we can begin
465 /// scanning the Other range starting at I.
467 const_iterator StartPos) const;
468
469 /// Returns true if all segments of the @p Other live range are completely
470 /// covered by this live range.
471 /// Adjacent live ranges do not affect the covering:the liverange
472 /// [1,5](5,10] covers (3,7].
473 LLVM_ABI bool covers(const LiveRange &Other) const;
474
475 /// Add the specified Segment to this range, merging segments as
476 /// appropriate. This returns an iterator to the inserted segment (which
477 /// may have grown since it was inserted).
478 LLVM_ABI iterator addSegment(Segment S);
479
480 /// Add \p NewSegs, sorted by start, in one pass. Gives the same result as
481 /// calling addSegment() for each.
483
484 /// Merge the segment pointed to by @p I with its immediate neighbors when
485 /// they use the same value number and touch it. @p I must be a valid
486 /// iterator into this live range. Returns an iterator to the merged
487 /// segment, which may be @p I or the previous segment if @p I was merged
488 /// into it.
490
491 /// Attempt to extend a value defined after @p StartIdx to include @p Use.
492 /// Both @p StartIdx and @p Use should be in the same basic block. In case
493 /// of subranges, an extension could be prevented by an explicit "undef"
494 /// caused by a <def,read-undef> on a non-overlapping lane. The list of
495 /// location of such "undefs" should be provided in @p Undefs.
496 /// The return value is a pair: the first element is VNInfo of the value
497 /// that was extended (possibly nullptr), the second is a boolean value
498 /// indicating whether an "undef" was encountered.
499 /// If this range is live before @p Use in the basic block that starts at
500 /// @p StartIdx, and there is no intervening "undef", extend it to be live
501 /// up to @p Use, and return the pair {value, false}. If there is no
502 /// segment before @p Use and there is no "undef" between @p StartIdx and
503 /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
504 /// return {nullptr, true}.
505 LLVM_ABI std::pair<VNInfo *, bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
506 SlotIndex StartIdx,
508
509 /// Simplified version of the above "extendInBlock", which assumes that
510 /// no register lanes are undefined by <def,read-undef> operands.
511 /// If this range is live before @p Use in the basic block that starts
512 /// at @p StartIdx, extend it to be live up to @p Use, and return the
513 /// value. If there is no segment before @p Use, return nullptr.
515
516 /// join - Join two live ranges (this, and other) together. This applies
517 /// mappings to the value numbers in the LHS/RHS ranges as specified. If
518 /// the ranges are not joinable, this aborts.
519 LLVM_ABI void join(LiveRange &Other, const int *ValNoAssignments,
520 const int *RHSValNoAssignments,
521 SmallVectorImpl<VNInfo *> &NewVNInfo);
522
523 /// True iff this segment is a single segment that lies between the
524 /// specified boundaries, exclusively. Vregs live across a backedge are not
525 /// considered local. The boundaries are expected to lie within an extended
526 /// basic block, so vregs that are not live out should contain no holes.
527 bool isLocal(SlotIndex Start, SlotIndex End) const {
528 return beginIndex() > Start.getBaseIndex() &&
529 endIndex() < End.getBoundaryIndex();
530 }
531
532 /// Remove the specified interval from this live range.
533 /// Does nothing if interval is not part of this live range.
534 /// Note that the interval must be within a single Segment in its entirety.
536 bool RemoveDeadValNo = false);
537
538 void removeSegment(Segment S, bool RemoveDeadValNo = false) {
539 removeSegment(S.start, S.end, RemoveDeadValNo);
540 }
541
542 /// Remove segment pointed to by iterator @p I from this range.
543 LLVM_ABI iterator removeSegment(iterator I, bool RemoveDeadValNo = false);
544
545 /// Mark \p ValNo for deletion if no segments in this range use it.
546 LLVM_ABI void removeValNoIfDead(VNInfo *ValNo);
547
548 /// Query Liveness at Idx.
549 /// The sub-instruction slot of Idx doesn't matter, only the instruction
550 /// it refers to is considered.
552 // Find the segment that enters the instruction.
553 const_iterator I = find(Idx.getBaseIndex());
554 const_iterator E = end();
555 if (I == E)
556 return LiveQueryResult(nullptr, nullptr, SlotIndex(), false);
557
558 // Is this an instruction live-in segment?
559 // If Idx is the start index of a basic block, include live-in segments
560 // that start at Idx.getBaseIndex().
561 VNInfo *EarlyVal = nullptr;
562 VNInfo *LateVal = nullptr;
563 SlotIndex EndPoint;
564 bool Kill = false;
565 if (I->start <= Idx.getBaseIndex()) {
566 EarlyVal = I->valno;
567 EndPoint = I->end;
568 // Move to the potentially live-out segment.
569 if (SlotIndex::isSameInstr(Idx, I->end)) {
570 Kill = true;
571 if (++I == E)
572 return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
573 }
574 // Special case: A PHIDef value can have its def in the middle of a
575 // segment if the value happens to be live out of the layout
576 // predecessor.
577 // Such a value is not live-in.
578 if (EarlyVal->def == Idx.getBaseIndex())
579 EarlyVal = nullptr;
580 }
581 // I now points to the segment that may be live-through, or defined by
582 // this instr. Ignore segments starting after the current instr.
583 if (!SlotIndex::isEarlierInstr(Idx, I->start)) {
584 LateVal = I->valno;
585 EndPoint = I->end;
586 }
587 return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
588 }
589
590 /// removeValNo - Remove all the segments defined by the specified value#.
591 /// Also remove the value# from value# list.
592 LLVM_ABI void removeValNo(VNInfo *ValNo);
593
594 /// Returns true if the live range is zero length, i.e. no live segments
595 /// span instructions. It doesn't pay to spill such a range.
596 bool isZeroLength(SlotIndexes *Indexes) const {
597 for (const Segment &S : segments)
598 if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
599 S.end.getBaseIndex())
600 return false;
601 return true;
602 }
603
604 // Returns true if any segment in the live range contains any of the
605 // provided slot indexes. Slots which occur in holes between
606 // segments will not cause the function to return true.
608
609 bool operator<(const LiveRange& other) const {
610 const SlotIndex &thisIndex = beginIndex();
611 const SlotIndex &otherIndex = other.beginIndex();
612 return thisIndex < otherIndex;
613 }
614
615 /// Returns true if there is an explicit "undef" between @p Begin
616 /// @p End.
618 SlotIndex End) const {
619 return llvm::any_of(Undefs, [Begin, End](SlotIndex Idx) -> bool {
620 return Begin <= Idx && Idx < End;
621 });
622 }
623
624 /// Stores indexes from the input index sequence R at which this LiveRange
625 /// is live to the output O iterator.
626 /// R is a range of _ascending sorted_ _random_ access iterators
627 /// to the input indexes. Indexes stored at O are ascending sorted so it
628 /// can be used directly in the subsequent search (for example for
629 /// subranges). Returns true if found at least one index.
630 template <typename Range, typename OutputIt>
631 bool findIndexesLiveAt(Range &&R, OutputIt O) const {
633 auto Idx = R.begin(), EndIdx = R.end();
634 auto Seg = segments.begin(), EndSeg = segments.end();
635 bool Found = false;
636 while (Idx != EndIdx && Seg != EndSeg) {
637 // if the Seg is lower find first segment that is above Idx using binary
638 // search
639 if (Seg->end <= *Idx) {
640 Seg =
641 std::upper_bound(++Seg, EndSeg, *Idx, [=](auto V, const auto &S) {
642 return V < S.end;
643 });
644 if (Seg == EndSeg)
645 break;
646 }
647 auto NotLessStart = std::lower_bound(Idx, EndIdx, Seg->start);
648 if (NotLessStart == EndIdx)
649 break;
650 auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end);
651 if (NotLessEnd != NotLessStart) {
652 Found = true;
653 O = std::copy(NotLessStart, NotLessEnd, O);
654 }
655 Idx = NotLessEnd;
656 ++Seg;
657 }
658 return Found;
659 }
660
661 LLVM_ABI void print(raw_ostream &OS) const;
662 LLVM_ABI void dump() const;
663
664 /// Walk the range and assert if any invariants fail to hold.
665 ///
666 /// Note that this is a no-op when asserts are disabled.
667#ifdef NDEBUG
668 [[nodiscard]] bool verify() const { return true; }
669#else
670 [[nodiscard]] bool verify() const;
671#endif
672
673 protected:
674 /// Append a segment to the list of segments.
675 LLVM_ABI void append(const LiveRange::Segment S);
676
677 private:
678 friend class LiveRangeUpdater;
679 void markValNoForDeletion(VNInfo *V);
680 };
681
682 inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
683 LR.print(OS);
684 return OS;
685 }
686
687 /// LiveInterval - This class represents the liveness of a register,
688 /// or stack slot.
689 class LiveInterval : public LiveRange {
690 public:
692
693 /// A live range for subregisters. The LaneMask specifies which parts of the
694 /// super register are covered by the interval.
695 /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
696 class SubRange : public LiveRange {
697 public:
698 SubRange *Next = nullptr;
700
701 /// Constructs a new SubRange object.
703
704 /// Constructs a new SubRange object by copying liveness from @p Other.
708
709 LLVM_ABI void print(raw_ostream &OS) const;
710 LLVM_ABI void dump() const;
711 };
712
713 private:
714 SubRange *SubRanges = nullptr; ///< Single linked list of subregister live
715 /// ranges.
716 const Register Reg; // the register or stack slot of this interval.
717 float Weight = 0.0; // weight of this interval
718
719 public:
720 Register reg() const { return Reg; }
721 float weight() const { return Weight; }
722 void incrementWeight(float Inc) { Weight += Inc; }
723 void setWeight(float Value) { Weight = Value; }
724
725 LiveInterval(Register Reg, float Weight) : Reg(Reg), Weight(Weight) {}
726
730
731 template<typename T>
733 T *P;
734
735 public:
737 using value_type = T;
738 using pointer = T *;
739 using reference = T &;
740 using iterator_category = std::forward_iterator_tag;
741
743
745 P = P->Next;
746 return *this;
747 }
749 SingleLinkedListIterator res = *this;
750 ++*this;
751 return res;
752 }
754 return P != Other.operator->();
755 }
757 return P == Other.operator->();
758 }
759 T &operator*() const {
760 return *P;
761 }
762 T *operator->() const {
763 return P;
764 }
765 };
766
769
771 return subrange_iterator(SubRanges);
772 }
774 return subrange_iterator(nullptr);
775 }
776
778 return const_subrange_iterator(SubRanges);
779 }
783
787
791
792 /// Creates a new empty subregister live range. The range is added at the
793 /// beginning of the subrange list; subrange iterators stay valid.
795 LaneBitmask LaneMask) {
796 SubRange *Range = new (Allocator) SubRange(LaneMask);
797 appendSubRange(Range);
798 return Range;
799 }
800
801 /// Like createSubRange() but the new range is filled with a copy of the
802 /// liveness information in @p CopyFrom.
804 LaneBitmask LaneMask,
805 const LiveRange &CopyFrom) {
806 SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
807 appendSubRange(Range);
808 return Range;
809 }
810
811 /// Returns true if subregister liveness information is available.
812 bool hasSubRanges() const {
813 return SubRanges != nullptr;
814 }
815
816 /// Removes all subregister liveness information.
818
819 /// Removes all subranges without any segments (subranges without segments
820 /// are not considered valid and should only exist temporarily).
822
823 /// getSize - Returns the sum of sizes of all the LiveRange's.
824 ///
825 LLVM_ABI unsigned getSize() const;
826
827 /// isSpillable - Can this interval be spilled?
828 bool isSpillable() const { return Weight != huge_valf; }
829
830 /// markNotSpillable - Mark interval as not spillable
831 void markNotSpillable() { Weight = huge_valf; }
832
833 /// For a given lane mask @p LaneMask, compute indexes at which the
834 /// lane is marked undefined by subregister <def,read-undef> definitions.
836 LaneBitmask LaneMask,
838 const SlotIndexes &Indexes) const;
839
840 /// Refines the subranges to support \p LaneMask. This may only be called
841 /// for LI.hasSubrange()==true. Subregister ranges are split or created
842 /// until \p LaneMask can be matched exactly. \p Mod is executed on the
843 /// matching subranges.
844 ///
845 /// Example:
846 /// Given an interval with subranges with lanemasks L0F00, L00F0 and
847 /// L000F, refining for mask L0018. Will split the L00F0 lane into
848 /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
849 /// function will be applied to the L0010 and L0008 subranges.
850 ///
851 /// \p Indexes and \p TRI are required to clean up the VNIs that
852 /// don't define the related lane masks after they get shrunk. E.g.,
853 /// when L000F gets split into L0007 and L0008 maybe only a subset
854 /// of the VNIs that defined L000F defines L0007.
855 ///
856 /// The clean up of the VNIs need to look at the actual instructions
857 /// to decide what is or is not live at a definition point. If the
858 /// update of the subranges occurs while the IR does not reflect these
859 /// changes, \p ComposeSubRegIdx can be used to specify how the
860 /// definition are going to be rewritten.
861 /// E.g., let say we want to merge:
862 /// V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32>
863 /// We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32>
864 /// overlap, i.e., by choosing a class where we can find "offset + 1 == 3".
865 /// Put differently we align V2's sub3 with V1's sub1:
866 /// V2: sub0 sub1 sub2 sub3
867 /// V1: <offset> sub0 sub1
868 ///
869 /// This offset will look like a composed subregidx in the class:
870 /// V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32>
871 /// => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32>
872 ///
873 /// Now if we didn't rewrite the uses and def of V1, all the checks for V1
874 /// need to account for this offset.
875 /// This happens during coalescing where we update the live-ranges while
876 /// still having the old IR around because updating the IR on-the-fly
877 /// would actually clobber some information on how the live-ranges that
878 /// are being updated look like.
879 LLVM_ABI void
881 std::function<void(LiveInterval::SubRange &)> Apply,
882 const SlotIndexes &Indexes, const TargetRegisterInfo &TRI,
883 unsigned ComposeSubRegIdx = 0);
884
885 bool operator<(const LiveInterval& other) const {
886 const SlotIndex &thisIndex = beginIndex();
887 const SlotIndex &otherIndex = other.beginIndex();
888 return std::tie(thisIndex, Reg) < std::tie(otherIndex, other.Reg);
889 }
890
891 LLVM_ABI void print(raw_ostream &OS) const;
892 LLVM_ABI void dump() const;
893
894 /// Walks the interval and assert if any invariants fail to hold.
895 ///
896 /// Note that this is a no-op when asserts are disabled.
897#ifdef NDEBUG
898 [[nodiscard]] bool verify(const MachineRegisterInfo *MRI = nullptr) const {
899 return true;
900 }
901#else
902 [[nodiscard]] bool verify(const MachineRegisterInfo *MRI = nullptr) const;
903#endif
904
905 private:
906 /// Appends @p Range to SubRanges list.
907 void appendSubRange(SubRange *Range) {
908 Range->Next = SubRanges;
909 SubRanges = Range;
910 }
911
912 /// Free memory held by SubRange.
913 void freeSubRange(SubRange *S);
914 };
915
917 const LiveInterval::SubRange &SR) {
918 SR.print(OS);
919 return OS;
920 }
921
923 LI.print(OS);
924 return OS;
925 }
926
927 LLVM_ABI raw_ostream &operator<<(raw_ostream &OS,
928 const LiveRange::Segment &S);
929
930 inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
931 return V < S.start;
932 }
933
934 inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
935 return S.start < V;
936 }
937
938 /// Helper class for performant LiveRange bulk updates.
939 ///
940 /// Calling LiveRange::addSegment() repeatedly can be expensive on large
941 /// live ranges because segments after the insertion point may need to be
942 /// shifted. The LiveRangeUpdater class can defer the shifting when adding
943 /// many segments in order.
944 ///
945 /// The LiveRange will be in an invalid state until flush() is called.
947 LiveRange *LR;
948 SlotIndex LastStart;
949 LiveRange::iterator WriteI;
952 void mergeSpills();
953
954 public:
955 /// Create a LiveRangeUpdater for adding segments to LR.
956 /// LR will temporarily be in an invalid state until flush() is called.
957 LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {}
958
960
961 /// Add a segment to LR and coalesce when possible, just like
962 /// LR.addSegment(). Segments should be added in increasing start order for
963 /// best performance.
965
966 void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
967 add(LiveRange::Segment(Start, End, VNI));
968 }
969
970 /// Return true if the LR is currently in an invalid state, and flush()
971 /// needs to be called.
972 bool isDirty() const { return LastStart.isValid(); }
973
974 /// Flush the updater state to LR so it is valid and contains all added
975 /// segments.
976 LLVM_ABI void flush();
977
978 /// Select a different destination live range.
979 void setDest(LiveRange *lr) {
980 if (LR != lr && isDirty())
981 flush();
982 LR = lr;
983 }
984
985 /// Get the current destination live range.
986 LiveRange *getDest() const { return LR; }
987
988 LLVM_ABI void dump() const;
989 LLVM_ABI void print(raw_ostream &) const;
990 };
991
993 X.print(OS);
994 return OS;
995 }
996
997 /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
998 /// LiveInterval into equivalence clases of connected components. A
999 /// LiveInterval that has multiple connected components can be broken into
1000 /// multiple LiveIntervals.
1001 ///
1002 /// Given a LiveInterval that may have multiple connected components, run:
1003 ///
1004 /// unsigned numComps = ConEQ.Classify(LI);
1005 /// if (numComps > 1) {
1006 /// // allocate numComps-1 new LiveIntervals into LIS[1..]
1007 /// ConEQ.Distribute(LIS);
1008 /// }
1009
1011 LiveIntervals &LIS;
1012 IntEqClasses EqClass;
1013
1014 public:
1015 explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
1016
1017 /// Classify the values in \p LR into connected components. A component
1018 /// made only of phi-defs in unreachable blocks has no def of its own, so
1019 /// it is joined with one that does. Returns the number of components.
1020 LLVM_ABI unsigned Classify(const LiveRange &LR);
1021
1022 /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
1023 /// the equivalence class assigned the VNI.
1024 unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
1025
1026 /// Distribute values in \p LI into a separate LiveIntervals
1027 /// for each connected component. LIV must have an empty LiveInterval for
1028 /// each additional connected component. The first connected component is
1029 /// left in \p LI.
1032 };
1033
1034} // end namespace llvm
1035
1036#endif // LLVM_CODEGEN_LIVEINTERVAL_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
Equivalence classes for small integers.
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
Register const TargetRegisterInfo * TRI
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
MachineRegisterInfo & MRI
Basic Register Allocator
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Value * RHS
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A helper class for register coalescers.
ConnectedVNInfoEqClasses(LiveIntervals &lis)
LLVM_ABI void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
LLVM_ABI unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
unsigned getEqClass(const VNInfo *VNI) const
getEqClass - Classify creates equivalence classes numbered 0..N.
SingleLinkedListIterator< T > operator++(int)
std::forward_iterator_tag iterator_category
bool operator==(const SingleLinkedListIterator< T > &Other) const
bool operator!=(const SingleLinkedListIterator< T > &Other) const
SingleLinkedListIterator< T > & operator++()
A live range for subregisters.
LLVM_ABI void print(raw_ostream &OS) const
SubRange(LaneBitmask LaneMask)
Constructs a new SubRange object.
LLVM_ABI void dump() const
SubRange(LaneBitmask LaneMask, const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new SubRange object by copying liveness from Other.
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
float weight() const
Register reg() const
bool isSpillable() const
isSpillable - Can this interval be spilled?
bool hasSubRanges() const
Returns true if subregister liveness information is available.
LLVM_ABI void dump() const
const_subrange_iterator subrange_begin() const
SingleLinkedListIterator< SubRange > subrange_iterator
LLVM_ABI unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
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...
iterator_range< subrange_iterator > subranges()
LLVM_ABI 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.
const_subrange_iterator subrange_end() const
void incrementWeight(float Inc)
bool operator<(const LiveInterval &other) const
LLVM_ABI void print(raw_ostream &OS) const
LiveInterval(Register Reg, float Weight)
iterator_range< const_subrange_iterator > subranges() const
subrange_iterator subrange_begin()
subrange_iterator subrange_end()
SingleLinkedListIterator< const SubRange > const_subrange_iterator
LLVM_ABI 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 ...
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
void setWeight(float Value)
LLVM_ABI void clearSubRanges()
Removes all subregister liveness information.
Result of a LiveRange query.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
bool isDeadDef() const
Return true if this instruction has a dead def.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, bool Kill)
bool isKill() const
Return true if the live-in value is killed by this instruction.
Helper class for performant LiveRange bulk updates.
LLVM_ABI void print(raw_ostream &) const
void setDest(LiveRange *lr)
Select a different destination live range.
LLVM_ABI void flush()
Flush the updater state to LR so it is valid and contains all added segments.
LiveRangeUpdater(LiveRange *lr=nullptr)
Create a LiveRangeUpdater for adding segments to LR.
void add(SlotIndex Start, SlotIndex End, VNInfo *VNI)
LLVM_ABI void dump() const
bool isDirty() const
Return true if the LR is currently in an invalid state, and flush() needs to be called.
LiveRange * getDest() const
Get the current destination live range.
LLVM_ABI void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
This class represents the liveness of a register, stack slot, etc.
iterator_range< const_vni_iterator > vnis() const
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::iterator iterator
const_iterator FindSegmentContaining(SlotIndex Idx) const
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
VNInfoList::iterator vni_iterator
LLVM_ABI void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
LLVM_ABI 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...
iterator_range< vni_iterator > vnis()
const_iterator advanceTo(const_iterator I, SlotIndex Pos) const
LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new LiveRange object by copying segments and valnos from another LiveRange.
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
Segments::const_iterator const_iterator
bool liveAt(SlotIndex index) const
LLVM_ABI VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
LLVM_ABI iterator mergeAdjacentSegments(iterator I)
Merge the segment pointed to by I with its immediate neighbors when they use the same value number an...
const_iterator find(SlotIndex Pos) const
const_iterator begin() const
LLVM_ABI bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
bool containsValue(const VNInfo *VNI) const
containsValue - Returns true if VNI belongs to this range.
LLVM_ABI bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
vni_iterator vni_begin()
LiveRange()=default
Constructs a new LiveRange object.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
LLVM_ABI void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
const_vni_iterator vni_begin() const
bool empty() const
LLVM_ABI void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
LLVM_ABI bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const
overlapsFrom - Return true if the intersection of the two live ranges is not empty.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
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...
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...
const_vni_iterator vni_end() const
LLVM_ABI std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
LLVM_ABI void addSegments(ArrayRef< Segment > NewSegs)
Add NewSegs, sorted by start, in one pass.
bool expiredAt(SlotIndex index) const
bool verify() const
Walk the range and assert if any invariants fail to hold.
LLVM_ABI void append(const LiveRange::Segment S)
Append a segment to the list of segments.
friend class LiveRangeUpdater
LLVM_ABI VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
unsigned getNumValNums() const
iterator begin()
const VNInfo * getValNumInfo(unsigned ValNo) const
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
const_iterator end() const
VNInfoList valnos
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
LLVM_ABI 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 ...
Segment * getSegmentContaining(SlotIndex Idx)
Return the live segment that contains the specified index, or null if there is none.
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
bool containsOneValue() const
size_t size() const
vni_iterator vni_end()
bool hasAtLeastOneValue() const
SmallVector< Segment, 2 > Segments
VNInfoList::const_iterator const_vni_iterator
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries,...
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
LLVM_ABI void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
LLVM_ABI void removeValNoIfDead(VNInfo *ValNo)
Mark ValNo for deletion if no segments in this range use it.
void removeSegment(Segment S, bool RemoveDeadValNo=false)
LLVM_ABI void dump() const
SmallVector< VNInfo *, 2 > VNInfoList
bool operator<(const LiveRange &other) const
LLVM_ABI void print(raw_ostream &OS) const
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
LLVM_ABI iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition Register.h:20
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:70
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndexes pass.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
LLVM_ABI void dump() const
VNInfo(unsigned i, SlotIndex d)
VNInfo constructor.
VNInfo(unsigned i, const VNInfo &orig)
VNInfo constructor, copies values from orig, except for the value number.
LLVM_ABI void print(raw_ostream &OS) const
void markUnused()
Mark this value as unused.
BumpPtrAllocator Allocator
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
LLVM Value Representation.
Definition Value.h:75
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
bool operator<(int64_t V1, const APSInt &V2)
Definition APSInt.h:360
@ Kill
The last use of a register.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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:1762
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:1986
@ Other
Any other memory.
Definition ModRef.h:68
LLVM_ABI const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
This represents a simple continuous liveness interval for a value.
bool operator==(const Segment &Other) const
bool containsInterval(SlotIndex S, SlotIndex E) const
Return true if the given interval, [S, E), is covered by this segment.
bool operator!=(const Segment &Other) const
Segment(SlotIndex S, SlotIndex E, VNInfo *V)
bool contains(SlotIndex I) const
Return true if the index is covered by this segment.
LLVM_ABI void dump() const
bool operator<(const Segment &Other) const