• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 interval 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 intervals can have holes,
15 // i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
16 // individual range is represented as an instance of LiveRange, and the whole
17 // interval is represented as an instance of LiveInterval.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "llvm/CodeGen/LiveInterval.h"
22 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SmallSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Target/TargetRegisterInfo.h"
30 #include <algorithm>
31 using namespace llvm;
32 
find(SlotIndex Pos)33 LiveInterval::iterator LiveInterval::find(SlotIndex Pos) {
34   // This algorithm is basically std::upper_bound.
35   // Unfortunately, std::upper_bound cannot be used with mixed types until we
36   // adopt C++0x. Many libraries can do it, but not all.
37   if (empty() || Pos >= endIndex())
38     return end();
39   iterator I = begin();
40   size_t Len = ranges.size();
41   do {
42     size_t Mid = Len >> 1;
43     if (Pos < I[Mid].end)
44       Len = Mid;
45     else
46       I += Mid + 1, Len -= Mid + 1;
47   } while (Len);
48   return I;
49 }
50 
51 /// killedInRange - Return true if the interval has kills in [Start,End).
killedInRange(SlotIndex Start,SlotIndex End) const52 bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
53   Ranges::const_iterator r =
54     std::lower_bound(ranges.begin(), ranges.end(), End);
55 
56   // Now r points to the first interval with start >= End, or ranges.end().
57   if (r == ranges.begin())
58     return false;
59 
60   --r;
61   // Now r points to the last interval with end <= End.
62   // r->end is the kill point.
63   return r->end >= Start && r->end < End;
64 }
65 
66 // overlaps - Return true if the intersection of the two live intervals is
67 // not empty.
68 //
69 // An example for overlaps():
70 //
71 // 0: A = ...
72 // 4: B = ...
73 // 8: C = A + B ;; last use of A
74 //
75 // The live intervals should look like:
76 //
77 // A = [3, 11)
78 // B = [7, x)
79 // C = [11, y)
80 //
81 // A->overlaps(C) should return false since we want to be able to join
82 // A and C.
83 //
overlapsFrom(const LiveInterval & other,const_iterator StartPos) const84 bool LiveInterval::overlapsFrom(const LiveInterval& other,
85                                 const_iterator StartPos) const {
86   assert(!empty() && "empty interval");
87   const_iterator i = begin();
88   const_iterator ie = end();
89   const_iterator j = StartPos;
90   const_iterator je = other.end();
91 
92   assert((StartPos->start <= i->start || StartPos == other.begin()) &&
93          StartPos != other.end() && "Bogus start position hint!");
94 
95   if (i->start < j->start) {
96     i = std::upper_bound(i, ie, j->start);
97     if (i != ranges.begin()) --i;
98   } else if (j->start < i->start) {
99     ++StartPos;
100     if (StartPos != other.end() && StartPos->start <= i->start) {
101       assert(StartPos < other.end() && i < end());
102       j = std::upper_bound(j, je, i->start);
103       if (j != other.ranges.begin()) --j;
104     }
105   } else {
106     return true;
107   }
108 
109   if (j == je) return false;
110 
111   while (i != ie) {
112     if (i->start > j->start) {
113       std::swap(i, j);
114       std::swap(ie, je);
115     }
116 
117     if (i->end > j->start)
118       return true;
119     ++i;
120   }
121 
122   return false;
123 }
124 
125 /// overlaps - Return true if the live interval overlaps a range specified
126 /// by [Start, End).
overlaps(SlotIndex Start,SlotIndex End) const127 bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
128   assert(Start < End && "Invalid range");
129   const_iterator I = std::lower_bound(begin(), end(), End);
130   return I != begin() && (--I)->end > Start;
131 }
132 
133 
134 /// ValNo is dead, remove it.  If it is the largest value number, just nuke it
135 /// (and any other deleted values neighboring it), otherwise mark it as ~1U so
136 /// it can be nuked later.
markValNoForDeletion(VNInfo * ValNo)137 void LiveInterval::markValNoForDeletion(VNInfo *ValNo) {
138   if (ValNo->id == getNumValNums()-1) {
139     do {
140       valnos.pop_back();
141     } while (!valnos.empty() && valnos.back()->isUnused());
142   } else {
143     ValNo->setIsUnused(true);
144   }
145 }
146 
147 /// RenumberValues - Renumber all values in order of appearance and delete the
148 /// remaining unused values.
RenumberValues(LiveIntervals & lis)149 void LiveInterval::RenumberValues(LiveIntervals &lis) {
150   SmallPtrSet<VNInfo*, 8> Seen;
151   valnos.clear();
152   for (const_iterator I = begin(), E = end(); I != E; ++I) {
153     VNInfo *VNI = I->valno;
154     if (!Seen.insert(VNI))
155       continue;
156     assert(!VNI->isUnused() && "Unused valno used by live range");
157     VNI->id = (unsigned)valnos.size();
158     valnos.push_back(VNI);
159   }
160 }
161 
162 /// extendIntervalEndTo - This method is used when we want to extend the range
163 /// specified by I to end at the specified endpoint.  To do this, we should
164 /// merge and eliminate all ranges that this will overlap with.  The iterator is
165 /// not invalidated.
extendIntervalEndTo(Ranges::iterator I,SlotIndex NewEnd)166 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
167   assert(I != ranges.end() && "Not a valid interval!");
168   VNInfo *ValNo = I->valno;
169 
170   // Search for the first interval that we can't merge with.
171   Ranges::iterator MergeTo = llvm::next(I);
172   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
173     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
174   }
175 
176   // If NewEnd was in the middle of an interval, make sure to get its endpoint.
177   I->end = std::max(NewEnd, prior(MergeTo)->end);
178 
179   // Erase any dead ranges.
180   ranges.erase(llvm::next(I), MergeTo);
181 
182   // If the newly formed range now touches the range after it and if they have
183   // the same value number, merge the two ranges into one range.
184   Ranges::iterator Next = llvm::next(I);
185   if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) {
186     I->end = Next->end;
187     ranges.erase(Next);
188   }
189 }
190 
191 
192 /// extendIntervalStartTo - This method is used when we want to extend the range
193 /// specified by I to start at the specified endpoint.  To do this, we should
194 /// merge and eliminate all ranges that this will overlap with.
195 LiveInterval::Ranges::iterator
extendIntervalStartTo(Ranges::iterator I,SlotIndex NewStart)196 LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) {
197   assert(I != ranges.end() && "Not a valid interval!");
198   VNInfo *ValNo = I->valno;
199 
200   // Search for the first interval that we can't merge with.
201   Ranges::iterator MergeTo = I;
202   do {
203     if (MergeTo == ranges.begin()) {
204       I->start = NewStart;
205       ranges.erase(MergeTo, I);
206       return I;
207     }
208     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
209     --MergeTo;
210   } while (NewStart <= MergeTo->start);
211 
212   // If we start in the middle of another interval, just delete a range and
213   // extend that interval.
214   if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
215     MergeTo->end = I->end;
216   } else {
217     // Otherwise, extend the interval right after.
218     ++MergeTo;
219     MergeTo->start = NewStart;
220     MergeTo->end = I->end;
221   }
222 
223   ranges.erase(llvm::next(MergeTo), llvm::next(I));
224   return MergeTo;
225 }
226 
227 LiveInterval::iterator
addRangeFrom(LiveRange LR,iterator From)228 LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
229   SlotIndex Start = LR.start, End = LR.end;
230   iterator it = std::upper_bound(From, ranges.end(), Start);
231 
232   // If the inserted interval starts in the middle or right at the end of
233   // another interval, just extend that interval to contain the range of LR.
234   if (it != ranges.begin()) {
235     iterator B = prior(it);
236     if (LR.valno == B->valno) {
237       if (B->start <= Start && B->end >= Start) {
238         extendIntervalEndTo(B, End);
239         return B;
240       }
241     } else {
242       // Check to make sure that we are not overlapping two live ranges with
243       // different valno's.
244       assert(B->end <= Start &&
245              "Cannot overlap two LiveRanges with differing ValID's"
246              " (did you def the same reg twice in a MachineInstr?)");
247     }
248   }
249 
250   // Otherwise, if this range ends in the middle of, or right next to, another
251   // interval, merge it into that interval.
252   if (it != ranges.end()) {
253     if (LR.valno == it->valno) {
254       if (it->start <= End) {
255         it = extendIntervalStartTo(it, Start);
256 
257         // If LR is a complete superset of an interval, we may need to grow its
258         // endpoint as well.
259         if (End > it->end)
260           extendIntervalEndTo(it, End);
261         return it;
262       }
263     } else {
264       // Check to make sure that we are not overlapping two live ranges with
265       // different valno's.
266       assert(it->start >= End &&
267              "Cannot overlap two LiveRanges with differing ValID's");
268     }
269   }
270 
271   // Otherwise, this is just a new range that doesn't interact with anything.
272   // Insert it.
273   return ranges.insert(it, LR);
274 }
275 
276 /// extendInBlock - If this interval is live before Kill in the basic
277 /// block that starts at StartIdx, extend it to be live up to Kill and return
278 /// the value. If there is no live range before Kill, return NULL.
extendInBlock(SlotIndex StartIdx,SlotIndex Kill)279 VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
280   if (empty())
281     return 0;
282   iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
283   if (I == begin())
284     return 0;
285   --I;
286   if (I->end <= StartIdx)
287     return 0;
288   if (I->end < Kill)
289     extendIntervalEndTo(I, Kill);
290   return I->valno;
291 }
292 
293 /// removeRange - Remove the specified range from this interval.  Note that
294 /// the range must be in a single LiveRange in its entirety.
removeRange(SlotIndex Start,SlotIndex End,bool RemoveDeadValNo)295 void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
296                                bool RemoveDeadValNo) {
297   // Find the LiveRange containing this span.
298   Ranges::iterator I = find(Start);
299   assert(I != ranges.end() && "Range is not in interval!");
300   assert(I->containsRange(Start, End) && "Range is not entirely in interval!");
301 
302   // If the span we are removing is at the start of the LiveRange, adjust it.
303   VNInfo *ValNo = I->valno;
304   if (I->start == Start) {
305     if (I->end == End) {
306       if (RemoveDeadValNo) {
307         // Check if val# is dead.
308         bool isDead = true;
309         for (const_iterator II = begin(), EE = end(); II != EE; ++II)
310           if (II != I && II->valno == ValNo) {
311             isDead = false;
312             break;
313           }
314         if (isDead) {
315           // Now that ValNo is dead, remove it.
316           markValNoForDeletion(ValNo);
317         }
318       }
319 
320       ranges.erase(I);  // Removed the whole LiveRange.
321     } else
322       I->start = End;
323     return;
324   }
325 
326   // Otherwise if the span we are removing is at the end of the LiveRange,
327   // adjust the other way.
328   if (I->end == End) {
329     I->end = Start;
330     return;
331   }
332 
333   // Otherwise, we are splitting the LiveRange into two pieces.
334   SlotIndex OldEnd = I->end;
335   I->end = Start;   // Trim the old interval.
336 
337   // Insert the new one.
338   ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo));
339 }
340 
341 /// removeValNo - Remove all the ranges defined by the specified value#.
342 /// Also remove the value# from value# list.
removeValNo(VNInfo * ValNo)343 void LiveInterval::removeValNo(VNInfo *ValNo) {
344   if (empty()) return;
345   Ranges::iterator I = ranges.end();
346   Ranges::iterator E = ranges.begin();
347   do {
348     --I;
349     if (I->valno == ValNo)
350       ranges.erase(I);
351   } while (I != E);
352   // Now that ValNo is dead, remove it.
353   markValNoForDeletion(ValNo);
354 }
355 
356 /// findDefinedVNInfo - Find the VNInfo defined by the specified
357 /// index (register interval).
findDefinedVNInfoForRegInt(SlotIndex Idx) const358 VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const {
359   for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end();
360        i != e; ++i) {
361     if ((*i)->def == Idx)
362       return *i;
363   }
364 
365   return 0;
366 }
367 
368 /// join - Join two live intervals (this, and other) together.  This applies
369 /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
370 /// the intervals are not joinable, this aborts.
join(LiveInterval & Other,const int * LHSValNoAssignments,const int * RHSValNoAssignments,SmallVector<VNInfo *,16> & NewVNInfo,MachineRegisterInfo * MRI)371 void LiveInterval::join(LiveInterval &Other,
372                         const int *LHSValNoAssignments,
373                         const int *RHSValNoAssignments,
374                         SmallVector<VNInfo*, 16> &NewVNInfo,
375                         MachineRegisterInfo *MRI) {
376   // Determine if any of our live range values are mapped.  This is uncommon, so
377   // we want to avoid the interval scan if not.
378   bool MustMapCurValNos = false;
379   unsigned NumVals = getNumValNums();
380   unsigned NumNewVals = NewVNInfo.size();
381   for (unsigned i = 0; i != NumVals; ++i) {
382     unsigned LHSValID = LHSValNoAssignments[i];
383     if (i != LHSValID ||
384         (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i)))
385       MustMapCurValNos = true;
386   }
387 
388   // If we have to apply a mapping to our base interval assignment, rewrite it
389   // now.
390   if (MustMapCurValNos) {
391     // Map the first live range.
392     iterator OutIt = begin();
393     OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
394     ++OutIt;
395     for (iterator I = OutIt, E = end(); I != E; ++I) {
396       OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]];
397 
398       // If this live range has the same value # as its immediate predecessor,
399       // and if they are neighbors, remove one LiveRange.  This happens when we
400       // have [0,3:0)[4,7:1) and map 0/1 onto the same value #.
401       if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) {
402         (OutIt-1)->end = OutIt->end;
403       } else {
404         if (I != OutIt) {
405           OutIt->start = I->start;
406           OutIt->end = I->end;
407         }
408 
409         // Didn't merge, on to the next one.
410         ++OutIt;
411       }
412     }
413 
414     // If we merge some live ranges, chop off the end.
415     ranges.erase(OutIt, end());
416   }
417 
418   // Remember assignements because val# ids are changing.
419   SmallVector<unsigned, 16> OtherAssignments;
420   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I)
421     OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]);
422 
423   // Update val# info. Renumber them and make sure they all belong to this
424   // LiveInterval now. Also remove dead val#'s.
425   unsigned NumValNos = 0;
426   for (unsigned i = 0; i < NumNewVals; ++i) {
427     VNInfo *VNI = NewVNInfo[i];
428     if (VNI) {
429       if (NumValNos >= NumVals)
430         valnos.push_back(VNI);
431       else
432         valnos[NumValNos] = VNI;
433       VNI->id = NumValNos++;  // Renumber val#.
434     }
435   }
436   if (NumNewVals < NumVals)
437     valnos.resize(NumNewVals);  // shrinkify
438 
439   // Okay, now insert the RHS live ranges into the LHS.
440   iterator InsertPos = begin();
441   unsigned RangeNo = 0;
442   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
443     // Map the valno in the other live range to the current live range.
444     I->valno = NewVNInfo[OtherAssignments[RangeNo]];
445     assert(I->valno && "Adding a dead range?");
446     InsertPos = addRangeFrom(*I, InsertPos);
447   }
448 
449   ComputeJoinedWeight(Other);
450 }
451 
452 /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
453 /// interval as the specified value number.  The LiveRanges in RHS are
454 /// allowed to overlap with LiveRanges in the current interval, but only if
455 /// the overlapping LiveRanges have the specified value number.
MergeRangesInAsValue(const LiveInterval & RHS,VNInfo * LHSValNo)456 void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
457                                         VNInfo *LHSValNo) {
458   // TODO: Make this more efficient.
459   iterator InsertPos = begin();
460   for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
461     // Map the valno in the other live range to the current live range.
462     LiveRange Tmp = *I;
463     Tmp.valno = LHSValNo;
464     InsertPos = addRangeFrom(Tmp, InsertPos);
465   }
466 }
467 
468 
469 /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
470 /// in RHS into this live interval as the specified value number.
471 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
472 /// current interval, it will replace the value numbers of the overlaped
473 /// live ranges with the specified value number.
MergeValueInAsValue(const LiveInterval & RHS,const VNInfo * RHSValNo,VNInfo * LHSValNo)474 void LiveInterval::MergeValueInAsValue(
475                                     const LiveInterval &RHS,
476                                     const VNInfo *RHSValNo, VNInfo *LHSValNo) {
477   // TODO: Make this more efficient.
478   iterator InsertPos = begin();
479   for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
480     if (I->valno != RHSValNo)
481       continue;
482     // Map the valno in the other live range to the current live range.
483     LiveRange Tmp = *I;
484     Tmp.valno = LHSValNo;
485     InsertPos = addRangeFrom(Tmp, InsertPos);
486   }
487 }
488 
489 
490 /// MergeValueNumberInto - This method is called when two value nubmers
491 /// are found to be equivalent.  This eliminates V1, replacing all
492 /// LiveRanges with the V1 value number with the V2 value number.  This can
493 /// cause merging of V1/V2 values numbers and compaction of the value space.
MergeValueNumberInto(VNInfo * V1,VNInfo * V2)494 VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
495   assert(V1 != V2 && "Identical value#'s are always equivalent!");
496 
497   // This code actually merges the (numerically) larger value number into the
498   // smaller value number, which is likely to allow us to compactify the value
499   // space.  The only thing we have to be careful of is to preserve the
500   // instruction that defines the result value.
501 
502   // Make sure V2 is smaller than V1.
503   if (V1->id < V2->id) {
504     V1->copyFrom(*V2);
505     std::swap(V1, V2);
506   }
507 
508   // Merge V1 live ranges into V2.
509   for (iterator I = begin(); I != end(); ) {
510     iterator LR = I++;
511     if (LR->valno != V1) continue;  // Not a V1 LiveRange.
512 
513     // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
514     // range, extend it.
515     if (LR != begin()) {
516       iterator Prev = LR-1;
517       if (Prev->valno == V2 && Prev->end == LR->start) {
518         Prev->end = LR->end;
519 
520         // Erase this live-range.
521         ranges.erase(LR);
522         I = Prev+1;
523         LR = Prev;
524       }
525     }
526 
527     // Okay, now we have a V1 or V2 live range that is maximally merged forward.
528     // Ensure that it is a V2 live-range.
529     LR->valno = V2;
530 
531     // If we can merge it into later V2 live ranges, do so now.  We ignore any
532     // following V1 live ranges, as they will be merged in subsequent iterations
533     // of the loop.
534     if (I != end()) {
535       if (I->start == LR->end && I->valno == V2) {
536         LR->end = I->end;
537         ranges.erase(I);
538         I = LR+1;
539       }
540     }
541   }
542 
543   // Merge the relevant flags.
544   V2->mergeFlags(V1);
545 
546   // Now that V1 is dead, remove it.
547   markValNoForDeletion(V1);
548 
549   return V2;
550 }
551 
Copy(const LiveInterval & RHS,MachineRegisterInfo * MRI,VNInfo::Allocator & VNInfoAllocator)552 void LiveInterval::Copy(const LiveInterval &RHS,
553                         MachineRegisterInfo *MRI,
554                         VNInfo::Allocator &VNInfoAllocator) {
555   ranges.clear();
556   valnos.clear();
557   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg);
558   MRI->setRegAllocationHint(reg, Hint.first, Hint.second);
559 
560   weight = RHS.weight;
561   for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
562     const VNInfo *VNI = RHS.getValNumInfo(i);
563     createValueCopy(VNI, VNInfoAllocator);
564   }
565   for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
566     const LiveRange &LR = RHS.ranges[i];
567     addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
568   }
569 }
570 
getSize() const571 unsigned LiveInterval::getSize() const {
572   unsigned Sum = 0;
573   for (const_iterator I = begin(), E = end(); I != E; ++I)
574     Sum += I->start.distance(I->end);
575   return Sum;
576 }
577 
578 /// ComputeJoinedWeight - Set the weight of a live interval Joined
579 /// after Other has been merged into it.
ComputeJoinedWeight(const LiveInterval & Other)580 void LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) {
581   // If either of these intervals was spilled, the weight is the
582   // weight of the non-spilled interval.  This can only happen with
583   // iterative coalescers.
584 
585   if (Other.weight != HUGE_VALF) {
586     weight += Other.weight;
587   }
588   else if (weight == HUGE_VALF &&
589       !TargetRegisterInfo::isPhysicalRegister(reg)) {
590     // Remove this assert if you have an iterative coalescer
591     assert(0 && "Joining to spilled interval");
592     weight = Other.weight;
593   }
594   else {
595     // Otherwise the weight stays the same
596     // Remove this assert if you have an iterative coalescer
597     assert(0 && "Joining from spilled interval");
598   }
599 }
600 
operator <<(raw_ostream & os,const LiveRange & LR)601 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) {
602   return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")";
603 }
604 
dump() const605 void LiveRange::dump() const {
606   dbgs() << *this << "\n";
607 }
608 
print(raw_ostream & OS,const TargetRegisterInfo * TRI) const609 void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
610   OS << PrintReg(reg, TRI);
611   if (weight != 0)
612     OS << ',' << weight;
613 
614   if (empty())
615     OS << " EMPTY";
616   else {
617     OS << " = ";
618     for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
619            E = ranges.end(); I != E; ++I) {
620       OS << *I;
621       assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo");
622     }
623   }
624 
625   // Print value number info.
626   if (getNumValNums()) {
627     OS << "  ";
628     unsigned vnum = 0;
629     for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
630          ++i, ++vnum) {
631       const VNInfo *vni = *i;
632       if (vnum) OS << " ";
633       OS << vnum << "@";
634       if (vni->isUnused()) {
635         OS << "x";
636       } else {
637         OS << vni->def;
638         if (vni->isPHIDef())
639           OS << "-phidef";
640         if (vni->hasPHIKill())
641           OS << "-phikill";
642         if (vni->hasRedefByEC())
643           OS << "-ec";
644       }
645     }
646   }
647 }
648 
dump() const649 void LiveInterval::dump() const {
650   dbgs() << *this << "\n";
651 }
652 
653 
print(raw_ostream & os) const654 void LiveRange::print(raw_ostream &os) const {
655   os << *this;
656 }
657 
Classify(const LiveInterval * LI)658 unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) {
659   // Create initial equivalence classes.
660   EqClass.clear();
661   EqClass.grow(LI->getNumValNums());
662 
663   const VNInfo *used = 0, *unused = 0;
664 
665   // Determine connections.
666   for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end();
667        I != E; ++I) {
668     const VNInfo *VNI = *I;
669     // Group all unused values into one class.
670     if (VNI->isUnused()) {
671       if (unused)
672         EqClass.join(unused->id, VNI->id);
673       unused = VNI;
674       continue;
675     }
676     used = VNI;
677     if (VNI->isPHIDef()) {
678       const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
679       assert(MBB && "Phi-def has no defining MBB");
680       // Connect to values live out of predecessors.
681       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
682            PE = MBB->pred_end(); PI != PE; ++PI)
683         if (const VNInfo *PVNI =
684               LI->getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot()))
685           EqClass.join(VNI->id, PVNI->id);
686     } else {
687       // Normal value defined by an instruction. Check for two-addr redef.
688       // FIXME: This could be coincidental. Should we really check for a tied
689       // operand constraint?
690       // Note that VNI->def may be a use slot for an early clobber def.
691       if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getPrevSlot()))
692         EqClass.join(VNI->id, UVNI->id);
693     }
694   }
695 
696   // Lump all the unused values in with the last used value.
697   if (used && unused)
698     EqClass.join(used->id, unused->id);
699 
700   EqClass.compress();
701   return EqClass.getNumClasses();
702 }
703 
Distribute(LiveInterval * LIV[],MachineRegisterInfo & MRI)704 void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
705                                           MachineRegisterInfo &MRI) {
706   assert(LIV[0] && "LIV[0] must be set");
707   LiveInterval &LI = *LIV[0];
708 
709   // Rewrite instructions.
710   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
711        RE = MRI.reg_end(); RI != RE;) {
712     MachineOperand &MO = RI.getOperand();
713     MachineInstr *MI = MO.getParent();
714     ++RI;
715     if (MO.isUse() && MO.isUndef())
716       continue;
717     // DBG_VALUE instructions should have been eliminated earlier.
718     SlotIndex Idx = LIS.getInstructionIndex(MI);
719     Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
720     const VNInfo *VNI = LI.getVNInfoAt(Idx);
721     assert(VNI && "Interval not live at use.");
722     MO.setReg(LIV[getEqClass(VNI)]->reg);
723   }
724 
725   // Move runs to new intervals.
726   LiveInterval::iterator J = LI.begin(), E = LI.end();
727   while (J != E && EqClass[J->valno->id] == 0)
728     ++J;
729   for (LiveInterval::iterator I = J; I != E; ++I) {
730     if (unsigned eq = EqClass[I->valno->id]) {
731       assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
732              "New intervals should be empty");
733       LIV[eq]->ranges.push_back(*I);
734     } else
735       *J++ = *I;
736   }
737   LI.ranges.erase(J, E);
738 
739   // Transfer VNInfos to their new owners and renumber them.
740   unsigned j = 0, e = LI.getNumValNums();
741   while (j != e && EqClass[j] == 0)
742     ++j;
743   for (unsigned i = j; i != e; ++i) {
744     VNInfo *VNI = LI.getValNumInfo(i);
745     if (unsigned eq = EqClass[i]) {
746       VNI->id = LIV[eq]->getNumValNums();
747       LIV[eq]->valnos.push_back(VNI);
748     } else {
749       VNI->id = j;
750       LI.valnos[j++] = VNI;
751     }
752   }
753   LI.valnos.resize(j);
754 }
755