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

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Operand class and its target-independent
@@ skipping 87 matching lines @@
 bool LiveRange::endsBefore(const LiveRange &Other) const {
   // Neither range should be empty, but let's be graceful.
   if (Range.empty() || Other.Range.empty())
     return true;
   InstNumberT MyEnd = (*Range.rbegin()).second;
   InstNumberT OtherStart = (*Other.Range.begin()).first;
   return MyEnd <= OtherStart;
 }
 
 // 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) {
       ++I1;
       continue;
     }
     if (I2->second <= I1->first) {
       ++I2;
       continue;
     }
     return true;
   }
   return false;
 }
 
 bool LiveRange::overlaps(InstNumberT OtherBegin) const {

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

Would it help to have this overlaps() check use a trimmed Range too?

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

I think you're right.

There are two instances of overlapsStart() that should directly benefit from
this.

For the calls to overlapsDefs(), which call overlaps(InstNumberT), the best
would be to trim the Defs list (and make sure the list is sorted).

   if (!IsNonpoints)
     return false;
   bool Result = false;
   for (const RangeElementType &I : Range) {
     if (OtherBegin < I.first) {
       Result = false;
       break;
     }
     if (OtherBegin < I.second) {
       Result = true;
@@ skipping 14 matching lines @@
 // number.  This is only used for validating the live range
 // calculation.
 bool LiveRange::containsValue(InstNumberT Value) const {
   for (const RangeElementType &I : Range) {
     if (I.first <= Value && Value <= I.second)
       return true;
   }
   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;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
 
 Variable Variable::asType(Type Ty) {
   // Note: This returns a Variable, even if the "this" object is a
@@ skipping 281 matching lines @@
 
 Ostream &operator<<(Ostream &Str, const RegWeight &W) {
   if (W.getWeight() == RegWeight::Inf)
     Str << "Inf";
   else
     Str << W.getWeight();
   return Str;
 }
 
 } // end of namespace Ice