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