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