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);
}