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