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