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