ART: Replace expensive calls to Covers in reg alloc

LiveInterval::Covers is implemented as a linear-time search over
liveness ranges and can therefore be rather expensive and should be
avoided unless necessary. This patch replaces calls to Covers when
searching for a sibling with the cheaper IsDefinedAt call.

Change-Id: I93fc73529c15a518335f4cbdc3a0def52d9501e5

3 files changed, 24 insertions, 40 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index a02b1dacf7..830f2c26e1 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1538,35 +1538,14 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
     return;
   }
 
-  // Intervals end at the lifetime end of a block. The decrement by one
-  // ensures the `Cover` call will return true.
-  size_t from_position = from->GetLifetimeEnd() - 1;
-  size_t to_position = to->GetLifetimeStart();
-
-  LiveInterval* destination = nullptr;
-  LiveInterval* source = nullptr;
-
-  LiveInterval* current = interval;
-
-  // Check the intervals that cover `from` and `to`.
-  while ((current != nullptr) && (source == nullptr || destination == nullptr)) {
-    if (current->Covers(from_position)) {
-      DCHECK(source == nullptr);
-      source = current;
-    }
-    if (current->Covers(to_position)) {
-      DCHECK(destination == nullptr);
-      destination = current;
-    }
-
-    current = current->GetNextSibling();
-  }
+  // Find the intervals that cover `from` and `to`.
+  LiveInterval* destination = interval->GetSiblingAt(to->GetLifetimeStart());
+  LiveInterval* source = interval->GetSiblingAt(from->GetLifetimeEnd() - 1);
 
   if (destination == source) {
     // Interval was not split.
     return;
   }
-
   DCHECK(destination != nullptr && source != nullptr);
 
   if (!destination->HasRegister()) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 302df2a1d2..ea0e7c3712 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -402,11 +402,11 @@ int LiveInterval::FindHintAtDefinition() const {
     for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) {
       HInstruction* input = defined_by_->InputAt(i);
       size_t end = predecessors.Get(i)->GetLifetimeEnd();
-      const LiveInterval& input_interval = input->GetLiveInterval()->GetIntervalAt(end - 1);
-      if (input_interval.GetEnd() == end) {
+      LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1);
+      if (input_interval->GetEnd() == end) {
         // If the input dies at the end of the predecessor, we know its register can
         // be reused.
-        Location input_location = input_interval.ToLocation();
+        Location input_location = input_interval->ToLocation();
         if (input_location.IsRegisterKind()) {
           DCHECK(SameRegisterKind(input_location));
           return RegisterOrLowRegister(input_location);
@@ -418,12 +418,12 @@ int LiveInterval::FindHintAtDefinition() const {
     Location out = locations->Out();
     if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) {
       // Try to use the same register as the first input.
-      const LiveInterval& input_interval =
-          GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetIntervalAt(GetStart() - 1);
-      if (input_interval.GetEnd() == GetStart()) {
+      LiveInterval* input_interval =
+          GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetSiblingAt(GetStart() - 1);
+      if (input_interval->GetEnd() == GetStart()) {
         // If the input dies at the start of this instruction, we know its register can
         // be reused.
-        Location location = input_interval.ToLocation();
+        Location location = input_interval->ToLocation();
         if (location.IsRegisterKind()) {
           DCHECK(SameRegisterKind(location));
           return RegisterOrLowRegister(location);
@@ -487,16 +487,17 @@ Location LiveInterval::ToLocation() const {
 }
 
 Location LiveInterval::GetLocationAt(size_t position) {
-  return GetIntervalAt(position).ToLocation();
+  LiveInterval* sibling = GetSiblingAt(position);
+  DCHECK(sibling != nullptr);
+  return sibling->ToLocation();
 }
 
-const LiveInterval& LiveInterval::GetIntervalAt(size_t position) {
+LiveInterval* LiveInterval::GetSiblingAt(size_t position) {
   LiveInterval* current = this;
-  while (!current->Covers(position)) {
+  while (current != nullptr && !current->IsDefinedAt(position)) {
     current = current->GetNextSibling();
-    DCHECK(current != nullptr);
   }
-  return *current;
+  return current;
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 98f98a29d1..beb4907bc1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -372,7 +372,11 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   bool HasRegister() const { return register_ != kNoRegister; }
 
   bool IsDeadAt(size_t position) const {
-    return last_range_->GetEnd() <= position;
+    return GetEnd() <= position;
+  }
+
+  bool IsDefinedAt(size_t position) const {
+    return GetStart() <= position && !IsDeadAt(position);
   }
 
   bool Covers(size_t position) {
@@ -513,7 +517,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     DCHECK(!is_fixed_);
     DCHECK_GT(position, GetStart());
 
-    if (last_range_->GetEnd() <= position) {
+    if (GetEnd() <= position) {
       // This range dies before `position`, no need to split.
       return nullptr;
     }
@@ -643,8 +647,8 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   // Returns the location of the interval following its siblings at `position`.
   Location GetLocationAt(size_t position);
 
-  // Finds the interval that covers `position`.
-  const LiveInterval& GetIntervalAt(size_t position);
+  // Finds the sibling that is defined at `position`.
+  LiveInterval* GetSiblingAt(size_t position);
 
   // Returns whether `other` and `this` share the same kind of register.
   bool SameRegisterKind(Location other) const;