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