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