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_file.h"
19 #include "dex_instruction.h"
20 #include "nodes.h"
21 #include "optimizing_unit_test.h"
22 #include "ssa_liveness_analysis.h"
23 #include "utils/arena_allocator.h"
24 #include "pretty_printer.h"
25
26 #include "gtest/gtest.h"
27
28 namespace art {
29
TestCode(const uint16_t * data,ArenaPool * pool)30 static HGraph* TestCode(const uint16_t* data, ArenaPool* pool) {
31 ArenaAllocator allocator(pool);
32 HGraphBuilder builder(&allocator);
33 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
34 HGraph* graph = builder.BuildGraph(*item);
35 graph->BuildDominatorTree();
36 graph->FindNaturalLoops();
37 return graph;
38 }
39
TEST(FindLoopsTest,CFG1)40 TEST(FindLoopsTest, CFG1) {
41 // Constant is not used.
42 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
43 Instruction::CONST_4 | 0 | 0,
44 Instruction::RETURN_VOID);
45
46 ArenaPool arena;
47 HGraph* graph = TestCode(data, &arena);
48 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
49 ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
50 }
51 }
52
TEST(FindLoopsTest,CFG2)53 TEST(FindLoopsTest, CFG2) {
54 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
55 Instruction::CONST_4 | 0 | 0,
56 Instruction::RETURN);
57
58 ArenaPool arena;
59 HGraph* graph = TestCode(data, &arena);
60 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
61 ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
62 }
63 }
64
TEST(FindLoopsTest,CFG3)65 TEST(FindLoopsTest, CFG3) {
66 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
67 Instruction::CONST_4 | 3 << 12 | 0,
68 Instruction::CONST_4 | 4 << 12 | 1 << 8,
69 Instruction::ADD_INT_2ADDR | 1 << 12,
70 Instruction::GOTO | 0x100,
71 Instruction::RETURN);
72
73 ArenaPool arena;
74 HGraph* graph = TestCode(data, &arena);
75 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
76 ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
77 }
78 }
79
TEST(FindLoopsTest,CFG4)80 TEST(FindLoopsTest, CFG4) {
81 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
82 Instruction::CONST_4 | 0 | 0,
83 Instruction::IF_EQ, 4,
84 Instruction::CONST_4 | 4 << 12 | 0,
85 Instruction::GOTO | 0x200,
86 Instruction::CONST_4 | 5 << 12 | 0,
87 Instruction::RETURN | 0 << 8);
88
89 ArenaPool arena;
90 HGraph* graph = TestCode(data, &arena);
91 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
92 ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
93 }
94 }
95
TEST(FindLoopsTest,CFG5)96 TEST(FindLoopsTest, CFG5) {
97 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
98 Instruction::CONST_4 | 0 | 0,
99 Instruction::IF_EQ, 3,
100 Instruction::CONST_4 | 4 << 12 | 0,
101 Instruction::RETURN | 0 << 8);
102
103 ArenaPool arena;
104 HGraph* graph = TestCode(data, &arena);
105 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
106 ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
107 }
108 }
109
TestBlock(HGraph * graph,int block_id,bool is_loop_header,int parent_loop_header_id,const int * blocks_in_loop=nullptr,size_t number_of_blocks=0)110 static void TestBlock(HGraph* graph,
111 int block_id,
112 bool is_loop_header,
113 int parent_loop_header_id,
114 const int* blocks_in_loop = nullptr,
115 size_t number_of_blocks = 0) {
116 HBasicBlock* block = graph->GetBlocks().Get(block_id);
117 ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
118 if (parent_loop_header_id == -1) {
119 ASSERT_EQ(block->GetLoopInformation(), nullptr);
120 } else {
121 ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
122 }
123
124 if (blocks_in_loop != nullptr) {
125 HLoopInformation* info = block->GetLoopInformation();
126 const BitVector& blocks = info->GetBlocks();
127 ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
128 for (size_t i = 0; i < number_of_blocks; ++i) {
129 ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
130 }
131 } else {
132 ASSERT_FALSE(block->IsLoopHeader());
133 }
134 }
135
TEST(FindLoopsTest,Loop1)136 TEST(FindLoopsTest, Loop1) {
137 // Simple loop with one preheader and one back edge.
138 // var a = 0;
139 // while (a == a) {
140 // }
141 // return;
142 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
143 Instruction::CONST_4 | 0 | 0,
144 Instruction::IF_EQ, 3,
145 Instruction::GOTO | 0xFE00,
146 Instruction::RETURN_VOID);
147
148 ArenaPool arena;
149 HGraph* graph = TestCode(data, &arena);
150
151 TestBlock(graph, 0, false, -1); // entry block
152 TestBlock(graph, 1, false, -1); // pre header
153 const int blocks2[] = {2, 3};
154 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
155 TestBlock(graph, 3, false, 2); // block in loop
156 TestBlock(graph, 4, false, -1); // return block
157 TestBlock(graph, 5, false, -1); // exit block
158 }
159
TEST(FindLoopsTest,Loop2)160 TEST(FindLoopsTest, Loop2) {
161 // Make sure we support a preheader of a loop not being the first predecessor
162 // in the predecessor list of the header.
163 // var a = 0;
164 // while (a == a) {
165 // }
166 // return a;
167 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
168 Instruction::CONST_4 | 0 | 0,
169 Instruction::GOTO | 0x400,
170 Instruction::IF_EQ, 4,
171 Instruction::GOTO | 0xFE00,
172 Instruction::GOTO | 0xFD00,
173 Instruction::RETURN | 0 << 8);
174
175 ArenaPool arena;
176 HGraph* graph = TestCode(data, &arena);
177
178 TestBlock(graph, 0, false, -1); // entry block
179 TestBlock(graph, 1, false, -1); // goto block
180 const int blocks2[] = {2, 3};
181 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
182 TestBlock(graph, 3, false, 2); // block in loop
183 TestBlock(graph, 4, false, -1); // pre header
184 TestBlock(graph, 5, false, -1); // return block
185 TestBlock(graph, 6, false, -1); // exit block
186 }
187
TEST(FindLoopsTest,Loop3)188 TEST(FindLoopsTest, Loop3) {
189 // Make sure we create a preheader of a loop when a header originally has two
190 // incoming blocks and one back edge.
191 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
192 Instruction::CONST_4 | 0 | 0,
193 Instruction::IF_EQ, 3,
194 Instruction::GOTO | 0x100,
195 Instruction::IF_EQ, 3,
196 Instruction::GOTO | 0xFE00,
197 Instruction::RETURN | 0 << 8);
198
199 ArenaPool arena;
200 HGraph* graph = TestCode(data, &arena);
201
202 TestBlock(graph, 0, false, -1); // entry block
203 TestBlock(graph, 1, false, -1); // goto block
204 TestBlock(graph, 2, false, -1);
205 const int blocks2[] = {3, 4};
206 TestBlock(graph, 3, true, 3, blocks2, 2); // loop header
207 TestBlock(graph, 4, false, 3); // block in loop
208 TestBlock(graph, 5, false, -1); // pre header
209 TestBlock(graph, 6, false, -1); // return block
210 TestBlock(graph, 7, false, -1); // exit block
211 TestBlock(graph, 8, false, -1); // synthesized pre header
212 }
213
TEST(FindLoopsTest,Loop4)214 TEST(FindLoopsTest, Loop4) {
215 // Test loop with originally two back edges.
216 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
217 Instruction::CONST_4 | 0 | 0,
218 Instruction::IF_EQ, 6,
219 Instruction::IF_EQ, 3,
220 Instruction::GOTO | 0xFC00,
221 Instruction::GOTO | 0xFB00,
222 Instruction::RETURN | 0 << 8);
223
224 ArenaPool arena;
225 HGraph* graph = TestCode(data, &arena);
226
227 TestBlock(graph, 0, false, -1); // entry block
228 TestBlock(graph, 1, false, -1); // pre header
229 const int blocks2[] = {2, 3, 4, 5, 8};
230 TestBlock(graph, 2, true, 2, blocks2, 5); // loop header
231 TestBlock(graph, 3, false, 2); // block in loop
232 TestBlock(graph, 4, false, 2); // original back edge
233 TestBlock(graph, 5, false, 2); // original back edge
234 TestBlock(graph, 6, false, -1); // return block
235 TestBlock(graph, 7, false, -1); // exit block
236 TestBlock(graph, 8, false, 2); // synthesized back edge
237 }
238
239
TEST(FindLoopsTest,Loop5)240 TEST(FindLoopsTest, Loop5) {
241 // Test loop with two exit edges.
242 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
243 Instruction::CONST_4 | 0 | 0,
244 Instruction::IF_EQ, 6,
245 Instruction::IF_EQ, 3,
246 Instruction::GOTO | 0x0200,
247 Instruction::GOTO | 0xFB00,
248 Instruction::RETURN | 0 << 8);
249
250 ArenaPool arena;
251 HGraph* graph = TestCode(data, &arena);
252
253 TestBlock(graph, 0, false, -1); // entry block
254 TestBlock(graph, 1, false, -1); // pre header
255 const int blocks2[] = {2, 3, 5};
256 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
257 TestBlock(graph, 3, false, 2); // block in loop
258 TestBlock(graph, 4, false, -1); // loop exit
259 TestBlock(graph, 5, false, 2); // back edge
260 TestBlock(graph, 6, false, -1); // return block
261 TestBlock(graph, 7, false, -1); // exit block
262 TestBlock(graph, 8, false, -1); // synthesized block at the loop exit
263 }
264
TEST(FindLoopsTest,InnerLoop)265 TEST(FindLoopsTest, InnerLoop) {
266 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
267 Instruction::CONST_4 | 0 | 0,
268 Instruction::IF_EQ, 6,
269 Instruction::IF_EQ, 3,
270 Instruction::GOTO | 0xFE00, // inner loop
271 Instruction::GOTO | 0xFB00,
272 Instruction::RETURN | 0 << 8);
273
274
275 ArenaPool arena;
276 HGraph* graph = TestCode(data, &arena);
277
278 TestBlock(graph, 0, false, -1); // entry block
279 TestBlock(graph, 1, false, -1); // pre header of outer loop
280 const int blocks2[] = {2, 3, 4, 5, 8};
281 TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header
282 const int blocks3[] = {3, 4};
283 TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header
284 TestBlock(graph, 4, false, 3); // back edge on inner loop
285 TestBlock(graph, 5, false, 2); // back edge on outer loop
286 TestBlock(graph, 6, false, -1); // return block
287 TestBlock(graph, 7, false, -1); // exit block
288 TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop
289
290 ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
291 *graph->GetBlocks().Get(2)->GetLoopInformation()));
292 ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
293 *graph->GetBlocks().Get(3)->GetLoopInformation()));
294 }
295
TEST(FindLoopsTest,TwoLoops)296 TEST(FindLoopsTest, TwoLoops) {
297 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
298 Instruction::CONST_4 | 0 | 0,
299 Instruction::IF_EQ, 3,
300 Instruction::GOTO | 0xFE00, // first loop
301 Instruction::IF_EQ, 3,
302 Instruction::GOTO | 0xFE00, // second loop
303 Instruction::RETURN | 0 << 8);
304
305
306 ArenaPool arena;
307 HGraph* graph = TestCode(data, &arena);
308
309 TestBlock(graph, 0, false, -1); // entry block
310 TestBlock(graph, 1, false, -1); // pre header of first loop
311 const int blocks2[] = {2, 3};
312 TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header
313 TestBlock(graph, 3, false, 2); // back edge of first loop
314 const int blocks4[] = {4, 5};
315 TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header
316 TestBlock(graph, 5, false, 4); // back edge of second loop
317 TestBlock(graph, 6, false, -1); // return block
318 TestBlock(graph, 7, false, -1); // exit block
319
320 ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
321 *graph->GetBlocks().Get(2)->GetLoopInformation()));
322 ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
323 *graph->GetBlocks().Get(4)->GetLoopInformation()));
324 }
325
TEST(FindLoopsTest,NonNaturalLoop)326 TEST(FindLoopsTest, NonNaturalLoop) {
327 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
328 Instruction::CONST_4 | 0 | 0,
329 Instruction::IF_EQ, 3,
330 Instruction::GOTO | 0x0100,
331 Instruction::IF_EQ, 3,
332 Instruction::GOTO | 0xFD00,
333 Instruction::RETURN | 0 << 8);
334
335 ArenaPool arena;
336 HGraph* graph = TestCode(data, &arena);
337 ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
338 HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
339 ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
340 }
341
TEST(FindLoopsTest,DoWhileLoop)342 TEST(FindLoopsTest, DoWhileLoop) {
343 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
344 Instruction::CONST_4 | 0 | 0,
345 Instruction::GOTO | 0x0100,
346 Instruction::IF_EQ, 0xFFFF,
347 Instruction::RETURN | 0 << 8);
348
349 ArenaPool arena;
350 HGraph* graph = TestCode(data, &arena);
351
352 TestBlock(graph, 0, false, -1); // entry block
353 TestBlock(graph, 1, false, -1); // pre header of first loop
354 const int blocks2[] = {2, 3, 6};
355 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
356 TestBlock(graph, 3, false, 2); // back edge of first loop
357 TestBlock(graph, 4, false, -1); // return block
358 TestBlock(graph, 5, false, -1); // exit block
359 TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge
360 }
361
362 } // namespace art
363