ART: Update DCE to work with try/catch
Dead block elimination was previously disabled because it needed
to be updated. With this patch, try/catch blocks can be removed
as a result of a dead if/switch branch.
Change-Id: I3261060bf24fd5fe7bb0f989247f0ef62ec5fd7b
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 9754043..02e5dab 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -123,20 +123,21 @@
}
// If we removed at least one block, we need to recompute the full
- // dominator tree.
+ // dominator tree and try block membership.
if (removed_one_or_more_blocks) {
graph_->ClearDominanceInformation();
graph_->ComputeDominanceInformation();
+ graph_->ComputeTryBlockInformation();
}
// Connect successive blocks created by dead branches. Order does not matter.
for (HReversePostOrderIterator it(*graph_); !it.Done();) {
HBasicBlock* block = it.Current();
- if (block->IsEntryBlock() || block->GetSuccessors().size() != 1u) {
+ if (block->IsEntryBlock() || !block->GetLastInstruction()->IsGoto()) {
it.Advance();
continue;
}
- HBasicBlock* successor = block->GetSuccessors()[0];
+ HBasicBlock* successor = block->GetSingleSuccessor();
if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) {
it.Advance();
continue;
@@ -176,10 +177,7 @@
}
void HDeadCodeElimination::Run() {
- if (!graph_->HasTryCatch()) {
- // TODO: Update dead block elimination and enable for try/catch.
- RemoveDeadBlocks();
- }
+ RemoveDeadBlocks();
SsaRedundantPhiElimination(graph_).Run();
RemoveDeadInstructions();
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 68fb0ac..4d79b55 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -366,7 +366,11 @@
HBasicBlock* first_predecessor = block->GetPredecessors()[0];
DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
- if (try_entry != nullptr) {
+ if (try_entry != nullptr &&
+ (block->GetTryCatchInformation() == nullptr ||
+ try_entry != &block->GetTryCatchInformation()->GetTryEntry())) {
+ // We are either setting try block membership for the first time or it
+ // has changed.
block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry));
}
}
@@ -1372,13 +1376,30 @@
// instructions.
for (HBasicBlock* predecessor : predecessors_) {
HInstruction* last_instruction = predecessor->GetLastInstruction();
+ if (last_instruction->IsTryBoundary() && !IsCatchBlock()) {
+ // This block is the only normal-flow successor of the TryBoundary which
+ // makes `predecessor` dead. Since DCE removes blocks in post order,
+ // exception handlers of this TryBoundary were already visited and any
+ // remaining handlers therefore must be live. We remove `predecessor` from
+ // their list of predecessors.
+ DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this);
+ while (predecessor->GetSuccessors().size() > 1) {
+ HBasicBlock* handler = predecessor->GetSuccessors()[1];
+ DCHECK(handler->IsCatchBlock());
+ predecessor->RemoveSuccessor(handler);
+ handler->RemovePredecessor(predecessor);
+ }
+ }
+
predecessor->RemoveSuccessor(this);
uint32_t num_pred_successors = predecessor->GetSuccessors().size();
if (num_pred_successors == 1u) {
// If we have one successor after removing one, then we must have
- // had an HIf or HPackedSwitch, as they have more than one successor.
- // Replace those with a HGoto.
- DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
+ // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one
+ // successor. Replace those with a HGoto.
+ DCHECK(last_instruction->IsIf() ||
+ last_instruction->IsPackedSwitch() ||
+ (last_instruction->IsTryBoundary() && IsCatchBlock()));
predecessor->RemoveInstruction(last_instruction);
predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
} else if (num_pred_successors == 0u) {
@@ -1387,10 +1408,12 @@
// SSAChecker fails unless it is not removed during the pass too.
predecessor->RemoveInstruction(last_instruction);
} else {
- // There are multiple successors left. This must come from a HPackedSwitch
- // and we are in the middle of removing the HPackedSwitch. Like above, leave
- // this alone, and the SSAChecker will fail if it is not removed as well.
- DCHECK(last_instruction->IsPackedSwitch());
+ // There are multiple successors left. The removed block might be a successor
+ // of a PackedSwitch which will be completely removed (perhaps replaced with
+ // a Goto), or we are deleting a catch block from a TryBoundary. In either
+ // case, leave `last_instruction` as is for now.
+ DCHECK(last_instruction->IsPackedSwitch() ||
+ (last_instruction->IsTryBoundary() && IsCatchBlock()));
}
}
predecessors_.clear();
diff --git a/test/543-checker-dce-trycatch/expected.txt b/test/543-checker-dce-trycatch/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/543-checker-dce-trycatch/expected.txt
diff --git a/test/543-checker-dce-trycatch/info.txt b/test/543-checker-dce-trycatch/info.txt
new file mode 100644
index 0000000..e541938
--- /dev/null
+++ b/test/543-checker-dce-trycatch/info.txt
@@ -0,0 +1 @@
+Tests removal of try/catch blocks by DCE.
\ No newline at end of file
diff --git a/test/543-checker-dce-trycatch/smali/TestCase.smali b/test/543-checker-dce-trycatch/smali/TestCase.smali
new file mode 100644
index 0000000..3e71937
--- /dev/null
+++ b/test/543-checker-dce-trycatch/smali/TestCase.smali
@@ -0,0 +1,200 @@
+# Copyright (C) 2015 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 LTestCase;
+.super Ljava/lang/Object;
+
+.method private static $inline$False()Z
+ .registers 1
+ const/4 v0, 0x0
+ return v0
+.end method
+
+# Test a case when one entering TryBoundary is dead but the rest of the try
+# block remains live.
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: Add
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: TryBoundary kind:entry
+## CHECK: TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (after)
+## CHECK-NOT: Add
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (after)
+## CHECK: TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+.method public static testDeadEntry(IIII)I
+ .registers 5
+
+ invoke-static {}, LTestCase;->$inline$False()Z
+ move-result v0
+
+ if-eqz v0, :else
+
+ add-int/2addr p0, p1
+
+ :try_start
+ div-int/2addr p0, p2
+
+ :else
+ div-int/2addr p0, p3
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :return
+ return p0
+
+ :catch_all
+ const/4 p0, -0x1
+ goto :return
+
+.end method
+
+# Test a case when one exiting TryBoundary is dead but the rest of the try
+# block remains live.
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: Add
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: TryBoundary kind:exit
+## CHECK: TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (after)
+## CHECK-NOT: Add
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (after)
+## CHECK: TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+.method public static testDeadExit(IIII)I
+ .registers 5
+
+ invoke-static {}, LTestCase;->$inline$False()Z
+ move-result v0
+
+ :try_start
+ div-int/2addr p0, p2
+
+ if-nez v0, :else
+
+ div-int/2addr p0, p3
+ goto :return
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :else
+ add-int/2addr p0, p1
+
+ :return
+ return p0
+
+ :catch_all
+ const/4 p0, -0x1
+ goto :return
+
+.end method
+
+# Test that a catch block remains live and consistent if some of try blocks
+# throwing into it are removed.
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: TryBoundary kind:entry
+## CHECK: TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: TryBoundary kind:exit
+## CHECK: TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (after)
+## CHECK: TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (after)
+## CHECK: TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+.method public static testOneTryBlockDead(IIII)I
+ .registers 5
+
+ invoke-static {}, LTestCase;->$inline$False()Z
+ move-result v0
+
+ :try_start_1
+ div-int/2addr p0, p2
+ :try_end_1
+ .catchall {:try_start_1 .. :try_end_1} :catch_all
+
+ if-eqz v0, :return
+
+ :try_start_2
+ div-int/2addr p0, p3
+ :try_end_2
+ .catchall {:try_start_2 .. :try_end_2} :catch_all
+
+ :return
+ return p0
+
+ :catch_all
+ const/4 p0, -0x1
+ goto :return
+
+.end method
+
+# Test that try block membership is recomputed. In this test case, the try entry
+# stored with the merge block gets deleted and SSAChecker would fail if it was
+# not replaced with the try entry from the live branch.
+
+.method public static testRecomputeTryMembership(IIII)I
+ .registers 5
+
+ invoke-static {}, LTestCase;->$inline$False()Z
+ move-result v0
+
+ if-eqz v0, :else
+
+ # Dead branch
+ :try_start
+ div-int/2addr p0, p1
+ goto :merge
+
+ # Live branch
+ :else
+ div-int/2addr p0, p2
+
+ # Merge block. Make complex so it does not get merged with the live branch.
+ :merge
+ div-int/2addr p0, p3
+ if-eqz p0, :else2
+ div-int/2addr p0, p3
+ :else2
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :return
+ return p0
+
+ :catch_all
+ const/4 p0, -0x1
+ goto :return
+
+.end method
diff --git a/test/543-checker-dce-trycatch/src/Main.java b/test/543-checker-dce-trycatch/src/Main.java
new file mode 100644
index 0000000..6e73d0d
--- /dev/null
+++ b/test/543-checker-dce-trycatch/src/Main.java
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2015 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 {
+
+ // Workaround for b/18051191.
+ class InnerClass {}
+
+ static boolean $inline$False() { return false; }
+
+ // DCE should only merge blocks where the first ends with a Goto.
+ // SSAChecker will fail if the following Throw->TryBoundary blocks are merged.
+ public static void doNotMergeThrow(String str) {
+ try {
+ throw new Exception(str);
+ } catch (Exception ex) {
+ return;
+ }
+ }
+
+ // Test deletion of all try/catch blocks. Multiple catch blocks test deletion
+ // where TryBoundary still has exception handler successors after having removed
+ // some already.
+
+ /// CHECK-START: void Main.testDeadTryCatch(boolean) dead_code_elimination_final (after)
+ /// CHECK-NOT: TryBoundary
+
+ /// CHECK-START: void Main.testDeadTryCatch(boolean) dead_code_elimination_final (after)
+ /// CHECK: begin_block
+ /// CHECK: begin_block
+ /// CHECK: begin_block
+ /// CHECK-NOT: begin_block
+
+ public static void testDeadTryCatch(boolean val) {
+ if ($inline$False()) {
+ try {
+ if (val) {
+ throw new ArithmeticException();
+ } else {
+ throw new ArrayIndexOutOfBoundsException();
+ }
+ } catch (ArithmeticException ex) {
+ System.out.println("Unexpected AE catch");
+ } catch (ArrayIndexOutOfBoundsException ex) {
+ System.out.println("Unexpected AIIOB catch");
+ }
+ }
+ }
+
+ public static void main(String[] args) {
+
+ }
+}
\ No newline at end of file
