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