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 "builder.h"
18 #include "code_generator.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 "utils/arena_allocator.h"
25
26 #include "gtest/gtest.h"
27
28 namespace art {
29
DumpBitVector(BitVector * vector,std::ostream & buffer,size_t count,const char * prefix)30 static void DumpBitVector(BitVector* vector,
31 std::ostream& buffer,
32 size_t count,
33 const char* prefix) {
34 buffer << prefix;
35 buffer << '(';
36 for (size_t i = 0; i < count; ++i) {
37 buffer << vector->IsBitSet(i);
38 }
39 buffer << ")\n";
40 }
41
TestCode(const uint16_t * data,const char * expected)42 static void TestCode(const uint16_t* data, const char* expected) {
43 ArenaPool pool;
44 ArenaAllocator allocator(&pool);
45 HGraphBuilder builder(&allocator);
46 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
47 HGraph* graph = builder.BuildGraph(*item);
48 ASSERT_NE(graph, nullptr);
49 graph->BuildDominatorTree();
50 graph->TransformToSSA();
51 graph->FindNaturalLoops();
52 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
53 SsaLivenessAnalysis liveness(*graph, codegen);
54 liveness.Analyze();
55
56 std::ostringstream buffer;
57 for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) {
58 HBasicBlock* block = it.Current();
59 buffer << "Block " << block->GetBlockId() << std::endl;
60 size_t ssa_values = liveness.GetNumberOfSsaValues();
61 BitVector* live_in = liveness.GetLiveInSet(*block);
62 DumpBitVector(live_in, buffer, ssa_values, " live in: ");
63 BitVector* live_out = liveness.GetLiveOutSet(*block);
64 DumpBitVector(live_out, buffer, ssa_values, " live out: ");
65 BitVector* kill = liveness.GetKillSet(*block);
66 DumpBitVector(kill, buffer, ssa_values, " kill: ");
67 }
68 ASSERT_STREQ(expected, buffer.str().c_str());
69 }
70
TEST(LivenessTest,CFG1)71 TEST(LivenessTest, CFG1) {
72 const char* expected =
73 "Block 0\n"
74 " live in: (0)\n"
75 " live out: (0)\n"
76 " kill: (1)\n"
77 "Block 1\n"
78 " live in: (0)\n"
79 " live out: (0)\n"
80 " kill: (0)\n"
81 "Block 2\n"
82 " live in: (0)\n"
83 " live out: (0)\n"
84 " kill: (0)\n";
85
86 // Constant is not used.
87 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
88 Instruction::CONST_4 | 0 | 0,
89 Instruction::RETURN_VOID);
90
91 TestCode(data, expected);
92 }
93
TEST(LivenessTest,CFG2)94 TEST(LivenessTest, CFG2) {
95 const char* expected =
96 "Block 0\n"
97 " live in: (0)\n"
98 " live out: (1)\n"
99 " kill: (1)\n"
100 "Block 1\n"
101 " live in: (1)\n"
102 " live out: (0)\n"
103 " kill: (0)\n"
104 "Block 2\n"
105 " live in: (0)\n"
106 " live out: (0)\n"
107 " kill: (0)\n";
108
109 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
110 Instruction::CONST_4 | 0 | 0,
111 Instruction::RETURN);
112
113 TestCode(data, expected);
114 }
115
TEST(LivenessTest,CFG3)116 TEST(LivenessTest, CFG3) {
117 const char* expected =
118 "Block 0\n" // entry block
119 " live in: (000)\n"
120 " live out: (110)\n"
121 " kill: (110)\n"
122 "Block 1\n" // block with add
123 " live in: (110)\n"
124 " live out: (001)\n"
125 " kill: (001)\n"
126 "Block 2\n" // block with return
127 " live in: (001)\n"
128 " live out: (000)\n"
129 " kill: (000)\n"
130 "Block 3\n" // exit block
131 " live in: (000)\n"
132 " live out: (000)\n"
133 " kill: (000)\n";
134
135 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
136 Instruction::CONST_4 | 3 << 12 | 0,
137 Instruction::CONST_4 | 4 << 12 | 1 << 8,
138 Instruction::ADD_INT_2ADDR | 1 << 12,
139 Instruction::GOTO | 0x100,
140 Instruction::RETURN);
141
142 TestCode(data, expected);
143 }
144
TEST(LivenessTest,CFG4)145 TEST(LivenessTest, CFG4) {
146 // var a;
147 // if (0 == 0) {
148 // a = 5;
149 // } else {
150 // a = 4;
151 // }
152 // return a;
153 //
154 // Bitsets are made of:
155 // (constant0, constant4, constant5, phi)
156 const char* expected =
157 "Block 0\n" // entry block
158 " live in: (0000)\n"
159 " live out: (1110)\n"
160 " kill: (1110)\n"
161 "Block 1\n" // block with if
162 " live in: (1110)\n"
163 " live out: (0110)\n"
164 " kill: (0000)\n"
165 "Block 2\n" // else block
166 " live in: (0100)\n"
167 " live out: (0000)\n"
168 " kill: (0000)\n"
169 "Block 3\n" // then block
170 " live in: (0010)\n"
171 " live out: (0000)\n"
172 " kill: (0000)\n"
173 "Block 4\n" // return block
174 " live in: (0000)\n"
175 " live out: (0000)\n"
176 " kill: (0001)\n"
177 "Block 5\n" // exit block
178 " live in: (0000)\n"
179 " live out: (0000)\n"
180 " kill: (0000)\n";
181
182 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
183 Instruction::CONST_4 | 0 | 0,
184 Instruction::IF_EQ, 4,
185 Instruction::CONST_4 | 4 << 12 | 0,
186 Instruction::GOTO | 0x200,
187 Instruction::CONST_4 | 5 << 12 | 0,
188 Instruction::RETURN | 0 << 8);
189
190 TestCode(data, expected);
191 }
192
TEST(LivenessTest,CFG5)193 TEST(LivenessTest, CFG5) {
194 // var a = 0;
195 // if (0 == 0) {
196 // } else {
197 // a = 4;
198 // }
199 // return a;
200 //
201 // Bitsets are made of:
202 // (constant0, constant4, phi)
203 const char* expected =
204 "Block 0\n" // entry block
205 " live in: (000)\n"
206 " live out: (110)\n"
207 " kill: (110)\n"
208 "Block 1\n" // block with if
209 " live in: (110)\n"
210 " live out: (110)\n"
211 " kill: (000)\n"
212 "Block 2\n" // else block
213 " live in: (010)\n"
214 " live out: (000)\n"
215 " kill: (000)\n"
216 "Block 3\n" // return block
217 " live in: (000)\n"
218 " live out: (000)\n"
219 " kill: (001)\n"
220 "Block 4\n" // exit block
221 " live in: (000)\n"
222 " live out: (000)\n"
223 " kill: (000)\n"
224 "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3.
225 " live in: (100)\n"
226 " live out: (000)\n"
227 " kill: (000)\n";
228
229 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
230 Instruction::CONST_4 | 0 | 0,
231 Instruction::IF_EQ, 3,
232 Instruction::CONST_4 | 4 << 12 | 0,
233 Instruction::RETURN | 0 << 8);
234
235 TestCode(data, expected);
236 }
237
TEST(LivenessTest,Loop1)238 TEST(LivenessTest, Loop1) {
239 // Simple loop with one preheader and one back edge.
240 // var a = 0;
241 // while (a == a) {
242 // a = 4;
243 // }
244 // return;
245 // Bitsets are made of:
246 // (constant0, constant4, phi)
247 const char* expected =
248 "Block 0\n" // entry block
249 " live in: (000)\n"
250 " live out: (110)\n"
251 " kill: (110)\n"
252 "Block 1\n" // pre header
253 " live in: (110)\n"
254 " live out: (010)\n"
255 " kill: (000)\n"
256 "Block 2\n" // loop header
257 " live in: (010)\n"
258 " live out: (010)\n"
259 " kill: (001)\n"
260 "Block 3\n" // back edge
261 " live in: (010)\n"
262 " live out: (010)\n"
263 " kill: (000)\n"
264 "Block 4\n" // return block
265 " live in: (000)\n"
266 " live out: (000)\n"
267 " kill: (000)\n"
268 "Block 5\n" // exit block
269 " live in: (000)\n"
270 " live out: (000)\n"
271 " kill: (000)\n";
272
273
274 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
275 Instruction::CONST_4 | 0 | 0,
276 Instruction::IF_EQ, 4,
277 Instruction::CONST_4 | 4 << 12 | 0,
278 Instruction::GOTO | 0xFD00,
279 Instruction::RETURN_VOID);
280
281 TestCode(data, expected);
282 }
283
TEST(LivenessTest,Loop3)284 TEST(LivenessTest, Loop3) {
285 // Test that the returned value stays live in a preceding loop.
286 // var a = 0;
287 // while (a == a) {
288 // a = 4;
289 // }
290 // return 5;
291 // Bitsets are made of:
292 // (constant0, constant4, constant5, phi)
293 const char* expected =
294 "Block 0\n"
295 " live in: (0000)\n"
296 " live out: (1110)\n"
297 " kill: (1110)\n"
298 "Block 1\n"
299 " live in: (1110)\n"
300 " live out: (0110)\n"
301 " kill: (0000)\n"
302 "Block 2\n" // loop header
303 " live in: (0110)\n"
304 " live out: (0110)\n"
305 " kill: (0001)\n"
306 "Block 3\n" // back edge
307 " live in: (0110)\n"
308 " live out: (0110)\n"
309 " kill: (0000)\n"
310 "Block 4\n" // return block
311 " live in: (0010)\n"
312 " live out: (0000)\n"
313 " kill: (0000)\n"
314 "Block 5\n" // exit block
315 " live in: (0000)\n"
316 " live out: (0000)\n"
317 " kill: (0000)\n";
318
319 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
320 Instruction::CONST_4 | 0 | 0,
321 Instruction::IF_EQ, 4,
322 Instruction::CONST_4 | 4 << 12 | 0,
323 Instruction::GOTO | 0xFD00,
324 Instruction::CONST_4 | 5 << 12 | 1 << 8,
325 Instruction::RETURN | 1 << 8);
326
327 TestCode(data, expected);
328 }
329
330
TEST(LivenessTest,Loop4)331 TEST(LivenessTest, Loop4) {
332 // Make sure we support a preheader of a loop not being the first predecessor
333 // in the predecessor list of the header.
334 // var a = 0;
335 // while (a == a) {
336 // a = 4;
337 // }
338 // return a;
339 // Bitsets are made of:
340 // (constant0, constant4, phi)
341 const char* expected =
342 "Block 0\n"
343 " live in: (000)\n"
344 " live out: (110)\n"
345 " kill: (110)\n"
346 "Block 1\n"
347 " live in: (110)\n"
348 " live out: (110)\n"
349 " kill: (000)\n"
350 "Block 2\n" // loop header
351 " live in: (010)\n"
352 " live out: (011)\n"
353 " kill: (001)\n"
354 "Block 3\n" // back edge
355 " live in: (010)\n"
356 " live out: (010)\n"
357 " kill: (000)\n"
358 "Block 4\n" // pre loop header
359 " live in: (110)\n"
360 " live out: (010)\n"
361 " kill: (000)\n"
362 "Block 5\n" // return block
363 " live in: (001)\n"
364 " live out: (000)\n"
365 " kill: (000)\n"
366 "Block 6\n" // exit block
367 " live in: (000)\n"
368 " live out: (000)\n"
369 " kill: (000)\n";
370
371 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
372 Instruction::CONST_4 | 0 | 0,
373 Instruction::GOTO | 0x500,
374 Instruction::IF_EQ, 5,
375 Instruction::CONST_4 | 4 << 12 | 0,
376 Instruction::GOTO | 0xFD00,
377 Instruction::GOTO | 0xFC00,
378 Instruction::RETURN | 0 << 8);
379
380 TestCode(data, expected);
381 }
382
TEST(LivenessTest,Loop5)383 TEST(LivenessTest, Loop5) {
384 // Make sure we create a preheader of a loop when a header originally has two
385 // incoming blocks and one back edge.
386 // Bitsets are made of:
387 // (constant0, constant4, constant5, phi in block 8, phi in block 4)
388 const char* expected =
389 "Block 0\n"
390 " live in: (00000)\n"
391 " live out: (11100)\n"
392 " kill: (11100)\n"
393 "Block 1\n"
394 " live in: (11100)\n"
395 " live out: (01100)\n"
396 " kill: (00000)\n"
397 "Block 2\n"
398 " live in: (01000)\n"
399 " live out: (00000)\n"
400 " kill: (00000)\n"
401 "Block 3\n"
402 " live in: (00100)\n"
403 " live out: (00000)\n"
404 " kill: (00000)\n"
405 "Block 4\n" // loop header
406 " live in: (00000)\n"
407 " live out: (00001)\n"
408 " kill: (00001)\n"
409 "Block 5\n" // back edge
410 " live in: (00001)\n"
411 " live out: (00000)\n"
412 " kill: (00000)\n"
413 "Block 6\n" // return block
414 " live in: (00001)\n"
415 " live out: (00000)\n"
416 " kill: (00000)\n"
417 "Block 7\n" // exit block
418 " live in: (00000)\n"
419 " live out: (00000)\n"
420 " kill: (00000)\n"
421 "Block 8\n" // synthesized pre header
422 " live in: (00000)\n"
423 " live out: (00000)\n"
424 " kill: (00010)\n";
425
426 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
427 Instruction::CONST_4 | 0 | 0,
428 Instruction::IF_EQ, 4,
429 Instruction::CONST_4 | 4 << 12 | 0,
430 Instruction::GOTO | 0x200,
431 Instruction::CONST_4 | 5 << 12 | 0,
432 Instruction::IF_EQ, 3,
433 Instruction::GOTO | 0xFE00,
434 Instruction::RETURN | 0 << 8);
435
436 TestCode(data, expected);
437 }
438
TEST(LivenessTest,Loop6)439 TEST(LivenessTest, Loop6) {
440 // Bitsets are made of:
441 // (constant0, constant4, constant5, phi in block 2, phi in block 8)
442 const char* expected =
443 "Block 0\n"
444 " live in: (00000)\n"
445 " live out: (11100)\n"
446 " kill: (11100)\n"
447 "Block 1\n"
448 " live in: (11100)\n"
449 " live out: (01100)\n"
450 " kill: (00000)\n"
451 "Block 2\n" // loop header
452 " live in: (01100)\n"
453 " live out: (01110)\n"
454 " kill: (00010)\n"
455 "Block 3\n"
456 " live in: (01100)\n"
457 " live out: (01100)\n"
458 " kill: (00000)\n"
459 "Block 4\n" // original back edge
460 " live in: (01100)\n"
461 " live out: (01100)\n"
462 " kill: (00000)\n"
463 "Block 5\n" // original back edge
464 " live in: (01100)\n"
465 " live out: (01100)\n"
466 " kill: (00000)\n"
467 "Block 6\n" // return block
468 " live in: (00010)\n"
469 " live out: (00000)\n"
470 " kill: (00000)\n"
471 "Block 7\n" // exit block
472 " live in: (00000)\n"
473 " live out: (00000)\n"
474 " kill: (00000)\n"
475 "Block 8\n" // synthesized back edge
476 " live in: (01100)\n"
477 " live out: (01100)\n"
478 " kill: (00001)\n";
479
480 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
481 Instruction::CONST_4 | 0 | 0,
482 Instruction::IF_EQ, 8,
483 Instruction::CONST_4 | 4 << 12 | 0,
484 Instruction::IF_EQ, 4,
485 Instruction::CONST_4 | 5 << 12 | 0,
486 Instruction::GOTO | 0xFA00,
487 Instruction::GOTO | 0xF900,
488 Instruction::RETURN | 0 << 8);
489
490 TestCode(data, expected);
491 }
492
493
TEST(LivenessTest,Loop7)494 TEST(LivenessTest, Loop7) {
495 // Bitsets are made of:
496 // (constant0, constant4, constant5, phi in block 2, phi in block 6)
497 const char* expected =
498 "Block 0\n"
499 " live in: (00000)\n"
500 " live out: (11100)\n"
501 " kill: (11100)\n"
502 "Block 1\n"
503 " live in: (11100)\n"
504 " live out: (01100)\n"
505 " kill: (00000)\n"
506 "Block 2\n" // loop header
507 " live in: (01100)\n"
508 " live out: (01110)\n"
509 " kill: (00010)\n"
510 "Block 3\n"
511 " live in: (01100)\n"
512 " live out: (01100)\n"
513 " kill: (00000)\n"
514 "Block 4\n" // loop exit
515 " live in: (00100)\n"
516 " live out: (00000)\n"
517 " kill: (00000)\n"
518 "Block 5\n" // back edge
519 " live in: (01100)\n"
520 " live out: (01100)\n"
521 " kill: (00000)\n"
522 "Block 6\n" // return block
523 " live in: (00000)\n"
524 " live out: (00000)\n"
525 " kill: (00001)\n"
526 "Block 7\n" // exit block
527 " live in: (00000)\n"
528 " live out: (00000)\n"
529 " kill: (00000)\n"
530 "Block 8\n" // synthesized block to avoid critical edge.
531 " live in: (00010)\n"
532 " live out: (00000)\n"
533 " kill: (00000)\n";
534
535 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
536 Instruction::CONST_4 | 0 | 0,
537 Instruction::IF_EQ, 8,
538 Instruction::CONST_4 | 4 << 12 | 0,
539 Instruction::IF_EQ, 4,
540 Instruction::CONST_4 | 5 << 12 | 0,
541 Instruction::GOTO | 0x0200,
542 Instruction::GOTO | 0xF900,
543 Instruction::RETURN | 0 << 8);
544
545 TestCode(data, expected);
546 }
547
548 } // namespace art
549