Fix off by one errors in linear scan register allocator.
Change-Id: I65eea3cc125e12106a7160d30cb91c5d173bd405
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 9e63f8b..6174ac6 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1831,7 +1831,7 @@
} 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 3b51bfb..fc65f97 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -260,10 +260,10 @@
// 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 @@
// (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 @@
// 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 @@
}
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 8ce5ce9..8f71848 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -370,14 +370,12 @@
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 0000000..e69de29
--- /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 0000000..c706c1d
--- /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 0000000..3e649f8
--- /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");
+ }
+ }
+}
