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