Add loop recognition and CFG simplifications in new compiler.
We do three simplifications:
- Split critical edges, for code generation from SSA (new).
- Ensure one back edge per loop, to simplify loop recognition (new).
- Ensure only one pre header for a loop, to simplify SSA creation (existing).
Change-Id: I9bfccd4b236a00486a261078627b091c8a68be33
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index d4e2cbb..c986c57 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@
compiler/oat_test.cc \
compiler/optimizing/codegen_test.cc \
compiler/optimizing/dominator_test.cc \
+ compiler/optimizing/find_loops_test.cc \
compiler/optimizing/liveness_test.cc \
compiler/optimizing/pretty_printer_test.cc \
compiler/optimizing/ssa_test.cc \
diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 0417050..3062e37 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -167,7 +167,8 @@
0,
1,
1,
- 3
+ 3,
+ 1, // Synthesized block to avoid critical edge.
};
TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -185,7 +186,9 @@
0,
1,
1,
- -1 // exit block is not dominated by any block due to the spin loop.
+ -1, // exit block is not dominated by any block due to the spin loop.
+ 1, // block to avoid critical edge.
+ 1 // block to avoid critical edge.
};
TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -205,7 +208,8 @@
1,
1,
1,
- -1 // exit block is not dominated by any block due to the spin loop.
+ -1, // exit block is not dominated by any block due to the spin loop.
+ 1 // block to avoid critical edge.
};
TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -225,7 +229,8 @@
1,
1,
1,
- -1 // exit block is not dominated by any block due to the spin loop.
+ -1, // exit block is not dominated by any block due to the spin loop.
+ 1 // block to avoid critical edge.
};
TestCode(data, dominators, sizeof(dominators) / sizeof(int));
@@ -247,7 +252,9 @@
2,
2,
1,
- 5 // Block number 5 dominates exit block
+ 5, // Block number 5 dominates exit block
+ 1, // block to avoid critical edge.
+ 2 // block to avoid critical edge.
};
TestCode(data, dominators, sizeof(dominators) / sizeof(int));
diff --git a/compiler/optimizing/find_loops_test.cc b/compiler/optimizing/find_loops_test.cc
new file mode 100644
index 0000000..fab9f7a
--- /dev/null
+++ b/compiler/optimizing/find_loops_test.cc
@@ -0,0 +1,362 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+#include "pretty_printer.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HGraph* TestCode(const uint16_t* data, ArenaPool* pool) {
+ ArenaAllocator allocator(pool);
+ HGraphBuilder builder(&allocator);
+ const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ graph->BuildDominatorTree();
+ graph->FindNaturalLoops();
+ return graph;
+}
+
+TEST(FindLoopsTest, CFG1) {
+ // Constant is not used.
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN_VOID);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+ }
+}
+
+TEST(FindLoopsTest, CFG2) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+ }
+}
+
+TEST(FindLoopsTest, CFG3) {
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 3 << 12 | 0,
+ Instruction::CONST_4 | 4 << 12 | 1 << 8,
+ Instruction::ADD_INT_2ADDR | 1 << 12,
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+ }
+}
+
+TEST(FindLoopsTest, CFG4) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0x200,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+ }
+}
+
+TEST(FindLoopsTest, CFG5) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
+ }
+}
+
+static void TestBlock(HGraph* graph,
+ int block_id,
+ bool is_loop_header,
+ int parent_loop_header_id,
+ const int* blocks_in_loop = nullptr,
+ size_t number_of_blocks = 0) {
+ HBasicBlock* block = graph->GetBlocks().Get(block_id);
+ ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
+ if (parent_loop_header_id == -1) {
+ ASSERT_EQ(block->GetLoopInformation(), nullptr);
+ } else {
+ ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
+ }
+
+ if (blocks_in_loop != nullptr) {
+ HLoopInformation* info = block->GetLoopInformation();
+ const BitVector& blocks = info->GetBlocks();
+ ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
+ for (size_t i = 0; i < number_of_blocks; ++i) {
+ ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
+ }
+ } else {
+ ASSERT_FALSE(block->IsLoopHeader());
+ }
+}
+
+TEST(FindLoopsTest, Loop1) {
+ // Simple loop with one preheader and one back edge.
+ // var a = 0;
+ // while (a == a) {
+ // }
+ // return;
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN_VOID);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header
+ const int blocks2[] = {2, 3};
+ TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
+ TestBlock(graph, 3, false, 2); // block in loop
+ TestBlock(graph, 4, false, -1); // return block
+ TestBlock(graph, 5, false, -1); // exit block
+}
+
+TEST(FindLoopsTest, Loop2) {
+ // Make sure we support a preheader of a loop not being the first predecessor
+ // in the predecessor list of the header.
+ // var a = 0;
+ // while (a == a) {
+ // }
+ // return a;
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x400,
+ Instruction::IF_EQ, 4,
+ Instruction::GOTO | 0xFE00,
+ Instruction::GOTO | 0xFD00,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // goto block
+ const int blocks2[] = {2, 3};
+ TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
+ TestBlock(graph, 3, false, 2); // block in loop
+ TestBlock(graph, 4, false, -1); // pre header
+ TestBlock(graph, 5, false, -1); // return block
+ TestBlock(graph, 6, false, -1); // exit block
+}
+
+TEST(FindLoopsTest, Loop3) {
+ // Make sure we create a preheader of a loop when a header originally has two
+ // incoming blocks and one back edge.
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x100,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // goto block
+ TestBlock(graph, 2, false, -1);
+ const int blocks2[] = {3, 4};
+ TestBlock(graph, 3, true, 3, blocks2, 2); // loop header
+ TestBlock(graph, 4, false, 3); // block in loop
+ TestBlock(graph, 5, false, -1); // pre header
+ TestBlock(graph, 6, false, -1); // return block
+ TestBlock(graph, 7, false, -1); // exit block
+ TestBlock(graph, 8, false, -1); // synthesized pre header
+}
+
+TEST(FindLoopsTest, Loop4) {
+ // Test loop with originally two back edges.
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 6,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFC00,
+ Instruction::GOTO | 0xFB00,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header
+ const int blocks2[] = {2, 3, 4, 5, 8};
+ TestBlock(graph, 2, true, 2, blocks2, 5); // loop header
+ TestBlock(graph, 3, false, 2); // block in loop
+ TestBlock(graph, 4, false, 2); // original back edge
+ TestBlock(graph, 5, false, 2); // original back edge
+ TestBlock(graph, 6, false, -1); // return block
+ TestBlock(graph, 7, false, -1); // exit block
+ TestBlock(graph, 8, false, 2); // synthesized back edge
+}
+
+
+TEST(FindLoopsTest, Loop5) {
+ // Test loop with two exit edges.
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 6,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x0200,
+ Instruction::GOTO | 0xFB00,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header
+ const int blocks2[] = {2, 3, 5};
+ TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
+ TestBlock(graph, 3, false, 2); // block in loop
+ TestBlock(graph, 4, false, -1); // loop exit
+ TestBlock(graph, 5, false, 2); // back edge
+ TestBlock(graph, 6, false, -1); // return block
+ TestBlock(graph, 7, false, -1); // exit block
+ TestBlock(graph, 8, false, -1); // synthesized block at the loop exit
+}
+
+TEST(FindLoopsTest, InnerLoop) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 6,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00, // inner loop
+ Instruction::GOTO | 0xFB00,
+ Instruction::RETURN | 0 << 8);
+
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header of outer loop
+ const int blocks2[] = {2, 3, 4, 5, 8};
+ TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header
+ const int blocks3[] = {3, 4};
+ TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header
+ TestBlock(graph, 4, false, 3); // back edge on inner loop
+ TestBlock(graph, 5, false, 2); // back edge on outer loop
+ TestBlock(graph, 6, false, -1); // return block
+ TestBlock(graph, 7, false, -1); // exit block
+ TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop
+
+ ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
+ *graph->GetBlocks().Get(2)->GetLoopInformation()));
+ ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
+ *graph->GetBlocks().Get(3)->GetLoopInformation()));
+}
+
+TEST(FindLoopsTest, TwoLoops) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00, // first loop
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00, // second loop
+ Instruction::RETURN | 0 << 8);
+
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header of first loop
+ const int blocks2[] = {2, 3};
+ TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header
+ TestBlock(graph, 3, false, 2); // back edge of first loop
+ const int blocks4[] = {4, 5};
+ TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header
+ TestBlock(graph, 5, false, 4); // back edge of second loop
+ TestBlock(graph, 6, false, -1); // return block
+ TestBlock(graph, 7, false, -1); // exit block
+
+ ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
+ *graph->GetBlocks().Get(2)->GetLoopInformation()));
+ ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
+ *graph->GetBlocks().Get(4)->GetLoopInformation()));
+}
+
+TEST(FindLoopsTest, NonNaturalLoop) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0x0100,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFD00,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+ ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
+ HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
+ ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
+}
+
+TEST(FindLoopsTest, DoWhileLoop) {
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x0100,
+ Instruction::IF_EQ, 0xFFFF,
+ Instruction::RETURN | 0 << 8);
+
+ ArenaPool arena;
+ HGraph* graph = TestCode(data, &arena);
+
+ TestBlock(graph, 0, false, -1); // entry block
+ TestBlock(graph, 1, false, -1); // pre header of first loop
+ const int blocks2[] = {2, 3, 6};
+ TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
+ TestBlock(graph, 3, false, 2); // back edge of first loop
+ TestBlock(graph, 4, false, -1); // return block
+ TestBlock(graph, 5, false, -1); // exit block
+ TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge
+}
+
+} // namespace art
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index aa4d35e..d665ab9 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -188,7 +188,7 @@
" kill: (1100)\n"
"Block 1\n" // block with if
" live in: (1100)\n"
- " live out: (0100)\n"
+ " live out: (1100)\n"
" kill: (0010)\n"
"Block 2\n" // else block
" live in: (0100)\n"
@@ -201,6 +201,10 @@
"Block 4\n" // exit block
" live in: (0000)\n"
" live out: (0000)\n"
+ " kill: (0000)\n"
+ "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3.
+ " live in: (1000)\n"
+ " live out: (0000)\n"
" kill: (0000)\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
@@ -412,40 +416,45 @@
TEST(LivenessTest, Loop6) {
// Bitsets are made of:
- // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3)
+ // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
+ // phi in block 8)
const char* expected =
"Block 0\n"
- " live in: (000000)\n"
- " live out: (111000)\n"
- " kill: (111000)\n"
+ " live in: (0000000)\n"
+ " live out: (1110000)\n"
+ " kill: (1110000)\n"
"Block 1\n"
- " live in: (111000)\n"
- " live out: (011000)\n"
- " kill: (000000)\n"
+ " live in: (1110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000000)\n"
"Block 2\n" // loop header
- " live in: (011000)\n"
- " live out: (011100)\n"
- " kill: (000110)\n"
+ " live in: (0110000)\n"
+ " live out: (0111000)\n"
+ " kill: (0001100)\n"
"Block 3\n"
- " live in: (011000)\n"
- " live out: (011000)\n"
- " kill: (000001)\n"
- "Block 4\n" // back edge
- " live in: (011000)\n"
- " live out: (011000)\n"
- " kill: (000000)\n"
- "Block 5\n" // back edge
- " live in: (011000)\n"
- " live out: (011000)\n"
- " kill: (000000)\n"
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000010)\n"
+ "Block 4\n" // original back edge
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000000)\n"
+ "Block 5\n" // original back edge
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000000)\n"
"Block 6\n" // return block
- " live in: (000100)\n"
- " live out: (000000)\n"
- " kill: (000000)\n"
+ " live in: (0001000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
"Block 7\n" // exit block
- " live in: (000000)\n"
- " live out: (000000)\n"
- " kill: (000000)\n";
+ " live in: (0000000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 8\n" // synthesized back edge
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000001)\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -476,7 +485,7 @@
" kill: (0000000)\n"
"Block 2\n" // loop header
" live in: (0110000)\n"
- " live out: (0110000)\n"
+ " live out: (0111000)\n"
" kill: (0001100)\n"
"Block 3\n"
" live in: (0110000)\n"
@@ -497,6 +506,10 @@
"Block 7\n" // exit block
" live in: (0000000)\n"
" live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 8\n" // synthesized block to avoid critical edge.
+ " live in: (0001000)\n"
+ " live out: (0000000)\n"
" kill: (0000000)\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d153bf7..cf2d1ee 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -31,11 +31,11 @@
}
void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
- for (size_t i = 0; i < blocks_.Size(); i++) {
+ for (size_t i = 0; i < blocks_.Size(); ++i) {
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_.Get(i);
- for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
- block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+ for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+ block->GetSuccessors().Get(j)->RemovePredecessor(block, false);
}
for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
block->RemovePhi(it.Current()->AsPhi());
@@ -55,15 +55,14 @@
visited->SetBit(id);
visiting->SetBit(id);
- for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
- HBasicBlock* successor = block->GetSuccessors()->Get(i);
+ for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+ HBasicBlock* successor = block->GetSuccessors().Get(i);
if (visiting->IsBitSet(successor->GetBlockId())) {
successor->AddBackEdge(block);
} else {
VisitBlockForBackEdges(successor, visited, visiting);
}
}
- post_order_.Add(block);
visiting->ClearBit(id);
}
@@ -78,13 +77,18 @@
// predecessors list of live blocks.
RemoveDeadBlocks(visited);
- // (3) Compute the immediate dominator of each block. We visit
+ // (3) Simplify the CFG now, so that we don't need to recompute
+ // dominators and the reverse post order.
+ SimplifyCFG();
+
+ // (4) Compute the immediate dominator of each block. We visit
// the successors of a block only when all its forward branches
// have been processed.
GrowableArray<size_t> visits(arena_, blocks_.Size());
visits.SetSize(blocks_.Size());
- for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) {
- VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits);
+ reverse_post_order_.Add(entry_block_);
+ for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) {
+ VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits);
}
}
@@ -119,59 +123,172 @@
// Once all the forward edges have been visited, we know the immediate
// dominator of the block. We can then start visiting its successors.
if (visits->Get(block->GetBlockId()) ==
- block->GetPredecessors()->Size() - block->NumberOfBackEdges()) {
- for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
- VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits);
+ block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+ reverse_post_order_.Add(block);
+ for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+ VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
}
}
}
void HGraph::TransformToSSA() {
- DCHECK(!post_order_.IsEmpty());
- SimplifyCFG();
+ DCHECK(!reverse_post_order_.IsEmpty());
SsaBuilder ssa_builder(this);
ssa_builder.BuildSsa();
}
-void HGraph::SimplifyCFG() {
- for (size_t i = post_order_.Size(); i > 0; --i) {
- HBasicBlock* current = post_order_.Get(i - 1);
- if (current->IsLoopHeader()) {
- // Make sure the loop has only one pre header. This simplifies SSA building by having
- // to just look at the pre header to know which locals are initialized at entry of the
- // loop.
- HLoopInformation* info = current->GetLoopInformation();
- size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
- if (number_of_incomings != 1) {
- HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
- AddBlock(pre_header);
- pre_header->AddInstruction(new (arena_) HGoto());
- pre_header->SetDominator(current->GetDominator());
- current->SetDominator(pre_header);
- post_order_.InsertAt(i, pre_header);
-
- ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
- for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
- back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
- }
- for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
- HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
- if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
- current->RemovePredecessor(predecessor);
- pred--;
- predecessor->AddSuccessor(pre_header);
- }
- }
- pre_header->AddSuccessor(current);
- }
- info->SetPreHeader(current->GetDominator());
+void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
+ // Insert a new node between `block` and `successor` to split the
+ // critical edge.
+ HBasicBlock* new_block = new (arena_) HBasicBlock(this);
+ AddBlock(new_block);
+ new_block->AddInstruction(new (arena_) HGoto());
+ block->RemoveSuccessor(successor);
+ block->AddSuccessor(new_block);
+ new_block->AddSuccessor(successor);
+ if (successor->IsLoopHeader()) {
+ // If we split at a back edge boundary, make the new block the back edge.
+ HLoopInformation* info = successor->GetLoopInformation();
+ if (info->IsBackEdge(block)) {
+ info->RemoveBackEdge(block);
+ info->AddBackEdge(new_block);
}
}
}
-void HLoopInformation::SetPreHeader(HBasicBlock* block) {
- DCHECK_EQ(header_->GetDominator(), block);
- pre_header_ = block;
+void HGraph::SimplifyLoop(HBasicBlock* header) {
+ HLoopInformation* info = header->GetLoopInformation();
+
+ // If there are more than one back edge, make them branch to the same block that
+ // will become the only back edge. This simplifies finding natural loops in the
+ // graph.
+ if (info->NumberOfBackEdges() > 1) {
+ HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this);
+ AddBlock(new_back_edge);
+ new_back_edge->AddInstruction(new (arena_) HGoto());
+ for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) {
+ HBasicBlock* back_edge = info->GetBackEdges().Get(pred);
+ header->RemovePredecessor(back_edge);
+ back_edge->AddSuccessor(new_back_edge);
+ }
+ info->ClearBackEdges();
+ info->AddBackEdge(new_back_edge);
+ new_back_edge->AddSuccessor(header);
+ }
+
+ // Make sure the loop has only one pre header. This simplifies SSA building by having
+ // to just look at the pre header to know which locals are initialized at entry of the
+ // loop.
+ size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges();
+ if (number_of_incomings != 1) {
+ HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+ AddBlock(pre_header);
+ pre_header->AddInstruction(new (arena_) HGoto());
+
+ ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
+ HBasicBlock* back_edge = info->GetBackEdges().Get(0);
+ for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) {
+ HBasicBlock* predecessor = header->GetPredecessors().Get(pred);
+ if (predecessor != back_edge) {
+ header->RemovePredecessor(predecessor);
+ pred--;
+ predecessor->AddSuccessor(pre_header);
+ }
+ }
+ pre_header->AddSuccessor(header);
+ }
+}
+
+void HGraph::SimplifyCFG() {
+ // 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.
+ for (size_t i = 0; i < blocks_.Size(); ++i) {
+ HBasicBlock* block = blocks_.Get(i);
+ if (block->GetSuccessors().Size() > 1) {
+ for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+ HBasicBlock* successor = block->GetSuccessors().Get(j);
+ if (successor->GetPredecessors().Size() > 1) {
+ SplitCriticalEdge(block, successor);
+ --j;
+ }
+ }
+ }
+ if (block->IsLoopHeader()) {
+ SimplifyLoop(block);
+ }
+ }
+}
+
+bool HGraph::FindNaturalLoops() const {
+ for (size_t i = 0; i < blocks_.Size(); ++i) {
+ HBasicBlock* block = blocks_.Get(i);
+ if (block->IsLoopHeader()) {
+ HLoopInformation* info = block->GetLoopInformation();
+ if (!info->Populate()) {
+ // Abort if the loop is non natural. We currently bailout in such cases.
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
+ if (blocks_.IsBitSet(block->GetBlockId())) {
+ return;
+ }
+
+ blocks_.SetBit(block->GetBlockId());
+ block->SetInLoop(this);
+ for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+ PopulateRecursive(block->GetPredecessors().Get(i));
+ }
+}
+
+bool HLoopInformation::Populate() {
+ DCHECK_EQ(GetBackEdges().Size(), 1u);
+ HBasicBlock* back_edge = GetBackEdges().Get(0);
+ DCHECK(back_edge->GetDominator() != nullptr);
+ if (!header_->Dominates(back_edge)) {
+ // This loop is not natural. Do not bother going further.
+ return false;
+ }
+
+ // Populate this loop: starting with the back edge, recursively add predecessors
+ // that are not already part of that loop. Set the header as part of the loop
+ // to end the recursion.
+ // This is a recursive implementation of the algorithm described in
+ // "Advanced Compiler Design & Implementation" (Muchnick) p192.
+ blocks_.SetBit(header_->GetBlockId());
+ PopulateRecursive(back_edge);
+ return true;
+}
+
+HBasicBlock* HLoopInformation::GetPreHeader() const {
+ DCHECK_EQ(header_->GetPredecessors().Size(), 2u);
+ return header_->GetDominator();
+}
+
+bool HLoopInformation::Contains(const HBasicBlock& block) const {
+ return blocks_.IsBitSet(block.GetBlockId());
+}
+
+bool HLoopInformation::IsIn(const HLoopInformation& other) const {
+ return other.blocks_.IsBitSet(header_->GetBlockId());
+}
+
+bool HBasicBlock::Dominates(HBasicBlock* other) const {
+ // Walk up the dominator tree from `other`, to find out if `this`
+ // is an ancestor.
+ HBasicBlock* current = other;
+ while (current != nullptr) {
+ if (current == this) {
+ return true;
+ }
+ current = current->GetDominator();
+ }
+ return false;
}
static void Add(HInstructionList* instruction_list,
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index bd3d703..081c2bd 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -60,7 +60,7 @@
explicit HGraph(ArenaAllocator* arena)
: arena_(arena),
blocks_(arena, kDefaultNumberOfBlocks),
- post_order_(arena, kDefaultNumberOfBlocks),
+ reverse_post_order_(arena, kDefaultNumberOfBlocks),
maximum_number_of_out_vregs_(0),
number_of_vregs_(0),
number_of_in_vregs_(0),
@@ -81,6 +81,14 @@
void TransformToSSA();
void SimplifyCFG();
+ // Find all natural loops in this graph. Aborts computation and returns false
+ // if one loop is not natural, that is the header does not dominated the back
+ // edge.
+ bool FindNaturalLoops() const;
+
+ void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
+ void SimplifyLoop(HBasicBlock* header);
+
int GetNextInstructionId() {
return current_instruction_id_++;
}
@@ -109,8 +117,8 @@
return number_of_in_vregs_;
}
- const GrowableArray<HBasicBlock*>& GetPostOrder() const {
- return post_order_;
+ const GrowableArray<HBasicBlock*>& GetReversePostOrder() const {
+ return reverse_post_order_;
}
private:
@@ -129,8 +137,8 @@
// List of blocks in insertion order.
GrowableArray<HBasicBlock*> blocks_;
- // List of blocks to perform a post order tree traversal.
- GrowableArray<HBasicBlock*> post_order_;
+ // List of blocks to perform a reverse post order tree traversal.
+ GrowableArray<HBasicBlock*> reverse_post_order_;
HBasicBlock* entry_block_;
HBasicBlock* exit_block_;
@@ -154,30 +162,63 @@
public:
HLoopInformation(HBasicBlock* header, HGraph* graph)
: header_(header),
- back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges) { }
+ back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
+ blocks_(graph->GetArena(), graph->GetBlocks().Size(), false) {}
+
+ HBasicBlock* GetHeader() const {
+ return header_;
+ }
void AddBackEdge(HBasicBlock* back_edge) {
back_edges_.Add(back_edge);
}
+ void RemoveBackEdge(HBasicBlock* back_edge) {
+ back_edges_.Delete(back_edge);
+ }
+
+ bool IsBackEdge(HBasicBlock* block) {
+ for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
+ if (back_edges_.Get(i) == block) return true;
+ }
+ return false;
+ }
+
int NumberOfBackEdges() const {
return back_edges_.Size();
}
- void SetPreHeader(HBasicBlock* block);
+ HBasicBlock* GetPreHeader() const;
- HBasicBlock* GetPreHeader() const {
- return pre_header_;
+ const GrowableArray<HBasicBlock*>& GetBackEdges() const {
+ return back_edges_;
}
- const GrowableArray<HBasicBlock*>* GetBackEdges() const {
- return &back_edges_;
+ void ClearBackEdges() {
+ back_edges_.Reset();
}
+ // Find blocks that are part of this loop. Returns whether the loop is a natural loop,
+ // that is the header dominates the back edge.
+ bool Populate();
+
+ // Returns whether this loop information contains `block`.
+ // Note that this loop information *must* be populated before entering this function.
+ bool Contains(const HBasicBlock& block) const;
+
+ // Returns whether this loop information is an inner loop of `other`.
+ // Note that `other` *must* be populated before entering this function.
+ bool IsIn(const HLoopInformation& other) const;
+
+ const ArenaBitVector& GetBlocks() const { return blocks_; }
+
private:
- HBasicBlock* pre_header_;
+ // Internal recursive implementation of `Populate`.
+ void PopulateRecursive(HBasicBlock* block);
+
HBasicBlock* header_;
GrowableArray<HBasicBlock*> back_edges_;
+ ArenaBitVector blocks_;
DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
};
@@ -195,18 +236,19 @@
dominator_(nullptr),
block_id_(-1) { }
- const GrowableArray<HBasicBlock*>* GetPredecessors() const {
- return &predecessors_;
+ const GrowableArray<HBasicBlock*>& GetPredecessors() const {
+ return predecessors_;
}
- const GrowableArray<HBasicBlock*>* GetSuccessors() const {
- return &successors_;
+ const GrowableArray<HBasicBlock*>& GetSuccessors() const {
+ return successors_;
}
void AddBackEdge(HBasicBlock* back_edge) {
if (loop_information_ == nullptr) {
loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
}
+ DCHECK_EQ(loop_information_->GetHeader(), this);
loop_information_->AddBackEdge(back_edge);
}
@@ -241,19 +283,57 @@
}
}
+ void RemoveSuccessor(HBasicBlock* block, bool remove_in_predecessor = true) {
+ successors_.Delete(block);
+ if (remove_in_predecessor) {
+ block->predecessors_.Delete(this);
+ }
+ }
+
+ void ClearAllPredecessors() {
+ predecessors_.Reset();
+ }
+
+ void AddPredecessor(HBasicBlock* block) {
+ predecessors_.Add(block);
+ block->successors_.Add(this);
+ }
+
void AddInstruction(HInstruction* instruction);
void RemoveInstruction(HInstruction* instruction);
void AddPhi(HPhi* phi);
void RemovePhi(HPhi* phi);
bool IsLoopHeader() const {
- return loop_information_ != nullptr;
+ return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
}
HLoopInformation* GetLoopInformation() const {
return loop_information_;
}
+ // Set the loop_information_ on this block. This method overrides the current
+ // loop_information if it is an outer loop of the passed loop information.
+ void SetInLoop(HLoopInformation* info) {
+ if (IsLoopHeader()) {
+ // Nothing to do. This just means `info` is an outer loop.
+ } else if (loop_information_ == nullptr) {
+ loop_information_ = info;
+ } else if (loop_information_->Contains(*info->GetHeader())) {
+ // Block is currently part of an outer loop. Make it part of this inner loop.
+ // Note that a non loop header having a loop information means this loop information
+ // has already been populated
+ loop_information_ = info;
+ } else {
+ // Block is part of an inner loop. Do not update the loop information.
+ // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()`
+ // at this point, because this method is being called while populating `info`.
+ }
+ }
+
+ // Returns wheter this block dominates the blocked passed as parameter.
+ bool Dominates(HBasicBlock* block) const;
+
private:
HGraph* const graph_;
GrowableArray<HBasicBlock*> predecessors_;
@@ -638,7 +718,7 @@
HGoto() { }
HBasicBlock* GetSuccessor() const {
- return GetBlock()->GetSuccessors()->Get(0);
+ return GetBlock()->GetSuccessors().Get(0);
}
DECLARE_INSTRUCTION(Goto)
@@ -656,11 +736,11 @@
}
HBasicBlock* IfTrueSuccessor() const {
- return GetBlock()->GetSuccessors()->Get(0);
+ return GetBlock()->GetSuccessors().Get(0);
}
HBasicBlock* IfFalseSuccessor() const {
- return GetBlock()->GetSuccessors()->Get(1);
+ return GetBlock()->GetSuccessors().Get(1);
}
DECLARE_INSTRUCTION(If)
@@ -1011,35 +1091,35 @@
DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
};
-class HPostOrderIterator : public ValueObject {
+class HReversePostOrderIterator : public ValueObject {
public:
- explicit HPostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+ explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
- bool Done() const { return index_ == graph_.GetPostOrder().Size(); }
- HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_); }
+ bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); }
+ HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); }
void Advance() { ++index_; }
private:
const HGraph& graph_;
size_t index_;
- DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
+ DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
};
-class HReversePostOrderIterator : public ValueObject {
+class HPostOrderIterator : public ValueObject {
public:
- explicit HReversePostOrderIterator(const HGraph& graph)
- : graph_(graph), index_(graph_.GetPostOrder().Size()) {}
+ explicit HPostOrderIterator(const HGraph& graph)
+ : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {}
bool Done() const { return index_ == 0; }
- HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_ - 1); }
+ HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); }
void Advance() { --index_; }
private:
const HGraph& graph_;
size_t index_;
- DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
+ DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
};
} // namespace art
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 8594c69..a5031e0 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -104,6 +104,7 @@
// Run these phases to get some test coverage.
graph->BuildDominatorTree();
graph->TransformToSSA();
+ graph->FindNaturalLoops();
SsaLivenessAnalysis(*graph).Analyze();
return new CompiledMethod(GetCompilerDriver(),
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index c82d0cc..dfeafe7 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -70,23 +70,23 @@
virtual void VisitBasicBlock(HBasicBlock* block) {
PrintString("BasicBlock ");
PrintInt(block->GetBlockId());
- const GrowableArray<HBasicBlock*>* blocks = block->GetPredecessors();
- if (!blocks->IsEmpty()) {
+ const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+ if (!predecessors.IsEmpty()) {
PrintString(", pred: ");
- for (size_t i = 0; i < blocks->Size() -1; i++) {
- PrintInt(blocks->Get(i)->GetBlockId());
+ for (size_t i = 0; i < predecessors.Size() -1; i++) {
+ PrintInt(predecessors.Get(i)->GetBlockId());
PrintString(", ");
}
- PrintInt(blocks->Peek()->GetBlockId());
+ PrintInt(predecessors.Peek()->GetBlockId());
}
- blocks = block->GetSuccessors();
- if (!blocks->IsEmpty()) {
+ const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors();
+ if (!successors.IsEmpty()) {
PrintString(", succ: ");
- for (size_t i = 0; i < blocks->Size() - 1; i++) {
- PrintInt(blocks->Get(i)->GetBlockId());
+ for (size_t i = 0; i < successors.Size() - 1; i++) {
+ PrintInt(successors.Get(i)->GetBlockId());
PrintString(", ");
}
- PrintInt(blocks->Peek()->GetBlockId());
+ PrintInt(successors.Peek()->GetBlockId());
}
PrintNewLine();
HGraphVisitor::VisitBasicBlock(block);
diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc
index 04db7a6..006349c 100644
--- a/compiler/optimizing/pretty_printer_test.cc
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -57,7 +57,7 @@
PrintString(" ");
PrintInt(gota->GetId());
PrintString(": Goto ");
- PrintInt(current_block_->GetSuccessors()->Get(0)->GetBlockId());
+ PrintInt(current_block_->GetSuccessors().Get(0)->GetBlockId());
PrintNewLine();
}
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index ee1e1e4..1fc041c 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -32,8 +32,8 @@
HBasicBlock* block = loop_headers_.Get(i);
for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
HPhi* phi = it.Current()->AsPhi();
- for (size_t pred = 0; pred < block->GetPredecessors()->Size(); pred++) {
- phi->AddInput(ValueOfLocal(block->GetPredecessors()->Get(pred), phi->GetRegNumber()));
+ for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) {
+ phi->AddInput(ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()));
}
}
}
@@ -75,14 +75,14 @@
// Save the loop header so that the last phase of the analysis knows which
// blocks need to be updated.
loop_headers_.Add(block);
- } else if (block->GetPredecessors()->Size() > 0) {
+ } else if (block->GetPredecessors().Size() > 0) {
// All predecessors have already been visited because we are visiting in reverse post order.
// We merge the values of all locals, creating phis if those values differ.
for (size_t local = 0; local < current_locals_->Size(); local++) {
bool is_different = false;
- HInstruction* value = ValueOfLocal(block->GetPredecessors()->Get(0), local);
- for (size_t i = 1; i < block->GetPredecessors()->Size(); i++) {
- if (ValueOfLocal(block->GetPredecessors()->Get(i), local) != value) {
+ HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local);
+ for (size_t i = 1; i < block->GetPredecessors().Size(); i++) {
+ if (ValueOfLocal(block->GetPredecessors().Get(i), local) != value) {
is_different = true;
break;
}
@@ -90,9 +90,9 @@
if (is_different) {
// TODO: Compute union type.
HPhi* phi = new (GetGraph()->GetArena()) HPhi(
- GetGraph()->GetArena(), local, block->GetPredecessors()->Size(), Primitive::kPrimVoid);
- for (size_t i = 0; i < block->GetPredecessors()->Size(); i++) {
- phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors()->Get(i), local));
+ GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid);
+ for (size_t i = 0; i < block->GetPredecessors().Size(); i++) {
+ phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors().Get(i), local));
}
block->AddPhi(phi);
value = phi;
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 838597d..0ab77ca 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -110,7 +110,7 @@
for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
HInstruction* input = current->InputAt(i);
- HBasicBlock* predecessor = block->GetPredecessors()->Get(i);
+ HBasicBlock* predecessor = block->GetPredecessors().Get(i);
size_t ssa_index = input->GetSsaIndex();
BitVector* predecessor_kill = GetKillSet(*predecessor);
BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
@@ -147,8 +147,8 @@
BitVector* live_out = GetLiveOutSet(block);
bool changed = false;
// The live_out set of a block is the union of live_in sets of its successors.
- for (size_t i = 0, e = block.GetSuccessors()->Size(); i < e; ++i) {
- HBasicBlock* successor = block.GetSuccessors()->Get(i);
+ for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) {
+ HBasicBlock* successor = block.GetSuccessors().Get(i);
if (live_out->Union(GetLiveInSet(*successor))) {
changed = true;
}
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index e4aafb7..9be2197 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -98,15 +98,18 @@
"BasicBlock 0, succ: 1\n"
" 0: IntConstant 0 [2, 2]\n"
" 1: Goto\n"
- "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ "BasicBlock 1, pred: 0, succ: 2, 5\n"
" 2: Equal(0, 0) [3]\n"
" 3: If(2)\n"
"BasicBlock 2, pred: 1, succ: 3\n"
" 4: Goto\n"
- "BasicBlock 3, pred: 1, 2, succ: 4\n"
+ "BasicBlock 3, pred: 2, 5, succ: 4\n"
" 5: ReturnVoid\n"
"BasicBlock 4, pred: 3\n"
- " 6: Exit\n";
+ " 6: Exit\n"
+ // Synthesized block to avoid critical edge.
+ "BasicBlock 5, pred: 1, succ: 3\n"
+ " 7: Goto\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -125,16 +128,19 @@
" 0: IntConstant 0 [6, 3, 3]\n"
" 1: IntConstant 4 [6]\n"
" 2: Goto\n"
- "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ "BasicBlock 1, pred: 0, succ: 2, 5\n"
" 3: Equal(0, 0) [4]\n"
" 4: If(3)\n"
"BasicBlock 2, pred: 1, succ: 3\n"
" 5: Goto\n"
- "BasicBlock 3, pred: 1, 2, succ: 4\n"
- " 6: Phi(0, 1) [7]\n"
+ "BasicBlock 3, pred: 2, 5, succ: 4\n"
+ " 6: Phi(1, 0) [7]\n"
" 7: Return(6)\n"
"BasicBlock 4, pred: 3\n"
- " 8: Exit\n";
+ " 8: Exit\n"
+ // Synthesized block to avoid critical edge.
+ "BasicBlock 5, pred: 1, succ: 3\n"
+ " 9: Goto\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -184,16 +190,21 @@
"BasicBlock 0, succ: 1\n"
" 0: IntConstant 0 [6, 4, 2, 2]\n"
" 1: Goto\n"
- "BasicBlock 1, pred: 0, succ: 3, 2\n"
+ "BasicBlock 1, pred: 0, succ: 5, 6\n"
" 2: Equal(0, 0) [3]\n"
" 3: If(2)\n"
- "BasicBlock 2, pred: 1, 3, succ: 3\n"
- " 4: Phi(0, 6) [6]\n"
+ "BasicBlock 2, pred: 3, 6, succ: 3\n"
+ " 4: Phi(6, 0) [6]\n"
" 5: Goto\n"
- "BasicBlock 3, pred: 1, 2, succ: 2\n"
- " 6: Phi(0, 4) [4]\n"
+ "BasicBlock 3, pred: 2, 5, succ: 2\n"
+ " 6: Phi(4, 0) [4]\n"
" 7: Goto\n"
- "BasicBlock 4\n";
+ "BasicBlock 4\n"
+ // Synthesized blocks to avoid critical edge.
+ "BasicBlock 5, pred: 1, succ: 3\n"
+ " 8: Goto\n"
+ "BasicBlock 6, pred: 1, succ: 2\n"
+ " 9: Goto\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -349,26 +360,30 @@
const char* expected =
"BasicBlock 0, succ: 1\n"
" 0: IntConstant 0 [5]\n"
- " 1: IntConstant 4 [5, 8, 8]\n"
- " 2: IntConstant 5 [5]\n"
+ " 1: IntConstant 4 [14, 8, 8]\n"
+ " 2: IntConstant 5 [14]\n"
" 3: Goto\n"
"BasicBlock 1, pred: 0, succ: 2\n"
" 4: Goto\n"
- "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
- " 5: Phi(0, 2, 1) [12, 6, 6]\n"
+ "BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
+ " 5: Phi(0, 14) [12, 6, 6]\n"
" 6: Equal(5, 5) [7]\n"
" 7: If(6)\n"
"BasicBlock 3, pred: 2, succ: 5, 4\n"
" 8: Equal(1, 1) [9]\n"
" 9: If(8)\n"
- "BasicBlock 4, pred: 3, succ: 2\n"
+ "BasicBlock 4, pred: 3, succ: 8\n"
" 10: Goto\n"
- "BasicBlock 5, pred: 3, succ: 2\n"
+ "BasicBlock 5, pred: 3, succ: 8\n"
" 11: Goto\n"
"BasicBlock 6, pred: 2, succ: 7\n"
" 12: Return(5)\n"
"BasicBlock 7, pred: 6\n"
- " 13: Exit\n";
+ " 13: Exit\n"
+ // Synthesized single back edge of loop.
+ "BasicBlock 8, pred: 5, 4, succ: 2\n"
+ " 14: Phi(1, 2) [5]\n"
+ " 15: Goto\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -393,7 +408,7 @@
" 3: Goto\n"
"BasicBlock 1, pred: 0, succ: 2\n"
" 4: Goto\n"
- "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+ "BasicBlock 2, pred: 1, 5, succ: 3, 8\n"
" 5: Phi(0, 1) [12, 6, 6]\n"
" 6: Equal(5, 5) [7]\n"
" 7: If(6)\n"
@@ -404,11 +419,13 @@
" 10: Goto\n"
"BasicBlock 5, pred: 3, succ: 2\n"
" 11: Goto\n"
- "BasicBlock 6, pred: 2, 4, succ: 7\n"
- " 12: Phi(5, 2) [13]\n"
+ "BasicBlock 6, pred: 4, 8, succ: 7\n"
+ " 12: Phi(2, 5) [13]\n"
" 13: Return(12)\n"
"BasicBlock 7, pred: 6\n"
- " 14: Exit\n";
+ " 14: Exit\n"
+ "BasicBlock 8, pred: 2, succ: 6\n"
+ " 15: Goto\n";
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 0e01dc2..a3e2b15 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -399,13 +399,13 @@
return count;
}
-void BitVector::Dump(std::ostream& os, const char *prefix) {
+void BitVector::Dump(std::ostream& os, const char *prefix) const {
std::ostringstream buffer;
DumpHelper(buffer, prefix);
os << buffer.str() << std::endl;
}
-void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) {
+void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) const {
std::ostringstream buffer;
Dump(buffer, prefix);
@@ -421,7 +421,7 @@
fprintf(file, "\\\n");
}
-void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) {
+void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) const {
// Initialize it.
if (prefix != nullptr) {
buffer << prefix;
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 6ee6b00..2a68396 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -148,11 +148,11 @@
bool EnsureSizeAndClear(unsigned int num);
- void Dump(std::ostream& os, const char* prefix);
- void DumpDot(FILE* file, const char* prefix, bool last_entry = false);
+ void Dump(std::ostream& os, const char* prefix) const;
+ void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const;
protected:
- void DumpHelper(std::ostringstream& buffer, const char* prefix);
+ void DumpHelper(std::ostringstream& buffer, const char* prefix) const;
private:
Allocator* const allocator_;