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
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 32c3a92..2218d0b 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -505,6 +505,7 @@
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 d77639d..44fb8de 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -179,7 +179,7 @@
}
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 @@
}
// 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 @@
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 @@
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 0000000..d00491f
--- /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 0000000..1e0dd02
--- /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 0000000..8a8c4eb
--- /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 0000000..3adb08c
--- /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));
+ }
+}