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