ART: Fix single-preheader transformation.
Original implementation of "Make sure the loop has only one
pre-header" had an assumption that the header had no phi
functions since loops with multiple preheaders now only may exist
during graph building before ssa construction; all of the
optimizations preserve the single-preheader invariant. This code is
used by DCE; DCE was called multiple times but after graph building
preheader transformation was never executed. However if someone
introduces a optimization which might not keep the invariant
(e.g. loop peeling) the data flow adjustments must be performed.
Test: loop_optimization_test.cc
Test: test-art-target, test-art-host
Change-Id: I88bb0aad2dd5241addef7fe9cda474a6868bf532
diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc
index 4e1857d..db83689 100644
--- a/compiler/optimizing/loop_optimization_test.cc
+++ b/compiler/optimizing/loop_optimization_test.cc
@@ -194,7 +194,9 @@
// Check that SimplifyLoop() doesn't invalidate data flow when ordering loop headers'
// predecessors.
-TEST_F(LoopOptimizationTest, SimplifyLoop) {
+//
+// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
+TEST_F(LoopOptimizationTest, SimplifyLoopReoderPredecessors) {
// Can't use AddLoop as we want special order for blocks predecessors.
HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
@@ -232,4 +234,83 @@
ASSERT_TRUE(input->GetBlock()->Dominates(header->GetPredecessors()[i]));
}
}
+
+// Test that SimplifyLoop() processes the multiple-preheaders loops correctly.
+//
+// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
+TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) {
+ HBasicBlock* header = AddLoop(entry_block_, return_block_);
+
+ header->InsertInstructionBefore(
+ new (GetAllocator()) HSuspendCheck(), header->GetLastInstruction());
+
+ // Insert an if construct before the loop so it will have two preheaders.
+ HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_);
+ HBasicBlock* preheader0 = new (GetAllocator()) HBasicBlock(graph_);
+ HBasicBlock* preheader1 = new (GetAllocator()) HBasicBlock(graph_);
+
+ graph_->AddBlock(if_block);
+ graph_->AddBlock(preheader0);
+ graph_->AddBlock(preheader1);
+
+ // Fix successors/predecessors.
+ entry_block_->ReplaceSuccessor(header, if_block);
+ if_block->AddSuccessor(preheader0);
+ if_block->AddSuccessor(preheader1);
+ preheader0->AddSuccessor(header);
+ preheader1->AddSuccessor(header);
+
+ if_block->AddInstruction(new (GetAllocator()) HIf(parameter_));
+ preheader0->AddInstruction(new (GetAllocator()) HGoto());
+ preheader1->AddInstruction(new (GetAllocator()) HGoto());
+
+ HBasicBlock* body = header->GetSuccessors()[0];
+ DCHECK(body != return_block_);
+
+ // Add some data flow.
+ HIntConstant* const_0 = graph_->GetIntConstant(0);
+ HIntConstant* const_1 = graph_->GetIntConstant(1);
+ HIntConstant* const_2 = graph_->GetIntConstant(2);
+
+ HAdd* preheader0_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_0);
+ preheader0->AddInstruction(preheader0_add);
+ HAdd* preheader1_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_1);
+ preheader1->AddInstruction(preheader1_add);
+
+ HPhi* header_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
+ header->AddPhi(header_phi);
+
+ HAdd* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_2);
+ body->AddInstruction(body_add);
+
+ DCHECK(header->GetPredecessors()[0] == body);
+ DCHECK(header->GetPredecessors()[1] == preheader0);
+ DCHECK(header->GetPredecessors()[2] == preheader1);
+
+ header_phi->AddInput(body_add);
+ header_phi->AddInput(preheader0_add);
+ header_phi->AddInput(preheader1_add);
+
+ graph_->ClearLoopInformation();
+ graph_->ClearDominanceInformation();
+ graph_->BuildDominatorTree();
+
+ EXPECT_EQ(header->GetPredecessors().size(), 2u);
+ EXPECT_EQ(header->GetPredecessors()[1], body);
+
+ HBasicBlock* new_preheader = header->GetLoopInformation()->GetPreHeader();
+ EXPECT_EQ(preheader0->GetSingleSuccessor(), new_preheader);
+ EXPECT_EQ(preheader1->GetSingleSuccessor(), new_preheader);
+
+ EXPECT_EQ(new_preheader->GetPhis().CountSize(), 1u);
+ HPhi* new_preheader_phi = new_preheader->GetFirstPhi()->AsPhi();
+ EXPECT_EQ(new_preheader_phi->InputCount(), 2u);
+ EXPECT_EQ(new_preheader_phi->InputAt(0), preheader0_add);
+ EXPECT_EQ(new_preheader_phi->InputAt(1), preheader1_add);
+
+ EXPECT_EQ(header_phi->InputCount(), 2u);
+ EXPECT_EQ(header_phi->InputAt(0), new_preheader_phi);
+ EXPECT_EQ(header_phi->InputAt(1), body_add);
+}
+
} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d39c2ad..099e6cc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -397,6 +397,117 @@
}
}
+// Transform control flow of the loop to a single preheader format (don't touch the data flow).
+// New_preheader can be already among the header predecessors - this situation will be correctly
+// processed.
+static void FixControlForNewSinglePreheader(HBasicBlock* header, HBasicBlock* new_preheader) {
+ HLoopInformation* loop_info = header->GetLoopInformation();
+ for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
+ HBasicBlock* predecessor = header->GetPredecessors()[pred];
+ if (!loop_info->IsBackEdge(*predecessor) && predecessor != new_preheader) {
+ predecessor->ReplaceSuccessor(header, new_preheader);
+ pred--;
+ }
+ }
+}
+
+// == Before == == After ==
+// _________ _________ _________ _________
+// | B0 | | B1 | (old preheaders) | B0 | | B1 |
+// |=========| |=========| |=========| |=========|
+// | i0 = .. | | i1 = .. | | i0 = .. | | i1 = .. |
+// |_________| |_________| |_________| |_________|
+// \ / \ /
+// \ / ___v____________v___
+// \ / (new preheader) | B20 <- B0, B1 |
+// | | |====================|
+// | | | i20 = phi(i0, i1) |
+// | | |____________________|
+// | | |
+// /\ | | /\ /\ | /\
+// / v_______v_________v_______v \ / v___________v_____________v \
+// | | B10 <- B0, B1, B2, B3 | | | | B10 <- B20, B2, B3 | |
+// | |===========================| | (header) | |===========================| |
+// | | i10 = phi(i0, i1, i2, i3) | | | | i10 = phi(i20, i2, i3) | |
+// | |___________________________| | | |___________________________| |
+// | / \ | | / \ |
+// | ... ... | | ... ... |
+// | _________ _________ | | _________ _________ |
+// | | B2 | | B3 | | | | B2 | | B3 | |
+// | |=========| |=========| | (back edges) | |=========| |=========| |
+// | | i2 = .. | | i3 = .. | | | | i2 = .. | | i3 = .. | |
+// | |_________| |_________| | | |_________| |_________| |
+// \ / \ / \ / \ /
+// \___/ \___/ \___/ \___/
+//
+void HGraph::TransformLoopToSinglePreheaderFormat(HBasicBlock* header) {
+ HLoopInformation* loop_info = header->GetLoopInformation();
+
+ HBasicBlock* preheader = new (allocator_) HBasicBlock(this, header->GetDexPc());
+ AddBlock(preheader);
+ preheader->AddInstruction(new (allocator_) HGoto(header->GetDexPc()));
+
+ // If the old header has no Phis then we only need to fix the control flow.
+ if (header->GetPhis().IsEmpty()) {
+ FixControlForNewSinglePreheader(header, preheader);
+ preheader->AddSuccessor(header);
+ return;
+ }
+
+ // Find the first non-back edge block in the header's predecessors list.
+ size_t first_nonbackedge_pred_pos = 0;
+ bool found = false;
+ for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
+ HBasicBlock* predecessor = header->GetPredecessors()[pred];
+ if (!loop_info->IsBackEdge(*predecessor)) {
+ first_nonbackedge_pred_pos = pred;
+ found = true;
+ break;
+ }
+ }
+
+ DCHECK(found);
+
+ // Fix the data-flow.
+ for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* header_phi = it.Current()->AsPhi();
+
+ HPhi* preheader_phi = new (GetAllocator()) HPhi(GetAllocator(),
+ header_phi->GetRegNumber(),
+ 0,
+ header_phi->GetType());
+ if (header_phi->GetType() == DataType::Type::kReference) {
+ preheader_phi->SetReferenceTypeInfo(header_phi->GetReferenceTypeInfo());
+ }
+ preheader->AddPhi(preheader_phi);
+
+ HInstruction* orig_input = header_phi->InputAt(first_nonbackedge_pred_pos);
+ header_phi->ReplaceInput(preheader_phi, first_nonbackedge_pred_pos);
+ preheader_phi->AddInput(orig_input);
+
+ for (size_t input_pos = first_nonbackedge_pred_pos + 1;
+ input_pos < header_phi->InputCount();
+ input_pos++) {
+ HInstruction* input = header_phi->InputAt(input_pos);
+ HBasicBlock* pred_block = header->GetPredecessors()[input_pos];
+
+ if (loop_info->Contains(*pred_block)) {
+ DCHECK(loop_info->IsBackEdge(*pred_block));
+ } else {
+ preheader_phi->AddInput(input);
+ header_phi->RemoveInputAt(input_pos);
+ input_pos--;
+ }
+ }
+ }
+
+ // Fix the control-flow.
+ HBasicBlock* first_pred = header->GetPredecessors()[first_nonbackedge_pred_pos];
+ preheader->InsertBetween(first_pred, header);
+
+ FixControlForNewSinglePreheader(header, preheader);
+}
+
void HGraph::SimplifyLoop(HBasicBlock* header) {
HLoopInformation* info = header->GetLoopInformation();
@@ -406,18 +517,7 @@
// this graph.
size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges();
if (number_of_incomings != 1 || (GetEntryBlock()->GetSingleSuccessor() == header)) {
- HBasicBlock* pre_header = new (allocator_) HBasicBlock(this, header->GetDexPc());
- AddBlock(pre_header);
- pre_header->AddInstruction(new (allocator_) HGoto(header->GetDexPc()));
-
- for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
- HBasicBlock* predecessor = header->GetPredecessors()[pred];
- if (!info->IsBackEdge(*predecessor)) {
- predecessor->ReplaceSuccessor(header, pre_header);
- pred--;
- }
- }
- pre_header->AddSuccessor(header);
+ TransformLoopToSinglePreheaderFormat(header);
}
OrderLoopHeaderPredecessors(header);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index affd54e..f83abd7 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -423,6 +423,17 @@
void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
void OrderLoopHeaderPredecessors(HBasicBlock* header);
+
+ // Transform a loop into a format with a single preheader.
+ //
+ // Each phi in the header should be split: original one in the header should only hold
+ // inputs reachable from the back edges and a single input from the preheader. The newly created
+ // phi in the preheader should collate the inputs from the original multiple incoming blocks.
+ //
+ // Loops in the graph typically have a single preheader, so this method is used to "repair" loops
+ // that no longer have this property.
+ void TransformLoopToSinglePreheaderFormat(HBasicBlock* header);
+
void SimplifyLoop(HBasicBlock* header);
int32_t GetNextInstructionId() {