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