1 //===-- LiveInterval.cpp - Live Interval Representation -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LiveRange and LiveInterval classes. Given some
11 // numbering of each the machine instructions an interval [i, j) is said to be a
12 // live range for register v if there is no instruction with number j' >= j
13 // such that v is live at j' and there is no instruction with number i' < i such
14 // that v is live at i'. In this implementation ranges can have holes,
15 // i.e. a range might look like [1,20), [50,65), [1000,1001). Each
16 // individual segment is represented as an instance of LiveRange::Segment,
17 // and the whole range is represented as an instance of LiveRange.
18 //
19 //===----------------------------------------------------------------------===//
20
21 #include "llvm/CodeGen/LiveInterval.h"
22 #include "RegisterCoalescer.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SmallSet.h"
26 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Format.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include <algorithm>
33 using namespace llvm;
34
find(SlotIndex Pos)35 LiveRange::iterator LiveRange::find(SlotIndex Pos) {
36 // This algorithm is basically std::upper_bound.
37 // Unfortunately, std::upper_bound cannot be used with mixed types until we
38 // adopt C++0x. Many libraries can do it, but not all.
39 if (empty() || Pos >= endIndex())
40 return end();
41 iterator I = begin();
42 size_t Len = size();
43 do {
44 size_t Mid = Len >> 1;
45 if (Pos < I[Mid].end)
46 Len = Mid;
47 else
48 I += Mid + 1, Len -= Mid + 1;
49 } while (Len);
50 return I;
51 }
52
createDeadDef(SlotIndex Def,VNInfo::Allocator & VNInfoAllocator)53 VNInfo *LiveRange::createDeadDef(SlotIndex Def,
54 VNInfo::Allocator &VNInfoAllocator) {
55 assert(!Def.isDead() && "Cannot define a value at the dead slot");
56 iterator I = find(Def);
57 if (I == end()) {
58 VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
59 segments.push_back(Segment(Def, Def.getDeadSlot(), VNI));
60 return VNI;
61 }
62 if (SlotIndex::isSameInstr(Def, I->start)) {
63 assert(I->valno->def == I->start && "Inconsistent existing value def");
64
65 // It is possible to have both normal and early-clobber defs of the same
66 // register on an instruction. It doesn't make a lot of sense, but it is
67 // possible to specify in inline assembly.
68 //
69 // Just convert everything to early-clobber.
70 Def = std::min(Def, I->start);
71 if (Def != I->start)
72 I->start = I->valno->def = Def;
73 return I->valno;
74 }
75 assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
76 VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
77 segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI));
78 return VNI;
79 }
80
81 // overlaps - Return true if the intersection of the two live ranges is
82 // not empty.
83 //
84 // An example for overlaps():
85 //
86 // 0: A = ...
87 // 4: B = ...
88 // 8: C = A + B ;; last use of A
89 //
90 // The live ranges should look like:
91 //
92 // A = [3, 11)
93 // B = [7, x)
94 // C = [11, y)
95 //
96 // A->overlaps(C) should return false since we want to be able to join
97 // A and C.
98 //
overlapsFrom(const LiveRange & other,const_iterator StartPos) const99 bool LiveRange::overlapsFrom(const LiveRange& other,
100 const_iterator StartPos) const {
101 assert(!empty() && "empty range");
102 const_iterator i = begin();
103 const_iterator ie = end();
104 const_iterator j = StartPos;
105 const_iterator je = other.end();
106
107 assert((StartPos->start <= i->start || StartPos == other.begin()) &&
108 StartPos != other.end() && "Bogus start position hint!");
109
110 if (i->start < j->start) {
111 i = std::upper_bound(i, ie, j->start);
112 if (i != begin()) --i;
113 } else if (j->start < i->start) {
114 ++StartPos;
115 if (StartPos != other.end() && StartPos->start <= i->start) {
116 assert(StartPos < other.end() && i < end());
117 j = std::upper_bound(j, je, i->start);
118 if (j != other.begin()) --j;
119 }
120 } else {
121 return true;
122 }
123
124 if (j == je) return false;
125
126 while (i != ie) {
127 if (i->start > j->start) {
128 std::swap(i, j);
129 std::swap(ie, je);
130 }
131
132 if (i->end > j->start)
133 return true;
134 ++i;
135 }
136
137 return false;
138 }
139
overlaps(const LiveRange & Other,const CoalescerPair & CP,const SlotIndexes & Indexes) const140 bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP,
141 const SlotIndexes &Indexes) const {
142 assert(!empty() && "empty range");
143 if (Other.empty())
144 return false;
145
146 // Use binary searches to find initial positions.
147 const_iterator I = find(Other.beginIndex());
148 const_iterator IE = end();
149 if (I == IE)
150 return false;
151 const_iterator J = Other.find(I->start);
152 const_iterator JE = Other.end();
153 if (J == JE)
154 return false;
155
156 for (;;) {
157 // J has just been advanced to satisfy:
158 assert(J->end >= I->start);
159 // Check for an overlap.
160 if (J->start < I->end) {
161 // I and J are overlapping. Find the later start.
162 SlotIndex Def = std::max(I->start, J->start);
163 // Allow the overlap if Def is a coalescable copy.
164 if (Def.isBlock() ||
165 !CP.isCoalescable(Indexes.getInstructionFromIndex(Def)))
166 return true;
167 }
168 // Advance the iterator that ends first to check for more overlaps.
169 if (J->end > I->end) {
170 std::swap(I, J);
171 std::swap(IE, JE);
172 }
173 // Advance J until J->end >= I->start.
174 do
175 if (++J == JE)
176 return false;
177 while (J->end < I->start);
178 }
179 }
180
181 /// overlaps - Return true if the live range overlaps an interval specified
182 /// by [Start, End).
overlaps(SlotIndex Start,SlotIndex End) const183 bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const {
184 assert(Start < End && "Invalid range");
185 const_iterator I = std::lower_bound(begin(), end(), End);
186 return I != begin() && (--I)->end > Start;
187 }
188
covers(const LiveRange & Other) const189 bool LiveRange::covers(const LiveRange &Other) const {
190 if (empty())
191 return Other.empty();
192
193 const_iterator I = begin();
194 for (const Segment &O : Other.segments) {
195 I = advanceTo(I, O.start);
196 if (I == end() || I->start > O.start)
197 return false;
198
199 // Check adjacent live segments and see if we can get behind O.end.
200 while (I->end < O.end) {
201 const_iterator Last = I;
202 // Get next segment and abort if it was not adjacent.
203 ++I;
204 if (I == end() || Last->end != I->start)
205 return false;
206 }
207 }
208 return true;
209 }
210
211 /// ValNo is dead, remove it. If it is the largest value number, just nuke it
212 /// (and any other deleted values neighboring it), otherwise mark it as ~1U so
213 /// it can be nuked later.
markValNoForDeletion(VNInfo * ValNo)214 void LiveRange::markValNoForDeletion(VNInfo *ValNo) {
215 if (ValNo->id == getNumValNums()-1) {
216 do {
217 valnos.pop_back();
218 } while (!valnos.empty() && valnos.back()->isUnused());
219 } else {
220 ValNo->markUnused();
221 }
222 }
223
224 /// RenumberValues - Renumber all values in order of appearance and delete the
225 /// remaining unused values.
RenumberValues()226 void LiveRange::RenumberValues() {
227 SmallPtrSet<VNInfo*, 8> Seen;
228 valnos.clear();
229 for (const Segment &S : segments) {
230 VNInfo *VNI = S.valno;
231 if (!Seen.insert(VNI).second)
232 continue;
233 assert(!VNI->isUnused() && "Unused valno used by live segment");
234 VNI->id = (unsigned)valnos.size();
235 valnos.push_back(VNI);
236 }
237 }
238
239 /// This method is used when we want to extend the segment specified by I to end
240 /// at the specified endpoint. To do this, we should merge and eliminate all
241 /// segments that this will overlap with. The iterator is not invalidated.
extendSegmentEndTo(iterator I,SlotIndex NewEnd)242 void LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
243 assert(I != end() && "Not a valid segment!");
244 VNInfo *ValNo = I->valno;
245
246 // Search for the first segment that we can't merge with.
247 iterator MergeTo = std::next(I);
248 for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) {
249 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
250 }
251
252 // If NewEnd was in the middle of a segment, make sure to get its endpoint.
253 I->end = std::max(NewEnd, std::prev(MergeTo)->end);
254
255 // If the newly formed segment now touches the segment after it and if they
256 // have the same value number, merge the two segments into one segment.
257 if (MergeTo != end() && MergeTo->start <= I->end &&
258 MergeTo->valno == ValNo) {
259 I->end = MergeTo->end;
260 ++MergeTo;
261 }
262
263 // Erase any dead segments.
264 segments.erase(std::next(I), MergeTo);
265 }
266
267
268 /// This method is used when we want to extend the segment specified by I to
269 /// start at the specified endpoint. To do this, we should merge and eliminate
270 /// all segments that this will overlap with.
271 LiveRange::iterator
extendSegmentStartTo(iterator I,SlotIndex NewStart)272 LiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) {
273 assert(I != end() && "Not a valid segment!");
274 VNInfo *ValNo = I->valno;
275
276 // Search for the first segment that we can't merge with.
277 iterator MergeTo = I;
278 do {
279 if (MergeTo == begin()) {
280 I->start = NewStart;
281 segments.erase(MergeTo, I);
282 return I;
283 }
284 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
285 --MergeTo;
286 } while (NewStart <= MergeTo->start);
287
288 // If we start in the middle of another segment, just delete a range and
289 // extend that segment.
290 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
291 MergeTo->end = I->end;
292 } else {
293 // Otherwise, extend the segment right after.
294 ++MergeTo;
295 MergeTo->start = NewStart;
296 MergeTo->end = I->end;
297 }
298
299 segments.erase(std::next(MergeTo), std::next(I));
300 return MergeTo;
301 }
302
append(const Segment S)303 void LiveRange::append(const Segment S) {
304 // Check that the segment belongs to the back of the list.
305 assert(segments.empty() || segments.back().end <= S.start);
306 segments.push_back(S);
307 }
308
addSegmentFrom(Segment S,iterator From)309 LiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) {
310 SlotIndex Start = S.start, End = S.end;
311 iterator it = std::upper_bound(From, end(), Start);
312
313 // If the inserted segment starts in the middle or right at the end of
314 // another segment, just extend that segment to contain the segment of S.
315 if (it != begin()) {
316 iterator B = std::prev(it);
317 if (S.valno == B->valno) {
318 if (B->start <= Start && B->end >= Start) {
319 extendSegmentEndTo(B, End);
320 return B;
321 }
322 } else {
323 // Check to make sure that we are not overlapping two live segments with
324 // different valno's.
325 assert(B->end <= Start &&
326 "Cannot overlap two segments with differing ValID's"
327 " (did you def the same reg twice in a MachineInstr?)");
328 }
329 }
330
331 // Otherwise, if this segment ends in the middle of, or right next to, another
332 // segment, merge it into that segment.
333 if (it != end()) {
334 if (S.valno == it->valno) {
335 if (it->start <= End) {
336 it = extendSegmentStartTo(it, Start);
337
338 // If S is a complete superset of a segment, we may need to grow its
339 // endpoint as well.
340 if (End > it->end)
341 extendSegmentEndTo(it, End);
342 return it;
343 }
344 } else {
345 // Check to make sure that we are not overlapping two live segments with
346 // different valno's.
347 assert(it->start >= End &&
348 "Cannot overlap two segments with differing ValID's");
349 }
350 }
351
352 // Otherwise, this is just a new segment that doesn't interact with anything.
353 // Insert it.
354 return segments.insert(it, S);
355 }
356
357 /// extendInBlock - If this range is live before Kill in the basic
358 /// block that starts at StartIdx, extend it to be live up to Kill and return
359 /// the value. If there is no live range before Kill, return NULL.
extendInBlock(SlotIndex StartIdx,SlotIndex Kill)360 VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
361 if (empty())
362 return nullptr;
363 iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
364 if (I == begin())
365 return nullptr;
366 --I;
367 if (I->end <= StartIdx)
368 return nullptr;
369 if (I->end < Kill)
370 extendSegmentEndTo(I, Kill);
371 return I->valno;
372 }
373
374 /// Remove the specified segment from this range. Note that the segment must
375 /// be in a single Segment in its entirety.
removeSegment(SlotIndex Start,SlotIndex End,bool RemoveDeadValNo)376 void LiveRange::removeSegment(SlotIndex Start, SlotIndex End,
377 bool RemoveDeadValNo) {
378 // Find the Segment containing this span.
379 iterator I = find(Start);
380 assert(I != end() && "Segment is not in range!");
381 assert(I->containsInterval(Start, End)
382 && "Segment is not entirely in range!");
383
384 // If the span we are removing is at the start of the Segment, adjust it.
385 VNInfo *ValNo = I->valno;
386 if (I->start == Start) {
387 if (I->end == End) {
388 if (RemoveDeadValNo) {
389 // Check if val# is dead.
390 bool isDead = true;
391 for (const_iterator II = begin(), EE = end(); II != EE; ++II)
392 if (II != I && II->valno == ValNo) {
393 isDead = false;
394 break;
395 }
396 if (isDead) {
397 // Now that ValNo is dead, remove it.
398 markValNoForDeletion(ValNo);
399 }
400 }
401
402 segments.erase(I); // Removed the whole Segment.
403 } else
404 I->start = End;
405 return;
406 }
407
408 // Otherwise if the span we are removing is at the end of the Segment,
409 // adjust the other way.
410 if (I->end == End) {
411 I->end = Start;
412 return;
413 }
414
415 // Otherwise, we are splitting the Segment into two pieces.
416 SlotIndex OldEnd = I->end;
417 I->end = Start; // Trim the old segment.
418
419 // Insert the new one.
420 segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
421 }
422
423 /// removeValNo - Remove all the segments defined by the specified value#.
424 /// Also remove the value# from value# list.
removeValNo(VNInfo * ValNo)425 void LiveRange::removeValNo(VNInfo *ValNo) {
426 if (empty()) return;
427 iterator I = end();
428 iterator E = begin();
429 do {
430 --I;
431 if (I->valno == ValNo)
432 segments.erase(I);
433 } while (I != E);
434 // Now that ValNo is dead, remove it.
435 markValNoForDeletion(ValNo);
436 }
437
join(LiveRange & Other,const int * LHSValNoAssignments,const int * RHSValNoAssignments,SmallVectorImpl<VNInfo * > & NewVNInfo)438 void LiveRange::join(LiveRange &Other,
439 const int *LHSValNoAssignments,
440 const int *RHSValNoAssignments,
441 SmallVectorImpl<VNInfo *> &NewVNInfo) {
442 verify();
443
444 // Determine if any of our values are mapped. This is uncommon, so we want
445 // to avoid the range scan if not.
446 bool MustMapCurValNos = false;
447 unsigned NumVals = getNumValNums();
448 unsigned NumNewVals = NewVNInfo.size();
449 for (unsigned i = 0; i != NumVals; ++i) {
450 unsigned LHSValID = LHSValNoAssignments[i];
451 if (i != LHSValID ||
452 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
453 MustMapCurValNos = true;
454 break;
455 }
456 }
457
458 // If we have to apply a mapping to our base range assignment, rewrite it now.
459 if (MustMapCurValNos && !empty()) {
460 // Map the first live range.
461
462 iterator OutIt = begin();
463 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
464 for (iterator I = std::next(OutIt), E = end(); I != E; ++I) {
465 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
466 assert(nextValNo && "Huh?");
467
468 // If this live range has the same value # as its immediate predecessor,
469 // and if they are neighbors, remove one Segment. This happens when we
470 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
471 if (OutIt->valno == nextValNo && OutIt->end == I->start) {
472 OutIt->end = I->end;
473 } else {
474 // Didn't merge. Move OutIt to the next segment,
475 ++OutIt;
476 OutIt->valno = nextValNo;
477 if (OutIt != I) {
478 OutIt->start = I->start;
479 OutIt->end = I->end;
480 }
481 }
482 }
483 // If we merge some segments, chop off the end.
484 ++OutIt;
485 segments.erase(OutIt, end());
486 }
487
488 // Rewrite Other values before changing the VNInfo ids.
489 // This can leave Other in an invalid state because we're not coalescing
490 // touching segments that now have identical values. That's OK since Other is
491 // not supposed to be valid after calling join();
492 for (Segment &S : Other.segments)
493 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
494
495 // Update val# info. Renumber them and make sure they all belong to this
496 // LiveRange now. Also remove dead val#'s.
497 unsigned NumValNos = 0;
498 for (unsigned i = 0; i < NumNewVals; ++i) {
499 VNInfo *VNI = NewVNInfo[i];
500 if (VNI) {
501 if (NumValNos >= NumVals)
502 valnos.push_back(VNI);
503 else
504 valnos[NumValNos] = VNI;
505 VNI->id = NumValNos++; // Renumber val#.
506 }
507 }
508 if (NumNewVals < NumVals)
509 valnos.resize(NumNewVals); // shrinkify
510
511 // Okay, now insert the RHS live segments into the LHS.
512 LiveRangeUpdater Updater(this);
513 for (Segment &S : Other.segments)
514 Updater.add(S);
515 }
516
517 /// Merge all of the segments in RHS into this live range as the specified
518 /// value number. The segments in RHS are allowed to overlap with segments in
519 /// the current range, but only if the overlapping segments have the
520 /// specified value number.
MergeSegmentsInAsValue(const LiveRange & RHS,VNInfo * LHSValNo)521 void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS,
522 VNInfo *LHSValNo) {
523 LiveRangeUpdater Updater(this);
524 for (const Segment &S : RHS.segments)
525 Updater.add(S.start, S.end, LHSValNo);
526 }
527
528 /// MergeValueInAsValue - Merge all of the live segments of a specific val#
529 /// in RHS into this live range as the specified value number.
530 /// The segments in RHS are allowed to overlap with segments in the
531 /// current range, it will replace the value numbers of the overlaped
532 /// segments with the specified value number.
MergeValueInAsValue(const LiveRange & RHS,const VNInfo * RHSValNo,VNInfo * LHSValNo)533 void LiveRange::MergeValueInAsValue(const LiveRange &RHS,
534 const VNInfo *RHSValNo,
535 VNInfo *LHSValNo) {
536 LiveRangeUpdater Updater(this);
537 for (const Segment &S : RHS.segments)
538 if (S.valno == RHSValNo)
539 Updater.add(S.start, S.end, LHSValNo);
540 }
541
542 /// MergeValueNumberInto - This method is called when two value nubmers
543 /// are found to be equivalent. This eliminates V1, replacing all
544 /// segments with the V1 value number with the V2 value number. This can
545 /// cause merging of V1/V2 values numbers and compaction of the value space.
MergeValueNumberInto(VNInfo * V1,VNInfo * V2)546 VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
547 assert(V1 != V2 && "Identical value#'s are always equivalent!");
548
549 // This code actually merges the (numerically) larger value number into the
550 // smaller value number, which is likely to allow us to compactify the value
551 // space. The only thing we have to be careful of is to preserve the
552 // instruction that defines the result value.
553
554 // Make sure V2 is smaller than V1.
555 if (V1->id < V2->id) {
556 V1->copyFrom(*V2);
557 std::swap(V1, V2);
558 }
559
560 // Merge V1 segments into V2.
561 for (iterator I = begin(); I != end(); ) {
562 iterator S = I++;
563 if (S->valno != V1) continue; // Not a V1 Segment.
564
565 // Okay, we found a V1 live range. If it had a previous, touching, V2 live
566 // range, extend it.
567 if (S != begin()) {
568 iterator Prev = S-1;
569 if (Prev->valno == V2 && Prev->end == S->start) {
570 Prev->end = S->end;
571
572 // Erase this live-range.
573 segments.erase(S);
574 I = Prev+1;
575 S = Prev;
576 }
577 }
578
579 // Okay, now we have a V1 or V2 live range that is maximally merged forward.
580 // Ensure that it is a V2 live-range.
581 S->valno = V2;
582
583 // If we can merge it into later V2 segments, do so now. We ignore any
584 // following V1 segments, as they will be merged in subsequent iterations
585 // of the loop.
586 if (I != end()) {
587 if (I->start == S->end && I->valno == V2) {
588 S->end = I->end;
589 segments.erase(I);
590 I = S+1;
591 }
592 }
593 }
594
595 // Now that V1 is dead, remove it.
596 markValNoForDeletion(V1);
597
598 return V2;
599 }
600
removeEmptySubRanges()601 void LiveInterval::removeEmptySubRanges() {
602 SubRange **NextPtr = &SubRanges;
603 SubRange *I = *NextPtr;
604 while (I != nullptr) {
605 if (!I->empty()) {
606 NextPtr = &I->Next;
607 I = *NextPtr;
608 continue;
609 }
610 // Skip empty subranges until we find the first nonempty one.
611 do {
612 I = I->Next;
613 } while (I != nullptr && I->empty());
614 *NextPtr = I;
615 }
616 }
617
618 /// Helper function for constructMainRangeFromSubranges(): Search the CFG
619 /// backwards until we find a place covered by a LiveRange segment that actually
620 /// has a valno set.
searchForVNI(const SlotIndexes & Indexes,LiveRange & LR,const MachineBasicBlock * MBB,SmallPtrSetImpl<const MachineBasicBlock * > & Visited)621 static VNInfo *searchForVNI(const SlotIndexes &Indexes, LiveRange &LR,
622 const MachineBasicBlock *MBB,
623 SmallPtrSetImpl<const MachineBasicBlock*> &Visited) {
624 // We start the search at the end of MBB.
625 SlotIndex EndIdx = Indexes.getMBBEndIdx(MBB);
626 // In our use case we can't live the area covered by the live segments without
627 // finding an actual VNI def.
628 LiveRange::iterator I = LR.find(EndIdx.getPrevSlot());
629 assert(I != LR.end());
630 LiveRange::Segment &S = *I;
631 if (S.valno != nullptr)
632 return S.valno;
633
634 VNInfo *VNI = nullptr;
635 // Continue at predecessors (we could even go to idom with domtree available).
636 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
637 // Avoid going in circles.
638 if (!Visited.insert(Pred).second)
639 continue;
640
641 VNI = searchForVNI(Indexes, LR, Pred, Visited);
642 if (VNI != nullptr) {
643 S.valno = VNI;
644 break;
645 }
646 }
647
648 return VNI;
649 }
650
determineMissingVNIs(const SlotIndexes & Indexes,LiveInterval & LI)651 static void determineMissingVNIs(const SlotIndexes &Indexes, LiveInterval &LI) {
652 SmallPtrSet<const MachineBasicBlock*, 5> Visited;
653 for (LiveRange::Segment &S : LI.segments) {
654 if (S.valno != nullptr)
655 continue;
656 // This can only happen at the begin of a basic block.
657 assert(S.start.isBlock() && "valno should only be missing at block begin");
658
659 Visited.clear();
660 const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start);
661 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
662 VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited);
663 if (VNI != nullptr) {
664 S.valno = VNI;
665 break;
666 }
667 }
668 assert(S.valno != nullptr && "could not determine valno");
669 }
670 }
671
constructMainRangeFromSubranges(const SlotIndexes & Indexes,VNInfo::Allocator & VNIAllocator)672 void LiveInterval::constructMainRangeFromSubranges(
673 const SlotIndexes &Indexes, VNInfo::Allocator &VNIAllocator) {
674 // The basic observations on which this algorithm is based:
675 // - Each Def/ValNo in a subrange must have a corresponding def on the main
676 // range, but not further defs/valnos are necessary.
677 // - If any of the subranges is live at a point the main liverange has to be
678 // live too, conversily if no subrange is live the main range mustn't be
679 // live either.
680 // We do this by scannig through all the subranges simultaneously creating new
681 // segments in the main range as segments start/ends come up in the subranges.
682 assert(hasSubRanges() && "expected subranges to be present");
683 assert(segments.empty() && valnos.empty() && "expected empty main range");
684
685 // Collect subrange, iterator pairs for the walk and determine first and last
686 // SlotIndex involved.
687 SmallVector<std::pair<const SubRange*, const_iterator>, 4> SRs;
688 SlotIndex First;
689 SlotIndex Last;
690 for (const SubRange &SR : subranges()) {
691 if (SR.empty())
692 continue;
693 SRs.push_back(std::make_pair(&SR, SR.begin()));
694 if (!First.isValid() || SR.segments.front().start < First)
695 First = SR.segments.front().start;
696 if (!Last.isValid() || SR.segments.back().end > Last)
697 Last = SR.segments.back().end;
698 }
699
700 // Walk over all subranges simultaneously.
701 Segment CurrentSegment;
702 bool ConstructingSegment = false;
703 bool NeedVNIFixup = false;
704 unsigned ActiveMask = 0;
705 SlotIndex Pos = First;
706 while (true) {
707 SlotIndex NextPos = Last;
708 enum {
709 NOTHING,
710 BEGIN_SEGMENT,
711 END_SEGMENT,
712 } Event = NOTHING;
713 // Which subregister lanes are affected by the current event.
714 unsigned EventMask = 0;
715 // Whether a BEGIN_SEGMENT is also a valno definition point.
716 bool IsDef = false;
717 // Find the next begin or end of a subrange segment. Combine masks if we
718 // have multiple begins/ends at the same position. Ends take precedence over
719 // Begins.
720 for (auto &SRP : SRs) {
721 const SubRange &SR = *SRP.first;
722 const_iterator &I = SRP.second;
723 // Advance iterator of subrange to a segment involving Pos; the earlier
724 // segments are already merged at this point.
725 while (I != SR.end() &&
726 (I->end < Pos ||
727 (I->end == Pos && (ActiveMask & SR.LaneMask) == 0)))
728 ++I;
729 if (I == SR.end())
730 continue;
731 if ((ActiveMask & SR.LaneMask) == 0 &&
732 Pos <= I->start && I->start <= NextPos) {
733 // Merge multiple begins at the same position.
734 if (I->start == NextPos && Event == BEGIN_SEGMENT) {
735 EventMask |= SR.LaneMask;
736 IsDef |= I->valno->def == I->start;
737 } else if (I->start < NextPos || Event != END_SEGMENT) {
738 Event = BEGIN_SEGMENT;
739 NextPos = I->start;
740 EventMask = SR.LaneMask;
741 IsDef = I->valno->def == I->start;
742 }
743 }
744 if ((ActiveMask & SR.LaneMask) != 0 &&
745 Pos <= I->end && I->end <= NextPos) {
746 // Merge multiple ends at the same position.
747 if (I->end == NextPos && Event == END_SEGMENT)
748 EventMask |= SR.LaneMask;
749 else {
750 Event = END_SEGMENT;
751 NextPos = I->end;
752 EventMask = SR.LaneMask;
753 }
754 }
755 }
756
757 // Advance scan position.
758 Pos = NextPos;
759 if (Event == BEGIN_SEGMENT) {
760 if (ConstructingSegment && IsDef) {
761 // Finish previous segment because we have to start a new one.
762 CurrentSegment.end = Pos;
763 append(CurrentSegment);
764 ConstructingSegment = false;
765 }
766
767 // Start a new segment if necessary.
768 if (!ConstructingSegment) {
769 // Determine value number for the segment.
770 VNInfo *VNI;
771 if (IsDef) {
772 VNI = getNextValue(Pos, VNIAllocator);
773 } else {
774 // We have to reuse an existing value number, if we are lucky
775 // then we already passed one of the predecessor blocks and determined
776 // its value number (with blocks in reverse postorder this would be
777 // always true but we have no such guarantee).
778 assert(Pos.isBlock());
779 const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Pos);
780 // See if any of the predecessor blocks has a lower number and a VNI
781 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
782 SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
783 VNI = getVNInfoBefore(PredEnd);
784 if (VNI != nullptr)
785 break;
786 }
787 // Def will come later: We have to do an extra fixup pass.
788 if (VNI == nullptr)
789 NeedVNIFixup = true;
790 }
791
792 CurrentSegment.start = Pos;
793 CurrentSegment.valno = VNI;
794 ConstructingSegment = true;
795 }
796 ActiveMask |= EventMask;
797 } else if (Event == END_SEGMENT) {
798 assert(ConstructingSegment);
799 // Finish segment if no lane is active anymore.
800 ActiveMask &= ~EventMask;
801 if (ActiveMask == 0) {
802 CurrentSegment.end = Pos;
803 append(CurrentSegment);
804 ConstructingSegment = false;
805 }
806 } else {
807 // We reached the end of the last subranges and can stop.
808 assert(Event == NOTHING);
809 break;
810 }
811 }
812
813 // We might not be able to assign new valnos for all segments if the basic
814 // block containing the definition comes after a segment using the valno.
815 // Do a fixup pass for this uncommon case.
816 if (NeedVNIFixup)
817 determineMissingVNIs(Indexes, *this);
818
819 assert(ActiveMask == 0 && !ConstructingSegment && "all segments ended");
820 verify();
821 }
822
getSize() const823 unsigned LiveInterval::getSize() const {
824 unsigned Sum = 0;
825 for (const Segment &S : segments)
826 Sum += S.start.distance(S.end);
827 return Sum;
828 }
829
operator <<(raw_ostream & os,const LiveRange::Segment & S)830 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) {
831 return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")";
832 }
833
834 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const835 void LiveRange::Segment::dump() const {
836 dbgs() << *this << "\n";
837 }
838 #endif
839
print(raw_ostream & OS) const840 void LiveRange::print(raw_ostream &OS) const {
841 if (empty())
842 OS << "EMPTY";
843 else {
844 for (const Segment &S : segments) {
845 OS << S;
846 assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
847 }
848 }
849
850 // Print value number info.
851 if (getNumValNums()) {
852 OS << " ";
853 unsigned vnum = 0;
854 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
855 ++i, ++vnum) {
856 const VNInfo *vni = *i;
857 if (vnum) OS << " ";
858 OS << vnum << "@";
859 if (vni->isUnused()) {
860 OS << "x";
861 } else {
862 OS << vni->def;
863 if (vni->isPHIDef())
864 OS << "-phi";
865 }
866 }
867 }
868 }
869
print(raw_ostream & OS) const870 void LiveInterval::print(raw_ostream &OS) const {
871 OS << PrintReg(reg) << ' ';
872 super::print(OS);
873 // Print subranges
874 for (const SubRange &SR : subranges()) {
875 OS << format(" L%04X ", SR.LaneMask) << SR;
876 }
877 }
878
879 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const880 void LiveRange::dump() const {
881 dbgs() << *this << "\n";
882 }
883
dump() const884 void LiveInterval::dump() const {
885 dbgs() << *this << "\n";
886 }
887 #endif
888
889 #ifndef NDEBUG
verify() const890 void LiveRange::verify() const {
891 for (const_iterator I = begin(), E = end(); I != E; ++I) {
892 assert(I->start.isValid());
893 assert(I->end.isValid());
894 assert(I->start < I->end);
895 assert(I->valno != nullptr);
896 assert(I->valno->id < valnos.size());
897 assert(I->valno == valnos[I->valno->id]);
898 if (std::next(I) != E) {
899 assert(I->end <= std::next(I)->start);
900 if (I->end == std::next(I)->start)
901 assert(I->valno != std::next(I)->valno);
902 }
903 }
904 }
905
verify(const MachineRegisterInfo * MRI) const906 void LiveInterval::verify(const MachineRegisterInfo *MRI) const {
907 super::verify();
908
909 // Make sure SubRanges are fine and LaneMasks are disjunct.
910 unsigned Mask = 0;
911 unsigned MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) : ~0u;
912 for (const SubRange &SR : subranges()) {
913 // Subrange lanemask should be disjunct to any previous subrange masks.
914 assert((Mask & SR.LaneMask) == 0);
915 Mask |= SR.LaneMask;
916
917 // subrange mask should not contained in maximum lane mask for the vreg.
918 assert((Mask & ~MaxMask) == 0);
919
920 SR.verify();
921 // Main liverange should cover subrange.
922 assert(covers(SR));
923 }
924 }
925 #endif
926
927
928 //===----------------------------------------------------------------------===//
929 // LiveRangeUpdater class
930 //===----------------------------------------------------------------------===//
931 //
932 // The LiveRangeUpdater class always maintains these invariants:
933 //
934 // - When LastStart is invalid, Spills is empty and the iterators are invalid.
935 // This is the initial state, and the state created by flush().
936 // In this state, isDirty() returns false.
937 //
938 // Otherwise, segments are kept in three separate areas:
939 //
940 // 1. [begin; WriteI) at the front of LR.
941 // 2. [ReadI; end) at the back of LR.
942 // 3. Spills.
943 //
944 // - LR.begin() <= WriteI <= ReadI <= LR.end().
945 // - Segments in all three areas are fully ordered and coalesced.
946 // - Segments in area 1 precede and can't coalesce with segments in area 2.
947 // - Segments in Spills precede and can't coalesce with segments in area 2.
948 // - No coalescing is possible between segments in Spills and segments in area
949 // 1, and there are no overlapping segments.
950 //
951 // The segments in Spills are not ordered with respect to the segments in area
952 // 1. They need to be merged.
953 //
954 // When they exist, Spills.back().start <= LastStart,
955 // and WriteI[-1].start <= LastStart.
956
print(raw_ostream & OS) const957 void LiveRangeUpdater::print(raw_ostream &OS) const {
958 if (!isDirty()) {
959 if (LR)
960 OS << "Clean updater: " << *LR << '\n';
961 else
962 OS << "Null updater.\n";
963 return;
964 }
965 assert(LR && "Can't have null LR in dirty updater.");
966 OS << " updater with gap = " << (ReadI - WriteI)
967 << ", last start = " << LastStart
968 << ":\n Area 1:";
969 for (const auto &S : make_range(LR->begin(), WriteI))
970 OS << ' ' << S;
971 OS << "\n Spills:";
972 for (unsigned I = 0, E = Spills.size(); I != E; ++I)
973 OS << ' ' << Spills[I];
974 OS << "\n Area 2:";
975 for (const auto &S : make_range(ReadI, LR->end()))
976 OS << ' ' << S;
977 OS << '\n';
978 }
979
dump() const980 void LiveRangeUpdater::dump() const
981 {
982 print(errs());
983 }
984
985 // Determine if A and B should be coalesced.
coalescable(const LiveRange::Segment & A,const LiveRange::Segment & B)986 static inline bool coalescable(const LiveRange::Segment &A,
987 const LiveRange::Segment &B) {
988 assert(A.start <= B.start && "Unordered live segments.");
989 if (A.end == B.start)
990 return A.valno == B.valno;
991 if (A.end < B.start)
992 return false;
993 assert(A.valno == B.valno && "Cannot overlap different values");
994 return true;
995 }
996
add(LiveRange::Segment Seg)997 void LiveRangeUpdater::add(LiveRange::Segment Seg) {
998 assert(LR && "Cannot add to a null destination");
999
1000 // Flush the state if Start moves backwards.
1001 if (!LastStart.isValid() || LastStart > Seg.start) {
1002 if (isDirty())
1003 flush();
1004 // This brings us to an uninitialized state. Reinitialize.
1005 assert(Spills.empty() && "Leftover spilled segments");
1006 WriteI = ReadI = LR->begin();
1007 }
1008
1009 // Remember start for next time.
1010 LastStart = Seg.start;
1011
1012 // Advance ReadI until it ends after Seg.start.
1013 LiveRange::iterator E = LR->end();
1014 if (ReadI != E && ReadI->end <= Seg.start) {
1015 // First try to close the gap between WriteI and ReadI with spills.
1016 if (ReadI != WriteI)
1017 mergeSpills();
1018 // Then advance ReadI.
1019 if (ReadI == WriteI)
1020 ReadI = WriteI = LR->find(Seg.start);
1021 else
1022 while (ReadI != E && ReadI->end <= Seg.start)
1023 *WriteI++ = *ReadI++;
1024 }
1025
1026 assert(ReadI == E || ReadI->end > Seg.start);
1027
1028 // Check if the ReadI segment begins early.
1029 if (ReadI != E && ReadI->start <= Seg.start) {
1030 assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1031 // Bail if Seg is completely contained in ReadI.
1032 if (ReadI->end >= Seg.end)
1033 return;
1034 // Coalesce into Seg.
1035 Seg.start = ReadI->start;
1036 ++ReadI;
1037 }
1038
1039 // Coalesce as much as possible from ReadI into Seg.
1040 while (ReadI != E && coalescable(Seg, *ReadI)) {
1041 Seg.end = std::max(Seg.end, ReadI->end);
1042 ++ReadI;
1043 }
1044
1045 // Try coalescing Spills.back() into Seg.
1046 if (!Spills.empty() && coalescable(Spills.back(), Seg)) {
1047 Seg.start = Spills.back().start;
1048 Seg.end = std::max(Spills.back().end, Seg.end);
1049 Spills.pop_back();
1050 }
1051
1052 // Try coalescing Seg into WriteI[-1].
1053 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) {
1054 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1055 return;
1056 }
1057
1058 // Seg doesn't coalesce with anything, and needs to be inserted somewhere.
1059 if (WriteI != ReadI) {
1060 *WriteI++ = Seg;
1061 return;
1062 }
1063
1064 // Finally, append to LR or Spills.
1065 if (WriteI == E) {
1066 LR->segments.push_back(Seg);
1067 WriteI = ReadI = LR->end();
1068 } else
1069 Spills.push_back(Seg);
1070 }
1071
1072 // Merge as many spilled segments as possible into the gap between WriteI
1073 // and ReadI. Advance WriteI to reflect the inserted instructions.
mergeSpills()1074 void LiveRangeUpdater::mergeSpills() {
1075 // Perform a backwards merge of Spills and [SpillI;WriteI).
1076 size_t GapSize = ReadI - WriteI;
1077 size_t NumMoved = std::min(Spills.size(), GapSize);
1078 LiveRange::iterator Src = WriteI;
1079 LiveRange::iterator Dst = Src + NumMoved;
1080 LiveRange::iterator SpillSrc = Spills.end();
1081 LiveRange::iterator B = LR->begin();
1082
1083 // This is the new WriteI position after merging spills.
1084 WriteI = Dst;
1085
1086 // Now merge Src and Spills backwards.
1087 while (Src != Dst) {
1088 if (Src != B && Src[-1].start > SpillSrc[-1].start)
1089 *--Dst = *--Src;
1090 else
1091 *--Dst = *--SpillSrc;
1092 }
1093 assert(NumMoved == size_t(Spills.end() - SpillSrc));
1094 Spills.erase(SpillSrc, Spills.end());
1095 }
1096
flush()1097 void LiveRangeUpdater::flush() {
1098 if (!isDirty())
1099 return;
1100 // Clear the dirty state.
1101 LastStart = SlotIndex();
1102
1103 assert(LR && "Cannot add to a null destination");
1104
1105 // Nothing to merge?
1106 if (Spills.empty()) {
1107 LR->segments.erase(WriteI, ReadI);
1108 LR->verify();
1109 return;
1110 }
1111
1112 // Resize the WriteI - ReadI gap to match Spills.
1113 size_t GapSize = ReadI - WriteI;
1114 if (GapSize < Spills.size()) {
1115 // The gap is too small. Make some room.
1116 size_t WritePos = WriteI - LR->begin();
1117 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1118 // This also invalidated ReadI, but it is recomputed below.
1119 WriteI = LR->begin() + WritePos;
1120 } else {
1121 // Shrink the gap if necessary.
1122 LR->segments.erase(WriteI + Spills.size(), ReadI);
1123 }
1124 ReadI = WriteI + Spills.size();
1125 mergeSpills();
1126 LR->verify();
1127 }
1128
Classify(const LiveInterval * LI)1129 unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) {
1130 // Create initial equivalence classes.
1131 EqClass.clear();
1132 EqClass.grow(LI->getNumValNums());
1133
1134 const VNInfo *used = nullptr, *unused = nullptr;
1135
1136 // Determine connections.
1137 for (const VNInfo *VNI : LI->valnos) {
1138 // Group all unused values into one class.
1139 if (VNI->isUnused()) {
1140 if (unused)
1141 EqClass.join(unused->id, VNI->id);
1142 unused = VNI;
1143 continue;
1144 }
1145 used = VNI;
1146 if (VNI->isPHIDef()) {
1147 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1148 assert(MBB && "Phi-def has no defining MBB");
1149 // Connect to values live out of predecessors.
1150 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
1151 PE = MBB->pred_end(); PI != PE; ++PI)
1152 if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
1153 EqClass.join(VNI->id, PVNI->id);
1154 } else {
1155 // Normal value defined by an instruction. Check for two-addr redef.
1156 // FIXME: This could be coincidental. Should we really check for a tied
1157 // operand constraint?
1158 // Note that VNI->def may be a use slot for an early clobber def.
1159 if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def))
1160 EqClass.join(VNI->id, UVNI->id);
1161 }
1162 }
1163
1164 // Lump all the unused values in with the last used value.
1165 if (used && unused)
1166 EqClass.join(used->id, unused->id);
1167
1168 EqClass.compress();
1169 return EqClass.getNumClasses();
1170 }
1171
Distribute(LiveInterval * LIV[],MachineRegisterInfo & MRI)1172 void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
1173 MachineRegisterInfo &MRI) {
1174 assert(LIV[0] && "LIV[0] must be set");
1175 LiveInterval &LI = *LIV[0];
1176
1177 // Rewrite instructions.
1178 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
1179 RE = MRI.reg_end(); RI != RE;) {
1180 MachineOperand &MO = *RI;
1181 MachineInstr *MI = RI->getParent();
1182 ++RI;
1183 // DBG_VALUE instructions don't have slot indexes, so get the index of the
1184 // instruction before them.
1185 // Normally, DBG_VALUE instructions are removed before this function is
1186 // called, but it is not a requirement.
1187 SlotIndex Idx;
1188 if (MI->isDebugValue())
1189 Idx = LIS.getSlotIndexes()->getIndexBefore(MI);
1190 else
1191 Idx = LIS.getInstructionIndex(MI);
1192 LiveQueryResult LRQ = LI.Query(Idx);
1193 const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
1194 // In the case of an <undef> use that isn't tied to any def, VNI will be
1195 // NULL. If the use is tied to a def, VNI will be the defined value.
1196 if (!VNI)
1197 continue;
1198 MO.setReg(LIV[getEqClass(VNI)]->reg);
1199 }
1200
1201 // Move runs to new intervals.
1202 LiveInterval::iterator J = LI.begin(), E = LI.end();
1203 while (J != E && EqClass[J->valno->id] == 0)
1204 ++J;
1205 for (LiveInterval::iterator I = J; I != E; ++I) {
1206 if (unsigned eq = EqClass[I->valno->id]) {
1207 assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
1208 "New intervals should be empty");
1209 LIV[eq]->segments.push_back(*I);
1210 } else
1211 *J++ = *I;
1212 }
1213 // TODO: do not cheat anymore by simply cleaning all subranges
1214 LI.clearSubRanges();
1215 LI.segments.erase(J, E);
1216
1217 // Transfer VNInfos to their new owners and renumber them.
1218 unsigned j = 0, e = LI.getNumValNums();
1219 while (j != e && EqClass[j] == 0)
1220 ++j;
1221 for (unsigned i = j; i != e; ++i) {
1222 VNInfo *VNI = LI.getValNumInfo(i);
1223 if (unsigned eq = EqClass[i]) {
1224 VNI->id = LIV[eq]->getNumValNums();
1225 LIV[eq]->valnos.push_back(VNI);
1226 } else {
1227 VNI->id = j;
1228 LI.valnos[j++] = VNI;
1229 }
1230 }
1231 LI.valnos.resize(j);
1232 }
1233