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
  29 // this spans slots [0,3]. The interval belongs to an spilled
  30 // definition of the variable it represents. This is because slot 1 is
  31 // used (def slot) and spans up to slot 3 (store slot).
  32 //
  33 bool LiveInterval::liveAt(unsigned index) const {
  34   LiveRange dummy(index, index+1);
  35   Ranges::const_iterator r = std::upper_bound(ranges.begin(),
  36                                               ranges.end(),
  37                                               dummy);
  38   if (r == ranges.begin())
  39     return false;
  40
  41   --r;
  42   return index >= r->start && index < r->end;
  43 }
  44
  45 // An example for overlaps():
  46 //
  47 // 0: A = ...
  48 // 4: B = ...
  49 // 8: C = A + B ;; last use of A
  50 //
  51 // The live intervals should look like:
  52 //
  53 // A = [3, 11)
  54 // B = [7, x)
  55 // C = [11, y)
  56 //
  57 // A->overlaps(C) should return false since we want to be able to join
  58 // A and C.
  59 bool LiveInterval::overlaps(const LiveInterval& other) const {
  60   Ranges::const_iterator i = ranges.begin();
  61   Ranges::const_iterator ie = ranges.end();
  62   Ranges::const_iterator j = other.ranges.begin();
  63   Ranges::const_iterator je = other.ranges.end();
  64   if (i->start < j->start) {
  65     i = std::upper_bound(i, ie, *j);
  66     if (i != ranges.begin()) --i;
  67   }
  68   else if (j->start < i->start) {
  69     j = std::upper_bound(j, je, *i);
  70     if (j != other.ranges.begin()) --j;
  71   }
  72
  73   while (i != ie && j != je) {
  74     if (i->start == j->start)
  75       return true;
  76
  77     if (i->start > j->start) {
  78       swap(i, j);
  79       swap(ie, je);
  80     }
  81     assert(i->start < j->start);
  82
  83     if (i->end > j->start)
  84       return true;
  85     ++i;
  86   }
  87
  88   return false;
  89 }
  90
  91 void LiveInterval::addRange(LiveRange LR) {
  92   Ranges::iterator it =
  93     ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR), LR);
  94
  95   mergeRangesBackward(mergeRangesForward(it));
  96 }
  97
  98 void LiveInterval::join(const LiveInterval& other) {
  99   Ranges::iterator cur = ranges.begin();
 100   isDefinedOnce &= other.isDefinedOnce;
 101
 102   for (Ranges::const_iterator i = other.ranges.begin(),
 103          e = other.ranges.end(); i != e; ++i) {
 104     cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i);
 105     cur = mergeRangesBackward(mergeRangesForward(cur));
 106   }
 107   weight += other.weight;
 108 }
 109
 110 LiveInterval::Ranges::iterator
 111 LiveInterval::mergeRangesForward(Ranges::iterator it) {
 112   Ranges::iterator n;
 113   while ((n = next(it)) != ranges.end()) {
 114     if (n->start > it->end)
 115       break;
 116     it->end = std::max(it->end, n->end);
 117     n = ranges.erase(n);
 118   }
 119   return it;
 120 }
 121
 122 LiveInterval::Ranges::iterator
 123 LiveInterval::mergeRangesBackward(Ranges::iterator it) {
 124   while (it != ranges.begin()) {
 125     Ranges::iterator p = prior(it);
 126     if (it->start > p->end)
 127       break;
 128
 129     it->start = std::min(it->start, p->start);
 130     it->end = std::max(it->end, p->end);
 131     it = ranges.erase(p);
 132   }
 133
 134   return it;
 135 }
 136
 137 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
 138   return os << "[" << LR.start << "," << LR.end << ")";
 139 }
 140
 141 std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
 142   os << "%reg" << li.reg << ',' << li.weight;
 143   if (li.empty())
 144     return os << "EMPTY";
 145
 146   os << " = ";
 147   for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(),
 148          e = li.ranges.end(); i != e; ++i)
 149     os << *i;
 150   return os;
 151 }