Correctly delete all uses when building up the domination graph
We now consider the edge case where the dead instruction we wanted to
remove was used in a phi which is not directly following the block
we are processing right now. To fix this, we process all blocks
before trying to remove the instructions.
As a note, we remove catch phi uses right before removing the
instruction as they are related to the instruction itself and not
the block hierarchy.
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Test: dex2oat compiling locally the apps mentioned in the bug
Bug: 239519319
Change-Id: I70d47891203ae118851a1f20a7cee21de305cd61
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index cb07d2e..19731ae 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -150,17 +150,22 @@
RemoveEnvironmentUses(instruction);
}
-void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const {
+void HGraph::RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVector& visited) const {
for (size_t i = 0; i < blocks_.size(); ++i) {
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_[i];
if (block == nullptr) continue;
+
+ // Remove as user.
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
RemoveAsUser(it.Current());
}
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
RemoveAsUser(it.Current());
}
+
+ // Remove non-catch phi uses, and disconnect the block.
+ block->DisconnectFromSuccessors(&visited);
}
}
}
@@ -175,7 +180,8 @@
const HUseListNode<HInstruction*>& use = insn->GetUses().front();
size_t use_index = use.GetIndex();
HBasicBlock* user_block = use.GetUser()->GetBlock();
- DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock());
+ DCHECK(use.GetUser()->IsPhi());
+ DCHECK(user_block->IsCatchBlock());
for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
}
@@ -189,8 +195,7 @@
HBasicBlock* block = blocks_[i];
if (block == nullptr) continue;
- // Disconnect from its sucessors, and remove all remaining uses.
- block->DisconnectFromSuccessors(&visited);
+ // Remove all remaining uses (which should be only catch phi uses), and the instructions.
block->RemoveCatchPhiUsesAndInstruction(/* building_dominator_tree = */ true);
// Remove the block from the list of blocks, so that further analyses
@@ -219,7 +224,8 @@
// (2) Remove instructions and phis from blocks not visited during
// the initial DFS as users from other instructions, so that
// users can be safely removed before uses later.
- RemoveInstructionsAsUsersFromDeadBlocks(visited);
+ // Also disconnect the block from its successors, updating the successor's phis if needed.
+ RemoveDeadBlocksInstructionsAsUsersAndDisconnect(visited);
// (3) Remove blocks not visited during the initial DFS.
// Step (5) requires dead blocks to be removed from the
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 98bcd38..8db8c02 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -735,7 +735,7 @@
void IncrementNumberOfCHAGuards() { number_of_cha_guards_++; }
private:
- void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
+ void RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVector& visited) const;
void RemoveDeadBlocks(const ArenaBitVector& visited);
template <class InstructionType, typename ValueType>
diff --git a/test/2042-checker-dce-always-throw/src/Main.java b/test/2042-checker-dce-always-throw/src/Main.java
index bc2e7a1..1aa10a0 100644
--- a/test/2042-checker-dce-always-throw/src/Main.java
+++ b/test/2042-checker-dce-always-throw/src/Main.java
@@ -31,7 +31,8 @@
// Test that we update the phis correctly after simplifying an always throwing method, and
// recomputing dominance.
- assertEquals(0, $noinline$UpdatePhisCorrectly(1, 1));
+ assertEquals(0, $noinline$testUpdatePhisCorrectly(1, 1));
+ assertEquals(0, $noinline$testDeleteAllUsesBeforeDeletingInstruction(1, 1));
}
private static void alwaysThrows() throws Error {
@@ -298,7 +299,7 @@
// Check that when we perform SimplifyAlwaysThrows, that the phi for `phi_value` exists, and that
// we correctly update it after running DCE.
- /// CHECK-START: int Main.$noinline$UpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (before)
+ /// CHECK-START: int Main.$noinline$testUpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (before)
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
/// CHECK-DAG: <<Const5:i\d+>> IntConstant 5
/// CHECK-DAG: <<ReturnValue:i\d+>> Phi [<<Const0>>,<<Const5>>]
@@ -308,16 +309,16 @@
/// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
/// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
- /// CHECK-START: int Main.$noinline$UpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (after)
+ /// CHECK-START: int Main.$noinline$testUpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (after)
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
/// CHECK-DAG: Return [<<Const0>>]
/// 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>>
- /// CHECK-START: int Main.$noinline$UpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (after)
+ /// CHECK-START: int Main.$noinline$testUpdatePhisCorrectly(int, int) dead_code_elimination$after_inlining (after)
/// CHECK-NOT: Phi
- private static int $noinline$UpdatePhisCorrectly(int num, int other_num) {
+ private static int $noinline$testUpdatePhisCorrectly(int num, int other_num) {
int phi_value = 0;
if (num == 0) {
alwaysThrows();
@@ -335,6 +336,53 @@
return phi_value;
}
+
+ // Test to check that we delete all uses before the instruction.
+ private static int $noinline$foo(int num) {
+ return num;
+ }
+
+ /// CHECK-START: int Main.$noinline$testDeleteAllUsesBeforeDeletingInstruction(int, int) dead_code_elimination$after_inlining (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Invoke:i\d+>> InvokeStaticOrDirect method_name:Main.$noinline$foo
+ /// CHECK-DAG: <<ReturnValue:i\d+>> Phi [<<Const0>>,<<Invoke>>]
+ /// CHECK-DAG: Return [<<ReturnValue>>]
+ /// 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$testDeleteAllUsesBeforeDeletingInstruction(int, int) dead_code_elimination$after_inlining (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: Return [<<Const0>>]
+ /// 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>>
+
+ /// CHECK-START: int Main.$noinline$testDeleteAllUsesBeforeDeletingInstruction(int, int) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: Phi
+ private static int $noinline$testDeleteAllUsesBeforeDeletingInstruction(int num, int other_num) {
+ int phi_value = 0;
+ if (num == 0) {
+ alwaysThrows();
+
+ // This while loop is here so that we have a Goto after `alwaysThrows` and therefore perform
+ // the `SimplifyAlwaysThrows` optimization. We use `other_num` here because otherwise we
+ // propagate the knowledge that `num` equals zero.
+ while (other_num == 0) {
+ // Assign to phi_value so that the loop is not empty.
+ phi_value = 2;
+ }
+
+ try {
+ phi_value = $noinline$foo(2);
+ } catch (Error e) {
+ throw new Error("We shouldn't hit this");
+ }
+ }
+ return phi_value;
+ }
+
static void assertEquals(int expected, int actual) {
if (expected != actual) {
throw new AssertionError("Expected " + expected + " got " + actual);