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 "arch/x86/instruction_set_features_x86.h"
20 #include "base/arena_allocator.h"
21 #include "base/stringprintf.h"
22 #include "builder.h"
23 #include "code_generator.h"
24 #include "code_generator_x86.h"
25 #include "dex_file.h"
26 #include "dex_instruction.h"
27 #include "driver/compiler_options.h"
28 #include "graph_visualizer.h"
29 #include "nodes.h"
30 #include "optimizing_unit_test.h"
31 #include "pretty_printer.h"
32 #include "ssa_builder.h"
33 #include "ssa_liveness_analysis.h"
34
35 #include "gtest/gtest.h"
36
37 namespace art {
38
TestCode(const uint16_t * data,const int * expected_order,size_t number_of_blocks)39 static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) {
40 ArenaPool pool;
41 ArenaAllocator allocator(&pool);
42 HGraph* graph = CreateGraph(&allocator);
43 HGraphBuilder builder(graph);
44 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
45 bool graph_built = builder.BuildGraph(*item);
46 ASSERT_TRUE(graph_built);
47
48 graph->TryBuildingSsa();
49
50 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
51 X86InstructionSetFeatures::FromCppDefines());
52 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
53 SsaLivenessAnalysis liveness(graph, &codegen);
54 liveness.Analyze();
55
56 ASSERT_EQ(graph->GetLinearOrder().Size(), number_of_blocks);
57 for (size_t i = 0; i < number_of_blocks; ++i) {
58 ASSERT_EQ(graph->GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]);
59 }
60 }
61
TEST(LinearizeTest,CFG1)62 TEST(LinearizeTest, CFG1) {
63 // Structure of this graph (+ are back edges)
64 // Block0
65 // |
66 // Block1
67 // |
68 // Block2 ++++++
69 // / \ +
70 // Block5 Block7 +
71 // | | +
72 // Block6 Block3 +
73 // + / \ +
74 // Block4 Block8
75
76 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
77 Instruction::CONST_4 | 0 | 0,
78 Instruction::IF_EQ, 5,
79 Instruction::IF_EQ, 0xFFFE,
80 Instruction::GOTO | 0xFE00,
81 Instruction::RETURN_VOID);
82
83 const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6};
84 TestCode(data, blocks, 9);
85 }
86
TEST(LinearizeTest,CFG2)87 TEST(LinearizeTest, CFG2) {
88 // Structure of this graph (+ are back edges)
89 // Block0
90 // |
91 // Block1
92 // |
93 // Block2 ++++++
94 // / \ +
95 // Block3 Block7 +
96 // | | +
97 // Block6 Block4 +
98 // + / \ +
99 // Block5 Block8
100
101 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
102 Instruction::CONST_4 | 0 | 0,
103 Instruction::IF_EQ, 3,
104 Instruction::RETURN_VOID,
105 Instruction::IF_EQ, 0xFFFD,
106 Instruction::GOTO | 0xFE00);
107
108 const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6};
109 TestCode(data, blocks, 9);
110 }
111
TEST(LinearizeTest,CFG3)112 TEST(LinearizeTest, CFG3) {
113 // Structure of this graph (+ are back edges)
114 // Block0
115 // |
116 // Block1
117 // |
118 // Block2 ++++++
119 // / \ +
120 // Block3 Block8 +
121 // | | +
122 // Block7 Block5 +
123 // / + \ +
124 // Block6 + Block9
125 // | +
126 // Block4 ++
127 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
128 Instruction::CONST_4 | 0 | 0,
129 Instruction::IF_EQ, 4,
130 Instruction::RETURN_VOID,
131 Instruction::GOTO | 0x0100,
132 Instruction::IF_EQ, 0xFFFC,
133 Instruction::GOTO | 0xFD00);
134
135 const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7};
136 TestCode(data, blocks, 10);
137 }
138
TEST(LinearizeTest,CFG4)139 TEST(LinearizeTest, CFG4) {
140 /* Structure of this graph (+ are back edges)
141 // Block0
142 // |
143 // Block1
144 // |
145 // Block2
146 // / + \
147 // Block6 + Block8
148 // | + |
149 // Block7 + Block3 +++++++
150 // + / \ +
151 // Block9 Block10 +
152 // | +
153 // Block4 +
154 // + / \ +
155 // Block5 Block11
156 */
157 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
158 Instruction::CONST_4 | 0 | 0,
159 Instruction::IF_EQ, 7,
160 Instruction::IF_EQ, 0xFFFE,
161 Instruction::IF_EQ, 0xFFFE,
162 Instruction::GOTO | 0xFE00,
163 Instruction::RETURN_VOID);
164
165 const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7};
166 TestCode(data, blocks, 12);
167 }
168
TEST(LinearizeTest,CFG5)169 TEST(LinearizeTest, CFG5) {
170 /* Structure of this graph (+ are back edges)
171 // Block0
172 // |
173 // Block1
174 // |
175 // Block2
176 // / + \
177 // Block3 + Block8
178 // | + |
179 // Block7 + Block4 +++++++
180 // + / \ +
181 // Block9 Block10 +
182 // | +
183 // Block5 +
184 // +/ \ +
185 // Block6 Block11
186 */
187 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
188 Instruction::CONST_4 | 0 | 0,
189 Instruction::IF_EQ, 3,
190 Instruction::RETURN_VOID,
191 Instruction::IF_EQ, 0xFFFD,
192 Instruction::IF_EQ, 0xFFFE,
193 Instruction::GOTO | 0xFE00);
194
195 const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7};
196 TestCode(data, blocks, 12);
197 }
198
TEST(LinearizeTest,CFG6)199 TEST(LinearizeTest, CFG6) {
200 // Block0
201 // |
202 // Block1
203 // |
204 // Block2 ++++++++++++++
205 // | +
206 // Block3 +
207 // / \ +
208 // Block8 Block4 +
209 // | / \ +
210 // Block5 <- Block9 Block6 +
211 // |
212 // Block7
213 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
214 Instruction::CONST_4 | 0 | 0,
215 Instruction::GOTO | 0x0100,
216 Instruction::IF_EQ, 0x0004,
217 Instruction::IF_EQ, 0x0003,
218 Instruction::RETURN_VOID,
219 Instruction::GOTO | 0xFA00);
220
221 const int blocks[] = {0, 1, 2, 3, 4, 6, 9, 8, 5, 7};
222 TestCode(data, blocks, arraysize(blocks));
223 }
224
TEST(LinearizeTest,CFG7)225 TEST(LinearizeTest, CFG7) {
226 // Structure of this graph (+ are back edges)
227 // Block0
228 // |
229 // Block1
230 // |
231 // Block2 ++++++++
232 // | +
233 // Block3 +
234 // / \ +
235 // Block4 Block8 +
236 // / \ | +
237 // Block5 Block9 - Block6 +
238 // |
239 // Block7
240 //
241 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
242 Instruction::CONST_4 | 0 | 0,
243 Instruction::GOTO | 0x0100,
244 Instruction::IF_EQ, 0x0005,
245 Instruction::IF_EQ, 0x0003,
246 Instruction::RETURN_VOID,
247 Instruction::GOTO | 0xFA00);
248
249 const int blocks[] = {0, 1, 2, 3, 4, 9, 8, 6, 5, 7};
250 TestCode(data, blocks, arraysize(blocks));
251 }
252
253 } // namespace art
254