From 79e9f43951c3cfa9ab3b0fea93e5bfdfa7aa5950 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Sat, 23 Jan 2016 23:00:45 +0000 Subject: [PATCH] Lift the spill at each irreducible loop block restriction. It was not intended to have it this way anyway. This also required to fix GetSiblingAt, to take into account interval holes, and ConnectSplitSibling to re-materialize a constant or a method. Change-Id: Ia5534a93a5413cd0458a251c022d0b655369502b --- compiler/optimizing/graph_visualizer.cc | 1 + compiler/optimizing/register_allocator.cc | 37 +++++++++++++--- test/565-checker-irreducible-loop/expected.txt | 1 + test/565-checker-irreducible-loop/info.txt | 2 + .../smali/IrreducibleLoop.smali | 50 ++++++++++++++++++++++ test/565-checker-irreducible-loop/src/Main.java | 29 +++++++++++++ 6 files changed, 114 insertions(+), 6 deletions(-) create mode 100644 test/565-checker-irreducible-loop/expected.txt create mode 100644 test/565-checker-irreducible-loop/info.txt create mode 100644 test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali create mode 100644 test/565-checker-irreducible-loop/src/Main.java diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index 32c3a925e..2218d0b82 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -505,6 +505,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { if (IsPass(LICM::kLoopInvariantCodeMotionPassName) || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName) || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName) + || IsPass(RegisterAllocator::kRegisterAllocatorPassName) || IsPass(SsaBuilder::kSsaBuilderPassName)) { HLoopInformation* info = instruction->GetBlock()->GetLoopInformation(); if (info == nullptr) { diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index d77639d60..44fb8de97 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -179,7 +179,7 @@ void RegisterAllocator::AllocateRegistersInternal() { } if (block->IsCatchBlock() || - (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) { + (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { // By blocking all registers at the top of each catch block or irreducible loop, we force // intervals belonging to the live-in set of the catch/header block to be spilled. // TODO(ngeoffray): Phis in this block could be allocated in register. @@ -1749,8 +1749,10 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, } // Find the intervals that cover `from` and `to`. - LiveInterval* destination = interval->GetSiblingAt(to->GetLifetimeStart()); - LiveInterval* source = interval->GetSiblingAt(from->GetLifetimeEnd() - 1); + size_t destination_position = to->GetLifetimeStart(); + size_t source_position = from->GetLifetimeEnd() - 1; + LiveInterval* destination = interval->GetSiblingAt(destination_position); + LiveInterval* source = interval->GetSiblingAt(source_position); if (destination == source) { // Interval was not split. @@ -1775,18 +1777,41 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, return; } + Location location_source; + // `GetSiblingAt` returns the interval whose start and end cover `position`, + // but does not check whether the interval is inactive at that position. + // The only situation where the interval is inactive at that position is in the + // presence of irreducible loops for constants and ArtMethod. + if (codegen_->GetGraph()->HasIrreducibleLoops() && + (source == nullptr || !source->CoversSlow(source_position))) { + DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by)); + if (defined_by->IsConstant()) { + location_source = defined_by->GetLocations()->Out(); + } else { + DCHECK(defined_by->IsCurrentMethod()); + location_source = parent->NeedsTwoSpillSlots() + ? Location::DoubleStackSlot(parent->GetSpillSlot()) + : Location::StackSlot(parent->GetSpillSlot()); + } + } else { + DCHECK(source != nullptr); + DCHECK(source->CoversSlow(source_position)); + DCHECK(destination->CoversSlow(destination_position)); + location_source = source->ToLocation(); + } + // If `from` has only one successor, we can put the moves at the exit of it. Otherwise // we need to put the moves at the entry of `to`. if (from->GetNormalSuccessors().size() == 1) { InsertParallelMoveAtExitOf(from, defined_by, - source->ToLocation(), + location_source, destination->ToLocation()); } else { DCHECK_EQ(to->GetPredecessors().size(), 1u); InsertParallelMoveAtEntryOf(to, defined_by, - source->ToLocation(), + location_source, destination->ToLocation()); } } @@ -1890,7 +1915,7 @@ void RegisterAllocator::Resolve() { for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); if (block->IsCatchBlock() || - (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) { + (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { // Instructions live at the top of catch blocks or irreducible loop header // were forced to spill. if (kIsDebugBuild) { diff --git a/test/565-checker-irreducible-loop/expected.txt b/test/565-checker-irreducible-loop/expected.txt new file mode 100644 index 000000000..d00491fd7 --- /dev/null +++ b/test/565-checker-irreducible-loop/expected.txt @@ -0,0 +1 @@ +1 diff --git a/test/565-checker-irreducible-loop/info.txt b/test/565-checker-irreducible-loop/info.txt new file mode 100644 index 000000000..1e0dd0228 --- /dev/null +++ b/test/565-checker-irreducible-loop/info.txt @@ -0,0 +1,2 @@ +Regression test for optimizing in the presence of +an irreducible loop. diff --git a/test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali new file mode 100644 index 000000000..8a8c4eb4a --- /dev/null +++ b/test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali @@ -0,0 +1,50 @@ +# Copyright (C) 2016 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 LIrreducibleLoop; + +.super Ljava/lang/Object; + +# Check that both the irreducible loop and the other loop entry +# move the constant-folded value to where it's expected. + +## CHECK-START-X86: int IrreducibleLoop.simpleLoop(int, long) register (after) +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:none +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:{{B\d+}} irreducible:true +.method public static simpleLoop(IJ)I + .registers 10 + const/16 v6, 2 + const/16 v4, 1 + const-wide/16 v0, 42 + add-long v2, v0, v0 + + if-eqz p0, :loop_entry + goto :other_loop_pre_entry + + # The then part: beginning of the irreducible loop. + :loop_entry + if-eqz p0, :exit + cmp-long v6, v2, p1 + :other_loop_entry + sub-int p0, p0, v4 + goto :loop_entry + + # The other block branching to the irreducible loop. + # In that block, v4 has no live range. + :other_loop_pre_entry + goto :other_loop_entry + + :exit + return v6 +.end method diff --git a/test/565-checker-irreducible-loop/src/Main.java b/test/565-checker-irreducible-loop/src/Main.java new file mode 100644 index 000000000..3adb08c2c --- /dev/null +++ b/test/565-checker-irreducible-loop/src/Main.java @@ -0,0 +1,29 @@ +/* + * Copyright (C) 2016 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; + +public class Main { + // Workaround for b/18051191. + class InnerClass {} + + public static void main(String[] args) throws Exception { + Class c = Class.forName("IrreducibleLoop"); + Method m = c.getMethod("simpleLoop", int.class, long.class); + Object[] arguments = { 42, 31L }; + System.out.println(m.invoke(null, arguments)); + } +} -- 2.11.0