blob: 9e0d352d3e9cf3e172f902cc5102c7a943067488 [file] [log] [blame]
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001/*
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
Mathieu Chartierb666f482015-02-18 14:33:14 -080017#include "base/arena_allocator.h"
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010018#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"
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010024#include "pretty_printer.h"
25
26#include "gtest/gtest.h"
27
28namespace art {
29
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +010030static HGraph* TestCode(const uint16_t* data, ArenaAllocator* allocator) {
Nicolas Geoffray0a23d742015-05-07 11:57:35 +010031 HGraph* graph = CreateGraph(allocator);
David Brazdil5e8b1372015-01-23 14:39:08 +000032 HGraphBuilder builder(graph);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010033 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
David Brazdil5e8b1372015-01-23 14:39:08 +000034 builder.BuildGraph(*item);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010035 graph->BuildDominatorTree();
Nicolas Geoffrayf5370122014-12-02 11:51:19 +000036 graph->AnalyzeNaturalLoops();
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010037 return graph;
38}
39
40TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +010047 ArenaAllocator allocator(&arena);
48 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +010049 for (HBasicBlock* block : graph->GetBlocks()) {
50 ASSERT_EQ(block->GetLoopInformation(), nullptr);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010051 }
52}
53
54TEST(FindLoopsTest, CFG2) {
55 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
56 Instruction::CONST_4 | 0 | 0,
57 Instruction::RETURN);
58
59 ArenaPool arena;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +010060 ArenaAllocator allocator(&arena);
61 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +010062 for (HBasicBlock* block : graph->GetBlocks()) {
63 ASSERT_EQ(block->GetLoopInformation(), nullptr);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010064 }
65}
66
67TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +010076 ArenaAllocator allocator(&arena);
77 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +010078 for (HBasicBlock* block : graph->GetBlocks()) {
79 ASSERT_EQ(block->GetLoopInformation(), nullptr);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010080 }
81}
82
83TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +010093 ArenaAllocator allocator(&arena);
94 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +010095 for (HBasicBlock* block : graph->GetBlocks()) {
96 ASSERT_EQ(block->GetLoopInformation(), nullptr);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010097 }
98}
99
100TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100108 ArenaAllocator allocator(&arena);
109 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100110 for (HBasicBlock* block : graph->GetBlocks()) {
111 ASSERT_EQ(block->GetLoopInformation(), nullptr);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100112 }
113}
114
115static void TestBlock(HGraph* graph,
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100116 uint32_t block_id,
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100117 bool is_loop_header,
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100118 uint32_t parent_loop_header_id,
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100119 const int* blocks_in_loop = nullptr,
120 size_t number_of_blocks = 0) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100121 HBasicBlock* block = graph->GetBlock(block_id);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100122 ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100123 if (parent_loop_header_id == kInvalidBlockId) {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100124 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
141TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100154 ArenaAllocator allocator(&arena);
155 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100156
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100157 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
158 TestBlock(graph, 1, false, kInvalidBlockId); // pre header
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100159 const int blocks2[] = {2, 3};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100160 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
161 TestBlock(graph, 3, false, 2); // block in loop
162 TestBlock(graph, 4, false, kInvalidBlockId); // return block
163 TestBlock(graph, 5, false, kInvalidBlockId); // exit block
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100164}
165
166TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100182 ArenaAllocator allocator(&arena);
183 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100184
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100185 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
186 TestBlock(graph, 1, false, kInvalidBlockId); // goto block
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100187 const int blocks2[] = {2, 3};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100188 TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
189 TestBlock(graph, 3, false, 2); // block in loop
190 TestBlock(graph, 4, false, kInvalidBlockId); // pre header
191 TestBlock(graph, 5, false, kInvalidBlockId); // return block
192 TestBlock(graph, 6, false, kInvalidBlockId); // exit block
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100193}
194
195TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100207 ArenaAllocator allocator(&arena);
208 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100209
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100210 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
211 TestBlock(graph, 1, false, kInvalidBlockId); // goto block
212 TestBlock(graph, 2, false, kInvalidBlockId);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100213 const int blocks2[] = {3, 4};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100214 TestBlock(graph, 3, true, 3, blocks2, 2); // loop header
215 TestBlock(graph, 4, false, 3); // block in loop
216 TestBlock(graph, 5, false, kInvalidBlockId); // pre header
217 TestBlock(graph, 6, false, kInvalidBlockId); // return block
218 TestBlock(graph, 7, false, kInvalidBlockId); // exit block
219 TestBlock(graph, 8, false, kInvalidBlockId); // synthesized pre header
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100220}
221
222TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100233 ArenaAllocator allocator(&arena);
234 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100235
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100236 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
237 TestBlock(graph, 1, false, kInvalidBlockId); // pre header
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100238 const int blocks2[] = {2, 3, 4, 5};
239 TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2)); // loop header
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100240 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, kInvalidBlockId); // return block
244 TestBlock(graph, 7, false, kInvalidBlockId); // exit block
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100245}
246
247
248TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100259 ArenaAllocator allocator(&arena);
260 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100261
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100262 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
263 TestBlock(graph, 1, false, kInvalidBlockId); // pre header
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100264 const int blocks2[] = {2, 3, 5};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100265 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
266 TestBlock(graph, 3, false, 2); // block in loop
267 TestBlock(graph, 4, false, kInvalidBlockId); // loop exit
268 TestBlock(graph, 5, false, 2); // back edge
269 TestBlock(graph, 6, false, kInvalidBlockId); // return block
270 TestBlock(graph, 7, false, kInvalidBlockId); // exit block
271 TestBlock(graph, 8, false, kInvalidBlockId); // synthesized block at the loop exit
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100272}
273
274TEST(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
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100283 ArenaPool arena;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100284 ArenaAllocator allocator(&arena);
285 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100286
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100287 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
288 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of outer loop
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100289 const int blocks2[] = {2, 3, 4, 5, 8};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100290 TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100291 const int blocks3[] = {3, 4};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100292 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, kInvalidBlockId); // return block
296 TestBlock(graph, 7, false, kInvalidBlockId); // exit block
297 TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100298
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100299 ASSERT_TRUE(graph->GetBlock(3)->GetLoopInformation()->IsIn(
300 *graph->GetBlock(2)->GetLoopInformation()));
301 ASSERT_FALSE(graph->GetBlock(2)->GetLoopInformation()->IsIn(
302 *graph->GetBlock(3)->GetLoopInformation()));
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100303}
304
305TEST(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
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100314 ArenaPool arena;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100315 ArenaAllocator allocator(&arena);
316 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100317
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100318 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
319 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100320 const int blocks2[] = {2, 3};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100321 TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header
322 TestBlock(graph, 3, false, 2); // back edge of first loop
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100323 const int blocks4[] = {4, 5};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100324 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, kInvalidBlockId); // return block
327 TestBlock(graph, 7, false, kInvalidBlockId); // exit block
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100328
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100329 ASSERT_FALSE(graph->GetBlock(4)->GetLoopInformation()->IsIn(
330 *graph->GetBlock(2)->GetLoopInformation()));
331 ASSERT_FALSE(graph->GetBlock(2)->GetLoopInformation()->IsIn(
332 *graph->GetBlock(4)->GetLoopInformation()));
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100333}
334
335TEST(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;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100345 ArenaAllocator allocator(&arena);
346 HGraph* graph = TestCode(data, &allocator);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100347 ASSERT_TRUE(graph->GetBlock(3)->IsLoopHeader());
348 HLoopInformation* info = graph->GetBlock(3)->GetLoopInformation();
349 ASSERT_EQ(1u, info->NumberOfBackEdges());
350 ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges()[0]));
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100351}
352
353TEST(FindLoopsTest, DoWhileLoop) {
354 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
355 Instruction::CONST_4 | 0 | 0,
356 Instruction::GOTO | 0x0100,
357 Instruction::IF_EQ, 0xFFFF,
358 Instruction::RETURN | 0 << 8);
359
360 ArenaPool arena;
Nicolas Geoffraye6c96d12014-09-10 10:34:01 +0100361 ArenaAllocator allocator(&arena);
362 HGraph* graph = TestCode(data, &allocator);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100363
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100364 TestBlock(graph, 0, false, kInvalidBlockId); // entry block
365 TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100366 const int blocks2[] = {2, 3, 6};
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100367 TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
368 TestBlock(graph, 3, false, 2); // back edge of first loop
369 TestBlock(graph, 4, false, kInvalidBlockId); // return block
370 TestBlock(graph, 5, false, kInvalidBlockId); // exit block
371 TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100372}
373
374} // namespace art