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