Do not inline loops without exit edges
Fixes an issue with LinearOrder after inlining a function containing a
loop that has no exit edge. The failure is due to incorrect loop
information being computed for blocks that are not on a path to the
inlined function's return. They should not be considered part of the
caller's enclosing loop, but are today.
Bug: 32547653
Test: run-test --host 478-checker-inline-noreturn
Change-Id: I9694a1cb861430051c801d07f7ce29752332cba5
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 9e81623..7fe54b9 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -1226,12 +1226,22 @@
// Skip the entry block, it does not contain instructions that prevent inlining.
for (HBasicBlock* block : callee_graph->GetReversePostOrderSkipEntryBlock()) {
- if (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible()) {
- // Don't inline methods with irreducible loops, they could prevent some
- // optimizations to run.
- VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
- << " could not be inlined because it contains an irreducible loop";
- return false;
+ if (block->IsLoopHeader()) {
+ if (block->GetLoopInformation()->IsIrreducible()) {
+ // Don't inline methods with irreducible loops, they could prevent some
+ // optimizations to run.
+ VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
+ << " could not be inlined because it contains an irreducible loop";
+ return false;
+ }
+ if (!block->GetLoopInformation()->HasExitEdge()) {
+ // Don't inline methods with loops without exit, since they cause the
+ // loop information to be computed incorrectly when updating after
+ // inlining.
+ VLOG(compiler) << "Method " << callee_dex_file.PrettyMethod(method_index)
+ << " could not be inlined because it contains a loop with no exit";
+ return false;
+ }
}
for (HInstructionIterator instr_it(block->GetInstructions());
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 4f2e257..cdd9c14 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -735,6 +735,20 @@
return true;
}
+
+bool HLoopInformation::HasExitEdge() const {
+ // Determine if this loop has at least one exit edge.
+ HBlocksInLoopReversePostOrderIterator it_loop(*this);
+ for (; !it_loop.Done(); it_loop.Advance()) {
+ for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) {
+ if (!Contains(*successor)) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
bool HBasicBlock::Dominates(HBasicBlock* other) const {
// Walk up the dominator tree from `other`, to find out if `this`
// is an ancestor.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 0e449e3..7d74e47 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -769,6 +769,8 @@
bool DominatesAllBackEdges(HBasicBlock* block);
+ bool HasExitEdge() const;
+
private:
// Internal recursive implementation of `Populate`.
void PopulateRecursive(HBasicBlock* block);
diff --git a/test/478-checker-inline-noreturn/expected.txt b/test/478-checker-inline-noreturn/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/478-checker-inline-noreturn/expected.txt
diff --git a/test/478-checker-inline-noreturn/info.txt b/test/478-checker-inline-noreturn/info.txt
new file mode 100644
index 0000000..64f42ed
--- /dev/null
+++ b/test/478-checker-inline-noreturn/info.txt
@@ -0,0 +1,3 @@
+Tests inlining a function with a no-exit loop into a loop. LinearOrder
+computation fails because of incorrect HLoopInformation if we inline
+a loop without an exit.
diff --git a/test/478-checker-inline-noreturn/src/Main.java b/test/478-checker-inline-noreturn/src/Main.java
new file mode 100644
index 0000000..7aaeac0
--- /dev/null
+++ b/test/478-checker-inline-noreturn/src/Main.java
@@ -0,0 +1,60 @@
+/*
+ * 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.
+ */
+
+
+/*
+ * A test that checks that the inliner does not inline functions that contain
+ * a loop with no exit. This because the incremental update to
+ * HLoopInformation done by the inliner does not work with the LinearOrder
+ * computation if the inlined function does not always return.
+ */
+
+public class Main {
+
+ public static void assertIntEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+
+ public static int $opt$noinline$Function(int x, int y) {
+ int result;
+ if (x <= y) {
+ result = 42;
+ } else {
+ while (true);
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.callerLoop(int, int) inliner (before)
+ /// CHECK: InvokeStaticOrDirect method_name:Main.$opt$noinline$Function loop:{{B\d+}}
+
+ /// CHECK-START: int Main.callerLoop(int, int) inliner (after)
+ /// CHECK: InvokeStaticOrDirect method_name:Main.$opt$noinline$Function loop:{{B\d+}}
+
+ public static int callerLoop(int max_x, int max_y) {
+ int total = 0;
+ for (int x = 0; x < max_x; ++x) {
+ total += $opt$noinline$Function(x, max_y);
+ }
+ return total;
+ }
+
+ public static void main(String[] args) {
+ assertIntEquals(42, callerLoop(1, 1));
+ }
+}