Fix a bug in the range remover
[oota-llvm.git] / lib / CodeGen / LiveInterval.cpp
index 25081e1f890ce63c1ad8cd19e1e1be6a84ebbe98..e5331530807c3e4983efcd50b78673461e8b6865 100644 (file)
@@ -20,7 +20,8 @@
 
 #include "LiveInterval.h"
 #include "Support/STLExtras.h"
-#include <ostream>
+#include <iostream>
+#include <map>
 using namespace llvm;
 
 // An example for liveAt():
@@ -74,8 +75,8 @@ bool LiveInterval::overlaps(const LiveInterval& other) const {
       return true;
 
     if (i->start > j->start) {
-      swap(i, j);
-      swap(ie, je);
+      std::swap(i, j);
+      std::swap(ie, je);
     }
     assert(i->start < j->start);
 
@@ -87,56 +88,216 @@ bool LiveInterval::overlaps(const LiveInterval& other) const {
   return false;
 }
 
-void LiveInterval::addRange(LiveRange LR) {
-  Ranges::iterator it =
-    ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR.start), LR);
+/// joinable - Two intervals are joinable if the either don't overlap at all
+/// or if the destination of the copy is a single assignment value, and it
+/// only overlaps with one value in the source interval.
+bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const {
+  return overlaps(other);
+}
+
+
+/// extendIntervalEndTo - This method is used when we want to extend the range
+/// specified by I to end at the specified endpoint.  To do this, we should
+/// merge and eliminate all ranges that this will overlap with.  The iterator is
+/// not invalidated.
+void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
+  assert(I != ranges.end() && "Not a valid interval!");
+  unsigned ValId = I->ValId;
+
+  // Search for the first interval that we can't merge with.
+  Ranges::iterator MergeTo = next(I);
+  for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
+    assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
+  }
+
+  // If NewEnd was in the middle of an interval, make sure to get its endpoint.
+  I->end = std::max(NewEnd, prior(MergeTo)->end);
 
-  mergeRangesBackward(mergeRangesForward(it));
+  // Erase any dead ranges
+  ranges.erase(next(I), MergeTo);
 }
 
-void LiveInterval::join(const LiveInterval& other) {
-  Ranges::iterator cur = ranges.begin();
-  isDefinedOnce &= other.isDefinedOnce;
 
-  for (Ranges::const_iterator i = other.ranges.begin(),
-         e = other.ranges.end(); i != e; ++i) {
-    cur = ranges.insert(std::upper_bound(cur, ranges.end(), i->start), *i);
-    cur = mergeRangesBackward(mergeRangesForward(cur));
+/// extendIntervalStartTo - This method is used when we want to extend the range
+/// specified by I to start at the specified endpoint.  To do this, we should
+/// merge and eliminate all ranges that this will overlap with.
+LiveInterval::Ranges::iterator 
+LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
+  assert(I != ranges.end() && "Not a valid interval!");
+  unsigned ValId = I->ValId;
+
+  // Search for the first interval that we can't merge with.
+  Ranges::iterator MergeTo = I;
+  do {
+    if (MergeTo == ranges.begin()) {
+      I->start = NewStart;
+      ranges.erase(MergeTo, I);
+      return I;
+    }
+    assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
+    --MergeTo;
+  } while (NewStart <= MergeTo->start);
+
+  // If we start in the middle of another interval, just delete a range and
+  // extend that interval.
+  if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) {
+    MergeTo->end = I->end;
+  } else {
+    // Otherwise, extend the interval right after.
+    ++MergeTo;
+    MergeTo->start = NewStart;
+    MergeTo->end = I->end;
   }
-  weight += other.weight;
+
+  ranges.erase(next(MergeTo), next(I));
+  return MergeTo;
 }
 
 LiveInterval::Ranges::iterator
-LiveInterval::mergeRangesForward(Ranges::iterator it) {
-  Ranges::iterator n;
-  while ((n = next(it)) != ranges.end()) {
-    if (n->start > it->end)
-      break;
-    it->end = std::max(it->end, n->end);
-    n = ranges.erase(n);
+LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) {
+  unsigned Start = LR.start, End = LR.end;
+  Ranges::iterator it = std::upper_bound(From, ranges.end(), Start);
+
+  // If the inserted interval starts in the middle or right at the end of
+  // another interval, just extend that interval to contain the range of LR.
+  if (it != ranges.begin()) {
+    Ranges::iterator B = prior(it);
+    if (LR.ValId == B->ValId) {
+      if (B->start <= Start && B->end >= Start) {
+        extendIntervalEndTo(B, End);
+        return B;
+      }
+    } else {
+      // Check to make sure that we are not overlapping two live ranges with
+      // different ValId's.
+      assert(B->end <= Start &&
+             "Cannot overlap two LiveRanges with differing ValID's");
+    }
   }
-  return it;
+
+  // Otherwise, if this range ends in the middle of, or right next to, another
+  // interval, merge it into that interval.
+  if (it != ranges.end())
+    if (LR.ValId == it->ValId) {
+      if (it->start <= End) {
+        it = extendIntervalStartTo(it, Start);
+
+        // If LR is a complete superset of an interval, we may need to grow its
+        // endpoint as well.
+        if (End > it->end)
+          extendIntervalEndTo(it, End);
+        return it;
+      }
+    } else {
+      // Check to make sure that we are not overlapping two live ranges with
+      // different ValId's.
+      assert(it->start >= End &&
+             "Cannot overlap two LiveRanges with differing ValID's");
+    }
+
+  // Otherwise, this is just a new range that doesn't interact with anything.
+  // Insert it.
+  return ranges.insert(it, LR);
 }
 
-LiveInterval::Ranges::iterator
-LiveInterval::mergeRangesBackward(Ranges::iterator it) {
-  while (it != ranges.begin()) {
-    Ranges::iterator p = prior(it);
-    if (it->start > p->end)
-      break;
-
-    it->start = std::min(it->start, p->start);
-    it->end = std::max(it->end, p->end);
-    it = ranges.erase(p);
+
+/// removeRange - Remove the specified range from this interval.  Note that
+/// the range must already be in this interval in its entirety.
+void LiveInterval::removeRange(unsigned Start, unsigned End) {
+  // Find the LiveRange containing this span.
+  Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
+  assert(I != ranges.begin() && "Range is not in interval!");
+  --I;
+  assert(I->contains(Start) && I->contains(End-1) &&
+         "Range is not entirely in interval!");
+
+  // If the span we are removing is at the start of the LiveRange, adjust it.
+  if (I->start == Start) {
+    if (I->end == End)
+      ranges.erase(I);  // Removed the whole LiveRange.
+    else
+      I->start = End;
+    return;
+  }
+
+  // Otherwise if the span we are removing is at the end of the LiveRange,
+  // adjust the other way.
+  if (I->end == End) {
+    I->end = Start;
+    return;
   }
 
-  return it;
+  // Otherwise, we are splitting the LiveRange into two pieces.
+  unsigned OldEnd = I->end;
+  I->end = Start;   // Trim the old interval.
+
+  // Insert the new one.
+  ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId));
+}
+
+/// getLiveRangeContaining - Return the live range that contains the
+/// specified index, or null if there is none.
+LiveRange *LiveInterval::getLiveRangeContaining(unsigned Idx) {
+  Ranges::iterator It = std::upper_bound(ranges.begin(), ranges.end(), Idx);
+  if (It != ranges.begin()) {
+    LiveRange &LR = *prior(It);
+    if (LR.contains(Idx))
+      return &LR;
+  }
+
+  return 0;
+}
+
+
+
+/// join - Join two live intervals (this, and other) together.  This operation
+/// is the result of a copy instruction in the source program, that occurs at
+/// index 'CopyIdx' that copies from 'Other' to 'this'.
+void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) {
+  LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-1);
+  LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
+  assert(SourceLR && DestLR && "Not joining due to a copy?");
+  unsigned MergedSrcValIdx = SourceLR->ValId;
+  unsigned MergedDstValIdx = DestLR->ValId;
+
+  // Try to do the least amount of work possible.  In particular, if there are
+  // more liverange chunks in the other set than there are in the 'this' set,
+  // swap sets to merge the fewest chunks in possible.
+  if (Other.ranges.size() > ranges.size()) {
+    std::swap(MergedSrcValIdx, MergedDstValIdx);
+    std::swap(ranges, Other.ranges);
+    std::swap(NumValues, Other.NumValues);
+  }
+
+  // Join the ranges of other into the ranges of this interval.
+  Ranges::iterator InsertPos = ranges.begin();
+  std::map<unsigned, unsigned> Dst2SrcIdxMap;
+  for (Ranges::iterator I = Other.ranges.begin(),
+         E = Other.ranges.end(); I != E; ++I) {
+    // Map the ValId in the other live range to the current live range.
+    if (I->ValId == MergedSrcValIdx)
+      I->ValId = MergedDstValIdx;
+    else {
+      unsigned &NV = Dst2SrcIdxMap[I->ValId];
+      if (NV == 0) NV = getNextValue();
+      I->ValId = NV;
+    }
+
+    InsertPos = addRangeFrom(*I, InsertPos);
+  }
+
+  weight += Other.weight;
 }
 
 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
-  return os << "[" << LR.start << "," << LR.end << ")";
+  return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")";
 }
 
+void LiveRange::dump() const {
+  std::cerr << *this << "\n";
+}
+
+
 std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
   os << "%reg" << li.reg << ',' << li.weight;
   if (li.empty())
@@ -148,3 +309,7 @@ std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
     os << *i;
   return os;
 }
+
+void LiveInterval::dump() const {
+  std::cerr << *this << "\n";
+}