diff options
| -rw-r--r-- | compiler/optimizing/graph_visualizer.cc | 1 | ||||
| -rw-r--r-- | compiler/optimizing/register_allocator.cc | 40 | ||||
| -rw-r--r-- | test/565-checker-irreducible-loop/expected.txt | 2 | ||||
| -rw-r--r-- | test/565-checker-irreducible-loop/info.txt | 2 | ||||
| -rw-r--r-- | test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali | 101 | ||||
| -rw-r--r-- | test/565-checker-irreducible-loop/src/Main.java | 37 |
6 files changed, 176 insertions, 7 deletions
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index 280516252b..9d796c1004 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -507,6 +507,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName) || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName) || IsPass(BoundsCheckElimination::kBoundsCheckEliminationPassName) + || 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 d77639d608..5cd30adb45 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. @@ -1759,7 +1761,8 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, LiveInterval* parent = interval->GetParent(); HInstruction* defined_by = parent->GetDefinedBy(); - if (destination == nullptr) { + if (codegen_->GetGraph()->HasIrreducibleLoops() && + (destination == nullptr || !destination->CoversSlow(destination_position))) { // Our live_in fixed point calculation has found that the instruction is live // in the `to` block because it will eventually enter an irreducible loop. Our // live interval computation however does not compute a fixed point, and @@ -1775,18 +1778,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 +1916,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 0000000000..6ed281c757 --- /dev/null +++ b/test/565-checker-irreducible-loop/expected.txt @@ -0,0 +1,2 @@ +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 0000000000..1e0dd02284 --- /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 0000000000..29547ca85e --- /dev/null +++ b/test/565-checker-irreducible-loop/smali/IrreducibleLoop.smali @@ -0,0 +1,101 @@ +# 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.test1(int, long) register (after) +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:none +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:{{B\d+}} irreducible:true +.method public static test1(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 + +# Check that the compiler does not crash when +# a live interval is found while connecting siblings, but that +# live interval is inactive at the desired position. + +## CHECK-START-X86: int IrreducibleLoop.test2(int, long) register (after) +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:none +## CHECK-DAG: ParallelMove {{.*84->.*}} loop:{{B\d+}} irreducible:true +.method public static test2(IJ)I + .registers 14 + const/16 v6, 2 + const/16 v4, 1 + const-wide/16 v0, 42 + const-wide/16 v8, 68 + 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. + :other_loop_pre_entry + # Make v2 have a register location. + sput-wide v2, LIrreducibleLoop;->myField:J + # Stress register allocator on x86 to split v2. + sput-wide v0, LIrreducibleLoop;->myField:J + sput-wide p1, LIrreducibleLoop;->myField:J + sput-wide v8, LIrreducibleLoop;->myField:J + if-eqz p0, :join + # Stress register allocator on x86 to split v2. + sput-wide p1, LIrreducibleLoop;->myField:J + sput-wide v8, LIrreducibleLoop;->myField:J + sput-wide v0, LIrreducibleLoop;->myField:J + # Last use of v2 before the irreducible loop, that + # will create an interval hole. + sput-wide v2, LIrreducibleLoop;->myField:J + :join + goto :other_loop_entry + + :exit + return v6 +.end method + +.field public static volatile myField:J 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 0000000000..e48bd6b411 --- /dev/null +++ b/test/565-checker-irreducible-loop/src/Main.java @@ -0,0 +1,37 @@ +/* + * 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("test1", int.class, long.class); + Object[] arguments = { 42, 31L }; + System.out.println(m.invoke(null, arguments)); + } + + { + Method m = c.getMethod("test2", int.class, long.class); + Object[] arguments = { 42, 31L }; + System.out.println(m.invoke(null, arguments)); + } + } +} |