From db51efb3617d15f1cd9e5ff0cc2d934777014e9a Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Fri, 6 Nov 2015 01:36:20 +0000 Subject: [PATCH] ART: Fix critical edge splitting under try/catch A critical edge would not be split if the predecessor ends with TryBoundary. This would eventually trip liveness analysis because a back edge block would have smaller liveness position than a nested loop. Another implication of this change is that an edge between a loop's pre-header ending with TryBoundary and the header will be split, guaranteeing that a pre-header always has just one successor. Bug: 25493695 Bug: 25454012 Change-Id: I5a13b8bb74509b48f5d628906f7158af007f99ae --- compiler/optimizing/graph_checker.cc | 17 ++++++- compiler/optimizing/induction_var_analysis_test.cc | 7 ++- compiler/optimizing/induction_var_range_test.cc | 8 ++- compiler/optimizing/licm_test.cc | 6 ++- compiler/optimizing/nodes.cc | 18 +++++-- .../expected.txt | 0 .../547-regression-trycatch-critical-edge/info.txt | 2 + .../smali/TestCase.smali | 57 ++++++++++++++++++++++ .../src/Main.java | 24 +++++++++ 9 files changed, 128 insertions(+), 11 deletions(-) create mode 100644 test/547-regression-trycatch-critical-edge/expected.txt create mode 100644 test/547-regression-trycatch-critical-edge/info.txt create mode 100644 test/547-regression-trycatch-critical-edge/smali/TestCase.smali create mode 100644 test/547-regression-trycatch-critical-edge/src/Main.java diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index c32ef5198..f77576db6 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -460,12 +460,18 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { int id = loop_header->GetBlockId(); HLoopInformation* loop_information = loop_header->GetLoopInformation(); - // Ensure the pre-header block is first in the list of - // predecessors of a loop header. + // Ensure the pre-header block is first in the list of predecessors of a loop + // header and that the header block is its only successor. if (!loop_header->IsLoopPreHeaderFirstPredecessor()) { AddError(StringPrintf( "Loop pre-header is not the first predecessor of the loop header %d.", id)); + } else if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) { + AddError(StringPrintf( + "Loop pre-header %d of loop defined by header %d has %zu successors.", + loop_information->GetPreHeader()->GetBlockId(), + id, + loop_information->GetPreHeader()->GetSuccessors().size())); } // Ensure the loop header has only one incoming branch and the remaining @@ -508,6 +514,13 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { "Loop defined by header %d has an invalid back edge %d.", id, back_edge_id)); + } else if (back_edge->GetLoopInformation() != loop_information) { + AddError(StringPrintf( + "Back edge %d of loop defined by header %d belongs to nested loop " + "with header %d.", + back_edge_id, + id, + back_edge->GetLoopInformation()->GetHeader()->GetBlockId())); } } } diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index b7262f6b2..5de94f43c 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -69,10 +69,13 @@ class InductionVarAnalysisTest : public testing::Test { entry_ = new (&allocator_) HBasicBlock(graph_); graph_->AddBlock(entry_); BuildForLoop(0, n); + return_ = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(return_); exit_ = new (&allocator_) HBasicBlock(graph_); graph_->AddBlock(exit_); entry_->AddSuccessor(loop_preheader_[0]); - loop_header_[0]->AddSuccessor(exit_); + loop_header_[0]->AddSuccessor(return_); + return_->AddSuccessor(exit_); graph_->SetEntryBlock(entry_); graph_->SetExitBlock(exit_); @@ -91,6 +94,7 @@ class InductionVarAnalysisTest : public testing::Test { entry_->AddInstruction(new (&allocator_) HStoreLocal(tmp_, constant100_)); dum_ = new (&allocator_) HLocal(n + 2); entry_->AddInstruction(dum_); + return_->AddInstruction(new (&allocator_) HReturnVoid()); exit_->AddInstruction(new (&allocator_) HExit()); // Provide loop instructions. @@ -177,6 +181,7 @@ class InductionVarAnalysisTest : public testing::Test { // Fixed basic blocks and instructions. HBasicBlock* entry_; + HBasicBlock* return_; HBasicBlock* exit_; HInstruction* parameter_; // "this" HInstruction* constant0_; diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index fda5153d4..c2ba157ed 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -70,11 +70,14 @@ class InductionVarRangeTest : public testing::Test { graph_->AddBlock(loop_header); HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_); graph_->AddBlock(loop_body); + HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(return_block); entry_block_->AddSuccessor(loop_preheader_); loop_preheader_->AddSuccessor(loop_header); loop_header->AddSuccessor(loop_body); - loop_header->AddSuccessor(exit_block_); + loop_header->AddSuccessor(return_block); loop_body->AddSuccessor(loop_header); + return_block->AddSuccessor(exit_block_); // Instructions. HLocal* induc = new (&allocator_) HLocal(0); entry_block_->AddInstruction(induc); @@ -96,7 +99,8 @@ class InductionVarRangeTest : public testing::Test { loop_body->AddInstruction(increment_); loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_)); // i += s loop_body->AddInstruction(new (&allocator_) HGoto()); - exit_block_->AddInstruction(new (&allocator_) HReturnVoid()); + return_block->AddInstruction(new (&allocator_) HReturnVoid()); + exit_block_->AddInstruction(new (&allocator_) HExit()); } /** Performs induction variable analysis. */ diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc index 47457dec7..2bb769a43 100644 --- a/compiler/optimizing/licm_test.cc +++ b/compiler/optimizing/licm_test.cc @@ -42,12 +42,14 @@ class LICMTest : public testing::Test { loop_preheader_ = new (&allocator_) HBasicBlock(graph_); loop_header_ = new (&allocator_) HBasicBlock(graph_); loop_body_ = new (&allocator_) HBasicBlock(graph_); + return_ = new (&allocator_) HBasicBlock(graph_); exit_ = new (&allocator_) HBasicBlock(graph_); graph_->AddBlock(entry_); graph_->AddBlock(loop_preheader_); graph_->AddBlock(loop_header_); graph_->AddBlock(loop_body_); + graph_->AddBlock(return_); graph_->AddBlock(exit_); graph_->SetEntryBlock(entry_); @@ -57,8 +59,9 @@ class LICMTest : public testing::Test { entry_->AddSuccessor(loop_preheader_); loop_preheader_->AddSuccessor(loop_header_); loop_header_->AddSuccessor(loop_body_); - loop_header_->AddSuccessor(exit_); + loop_header_->AddSuccessor(return_); loop_body_->AddSuccessor(loop_header_); + return_->AddSuccessor(exit_); // Provide boiler-plate instructions. parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot); @@ -89,6 +92,7 @@ class LICMTest : public testing::Test { HBasicBlock* loop_preheader_; HBasicBlock* loop_header_; HBasicBlock* loop_body_; + HBasicBlock* return_; HBasicBlock* exit_; HInstruction* parameter_; // "this" diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index af3d8f4a6..3e137ff17 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -383,19 +383,27 @@ void HGraph::ComputeTryBlockInformation() { } void HGraph::SimplifyCFG() { - // Simplify the CFG for future analysis, and code generation: +// Simplify the CFG for future analysis, and code generation: // (1): Split critical edges. - // (2): Simplify loops by having only one back edge, and one preheader. + // (2): Simplify loops by having only one preheader. // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators // can be invalidated. We remember the initial size to avoid iterating over the new blocks. for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) { HBasicBlock* block = blocks_[block_id]; if (block == nullptr) continue; - if (block->NumberOfNormalSuccessors() > 1) { - for (size_t j = 0; j < block->GetSuccessors().size(); ++j) { + if (block->GetSuccessors().size() > 1) { + // Only split normal-flow edges. We cannot split exceptional edges as they + // are synthesized (approximate real control flow), and we do not need to + // anyway. Moves that would be inserted there are performed by the runtime. + for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) { HBasicBlock* successor = block->GetSuccessors()[j]; DCHECK(!successor->IsCatchBlock()); - if (successor->GetPredecessors().size() > 1) { + if (successor == exit_block_) { + // Throw->TryBoundary->Exit. Special case which we do not want to split + // because Goto->Exit is not allowed. + DCHECK(block->IsSingleTryBoundary()); + DCHECK(block->GetSinglePredecessor()->GetLastInstruction()->IsThrow()); + } else if (successor->GetPredecessors().size() > 1) { SplitCriticalEdge(block, successor); --j; } diff --git a/test/547-regression-trycatch-critical-edge/expected.txt b/test/547-regression-trycatch-critical-edge/expected.txt new file mode 100644 index 000000000..e69de29bb diff --git a/test/547-regression-trycatch-critical-edge/info.txt b/test/547-regression-trycatch-critical-edge/info.txt new file mode 100644 index 000000000..dc798c001 --- /dev/null +++ b/test/547-regression-trycatch-critical-edge/info.txt @@ -0,0 +1,2 @@ +Test a specific SSA building regression a back edge would not be split due to +being on try/catch boundary. \ No newline at end of file diff --git a/test/547-regression-trycatch-critical-edge/smali/TestCase.smali b/test/547-regression-trycatch-critical-edge/smali/TestCase.smali new file mode 100644 index 000000000..53a3cc5b6 --- /dev/null +++ b/test/547-regression-trycatch-critical-edge/smali/TestCase.smali @@ -0,0 +1,57 @@ +# 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 public LTestCase; +.super Ljava/lang/Object; + +# The following test case would crash liveness analysis because the back edge of +# the outer loop would have a smaller liveness position than the two back edges +# of the inner loop. This was caused by a bug which did not split the critical +# edge between TryBoundary and outer loop header (b/25493695). + +.method public static testCase(II)I + .registers 10 + + const v0, 0x0 # v0 = result + const v1, 0x1 # v1 = const 1 + + move v2, p0 # v2 = outer loop counter + :outer_loop + if-eqz v2, :return + sub-int/2addr v2, v1 + + :try_start + + move v3, p1 # v3 = inner loop counter + :inner_loop + invoke-static {}, Ljava/lang/System;->nanoTime()J # throwing instruction + if-eqz v3, :outer_loop # back edge of outer loop + sub-int/2addr v3, v1 + + invoke-static {}, Ljava/lang/System;->nanoTime()J # throwing instruction + add-int/2addr v0, v1 + goto :inner_loop # back edge of inner loop + + :try_end + .catchall {:try_start .. :try_end} :catch + + :catch + const v4, 0x2 + add-int/2addr v0, v4 + goto :inner_loop # back edge of inner loop + + :return + return v0 + +.end method diff --git a/test/547-regression-trycatch-critical-edge/src/Main.java b/test/547-regression-trycatch-critical-edge/src/Main.java new file mode 100644 index 000000000..8eddac3fe --- /dev/null +++ b/test/547-regression-trycatch-critical-edge/src/Main.java @@ -0,0 +1,24 @@ +/* + * 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. + */ + +public class Main { + + // Workaround for b/18051191. + class InnerClass {} + + public static void main(String[] args) {} + +} -- 2.11.0