From 3054a90063d379ab8c9e5a42a7daf0d644b48b07 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Fri, 21 Nov 2014 13:33:51 +0000 Subject: Fix the computation of linear ordering. The register allocator makes assumptions on the order, and we ended up not computing the right one. The algorithm worked fine when the loop header is the block branching to the exit, but in the presence of breaks or do/while, it was incorrect. Change-Id: Iad0a89872cd3f7b7a8b2bdf560f0d03493f93ba5 --- compiler/optimizing/linearize_test.cc | 59 +++++++++++++++++++++++++++++++++-- 1 file changed, 56 insertions(+), 3 deletions(-) (limited to 'compiler/optimizing/linearize_test.cc') diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc index 6dd4207795..c49cf7e03f 100644 --- a/compiler/optimizing/linearize_test.cc +++ b/compiler/optimizing/linearize_test.cc @@ -50,10 +50,9 @@ static void TestCode(const uint16_t* data, const int* expected_order, size_t num SsaLivenessAnalysis liveness(*graph, &codegen); liveness.Analyze(); - ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks); + ASSERT_EQ(liveness.GetLinearOrder().Size(), number_of_blocks); for (size_t i = 0; i < number_of_blocks; ++i) { - ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(), - expected_order[i]); + ASSERT_EQ(liveness.GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]); } } @@ -194,4 +193,58 @@ TEST(LinearizeTest, CFG5) { TestCode(data, blocks, 12); } +TEST(LinearizeTest, CFG6) { + // Block0 + // | + // Block1 + // | + // Block2 ++++++++++++++ + // | + + // Block3 + + // / \ + + // Block8 Block4 + + // | / \ + + // Block5 <- Block9 Block6 + + // | + // Block7 + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::GOTO | 0x0100, + Instruction::IF_EQ, 0x0004, + Instruction::IF_EQ, 0x0003, + Instruction::RETURN_VOID, + Instruction::GOTO | 0xFA00); + + const int blocks[] = {0, 1, 2, 3, 4, 6, 9, 8, 5, 7}; + TestCode(data, blocks, arraysize(blocks)); +} + +TEST(LinearizeTest, CFG7) { + // Structure of this graph (+ are back edges) + // Block0 + // | + // Block1 + // | + // Block2 ++++++++ + // | + + // Block3 + + // / \ + + // Block4 Block8 + + // / \ | + + // Block5 Block9 - Block6 + + // | + // Block7 + // + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::GOTO | 0x0100, + Instruction::IF_EQ, 0x0005, + Instruction::IF_EQ, 0x0003, + Instruction::RETURN_VOID, + Instruction::GOTO | 0xFA00); + + const int blocks[] = {0, 1, 2, 3, 4, 9, 8, 6, 5, 7}; + TestCode(data, blocks, arraysize(blocks)); +} + } // namespace art -- cgit v1.2.3-59-g8ed1b