1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <fstream>
18
19 #include "base/stringprintf.h"
20 #include "builder.h"
21 #include "code_generator.h"
22 #include "dex_file.h"
23 #include "dex_instruction.h"
24 #include "graph_visualizer.h"
25 #include "nodes.h"
26 #include "optimizing_unit_test.h"
27 #include "pretty_printer.h"
28 #include "ssa_builder.h"
29 #include "ssa_liveness_analysis.h"
30 #include "utils/arena_allocator.h"
31
32 #include "gtest/gtest.h"
33
34 namespace art {
35
TestCode(const uint16_t * data,const int * expected_order,size_t number_of_blocks)36 static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) {
37 ArenaPool pool;
38 ArenaAllocator allocator(&pool);
39 HGraphBuilder builder(&allocator);
40 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
41 HGraph* graph = builder.BuildGraph(*item);
42 ASSERT_NE(graph, nullptr);
43
44 graph->BuildDominatorTree();
45 graph->TransformToSSA();
46 graph->FindNaturalLoops();
47
48 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
49 SsaLivenessAnalysis liveness(*graph, codegen);
50 liveness.Analyze();
51
52 ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks);
53 for (size_t i = 0; i < number_of_blocks; ++i) {
54 ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(),
55 expected_order[i]);
56 }
57 }
58
TEST(LinearizeTest,CFG1)59 TEST(LinearizeTest, CFG1) {
60 // Structure of this graph (+ are back edges)
61 // Block0
62 // |
63 // Block1
64 // |
65 // Block2 ++++++
66 // / \ +
67 // Block5 Block7 +
68 // | | +
69 // Block6 Block3 +
70 // + / \ +
71 // Block4 Block8
72
73 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
74 Instruction::CONST_4 | 0 | 0,
75 Instruction::IF_EQ, 5,
76 Instruction::IF_EQ, 0xFFFE,
77 Instruction::GOTO | 0xFE00,
78 Instruction::RETURN_VOID);
79
80 const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6};
81 TestCode(data, blocks, 9);
82 }
83
TEST(LinearizeTest,CFG2)84 TEST(LinearizeTest, CFG2) {
85 // Structure of this graph (+ are back edges)
86 // Block0
87 // |
88 // Block1
89 // |
90 // Block2 ++++++
91 // / \ +
92 // Block3 Block7 +
93 // | | +
94 // Block6 Block4 +
95 // + / \ +
96 // Block5 Block8
97
98 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
99 Instruction::CONST_4 | 0 | 0,
100 Instruction::IF_EQ, 3,
101 Instruction::RETURN_VOID,
102 Instruction::IF_EQ, 0xFFFD,
103 Instruction::GOTO | 0xFE00);
104
105 const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6};
106 TestCode(data, blocks, 9);
107 }
108
TEST(LinearizeTest,CFG3)109 TEST(LinearizeTest, CFG3) {
110 // Structure of this graph (+ are back edges)
111 // Block0
112 // |
113 // Block1
114 // |
115 // Block2 ++++++
116 // / \ +
117 // Block3 Block8 +
118 // | | +
119 // Block7 Block5 +
120 // / + \ +
121 // Block6 + Block9
122 // | +
123 // Block4 ++
124 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
125 Instruction::CONST_4 | 0 | 0,
126 Instruction::IF_EQ, 4,
127 Instruction::RETURN_VOID,
128 Instruction::GOTO | 0x0100,
129 Instruction::IF_EQ, 0xFFFC,
130 Instruction::GOTO | 0xFD00);
131
132 const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7};
133 TestCode(data, blocks, 10);
134 }
135
TEST(LinearizeTest,CFG4)136 TEST(LinearizeTest, CFG4) {
137 /* Structure of this graph (+ are back edges)
138 // Block0
139 // |
140 // Block1
141 // |
142 // Block2
143 // / + \
144 // Block6 + Block8
145 // | + |
146 // Block7 + Block3 +++++++
147 // + / \ +
148 // Block9 Block10 +
149 // | +
150 // Block4 +
151 // + / \ +
152 // Block5 Block11
153 */
154 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
155 Instruction::CONST_4 | 0 | 0,
156 Instruction::IF_EQ, 7,
157 Instruction::IF_EQ, 0xFFFE,
158 Instruction::IF_EQ, 0xFFFE,
159 Instruction::GOTO | 0xFE00,
160 Instruction::RETURN_VOID);
161
162 const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7};
163 TestCode(data, blocks, 12);
164 }
165
TEST(LinearizeTest,CFG5)166 TEST(LinearizeTest, CFG5) {
167 /* Structure of this graph (+ are back edges)
168 // Block0
169 // |
170 // Block1
171 // |
172 // Block2
173 // / + \
174 // Block3 + Block8
175 // | + |
176 // Block7 + Block4 +++++++
177 // + / \ +
178 // Block9 Block10 +
179 // | +
180 // Block5 +
181 // +/ \ +
182 // Block6 Block11
183 */
184 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
185 Instruction::CONST_4 | 0 | 0,
186 Instruction::IF_EQ, 3,
187 Instruction::RETURN_VOID,
188 Instruction::IF_EQ, 0xFFFD,
189 Instruction::IF_EQ, 0xFFFE,
190 Instruction::GOTO | 0xFE00);
191
192 const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7};
193 TestCode(data, blocks, 12);
194 }
195
196 } // namespace art
197