LLVM  15.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"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/Config/llvm-config.h"
36 #include "llvm/MC/LaneBitmask.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
40 #include <algorithm>
41 #include <cassert>
42 #include <cstddef>
43 #include <iterator>
44 #include <utility>
45 
46 using namespace llvm;
47 
48 namespace {
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 
64 template <typename ImplT, typename IteratorT, typename CollectionT>
65 class CalcLiveRangeUtilBase {
66 protected:
67  LiveRange *LR;
68 
69 protected:
70  CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
71 
72 public:
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.
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 
268 private:
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 
281 class CalcLiveRangeUtilVector;
282 using CalcLiveRangeUtilVectorBase =
283  CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator,
285 
286 class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {
287 public:
288  CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {}
289 
290 private:
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 
307 class CalcLiveRangeUtilSet;
308 using CalcLiveRangeUtilSetBase =
309  CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, LiveRange::SegmentSet::iterator,
311 
312 class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {
313 public:
314  CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {}
315 
316 private:
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  // This algorithm is basically std::upper_bound.
352  // Unfortunately, std::upper_bound cannot be used with mixed types until we
353  // adopt C++0x. Many libraries can do it, but not all.
354  if (empty() || Pos >= endIndex())
355  return end();
356  iterator I = begin();
357  size_t Len = size();
358  do {
359  size_t Mid = Len >> 1;
360  if (Pos < I[Mid].end) {
361  Len = Mid;
362  } else {
363  I += Mid + 1;
364  Len -= Mid + 1;
365  }
366  } while (Len);
367  return I;
368 }
369 
371  // Use the segment set, if it is available.
372  if (segmentSet != nullptr)
373  return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr);
374  // Otherwise use the segment vector.
375  return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr);
376 }
377 
379  // Use the segment set, if it is available.
380  if (segmentSet != nullptr)
381  return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);
382  // Otherwise use the segment vector.
383  return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);
384 }
385 
386 // overlaps - Return true if the intersection of the two live ranges is
387 // not empty.
388 //
389 // An example for overlaps():
390 //
391 // 0: A = ...
392 // 4: B = ...
393 // 8: C = A + B ;; last use of A
394 //
395 // The live ranges should look like:
396 //
397 // A = [3, 11)
398 // B = [7, x)
399 // C = [11, y)
400 //
401 // A->overlaps(C) should return false since we want to be able to join
402 // A and C.
403 //
405  const_iterator StartPos) const {
406  assert(!empty() && "empty range");
407  const_iterator i = begin();
408  const_iterator ie = end();
409  const_iterator j = StartPos;
410  const_iterator je = other.end();
411 
412  assert((StartPos->start <= i->start || StartPos == other.begin()) &&
413  StartPos != other.end() && "Bogus start position hint!");
414 
415  if (i->start < j->start) {
416  i = std::upper_bound(i, ie, j->start);
417  if (i != begin()) --i;
418  } else if (j->start < i->start) {
419  ++StartPos;
420  if (StartPos != other.end() && StartPos->start <= i->start) {
421  assert(StartPos < other.end() && i < end());
422  j = std::upper_bound(j, je, i->start);
423  if (j != other.begin()) --j;
424  }
425  } else {
426  return true;
427  }
428 
429  if (j == je) return false;
430 
431  while (i != ie) {
432  if (i->start > j->start) {
433  std::swap(i, j);
434  std::swap(ie, je);
435  }
436 
437  if (i->end > j->start)
438  return true;
439  ++i;
440  }
441 
442  return false;
443 }
444 
445 bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP,
446  const SlotIndexes &Indexes) const {
447  assert(!empty() && "empty range");
448  if (Other.empty())
449  return false;
450 
451  // Use binary searches to find initial positions.
452  const_iterator I = find(Other.beginIndex());
453  const_iterator IE = end();
454  if (I == IE)
455  return false;
456  const_iterator J = Other.find(I->start);
457  const_iterator JE = Other.end();
458  if (J == JE)
459  return false;
460 
461  while (true) {
462  // J has just been advanced to satisfy:
463  assert(J->end >= I->start);
464  // Check for an overlap.
465  if (J->start < I->end) {
466  // I and J are overlapping. Find the later start.
467  SlotIndex Def = std::max(I->start, J->start);
468  // Allow the overlap if Def is a coalescable copy.
469  if (Def.isBlock() ||
470  !CP.isCoalescable(Indexes.getInstructionFromIndex(Def)))
471  return true;
472  }
473  // Advance the iterator that ends first to check for more overlaps.
474  if (J->end > I->end) {
475  std::swap(I, J);
476  std::swap(IE, JE);
477  }
478  // Advance J until J->end >= I->start.
479  do
480  if (++J == JE)
481  return false;
482  while (J->end < I->start);
483  }
484 }
485 
486 /// overlaps - Return true if the live range overlaps an interval specified
487 /// by [Start, End).
488 bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const {
489  assert(Start < End && "Invalid range");
490  const_iterator I = lower_bound(*this, End);
491  return I != begin() && (--I)->end > Start;
492 }
493 
494 bool LiveRange::covers(const LiveRange &Other) const {
495  if (empty())
496  return Other.empty();
497 
498  const_iterator I = begin();
499  for (const Segment &O : Other.segments) {
500  I = advanceTo(I, O.start);
501  if (I == end() || I->start > O.start)
502  return false;
503 
504  // Check adjacent live segments and see if we can get behind O.end.
505  while (I->end < O.end) {
506  const_iterator Last = I;
507  // Get next segment and abort if it was not adjacent.
508  ++I;
509  if (I == end() || Last->end != I->start)
510  return false;
511  }
512  }
513  return true;
514 }
515 
516 /// ValNo is dead, remove it. If it is the largest value number, just nuke it
517 /// (and any other deleted values neighboring it), otherwise mark it as ~1U so
518 /// it can be nuked later.
519 void LiveRange::markValNoForDeletion(VNInfo *ValNo) {
520  if (ValNo->id == getNumValNums()-1) {
521  do {
522  valnos.pop_back();
523  } while (!valnos.empty() && valnos.back()->isUnused());
524  } else {
525  ValNo->markUnused();
526  }
527 }
528 
529 /// RenumberValues - Renumber all values in order of appearance and delete the
530 /// remaining unused values.
533  valnos.clear();
534  for (const Segment &S : segments) {
535  VNInfo *VNI = S.valno;
536  if (!Seen.insert(VNI).second)
537  continue;
538  assert(!VNI->isUnused() && "Unused valno used by live segment");
539  VNI->id = (unsigned)valnos.size();
540  valnos.push_back(VNI);
541  }
542 }
543 
544 void LiveRange::addSegmentToSet(Segment S) {
545  CalcLiveRangeUtilSet(this).addSegment(S);
546 }
547 
549  // Use the segment set, if it is available.
550  if (segmentSet != nullptr) {
551  addSegmentToSet(S);
552  return end();
553  }
554  // Otherwise use the segment vector.
555  return CalcLiveRangeUtilVector(this).addSegment(S);
556 }
557 
559  // Check that the segment belongs to the back of the list.
560  assert(segments.empty() || segments.back().end <= S.start);
561  segments.push_back(S);
562 }
563 
564 std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs,
565  SlotIndex StartIdx, SlotIndex Kill) {
566  // Use the segment set, if it is available.
567  if (segmentSet != nullptr)
568  return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill);
569  // Otherwise use the segment vector.
570  return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill);
571 }
572 
574  // Use the segment set, if it is available.
575  if (segmentSet != nullptr)
576  return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
577  // Otherwise use the segment vector.
578  return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
579 }
580 
581 /// Remove the specified segment from this range. Note that the segment must
582 /// be in a single Segment in its entirety.
584  bool RemoveDeadValNo) {
585  // Find the Segment containing this span.
586  iterator I = find(Start);
587  assert(I != end() && "Segment is not in range!");
588  assert(I->containsInterval(Start, End)
589  && "Segment is not entirely in range!");
590 
591  // If the span we are removing is at the start of the Segment, adjust it.
592  VNInfo *ValNo = I->valno;
593  if (I->start == Start) {
594  if (I->end == End) {
595  segments.erase(I); // Removed the whole Segment.
596 
597  if (RemoveDeadValNo)
598  removeValNoIfDead(ValNo);
599  } else
600  I->start = End;
601  return;
602  }
603 
604  // Otherwise if the span we are removing is at the end of the Segment,
605  // adjust the other way.
606  if (I->end == End) {
607  I->end = Start;
608  return;
609  }
610 
611  // Otherwise, we are splitting the Segment into two pieces.
612  SlotIndex OldEnd = I->end;
613  I->end = Start; // Trim the old segment.
614 
615  // Insert the new one.
616  segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
617 }
618 
620  VNInfo *ValNo = I->valno;
621  I = segments.erase(I);
622  if (RemoveDeadValNo)
623  removeValNoIfDead(ValNo);
624  return I;
625 }
626 
628  if (none_of(*this, [=](const Segment &S) { return S.valno == ValNo; }))
629  markValNoForDeletion(ValNo);
630 }
631 
632 /// removeValNo - Remove all the segments defined by the specified value#.
633 /// Also remove the value# from value# list.
635  if (empty()) return;
637  [ValNo](const Segment &S) { return S.valno == ValNo; });
638  // Now that ValNo is dead, remove it.
639  markValNoForDeletion(ValNo);
640 }
641 
643  const int *LHSValNoAssignments,
644  const int *RHSValNoAssignments,
645  SmallVectorImpl<VNInfo *> &NewVNInfo) {
646  verify();
647 
648  // Determine if any of our values are mapped. This is uncommon, so we want
649  // to avoid the range scan if not.
650  bool MustMapCurValNos = false;
651  unsigned NumVals = getNumValNums();
652  unsigned NumNewVals = NewVNInfo.size();
653  for (unsigned i = 0; i != NumVals; ++i) {
654  unsigned LHSValID = LHSValNoAssignments[i];
655  if (i != LHSValID ||
656  (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
657  MustMapCurValNos = true;
658  break;
659  }
660  }
661 
662  // If we have to apply a mapping to our base range assignment, rewrite it now.
663  if (MustMapCurValNos && !empty()) {
664  // Map the first live range.
665 
666  iterator OutIt = begin();
667  OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
668  for (iterator I = std::next(OutIt), E = end(); I != E; ++I) {
669  VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
670  assert(nextValNo && "Huh?");
671 
672  // If this live range has the same value # as its immediate predecessor,
673  // and if they are neighbors, remove one Segment. This happens when we
674  // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
675  if (OutIt->valno == nextValNo && OutIt->end == I->start) {
676  OutIt->end = I->end;
677  } else {
678  // Didn't merge. Move OutIt to the next segment,
679  ++OutIt;
680  OutIt->valno = nextValNo;
681  if (OutIt != I) {
682  OutIt->start = I->start;
683  OutIt->end = I->end;
684  }
685  }
686  }
687  // If we merge some segments, chop off the end.
688  ++OutIt;
689  segments.erase(OutIt, end());
690  }
691 
692  // Rewrite Other values before changing the VNInfo ids.
693  // This can leave Other in an invalid state because we're not coalescing
694  // touching segments that now have identical values. That's OK since Other is
695  // not supposed to be valid after calling join();
696  for (Segment &S : Other.segments)
697  S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
698 
699  // Update val# info. Renumber them and make sure they all belong to this
700  // LiveRange now. Also remove dead val#'s.
701  unsigned NumValNos = 0;
702  for (unsigned i = 0; i < NumNewVals; ++i) {
703  VNInfo *VNI = NewVNInfo[i];
704  if (VNI) {
705  if (NumValNos >= NumVals)
706  valnos.push_back(VNI);
707  else
708  valnos[NumValNos] = VNI;
709  VNI->id = NumValNos++; // Renumber val#.
710  }
711  }
712  if (NumNewVals < NumVals)
713  valnos.resize(NumNewVals); // shrinkify
714 
715  // Okay, now insert the RHS live segments into the LHS.
716  LiveRangeUpdater Updater(this);
717  for (Segment &S : Other.segments)
718  Updater.add(S);
719 }
720 
721 /// Merge all of the segments in RHS into this live range as the specified
722 /// value number. The segments in RHS are allowed to overlap with segments in
723 /// the current range, but only if the overlapping segments have the
724 /// specified value number.
726  VNInfo *LHSValNo) {
727  LiveRangeUpdater Updater(this);
728  for (const Segment &S : RHS.segments)
729  Updater.add(S.start, S.end, LHSValNo);
730 }
731 
732 /// MergeValueInAsValue - Merge all of the live segments of a specific val#
733 /// in RHS into this live range as the specified value number.
734 /// The segments in RHS are allowed to overlap with segments in the
735 /// current range, it will replace the value numbers of the overlaped
736 /// segments with the specified value number.
738  const VNInfo *RHSValNo,
739  VNInfo *LHSValNo) {
740  LiveRangeUpdater Updater(this);
741  for (const Segment &S : RHS.segments)
742  if (S.valno == RHSValNo)
743  Updater.add(S.start, S.end, LHSValNo);
744 }
745 
746 /// MergeValueNumberInto - This method is called when two value nubmers
747 /// are found to be equivalent. This eliminates V1, replacing all
748 /// segments with the V1 value number with the V2 value number. This can
749 /// cause merging of V1/V2 values numbers and compaction of the value space.
751  assert(V1 != V2 && "Identical value#'s are always equivalent!");
752 
753  // This code actually merges the (numerically) larger value number into the
754  // smaller value number, which is likely to allow us to compactify the value
755  // space. The only thing we have to be careful of is to preserve the
756  // instruction that defines the result value.
757 
758  // Make sure V2 is smaller than V1.
759  if (V1->id < V2->id) {
760  V1->copyFrom(*V2);
761  std::swap(V1, V2);
762  }
763 
764  // Merge V1 segments into V2.
765  for (iterator I = begin(); I != end(); ) {
766  iterator S = I++;
767  if (S->valno != V1) continue; // Not a V1 Segment.
768 
769  // Okay, we found a V1 live range. If it had a previous, touching, V2 live
770  // range, extend it.
771  if (S != begin()) {
772  iterator Prev = S-1;
773  if (Prev->valno == V2 && Prev->end == S->start) {
774  Prev->end = S->end;
775 
776  // Erase this live-range.
777  segments.erase(S);
778  I = Prev+1;
779  S = Prev;
780  }
781  }
782 
783  // Okay, now we have a V1 or V2 live range that is maximally merged forward.
784  // Ensure that it is a V2 live-range.
785  S->valno = V2;
786 
787  // If we can merge it into later V2 segments, do so now. We ignore any
788  // following V1 segments, as they will be merged in subsequent iterations
789  // of the loop.
790  if (I != end()) {
791  if (I->start == S->end && I->valno == V2) {
792  S->end = I->end;
793  segments.erase(I);
794  I = S+1;
795  }
796  }
797  }
798 
799  // Now that V1 is dead, remove it.
800  markValNoForDeletion(V1);
801 
802  return V2;
803 }
804 
806  assert(segmentSet != nullptr && "segment set must have been created");
807  assert(
808  segments.empty() &&
809  "segment set can be used only initially before switching to the array");
810  segments.append(segmentSet->begin(), segmentSet->end());
811  segmentSet = nullptr;
812  verify();
813 }
814 
816  ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
817  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
818 
819  // If there are no regmask slots, we have nothing to search.
820  if (SlotI == SlotE)
821  return false;
822 
823  // Start our search at the first segment that ends after the first slot.
824  const_iterator SegmentI = find(*SlotI);
825  const_iterator SegmentE = end();
826 
827  // If there are no segments that end after the first slot, we're done.
828  if (SegmentI == SegmentE)
829  return false;
830 
831  // Look for each slot in the live range.
832  for ( ; SlotI != SlotE; ++SlotI) {
833  // Go to the next segment that ends after the current slot.
834  // The slot may be within a hole in the range.
835  SegmentI = advanceTo(SegmentI, *SlotI);
836  if (SegmentI == SegmentE)
837  return false;
838 
839  // If this segment contains the slot, we're done.
840  if (SegmentI->contains(*SlotI))
841  return true;
842  // Otherwise, look for the next slot.
843  }
844 
845  // We didn't find a segment containing any of the slots.
846  return false;
847 }
848 
849 void LiveInterval::freeSubRange(SubRange *S) {
850  S->~SubRange();
851  // Memory was allocated with BumpPtr allocator and is not freed here.
852 }
853 
855  SubRange **NextPtr = &SubRanges;
856  SubRange *I = *NextPtr;
857  while (I != nullptr) {
858  if (!I->empty()) {
859  NextPtr = &I->Next;
860  I = *NextPtr;
861  continue;
862  }
863  // Skip empty subranges until we find the first nonempty one.
864  do {
865  SubRange *Next = I->Next;
866  freeSubRange(I);
867  I = Next;
868  } while (I != nullptr && I->empty());
869  *NextPtr = I;
870  }
871 }
872 
874  for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
875  Next = I->Next;
876  freeSubRange(I);
877  }
878  SubRanges = nullptr;
879 }
880 
881 /// For each VNI in \p SR, check whether or not that value defines part
882 /// of the mask describe by \p LaneMask and if not, remove that value
883 /// from \p SR.
885  LaneBitmask LaneMask,
886  const SlotIndexes &Indexes,
887  const TargetRegisterInfo &TRI,
888  unsigned ComposeSubRegIdx) {
889  // Phys reg should not be tracked at subreg level.
890  // Same for noreg (Reg == 0).
892  return;
893  // Remove the values that don't define those lanes.
894  SmallVector<VNInfo *, 8> ToBeRemoved;
895  for (VNInfo *VNI : SR.valnos) {
896  if (VNI->isUnused())
897  continue;
898  // PHI definitions don't have MI attached, so there is nothing
899  // we can use to strip the VNI.
900  if (VNI->isPHIDef())
901  continue;
902  const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
903  assert(MI && "Cannot find the definition of a value");
904  bool hasDef = false;
905  for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
906  if (!MOI->isReg() || !MOI->isDef())
907  continue;
908  if (MOI->getReg() != Reg)
909  continue;
910  LaneBitmask OrigMask = TRI.getSubRegIndexLaneMask(MOI->getSubReg());
911  LaneBitmask ExpectedDefMask =
912  ComposeSubRegIdx
913  ? TRI.composeSubRegIndexLaneMask(ComposeSubRegIdx, OrigMask)
914  : OrigMask;
915  if ((ExpectedDefMask & LaneMask).none())
916  continue;
917  hasDef = true;
918  break;
919  }
920 
921  if (!hasDef)
922  ToBeRemoved.push_back(VNI);
923  }
924  for (VNInfo *VNI : ToBeRemoved)
925  SR.removeValNo(VNI);
926 
927  // If the subrange is empty at this point, the MIR is invalid. Do not assert
928  // and let the verifier catch this case.
929 }
930 
933  std::function<void(LiveInterval::SubRange &)> Apply,
934  const SlotIndexes &Indexes, const TargetRegisterInfo &TRI,
935  unsigned ComposeSubRegIdx) {
936  LaneBitmask ToApply = LaneMask;
937  for (SubRange &SR : subranges()) {
938  LaneBitmask SRMask = SR.LaneMask;
939  LaneBitmask Matching = SRMask & LaneMask;
940  if (Matching.none())
941  continue;
942 
943  SubRange *MatchingRange;
944  if (SRMask == Matching) {
945  // The subrange fits (it does not cover bits outside \p LaneMask).
946  MatchingRange = &SR;
947  } else {
948  // We have to split the subrange into a matching and non-matching part.
949  // Reduce lanemask of existing lane to non-matching part.
950  SR.LaneMask = SRMask & ~Matching;
951  // Create a new subrange for the matching part
952  MatchingRange = createSubRangeFrom(Allocator, Matching, SR);
953  // Now that the subrange is split in half, make sure we
954  // only keep in the subranges the VNIs that touch the related half.
955  stripValuesNotDefiningMask(reg(), *MatchingRange, Matching, Indexes, TRI,
956  ComposeSubRegIdx);
957  stripValuesNotDefiningMask(reg(), SR, SR.LaneMask, Indexes, TRI,
958  ComposeSubRegIdx);
959  }
960  Apply(*MatchingRange);
961  ToApply &= ~Matching;
962  }
963  // Create a new subrange if there are uncovered bits left.
964  if (ToApply.any()) {
965  SubRange *NewRange = createSubRange(Allocator, ToApply);
966  Apply(*NewRange);
967  }
968 }
969 
970 unsigned LiveInterval::getSize() const {
971  unsigned Sum = 0;
972  for (const Segment &S : segments)
973  Sum += S.start.distance(S.end);
974  return Sum;
975 }
976 
978  LaneBitmask LaneMask,
979  const MachineRegisterInfo &MRI,
980  const SlotIndexes &Indexes) const {
983  assert((VRegMask & LaneMask).any());
985  for (const MachineOperand &MO : MRI.def_operands(reg())) {
986  if (!MO.isUndef())
987  continue;
988  unsigned SubReg = MO.getSubReg();
989  assert(SubReg != 0 && "Undef should only be set on subreg defs");
991  LaneBitmask UndefMask = VRegMask & ~DefMask;
992  if ((UndefMask & LaneMask).any()) {
993  const MachineInstr &MI = *MO.getParent();
994  bool EarlyClobber = MO.isEarlyClobber();
996  Undefs.push_back(Pos);
997  }
998  }
999 }
1000 
1002  return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';
1003 }
1004 
1005 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1007  dbgs() << *this << '\n';
1008 }
1009 #endif
1010 
1012  if (empty())
1013  OS << "EMPTY";
1014  else {
1015  for (const Segment &S : segments) {
1016  OS << S;
1017  assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
1018  }
1019  }
1020 
1021  // Print value number info.
1022  if (getNumValNums()) {
1023  OS << ' ';
1024  unsigned vnum = 0;
1025  for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
1026  ++i, ++vnum) {
1027  const VNInfo *vni = *i;
1028  if (vnum) OS << ' ';
1029  OS << vnum << '@';
1030  if (vni->isUnused()) {
1031  OS << 'x';
1032  } else {
1033  OS << vni->def;
1034  if (vni->isPHIDef())
1035  OS << "-phi";
1036  }
1037  }
1038  }
1039 }
1040 
1042  OS << " L" << PrintLaneMask(LaneMask) << ' '
1043  << static_cast<const LiveRange &>(*this);
1044 }
1045 
1047  OS << printReg(reg()) << ' ';
1048  super::print(OS);
1049  // Print subranges
1050  for (const SubRange &SR : subranges())
1051  OS << SR;
1052  OS << " weight:" << Weight;
1053 }
1054 
1055 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1057  dbgs() << *this << '\n';
1058 }
1059 
1061  dbgs() << *this << '\n';
1062 }
1063 
1065  dbgs() << *this << '\n';
1066 }
1067 #endif
1068 
1069 #ifndef NDEBUG
1070 void LiveRange::verify() const {
1071  for (const_iterator I = begin(), E = end(); I != E; ++I) {
1072  assert(I->start.isValid());
1073  assert(I->end.isValid());
1074  assert(I->start < I->end);
1075  assert(I->valno != nullptr);
1076  assert(I->valno->id < valnos.size());
1077  assert(I->valno == valnos[I->valno->id]);
1078  if (std::next(I) != E) {
1079  assert(I->end <= std::next(I)->start);
1080  if (I->end == std::next(I)->start)
1081  assert(I->valno != std::next(I)->valno);
1082  }
1083  }
1084 }
1085 
1087  super::verify();
1088 
1089  // Make sure SubRanges are fine and LaneMasks are disjunct.
1090  LaneBitmask Mask;
1091  LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg())
1092  : LaneBitmask::getAll();
1093  for (const SubRange &SR : subranges()) {
1094  // Subrange lanemask should be disjunct to any previous subrange masks.
1095  assert((Mask & SR.LaneMask).none());
1096  Mask |= SR.LaneMask;
1097 
1098  // subrange mask should not contained in maximum lane mask for the vreg.
1099  assert((Mask & ~MaxMask).none());
1100  // empty subranges must be removed.
1101  assert(!SR.empty());
1102 
1103  SR.verify();
1104  // Main liverange should cover subrange.
1105  assert(covers(SR));
1106  }
1107 }
1108 #endif
1109 
1110 //===----------------------------------------------------------------------===//
1111 // LiveRangeUpdater class
1112 //===----------------------------------------------------------------------===//
1113 //
1114 // The LiveRangeUpdater class always maintains these invariants:
1115 //
1116 // - When LastStart is invalid, Spills is empty and the iterators are invalid.
1117 // This is the initial state, and the state created by flush().
1118 // In this state, isDirty() returns false.
1119 //
1120 // Otherwise, segments are kept in three separate areas:
1121 //
1122 // 1. [begin; WriteI) at the front of LR.
1123 // 2. [ReadI; end) at the back of LR.
1124 // 3. Spills.
1125 //
1126 // - LR.begin() <= WriteI <= ReadI <= LR.end().
1127 // - Segments in all three areas are fully ordered and coalesced.
1128 // - Segments in area 1 precede and can't coalesce with segments in area 2.
1129 // - Segments in Spills precede and can't coalesce with segments in area 2.
1130 // - No coalescing is possible between segments in Spills and segments in area
1131 // 1, and there are no overlapping segments.
1132 //
1133 // The segments in Spills are not ordered with respect to the segments in area
1134 // 1. They need to be merged.
1135 //
1136 // When they exist, Spills.back().start <= LastStart,
1137 // and WriteI[-1].start <= LastStart.
1138 
1139 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1141  if (!isDirty()) {
1142  if (LR)
1143  OS << "Clean updater: " << *LR << '\n';
1144  else
1145  OS << "Null updater.\n";
1146  return;
1147  }
1148  assert(LR && "Can't have null LR in dirty updater.");
1149  OS << " updater with gap = " << (ReadI - WriteI)
1150  << ", last start = " << LastStart
1151  << ":\n Area 1:";
1152  for (const auto &S : make_range(LR->begin(), WriteI))
1153  OS << ' ' << S;
1154  OS << "\n Spills:";
1155  for (unsigned I = 0, E = Spills.size(); I != E; ++I)
1156  OS << ' ' << Spills[I];
1157  OS << "\n Area 2:";
1158  for (const auto &S : make_range(ReadI, LR->end()))
1159  OS << ' ' << S;
1160  OS << '\n';
1161 }
1162 
1164  print(errs());
1165 }
1166 #endif
1167 
1168 // Determine if A and B should be coalesced.
1169 static inline bool coalescable(const LiveRange::Segment &A,
1170  const LiveRange::Segment &B) {
1171  assert(A.start <= B.start && "Unordered live segments.");
1172  if (A.end == B.start)
1173  return A.valno == B.valno;
1174  if (A.end < B.start)
1175  return false;
1176  assert(A.valno == B.valno && "Cannot overlap different values");
1177  return true;
1178 }
1179 
1181  assert(LR && "Cannot add to a null destination");
1182 
1183  // Fall back to the regular add method if the live range
1184  // is using the segment set instead of the segment vector.
1185  if (LR->segmentSet != nullptr) {
1186  LR->addSegmentToSet(Seg);
1187  return;
1188  }
1189 
1190  // Flush the state if Start moves backwards.
1191  if (!LastStart.isValid() || LastStart > Seg.start) {
1192  if (isDirty())
1193  flush();
1194  // This brings us to an uninitialized state. Reinitialize.
1195  assert(Spills.empty() && "Leftover spilled segments");
1196  WriteI = ReadI = LR->begin();
1197  }
1198 
1199  // Remember start for next time.
1200  LastStart = Seg.start;
1201 
1202  // Advance ReadI until it ends after Seg.start.
1203  LiveRange::iterator E = LR->end();
1204  if (ReadI != E && ReadI->end <= Seg.start) {
1205  // First try to close the gap between WriteI and ReadI with spills.
1206  if (ReadI != WriteI)
1207  mergeSpills();
1208  // Then advance ReadI.
1209  if (ReadI == WriteI)
1210  ReadI = WriteI = LR->find(Seg.start);
1211  else
1212  while (ReadI != E && ReadI->end <= Seg.start)
1213  *WriteI++ = *ReadI++;
1214  }
1215 
1216  assert(ReadI == E || ReadI->end > Seg.start);
1217 
1218  // Check if the ReadI segment begins early.
1219  if (ReadI != E && ReadI->start <= Seg.start) {
1220  assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1221  // Bail if Seg is completely contained in ReadI.
1222  if (ReadI->end >= Seg.end)
1223  return;
1224  // Coalesce into Seg.
1225  Seg.start = ReadI->start;
1226  ++ReadI;
1227  }
1228 
1229  // Coalesce as much as possible from ReadI into Seg.
1230  while (ReadI != E && coalescable(Seg, *ReadI)) {
1231  Seg.end = std::max(Seg.end, ReadI->end);
1232  ++ReadI;
1233  }
1234 
1235  // Try coalescing Spills.back() into Seg.
1236  if (!Spills.empty() && coalescable(Spills.back(), Seg)) {
1237  Seg.start = Spills.back().start;
1238  Seg.end = std::max(Spills.back().end, Seg.end);
1239  Spills.pop_back();
1240  }
1241 
1242  // Try coalescing Seg into WriteI[-1].
1243  if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {
1244  WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1245  return;
1246  }
1247 
1248  // Seg doesn't coalesce with anything, and needs to be inserted somewhere.
1249  if (WriteI != ReadI) {
1250  *WriteI++ = Seg;
1251  return;
1252  }
1253 
1254  // Finally, append to LR or Spills.
1255  if (WriteI == E) {
1256  LR->segments.push_back(Seg);
1257  WriteI = ReadI = LR->end();
1258  } else
1259  Spills.push_back(Seg);
1260 }
1261 
1262 // Merge as many spilled segments as possible into the gap between WriteI
1263 // and ReadI. Advance WriteI to reflect the inserted instructions.
1264 void LiveRangeUpdater::mergeSpills() {
1265  // Perform a backwards merge of Spills and [SpillI;WriteI).
1266  size_t GapSize = ReadI - WriteI;
1267  size_t NumMoved = std::min(Spills.size(), GapSize);
1268  LiveRange::iterator Src = WriteI;
1269  LiveRange::iterator Dst = Src + NumMoved;
1270  LiveRange::iterator SpillSrc = Spills.end();
1271  LiveRange::iterator B = LR->begin();
1272 
1273  // This is the new WriteI position after merging spills.
1274  WriteI = Dst;
1275 
1276  // Now merge Src and Spills backwards.
1277  while (Src != Dst) {
1278  if (Src != B && Src[-1].start > SpillSrc[-1].start)
1279  *--Dst = *--Src;
1280  else
1281  *--Dst = *--SpillSrc;
1282  }
1283  assert(NumMoved == size_t(Spills.end() - SpillSrc));
1284  Spills.erase(SpillSrc, Spills.end());
1285 }
1286 
1288  if (!isDirty())
1289  return;
1290  // Clear the dirty state.
1291  LastStart = SlotIndex();
1292 
1293  assert(LR && "Cannot add to a null destination");
1294 
1295  // Nothing to merge?
1296  if (Spills.empty()) {
1297  LR->segments.erase(WriteI, ReadI);
1298  LR->verify();
1299  return;
1300  }
1301 
1302  // Resize the WriteI - ReadI gap to match Spills.
1303  size_t GapSize = ReadI - WriteI;
1304  if (GapSize < Spills.size()) {
1305  // The gap is too small. Make some room.
1306  size_t WritePos = WriteI - LR->begin();
1307  LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1308  // This also invalidated ReadI, but it is recomputed below.
1309  WriteI = LR->begin() + WritePos;
1310  } else {
1311  // Shrink the gap if necessary.
1312  LR->segments.erase(WriteI + Spills.size(), ReadI);
1313  }
1314  ReadI = WriteI + Spills.size();
1315  mergeSpills();
1316  LR->verify();
1317 }
1318 
1320  // Create initial equivalence classes.
1321  EqClass.clear();
1322  EqClass.grow(LR.getNumValNums());
1323 
1324  const VNInfo *used = nullptr, *unused = nullptr;
1325 
1326  // Determine connections.
1327  for (const VNInfo *VNI : LR.valnos) {
1328  // Group all unused values into one class.
1329  if (VNI->isUnused()) {
1330  if (unused)
1331  EqClass.join(unused->id, VNI->id);
1332  unused = VNI;
1333  continue;
1334  }
1335  used = VNI;
1336  if (VNI->isPHIDef()) {
1337  const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1338  assert(MBB && "Phi-def has no defining MBB");
1339  // Connect to values live out of predecessors.
1340  for (MachineBasicBlock *Pred : MBB->predecessors())
1341  if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(Pred)))
1342  EqClass.join(VNI->id, PVNI->id);
1343  } else {
1344  // Normal value defined by an instruction. Check for two-addr redef.
1345  // FIXME: This could be coincidental. Should we really check for a tied
1346  // operand constraint?
1347  // Note that VNI->def may be a use slot for an early clobber def.
1348  if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
1349  EqClass.join(VNI->id, UVNI->id);
1350  }
1351  }
1352 
1353  // Lump all the unused values in with the last used value.
1354  if (used && unused)
1355  EqClass.join(used->id, unused->id);
1356 
1357  EqClass.compress();
1358  return EqClass.getNumClasses();
1359 }
1360 
1363  // Rewrite instructions.
1364  for (MachineOperand &MO :
1366  MachineInstr *MI = MO.getParent();
1367  const VNInfo *VNI;
1368  if (MI->isDebugValue()) {
1369  // DBG_VALUE instructions don't have slot indexes, so get the index of
1370  // the instruction before them. The value is defined there too.
1371  SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);
1372  VNI = LI.Query(Idx).valueOut();
1373  } else {
1374  SlotIndex Idx = LIS.getInstructionIndex(*MI);
1375  LiveQueryResult LRQ = LI.Query(Idx);
1376  VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
1377  }
1378  // In the case of an <undef> use that isn't tied to any def, VNI will be
1379  // NULL. If the use is tied to a def, VNI will be the defined value.
1380  if (!VNI)
1381  continue;
1382  if (unsigned EqClass = getEqClass(VNI))
1383  MO.setReg(LIV[EqClass - 1]->reg());
1384  }
1385 
1386  // Distribute subregister liveranges.
1387  if (LI.hasSubRanges()) {
1388  unsigned NumComponents = EqClass.getNumClasses();
1389  SmallVector<unsigned, 8> VNIMapping;
1391  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1392  for (LiveInterval::SubRange &SR : LI.subranges()) {
1393  // Create new subranges in the split intervals and construct a mapping
1394  // for the VNInfos in the subrange.
1395  unsigned NumValNos = SR.valnos.size();
1396  VNIMapping.clear();
1397  VNIMapping.reserve(NumValNos);
1398  SubRanges.clear();
1399  SubRanges.resize(NumComponents-1, nullptr);
1400  for (unsigned I = 0; I < NumValNos; ++I) {
1401  const VNInfo &VNI = *SR.valnos[I];
1402  unsigned ComponentNum;
1403  if (VNI.isUnused()) {
1404  ComponentNum = 0;
1405  } else {
1406  const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def);
1407  assert(MainRangeVNI != nullptr
1408  && "SubRange def must have corresponding main range def");
1409  ComponentNum = getEqClass(MainRangeVNI);
1410  if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) {
1411  SubRanges[ComponentNum-1]
1412  = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);
1413  }
1414  }
1415  VNIMapping.push_back(ComponentNum);
1416  }
1417  DistributeRange(SR, SubRanges.data(), VNIMapping);
1418  }
1419  LI.removeEmptySubRanges();
1420  }
1421 
1422  // Distribute main liverange.
1423  DistributeRange(LI, LIV, EqClass);
1424 }
llvm::LiveRange::find
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
Definition: LiveInterval.cpp:350
llvm::LaneBitmask
Definition: LaneBitmask.h:40
i
i
Definition: README.txt:29
llvm::LiveQueryResult::valueDefined
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Definition: LiveInterval.h:135
llvm::LiveInterval::computeSubRangeUndefs
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 ...
Definition: LiveInterval.cpp:977
llvm::LiveRange::join
void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
Definition: LiveInterval.cpp:642
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::upper_bound
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:1737
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::none_of
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:1619
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::LiveRange::flushSegmentSet
void flushSegmentSet()
Flush segment set into the regular segment vector.
Definition: LiveInterval.cpp:805
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:152
llvm::ConnectedVNInfoEqClasses::Distribute
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
Definition: LiveInterval.cpp:1361
llvm::LiveInterval::createSubRange
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
Definition: LiveInterval.h:785
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::lower_bound
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:1724
llvm::LiveRange::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1011
llvm::ArrayRef::iterator
const_pointer iterator
Definition: ArrayRef.h:49
LiveRangeUtils.h
llvm::SmallVector< Segment, 2 >
llvm::LiveRange::advanceTo
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
Definition: LiveInterval.h:271
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:151
llvm::erase_if
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:1795
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
MachineBasicBlock.h
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::LiveRange::Segment::start
SlotIndex start
Definition: LiveInterval.h:163
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
impl
place backedge safepoints impl
Definition: PlaceSafepoints.cpp:613
llvm::LiveRange::vni_begin
vni_iterator vni_begin()
Definition: LiveInterval.h:224
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LiveInterval::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1046
createDeadDef
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
Definition: LiveIntervalCalc.cpp:33
llvm::LiveQueryResult
Result of a LiveRange query.
Definition: LiveInterval.h:90
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1618
llvm::RegState::EarlyClobber
@ EarlyClobber
Register definition happens before uses.
Definition: MachineInstrBuilder.h:54
llvm::LegalityPredicates::any
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
Definition: LegalizerInfo.h:241
MachineRegisterInfo.h
llvm::LiveRange::extendInBlock
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
Definition: LiveInterval.cpp:564
llvm::LiveRange::isLiveAtIndexes
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
Definition: LiveInterval.cpp:815
llvm::LiveInterval::SubRange::LaneMask
LaneBitmask LaneMask
Definition: LiveInterval.h:696
llvm::DistributeRange
static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], EqClassesT VNIClasses)
Helper function that distributes live range value numbers and the corresponding segments of a primary...
Definition: LiveRangeUtils.h:26
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::LiveRange::Segment::dump
void dump() const
Definition: LiveInterval.cpp:1006
llvm::LiveRange::SegmentSet
std::set< Segment > SegmentSet
Definition: LiveInterval.h:209
llvm::LiveRange::begin
iterator begin()
Definition: LiveInterval.h:215
llvm::TargetRegisterInfo::getSubRegIndexLaneMask
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
Definition: TargetRegisterInfo.h:378
llvm::LiveRange::covers
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
Definition: LiveInterval.cpp:494
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
llvm::SlotIndex::isEarlierInstr
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:202
llvm::LiveInterval::SubRange::dump
void dump() const
Definition: LiveInterval.cpp:1060
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::LiveInterval::getSize
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
Definition: LiveInterval.cpp:970
llvm::LiveRange::const_iterator
Segments::const_iterator const_iterator
Definition: LiveInterval.h:213
llvm::LiveInterval::dump
void dump() const
Definition: LiveInterval.cpp:1064
llvm::LiveRangeUpdater
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:934
llvm::LiveInterval::clearSubRanges
void clearSubRanges()
Removes all subregister liveness information.
Definition: LiveInterval.cpp:873
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::LiveRange::valnos
VNInfoList valnos
Definition: LiveInterval.h:204
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::SlotIndexes::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:384
llvm::PrintLaneMask
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::LiveRange::size
size_t size() const
Definition: LiveInterval.h:305
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:313
SmallPtrSet.h
llvm::LiveRange::overlapsFrom
bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const
overlapsFrom - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.cpp:404
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::LiveQueryResult::valueIn
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
llvm::LiveRange::removeValNoIfDead
void removeValNoIfDead(VNInfo *ValNo)
Mark ValNo for deletion if no segments in this range use it.
Definition: LiveInterval.cpp:627
llvm::SlotIndexes::getInstructionFromIndex
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:402
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::LiveQueryResult::valueOut
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
Definition: LiveInterval.h:123
llvm::LiveRange::append
void append(const LiveRange::Segment S)
Append a segment to the list of segments.
Definition: LiveInterval.cpp:558
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::LiveInterval::SubRange::print
void print(raw_ostream &OS) const
Definition: LiveInterval.cpp:1041
llvm::LiveRange::dump
void dump() const
Definition: LiveInterval.cpp:1056
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
llvm::LiveRange::RenumberValues
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
Definition: LiveInterval.cpp:531
llvm::LiveRange::getVNInfoBefore
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:429
llvm::LiveInterval::removeEmptySubRanges
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Definition: LiveInterval.cpp:854
llvm::LiveInterval::refineSubRanges
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.
Definition: LiveInterval.cpp:931
llvm::LiveRangeUpdater::print
void print(raw_ostream &) const
Definition: LiveInterval.cpp:1140
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
LiveIntervals.h
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::find
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:1625
llvm::VNInfo::id
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::LiveRange::getNumValNums
unsigned getNumValNums() const
Definition: LiveInterval.h:313
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LaneBitmask::any
constexpr bool any() const
Definition: LaneBitmask.h:53
llvm::make_early_inc_range
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:608
llvm::LiveRangeUpdater::dump
void dump() const
Definition: LiveInterval.cpp:1163
llvm::LiveRange::overlaps
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:448
llvm::SlotIndex::isSameInstr
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:196
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
ArrayRef.h
llvm::LiveRange::Query
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:541
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::MIBundleOperandIteratorBase::isValid
bool isValid() const
isValid - Returns true until all the operands have been visited.
Definition: MachineInstrBundle.h:136
llvm::MachineRegisterInfo::reg_operands
iterator_range< reg_iterator > reg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:294
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::ConnectedVNInfoEqClasses::Classify
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Definition: LiveInterval.cpp:1319
iterator_range.h
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:358
llvm::SlotIndex::getRegSlot
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:253
llvm::LiveRange::MergeValueNumberInto
VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
Definition: LiveInterval.cpp:750
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
coalescable
static bool coalescable(const LiveRange::Segment &A, const LiveRange::Segment &B)
Definition: LiveInterval.cpp:1169
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::LiveRangeUpdater::flush
void flush()
Flush the updater state to LR so it is valid and contains all added segments.
Definition: LiveInterval.cpp:1287
llvm::LaneBitmask::none
constexpr bool none() const
Definition: LaneBitmask.h:52
Compiler.h
llvm::CoalescerPair
A helper class for register coalescers.
Definition: RegisterCoalescer.h:28
llvm::SlotIndex::getNextSlot
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:268
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LiveRange::Segment::end
SlotIndex end
Definition: LiveInterval.h:164
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:693
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::LiveRange::endIndex
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
llvm::VNInfo::isPHIDef
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
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::HexagonISD::CP
@ CP
Definition: HexagonISelLowering.h:53
llvm::MachineRegisterInfo::def_operands
iterator_range< def_iterator > def_operands(Register Reg) const
Definition: MachineRegisterInfo.h:397
j
return j(j<< 16)
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::LiveRange::MergeSegmentsInAsValue
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 ...
Definition: LiveInterval.cpp:725
llvm::LiveRange::iterator
Segments::iterator iterator
Definition: LiveInterval.h:212
llvm::MachineRegisterInfo::getMaxLaneMaskForVReg
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
Definition: MachineRegisterInfo.cpp:489
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::ConstMIBundleOperands
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
Definition: MachineInstrBundle.h:185
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::TargetRegisterInfo::composeSubRegIndexLaneMask
LaneBitmask composeSubRegIndexLaneMask(unsigned IdxA, LaneBitmask Mask) const
Transforms a LaneMask computed for one subregister to the lanemask that would have been computed when...
Definition: TargetRegisterInfo.h:651
llvm::LiveRangeUpdater::add
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
Definition: LiveInterval.cpp:1180
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::LiveRange::getValNumInfo
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
Definition: LiveInterval.h:317
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveRange::getVNInfoAt
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::VNInfo::copyFrom
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
Definition: LiveInterval.h:70
llvm::LiveRange::verify
void verify() const
Walk the range and assert if any invariants fail to hold.
Definition: LiveInterval.cpp:1070
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:583
LiveInterval.h
llvm::LiveRange::MergeValueInAsValue
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...
Definition: LiveInterval.cpp:737
llvm::LiveRange::Segment::valno
VNInfo * valno
Definition: LiveInterval.h:165
SmallVector.h
used
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is used
Definition: README-SSE.txt:270
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:142
llvm::LiveRange::segments
Segments segments
Definition: LiveInterval.h:203
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:717
llvm::LiveInterval::hasSubRanges
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
LaneBitmask.h
stripValuesNotDefiningMask
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...
Definition: LiveInterval.cpp:884
llvm::SmallVectorImpl< VNInfo * >
MachineOperand.h
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
llvm::LiveRange::removeValNo
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
Definition: LiveInterval.cpp:634
SlotIndexes.h
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
raw_ostream.h
llvm::LiveRange::vni_end
vni_iterator vni_end()
Definition: LiveInterval.h:225
llvm::LiveRange::const_vni_iterator
VNInfoList::const_iterator const_vni_iterator
Definition: LiveInterval.h:222
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:111
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
llvm::LiveRange::segmentSet
std::unique_ptr< SegmentSet > segmentSet
Definition: LiveInterval.h:210
llvm::LiveRange::isUndefIn
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
TargetRegisterInfo.h
Debug.h
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::LiveInterval::createSubRangeFrom
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
llvm::LiveRange::end
iterator end()
Definition: LiveInterval.h:216
llvm::VNInfo::markUnused
void markUnused()
Mark this value as unused.
Definition: LiveInterval.h:84
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1225
RegisterCoalescer.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775