Remove trailing whitespace
[oota-llvm.git] / lib / CodeGen / LiveInterval.cpp
index 6bd441f6431b4091fd15ed66f0ac7d1f0ed38fc7..ffa4caab06f13960aa4d0af45ef919cd0db8b41b 100644 (file)
@@ -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,31 +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;
@@ -163,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;
@@ -213,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?)");
     }
   }