Subzero: Optimize live range overlaps() computation through trimming.

src/IceOperand.cpp

Index: src/IceOperand.cpp
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index c366dd993558f604ff6ddf7b441b5350e7c5a36c..ef163d0ee173b8f05b98f6de117aa12c11ca3a6e 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -105,9 +105,11 @@ bool LiveRange::endsBefore(const LiveRange &Other) const {
 }
 
 // Returns true if there is any overlap between the two live ranges.
-bool LiveRange::overlaps(const LiveRange &Other) const {
+bool LiveRange::overlaps(const LiveRange &Other, bool UseTrimmed) const {
   // Do a two-finger walk through the two sorted lists of segments.
-  RangeType::const_iterator I1 = Range.begin(), I2 = Other.Range.begin();
+  RangeType::const_iterator I1 = (UseTrimmed ? TrimmedBegin : Range.begin()),
+                            I2 = (UseTrimmed ? Other.TrimmedBegin
+                                             : Other.Range.begin());
   RangeType::const_iterator E1 = Range.end(), E2 = Other.Range.end();
   while (I1 != E1 && I2 != E2) {
     if (I1->second <= I2->first) {
@@ -158,6 +160,11 @@ bool LiveRange::containsValue(InstNumberT Value) const {
   return false;
 }
 
+void LiveRange::trim(InstNumberT Lower) {
+  while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower)

[jvoung (off chromium), 2014/10/05 20:34:13]

I might be reading this wrong, but it looks like trim() pushes the ranges past
"Lower" w/ testing that while "TrimmedBegin->second <= Lower", keep bumping.

Should trim() only push up till Lower >= TrimmedBegin->first? Intuitively, that
seems like that would bump past ranges that clearly won't overlap, but keeps the
very last range that could still overlap?

[Jim Stichnoth, 2014/10/06 13:38:01]

Are you asking e.g. what would happen if "this" live range is [1:10),[20:30) and
Cur is [10:15) such that Lower=10 in this method?  In this case, it is OK to
advance this->TrimmedBegin to the [20:30) element because [1:10) and [10:15) do
not overlap.

[jvoung (off chromium), 2014/10/06 21:57:26]

Okay, I see I think I was confused by the order of the comparison (Lower on the
left vs right).

+    ++TrimmedBegin;
+}
+
 IceString Variable::getName() const {
   if (!Name.empty())
     return Name;