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
25namespace art {
26
27class OptimizerTest : public CommonCompilerTest {};
28
29static 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
50TEST_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
63TEST_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
78TEST_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
95TEST_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
126TEST_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
146TEST_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
163TEST_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
182TEST_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
202TEST_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
223TEST_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
244TEST_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