From 5b168deeae2c5a8a566ce5c140741f0e2227af21 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Fri, 27 Mar 2015 10:27:22 +0000 Subject: [PATCH] Fix user-build on fugu. Calling Delete on an array shifts the elements, so when iterating over inactives and removing entries we need to decrement for the found interval, but also its potential other half. The code used to not decrement for the other half Change-Id: Idcb1533643c11a37ed4f459fe88aaef208a4bfd6 --- compiler/optimizing/register_allocator.cc | 64 +++++++++++------------------ compiler/optimizing/register_allocator.h | 7 ++++ test/467-regalloc-pair/expected.txt | 1 + test/467-regalloc-pair/info.txt | 2 + test/467-regalloc-pair/smali/TestCase.smali | 59 ++++++++++++++++++++++++++ test/467-regalloc-pair/src/Main.java | 37 +++++++++++++++++ 6 files changed, 131 insertions(+), 39 deletions(-) create mode 100644 test/467-regalloc-pair/expected.txt create mode 100644 test/467-regalloc-pair/info.txt create mode 100644 test/467-regalloc-pair/smali/TestCase.smali create mode 100644 test/467-regalloc-pair/src/Main.java diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index cecc210cb..efb98f0ad 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -851,6 +851,23 @@ bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position return false; } +bool RegisterAllocator::PotentiallyRemoveOtherHalf(LiveInterval* interval, + GrowableArray* intervals, + size_t index) { + if (interval->IsLowInterval()) { + DCHECK_EQ(intervals->Get(index), interval->GetHighInterval()); + intervals->DeleteAt(index); + return true; + } else if (interval->IsHighInterval()) { + DCHECK_GT(index, 0u); + DCHECK_EQ(intervals->Get(index - 1), interval->GetLowInterval()); + intervals->DeleteAt(index - 1); + return true; + } else { + return false; + } +} + // Find the register that is used the last, and spill the interval // that holds it. If the first use of `current` is after that register // we spill `current` instead. @@ -974,33 +991,17 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { if (active->GetRegister() == reg) { DCHECK(!active->IsFixed()); LiveInterval* split = Split(active, current->GetStart()); - active_.DeleteAt(i); if (split != active) { handled_.Add(active); } + active_.DeleteAt(i); + PotentiallyRemoveOtherHalf(active, &active_, i); AddSorted(unhandled_, split); - - if (active->IsLowInterval() || active->IsHighInterval()) { - LiveInterval* other_half = active->IsLowInterval() - ? active->GetHighInterval() - : active->GetLowInterval(); - // We also need to remove the other half from the list of actives. - bool found = false; - for (size_t j = 0; j < active_.Size(); ++j) { - if (active_.Get(j) == other_half) { - found = true; - active_.DeleteAt(j); - handled_.Add(other_half); - break; - } - } - DCHECK(found); - } break; } } - for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { + for (size_t i = 0; i < inactive_.Size(); ++i) { LiveInterval* inactive = inactive_.Get(i); if (inactive->GetRegister() == reg) { if (!current->IsSplit() && !inactive->IsFixed()) { @@ -1024,29 +1025,14 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { // If it's inactive, it must start before the current interval. DCHECK_NE(split, inactive); inactive_.DeleteAt(i); + if (PotentiallyRemoveOtherHalf(inactive, &inactive_, i) && inactive->IsHighInterval()) { + // We have removed an entry prior to `inactive`. So we need to decrement. + --i; + } + // Decrement because we have removed `inactive` from the list. --i; - --e; handled_.Add(inactive); AddSorted(unhandled_, split); - - if (inactive->IsLowInterval() || inactive->IsHighInterval()) { - LiveInterval* other_half = inactive->IsLowInterval() - ? inactive->GetHighInterval() - : inactive->GetLowInterval(); - - // We also need to remove the other half from the list of inactives. - bool found = false; - for (size_t j = 0; j < inactive_.Size(); ++j) { - if (inactive_.Get(j) == other_half) { - found = true; - inactive_.DeleteAt(j); - --e; - handled_.Add(other_half); - break; - } - } - DCHECK(found); - } } } } diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h index fcc61128a..717be7553 100644 --- a/compiler/optimizing/register_allocator.h +++ b/compiler/optimizing/register_allocator.h @@ -144,6 +144,13 @@ class RegisterAllocator { size_t first_register_use, size_t* next_use); + // If `interval` has another half, remove it from the list of `intervals`. + // `index` holds the index at which `interval` is in `intervals`. + // Returns whether there is another half. + bool PotentiallyRemoveOtherHalf(LiveInterval* interval, + GrowableArray* intervals, + size_t index); + ArenaAllocator* const allocator_; CodeGenerator* const codegen_; const SsaLivenessAnalysis& liveness_; diff --git a/test/467-regalloc-pair/expected.txt b/test/467-regalloc-pair/expected.txt new file mode 100644 index 000000000..da39d9da2 --- /dev/null +++ b/test/467-regalloc-pair/expected.txt @@ -0,0 +1 @@ +In interface diff --git a/test/467-regalloc-pair/info.txt b/test/467-regalloc-pair/info.txt new file mode 100644 index 000000000..882a29c02 --- /dev/null +++ b/test/467-regalloc-pair/info.txt @@ -0,0 +1,2 @@ +Regression test for optimizing's register allocator +that used to trip when compiling TestCase.testCase on x86. diff --git a/test/467-regalloc-pair/smali/TestCase.smali b/test/467-regalloc-pair/smali/TestCase.smali new file mode 100644 index 000000000..a3101feb1 --- /dev/null +++ b/test/467-regalloc-pair/smali/TestCase.smali @@ -0,0 +1,59 @@ +# 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 public LTestCase; + +.super Ljava/lang/Object; + +.method public static testCase([BLMain;)V + .registers 12 + const/4 v2, 0 + array-length v0, v10 + div-int/lit8 v0, v0, 7 + invoke-static {v2, v0}, Ljava/lang/Math;->max(II)I + move-result v7 + move v6, v2 + move v3, v2 + :label5 + if-ge v6, v7, :label1 + const-wide/16 v0, 0 + move-wide v4, v0 + move v1, v2 + move v0, v3 + :label4 + const/4 v3, 6 + if-ge v1, v3, :label2 + const/16 v3, 8 + shl-long/2addr v4, v3 + add-int/lit8 v3, v0, 1 + aget-byte v0, v10, v0 + if-gez v0, :label3 + add-int/lit16 v0, v0, 256 + :label3 + int-to-long v8, v0 + or-long/2addr v4, v8 + add-int/lit8 v0, v1, 1 + move v1, v0 + move v0, v3 + goto :label4 + :label2 + add-int/lit8 v3, v0, 1 + aget-byte v0, v10, v0 + invoke-interface {v11, v4, v5, v0}, LItf;->invokeInterface(JI)V + add-int/lit8 v0, v6, 1 + move v6, v0 + goto :label5 + :label1 + return-void +.end method diff --git a/test/467-regalloc-pair/src/Main.java b/test/467-regalloc-pair/src/Main.java new file mode 100644 index 000000000..aac07fdc2 --- /dev/null +++ b/test/467-regalloc-pair/src/Main.java @@ -0,0 +1,37 @@ +/* + * 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. + */ + +import java.lang.reflect.Method; + +interface Itf { + public void invokeInterface(long l, int i); +} + +public class Main implements Itf { + + // Workaround for b/18051191. + class InnerClass {} + + public static void main(String[] args) throws Exception { + Class c = Class.forName("TestCase"); + Method m = c.getMethod("testCase", byte[].class, Main.class); + m.invoke(null, new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 }, new Main()); + } + + public void invokeInterface(long l, int i) { + System.out.println("In interface"); + } +} -- 2.11.0