commit 037fa1d997307fd68c7e6d9c385e30890d65604d
author Jim Stichnoth <stichnot@chromium.org> Tue Oct 07 11:09:33 2014 -0700
committer Jim Stichnoth <stichnot@chromium.org> Tue Oct 07 11:09:33 2014 -0700
tree 52cb7206043c2277ac80d8688d7194a50c06d27c
parent e3f64d0967aa918a151a1d7e9971060c85f4aa1d

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

The main optimization is for the repeated overlaps() calls against the Inactive set, by iteratively trimming away the early sections of the Inactive live ranges that can no longer overlap with Cur.

A more minor optimization doesn't bother checking pure point-valued Inactive ranges for expiring or reactivating.

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/627203002

src/IceOperand.cpp

diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index c631e80..9ecfd31 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -105,10 +105,11 @@
 }
 
 // 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 E1 = Range.end(), E2 = Other.Range.end();
+  auto I1 = (UseTrimmed ? TrimmedBegin : Range.begin()),
+       I2 = (UseTrimmed ? Other.TrimmedBegin : Other.Range.begin());
+  auto E1 = Range.end(), E2 = Other.Range.end();
   while (I1 != E1 && I2 != E2) {
     if (I1->second <= I2->first) {
       ++I1;
@@ -123,16 +124,17 @@
   return false;
 }
 
-bool LiveRange::overlaps(InstNumberT OtherBegin) const {
+bool LiveRange::overlapsInst(InstNumberT OtherBegin, bool UseTrimmed) const {
   if (!IsNonpoints)
     return false;
   bool Result = false;
-  for (const RangeElementType &I : Range) {
-    if (OtherBegin < I.first) {
+  for (auto I = (UseTrimmed ? TrimmedBegin : Range.begin()), E = Range.end();
+       I != E; ++I) {
+    if (OtherBegin < I->first) {
       Result = false;
       break;
     }
-    if (OtherBegin < I.second) {
+    if (OtherBegin < I->second) {
       Result = true;
       break;
     }
@@ -158,6 +160,11 @@
   return false;
 }
 
+void LiveRange::trim(InstNumberT Lower) {
+  while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower)
+    ++TrimmedBegin;
+}
+
 IceString Variable::getName() const {
   if (!Name.empty())
     return Name;
@@ -221,6 +228,9 @@
   // be careful not to omit all uses of the variable if markDef() and
   // markUse() both use this optimization.
   assert(Node);
+  // Verify that instructions are added in increasing order.
+  assert(Definitions.empty() ||
+         Instr->getNumber() >= Definitions.back()->getNumber());
   Definitions.push_back(Instr);
   const bool IsFromDef = true;
   const bool IsImplicit = false;