From 9eeebf646b118269b3f5bd6fc6c1b0a58c26c6d4 Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Thu, 24 Mar 2016 11:18:15 +0000 Subject: [PATCH] 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 --- compiler/optimizing/nodes.cc | 135 ++++++++++++--------- test/591-checker-regression-dead-loop/expected.txt | 0 test/591-checker-regression-dead-loop/info.txt | 2 + .../591-checker-regression-dead-loop/src/Main.java | 35 ++++++ 4 files changed, 116 insertions(+), 56 deletions(-) create mode 100644 test/591-checker-regression-dead-loop/expected.txt create mode 100644 test/591-checker-regression-dead-loop/info.txt create mode 100644 test/591-checker-regression-dead-loop/src/Main.java diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index e08e8fb7b..fcc7076e3 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1654,21 +1654,77 @@ void HBasicBlock::DisconnectAndDelete() { // 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(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId()); + loop_update_start = loop_info->GetPreHeader(); + } + + // (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); + } - // (2) Disconnect the block from its predecessors and update their + // (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 @@ void HBasicBlock::DisconnectAndDelete() { } 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 000000000..e69de29bb 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 000000000..f192b8d1a --- /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 000000000..6d9fcf8e6 --- /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: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK-DAG: <> Phi [<>,<>] loop:{{B\d+}} + /// CHECK-DAG: InvokeVirtual [{{l\d+}},<>] method_name:java.io.PrintStream.println + /// CHECK-DAG: <> Add [<>,<>] + + public static void main(String[] args) { + if ($inline$false()) { + int x = 0; + while (true) { + System.out.println(x++); + } + } + } +} -- 2.11.0