From f776b92a0d52bb522043812dacb9c21ac11858e2 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Wed, 15 Apr 2015 18:22:45 +0100 Subject: [PATCH] Remove dead blocks for the blocks_ array. This prevents crashing because of structurally incorrect blocks. Also we now don't need to remove its instructions. Test case courtesy of Serguei I Katkov. Change-Id: Ia3ef9580549fc3546e8cd5f346079b1f0ceb2a61 --- compiler/optimizing/dominator_test.cc | 8 +++++- compiler/optimizing/nodes.cc | 22 ++++++++--------- compiler/optimizing/nodes.h | 2 +- test/473-remove-dead-block/expected.txt | 1 + test/473-remove-dead-block/info.txt | 3 +++ test/473-remove-dead-block/src/Main.java | 42 ++++++++++++++++++++++++++++++++ 6 files changed, 64 insertions(+), 14 deletions(-) create mode 100644 test/473-remove-dead-block/expected.txt create mode 100644 test/473-remove-dead-block/info.txt create mode 100644 test/473-remove-dead-block/src/Main.java diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc index 7623e421f..61a769730 100644 --- a/compiler/optimizing/dominator_test.cc +++ b/compiler/optimizing/dominator_test.cc @@ -36,7 +36,13 @@ static void TestCode(const uint16_t* data, const int* blocks, size_t blocks_leng ASSERT_EQ(graph->GetBlocks().Size(), blocks_length); for (size_t i = 0, e = blocks_length; i < e; ++i) { if (blocks[i] == -1) { - ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator()); + if (graph->GetBlocks().Get(i) == nullptr) { + // Dead block. + } else { + // Only the entry block has no dominator. + ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator()); + ASSERT_TRUE(graph->GetBlocks().Get(i)->IsEntryBlock()); + } } else { ASSERT_NE(nullptr, graph->GetBlocks().Get(i)->GetDominator()); ASSERT_EQ(blocks[i], graph->GetBlocks().Get(i)->GetDominator()->GetBlockId()); diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index d8a855461..ada348796 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -51,9 +51,7 @@ void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visit for (size_t i = 0; i < blocks_.Size(); ++i) { if (!visited.IsBitSet(i)) { HBasicBlock* block = blocks_.Get(i); - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - RemoveAsUser(it.Current()); - } + DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage"; for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { RemoveAsUser(it.Current()); } @@ -61,19 +59,17 @@ void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visit } } -void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { +void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { for (size_t i = 0; i < blocks_.Size(); ++i) { if (!visited.IsBitSet(i)) { HBasicBlock* block = blocks_.Get(i); + // We only need to update the successor, which might be live. for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { block->GetSuccessors().Get(j)->RemovePredecessor(block); } - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false); - } - for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { - block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false); - } + // Remove the block from the list of blocks, so that further analyses + // never see it. + blocks_.Put(i, nullptr); } } } @@ -258,6 +254,7 @@ void HGraph::SimplifyCFG() { // (2): Simplify loops by having only one back edge, and one preheader. for (size_t i = 0; i < blocks_.Size(); ++i) { HBasicBlock* block = blocks_.Get(i); + if (block == nullptr) continue; if (block->GetSuccessors().Size() > 1) { for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { HBasicBlock* successor = block->GetSuccessors().Get(j); @@ -274,8 +271,9 @@ void HGraph::SimplifyCFG() { } bool HGraph::AnalyzeNaturalLoops() const { - for (size_t i = 0; i < blocks_.Size(); ++i) { - HBasicBlock* block = blocks_.Get(i); + // Order does not matter. + for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); if (block->IsLoopHeader()) { HLoopInformation* info = block->GetLoopInformation(); if (!info->Populate()) { diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 539e0b5de..4bca9aaf8 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -253,7 +253,7 @@ class HGraph : public ArenaObject { ArenaBitVector* visited, ArenaBitVector* visiting); void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; - void RemoveDeadBlocks(const ArenaBitVector& visited) const; + void RemoveDeadBlocks(const ArenaBitVector& visited); template InstType* CreateConstant(ValueType value, ArenaSafeMap* cache); diff --git a/test/473-remove-dead-block/expected.txt b/test/473-remove-dead-block/expected.txt new file mode 100644 index 000000000..c09201e9d --- /dev/null +++ b/test/473-remove-dead-block/expected.txt @@ -0,0 +1 @@ +123368133 diff --git a/test/473-remove-dead-block/info.txt b/test/473-remove-dead-block/info.txt new file mode 100644 index 000000000..81de4e6f6 --- /dev/null +++ b/test/473-remove-dead-block/info.txt @@ -0,0 +1,3 @@ +Regression test for optimizing's dead block removing: +Removing from predecessors require remove successor otherwise +CFG remains in an unexpected shape causing further crash of compiler. diff --git a/test/473-remove-dead-block/src/Main.java b/test/473-remove-dead-block/src/Main.java new file mode 100644 index 000000000..cca2976e8 --- /dev/null +++ b/test/473-remove-dead-block/src/Main.java @@ -0,0 +1,42 @@ +/* + * Copyright (C) 2015 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 { + public static void main(String[] args) { + System.out.println(test(false, 5)); + } + + public static int test(boolean b, int i1) { + int j=4; + int s1=26294; + + for (int i = 25; i > 1; --i) { + if (b) continue; + // javac/dx will remove the catch information, but + // keep the catch code around. The optimizing compiler + // used to crash in the presence of dead blocks like the + // code in catch. + try { + i1 = i1 * 26295 + (s1 / 26295); + } catch (Throwable exc2) { + for (j = 1; j < 39; ++j) { + j++; + } + } + } + return i1; + } +} -- 2.11.0