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

1 files changed, 13 insertions, 12 deletions

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