Remove trailing whitespace

[oota-llvm.git] / lib / CodeGen / LiveInterval.cpp

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 29bee9bd6bf640b4a710a90822652404739497c7..ffa4caab06f13960aa4d0af45ef919cd0db8b41b 100644 (file)
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -19,7 +19,8 @@
 //===----------------------------------------------------------------------===//
 
 #include "LiveInterval.h"
-#include "Support/STLExtras.h"
+#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
 #include <iostream>
 #include <map>
 using namespace llvm;
@@ -33,7 +34,7 @@ using namespace llvm;
 //
 bool LiveInterval::liveAt(unsigned I) const {
   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
-                                              
+
   if (r == ranges.begin())
     return false;
 
@@ -41,6 +42,9 @@ bool LiveInterval::liveAt(unsigned I) const {
   return r->contains(I);
 }
 
+// overlaps - Return true if the intersection of the two live intervals is
+// not empty.
+//
 // An example for overlaps():
 //
 // 0: A = ...
@@ -55,30 +59,38 @@ bool LiveInterval::liveAt(unsigned I) const {
 //
 // A->overlaps(C) should return false since we want to be able to join
 // A and C.
-bool LiveInterval::overlaps(const LiveInterval& other) const {
-  Ranges::const_iterator i = ranges.begin();
-  Ranges::const_iterator ie = ranges.end();
-  Ranges::const_iterator j = other.ranges.begin();
-  Ranges::const_iterator je = other.ranges.end();
+//
+bool LiveInterval::overlapsFrom(const LiveInterval& other,
+                                const_iterator StartPos) const {
+  const_iterator i = begin();
+  const_iterator ie = end();
+  const_iterator j = StartPos;
+  const_iterator je = other.end();
+
+  assert((StartPos->start <= i->start || StartPos == other.begin()) &&
+         StartPos != other.end() && "Bogus start position hint!");
+
   if (i->start < j->start) {
     i = std::upper_bound(i, ie, j->start);
     if (i != ranges.begin()) --i;
   } else if (j->start < i->start) {
-    j = std::upper_bound(j, je, i->start);
-    if (j != other.ranges.begin()) --j;
+    ++StartPos;
+    if (StartPos != other.end() && StartPos->start <= i->start) {
+      assert(StartPos < other.end() && i < end());
+      j = std::upper_bound(j, je, i->start);
+      if (j != other.ranges.begin()) --j;
+    }
   } else {
     return true;
   }
 
-  while (i != ie && j != je) {
-    if (i->start == j->start)
-      return true;
+  if (j == je) return false;
 
+  while (i != ie) {
     if (i->start > j->start) {
       std::swap(i, j);
       std::swap(ie, je);
     }
-    assert(i->start < j->start);
 
     if (i->end > j->start)
       return true;
@@ -92,7 +104,48 @@ bool LiveInterval::overlaps(const LiveInterval& other) const {
 /// 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);
+  const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1);
+  const LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
+  assert(SourceLR && DestLR && "Not joining due to a copy?");
+  unsigned OtherValIdx = SourceLR->ValId;
+  unsigned ThisValIdx = DestLR->ValId;
+
+  Ranges::const_iterator i = ranges.begin();
+  Ranges::const_iterator ie = ranges.end();
+  Ranges::const_iterator j = other.ranges.begin();
+  Ranges::const_iterator je = other.ranges.end();
+
+  if (i->start < j->start) {
+    i = std::upper_bound(i, ie, j->start);
+    if (i != ranges.begin()) --i;
+  } else if (j->start < i->start) {
+    j = std::upper_bound(j, je, i->start);
+    if (j != other.ranges.begin()) --j;
+  }
+
+  while (i != ie && j != je) {
+    if (i->start == j->start) {
+      // If this is not the allowed value merge, we cannot join.
+      if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
+        return false;
+    } else if (i->start < j->start) {
+      if (i->end > j->start) {
+        if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
+          return false;
+      }
+    } else {
+      if (j->end > i->start) {
+        if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
+          return false;
+      }
+    }
+    if (i->end < j->end)
+      ++i;
+    else
+      ++j;
+  }
+
+  return true;
 }
 
 
@@ -121,7 +174,7 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
 /// 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::Ranges::iterator
 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
   assert(I != ranges.end() && "Not a valid interval!");
   unsigned ValId = I->ValId;
@@ -171,7 +224,8 @@ LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) {
       // 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");
+             "Cannot overlap two LiveRanges with differing ValID's"
+             " (did you def the same reg twice in a MachineInstr?)");
     }
   }