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