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