Fix a bug in the register allocator when allocating pairs.
bug:22913897
Change-Id: I402d8a29a482f6cb98c8d1fcdcbf0eddf744e038
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 72ddabe..00848f3 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -949,7 +949,16 @@
// we spill `current` instead.
bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
size_t first_register_use = current->FirstRegisterUse();
- if (first_register_use == kNoLifetime) {
+ if (current->HasRegister()) {
+ DCHECK(current->IsHighInterval());
+ // The low interval has allocated the register for the high interval. In
+ // case the low interval had to split both intervals, we may end up in a
+ // situation where the high interval does not have a register use anymore.
+ // We must still proceed in order to split currently active and inactive
+ // uses of the high interval's register, and put the high interval in the
+ // active set.
+ DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr));
+ } else if (first_register_use == kNoLifetime) {
AllocateSpillSlotFor(current);
return false;
}
@@ -1016,7 +1025,7 @@
// When allocating the low part, we made sure the high register was available.
DCHECK_LT(first_use, next_use[reg]);
} else if (current->IsLowInterval()) {
- reg = FindAvailableRegisterPair(next_use, first_register_use);
+ reg = FindAvailableRegisterPair(next_use, first_use);
// We should spill if both registers are not available.
should_spill = (first_use >= next_use[reg])
|| (first_use >= next_use[GetHighForLowRegister(reg)]);
@@ -1030,16 +1039,28 @@
if (should_spill) {
DCHECK(!current->IsHighInterval());
bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1));
- if (current->IsLowInterval()
- && is_allocation_at_use_site
- && TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(),
- first_register_use,
- next_use)) {
+ if (is_allocation_at_use_site) {
+ if (!current->IsLowInterval()) {
+ DumpInterval(std::cerr, current);
+ DumpAllIntervals(std::cerr);
+ // This situation has the potential to infinite loop, so we make it a non-debug CHECK.
+ HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2);
+ CHECK(false) << "There is not enough registers available for "
+ << current->GetParent()->GetDefinedBy()->DebugName() << " "
+ << current->GetParent()->GetDefinedBy()->GetId()
+ << " at " << first_register_use - 1 << " "
+ << (at == nullptr ? "" : at->DebugName());
+ }
+
// If we're allocating a register for `current` because the instruction at
// that position requires it, but we think we should spill, then there are
// non-pair intervals or unaligned pair intervals blocking the allocation.
// We split the first interval found, and put ourselves first in the
// `unhandled_` list.
+ bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(),
+ first_register_use,
+ next_use);
+ DCHECK(success);
LiveInterval* existing = unhandled_->Peek();
DCHECK(existing->IsHighInterval());
DCHECK_EQ(existing->GetLowInterval(), current);
@@ -1049,17 +1070,7 @@
// register, we split this interval just before its first register use.
AllocateSpillSlotFor(current);
LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
- if (current == split) {
- DumpInterval(std::cerr, current);
- DumpAllIntervals(std::cerr);
- // This situation has the potential to infinite loop, so we make it a non-debug CHECK.
- HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2);
- CHECK(false) << "There is not enough registers available for "
- << split->GetParent()->GetDefinedBy()->DebugName() << " "
- << split->GetParent()->GetDefinedBy()->GetId()
- << " at " << first_register_use - 1 << " "
- << (at == nullptr ? "" : at->DebugName());
- }
+ DCHECK(current != split);
AddSorted(unhandled_, split);
}
return false;
@@ -1240,7 +1251,9 @@
void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
if (interval->IsHighInterval()) {
- // The low interval will contain the spill slot.
+ // The low interval already took care of allocating the spill slot.
+ DCHECK(!interval->GetLowInterval()->HasRegister());
+ DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot());
return;
}
diff --git a/test/526-long-regalloc/expected.txt b/test/526-long-regalloc/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/526-long-regalloc/expected.txt
diff --git a/test/526-long-regalloc/info.txt b/test/526-long-regalloc/info.txt
new file mode 100644
index 0000000..a5ce1bc
--- /dev/null
+++ b/test/526-long-regalloc/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing that used to trip when allocating a register
+pair under certain circumstances.
diff --git a/test/526-long-regalloc/src/Main.java b/test/526-long-regalloc/src/Main.java
new file mode 100644
index 0000000..e8b3096
--- /dev/null
+++ b/test/526-long-regalloc/src/Main.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+class Main {
+ public static void main(String[] args) {
+ foo();
+ }
+
+ public static void foo() {
+ int a = myField1; // esi
+ int b = myField2; // edi
+ $noinline$bar(); // makes allocation of a and b to be callee-save registers
+ int c = myField3; // ecx
+ int e = myField4; // ebx
+ int f = myField5; // edx
+ long d = a == 42 ? myLongField1 : 42L; // Will call AllocateBlockedReg -> edx/ebx
+
+ // At this point, the register allocator used to be in a bogus state, where the low
+ // part of the interval was in the active set, but not the high part.
+
+ long i = myLongField1; // Will call TrySplitNonPairOrUnalignedPairIntervalAt -> Failing DCHECK
+
+ // Use esi and edi first to not have d allocated to them.
+ myField2 = a;
+ myField3 = b;
+
+ // The following sequence of instructions are making the AllocateBlockedReg call
+ // for allocating the d variable misbehave: allocation of the low interval would split
+ // both low and high interval at the fixed use; therefore the allocation of the high interval
+ // would not see the register use, and think the interval can just be spilled and not be
+ // put in the active set, even though it is holding a register.
+ myField1 = (int)d; // stack use
+ myLongField3 = (long) myField2; // edx fixed use
+ myLongField2 = d; // register use
+
+ // Ensure the HInstruction mapping to i, c, e, and f have a live range.
+ myLongField1 = i;
+ myField4 = c;
+ myField5 = e;
+ myField6 = f;
+ }
+
+ public static long $noinline$bar() {
+ if (doThrow) throw new Error();
+ return 42;
+ }
+
+ public static boolean doThrow = false;
+
+ public static int myField1 = 0;
+ public static int myField2 = 0;
+ public static int myField3 = 0;
+ public static int myField4 = 0;
+ public static int myField5 = 0;
+ public static int myField6 = 0;
+ public static long myLongField1 = 0L;
+ public static long myLongField2 = 0L;
+ public static long myLongField3 = 0L;
+}