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