DCE SimplifyAlwaysThrowing optimizations
We can do two optimizations to this method:
1) If we have a try catch in the graph, we now allow to simplify
always throwing instructions to point them directly to the exit
block.
2) We now allow to simplify always throwing instruction for
non-trivial basic blocks i.e. not just Invoke and a Goto. We
still require that the second to last instruction is an always
throwing invoke followed by a Goto.
Bug: 227316307
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I8208163e48b07d8a1bb77e11763516f65fb88827
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 1dc1094..d808f2c 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -209,6 +209,9 @@
//
// B1
// / \
+// | instr_1
+// | ...
+// | instr_n
// | foo() // always throws
// \ goto B2
// \ /
@@ -218,6 +221,9 @@
//
// B1
// / \
+// | instr_1
+// | ...
+// | instr_n
// | foo()
// | goto Exit
// | |
@@ -227,10 +233,6 @@
// Removal of the never taken edge to B2 may expose
// other optimization opportunities, such as code sinking.
bool HDeadCodeElimination::SimplifyAlwaysThrows() {
- // Make sure exceptions go to exit.
- if (graph_->HasTryCatch()) {
- return false;
- }
HBasicBlock* exit = graph_->GetExitBlock();
if (exit == nullptr) {
return false;
@@ -240,15 +242,35 @@
// Order does not matter, just pick one.
for (HBasicBlock* block : graph_->GetReversePostOrder()) {
- HInstruction* first = block->GetFirstInstruction();
+ if (block->GetTryCatchInformation() != nullptr) {
+ // We don't want to perform the simplify always throws optimizations for throws inside of
+ // tries since those throws might not go to the exit block. We do that by checking the
+ // TryCatchInformation of the blocks.
+ //
+ // As a special case the `catch_block` is the first block of the catch and it has
+ // TryCatchInformation. Other blocks in the catch don't have try catch information (as long as
+ // they are not part of an outer try). Knowing if a `catch_block` is part of an outer try is
+ // possible by checking its successors, but other restrictions of the simplify always throws
+ // optimization will block `catch_block` nevertheless (e.g. only one predecessor) so it is not
+ // worth the effort.
+
+ // TODO(solanes): Maybe we can do a `goto catch` if inside of a try catch instead of going to
+ // the exit. If we do so, we have to take into account that we should go to the nearest valid
+ // catch i.e. one that would accept our exception type.
+ continue;
+ }
+
HInstruction* last = block->GetLastInstruction();
- // Ensure only one throwing instruction appears before goto.
- if (first->AlwaysThrows() &&
- first->GetNext() == last &&
+ HInstruction* prev = last->GetPrevious();
+ if (prev == nullptr) {
+ DCHECK_EQ(block->GetFirstInstruction(), block->GetLastInstruction());
+ continue;
+ }
+
+ if (prev->AlwaysThrows() &&
last->IsGoto() &&
block->GetPhis().IsEmpty() &&
block->GetPredecessors().size() == 1u) {
- DCHECK_EQ(block->GetSuccessors().size(), 1u);
HBasicBlock* pred = block->GetSinglePredecessor();
HBasicBlock* succ = block->GetSingleSuccessor();
// Ensure no computations are merged through throwing block.
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 716fee4..4a6ee13 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -586,6 +586,10 @@
StartAttributeStream("kind") << (try_boundary->IsEntry() ? "entry" : "exit");
}
+ void VisitGoto(HGoto* instruction) override {
+ StartAttributeStream("target") << namer_.GetName(instruction->GetBlock()->GetSingleSuccessor());
+ }
+
void VisitDeoptimize(HDeoptimize* deoptimize) override {
StartAttributeStream("kind") << deoptimize->GetKind();
}
@@ -657,10 +661,8 @@
StartAttributeStream("dex_pc") << "n/a";
}
HBasicBlock* block = instruction->GetBlock();
- if (IsPass(kDebugDumpName)) {
- // Include block name for logcat use.
- StartAttributeStream("block") << namer_.GetName(block);
- }
+ StartAttributeStream("block") << namer_.GetName(block);
+
instruction->Accept(this);
if (instruction->HasEnvironment()) {
StringList envs;
diff --git a/test/2042-checker-dce-always-throw/expected-stderr.txt b/test/2042-checker-dce-always-throw/expected-stderr.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2042-checker-dce-always-throw/expected-stderr.txt
diff --git a/test/2042-checker-dce-always-throw/expected-stdout.txt b/test/2042-checker-dce-always-throw/expected-stdout.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2042-checker-dce-always-throw/expected-stdout.txt
diff --git a/test/2042-checker-dce-always-throw/info.txt b/test/2042-checker-dce-always-throw/info.txt
new file mode 100644
index 0000000..db45200
--- /dev/null
+++ b/test/2042-checker-dce-always-throw/info.txt
@@ -0,0 +1 @@
+Tests regarding simplifying always throwing instructions in dead code elimination.
diff --git a/test/2042-checker-dce-always-throw/src/Main.java b/test/2042-checker-dce-always-throw/src/Main.java
new file mode 100644
index 0000000..705aca4
--- /dev/null
+++ b/test/2042-checker-dce-always-throw/src/Main.java
@@ -0,0 +1,240 @@
+/*
+ * Copyright (C) 2022 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.
+ */
+
+public class Main {
+ public static void main(String[] args) throws Exception {
+ // Basic test
+ assertEquals(0, $noinline$testSimplifyThrow(1));
+
+ // Basic test for non-trivial blocks (i.e. not just an invoke and a Goto)
+ assertEquals(0, $noinline$testSimplifyTwoThrows(1));
+
+ // Try catch tests
+ assertEquals(0, $noinline$testDoNotSimplifyInTry(1));
+ assertEquals(0, $noinline$testSimplifyInCatch(1));
+ assertEquals(0, $noinline$testDoNotSimplifyInCatchInOuterTry(1));
+ }
+
+ private static void alwaysThrows() throws Error {
+ throw new Error("");
+ }
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrow(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrow(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+
+ // Tests that we simplify the always throwing branch directly to the exit.
+ private static int $noinline$testSimplifyThrow(int num) {
+ if (num == 0) {
+ alwaysThrows();
+ }
+ return 0;
+ }
+
+ /// CHECK-START: int Main.$noinline$testSimplifyTwoThrows(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testSimplifyTwoThrows(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+
+ // Tests that we simplify the always throwing branch directly to the exit, even with blocks that
+ // are not just the throwing instruction and a Goto.
+ private static int $noinline$testSimplifyTwoThrows(int num) {
+ if (num == 0) {
+ alwaysThrows();
+ alwaysThrows();
+ }
+ return 0;
+ }
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowWithTryCatch(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowWithTryCatch(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+
+ // Consistency check to make sure we have the try catches in the graph at this stage.
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowWithTryCatch(int) dead_code_elimination$after_gvn (before)
+ /// CHECK: TryBoundary kind:entry
+ /// CHECK: TryBoundary kind:entry
+
+ // Tests that we simplify the always throwing branch directly to the exit, with non-blocking try
+ // catches in the graph.
+ private static int $noinline$testSimplifyThrowWithTryCatch(int num) {
+ try {
+ if (num == 123) {
+ throw new Error();
+ }
+ } catch (Error e) {
+ return 123;
+ }
+
+ if (num == 0) {
+ alwaysThrows();
+ }
+
+ try {
+ if (num == 456) {
+ throw new Error();
+ }
+ } catch (Error e) {
+ return 456;
+ }
+ return 0;
+ }
+
+ private static void $inline$testDoNotSimplifyInner(int num) {
+ alwaysThrows();
+ while (num == 0) {
+ // We should never hit this since we are always throwing.
+ System.out.println(num);
+ }
+ }
+
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInTry(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInTry(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ // Consistency check to make sure we have the try catch in the graph at this stage.
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInTry(int) dead_code_elimination$after_gvn (before)
+ /// CHECK: TryBoundary kind:entry
+
+ // Consistency check to that we do not simplify it by the last DCE pass either
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInTry(int) dead_code_elimination$final (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ // Tests that we have the necessary conditions for us to simplify the always throwing instruction
+ // (e.g. InvokeStaticOrDirect followed by a Goto) but we are blocking this due to being in a try.
+ // Changing the Goto here for the exit would be wrong since we want to flow to the catch rather
+ // than the Exit. The preconditions are tricky to do with just one function (since we will have an
+ // invoke followed by a TryBoundary rather than a Goto) but we can do so with the help of the
+ // inliner.
+ private static int $noinline$testDoNotSimplifyInTry(int num) {
+ try {
+ $inline$testDoNotSimplifyInner(num);
+ } catch (Error e) {
+ return 0;
+ }
+ return 123;
+ }
+
+ /// CHECK-START: int Main.$noinline$testSimplifyInCatch(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testSimplifyInCatch(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+
+ // Consistency check to make sure we have the try catch in the graph at this stage.
+ /// CHECK-START: int Main.$noinline$testSimplifyInCatch(int) dead_code_elimination$after_gvn (before)
+ /// CHECK: TryBoundary kind:entry
+
+ // We are able to simplify the `alwaysThrows` even though we are inside of the catch { ... } since
+ // the if makes it so that we are not the first block of the catch and therefore not in the
+ // "catch_block".
+ private static int $noinline$testSimplifyInCatch(int num) {
+ try {
+ throw new Error();
+ } catch (Error e) {
+ if (num == 0) {
+ alwaysThrows();
+ }
+ return 0;
+ }
+ }
+
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInCatchInOuterTry(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInCatchInOuterTry(int) dead_code_elimination$after_gvn (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ // Consistency check to make sure we have the try catches in the graph at this stage.
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInCatchInOuterTry(int) dead_code_elimination$after_gvn (before)
+ /// CHECK-DAG: TryBoundary kind:entry
+ /// CHECK-DAG: TryBoundary kind:entry
+
+ // Consistency check to that we do not simplify it by the last DCE pass either
+ /// CHECK-START: int Main.$noinline$testDoNotSimplifyInCatchInOuterTry(int) dead_code_elimination$final (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ // Similar to testSimplifyInCatch, but now the throw is in an outer try and we shouldn't simplify
+ // it. Like in testDoNotSimplifyInTry, we need the help of the inliner to have an invoke followed
+ // by a Goto.
+ private static int $noinline$testDoNotSimplifyInCatchInOuterTry(int num) {
+ try {
+ try {
+ throw new Error();
+ } catch (Error e) {
+ if (num == 0) {
+ $inline$testDoNotSimplifyInner(num);
+ }
+ return 0;
+ }
+ } catch (Error e) {
+ return 123;
+ }
+ }
+
+ static void assertEquals(int expected, int actual) {
+ if (expected != actual) {
+ throw new AssertionError("Expected " + expected + " got " + actual);
+ }
+ }
+}
