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
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index c32ef51..f77576d 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -460,12 +460,18 @@
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 @@
"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 b7262f6..5de94f4 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -69,10 +69,13 @@
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 @@
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 @@
// 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 fda5153..c2ba157 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -70,11 +70,14 @@
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 @@
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 47457de..2bb769a 100644
--- a/compiler/optimizing/licm_test.cc
+++ b/compiler/optimizing/licm_test.cc
@@ -42,12 +42,14 @@
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 @@
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 @@
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 af3d8f4..3e137ff 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -383,19 +383,27 @@
}
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;
}