dominator_test.cc revision 787c3076635cf117eb646c5a89a9014b2072fb44 
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
25namespace art {
26
27static 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; i < blocks_length; 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
46TEST(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
59TEST(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
74TEST(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
91TEST(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
122TEST(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
141TEST(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
158TEST(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  };
172
173  TestCode(data, dominators, sizeof(dominators) / sizeof(int));
174}
175
176TEST(OptimizerTest, CFG7) {
177  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
178    Instruction::CONST_4 | 0 | 0,
179    Instruction::IF_EQ, 3,        // Block number 1
180    Instruction::GOTO | 0x100,    // Block number 2
181    Instruction::GOTO | 0xFF00);  // Block number 3
182
183  const int dominators[] = {
184    -1,
185    0,
186    1,
187    1,
188    -1  // exit block is not dominated by any block due to the spin loop.
189  };
190
191  TestCode(data, dominators, sizeof(dominators) / sizeof(int));
192}
193
194TEST(OptimizerTest, CFG8) {
195  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
196    Instruction::CONST_4 | 0 | 0,
197    Instruction::IF_EQ, 3,        // Block number 1
198    Instruction::GOTO | 0x200,    // Block number 2
199    Instruction::GOTO | 0x100,    // Block number 3
200    Instruction::GOTO | 0xFF00);  // Block number 4
201
202  const int dominators[] = {
203    -1,
204    0,
205    1,
206    1,
207    1,
208    -1  // exit block is not dominated by any block due to the spin loop.
209  };
210
211  TestCode(data, dominators, sizeof(dominators) / sizeof(int));
212}
213
214TEST(OptimizerTest, CFG9) {
215  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
216    Instruction::CONST_4 | 0 | 0,
217    Instruction::IF_EQ, 3,        // Block number 1
218    Instruction::GOTO | 0x200,    // Block number 2
219    Instruction::GOTO | 0x100,    // Block number 3
220    Instruction::GOTO | 0xFE00);  // Block number 4
221
222  const int dominators[] = {
223    -1,
224    0,
225    1,
226    1,
227    1,
228    -1  // exit block is not dominated by any block due to the spin loop.
229  };
230
231  TestCode(data, dominators, sizeof(dominators) / sizeof(int));
232}
233
234TEST(OptimizerTest, CFG10) {
235  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
236    Instruction::CONST_4 | 0 | 0,
237    Instruction::IF_EQ, 6,  // Block number 1
238    Instruction::IF_EQ, 3,  // Block number 2
239    Instruction::GOTO | 0x100,  // Block number 3
240    Instruction::GOTO | 0x100,  // Block number 4
241    Instruction::RETURN_VOID);  // Block number 5
242
243  const int dominators[] = {
244    -1,
245    0,
246    1,
247    2,
248    2,
249    1,
250    5  // Block number 5 dominates exit block
251  };
252
253  TestCode(data, dominators, sizeof(dominators) / sizeof(int));
254}
255
256}  // namespace art
257