Add ability to give hints to the overlaps routines.
llvm-svn: 17934
diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index 8306116..3c7e8dd763 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -42,6 +42,9 @@
return r->contains(I);
}
+// overlaps - Return true if the intersection of the two live intervals is
+// not empty.
+//
// An example for overlaps():
//
// 0: A = ...
@@ -56,11 +59,16 @@
//
// 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()) &&
+ "Bogus start position hint!");
if (i->start < j->start) {
i = std::upper_bound(i, ie, j->start);
diff --git a/llvm/lib/CodeGen/LiveInterval.h b/llvm/lib/CodeGen/LiveInterval.h
index 05ebcc1..55de7e3 100644
--- a/llvm/lib/CodeGen/LiveInterval.h
+++ b/llvm/lib/CodeGen/LiveInterval.h
@@ -76,11 +76,14 @@
: reg(Reg), weight(Weight), NumValues(0) {
}
-
typedef Ranges::iterator iterator;
iterator begin() { return ranges.begin(); }
iterator end() { return ranges.end(); }
+ typedef Ranges::const_iterator const_iterator;
+ const_iterator begin() const { return ranges.begin(); }
+ const_iterator end() const { return ranges.end(); }
+
/// advanceTo - Advance the specified iterator to point to the LiveRange
/// containing the specified position, or end() if the position is past the
@@ -139,7 +142,16 @@
bool joinable(const LiveInterval& other, unsigned CopyIdx) const;
- bool overlaps(const LiveInterval& other) const;
+ /// overlaps - Return true if the intersection of the two live intervals is
+ /// not empty.
+ bool overlaps(const LiveInterval& other) const {
+ return overlapsFrom(other, other.begin());
+ }
+
+ /// overlapsFrom - Return true if the intersection of the two live intervals
+ /// is not empty. The specified iterator is a hint that we can begin
+ /// scanning the Other interval starting at I.
+ bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
/// addRange - Add the specified LiveRange to this interval, merging
/// intervals as appropriate. This returns an iterator to the inserted live