Update the successor's Phis in RemoveDeadBlocks
When we remove a dead block, we update its successor's phis (as long
as the successor is still reachable). We can reuse code from
DisconnectAndDelete if we refactor it a little bit.
Bug: 240546614
Fixes: 240546614
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I70c509bd1c9e392118bbf95c7aaac64faa46237f
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ba6d1a7..6ac4e07 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -165,15 +165,33 @@
}
}
+// This method assumes `insn` has been removed from all users with the exception of catch
+// phis because of missing exceptional edges in the graph. It removes the
+// instruction from catch phi uses, together with inputs of other catch phis in
+// the catch block at the same index, as these must be dead too.
+static void RemoveCatchPhiUsesOfDeadInstruction(HInstruction* insn) {
+ DCHECK(!insn->HasEnvironmentUses());
+ while (insn->HasNonEnvironmentUses()) {
+ 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());
+ for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
+ }
+ }
+}
+
void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
for (size_t i = 0; i < blocks_.size(); ++i) {
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_[i];
if (block == nullptr) continue;
- // We only need to update the successor, which might be live.
- for (HBasicBlock* successor : block->GetSuccessors()) {
- successor->RemovePredecessor(block);
- }
+
+ // Disconnect from its sucessors, and remove all remaining uses.
+ block->DisconnectFromSuccessors(&visited);
+ block->RemoveCatchPhiUses(/* remove_instruction = */ false);
+
// Remove the block from the list of blocks, so that further analyses
// never see it.
blocks_[i] = nullptr;
@@ -2377,24 +2395,6 @@
}
}
-// Should be called on instructions in a dead block in post order. This method
-// assumes `insn` has been removed from all users with the exception of catch
-// phis because of missing exceptional edges in the graph. It removes the
-// instruction from catch phi uses, together with inputs of other catch phis in
-// the catch block at the same index, as these must be dead too.
-static void RemoveUsesOfDeadInstruction(HInstruction* insn) {
- DCHECK(!insn->HasEnvironmentUses());
- while (insn->HasNonEnvironmentUses()) {
- 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());
- for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
- phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
- }
- }
-}
-
void HBasicBlock::DisconnectAndDelete() {
// Dominators must be removed after all the blocks they dominate. This way
// a loop header is removed last, a requirement for correct loop information
@@ -2419,52 +2419,14 @@
}
// (2) Disconnect the block from its successors and update their phis.
- for (HBasicBlock* successor : successors_) {
- // Delete this block from the list of predecessors.
- size_t this_index = successor->GetPredecessorIndexOf(this);
- successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
-
- // Check that `successor` has other predecessors, otherwise `this` is the
- // dominator of `successor` which violates the order DCHECKed at the top.
- DCHECK(!successor->predecessors_.empty());
-
- // Remove this block's entries in the successor's phis. Skip exceptional
- // successors because catch phi inputs do not correspond to predecessor
- // blocks but throwing instructions. The inputs of the catch phis will be
- // updated in step (3).
- if (!successor->IsCatchBlock()) {
- if (successor->predecessors_.size() == 1u) {
- // The successor has just one predecessor left. Replace phis with the only
- // remaining input.
- for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
- HPhi* phi = phi_it.Current()->AsPhi();
- phi->ReplaceWith(phi->InputAt(1 - this_index));
- successor->RemovePhi(phi);
- }
- } else {
- for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
- phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
- }
- }
- }
- }
- successors_.clear();
+ DisconnectFromSuccessors();
// (3) Remove instructions and phis. Instructions should have no remaining uses
// except in catch phis. If an instruction is used by a catch phi at `index`,
// remove `index`-th input of all phis in the catch block since they are
// guaranteed dead. Note that we may miss dead inputs this way but the
// graph will always remain consistent.
- for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
- HInstruction* insn = it.Current();
- RemoveUsesOfDeadInstruction(insn);
- RemoveInstruction(insn);
- }
- for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
- HPhi* insn = it.Current()->AsPhi();
- RemoveUsesOfDeadInstruction(insn);
- RemovePhi(insn);
- }
+ RemoveCatchPhiUses(/* remove_instruction = */ true);
// (4) Disconnect the block from its predecessors and update their
// control-flow instructions.
@@ -2538,6 +2500,58 @@
SetGraph(nullptr);
}
+void HBasicBlock::DisconnectFromSuccessors(const ArenaBitVector* visited) {
+ for (HBasicBlock* successor : successors_) {
+ // Delete this block from the list of predecessors.
+ size_t this_index = successor->GetPredecessorIndexOf(this);
+ successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
+
+ if (visited != nullptr && !visited->IsBitSet(successor->GetBlockId())) {
+ // `successor` itself is dead. Therefore, there is no need to update its phis.
+ continue;
+ }
+
+ DCHECK(!successor->predecessors_.empty());
+
+ // Remove this block's entries in the successor's phis. Skips exceptional
+ // successors because catch phi inputs do not correspond to predecessor
+ // blocks but throwing instructions. They are removed in `RemoveCatchPhiUses`.
+ if (!successor->IsCatchBlock()) {
+ if (successor->predecessors_.size() == 1u) {
+ // The successor has just one predecessor left. Replace phis with the only
+ // remaining input.
+ for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ HPhi* phi = phi_it.Current()->AsPhi();
+ phi->ReplaceWith(phi->InputAt(1 - this_index));
+ successor->RemovePhi(phi);
+ }
+ } else {
+ for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
+ }
+ }
+ }
+ }
+ successors_.clear();
+}
+
+void HBasicBlock::RemoveCatchPhiUses(bool remove_instruction) {
+ for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* insn = it.Current();
+ RemoveCatchPhiUsesOfDeadInstruction(insn);
+ if (remove_instruction) {
+ RemoveInstruction(insn);
+ }
+ }
+ for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* insn = it.Current()->AsPhi();
+ RemoveCatchPhiUsesOfDeadInstruction(insn);
+ if (remove_instruction) {
+ RemovePhi(insn);
+ }
+ }
+}
+
void HBasicBlock::MergeInstructionsWith(HBasicBlock* other) {
DCHECK(EndsWithControlFlowInstruction());
RemoveInstruction(GetLastInstruction());
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index a1a6747..1ceb8f1 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1346,6 +1346,17 @@
// are safely updated.
void DisconnectAndDelete();
+ // Disconnects `this` from all its successors and updates their phis, if the successors have them.
+ // If `visited` is provided, it will use the information to know if a successor is reachable and
+ // skip updating those phis.
+ void DisconnectFromSuccessors(const ArenaBitVector* visited = nullptr);
+
+ // Removes the catch phi uses of the instructions in `this`. If `remove_instruction` is set to
+ // true, it will also remove the instructions themselves. This method assumes the instructions
+ // have been removed from all users with the exception of catch phis because of missing
+ // exceptional edges in the graph.
+ void RemoveCatchPhiUses(bool remove_instruction);
+
void AddInstruction(HInstruction* instruction);
// Insert `instruction` before/after an existing instruction `cursor`.
void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
diff --git a/test/2042-checker-dce-always-throw/src/Main.java b/test/2042-checker-dce-always-throw/src/Main.java
index 097c9e0..b601f20 100644
--- a/test/2042-checker-dce-always-throw/src/Main.java
+++ b/test/2042-checker-dce-always-throw/src/Main.java
@@ -28,6 +28,10 @@
assertEquals(0, $noinline$testDoNotSimplifyInTry(1));
assertEquals(0, $noinline$testSimplifyInCatch(1));
assertEquals(0, $noinline$testDoNotSimplifyInCatchInOuterTry(1));
+
+ // Test that we update the phis correctly after simplifying an always throwing method, and
+ // recomputing dominance.
+ assertEquals(0, $noinline$UpdatePhisCorrectly(1));
}
private static void alwaysThrows() throws Error {
@@ -289,6 +293,45 @@
}
}
+ // 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) 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>>]
+ /// 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$UpdatePhisCorrectly(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) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: Phi
+ private static int $noinline$UpdatePhisCorrectly(int num) {
+ int phi_value = 0;
+ if (num == 0) {
+ alwaysThrows();
+
+ // This while loop is here so that the `if (num == 0)` will be several blocks instead of
+ // just one.
+ while (num == 0) {
+ // Assign to phi_value so that the loop is not empty.
+ phi_value = 2;
+ }
+
+ phi_value = 5;
+ }
+ return phi_value;
+ }
+
static void assertEquals(int expected, int actual) {
if (expected != actual) {
throw new AssertionError("Expected " + expected + " got " + actual);