lib/CodeGen/LiveInterval.cpp

   1 //===-- LiveInterval.cpp - Live Interval Representation -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 "LiveInterval.h"
  22 #include "Support/STLExtras.h"
  23 #include <ostream>
  24 using namespace llvm;
  25
  26 // An example for liveAt():
  27 //
  28 // this = [1,4), liveAt(0) will return false. The instruction defining this
  29 // spans slots [0,3]. The interval belongs to an spilled definition of the
  30 // variable it represents. This is because slot 1 is used (def slot) and spans
  31 // up to slot 3 (store slot).
  32 //
  33 bool LiveInterval::liveAt(unsigned I) const {
  34   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
  35
  36   if (r == ranges.begin())
  37     return false;
  38
  39   --r;
  40   return r->contains(I);
  41 }
  42
  43 // An example for overlaps():
  44 //
  45 // 0: A = ...
  46 // 4: B = ...
  47 // 8: C = A + B ;; last use of A
  48 //
  49 // The live intervals should look like:
  50 //
  51 // A = [3, 11)
  52 // B = [7, x)
  53 // C = [11, y)
  54 //
  55 // A->overlaps(C) should return false since we want to be able to join
  56 // A and C.
  57 bool LiveInterval::overlaps(const LiveInterval& other) const {
  58   Ranges::const_iterator i = ranges.begin();
  59   Ranges::const_iterator ie = ranges.end();
  60   Ranges::const_iterator j = other.ranges.begin();
  61   Ranges::const_iterator je = other.ranges.end();
  62   if (i->start < j->start) {
  63     i = std::upper_bound(i, ie, j->start);
  64     if (i != ranges.begin()) --i;
  65   } else if (j->start < i->start) {
  66     j = std::upper_bound(j, je, i->start);
  67     if (j != other.ranges.begin()) --j;
  68   } else {
  69     return true;
  70   }
  71
  72   while (i != ie && j != je) {
  73     if (i->start == j->start)
  74       return true;
  75
  76     if (i->start > j->start) {
  77       swap(i, j);
  78       swap(ie, je);
  79     }
  80     assert(i->start < j->start);
  81
  82     if (i->end > j->start)
  83       return true;
  84     ++i;
  85   }
  86
  87   return false;
  88 }
  89
  90 /// extendIntervalEndTo - This method is used when we want to extend the range
  91 /// specified by I to end at the specified endpoint.  To do this, we should
  92 /// merge and eliminate all ranges that this will overlap with.  The iterator is
  93 /// not invalidated.
  94 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
  95   assert(I != ranges.end() && "Not a valid interval!");
  96
  97   // Search for the first interval that we can't merge with.
  98   Ranges::iterator MergeTo = next(I);
  99   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo)
 100     /*empty*/;
 101
 102   // If NewEnd was in the middle of an interval, make sure to get its endpoint.
 103   I->end = std::max(NewEnd, prior(MergeTo)->end);
 104
 105   // Erase any dead ranges
 106   ranges.erase(next(I), MergeTo);
 107 }
 108
 109
 110 /// extendIntervalStartTo - This method is used when we want to extend the range
 111 /// specified by I to start at the specified endpoint.  To do this, we should
 112 /// merge and eliminate all ranges that this will overlap with.
 113 LiveInterval::Ranges::iterator
 114 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
 115   assert(I != ranges.end() && "Not a valid interval!");
 116
 117   // Search for the first interval that we can't merge with.
 118   Ranges::iterator MergeTo = I;
 119   do {
 120     if (MergeTo == ranges.begin()) {
 121       I->start = NewStart;
 122       return I;
 123     }
 124     --MergeTo;
 125   } while (NewStart <= MergeTo->start);
 126
 127   // If we start in the middle of another interval, just delete a range and
 128   // extend that interval.
 129   if (MergeTo->end >= NewStart) {
 130     MergeTo->end = I->end;
 131   } else {
 132     // Otherwise, extend the interval right after.
 133     ++MergeTo;
 134     MergeTo->start = NewStart;
 135     MergeTo->end = I->end;
 136   }
 137
 138   ranges.erase(next(MergeTo), next(I));
 139   return MergeTo;
 140 }
 141
 142 LiveInterval::Ranges::iterator
 143 LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) {
 144   unsigned Start = LR.start, End = LR.end;
 145   Ranges::iterator it = std::upper_bound(From, ranges.end(), Start);
 146
 147   // If the inserted interval starts in the middle or right at the end of
 148   // another interval, just extend that interval to contain the range of LR.
 149   if (it != ranges.begin()) {
 150     Ranges::iterator B = prior(it);
 151     if (B->start <= Start && B->end >= Start) {
 152       extendIntervalEndTo(B, End);
 153       return B;
 154     }
 155   }
 156
 157   // Otherwise, if this range ends in the middle of, or right next to, another
 158   // interval, merge it into that interval.
 159   if (it != ranges.end() && it->start <= End)
 160     return extendIntervalStartTo(it, Start);
 161
 162   // Otherwise, this is just a new range that doesn't interact with anything.
 163   // Insert it.
 164   return ranges.insert(it, LR);
 165 }
 166
 167 void LiveInterval::join(const LiveInterval& other) {
 168   isDefinedOnce &= other.isDefinedOnce;
 169
 170   // Join the ranges of other into the ranges of this interval.
 171   Ranges::iterator cur = ranges.begin();
 172   for (Ranges::const_iterator i = other.ranges.begin(),
 173          e = other.ranges.end(); i != e; ++i)
 174     cur = addRangeFrom(*i, cur);
 175
 176   weight += other.weight;
 177 }
 178
 179 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
 180   return os << "[" << LR.start << "," << LR.end << ")";
 181 }
 182
 183 std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
 184   os << "%reg" << li.reg << ',' << li.weight;
 185   if (li.empty())
 186     return os << "EMPTY";
 187
 188   os << " = ";
 189   for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(),
 190          e = li.ranges.end(); i != e; ++i)
 191     os << *i;
 192   return os;
 193 }