Linearize the graph before creating live ranges.
Change-Id: I02eb5671e3304ab062286131745c1366448aff58
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
new file mode 100644
index 0000000..4c819a2
--- /dev/null
+++ b/compiler/optimizing/linearize_test.cc
@@ -0,0 +1,190 @@
+/*
+ * 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 <fstream>
+
+#include "base/stringprintf.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "graph_visualizer.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "ssa_builder.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraphBuilder builder(&allocator);
+ const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ ASSERT_NE(graph, nullptr);
+
+ graph->BuildDominatorTree();
+ graph->FindNaturalLoops();
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ ASSERT_EQ(liveness.GetLinearPostOrder().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]);
+ }
+}
+
+TEST(LinearizeTest, CFG1) {
+ // Structure of this graph (* are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2 ******
+ // / \ *
+ // Block5 Block7 *
+ // | | *
+ // Block6 Block3 *
+ // * / \ *
+ // Block4 Block8
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 5,
+ Instruction::IF_EQ, 0xFFFE,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN_VOID);
+
+ const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6};
+ TestCode(data, blocks, 9);
+}
+
+TEST(LinearizeTest, CFG2) {
+ // Structure of this graph (* are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2 ******
+ // / \ *
+ // Block3 Block7 *
+ // | | *
+ // Block6 Block4 *
+ // * / \ *
+ // Block5 Block8
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::RETURN_VOID,
+ Instruction::IF_EQ, 0xFFFD,
+ Instruction::GOTO | 0xFE00);
+
+ const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6};
+ TestCode(data, blocks, 9);
+}
+
+TEST(LinearizeTest, CFG3) {
+ // Structure of this graph (* are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2 ******
+ // / \ *
+ // Block3 Block8 *
+ // | | *
+ // Block7 Block5 *
+ // / * \ *
+ // Block6 * Block9
+ // | *
+ // Block4 **
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::RETURN_VOID,
+ Instruction::GOTO | 0x0100,
+ Instruction::IF_EQ, 0xFFFC,
+ Instruction::GOTO | 0xFD00);
+
+ const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7};
+ TestCode(data, blocks, 10);
+}
+
+TEST(LinearizeTest, CFG4) {
+ // Structure of this graph (* are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2
+ // / * \
+ // Block6 * Block8
+ // | * |
+ // Block7 * Block3 *******
+ // * / \ *
+ // Block9 Block10 *
+ // | *
+ // Block4 *
+ // */ \ *
+ // Block5 Block11
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 7,
+ Instruction::IF_EQ, 0xFFFE,
+ Instruction::IF_EQ, 0xFFFE,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN_VOID);
+
+ const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7};
+ TestCode(data, blocks, 12);
+}
+
+TEST(LinearizeTest, CFG5) {
+ // Structure of this graph (* are back edges)
+ // Block0
+ // |
+ // Block1
+ // |
+ // Block2
+ // / * \
+ // Block3 * Block8
+ // | * |
+ // Block7 * Block4 *******
+ // * / \ *
+ // Block9 Block10 *
+ // | *
+ // Block5 *
+ // */ \ *
+ // Block6 Block11
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::RETURN_VOID,
+ Instruction::IF_EQ, 0xFFFD,
+ Instruction::IF_EQ, 0xFFFE,
+ Instruction::GOTO | 0xFE00);
+
+ const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7};
+ TestCode(data, blocks, 12);
+}
+
+} // namespace art