LLVM 17.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");
475 const_iterator I = lower_bound(*this, End);
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
566/// Remove the specified segment from this range. Note that the segment must
567/// be in a single Segment in its entirety.
569 bool RemoveDeadValNo) {
570 // Find the Segment containing this span.
571 iterator I = find(Start);
572 assert(I != end() && "Segment is not in range!");
573 assert(I->containsInterval(Start, End)
574 && "Segment is not entirely in range!");
575
576 // If the span we are removing is at the start of the Segment, adjust it.
577 VNInfo *ValNo = I->valno;
578 if (I->start == Start) {
579 if (I->end == End) {
580 segments.erase(I); // Removed the whole Segment.
581
582 if (RemoveDeadValNo)
583 removeValNoIfDead(ValNo);
584 } else
585 I->start = End;
586 return;
587 }
588
589 // Otherwise if the span we are removing is at the end of the Segment,
590 // adjust the other way.
591 if (I->end == End) {
592 I->end = Start;
593 return;
594 }
595
596 // Otherwise, we are splitting the Segment into two pieces.
597 SlotIndex OldEnd = I->end;
598 I->end = Start; // Trim the old segment.
599
600 // Insert the new one.
601 segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
602}
603
605 VNInfo *ValNo = I->valno;
606 I = segments.erase(I);
607 if (RemoveDeadValNo)
608 removeValNoIfDead(ValNo);
609 return I;
610}
611
613 if (none_of(*this, [=](const Segment &S) { return S.valno == ValNo; }))
614 markValNoForDeletion(ValNo);
615}
616
617/// removeValNo - Remove all the segments defined by the specified value#.
618/// Also remove the value# from value# list.
620 if (empty()) return;
622 [ValNo](const Segment &S) { return S.valno == ValNo; });
623 // Now that ValNo is dead, remove it.
624 markValNoForDeletion(ValNo);
625}
626
628 const int *LHSValNoAssignments,
629 const int *RHSValNoAssignments,
630 SmallVectorImpl<VNInfo *> &NewVNInfo) {
631 verify();
632
633 // Determine if any of our values are mapped. This is uncommon, so we want
634 // to avoid the range scan if not.
635 bool MustMapCurValNos = false;
636 unsigned NumVals = getNumValNums();
637 unsigned NumNewVals = NewVNInfo.size();
638 for (unsigned i = 0; i != NumVals; ++i) {
639 unsigned LHSValID = LHSValNoAssignments[i];
640 if (i != LHSValID ||
641 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
642 MustMapCurValNos = true;
643 break;
644 }
645 }
646
647 // If we have to apply a mapping to our base range assignment, rewrite it now.
648 if (MustMapCurValNos && !empty()) {
649 // Map the first live range.
650
651 iterator OutIt = begin();
652 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
653 for (iterator I = std::next(OutIt), E = end(); I != E; ++I) {
654 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
655 assert(nextValNo && "Huh?");
656
657 // If this live range has the same value # as its immediate predecessor,
658 // and if they are neighbors, remove one Segment. This happens when we
659 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
660 if (OutIt->valno == nextValNo && OutIt->end == I->start) {
661 OutIt->end = I->end;
662 } else {
663 // Didn't merge. Move OutIt to the next segment,
664 ++OutIt;
665 OutIt->valno = nextValNo;
666 if (OutIt != I) {
667 OutIt->start = I->start;
668 OutIt->end = I->end;
669 }
670 }
671 }
672 // If we merge some segments, chop off the end.
673 ++OutIt;
674 segments.erase(OutIt, end());
675 }
676
677 // Rewrite Other values before changing the VNInfo ids.
678 // This can leave Other in an invalid state because we're not coalescing
679 // touching segments that now have identical values. That's OK since Other is
680 // not supposed to be valid after calling join();
681 for (Segment &S : Other.segments)
682 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
683
684 // Update val# info. Renumber them and make sure they all belong to this
685 // LiveRange now. Also remove dead val#'s.
686 unsigned NumValNos = 0;
687 for (unsigned i = 0; i < NumNewVals; ++i) {
688 VNInfo *VNI = NewVNInfo[i];
689 if (VNI) {
690 if (NumValNos >= NumVals)
691 valnos.push_back(VNI);
692 else
693 valnos[NumValNos] = VNI;
694 VNI->id = NumValNos++; // Renumber val#.
695 }
696 }
697 if (NumNewVals < NumVals)
698 valnos.resize(NumNewVals); // shrinkify
699
700 // Okay, now insert the RHS live segments into the LHS.
701 LiveRangeUpdater Updater(this);
702 for (Segment &S : Other.segments)
703 Updater.add(S);
704}
705
706/// Merge all of the segments in RHS into this live range as the specified
707/// value number. The segments in RHS are allowed to overlap with segments in
708/// the current range, but only if the overlapping segments have the
709/// specified value number.
711 VNInfo *LHSValNo) {
712 LiveRangeUpdater Updater(this);
713 for (const Segment &S : RHS.segments)
714 Updater.add(S.start, S.end, LHSValNo);
715}
716
717/// MergeValueInAsValue - Merge all of the live segments of a specific val#
718/// in RHS into this live range as the specified value number.
719/// The segments in RHS are allowed to overlap with segments in the
720/// current range, it will replace the value numbers of the overlaped
721/// segments with the specified value number.
723 const VNInfo *RHSValNo,
724 VNInfo *LHSValNo) {
725 LiveRangeUpdater Updater(this);
726 for (const Segment &S : RHS.segments)
727 if (S.valno == RHSValNo)
728 Updater.add(S.start, S.end, LHSValNo);
729}
730
731/// MergeValueNumberInto - This method is called when two value nubmers
732/// are found to be equivalent. This eliminates V1, replacing all
733/// segments with the V1 value number with the V2 value number. This can
734/// cause merging of V1/V2 values numbers and compaction of the value space.
736 assert(V1 != V2 && "Identical value#'s are always equivalent!");
737
738 // This code actually merges the (numerically) larger value number into the
739 // smaller value number, which is likely to allow us to compactify the value
740 // space. The only thing we have to be careful of is to preserve the
741 // instruction that defines the result value.
742
743 // Make sure V2 is smaller than V1.
744 if (V1->id < V2->id) {
745 V1->copyFrom(*V2);
746 std::swap(V1, V2);
747 }
748
749 // Merge V1 segments into V2.
750 for (iterator I = begin(); I != end(); ) {
751 iterator S = I++;
752 if (S->valno != V1) continue; // Not a V1 Segment.
753
754 // Okay, we found a V1 live range. If it had a previous, touching, V2 live
755 // range, extend it.
756 if (S != begin()) {
757 iterator Prev = S-1;
758 if (Prev->valno == V2 && Prev->end == S->start) {
759 Prev->end = S->end;
760
761 // Erase this live-range.
762 segments.erase(S);
763 I = Prev+1;
764 S = Prev;
765 }
766 }
767
768 // Okay, now we have a V1 or V2 live range that is maximally merged forward.
769 // Ensure that it is a V2 live-range.
770 S->valno = V2;
771
772 // If we can merge it into later V2 segments, do so now. We ignore any
773 // following V1 segments, as they will be merged in subsequent iterations
774 // of the loop.
775 if (I != end()) {
776 if (I->start == S->end && I->valno == V2) {
777 S->end = I->end;
779 I = S+1;
780 }
781 }
782 }
783
784 // Now that V1 is dead, remove it.
785 markValNoForDeletion(V1);
786
787 return V2;
788}
789
791 assert(segmentSet != nullptr && "segment set must have been created");
792 assert(
793 segments.empty() &&
794 "segment set can be used only initially before switching to the array");
795 segments.append(segmentSet->begin(), segmentSet->end());
796 segmentSet = nullptr;
797 verify();
798}
799
801 ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
802 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
803
804 // If there are no regmask slots, we have nothing to search.
805 if (SlotI == SlotE)
806 return false;
807
808 // Start our search at the first segment that ends after the first slot.
809 const_iterator SegmentI = find(*SlotI);
810 const_iterator SegmentE = end();
811
812 // If there are no segments that end after the first slot, we're done.
813 if (SegmentI == SegmentE)
814 return false;
815
816 // Look for each slot in the live range.
817 for ( ; SlotI != SlotE; ++SlotI) {
818 // Go to the next segment that ends after the current slot.
819 // The slot may be within a hole in the range.
820 SegmentI = advanceTo(SegmentI, *SlotI);
821 if (SegmentI == SegmentE)
822 return false;
823
824 // If this segment contains the slot, we're done.
825 if (SegmentI->contains(*SlotI))
826 return true;
827 // Otherwise, look for the next slot.
828 }
829
830 // We didn't find a segment containing any of the slots.
831 return false;
832}
833
834void LiveInterval::freeSubRange(SubRange *S) {
835 S->~SubRange();
836 // Memory was allocated with BumpPtr allocator and is not freed here.
837}
838
840 SubRange **NextPtr = &SubRanges;
841 SubRange *I = *NextPtr;
842 while (I != nullptr) {
843 if (!I->empty()) {
844 NextPtr = &I->Next;
845 I = *NextPtr;
846 continue;
847 }
848 // Skip empty subranges until we find the first nonempty one.
849 do {
850 SubRange *Next = I->Next;
851 freeSubRange(I);
852 I = Next;
853 } while (I != nullptr && I->empty());
854 *NextPtr = I;
855 }
856}
857
859 for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
860 Next = I->Next;
861 freeSubRange(I);
862 }
863 SubRanges = nullptr;
864}
865
866/// For each VNI in \p SR, check whether or not that value defines part
867/// of the mask describe by \p LaneMask and if not, remove that value
868/// from \p SR.
870 LaneBitmask LaneMask,
871 const SlotIndexes &Indexes,
872 const TargetRegisterInfo &TRI,
873 unsigned ComposeSubRegIdx) {
874 // Phys reg should not be tracked at subreg level.
875 // Same for noreg (Reg == 0).
876 if (!Register::isVirtualRegister(Reg) || !Reg)
877 return;
878 // Remove the values that don't define those lanes.
879 SmallVector<VNInfo *, 8> ToBeRemoved;
880 for (VNInfo *VNI : SR.valnos) {
881 if (VNI->isUnused())
882 continue;
883 // PHI definitions don't have MI attached, so there is nothing
884 // we can use to strip the VNI.
885 if (VNI->isPHIDef())
886 continue;
887 const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
888 assert(MI && "Cannot find the definition of a value");
889 bool hasDef = false;
890 for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
891 if (!MOI->isReg() || !MOI->isDef())
892 continue;
893 if (MOI->getReg() != Reg)
894 continue;
895 LaneBitmask OrigMask = TRI.getSubRegIndexLaneMask(MOI->getSubReg());
896 LaneBitmask ExpectedDefMask =
897 ComposeSubRegIdx
898 ? TRI.composeSubRegIndexLaneMask(ComposeSubRegIdx, OrigMask)
899 : OrigMask;
900 if ((ExpectedDefMask & LaneMask).none())
901 continue;
902 hasDef = true;
903 break;
904 }
905
906 if (!hasDef)
907 ToBeRemoved.push_back(VNI);
908 }
909 for (VNInfo *VNI : ToBeRemoved)
910 SR.removeValNo(VNI);
911
912 // If the subrange is empty at this point, the MIR is invalid. Do not assert
913 // and let the verifier catch this case.
914}
915
917 BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
918 std::function<void(LiveInterval::SubRange &)> Apply,
919 const SlotIndexes &Indexes, const TargetRegisterInfo &TRI,
920 unsigned ComposeSubRegIdx) {
921 LaneBitmask ToApply = LaneMask;
922 for (SubRange &SR : subranges()) {
923 LaneBitmask SRMask = SR.LaneMask;
924 LaneBitmask Matching = SRMask & LaneMask;
925 if (Matching.none())
926 continue;
927
928 SubRange *MatchingRange;
929 if (SRMask == Matching) {
930 // The subrange fits (it does not cover bits outside \p LaneMask).
931 MatchingRange = &SR;
932 } else {
933 // We have to split the subrange into a matching and non-matching part.
934 // Reduce lanemask of existing lane to non-matching part.
935 SR.LaneMask = SRMask & ~Matching;
936 // Create a new subrange for the matching part
937 MatchingRange = createSubRangeFrom(Allocator, Matching, SR);
938 // Now that the subrange is split in half, make sure we
939 // only keep in the subranges the VNIs that touch the related half.
940 stripValuesNotDefiningMask(reg(), *MatchingRange, Matching, Indexes, TRI,
941 ComposeSubRegIdx);
942 stripValuesNotDefiningMask(reg(), SR, SR.LaneMask, Indexes, TRI,
943 ComposeSubRegIdx);
944 }
945 Apply(*MatchingRange);
946 ToApply &= ~Matching;
947 }
948 // Create a new subrange if there are uncovered bits left.
949 if (ToApply.any()) {
950 SubRange *NewRange = createSubRange(Allocator, ToApply);
951 Apply(*NewRange);
952 }
953}
954
955unsigned LiveInterval::getSize() const {
956 unsigned Sum = 0;
957 for (const Segment &S : segments)
958 Sum += S.start.distance(S.end);
959 return Sum;
960}
961
963 LaneBitmask LaneMask,
965 const SlotIndexes &Indexes) const {
966 assert(reg().isVirtual());
967 LaneBitmask VRegMask = MRI.getMaxLaneMaskForVReg(reg());
968 assert((VRegMask & LaneMask).any());
969 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
970 for (const MachineOperand &MO : MRI.def_operands(reg())) {
971 if (!MO.isUndef())
972 continue;
973 unsigned SubReg = MO.getSubReg();
974 assert(SubReg != 0 && "Undef should only be set on subreg defs");
975 LaneBitmask DefMask = TRI.getSubRegIndexLaneMask(SubReg);
976 LaneBitmask UndefMask = VRegMask & ~DefMask;
977 if ((UndefMask & LaneMask).any()) {
978 const MachineInstr &MI = *MO.getParent();
979 bool EarlyClobber = MO.isEarlyClobber();
980 SlotIndex Pos = Indexes.getInstructionIndex(MI).getRegSlot(EarlyClobber);
981 Undefs.push_back(Pos);
982 }
983 }
984}
985
987 return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';
988}
989
990#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
992 dbgs() << *this << '\n';
993}
994#endif
995
997 if (empty())
998 OS << "EMPTY";
999 else {
1000 for (const Segment &S : segments) {
1001 OS << S;
1002 assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
1003 }
1004 }
1005
1006 // Print value number info.
1007 if (getNumValNums()) {
1008 OS << ' ';
1009 unsigned vnum = 0;
1010 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
1011 ++i, ++vnum) {
1012 const VNInfo *vni = *i;
1013 if (vnum) OS << ' ';
1014 OS << vnum << '@';
1015 if (vni->isUnused()) {
1016 OS << 'x';
1017 } else {
1018 OS << vni->def;
1019 if (vni->isPHIDef())
1020 OS << "-phi";
1021 }
1022 }
1023 }
1024}
1025
1027 OS << " L" << PrintLaneMask(LaneMask) << ' '
1028 << static_cast<const LiveRange &>(*this);
1029}
1030
1032 OS << printReg(reg()) << ' ';
1033 super::print(OS);
1034 // Print subranges
1035 for (const SubRange &SR : subranges())
1036 OS << SR;
1037 OS << " weight:" << Weight;
1038}
1039
1040#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1042 dbgs() << *this << '\n';
1043}
1044
1046 dbgs() << *this << '\n';
1047}
1048
1050 dbgs() << *this << '\n';
1051}
1052#endif
1053
1054#ifndef NDEBUG
1055void LiveRange::verify() const {
1056 for (const_iterator I = begin(), E = end(); I != E; ++I) {
1057 assert(I->start.isValid());
1058 assert(I->end.isValid());
1059 assert(I->start < I->end);
1060 assert(I->valno != nullptr);
1061 assert(I->valno->id < valnos.size());
1062 assert(I->valno == valnos[I->valno->id]);
1063 if (std::next(I) != E) {
1064 assert(I->end <= std::next(I)->start);
1065 if (I->end == std::next(I)->start)
1066 assert(I->valno != std::next(I)->valno);
1067 }
1068 }
1069}
1070
1072 super::verify();
1073
1074 // Make sure SubRanges are fine and LaneMasks are disjunct.
1075 LaneBitmask Mask;
1076 LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg())
1078 for (const SubRange &SR : subranges()) {
1079 // Subrange lanemask should be disjunct to any previous subrange masks.
1080 assert((Mask & SR.LaneMask).none());
1081 Mask |= SR.LaneMask;
1082
1083 // subrange mask should not contained in maximum lane mask for the vreg.
1084 assert((Mask & ~MaxMask).none());
1085 // empty subranges must be removed.
1086 assert(!SR.empty());
1087
1088 SR.verify();
1089 // Main liverange should cover subrange.
1090 assert(covers(SR));
1091 }
1092}
1093#endif
1094
1095//===----------------------------------------------------------------------===//
1096// LiveRangeUpdater class
1097//===----------------------------------------------------------------------===//
1098//
1099// The LiveRangeUpdater class always maintains these invariants:
1100//
1101// - When LastStart is invalid, Spills is empty and the iterators are invalid.
1102// This is the initial state, and the state created by flush().
1103// In this state, isDirty() returns false.
1104//
1105// Otherwise, segments are kept in three separate areas:
1106//
1107// 1. [begin; WriteI) at the front of LR.
1108// 2. [ReadI; end) at the back of LR.
1109// 3. Spills.
1110//
1111// - LR.begin() <= WriteI <= ReadI <= LR.end().
1112// - Segments in all three areas are fully ordered and coalesced.
1113// - Segments in area 1 precede and can't coalesce with segments in area 2.
1114// - Segments in Spills precede and can't coalesce with segments in area 2.
1115// - No coalescing is possible between segments in Spills and segments in area
1116// 1, and there are no overlapping segments.
1117//
1118// The segments in Spills are not ordered with respect to the segments in area
1119// 1. They need to be merged.
1120//
1121// When they exist, Spills.back().start <= LastStart,
1122// and WriteI[-1].start <= LastStart.
1123
1124#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1126 if (!isDirty()) {
1127 if (LR)
1128 OS << "Clean updater: " << *LR << '\n';
1129 else
1130 OS << "Null updater.\n";
1131 return;
1132 }
1133 assert(LR && "Can't have null LR in dirty updater.");
1134 OS << " updater with gap = " << (ReadI - WriteI)
1135 << ", last start = " << LastStart
1136 << ":\n Area 1:";
1137 for (const auto &S : make_range(LR->begin(), WriteI))
1138 OS << ' ' << S;
1139 OS << "\n Spills:";
1140 for (unsigned I = 0, E = Spills.size(); I != E; ++I)
1141 OS << ' ' << Spills[I];
1142 OS << "\n Area 2:";
1143 for (const auto &S : make_range(ReadI, LR->end()))
1144 OS << ' ' << S;
1145 OS << '\n';
1146}
1147
1149 print(errs());
1150}
1151#endif
1152
1153// Determine if A and B should be coalesced.
1154static inline bool coalescable(const LiveRange::Segment &A,
1155 const LiveRange::Segment &B) {
1156 assert(A.start <= B.start && "Unordered live segments.");
1157 if (A.end == B.start)
1158 return A.valno == B.valno;
1159 if (A.end < B.start)
1160 return false;
1161 assert(A.valno == B.valno && "Cannot overlap different values");
1162 return true;
1163}
1164
1166 assert(LR && "Cannot add to a null destination");
1167
1168 // Fall back to the regular add method if the live range
1169 // is using the segment set instead of the segment vector.
1170 if (LR->segmentSet != nullptr) {
1171 LR->addSegmentToSet(Seg);
1172 return;
1173 }
1174
1175 // Flush the state if Start moves backwards.
1176 if (!LastStart.isValid() || LastStart > Seg.start) {
1177 if (isDirty())
1178 flush();
1179 // This brings us to an uninitialized state. Reinitialize.
1180 assert(Spills.empty() && "Leftover spilled segments");
1181 WriteI = ReadI = LR->begin();
1182 }
1183
1184 // Remember start for next time.
1185 LastStart = Seg.start;
1186
1187 // Advance ReadI until it ends after Seg.start.
1188 LiveRange::iterator E = LR->end();
1189 if (ReadI != E && ReadI->end <= Seg.start) {
1190 // First try to close the gap between WriteI and ReadI with spills.
1191 if (ReadI != WriteI)
1192 mergeSpills();
1193 // Then advance ReadI.
1194 if (ReadI == WriteI)
1195 ReadI = WriteI = LR->find(Seg.start);
1196 else
1197 while (ReadI != E && ReadI->end <= Seg.start)
1198 *WriteI++ = *ReadI++;
1199 }
1200
1201 assert(ReadI == E || ReadI->end > Seg.start);
1202
1203 // Check if the ReadI segment begins early.
1204 if (ReadI != E && ReadI->start <= Seg.start) {
1205 assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1206 // Bail if Seg is completely contained in ReadI.
1207 if (ReadI->end >= Seg.end)
1208 return;
1209 // Coalesce into Seg.
1210 Seg.start = ReadI->start;
1211 ++ReadI;
1212 }
1213
1214 // Coalesce as much as possible from ReadI into Seg.
1215 while (ReadI != E && coalescable(Seg, *ReadI)) {
1216 Seg.end = std::max(Seg.end, ReadI->end);
1217 ++ReadI;
1218 }
1219
1220 // Try coalescing Spills.back() into Seg.
1221 if (!Spills.empty() && coalescable(Spills.back(), Seg)) {
1222 Seg.start = Spills.back().start;
1223 Seg.end = std::max(Spills.back().end, Seg.end);
1224 Spills.pop_back();
1225 }
1226
1227 // Try coalescing Seg into WriteI[-1].
1228 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {
1229 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1230 return;
1231 }
1232
1233 // Seg doesn't coalesce with anything, and needs to be inserted somewhere.
1234 if (WriteI != ReadI) {
1235 *WriteI++ = Seg;
1236 return;
1237 }
1238
1239 // Finally, append to LR or Spills.
1240 if (WriteI == E) {
1241 LR->segments.push_back(Seg);
1242 WriteI = ReadI = LR->end();
1243 } else
1244 Spills.push_back(Seg);
1245}
1246
1247// Merge as many spilled segments as possible into the gap between WriteI
1248// and ReadI. Advance WriteI to reflect the inserted instructions.
1249void LiveRangeUpdater::mergeSpills() {
1250 // Perform a backwards merge of Spills and [SpillI;WriteI).
1251 size_t GapSize = ReadI - WriteI;
1252 size_t NumMoved = std::min(Spills.size(), GapSize);
1253 LiveRange::iterator Src = WriteI;
1254 LiveRange::iterator Dst = Src + NumMoved;
1255 LiveRange::iterator SpillSrc = Spills.end();
1256 LiveRange::iterator B = LR->begin();
1257
1258 // This is the new WriteI position after merging spills.
1259 WriteI = Dst;
1260
1261 // Now merge Src and Spills backwards.
1262 while (Src != Dst) {
1263 if (Src != B && Src[-1].start > SpillSrc[-1].start)
1264 *--Dst = *--Src;
1265 else
1266 *--Dst = *--SpillSrc;
1267 }
1268 assert(NumMoved == size_t(Spills.end() - SpillSrc));
1269 Spills.erase(SpillSrc, Spills.end());
1270}
1271
1273 if (!isDirty())
1274 return;
1275 // Clear the dirty state.
1276 LastStart = SlotIndex();
1277
1278 assert(LR && "Cannot add to a null destination");
1279
1280 // Nothing to merge?
1281 if (Spills.empty()) {
1282 LR->segments.erase(WriteI, ReadI);
1283 LR->verify();
1284 return;
1285 }
1286
1287 // Resize the WriteI - ReadI gap to match Spills.
1288 size_t GapSize = ReadI - WriteI;
1289 if (GapSize < Spills.size()) {
1290 // The gap is too small. Make some room.
1291 size_t WritePos = WriteI - LR->begin();
1292 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1293 // This also invalidated ReadI, but it is recomputed below.
1294 WriteI = LR->begin() + WritePos;
1295 } else {
1296 // Shrink the gap if necessary.
1297 LR->segments.erase(WriteI + Spills.size(), ReadI);
1298 }
1299 ReadI = WriteI + Spills.size();
1300 mergeSpills();
1301 LR->verify();
1302}
1303
1305 // Create initial equivalence classes.
1306 EqClass.clear();
1307 EqClass.grow(LR.getNumValNums());
1308
1309 const VNInfo *used = nullptr, *unused = nullptr;
1310
1311 // Determine connections.
1312 for (const VNInfo *VNI : LR.valnos) {
1313 // Group all unused values into one class.
1314 if (VNI->isUnused()) {
1315 if (unused)
1316 EqClass.join(unused->id, VNI->id);
1317 unused = VNI;
1318 continue;
1319 }
1320 used = VNI;
1321 if (VNI->isPHIDef()) {
1322 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1323 assert(MBB && "Phi-def has no defining MBB");
1324 // Connect to values live out of predecessors.
1325 for (MachineBasicBlock *Pred : MBB->predecessors())
1326 if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(Pred)))
1327 EqClass.join(VNI->id, PVNI->id);
1328 } else {
1329 // Normal value defined by an instruction. Check for two-addr redef.
1330 // FIXME: This could be coincidental. Should we really check for a tied
1331 // operand constraint?
1332 // Note that VNI->def may be a use slot for an early clobber def.
1333 if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
1334 EqClass.join(VNI->id, UVNI->id);
1335 }
1336 }
1337
1338 // Lump all the unused values in with the last used value.
1339 if (used && unused)
1340 EqClass.join(used->id, unused->id);
1341
1342 EqClass.compress();
1343 return EqClass.getNumClasses();
1344}
1345
1348 // Rewrite instructions.
1349 for (MachineOperand &MO :
1350 llvm::make_early_inc_range(MRI.reg_operands(LI.reg()))) {
1351 MachineInstr *MI = MO.getParent();
1352 const VNInfo *VNI;
1353 if (MI->isDebugValue()) {
1354 // DBG_VALUE instructions don't have slot indexes, so get the index of
1355 // the instruction before them. The value is defined there too.
1356 SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);
1357 VNI = LI.Query(Idx).valueOut();
1358 } else {
1359 SlotIndex Idx = LIS.getInstructionIndex(*MI);
1360 LiveQueryResult LRQ = LI.Query(Idx);
1361 VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
1362 }
1363 // In the case of an <undef> use that isn't tied to any def, VNI will be
1364 // NULL. If the use is tied to a def, VNI will be the defined value.
1365 if (!VNI)
1366 continue;
1367 if (unsigned EqClass = getEqClass(VNI))
1368 MO.setReg(LIV[EqClass - 1]->reg());
1369 }
1370
1371 // Distribute subregister liveranges.
1372 if (LI.hasSubRanges()) {
1373 unsigned NumComponents = EqClass.getNumClasses();
1374 SmallVector<unsigned, 8> VNIMapping;
1376 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1377 for (LiveInterval::SubRange &SR : LI.subranges()) {
1378 // Create new subranges in the split intervals and construct a mapping
1379 // for the VNInfos in the subrange.
1380 unsigned NumValNos = SR.valnos.size();
1381 VNIMapping.clear();
1382 VNIMapping.reserve(NumValNos);
1383 SubRanges.clear();
1384 SubRanges.resize(NumComponents-1, nullptr);
1385 for (unsigned I = 0; I < NumValNos; ++I) {
1386 const VNInfo &VNI = *SR.valnos[I];
1387 unsigned ComponentNum;
1388 if (VNI.isUnused()) {
1389 ComponentNum = 0;
1390 } else {
1391 const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def);
1392 assert(MainRangeVNI != nullptr
1393 && "SubRange def must have corresponding main range def");
1394 ComponentNum = getEqClass(MainRangeVNI);
1395 if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {
1396 SubRanges[ComponentNum-1]
1397 = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);
1398 }
1399 }
1400 VNIMapping.push_back(ComponentNum);
1401 }
1402 DistributeRange(SR, SubRanges.data(), VNIMapping);
1403 }
1405 }
1406
1407 // Distribute main liverange.
1408 DistributeRange(LI, LIV, EqClass);
1409}
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")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
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
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.
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:152
iterator begin() const
Definition: ArrayRef.h:151
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:693
void print(raw_ostream &OS) const
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Register reg() const
Definition: LiveInterval.h:717
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
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:794
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775
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:785
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:934
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:541
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:607
vni_iterator vni_end()
Definition: LiveInterval.h:225
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
void removeValNoIfDead(VNInfo *ValNo)
Mark ValNo for deletion if no segments in this range use it.
void dump() const
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
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:68
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static 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:82
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:204
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:274
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:259
SlotIndexes pass.
Definition: SlotIndexes.h:319
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:390
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:408
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:577
void reserve(size_type N)
Definition: SmallVector.h:667
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:289
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.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
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:1755
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1961
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:721
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:1936
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:1749
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
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:1923
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:1998
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:853
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