Finally implement Location::kNoOutputOverlap.

The [i, i + 1) interval scheme we chose for representing
lifetime positions is not optimal for doing this optimization.
It however doesn't prevent recognizing a non-split interval
during the TryAllocateFreeReg phase, and try to re-use
its inputs' registers.

Change-Id: I80a2823b0048d3310becfc5f5fb7b1230dfd8201

1 files changed, 97 insertions, 5 deletions

diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b0d3853..0e68a61 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -18,6 +18,7 @@
 #define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
 
 #include "nodes.h"
+#include <iostream>
 
 namespace art {
 
@@ -181,12 +182,21 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
 
   void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
     // Set the use within the instruction.
-    size_t position = instruction->GetLifetimePosition();
-    if (instruction->GetLocations()->InputOverlapsWithOutputOrTemp(input_index, is_environment)) {
-      // If it overlaps, we need to make sure the user will not try to allocate a temp
-      // or its output to the same register.
-      ++position;
+    size_t position = instruction->GetLifetimePosition() + 1;
+    LocationSummary* locations = instruction->GetLocations();
+    if (!is_environment) {
+      if (locations->IsFixedInput(input_index) || locations->OutputUsesSameAs(input_index)) {
+        // For fixed inputs and output same as input, the register allocator
+        // requires to have inputs die at the instruction, so that input moves use the
+        // location of the input just before that instruction (and not potential moves due
+        // to splitting).
+        position = instruction->GetLifetimePosition();
+      }
     }
+
+    DCHECK(position == instruction->GetLifetimePosition()
+           || position == instruction->GetLifetimePosition() + 1);
+
     if ((first_use_ != nullptr)
         && (first_use_->GetUser() == instruction)
         && (first_use_->GetPosition() < position)) {
@@ -301,6 +311,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   LiveInterval* GetParent() const { return parent_; }
 
   LiveRange* GetFirstRange() const { return first_range_; }
+  LiveRange* GetLastRange() const { return last_range_; }
 
   int GetRegister() const { return register_; }
   void SetRegister(int reg) { register_ = reg; }
@@ -403,6 +414,23 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     return FirstRegisterUseAfter(GetStart());
   }
 
+  size_t FirstUseAfter(size_t position) const {
+    if (is_temp_) {
+      return position == GetStart() ? position : kNoLifetime;
+    }
+
+    UsePosition* use = first_use_;
+    size_t end = GetEnd();
+    while (use != nullptr && use->GetPosition() <= end) {
+      size_t use_position = use->GetPosition();
+      if (use_position > position) {
+        return use_position;
+      }
+      use = use->GetNext();
+    }
+    return kNoLifetime;
+  }
+
   UsePosition* GetFirstUse() const {
     return first_use_;
   }
@@ -511,6 +539,13 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   }
 
   LiveInterval* GetNextSibling() const { return next_sibling_; }
+  LiveInterval* GetLastSibling() {
+    LiveInterval* result = this;
+    while (result->next_sibling_ != nullptr) {
+      result = result->next_sibling_;
+    }
+    return result;
+  }
 
   // Returns the first register hint that is at least free before
   // the value contained in `free_until`. If none is found, returns
@@ -541,6 +576,9 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
 
   // Returns whether `other` and `this` share the same kind of register.
   bool SameRegisterKind(Location other) const;
+  bool SameRegisterKind(const LiveInterval& other) const {
+    return IsFloatingPoint() == other.IsFloatingPoint();
+  }
 
   bool HasHighInterval() const {
     return IsLowInterval();
@@ -594,6 +632,60 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     }
   }
 
+  // Returns whether an interval, when it is non-split, is using
+  // the same register of one of its input.
+  bool IsUsingInputRegister() const {
+    if (defined_by_ != nullptr && !IsSplit()) {
+      for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
+        LiveInterval* interval = it.Current()->GetLiveInterval();
+
+        // Find the interval that covers `defined_by`_.
+        while (interval != nullptr && !interval->Covers(defined_by_->GetLifetimePosition())) {
+          interval = interval->GetNextSibling();
+        }
+
+        // Check if both intervals have the same register of the same kind.
+        if (interval != nullptr
+            && interval->SameRegisterKind(*this)
+            && interval->GetRegister() == GetRegister()) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  // Returns whether an interval, when it is non-split, can safely use
+  // the same register of one of its input. Note that this method requires
+  // IsUsingInputRegister() to be true.
+  bool CanUseInputRegister() const {
+    DCHECK(IsUsingInputRegister());
+    if (defined_by_ != nullptr && !IsSplit()) {
+      LocationSummary* locations = defined_by_->GetLocations();
+      if (locations->OutputCanOverlapWithInputs()) {
+        return false;
+      }
+      for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
+        LiveInterval* interval = it.Current()->GetLiveInterval();
+
+        // Find the interval that covers `defined_by`_.
+        while (interval != nullptr && !interval->Covers(defined_by_->GetLifetimePosition())) {
+          interval = interval->GetNextSibling();
+        }
+
+        if (interval != nullptr
+            && interval->SameRegisterKind(*this)
+            && interval->GetRegister() == GetRegister()) {
+          // We found the input that has the same register. Check if it is live after
+          // `defined_by`_.
+          return !interval->Covers(defined_by_->GetLifetimePosition() + 1);
+        }
+      }
+    }
+    LOG(FATAL) << "Unreachable";
+    UNREACHABLE();
+  }
+
  private:
   LiveInterval(ArenaAllocator* allocator,
                Primitive::Type type,