DCE SimplifyAlwaysThrowing optimizations am: 298112a02c am: 936e0e9d00
Original change: https://android-review.googlesource.com/c/platform/art/+/2047843
Change-Id: I8b91e9cc3d402b578c89527cfc12f9a08320aaf3
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
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);
+ }
+ }
+}