ART: Fix order of operations in HBasicBlock::DisconnectAndDelete
The method would remove predecessors before successors. As a result,
instructions used by dead loop phis would see dangling uses, causing
a DCHECK to fail.
Steps were reordered to remove dependencies in post order.
Bug: 27683071
Change-Id: I8e0e976443fb410908321a065276f1340b757c41
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index e08e8fb..fcc7076 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1654,21 +1654,77 @@
// iteration.
DCHECK(dominated_blocks_.empty());
- // (1) Remove the block from all loops it is included in.
- for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) {
- HLoopInformation* loop_info = it.Current();
- loop_info->Remove(this);
- if (loop_info->IsBackEdge(*this)) {
- // If this was the last back edge of the loop, we deliberately leave the
- // loop in an inconsistent state and will fail GraphChecker unless the
- // entire loop is removed during the pass.
- loop_info->RemoveBackEdge(this);
- }
+ // The following steps gradually remove the block from all its dependants in
+ // post order (b/27683071).
+
+ // (1) Store a basic block that we'll use in step (5) to find loops to be updated.
+ // We need to do this before step (4) which destroys the predecessor list.
+ HBasicBlock* loop_update_start = this;
+ if (IsLoopHeader()) {
+ HLoopInformation* loop_info = GetLoopInformation();
+ // All other blocks in this loop should have been removed because the header
+ // was their dominator.
+ // Note that we do not remove `this` from `loop_info` as it is unreachable.
+ DCHECK(!loop_info->IsIrreducible());
+ DCHECK_EQ(loop_info->GetBlocks().NumSetBits(), 1u);
+ DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId());
+ loop_update_start = loop_info->GetPreHeader();
}
- // (2) Disconnect the block from its predecessors and update their
+ // (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();
+
+ // (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);
+ }
+
+ // (4) Disconnect the block from its predecessors and update their
// control-flow instructions.
for (HBasicBlock* predecessor : predecessors_) {
+ // We should not see any back edges as they would have been removed by step (3).
+ DCHECK(!IsInLoop() || !GetLoopInformation()->IsBackEdge(*predecessor));
+
HInstruction* last_instruction = predecessor->GetLastInstruction();
if (last_instruction->IsTryBoundary() && !IsCatchBlock()) {
// This block is the only normal-flow successor of the TryBoundary which
@@ -1712,58 +1768,25 @@
}
predecessors_.clear();
- // (3) 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. Their inputs will be updated in step (4).
- 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);
- }
- }
+ // (5) Remove the block from all loops it is included in. Skip the inner-most
+ // loop if this is the loop header (see definition of `loop_update_start`)
+ // because the loop header's predecessor list has been destroyed in step (4).
+ for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) {
+ HLoopInformation* loop_info = it.Current();
+ loop_info->Remove(this);
+ if (loop_info->IsBackEdge(*this)) {
+ // If this was the last back edge of the loop, we deliberately leave the
+ // loop in an inconsistent state and will fail GraphChecker unless the
+ // entire loop is removed during the pass.
+ loop_info->RemoveBackEdge(this);
}
}
- successors_.clear();
- // (4) 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);
- }
-
- // Disconnect from the dominator.
+ // (6) Disconnect from the dominator.
dominator_->RemoveDominatedBlock(this);
SetDominator(nullptr);
- // Delete from the graph, update reverse post order.
+ // (7) Delete from the graph, update reverse post order.
graph_->DeleteDeadEmptyBlock(this);
SetGraph(nullptr);
}
diff --git a/test/591-checker-regression-dead-loop/expected.txt b/test/591-checker-regression-dead-loop/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/591-checker-regression-dead-loop/expected.txt
diff --git a/test/591-checker-regression-dead-loop/info.txt b/test/591-checker-regression-dead-loop/info.txt
new file mode 100644
index 0000000..f192b8d
--- /dev/null
+++ b/test/591-checker-regression-dead-loop/info.txt
@@ -0,0 +1,2 @@
+Regression test for Optimizing's dead block elimination which used to remove
+dependencies in the wrong order.
\ No newline at end of file
diff --git a/test/591-checker-regression-dead-loop/src/Main.java b/test/591-checker-regression-dead-loop/src/Main.java
new file mode 100644
index 0000000..6d9fcf8
--- /dev/null
+++ b/test/591-checker-regression-dead-loop/src/Main.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2016 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 Main {
+ private static boolean $inline$false() { return false; }
+
+ /// CHECK-START: void Main.main(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,<<Add:i\d+>>] loop:{{B\d+}}
+ /// CHECK-DAG: InvokeVirtual [{{l\d+}},<<Phi>>] method_name:java.io.PrintStream.println
+ /// CHECK-DAG: <<Add>> Add [<<Phi>>,<<Const1>>]
+
+ public static void main(String[] args) {
+ if ($inline$false()) {
+ int x = 0;
+ while (true) {
+ System.out.println(x++);
+ }
+ }
+ }
+}
