LLVM 20.0.0git
LiveInterval.cpp
Go to the documentation of this file.
1//===- LiveInterval.cpp - Live Interval Representation --------------------===//
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
21#include "LiveRangeUtils.h"
22#include "RegisterCoalescer.h"
23#include "llvm/ADT/ArrayRef.h"
24#include "llvm/ADT/STLExtras.h"
35#include "llvm/Config/llvm-config.h"
36#include "llvm/MC/LaneBitmask.h"
38#include "llvm/Support/Debug.h"
40#include <algorithm>
41#include <cassert>
42#include <cstddef>
43#include <iterator>
44#include <utility>
45
46using namespace llvm;
47
48namespace {
49
50//===----------------------------------------------------------------------===//
51// Implementation of various methods necessary for calculation of live ranges.
52// The implementation of the methods abstracts from the concrete type of the
53// segment collection.
54//
55// Implementation of the class follows the Template design pattern. The base
56// class contains generic algorithms that call collection-specific methods,
57// which are provided in concrete subclasses. In order to avoid virtual calls
58// these methods are provided by means of C++ template instantiation.
59// The base class calls the methods of the subclass through method impl(),
60// which casts 'this' pointer to the type of the subclass.
61//
62//===----------------------------------------------------------------------===//
63
64template <typename ImplT, typename IteratorT, typename CollectionT>
65class CalcLiveRangeUtilBase {
66protected:
67 LiveRange *LR;
68
69protected:
70 CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
71
72public:
73 using Segment = LiveRange::Segment;
74 using iterator = IteratorT;
75
76 /// A counterpart of LiveRange::createDeadDef: Make sure the range has a
77 /// value defined at @p Def.
78 /// If @p ForVNI is null, and there is no value defined at @p Def, a new
79 /// value will be allocated using @p VNInfoAllocator.
80 /// If @p ForVNI is null, the return value is the value defined at @p Def,
81 /// either a pre-existing one, or the one newly created.
82 /// If @p ForVNI is not null, then @p Def should be the location where
83 /// @p ForVNI is defined. If the range does not have a value defined at
84 /// @p Def, the value @p ForVNI will be used instead of allocating a new
85 /// one. If the range already has a value defined at @p Def, it must be
86 /// same as @p ForVNI. In either case, @p ForVNI will be the return value.
87 VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator *VNInfoAllocator,
88 VNInfo *ForVNI) {
89 assert(!Def.isDead() && "Cannot define a value at the dead slot");
90 assert((!ForVNI || ForVNI->def == Def) &&
91 "If ForVNI is specified, it must match Def");
92 iterator I = impl().find(Def);
93 if (I == segments().end()) {
94 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
95 impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
96 return VNI;
97 }
98
99 Segment *S = segmentAt(I);
100 if (SlotIndex::isSameInstr(Def, S->start)) {
101 assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
102 assert(S->valno->def == S->start && "Inconsistent existing value def");
103
104 // It is possible to have both normal and early-clobber defs of the same
105 // register on an instruction. It doesn't make a lot of sense, but it is
106 // possible to specify in inline assembly.
107 //
108 // Just convert everything to early-clobber.
109 Def = std::min(Def, S->start);
110 if (Def != S->start)
111 S->start = S->valno->def = Def;
112 return S->valno;
113 }
114 assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
115 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
116 segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
117 return VNI;
118 }
119
120 VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
121 if (segments().empty())
122 return nullptr;
123 iterator I =
124 impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
125 if (I == segments().begin())
126 return nullptr;
127 --I;
128 if (I->end <= StartIdx)
129 return nullptr;
130 if (I->end < Use)
131 extendSegmentEndTo(I, Use);
132 return I->valno;
133 }
134
135 std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
136 SlotIndex StartIdx, SlotIndex Use) {
137 if (segments().empty())
138 return std::make_pair(nullptr, false);
139 SlotIndex BeforeUse = Use.getPrevSlot();
140 iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
141 if (I == segments().begin())
142 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
143 --I;
144 if (I->end <= StartIdx)
145 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
146 if (I->end < Use) {
147 if (LR->isUndefIn(Undefs, I->end, BeforeUse))
148 return std::make_pair(nullptr, true);
149 extendSegmentEndTo(I, Use);
150 }
151 return std::make_pair(I->valno, false);
152 }
153
154 /// This method is used when we want to extend the segment specified
155 /// by I to end at the specified endpoint. To do this, we should
156 /// merge and eliminate all segments that this will overlap
157 /// with. The iterator is not invalidated.
158 void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
159 assert(I != segments().end() && "Not a valid segment!");
160 Segment *S = segmentAt(I);
161 VNInfo *ValNo = I->valno;
162
163 // Search for the first segment that we can't merge with.
164 iterator MergeTo = std::next(I);
165 for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo)
166 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
167
168 // If NewEnd was in the middle of a segment, make sure to get its endpoint.
169 S->end = std::max(NewEnd, std::prev(MergeTo)->end);
170
171 // If the newly formed segment now touches the segment after it and if they
172 // have the same value number, merge the two segments into one segment.
173 if (MergeTo != segments().end() && MergeTo->start <= I->end &&
174 MergeTo->valno == ValNo) {
175 S->end = MergeTo->end;
176 ++MergeTo;
177 }
178
179 // Erase any dead segments.
180 segments().erase(std::next(I), MergeTo);
181 }
182
183 /// This method is used when we want to extend the segment specified
184 /// by I to start at the specified endpoint. To do this, we should
185 /// merge and eliminate all segments that this will overlap with.
186 iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
187 assert(I != segments().end() && "Not a valid segment!");
188 Segment *S = segmentAt(I);
189 VNInfo *ValNo = I->valno;
190
191 // Search for the first segment that we can't merge with.
192 iterator MergeTo = I;
193 do {
194 if (MergeTo == segments().begin()) {
195 S->start = NewStart;
196 segments().erase(MergeTo, I);
197 return I;
198 }
199 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
200 --MergeTo;
201 } while (NewStart <= MergeTo->start);
202
203 // If we start in the middle of another segment, just delete a range and
204 // extend that segment.
205 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
206 segmentAt(MergeTo)->end = S->end;
207 } else {
208 // Otherwise, extend the segment right after.
209 ++MergeTo;
210 Segment *MergeToSeg = segmentAt(MergeTo);
211 MergeToSeg->start = NewStart;
212 MergeToSeg->end = S->end;
213 }
214
215 segments().erase(std::next(MergeTo), std::next(I));
216 return MergeTo;
217 }
218
219 iterator addSegment(Segment S) {
220 SlotIndex Start = S.start, End = S.end;
221 iterator I = impl().findInsertPos(S);
222
223 // If the inserted segment starts in the middle or right at the end of
224 // another segment, just extend that segment to contain the segment of S.
225 if (I != segments().begin()) {
226 iterator B = std::prev(I);
227 if (S.valno == B->valno) {
228 if (B->start <= Start && B->end >= Start) {
229 extendSegmentEndTo(B, End);
230 return B;
231 }
232 } else {
233 // Check to make sure that we are not overlapping two live segments with
234 // different valno's.
235 assert(B->end <= Start &&
236 "Cannot overlap two segments with differing ValID's"
237 " (did you def the same reg twice in a MachineInstr?)");
238 }
239 }
240
241 // Otherwise, if this segment ends in the middle of, or right next
242 // to, another segment, merge it into that segment.
243 if (I != segments().end()) {
244 if (S.valno == I->valno) {
245 if (I->start <= End) {
246 I = extendSegmentStartTo(I, Start);
247
248 // If S is a complete superset of a segment, we may need to grow its
249 // endpoint as well.
250 if (End > I->end)
251 extendSegmentEndTo(I, End);
252 return I;
253 }
254 } else {
255 // Check to make sure that we are not overlapping two live segments with
256 // different valno's.
257 assert(I->start >= End &&
258 "Cannot overlap two segments with differing ValID's");
259 }
260 }
261
262 // Otherwise, this is just a new segment that doesn't interact with
263 // anything.
264 // Insert it.
265 return segments().insert(I, S);
266 }
267
268private:
269 ImplT &impl() { return *static_cast<ImplT *>(this); }
270
271 CollectionT &segments() { return impl().segmentsColl(); }
272
273 Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
274};
275
276//===----------------------------------------------------------------------===//
277// Instantiation of the methods for calculation of live ranges
278// based on a segment vector.
279//===----------------------------------------------------------------------===//
280
281class CalcLiveRangeUtilVector;
282using CalcLiveRangeUtilVectorBase =
283 CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator,
285
286class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {
287public:
288 CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {}
289
290private:
291 friend CalcLiveRangeUtilVectorBase;
292
293 LiveRange::Segments &segmentsColl() { return LR->segments; }
294
295 void insertAtEnd(const Segment &S) { LR->segments.push_back(S); }
296
297 iterator find(SlotIndex Pos) { return LR->find(Pos); }
298
299 iterator findInsertPos(Segment S) { return llvm::upper_bound(*LR, S.start); }
300};
301
302//===----------------------------------------------------------------------===//
303// Instantiation of the methods for calculation of live ranges
304// based on a segment set.
305//===----------------------------------------------------------------------===//
306
307class CalcLiveRangeUtilSet;
308using CalcLiveRangeUtilSetBase =
309 CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, LiveRange::SegmentSet::iterator,
311
312class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {
313public:
314 CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {}
315
316private:
317 friend CalcLiveRangeUtilSetBase;
318
319 LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; }
320
321 void insertAtEnd(const Segment &S) {
322 LR->segmentSet->insert(LR->segmentSet->end(), S);
323 }
324
325 iterator find(SlotIndex Pos) {
326 iterator I =
327 LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr));
328 if (I == LR->segmentSet->begin())
329 return I;
330 iterator PrevI = std::prev(I);
331 if (Pos < (*PrevI).end)
332 return PrevI;
333 return I;
334 }
335
336 iterator findInsertPos(Segment S) {
337 iterator I = LR->segmentSet->upper_bound(S);
338 if (I != LR->segmentSet->end() && !(S.start < *I))
339 ++I;
340 return I;
341 }
342};
343
344} // end anonymous namespace
345
346//===----------------------------------------------------------------------===//
347// LiveRange methods
348//===----------------------------------------------------------------------===//
349
351 return llvm::partition_point(*this,
352 [&](const Segment &X) { return X.end <= Pos; });
353}
354
356 // Use the segment set, if it is available.
357 if (segmentSet != nullptr)
358 return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr);
359 // Otherwise use the segment vector.
360 return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr);
361}
362
364 // Use the segment set, if it is available.
365 if (segmentSet != nullptr)
366 return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);
367 // Otherwise use the segment vector.
368 return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);
369}
370
371// overlaps - Return true if the intersection of the two live ranges is
372// not empty.
373//
374// An example for overlaps():
375//
376// 0: A = ...
377// 4: B = ...
378// 8: C = A + B ;; last use of A
379//
380// The live ranges should look like:
381//
382// A = [3, 11)
383// B = [7, x)
384// C = [11, y)
385//
386// A->overlaps(C) should return false since we want to be able to join
387// A and C.
388//
390 const_iterator StartPos) const {
391 assert(!empty() && "empty range");
392 const_iterator i = begin();
393 const_iterator ie = end();
394 const_iterator j = StartPos;
395 const_iterator je = other.end();
396
397 assert((StartPos->start <= i->start || StartPos == other.begin()) &&
398 StartPos != other.end() && "Bogus start position hint!");
399
400 if (i->start < j->start) {
401 i = std::upper_bound(i, ie, j->start);
402 if (i != begin()) --i;
403 } else if (j->start < i->start) {
404 ++StartPos;
405 if (StartPos != other.end() && StartPos->start <= i->start) {
406 assert(StartPos < other.end() && i < end());
407 j = std::upper_bound(j, je, i->start);
408 if (j != other.begin()) --j;
409 }
410 } else {
411 return true;
412 }
413
414 if (j == je) return false;
415
416 while (i != ie) {
417 if (i->start > j->start) {
418 std::swap(i, j);
419 std::swap(ie, je);
420 }
421
422 if (i->end > j->start)
423 return true;
424 ++i;
425 }
426
427 return false;
428}
429
431 const SlotIndexes &Indexes) const {
432 assert(!empty() && "empty range");
433 if (Other.empty())
434 return false;
435
436 // Use binary searches to find initial positions.
437 const_iterator I = find(Other.beginIndex());
438 const_iterator IE = end();
439 if (I == IE)
440 return false;
441 const_iterator J = Other.find(I->start);
442 const_iterator JE = Other.end();
443 if (J == JE)
444 return false;
445
446 while (true) {
447 // J has just been advanced to satisfy:
448 assert(J->end > I->start);
449 // Check for an overlap.
450 if (J->start < I->end) {
451 // I and J are overlapping. Find the later start.
452 SlotIndex Def = std::max(I->start, J->start);
453 // Allow the overlap if Def is a coalescable copy.
454 if (Def.isBlock() ||
455 !CP.isCoalescable(Indexes.getInstructionFromIndex(Def)))
456 return true;
457 }
458 // Advance the iterator that ends first to check for more overlaps.
459 if (J->end > I->end) {
460 std::swap(I, J);
461 std::swap(IE, JE);
462 }
463 // Advance J until J->end > I->start.
464 do
465 if (++J == JE)
466 return false;
467 while (J->end <= I->start);
468 }
469}
470
471/// overlaps - Return true if the live range overlaps an interval specified
472/// by [Start, End).
474 assert(Start < End && "Invalid range");
476 return I != begin() && (--I)->end > Start;
477}
478
480 if (empty())
481 return Other.empty();
482
484 for (const Segment &O : Other.segments) {
485 I = advanceTo(I, O.start);
486 if (I == end() || I->start > O.start)
487 return false;
488
489 // Check adjacent live segments and see if we can get behind O.end.
490 while (I->end < O.end) {
492 // Get next segment and abort if it was not adjacent.
493 ++I;
494 if (I == end() || Last->end != I->start)
495 return false;
496 }
497 }
498 return true;
499}
500
501/// ValNo is dead, remove it. If it is the largest value number, just nuke it
502/// (and any other deleted values neighboring it), otherwise mark it as ~1U so
503/// it can be nuked later.
504void LiveRange::markValNoForDeletion(VNInfo *ValNo) {
505 if (ValNo->id == getNumValNums()-1) {
506 do {
508 } while (!valnos.empty() && valnos.back()->isUnused());
509 } else {
510 ValNo->markUnused();
511 }
512}
513
514/// RenumberValues - Renumber all values in order of appearance and delete the
515/// remaining unused values.
518 valnos.clear();
519 for (const Segment &S : segments) {
520 VNInfo *VNI = S.valno;
521 if (!Seen.insert(VNI).second)
522 continue;
523 assert(!VNI->isUnused() && "Unused valno used by live segment");
524 VNI->id = (unsigned)valnos.size();
525 valnos.push_back(VNI);
526 }
527}
528
529void LiveRange::addSegmentToSet(Segment S) {
530 CalcLiveRangeUtilSet(this).addSegment(S);
531}
532
534 // Use the segment set, if it is available.
535 if (segmentSet != nullptr) {
536 addSegmentToSet(S);
537 return end();
538 }
539 // Otherwise use the segment vector.
540 return CalcLiveRangeUtilVector(this).addSegment(S);
541}
542
544 // Check that the segment belongs to the back of the list.
545 assert(segments.empty() || segments.back().end <= S.start);
547}
548
549std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs,
550 SlotIndex StartIdx, SlotIndex Kill) {
551 // Use the segment set, if it is available.
552 if (segmentSet != nullptr)
553 return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill);
554 // Otherwise use the segment vector.
555 return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill);
556}
557
559 // Use the segment set, if it is available.
560 if (segmentSet != nullptr)
561 return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
562 // Otherwise use the segment vector.
563 return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
564}
565
567 bool RemoveDeadValNo) {
568 // Find the Segment containing this span.
569 iterator I = find(Start);
570
571 // No Segment found, so nothing to do.
572 if (I == end())
573 return;
574
575 assert(I->containsInterval(Start, End)
576 && "Segment is not entirely in range!");
577
578 // If the span we are removing is at the start of the Segment, adjust it.
579 VNInfo *ValNo = I->valno;
580 if (I->start == Start) {
581 if (I->end == End) {
582 segments.erase(I); // Removed the whole Segment.
583
584 if (RemoveDeadValNo)
585 removeValNoIfDead(ValNo);
586 } else
587 I->start = End;
588 return;
589 }
590
591 // Otherwise if the span we are removing is at the end of the Segment,
592 // adjust the other way.
593 if (I->end == End) {
594 I->end = Start;
595 return;
596 }
597
598 // Otherwise, we are splitting the Segment into two pieces.
599 SlotIndex OldEnd = I->end;
600 I->end = Start; // Trim the old segment.
601
602 // Insert the new one.
603 segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
604}
605
607 VNInfo *ValNo = I->valno;
608 I = segments.erase(I);
609 if (RemoveDeadValNo)
610 removeValNoIfDead(ValNo);
611 return I;
612}
613
615 if (none_of(*this, [=](const Segment &S) { return S.valno == ValNo; }))
616 markValNoForDeletion(ValNo);
617}
618
619/// removeValNo - Remove all the segments defined by the specified value#.
620/// Also remove the value# from value# list.
622 if (empty()) return;
624 [ValNo](const Segment &S) { return S.valno == ValNo; });
625 // Now that ValNo is dead, remove it.
626 markValNoForDeletion(ValNo);
627}
628
630 const int *LHSValNoAssignments,
631 const int *RHSValNoAssignments,
632 SmallVectorImpl<VNInfo *> &NewVNInfo) {
633 verify();
634 Other.verify();
635
636 // Determine if any of our values are mapped. This is uncommon, so we want
637 // to avoid the range scan if not.
638 bool MustMapCurValNos = false;
639 unsigned NumVals = getNumValNums();
640 unsigned NumNewVals = NewVNInfo.size();
641 for (unsigned i = 0; i != NumVals; ++i) {
642 unsigned LHSValID = LHSValNoAssignments[i];
643 if (i != LHSValID ||
644 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
645 MustMapCurValNos = true;
646 break;
647 }
648 }
649
650 // If we have to apply a mapping to our base range assignment, rewrite it now.
651 if (MustMapCurValNos && !empty()) {
652 // Map the first live range.
653
654 iterator OutIt = begin();
655 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
656 for (iterator I = std::next(OutIt), E = end(); I != E; ++I) {
657 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
658 assert(nextValNo && "Huh?");
659
660 // If this live range has the same value # as its immediate predecessor,
661 // and if they are neighbors, remove one Segment. This happens when we
662 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
663 if (OutIt->valno == nextValNo && OutIt->end == I->start) {
664 OutIt->end = I->end;
665 } else {
666 // Didn't merge. Move OutIt to the next segment,
667 ++OutIt;
668 OutIt->valno = nextValNo;
669 if (OutIt != I) {
670 OutIt->start = I->start;
671 OutIt->end = I->end;
672 }
673 }
674 }
675 // If we merge some segments, chop off the end.
676 ++OutIt;
677 segments.erase(OutIt, end());
678 }
679
680 // Rewrite Other values before changing the VNInfo ids.
681 // This can leave Other in an invalid state because we're not coalescing
682 // touching segments that now have identical values. That's OK since Other is
683 // not supposed to be valid after calling join();
684 for (Segment &S : Other.segments)
685 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
686
687 // Update val# info. Renumber them and make sure they all belong to this
688 // LiveRange now. Also remove dead val#'s.
689 unsigned NumValNos = 0;
690 for (unsigned i = 0; i < NumNewVals; ++i) {
691 VNInfo *VNI = NewVNInfo[i];
692 if (VNI) {
693 if (NumValNos >= NumVals)
694 valnos.push_back(VNI);
695 else
696 valnos[NumValNos] = VNI;
697 VNI->id = NumValNos++; // Renumber val#.
698 }
699 }
700 if (NumNewVals < NumVals)
701 valnos.resize(NumNewVals); // shrinkify
702
703 // Okay, now insert the RHS live segments into the LHS.
704 LiveRangeUpdater Updater(this);
705 for (Segment &S : Other.segments)
706 Updater.add(S);
707}
708
709/// Merge all of the segments in RHS into this live range as the specified
710/// value number. The segments in RHS are allowed to overlap with segments in
711/// the current range, but only if the overlapping segments have the
712/// specified value number.
714 VNInfo *LHSValNo) {
715 LiveRangeUpdater Updater(this);
716 for (const Segment &S : RHS.segments)
717 Updater.add(S.start, S.end, LHSValNo);
718}
719
720/// MergeValueInAsValue - Merge all of the live segments of a specific val#
721/// in RHS into this live range as the specified value number.
722/// The segments in RHS are allowed to overlap with segments in the
723/// current range, it will replace the value numbers of the overlaped
724/// segments with the specified value number.
726 const VNInfo *RHSValNo,
727 VNInfo *LHSValNo) {
728 LiveRangeUpdater Updater(this);
729 for (const Segment &S : RHS.segments)
730 if (S.valno == RHSValNo)
731 Updater.add(S.start, S.end, LHSValNo);
732}
733
734/// MergeValueNumberInto - This method is called when two value nubmers
735/// are found to be equivalent. This eliminates V1, replacing all
736/// segments with the V1 value number with the V2 value number. This can
737/// cause merging of V1/V2 values numbers and compaction of the value space.
739 assert(V1 != V2 && "Identical value#'s are always equivalent!");
740
741 // This code actually merges the (numerically) larger value number into the
742 // smaller value number, which is likely to allow us to compactify the value
743 // space. The only thing we have to be careful of is to preserve the
744 // instruction that defines the result value.
745
746 // Make sure V2 is smaller than V1.
747 if (V1->id < V2->id) {
748 V1->copyFrom(*V2);
749 std::swap(V1, V2);
750 }
751
752 // Merge V1 segments into V2.
753 for (iterator I = begin(); I != end(); ) {
754 iterator S = I++;
755 if (S->valno != V1) continue; // Not a V1 Segment.
756
757 // Okay, we found a V1 live range. If it had a previous, touching, V2 live
758 // range, extend it.
759 if (S != begin()) {
760 iterator Prev = S-1;
761 if (Prev->valno == V2 && Prev->end == S->start) {
762 Prev->end = S->end;
763
764 // Erase this live-range.
765 segments.erase(S);
766 I = Prev+1;
767 S = Prev;
768 }
769 }
770
771 // Okay, now we have a V1 or V2 live range that is maximally merged forward.
772 // Ensure that it is a V2 live-range.
773 S->valno = V2;
774
775 // If we can merge it into later V2 segments, do so now. We ignore any
776 // following V1 segments, as they will be merged in subsequent iterations
777 // of the loop.
778 if (I != end()) {
779 if (I->start == S->end && I->valno == V2) {
780 S->end = I->end;
782 I = S+1;
783 }
784 }
785 }
786
787 // Now that V1 is dead, remove it.
788 markValNoForDeletion(V1);
789
790 return V2;
791}
792
794 assert(segmentSet != nullptr && "segment set must have been created");
795 assert(
796 segments.empty() &&
797 "segment set can be used only initially before switching to the array");
798 segments.append(segmentSet->begin(), segmentSet->end());
799 segmentSet = nullptr;
800 verify();
801}
802
804 ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
805 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
806
807 // If there are no regmask slots, we have nothing to search.
808 if (SlotI == SlotE)
809 return false;
810
811 // Start our search at the first segment that ends after the first slot.
812 const_iterator SegmentI = find(*SlotI);
813 const_iterator SegmentE = end();
814
815 // If there are no segments that end after the first slot, we're done.
816 if (SegmentI == SegmentE)
817 return false;
818
819 // Look for each slot in the live range.
820 for ( ; SlotI != SlotE; ++SlotI) {
821 // Go to the next segment that ends after the current slot.
822 // The slot may be within a hole in the range.
823 SegmentI = advanceTo(SegmentI, *SlotI);
824 if (SegmentI == SegmentE)
825 return false;
826
827 // If this segment contains the slot, we're done.
828 if (SegmentI->contains(*SlotI))
829 return true;
830 // Otherwise, look for the next slot.
831 }
832
833 // We didn't find a segment containing any of the slots.
834 return false;
835}
836
837void LiveInterval::freeSubRange(SubRange *S) {
838 S->~SubRange();
839 // Memory was allocated with BumpPtr allocator and is not freed here.
840}
841
843 SubRange **NextPtr = &SubRanges;
844 SubRange *I = *NextPtr;
845 while (I != nullptr) {
846 if (!I->empty()) {
847 NextPtr = &I->Next;
848 I = *NextPtr;
849 continue;
850 }
851 // Skip empty subranges until we find the first nonempty one.
852 do {
853 SubRange *Next = I->Next;
854 freeSubRange(I);
855 I = Next;
856 } while (I != nullptr && I->empty());
857 *NextPtr = I;
858 }
859}
860
862 for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
863 Next = I->Next;
864 freeSubRange(I);
865 }
866 SubRanges = nullptr;
867}
868
869/// For each VNI in \p SR, check whether or not that value defines part
870/// of the mask describe by \p LaneMask and if not, remove that value
871/// from \p SR.
873 LaneBitmask LaneMask,
874 const SlotIndexes &Indexes,
875 const TargetRegisterInfo &TRI,
876 unsigned ComposeSubRegIdx) {
877 // Phys reg should not be tracked at subreg level.
878 // Same for noreg (Reg == 0).
879 if (!Register::isVirtualRegister(Reg) || !Reg)
880 return;
881 // Remove the values that don't define those lanes.
882 SmallVector<VNInfo *, 8> ToBeRemoved;
883 for (VNInfo *VNI : SR.valnos) {
884 if (VNI->isUnused())
885 continue;
886 // PHI definitions don't have MI attached, so there is nothing
887 // we can use to strip the VNI.
888 if (VNI->isPHIDef())
889 continue;
890 const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
891 assert(MI && "Cannot find the definition of a value");
892 bool hasDef = false;
893 for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
894 if (!MOI->isReg() || !MOI->isDef())
895 continue;
896 if (MOI->getReg() != Reg)
897 continue;
898 LaneBitmask OrigMask = TRI.getSubRegIndexLaneMask(MOI->getSubReg());
899 LaneBitmask ExpectedDefMask =
900 ComposeSubRegIdx
901 ? TRI.composeSubRegIndexLaneMask(ComposeSubRegIdx, OrigMask)
902 : OrigMask;
903 if ((ExpectedDefMask & LaneMask).none())
904 continue;
905 hasDef = true;
906 break;
907 }
908
909 if (!hasDef)
910 ToBeRemoved.push_back(VNI);
911 }
912 for (VNInfo *VNI : ToBeRemoved)
913 SR.removeValNo(VNI);
914
915 // If the subrange is empty at this point, the MIR is invalid. Do not assert
916 // and let the verifier catch this case.
917}
918
920 BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
921 std::function<void(LiveInterval::SubRange &)> Apply,
922 const SlotIndexes &Indexes, const TargetRegisterInfo &TRI,
923 unsigned ComposeSubRegIdx) {
924 LaneBitmask ToApply = LaneMask;
925 for (SubRange &SR : subranges()) {
926 LaneBitmask SRMask = SR.LaneMask;
927 LaneBitmask Matching = SRMask & LaneMask;
928 if (Matching.none())
929 continue;
930
931 SubRange *MatchingRange;
932 if (SRMask == Matching) {
933 // The subrange fits (it does not cover bits outside \p LaneMask).
934 MatchingRange = &SR;
935 } else {
936 // We have to split the subrange into a matching and non-matching part.
937 // Reduce lanemask of existing lane to non-matching part.
938 SR.LaneMask = SRMask & ~Matching;
939 // Create a new subrange for the matching part
940 MatchingRange = createSubRangeFrom(Allocator, Matching, SR);
941 // Now that the subrange is split in half, make sure we
942 // only keep in the subranges the VNIs that touch the related half.
943 stripValuesNotDefiningMask(reg(), *MatchingRange, Matching, Indexes, TRI,
944 ComposeSubRegIdx);
945 stripValuesNotDefiningMask(reg(), SR, SR.LaneMask, Indexes, TRI,
946 ComposeSubRegIdx);
947 }
948 Apply(*MatchingRange);
949 ToApply &= ~Matching;
950 }
951 // Create a new subrange if there are uncovered bits left.
952 if (ToApply.any()) {
953 SubRange *NewRange = createSubRange(Allocator, ToApply);
954 Apply(*NewRange);
955 }
956}
957
958unsigned LiveInterval::getSize() const {
959 unsigned Sum = 0;
960 for (const Segment &S : segments)
961 Sum += S.start.distance(S.end);
962 return Sum;
963}
964
966 LaneBitmask LaneMask,
968 const SlotIndexes &Indexes) const {
969 assert(reg().isVirtual());
970 LaneBitmask VRegMask = MRI.getMaxLaneMaskForVReg(reg());
971 assert((VRegMask & LaneMask).any());
972 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
973 for (const MachineOperand &MO : MRI.def_operands(reg())) {
974 if (!MO.isUndef())
975 continue;
976 unsigned SubReg = MO.getSubReg();
977 assert(SubReg != 0 && "Undef should only be set on subreg defs");
978 LaneBitmask DefMask = TRI.getSubRegIndexLaneMask(SubReg);
979 LaneBitmask UndefMask = VRegMask & ~DefMask;
980 if ((UndefMask & LaneMask).any()) {
981 const MachineInstr &MI = *MO.getParent();
982 bool EarlyClobber = MO.isEarlyClobber();
983 SlotIndex Pos = Indexes.getInstructionIndex(MI).getRegSlot(EarlyClobber);
984 Undefs.push_back(Pos);
985 }
986 }
987}
988
990 return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';
991}
992
993#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
995 dbgs() << *this << '\n';
996}
997#endif
998
1000 if (empty())
1001 OS << "EMPTY";
1002 else {
1003 for (const Segment &S : segments) {
1004 OS << S;
1005 assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
1006 }
1007 }
1008
1009 // Print value number info.
1010 if (getNumValNums()) {
1011 OS << ' ';
1012 unsigned vnum = 0;
1013 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
1014 ++i, ++vnum) {
1015 const VNInfo *vni = *i;
1016 if (vnum) OS << ' ';
1017 OS << vnum << '@';
1018 if (vni->isUnused()) {
1019 OS << 'x';
1020 } else {
1021 OS << vni->def;
1022 if (vni->isPHIDef())
1023 OS << "-phi";
1024 }
1025 }
1026 }
1027}
1028
1030 OS << " L" << PrintLaneMask(LaneMask) << ' '
1031 << static_cast<const LiveRange &>(*this);
1032}
1033
1035 OS << printReg(reg()) << ' ';
1036 super::print(OS);
1037 // Print subranges
1038 for (const SubRange &SR : subranges())
1039 OS << SR;
1040 OS << " weight:" << Weight;
1041}
1042
1043#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1045 dbgs() << *this << '\n';
1046}
1047
1049 dbgs() << *this << '\n';
1050}
1051
1053 dbgs() << *this << '\n';
1054}
1055#endif
1056
1057#ifndef NDEBUG
1058void LiveRange::verify() const {
1059 for (const_iterator I = begin(), E = end(); I != E; ++I) {
1060 assert(I->start.isValid());
1061 assert(I->end.isValid());
1062 assert(I->start < I->end);
1063 assert(I->valno != nullptr);
1064 assert(I->valno->id < valnos.size());
1065 assert(I->valno == valnos[I->valno->id]);
1066 if (std::next(I) != E) {
1067 assert(I->end <= std::next(I)->start);
1068 if (I->end == std::next(I)->start)
1069 assert(I->valno != std::next(I)->valno);
1070 }
1071 }
1072}
1073
1075 super::verify();
1076
1077 // Make sure SubRanges are fine and LaneMasks are disjunct.
1078 LaneBitmask Mask;
1079 LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg())
1081 for (const SubRange &SR : subranges()) {
1082 // Subrange lanemask should be disjunct to any previous subrange masks.
1083 assert((Mask & SR.LaneMask).none());
1084 Mask |= SR.LaneMask;
1085
1086 // subrange mask should not contained in maximum lane mask for the vreg.
1087 assert((Mask & ~MaxMask).none());
1088 // empty subranges must be removed.
1089 assert(!SR.empty());
1090
1091 SR.verify();
1092 // Main liverange should cover subrange.
1093 assert(covers(SR));
1094 }
1095}
1096#endif
1097
1098//===----------------------------------------------------------------------===//
1099// LiveRangeUpdater class
1100//===----------------------------------------------------------------------===//
1101//
1102// The LiveRangeUpdater class always maintains these invariants:
1103//
1104// - When LastStart is invalid, Spills is empty and the iterators are invalid.
1105// This is the initial state, and the state created by flush().
1106// In this state, isDirty() returns false.
1107//
1108// Otherwise, segments are kept in three separate areas:
1109//
1110// 1. [begin; WriteI) at the front of LR.
1111// 2. [ReadI; end) at the back of LR.
1112// 3. Spills.
1113//
1114// - LR.begin() <= WriteI <= ReadI <= LR.end().
1115// - Segments in all three areas are fully ordered and coalesced.
1116// - Segments in area 1 precede and can't coalesce with segments in area 2.
1117// - Segments in Spills precede and can't coalesce with segments in area 2.
1118// - No coalescing is possible between segments in Spills and segments in area
1119// 1, and there are no overlapping segments.
1120//
1121// The segments in Spills are not ordered with respect to the segments in area
1122// 1. They need to be merged.
1123//
1124// When they exist, Spills.back().start <= LastStart,
1125// and WriteI[-1].start <= LastStart.
1126
1127#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1129 if (!isDirty()) {
1130 if (LR)
1131 OS << "Clean updater: " << *LR << '\n';
1132 else
1133 OS << "Null updater.\n";
1134 return;
1135 }
1136 assert(LR && "Can't have null LR in dirty updater.");
1137 OS << " updater with gap = " << (ReadI - WriteI)
1138 << ", last start = " << LastStart
1139 << ":\n Area 1:";
1140 for (const auto &S : make_range(LR->begin(), WriteI))
1141 OS << ' ' << S;
1142 OS << "\n Spills:";
1143 for (unsigned I = 0, E = Spills.size(); I != E; ++I)
1144 OS << ' ' << Spills[I];
1145 OS << "\n Area 2:";
1146 for (const auto &S : make_range(ReadI, LR->end()))
1147 OS << ' ' << S;
1148 OS << '\n';
1149}
1150
1152 print(errs());
1153}
1154#endif
1155
1156// Determine if A and B should be coalesced.
1157static inline bool coalescable(const LiveRange::Segment &A,
1158 const LiveRange::Segment &B) {
1159 assert(A.start <= B.start && "Unordered live segments.");
1160 if (A.end == B.start)
1161 return A.valno == B.valno;
1162 if (A.end < B.start)
1163 return false;
1164 assert(A.valno == B.valno && "Cannot overlap different values");
1165 return true;
1166}
1167
1169 assert(LR && "Cannot add to a null destination");
1170
1171 // Fall back to the regular add method if the live range
1172 // is using the segment set instead of the segment vector.
1173 if (LR->segmentSet != nullptr) {
1174 LR->addSegmentToSet(Seg);
1175 return;
1176 }
1177
1178 // Flush the state if Start moves backwards.
1179 if (!LastStart.isValid() || LastStart > Seg.start) {
1180 if (isDirty())
1181 flush();
1182 // This brings us to an uninitialized state. Reinitialize.
1183 assert(Spills.empty() && "Leftover spilled segments");
1184 WriteI = ReadI = LR->begin();
1185 }
1186
1187 // Remember start for next time.
1188 LastStart = Seg.start;
1189
1190 // Advance ReadI until it ends after Seg.start.
1191 LiveRange::iterator E = LR->end();
1192 if (ReadI != E && ReadI->end <= Seg.start) {
1193 // First try to close the gap between WriteI and ReadI with spills.
1194 if (ReadI != WriteI)
1195 mergeSpills();
1196 // Then advance ReadI.
1197 if (ReadI == WriteI)
1198 ReadI = WriteI = LR->find(Seg.start);
1199 else
1200 while (ReadI != E && ReadI->end <= Seg.start)
1201 *WriteI++ = *ReadI++;
1202 }
1203
1204 assert(ReadI == E || ReadI->end > Seg.start);
1205
1206 // Check if the ReadI segment begins early.
1207 if (ReadI != E && ReadI->start <= Seg.start) {
1208 assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1209 // Bail if Seg is completely contained in ReadI.
1210 if (ReadI->end >= Seg.end)
1211 return;
1212 // Coalesce into Seg.
1213 Seg.start = ReadI->start;
1214 ++ReadI;
1215 }
1216
1217 // Coalesce as much as possible from ReadI into Seg.
1218 while (ReadI != E && coalescable(Seg, *ReadI)) {
1219 Seg.end = std::max(Seg.end, ReadI->end);
1220 ++ReadI;
1221 }
1222
1223 // Try coalescing Spills.back() into Seg.
1224 if (!Spills.empty() && coalescable(Spills.back(), Seg)) {
1225 Seg.start = Spills.back().start;
1226 Seg.end = std::max(Spills.back().end, Seg.end);
1227 Spills.pop_back();
1228 }
1229
1230 // Try coalescing Seg into WriteI[-1].
1231 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {
1232 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1233 return;
1234 }
1235
1236 // Seg doesn't coalesce with anything, and needs to be inserted somewhere.
1237 if (WriteI != ReadI) {
1238 *WriteI++ = Seg;
1239 return;
1240 }
1241
1242 // Finally, append to LR or Spills.
1243 if (WriteI == E) {
1244 LR->segments.push_back(Seg);
1245 WriteI = ReadI = LR->end();
1246 } else
1247 Spills.push_back(Seg);
1248}
1249
1250// Merge as many spilled segments as possible into the gap between WriteI
1251// and ReadI. Advance WriteI to reflect the inserted instructions.
1252void LiveRangeUpdater::mergeSpills() {
1253 // Perform a backwards merge of Spills and [SpillI;WriteI).
1254 size_t GapSize = ReadI - WriteI;
1255 size_t NumMoved = std::min(Spills.size(), GapSize);
1256 LiveRange::iterator Src = WriteI;
1257 LiveRange::iterator Dst = Src + NumMoved;
1258 LiveRange::iterator SpillSrc = Spills.end();
1259 LiveRange::iterator B = LR->begin();
1260
1261 // This is the new WriteI position after merging spills.
1262 WriteI = Dst;
1263
1264 // Now merge Src and Spills backwards.
1265 while (Src != Dst) {
1266 if (Src != B && Src[-1].start > SpillSrc[-1].start)
1267 *--Dst = *--Src;
1268 else
1269 *--Dst = *--SpillSrc;
1270 }
1271 assert(NumMoved == size_t(Spills.end() - SpillSrc));
1272 Spills.erase(SpillSrc, Spills.end());
1273}
1274
1276 if (!isDirty())
1277 return;
1278 // Clear the dirty state.
1279 LastStart = SlotIndex();
1280
1281 assert(LR && "Cannot add to a null destination");
1282
1283 // Nothing to merge?
1284 if (Spills.empty()) {
1285 LR->segments.erase(WriteI, ReadI);
1286 LR->verify();
1287 return;
1288 }
1289
1290 // Resize the WriteI - ReadI gap to match Spills.
1291 size_t GapSize = ReadI - WriteI;
1292 if (GapSize < Spills.size()) {
1293 // The gap is too small. Make some room.
1294 size_t WritePos = WriteI - LR->begin();
1295 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1296 // This also invalidated ReadI, but it is recomputed below.
1297 WriteI = LR->begin() + WritePos;
1298 } else {
1299 // Shrink the gap if necessary.
1300 LR->segments.erase(WriteI + Spills.size(), ReadI);
1301 }
1302 ReadI = WriteI + Spills.size();
1303 mergeSpills();
1304 LR->verify();
1305}
1306
1308 // Create initial equivalence classes.
1309 EqClass.clear();
1310 EqClass.grow(LR.getNumValNums());
1311
1312 const VNInfo *used = nullptr, *unused = nullptr;
1313
1314 // Determine connections.
1315 for (const VNInfo *VNI : LR.valnos) {
1316 // Group all unused values into one class.
1317 if (VNI->isUnused()) {
1318 if (unused)
1319 EqClass.join(unused->id, VNI->id);
1320 unused = VNI;
1321 continue;
1322 }
1323 used = VNI;
1324 if (VNI->isPHIDef()) {
1325 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1326 assert(MBB && "Phi-def has no defining MBB");
1327 // Connect to values live out of predecessors.
1328 for (MachineBasicBlock *Pred : MBB->predecessors())
1329 if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(Pred)))
1330 EqClass.join(VNI->id, PVNI->id);
1331 } else {
1332 // Normal value defined by an instruction. Check for two-addr redef.
1333 // FIXME: This could be coincidental. Should we really check for a tied
1334 // operand constraint?
1335 // Note that VNI->def may be a use slot for an early clobber def.
1336 if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
1337 EqClass.join(VNI->id, UVNI->id);
1338 }
1339 }
1340
1341 // Lump all the unused values in with the last used value.
1342 if (used && unused)
1343 EqClass.join(used->id, unused->id);
1344
1345 EqClass.compress();
1346 return EqClass.getNumClasses();
1347}
1348
1351 // Rewrite instructions.
1352 for (MachineOperand &MO :
1353 llvm::make_early_inc_range(MRI.reg_operands(LI.reg()))) {
1354 MachineInstr *MI = MO.getParent();
1355 const VNInfo *VNI;
1356 if (MI->isDebugValue()) {
1357 // DBG_VALUE instructions don't have slot indexes, so get the index of
1358 // the instruction before them. The value is defined there too.
1359 SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);
1360 VNI = LI.Query(Idx).valueOut();
1361 } else {
1362 SlotIndex Idx = LIS.getInstructionIndex(*MI);
1363 LiveQueryResult LRQ = LI.Query(Idx);
1364 VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
1365 }
1366 // In the case of an <undef> use that isn't tied to any def, VNI will be
1367 // NULL. If the use is tied to a def, VNI will be the defined value.
1368 if (!VNI)
1369 continue;
1370 if (unsigned EqClass = getEqClass(VNI))
1371 MO.setReg(LIV[EqClass - 1]->reg());
1372 }
1373
1374 // Distribute subregister liveranges.
1375 if (LI.hasSubRanges()) {
1376 unsigned NumComponents = EqClass.getNumClasses();
1377 SmallVector<unsigned, 8> VNIMapping;
1379 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1380 for (LiveInterval::SubRange &SR : LI.subranges()) {
1381 // Create new subranges in the split intervals and construct a mapping
1382 // for the VNInfos in the subrange.
1383 unsigned NumValNos = SR.valnos.size();
1384 VNIMapping.clear();
1385 VNIMapping.reserve(NumValNos);
1386 SubRanges.clear();
1387 SubRanges.resize(NumComponents-1, nullptr);
1388 for (unsigned I = 0; I < NumValNos; ++I) {
1389 const VNInfo &VNI = *SR.valnos[I];
1390 unsigned ComponentNum;
1391 if (VNI.isUnused()) {
1392 ComponentNum = 0;
1393 } else {
1394 const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def);
1395 assert(MainRangeVNI != nullptr
1396 && "SubRange def must have corresponding main range def");
1397 ComponentNum = getEqClass(MainRangeVNI);
1398 if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {
1399 SubRanges[ComponentNum-1]
1400 = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);
1401 }
1402 }
1403 VNIMapping.push_back(ComponentNum);
1404 }
1405 DistributeRange(SR, SubRanges.data(), VNIMapping);
1406 }
1408 }
1409
1410 // Distribute main liverange.
1411 DistributeRange(LI, LIV, EqClass);
1412}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
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")
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
static bool coalescable(const LiveRange::Segment &A, const LiveRange::Segment &B)
static void stripValuesNotDefiningMask(unsigned Reg, LiveInterval::SubRange &SR, LaneBitmask LaneMask, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx)
For each VNI in SR, check whether or not that value defines part of the mask describe by LaneMask and...
This file contains helper functions to modify live ranges.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
place backedge safepoints impl
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 SmallPtrSet class.
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
iterator end() const
Definition: ArrayRef.h:154
iterator begin() const
Definition: ArrayRef.h:153
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
A helper class for register coalescers.
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.
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
A live range for subregisters.
Definition: LiveInterval.h:694
void print(raw_ostream &OS) const
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...
Register reg() const
Definition: LiveInterval.h:718
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:810
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...
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.
void print(raw_ostream &OS) const
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 clearSubRanges()
Removes all subregister liveness information.
Result of a LiveRange query.
Definition: LiveInterval.h:90
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
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:941
void print(raw_ostream &) const
void flush()
Flush the updater state to LR so it is valid and contains all added segments.
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
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
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...
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
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
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
std::unique_ptr< SegmentSet > segmentSet
Definition: LiveInterval.h:210
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
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
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:429
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
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
Segments segments
Definition: LiveInterval.h:203
VNInfoList valnos
Definition: LiveInterval.h:204
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 ...
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
vni_iterator vni_end()
Definition: LiveInterval.h:225
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
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 dump() const
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().
bool isValid() const
isValid - Returns true until all the operands have been visited.
iterator_range< pred_iterator > predecessors()
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:176
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:182
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:252
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:237
SlotIndexes pass.
Definition: SlotIndexes.h:297
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:379
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:397
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:367
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
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 reserve(size_type N)
Definition: SmallVector.h:676
iterator erase(const_iterator CI)
Definition: SmallVector.h:750
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:818
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:299
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
Definition: LiveInterval.h:70
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
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.
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:2033
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:92
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1974
static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], EqClassesT VNIClasses)
Helper function that distributes live range value numbers and the corresponding segments of a primary...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Other
Any other memory.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1961
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2082
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
ListT< IteratorSpecifierT< T, I, E > > IteratorT
Definition: ClauseT.h:274
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool none() const
Definition: LaneBitmask.h:52
constexpr bool any() const
Definition: LaneBitmask.h:53
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162