LiveInterval.cpp revision a6c3f80d970ea7a5c8597bca495495832a56a54b
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' abd 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/ADT/SmallSet.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/Support/Streams.h"
25#include "llvm/Target/MRegisterInfo.h"
26#include <algorithm>
27#include <ostream>
28using namespace llvm;
29
30// An example for liveAt():
31//
32// this = [1,4), liveAt(0) will return false. The instruction defining this
33// spans slots [0,3]. The interval belongs to an spilled definition of the
34// variable it represents. This is because slot 1 is used (def slot) and spans
35// up to slot 3 (store slot).
36//
37bool LiveInterval::liveAt(unsigned I) const {
38  Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
39
40  if (r == ranges.begin())
41    return false;
42
43  --r;
44  return r->contains(I);
45}
46
47// overlaps - Return true if the intersection of the two live intervals is
48// not empty.
49//
50// An example for overlaps():
51//
52// 0: A = ...
53// 4: B = ...
54// 8: C = A + B ;; last use of A
55//
56// The live intervals should look like:
57//
58// A = [3, 11)
59// B = [7, x)
60// C = [11, y)
61//
62// A->overlaps(C) should return false since we want to be able to join
63// A and C.
64//
65bool LiveInterval::overlapsFrom(const LiveInterval& other,
66                                const_iterator StartPos) const {
67  const_iterator i = begin();
68  const_iterator ie = end();
69  const_iterator j = StartPos;
70  const_iterator je = other.end();
71
72  assert((StartPos->start <= i->start || StartPos == other.begin()) &&
73         StartPos != other.end() && "Bogus start position hint!");
74
75  if (i->start < j->start) {
76    i = std::upper_bound(i, ie, j->start);
77    if (i != ranges.begin()) --i;
78  } else if (j->start < i->start) {
79    ++StartPos;
80    if (StartPos != other.end() && StartPos->start <= i->start) {
81      assert(StartPos < other.end() && i < end());
82      j = std::upper_bound(j, je, i->start);
83      if (j != other.ranges.begin()) --j;
84    }
85  } else {
86    return true;
87  }
88
89  if (j == je) return false;
90
91  while (i != ie) {
92    if (i->start > j->start) {
93      std::swap(i, j);
94      std::swap(ie, je);
95    }
96
97    if (i->end > j->start)
98      return true;
99    ++i;
100  }
101
102  return false;
103}
104
105/// extendIntervalEndTo - This method is used when we want to extend the range
106/// specified by I to end at the specified endpoint.  To do this, we should
107/// merge and eliminate all ranges that this will overlap with.  The iterator is
108/// not invalidated.
109void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
110  assert(I != ranges.end() && "Not a valid interval!");
111  VNInfo *ValNo = I->valno;
112  unsigned OldEnd = I->end;
113
114  // Search for the first interval that we can't merge with.
115  Ranges::iterator MergeTo = next(I);
116  for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
117    assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
118  }
119
120  // If NewEnd was in the middle of an interval, make sure to get its endpoint.
121  I->end = std::max(NewEnd, prior(MergeTo)->end);
122
123  // Erase any dead ranges.
124  ranges.erase(next(I), MergeTo);
125
126  // Update kill info.
127  removeKills(ValNo, OldEnd, I->end-1);
128
129  // If the newly formed range now touches the range after it and if they have
130  // the same value number, merge the two ranges into one range.
131  Ranges::iterator Next = next(I);
132  if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) {
133    I->end = Next->end;
134    ranges.erase(Next);
135  }
136}
137
138
139/// extendIntervalStartTo - This method is used when we want to extend the range
140/// specified by I to start at the specified endpoint.  To do this, we should
141/// merge and eliminate all ranges that this will overlap with.
142LiveInterval::Ranges::iterator
143LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
144  assert(I != ranges.end() && "Not a valid interval!");
145  VNInfo *ValNo = I->valno;
146
147  // Search for the first interval that we can't merge with.
148  Ranges::iterator MergeTo = I;
149  do {
150    if (MergeTo == ranges.begin()) {
151      I->start = NewStart;
152      ranges.erase(MergeTo, I);
153      return I;
154    }
155    assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
156    --MergeTo;
157  } while (NewStart <= MergeTo->start);
158
159  // If we start in the middle of another interval, just delete a range and
160  // extend that interval.
161  if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
162    MergeTo->end = I->end;
163  } else {
164    // Otherwise, extend the interval right after.
165    ++MergeTo;
166    MergeTo->start = NewStart;
167    MergeTo->end = I->end;
168  }
169
170  ranges.erase(next(MergeTo), next(I));
171  return MergeTo;
172}
173
174LiveInterval::iterator
175LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
176  unsigned Start = LR.start, End = LR.end;
177  iterator it = std::upper_bound(From, ranges.end(), Start);
178
179  // If the inserted interval starts in the middle or right at the end of
180  // another interval, just extend that interval to contain the range of LR.
181  if (it != ranges.begin()) {
182    iterator B = prior(it);
183    if (LR.valno == B->valno) {
184      if (B->start <= Start && B->end >= Start) {
185        extendIntervalEndTo(B, End);
186        return B;
187      }
188    } else {
189      // Check to make sure that we are not overlapping two live ranges with
190      // different valno's.
191      assert(B->end <= Start &&
192             "Cannot overlap two LiveRanges with differing ValID's"
193             " (did you def the same reg twice in a MachineInstr?)");
194    }
195  }
196
197  // Otherwise, if this range ends in the middle of, or right next to, another
198  // interval, merge it into that interval.
199  if (it != ranges.end())
200    if (LR.valno == it->valno) {
201      if (it->start <= End) {
202        it = extendIntervalStartTo(it, Start);
203
204        // If LR is a complete superset of an interval, we may need to grow its
205        // endpoint as well.
206        if (End > it->end)
207          extendIntervalEndTo(it, End);
208        else if (End < it->end)
209          // Overlapping intervals, there might have been a kill here.
210          removeKill(it->valno, End);
211        return it;
212      }
213    } else {
214      // Check to make sure that we are not overlapping two live ranges with
215      // different valno's.
216      assert(it->start >= End &&
217             "Cannot overlap two LiveRanges with differing ValID's");
218    }
219
220  // Otherwise, this is just a new range that doesn't interact with anything.
221  // Insert it.
222  return ranges.insert(it, LR);
223}
224
225
226/// removeRange - Remove the specified range from this interval.  Note that
227/// the range must already be in this interval in its entirety.
228void LiveInterval::removeRange(unsigned Start, unsigned End) {
229  // Find the LiveRange containing this span.
230  Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
231  assert(I != ranges.begin() && "Range is not in interval!");
232  --I;
233  assert(I->contains(Start) && I->contains(End-1) &&
234         "Range is not entirely in interval!");
235
236  // If the span we are removing is at the start of the LiveRange, adjust it.
237  if (I->start == Start) {
238    if (I->end == End) {
239      removeKills(I->valno, Start, End);
240      ranges.erase(I);  // Removed the whole LiveRange.
241    } else
242      I->start = End;
243    return;
244  }
245
246  // Otherwise if the span we are removing is at the end of the LiveRange,
247  // adjust the other way.
248  if (I->end == End) {
249    removeKills(I->valno, Start, End);
250    I->end = Start;
251    return;
252  }
253
254  // Otherwise, we are splitting the LiveRange into two pieces.
255  unsigned OldEnd = I->end;
256  I->end = Start;   // Trim the old interval.
257
258  // Insert the new one.
259  ranges.insert(next(I), LiveRange(End, OldEnd, I->valno));
260}
261
262/// getLiveRangeContaining - Return the live range that contains the
263/// specified index, or null if there is none.
264LiveInterval::const_iterator
265LiveInterval::FindLiveRangeContaining(unsigned Idx) const {
266  const_iterator It = std::upper_bound(begin(), end(), Idx);
267  if (It != ranges.begin()) {
268    --It;
269    if (It->contains(Idx))
270      return It;
271  }
272
273  return end();
274}
275
276LiveInterval::iterator
277LiveInterval::FindLiveRangeContaining(unsigned Idx) {
278  iterator It = std::upper_bound(begin(), end(), Idx);
279  if (It != begin()) {
280    --It;
281    if (It->contains(Idx))
282      return It;
283  }
284
285  return end();
286}
287
288/// join - Join two live intervals (this, and other) together.  This applies
289/// mappings to the value numbers in the LHS/RHS intervals as specified.  If
290/// the intervals are not joinable, this aborts.
291void LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments,
292                        const int *RHSValNoAssignments,
293                        SmallVector<VNInfo*, 16> &NewVNInfo) {
294  // Determine if any of our live range values are mapped.  This is uncommon, so
295  // we want to avoid the interval scan if not.
296  bool MustMapCurValNos = false;
297  unsigned NumVals = getNumValNums();
298  unsigned NumNewVals = NewVNInfo.size();
299  for (unsigned i = 0; i != NumVals; ++i) {
300    unsigned LHSValID = LHSValNoAssignments[i];
301    if (i != LHSValID ||
302        (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i)))
303      MustMapCurValNos = true;
304  }
305
306  // If we have to apply a mapping to our base interval assignment, rewrite it
307  // now.
308  if (MustMapCurValNos) {
309    // Map the first live range.
310    iterator OutIt = begin();
311    OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
312    ++OutIt;
313    for (iterator I = OutIt, E = end(); I != E; ++I) {
314      OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]];
315
316      // If this live range has the same value # as its immediate predecessor,
317      // and if they are neighbors, remove one LiveRange.  This happens when we
318      // have [0,3:0)[4,7:1) and map 0/1 onto the same value #.
319      if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) {
320        (OutIt-1)->end = OutIt->end;
321      } else {
322        if (I != OutIt) {
323          OutIt->start = I->start;
324          OutIt->end = I->end;
325        }
326
327        // Didn't merge, on to the next one.
328        ++OutIt;
329      }
330    }
331
332    // If we merge some live ranges, chop off the end.
333    ranges.erase(OutIt, end());
334  }
335
336  // Remember assignements because val# ids are changing.
337  SmallVector<unsigned, 16> OtherAssignments;
338  for (iterator I = Other.begin(), E = Other.end(); I != E; ++I)
339    OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]);
340
341  // Update val# info. Renumber them and make sure they all belong to this
342  // LiveInterval now. Also remove dead val#'s.
343  unsigned NumValNos = 0;
344  for (unsigned i = 0; i < NumNewVals; ++i) {
345    VNInfo *VNI = NewVNInfo[i];
346    if (VNI) {
347      if (i >= NumVals)
348        valnos.push_back(VNI);
349      else
350        valnos[NumValNos] = VNI;
351      VNI->id = NumValNos++;  // Renumber val#.
352    }
353  }
354  if (NumNewVals < NumVals)
355    valnos.resize(NumNewVals);  // shrinkify
356
357  // Okay, now insert the RHS live ranges into the LHS.
358  iterator InsertPos = begin();
359  unsigned RangeNo = 0;
360  for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
361    // Map the valno in the other live range to the current live range.
362    I->valno = NewVNInfo[OtherAssignments[RangeNo]];
363    assert(I->valno && "Adding a dead range?");
364    InsertPos = addRangeFrom(*I, InsertPos);
365  }
366
367  weight += Other.weight;
368  if (Other.preference && !preference)
369    preference = Other.preference;
370}
371
372/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
373/// interval as the specified value number.  The LiveRanges in RHS are
374/// allowed to overlap with LiveRanges in the current interval, but only if
375/// the overlapping LiveRanges have the specified value number.
376void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
377                                        VNInfo *LHSValNo) {
378  // TODO: Make this more efficient.
379  iterator InsertPos = begin();
380  for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
381    // Map the valno in the other live range to the current live range.
382    LiveRange Tmp = *I;
383    Tmp.valno = LHSValNo;
384    InsertPos = addRangeFrom(Tmp, InsertPos);
385  }
386}
387
388
389/// MergeValueInAsValue - Merge all of the live ranges of a specific val#
390/// in RHS into this live interval as the specified value number.
391/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
392/// current interval, it will replace the value numbers of the overlaped
393/// live ranges with the specified value number.
394void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
395                                     const VNInfo *RHSValNo, VNInfo *LHSValNo) {
396  SmallVector<VNInfo*, 4> ReplacedValNos;
397  iterator IP = begin();
398  for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
399    if (I->valno != RHSValNo)
400      continue;
401    unsigned Start = I->start, End = I->end;
402    IP = std::upper_bound(IP, end(), Start);
403    // If the start of this range overlaps with an existing liverange, trim it.
404    if (IP != begin() && IP[-1].end > Start) {
405      if (IP->valno != LHSValNo) {
406        ReplacedValNos.push_back(IP->valno);
407        IP->valno = LHSValNo; // Update val#.
408      }
409      Start = IP[-1].end;
410      // Trimmed away the whole range?
411      if (Start >= End) continue;
412    }
413    // If the end of this range overlaps with an existing liverange, trim it.
414    if (IP != end() && End > IP->start) {
415      if (IP->valno != LHSValNo) {
416        ReplacedValNos.push_back(IP->valno);
417        IP->valno = LHSValNo;  // Update val#.
418      }
419      End = IP->start;
420      // If this trimmed away the whole range, ignore it.
421      if (Start == End) continue;
422    }
423
424    // Map the valno in the other live range to the current live range.
425    IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP);
426  }
427
428
429  SmallSet<VNInfo*, 4> Seen;
430  for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) {
431    VNInfo *V1 = ReplacedValNos[i];
432    if (Seen.insert(V1)) {
433      bool isDead = true;
434      for (const_iterator I = begin(), E = end(); I != E; ++I)
435        if (I->valno == V1) {
436          isDead = false;
437          break;
438        }
439      if (isDead) {
440        // Now that V1 is dead, remove it.  If it is the largest value number,
441        // just nuke it (and any other deleted values neighboring it), otherwise
442        // mark it as ~1U so it can be nuked later.
443        if (V1->id == getNumValNums()-1) {
444          do {
445            VNInfo *VNI = valnos.back();
446            valnos.pop_back();
447            VNI->~VNInfo();
448          } while (valnos.back()->def == ~1U);
449        } else {
450          V1->def = ~1U;
451        }
452      }
453    }
454  }
455}
456
457
458/// MergeInClobberRanges - For any live ranges that are not defined in the
459/// current interval, but are defined in the Clobbers interval, mark them
460/// used with an unknown definition value.
461void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
462                                        BumpPtrAllocator &VNInfoAllocator) {
463  if (Clobbers.begin() == Clobbers.end()) return;
464
465  // Find a value # to use for the clobber ranges.  If there is already a value#
466  // for unknown values, use it.
467  // FIXME: Use a single sentinal number for these!
468  VNInfo *ClobberValNo = getNextValue(~0U, 0, VNInfoAllocator);
469
470  iterator IP = begin();
471  for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) {
472    unsigned Start = I->start, End = I->end;
473    IP = std::upper_bound(IP, end(), Start);
474
475    // If the start of this range overlaps with an existing liverange, trim it.
476    if (IP != begin() && IP[-1].end > Start) {
477      Start = IP[-1].end;
478      // Trimmed away the whole range?
479      if (Start >= End) continue;
480    }
481    // If the end of this range overlaps with an existing liverange, trim it.
482    if (IP != end() && End > IP->start) {
483      End = IP->start;
484      // If this trimmed away the whole range, ignore it.
485      if (Start == End) continue;
486    }
487
488    // Insert the clobber interval.
489    IP = addRangeFrom(LiveRange(Start, End, ClobberValNo), IP);
490  }
491}
492
493/// MergeValueNumberInto - This method is called when two value nubmers
494/// are found to be equivalent.  This eliminates V1, replacing all
495/// LiveRanges with the V1 value number with the V2 value number.  This can
496/// cause merging of V1/V2 values numbers and compaction of the value space.
497void LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
498  assert(V1 != V2 && "Identical value#'s are always equivalent!");
499
500  // This code actually merges the (numerically) larger value number into the
501  // smaller value number, which is likely to allow us to compactify the value
502  // space.  The only thing we have to be careful of is to preserve the
503  // instruction that defines the result value.
504
505  // Make sure V2 is smaller than V1.
506  if (V1->id < V2->id) {
507    copyValNumInfo(V1, V2);
508    std::swap(V1, V2);
509  }
510
511  // Merge V1 live ranges into V2.
512  for (iterator I = begin(); I != end(); ) {
513    iterator LR = I++;
514    if (LR->valno != V1) continue;  // Not a V1 LiveRange.
515
516    // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
517    // range, extend it.
518    if (LR != begin()) {
519      iterator Prev = LR-1;
520      if (Prev->valno == V2 && Prev->end == LR->start) {
521        Prev->end = LR->end;
522
523        // Erase this live-range.
524        ranges.erase(LR);
525        I = Prev+1;
526        LR = Prev;
527      }
528    }
529
530    // Okay, now we have a V1 or V2 live range that is maximally merged forward.
531    // Ensure that it is a V2 live-range.
532    LR->valno = V2;
533
534    // If we can merge it into later V2 live ranges, do so now.  We ignore any
535    // following V1 live ranges, as they will be merged in subsequent iterations
536    // of the loop.
537    if (I != end()) {
538      if (I->start == LR->end && I->valno == V2) {
539        LR->end = I->end;
540        ranges.erase(I);
541        I = LR+1;
542      }
543    }
544  }
545
546  // Now that V1 is dead, remove it.  If it is the largest value number, just
547  // nuke it (and any other deleted values neighboring it), otherwise mark it as
548  // ~1U so it can be nuked later.
549  if (V1->id == getNumValNums()-1) {
550    do {
551      VNInfo *VNI = valnos.back();
552      valnos.pop_back();
553      VNI->~VNInfo();
554    } while (valnos.back()->def == ~1U);
555  } else {
556    V1->def = ~1U;
557  }
558}
559
560void LiveInterval::Copy(const LiveInterval &RHS,
561                        BumpPtrAllocator &VNInfoAllocator) {
562  ranges.clear();
563  valnos.clear();
564  preference = RHS.preference;
565  weight = RHS.weight;
566  for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
567    const VNInfo *VNI = RHS.getValNumInfo(i);
568    VNInfo *NewVNI = getNextValue(~0U, 0, VNInfoAllocator);
569    copyValNumInfo(NewVNI, VNI);
570  }
571  for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
572    const LiveRange &LR = RHS.ranges[i];
573    addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
574  }
575}
576
577unsigned LiveInterval::getSize() const {
578  unsigned Sum = 0;
579  for (const_iterator I = begin(), E = end(); I != E; ++I)
580    Sum += I->end - I->start;
581  return Sum;
582}
583
584std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
585  return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")";
586}
587
588void LiveRange::dump() const {
589  cerr << *this << "\n";
590}
591
592void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
593  if (MRI && MRegisterInfo::isPhysicalRegister(reg))
594    OS << MRI->getName(reg);
595  else
596    OS << "%reg" << reg;
597
598  OS << ',' << weight;
599
600  if (empty())
601    OS << "EMPTY";
602  else {
603    OS << " = ";
604    for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
605           E = ranges.end(); I != E; ++I)
606    OS << *I;
607  }
608
609  // Print value number info.
610  if (getNumValNums()) {
611    OS << "  ";
612    unsigned vnum = 0;
613    for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
614         ++i, ++vnum) {
615      const VNInfo *vni = *i;
616      if (vnum) OS << " ";
617      OS << vnum << "@";
618      if (vni->def == ~1U) {
619        OS << "x";
620      } else {
621        if (vni->def == ~0U)
622          OS << "?";
623        else
624          OS << vni->def;
625        unsigned ee = vni->kills.size();
626        if (ee) {
627          OS << "-(";
628          for (unsigned j = 0; j != ee; ++j) {
629            OS << vni->kills[j];
630            if (j != ee-1)
631              OS << " ";
632          }
633          if (vni->hasPHIKill)
634            OS << " phi";
635          OS << ")";
636        }
637      }
638    }
639  }
640}
641
642void LiveInterval::dump() const {
643  cerr << *this << "\n";
644}
645
646
647void LiveRange::print(std::ostream &os) const {
648  os << *this;
649}
650