Fix off by one errors in linear scan register allocator.

Change-Id: I65eea3cc125e12106a7160d30cb91c5d173bd405

6 files changed, 53 insertions, 8 deletions

diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 9e63f8bc52..6174ac6be0 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1831,7 +1831,7 @@ void ParallelMoveResolverX86_64::EmitMove(size_t index) {
     } else if (destination.IsFpuRegister()) {
       __ movsd(destination.As<XmmRegister>(), Address(CpuRegister(RSP), source.GetStackIndex()));
     } else {
-      DCHECK(destination.IsDoubleStackSlot());
+      DCHECK(destination.IsDoubleStackSlot()) << destination;
       __ movq(CpuRegister(TMP), Address(CpuRegister(RSP), source.GetStackIndex()));
       __ movq(Address(CpuRegister(RSP), destination.GetStackIndex()), CpuRegister(TMP));
     }
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 3b51bfb2d0..fc65f97f69 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -260,10 +260,10 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
 
   // If needed, add interval to the list of unhandled intervals.
   if (current->HasSpillSlot() || instruction->IsConstant()) {
-    // Split before first register use.
+    // Split just before first register use.
     size_t first_register_use = current->FirstRegisterUse();
     if (first_register_use != kNoLifetime) {
-      LiveInterval* split = Split(current, first_register_use);
+      LiveInterval* split = Split(current, first_register_use - 1);
       // 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);
@@ -436,6 +436,7 @@ void RegisterAllocator::LinearScan() {
     // (1) Remove interval with the lowest start position from unhandled.
     LiveInterval* current = unhandled_->Pop();
     DCHECK(!current->IsFixed() && !current->HasSpillSlot());
+    DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart());
     size_t position = current->GetStart();
 
     // (2) Remove currently active intervals that are dead at this position.
@@ -635,7 +636,9 @@ 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);
+    LiveInterval* split = Split(current, first_register_use - 1);
+    DCHECK_NE(current, split) << "There is not enough registers available for "
+      << split->GetParent()->GetDefinedBy()->DebugName();
     AddSorted(unhandled_, split);
     return false;
   } else {
@@ -679,6 +682,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
 }
 
 void RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) {
+  DCHECK(!interval->IsFixed() && !interval->HasSpillSlot());
   size_t insert_at = 0;
   for (size_t i = array->Size(); i > 0; --i) {
     LiveInterval* current = array->Get(i - 1);
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 8ce5ce902e..8f718480b3 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -370,14 +370,12 @@ class LiveInterval : public ArenaObject {
     size_t end = GetEnd();
     while (use != nullptr && use->GetPosition() <= end) {
       size_t use_position = use->GetPosition();
-      if (use_position >= position && !use->GetIsEnvironment()) {
+      if (use_position > position && !use->GetIsEnvironment()) {
         Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
         if (location.IsUnallocated()
             && (location.GetPolicy() == Location::kRequiresRegister
                 || location.GetPolicy() == Location::kRequiresFpuRegister)) {
-          // Return the lifetime just before the user, so that the interval has a register
-          // when entering the user.
-          return use->GetUser()->GetLifetimePosition() - 1;
+          return use_position;
         }
       }
       use = use->GetNext();
diff --git a/test/413-regalloc-regression/expected.txt b/test/413-regalloc-regression/expected.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/413-regalloc-regression/expected.txt
diff --git a/test/413-regalloc-regression/info.txt b/test/413-regalloc-regression/info.txt
new file mode 100644
index 0000000000..c706c1d4e4
--- /dev/null
+++ b/test/413-regalloc-regression/info.txt
@@ -0,0 +1,2 @@
+Regression test for the linear scan register allocator, that use to
+fail compiling removeElementAt in x86.
diff --git a/test/413-regalloc-regression/src/Main.java b/test/413-regalloc-regression/src/Main.java
new file mode 100644
index 0000000000..3e649f8e57
--- /dev/null
+++ b/test/413-regalloc-regression/src/Main.java
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+  private Object[] data;
+  private int size;
+
+  public Main() {
+    data = new Object[4];
+    size = 0;
+  }
+
+  public void removeElementAt(int index) {
+    for (int i = index; i < size - 1; i++) {
+      data[i] = data[i + 1];
+    }
+    data[--size] = null;
+  }
+
+  public static void main(String[] args) {
+    Main main = new Main();
+    main.size++;
+    main.removeElementAt(0);
+    if (main.size != 0) {
+      throw new Error("Unexpected size");
+    }
+  }
+}