Merge "Register allocator: refine instructions liveness."

3 files changed, 52 insertions, 15 deletions

diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index a2f5bfaace..f358e051ae 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -387,6 +387,16 @@ class LocationSummary : public ArenaObject {
     return &live_registers_;
   }
 
+  bool InputOverlapsWithOutputOrTemp(uint32_t input, bool is_environment) const {
+    if (is_environment) return true;
+    Location location = Out();
+    // TODO: Add more policies.
+    if (input == 0 && location.IsUnallocated() && location.GetPolicy() == Location::kSameAsFirstInput) {
+      return false;
+    }
+    return true;
+  }
+
  private:
   GrowableArray<Location> inputs_;
   GrowableArray<Location> temps_;
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 78f20a1551..4b45f43016 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -205,7 +205,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
   LiveInterval* current = instruction->GetLiveInterval();
   if (current == nullptr) return;
 
-  DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek()));
+  DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek()));
   // Some instructions define their output in fixed register/stack slot. We need
   // to ensure we know these locations before doing register allocation. For a
   // given register, we create an interval that covers these locations. The register
@@ -228,7 +228,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
     // Split before first register use.
     size_t first_register_use = current->FirstRegisterUse();
     if (first_register_use != kNoLifetime) {
-      LiveInterval* split = Split(current, first_register_use - 1);
+      LiveInterval* split = Split(current, first_register_use);
       // Don't add direclty to `unhandled`, it needs to be sorted and the start
       // of this new interval might be after intervals already in the list.
       AddSorted(&unhandled, split);
@@ -236,7 +236,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
       // Nothing to do, we won't allocate a register for this value.
     }
   } else {
-    DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek()));
+    DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek()));
     unhandled.Add(current);
   }
 }
@@ -586,7 +586,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
     // If the first use of that instruction is after the last use of the found
     // register, we split this interval just before its first register use.
     AllocateSpillSlotFor(current);
-    LiveInterval* split = Split(current, first_register_use - 1);
+    LiveInterval* split = Split(current, first_register_use);
     AddSorted(unhandled_, split);
     return false;
   } else {
@@ -977,7 +977,11 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
   }
 
   size_t from_position = from->GetLifetimeEnd() - 1;
-  size_t to_position = to->GetLifetimeStart();
+  // When an instructions dies at entry of another, and the latter is the beginning
+  // of a block, the register allocator ensures the former has a register
+  // at block->GetLifetimeStart() + 1. Since this is at a block boundary, it must
+  // must be handled in this method.
+  size_t to_position = to->GetLifetimeStart() + 1;
 
   LiveInterval* destination = nullptr;
   LiveInterval* source = nullptr;
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index dea6181cb2..3ef24137cc 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -76,7 +76,7 @@ class LiveRange : public ArenaObject {
 
  private:
   size_t start_;
-  const size_t end_;
+  size_t end_;
   LiveRange* next_;
 
   friend class LiveInterval;
@@ -99,13 +99,16 @@ class UsePosition : public ArenaObject {
         is_environment_(is_environment),
         position_(position),
         next_(next) {
-    DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1);
+    DCHECK(user->IsPhi()
+        || (GetPosition() == user->GetLifetimePosition() + 1)
+        || (GetPosition() == user->GetLifetimePosition()));
     DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
   }
 
   size_t GetPosition() const { return position_; }
 
   UsePosition* GetNext() const { return next_; }
+  void SetNext(UsePosition* next) { next_ = next; }
 
   HInstruction* GetUser() const { return user_; }
 
@@ -122,7 +125,7 @@ class UsePosition : public ArenaObject {
   const size_t input_index_;
   const bool is_environment_;
   const size_t position_;
-  UsePosition* const next_;
+  UsePosition* next_;
 
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
@@ -174,11 +177,29 @@ class LiveInterval : public ArenaObject {
 
   void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
     // Set the use within the instruction.
-    // TODO: Use the instruction's location to know whether the instruction can die
-    // at entry, or needs to say alive within the user.
-    size_t position = instruction->GetLifetimePosition() + 1;
+    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 start_block_position = instruction->GetBlock()->GetLifetimeStart();
     size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
+    if ((first_use_ != nullptr)
+        && (first_use_->GetUser() == instruction)
+        && (first_use_->GetPosition() < position)) {
+      // The user uses the instruction multiple times, and one use dies before the other.
+      // We update the use list so that the latter is first.
+      DCHECK(first_use_->GetPosition() + 1 == position);
+      UsePosition* new_use = new (allocator_) UsePosition(
+          instruction, input_index, is_environment, position, first_use_->GetNext());
+      first_use_->SetNext(new_use);
+      if (first_range_->GetEnd() == first_use_->GetPosition()) {
+        first_range_->end_ = position;
+      }
+      return;
+    }
+
     if (first_range_ == nullptr) {
       // First time we see a use of that interval.
       first_range_ = last_range_ = new (allocator_) LiveRange(start_block_position, position, nullptr);
@@ -198,7 +219,7 @@ class LiveInterval : public ArenaObject {
   }
 
   void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
-    DCHECK(instruction->AsPhi() != nullptr);
+    DCHECK(instruction->IsPhi());
     first_use_ = new (allocator_) UsePosition(
         instruction, input_index, false, block->GetLifetimeEnd(), first_use_);
   }
@@ -339,7 +360,9 @@ class LiveInterval : public ArenaObject {
       if (use_position >= position && !use->GetIsEnvironment()) {
         Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
         if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) {
-          return use_position;
+          // Return the lifetime just before the user, so that the interval has a register
+          // when entering the user.
+          return use->GetUser()->GetLifetimePosition() - 1;
         }
       }
       use = use->GetNext();
@@ -428,12 +451,12 @@ class LiveInterval : public ArenaObject {
     return nullptr;
   }
 
-  bool StartsBefore(LiveInterval* other) const {
+  bool StartsBeforeOrAt(LiveInterval* other) const {
     return GetStart() <= other->GetStart();
   }
 
   bool StartsAfter(LiveInterval* other) const {
-    return GetStart() >= other->GetStart();
+    return GetStart() > other->GetStart();
   }
 
   void Dump(std::ostream& stream) const {