diff options
author | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-12 16:11:02 +0100 |
---|---|---|
committer | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-13 09:06:14 +0100 |
commit | 622d9c31febd950255b36a48b47e1f630197c5fe (patch) | |
tree | 8a7f14ce3c6c087955ad5fe91a3ce7d5b5a82461 /compiler/optimizing | |
parent | 98a8a542f95e41c09d214a329a940b270f08f5b3 (diff) | |
download | art-622d9c31febd950255b36a48b47e1f630197c5fe.zip art-622d9c31febd950255b36a48b47e1f630197c5fe.tar.gz art-622d9c31febd950255b36a48b47e1f630197c5fe.tar.bz2 |
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
Diffstat (limited to 'compiler/optimizing')
-rw-r--r-- | compiler/optimizing/dominator_test.cc | 17 | ||||
-rw-r--r-- | compiler/optimizing/find_loops_test.cc | 362 | ||||
-rw-r--r-- | compiler/optimizing/liveness_test.cc | 71 | ||||
-rw-r--r-- | compiler/optimizing/nodes.cc | 209 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 140 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 1 | ||||
-rw-r--r-- | compiler/optimizing/pretty_printer.h | 20 | ||||
-rw-r--r-- | compiler/optimizing/pretty_printer_test.cc | 2 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.cc | 18 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.cc | 6 | ||||
-rw-r--r-- | compiler/optimizing/ssa_test.cc | 65 |
11 files changed, 754 insertions, 157 deletions
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 @@ TEST(OptimizerTest, CFG6) { 0, 1, 1, - 3 + 3, + 1, // Synthesized block to avoid critical edge. }; TestCode(data, dominators, sizeof(dominators) / sizeof(int)); @@ -185,7 +186,9 @@ TEST(OptimizerTest, CFG7) { 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 @@ TEST(OptimizerTest, CFG8) { 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 @@ TEST(OptimizerTest, CFG9) { 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 @@ TEST(OptimizerTest, CFG10) { 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 @@ TEST(LivenessTest, CFG5) { " 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 @@ TEST(LivenessTest, CFG5) { "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, Loop5) { 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 @@ TEST(LivenessTest, Loop7) { " 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 @@ TEST(LivenessTest, Loop7) { "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::FindBackEdges(ArenaBitVector* visited) { } 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 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block, 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 @@ void HGraph::BuildDominatorTree() { // 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 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, // 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::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 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() { - 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()); + // 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; } - 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()); } + 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()); } -void HLoopInformation::SetPreHeader(HBasicBlock* block) { - DCHECK_EQ(header_->GetDominator(), block); - pre_header_ = block; +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 @@ class HGraph : public ArenaObject { 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 @@ class HGraph : public ArenaObject { 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 @@ class HGraph : public ArenaObject { 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 @@ class HGraph : public ArenaObject { // 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 @@ class HLoopInformation : public ArenaObject { 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 @@ class HBasicBlock : public ArenaObject { 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 @@ class HBasicBlock : public ArenaObject { } } + 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 @@ class HGoto : public HTemplateInstruction<0> { HGoto() { } HBasicBlock* GetSuccessor() const { - return GetBlock()->GetSuccessors()->Get(0); + return GetBlock()->GetSuccessors().Get(0); } DECLARE_INSTRUCTION(Goto) @@ -656,11 +736,11 @@ class HIf : public HTemplateInstruction<1> { } 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 @@ class HInsertionOrderIterator : public ValueObject { 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 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite // 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 @@ class HPrettyPrinter : public HGraphVisitor { 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 @@ class StringPrettyPrinter : public HPrettyPrinter { 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 @@ void SsaBuilder::BuildSsa() { 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 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { // 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 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 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 @@ void SsaLivenessAnalysis::ComputeInitialSets() { 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 @@ bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { 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 @@ TEST(SsaTest, CFG1) { "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 @@ TEST(SsaTest, CFG2) { " 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 @@ TEST(SsaTest, Loop1) { "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 @@ TEST(SsaTest, Loop6) { 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 @@ TEST(SsaTest, Loop7) { " 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 @@ TEST(SsaTest, Loop7) { " 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, |