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 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 I >= r->start && I < r->end;
  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);
  64     if (i != ranges.begin()) --i;
  65   }
  66   else if (j->start < i->start) {
  67     j = std::upper_bound(j, je, *i);
  68     if (j != other.ranges.begin()) --j;
  69   }
  70
  71   while (i != ie && j != je) {
  72     if (i->start == j->start)
  73       return true;
  74
  75     if (i->start > j->start) {
  76       swap(i, j);
  77       swap(ie, je);
  78     }
  79     assert(i->start < j->start);
  80
  81     if (i->end > j->start)
  82       return true;
  83     ++i;
  84   }
  85
  86   return false;
  87 }
  88
  89 void LiveInterval::addRange(LiveRange LR) {
  90   Ranges::iterator it =
  91     ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR), LR);
  92
  93   mergeRangesBackward(mergeRangesForward(it));
  94 }
  95
  96 void LiveInterval::join(const LiveInterval& other) {
  97   Ranges::iterator cur = ranges.begin();
  98   isDefinedOnce &= other.isDefinedOnce;
  99
 100   for (Ranges::const_iterator i = other.ranges.begin(),
 101          e = other.ranges.end(); i != e; ++i) {
 102     cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i);
 103     cur = mergeRangesBackward(mergeRangesForward(cur));
 104   }
 105   weight += other.weight;
 106 }
 107
 108 LiveInterval::Ranges::iterator
 109 LiveInterval::mergeRangesForward(Ranges::iterator it) {
 110   Ranges::iterator n;
 111   while ((n = next(it)) != ranges.end()) {
 112     if (n->start > it->end)
 113       break;
 114     it->end = std::max(it->end, n->end);
 115     n = ranges.erase(n);
 116   }
 117   return it;
 118 }
 119
 120 LiveInterval::Ranges::iterator
 121 LiveInterval::mergeRangesBackward(Ranges::iterator it) {
 122   while (it != ranges.begin()) {
 123     Ranges::iterator p = prior(it);
 124     if (it->start > p->end)
 125       break;
 126
 127     it->start = std::min(it->start, p->start);
 128     it->end = std::max(it->end, p->end);
 129     it = ranges.erase(p);
 130   }
 131
 132   return it;
 133 }
 134
 135 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
 136   return os << "[" << LR.start << "," << LR.end << ")";
 137 }
 138
 139 std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
 140   os << "%reg" << li.reg << ',' << li.weight;
 141   if (li.empty())
 142     return os << "EMPTY";
 143
 144   os << " = ";
 145   for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(),
 146          e = li.ranges.end(); i != e; ++i)
 147     os << *i;
 148   return os;
 149 }