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 "base/arena_allocator.h"
18 #include "builder.h"
19 #include "dex/dex_instruction.h"
20 #include "nodes.h"
21 #include "optimizing_unit_test.h"
22
23 #include "gtest/gtest.h"
24
25 namespace art {
26
27 class OptimizerTest : public OptimizingUnitTest {
28 protected:
29 void TestCode(const std::vector<uint16_t>& data, const uint32_t* blocks, size_t blocks_length);
30 };
31
TestCode(const std::vector<uint16_t> & data,const uint32_t * blocks,size_t blocks_length)32 void OptimizerTest::TestCode(const std::vector<uint16_t>& data,
33 const uint32_t* blocks,
34 size_t blocks_length) {
35 HGraph* graph = CreateCFG(data);
36 ASSERT_EQ(graph->GetBlocks().size(), blocks_length);
37 for (size_t i = 0, e = blocks_length; i < e; ++i) {
38 if (blocks[i] == kInvalidBlockId) {
39 if (graph->GetBlocks()[i] == nullptr) {
40 // Dead block.
41 } else {
42 // Only the entry block has no dominator.
43 ASSERT_EQ(nullptr, graph->GetBlocks()[i]->GetDominator());
44 ASSERT_TRUE(graph->GetBlocks()[i]->IsEntryBlock());
45 }
46 } else {
47 ASSERT_NE(nullptr, graph->GetBlocks()[i]->GetDominator());
48 ASSERT_EQ(blocks[i], graph->GetBlocks()[i]->GetDominator()->GetBlockId());
49 }
50 }
51 }
52
TEST_F(OptimizerTest,ReturnVoid)53 TEST_F(OptimizerTest, ReturnVoid) {
54 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
55 Instruction::RETURN_VOID); // Block number 1
56
57 const uint32_t dominators[] = {
58 kInvalidBlockId,
59 0,
60 1
61 };
62
63 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
64 }
65
TEST_F(OptimizerTest,CFG1)66 TEST_F(OptimizerTest, CFG1) {
67 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
68 Instruction::GOTO | 0x100, // Block number 1
69 Instruction::RETURN_VOID); // Block number 2
70
71 const uint32_t dominators[] = {
72 kInvalidBlockId,
73 0,
74 1,
75 2
76 };
77
78 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
79 }
80
TEST_F(OptimizerTest,CFG2)81 TEST_F(OptimizerTest, CFG2) {
82 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
83 Instruction::GOTO | 0x100, // Block number 1
84 Instruction::GOTO | 0x100, // Block number 2
85 Instruction::RETURN_VOID); // Block number 3
86
87 const uint32_t dominators[] = {
88 kInvalidBlockId,
89 0,
90 1,
91 2,
92 3
93 };
94
95 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
96 }
97
TEST_F(OptimizerTest,CFG3)98 TEST_F(OptimizerTest, CFG3) {
99 const std::vector<uint16_t> data1 = ZERO_REGISTER_CODE_ITEM(
100 Instruction::GOTO | 0x200, // Block number 1
101 Instruction::RETURN_VOID, // Block number 2
102 Instruction::GOTO | 0xFF00); // Block number 3
103
104 const uint32_t dominators[] = {
105 kInvalidBlockId,
106 0,
107 3,
108 1,
109 2
110 };
111
112 TestCode(data1, dominators, sizeof(dominators) / sizeof(int));
113
114 const std::vector<uint16_t> data2 = ZERO_REGISTER_CODE_ITEM(
115 Instruction::GOTO_16, 3,
116 Instruction::RETURN_VOID,
117 Instruction::GOTO_16, 0xFFFF);
118
119 TestCode(data2, dominators, sizeof(dominators) / sizeof(int));
120
121 const std::vector<uint16_t> data3 = ZERO_REGISTER_CODE_ITEM(
122 Instruction::GOTO_32, 4, 0,
123 Instruction::RETURN_VOID,
124 Instruction::GOTO_32, 0xFFFF, 0xFFFF);
125
126 TestCode(data3, dominators, sizeof(dominators) / sizeof(int));
127 }
128
TEST_F(OptimizerTest,CFG4)129 TEST_F(OptimizerTest, CFG4) {
130 const std::vector<uint16_t> data1 = ZERO_REGISTER_CODE_ITEM(
131 Instruction::NOP,
132 Instruction::GOTO | 0xFF00);
133
134 const uint32_t dominators[] = {
135 kInvalidBlockId,
136 3,
137 kInvalidBlockId,
138 0
139 };
140
141 TestCode(data1, dominators, sizeof(dominators) / sizeof(int));
142
143 const std::vector<uint16_t> data2 = ZERO_REGISTER_CODE_ITEM(
144 Instruction::GOTO_32, 0, 0);
145
146 TestCode(data2, dominators, sizeof(dominators) / sizeof(int));
147 }
148
TEST_F(OptimizerTest,CFG5)149 TEST_F(OptimizerTest, CFG5) {
150 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
151 Instruction::RETURN_VOID, // Block number 1
152 Instruction::GOTO | 0x100, // Dead block
153 Instruction::GOTO | 0xFE00); // Block number 2
154
155
156 const uint32_t dominators[] = {
157 kInvalidBlockId,
158 0,
159 kInvalidBlockId,
160 1
161 };
162
163 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
164 }
165
TEST_F(OptimizerTest,CFG6)166 TEST_F(OptimizerTest, CFG6) {
167 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
168 Instruction::CONST_4 | 0 | 0,
169 Instruction::IF_EQ, 3,
170 Instruction::GOTO | 0x100,
171 Instruction::RETURN_VOID);
172
173 const uint32_t dominators[] = {
174 kInvalidBlockId,
175 0,
176 1,
177 1,
178 3,
179 1, // Synthesized block to avoid critical edge.
180 };
181
182 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
183 }
184
TEST_F(OptimizerTest,CFG7)185 TEST_F(OptimizerTest, CFG7) {
186 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
187 Instruction::CONST_4 | 0 | 0,
188 Instruction::IF_EQ, 3, // Block number 1
189 Instruction::GOTO | 0x100, // Block number 2
190 Instruction::GOTO | 0xFF00); // Block number 3
191
192 const uint32_t dominators[] = {
193 kInvalidBlockId,
194 0,
195 1,
196 1,
197 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop.
198 1, // block to avoid critical edge.
199 1 // block to avoid critical edge.
200 };
201
202 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
203 }
204
TEST_F(OptimizerTest,CFG8)205 TEST_F(OptimizerTest, CFG8) {
206 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
207 Instruction::CONST_4 | 0 | 0,
208 Instruction::IF_EQ, 3, // Block number 1
209 Instruction::GOTO | 0x200, // Block number 2
210 Instruction::GOTO | 0x100, // Block number 3
211 Instruction::GOTO | 0xFF00); // Block number 4
212
213 const uint32_t dominators[] = {
214 kInvalidBlockId,
215 0,
216 1,
217 1,
218 1,
219 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop.
220 1 // block to avoid critical edge.
221 };
222
223 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
224 }
225
TEST_F(OptimizerTest,CFG9)226 TEST_F(OptimizerTest, CFG9) {
227 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
228 Instruction::CONST_4 | 0 | 0,
229 Instruction::IF_EQ, 3, // Block number 1
230 Instruction::GOTO | 0x200, // Block number 2
231 Instruction::GOTO | 0x100, // Block number 3
232 Instruction::GOTO | 0xFE00); // Block number 4
233
234 const uint32_t dominators[] = {
235 kInvalidBlockId,
236 0,
237 1,
238 1,
239 1,
240 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop.
241 1 // block to avoid critical edge.
242 };
243
244 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
245 }
246
TEST_F(OptimizerTest,CFG10)247 TEST_F(OptimizerTest, CFG10) {
248 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
249 Instruction::CONST_4 | 0 | 0,
250 Instruction::IF_EQ, 6, // Block number 1
251 Instruction::IF_EQ, 3, // Block number 2
252 Instruction::GOTO | 0x100, // Block number 3
253 Instruction::GOTO | 0x100, // Block number 4
254 Instruction::RETURN_VOID); // Block number 5
255
256 const uint32_t dominators[] = {
257 kInvalidBlockId,
258 0,
259 1,
260 2,
261 2,
262 1,
263 5, // Block number 5 dominates exit block
264 1, // block to avoid critical edge.
265 2 // block to avoid critical edge.
266 };
267
268 TestCode(data, dominators, sizeof(dominators) / sizeof(int));
269 }
270
271 } // namespace art
272