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