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 std::unique_ptr<CompilerOptions> compiler_options =
51 CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
52 PrepareForRegisterAllocation(graph, *compiler_options).Run();
53 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options);
54 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
55 liveness.Analyze();
56
57 std::ostringstream buffer;
58 for (HBasicBlock* block : graph->GetBlocks()) {
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_F(LivenessTest,CFG1)71 TEST_F(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 std::vector<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_F(LivenessTest,CFG2)94 TEST_F(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 std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
110 Instruction::CONST_4 | 0 | 0,
111 Instruction::RETURN);
112
113 TestCode(data, expected);
114 }
115
TEST_F(LivenessTest,CFG3)116 TEST_F(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 std::vector<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_F(LivenessTest,CFG4)145 TEST_F(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, constant5, constant4, 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: (0010)\n"
167 " live out: (0000)\n"
168 " kill: (0000)\n"
169 "Block 3\n" // then block
170 " live in: (0100)\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 std::vector<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_F(LivenessTest,CFG5)193 TEST_F(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 std::vector<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_F(LivenessTest,Loop1)238 TEST_F(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 std::vector<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_F(LivenessTest,Loop3)284 TEST_F(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, constant5, constant4, 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: (0100)\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 std::vector<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_F(LivenessTest,Loop4)331 TEST_F(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 std::vector<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_F(LivenessTest,Loop5)383 TEST_F(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, constant5, constant4, phi in block 8)
388 const char* expected =
389 "Block 0\n"
390 " live in: (0000)\n"
391 " live out: (1110)\n"
392 " kill: (1110)\n"
393 "Block 1\n"
394 " live in: (1110)\n"
395 " live out: (0110)\n"
396 " kill: (0000)\n"
397 "Block 2\n"
398 " live in: (0010)\n"
399 " live out: (0000)\n"
400 " kill: (0000)\n"
401 "Block 3\n"
402 " live in: (0100)\n"
403 " live out: (0000)\n"
404 " kill: (0000)\n"
405 "Block 4\n" // loop header
406 " live in: (0001)\n"
407 " live out: (0001)\n"
408 " kill: (0000)\n"
409 "Block 5\n" // back edge
410 " live in: (0001)\n"
411 " live out: (0001)\n"
412 " kill: (0000)\n"
413 "Block 6\n" // return block
414 " live in: (0001)\n"
415 " live out: (0000)\n"
416 " kill: (0000)\n"
417 "Block 7\n" // exit block
418 " live in: (0000)\n"
419 " live out: (0000)\n"
420 " kill: (0000)\n"
421 "Block 8\n" // synthesized pre header
422 " live in: (0000)\n"
423 " live out: (0001)\n"
424 " kill: (0001)\n";
425
426 const std::vector<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_F(LivenessTest,Loop6)439 TEST_F(LivenessTest, Loop6) {
440 // Bitsets are made of:
441 // (constant0, constant4, constant5, phi in block 2)
442 const char* expected =
443 "Block 0\n"
444 " live in: (0000)\n"
445 " live out: (1110)\n"
446 " kill: (1110)\n"
447 "Block 1\n"
448 " live in: (1110)\n"
449 " live out: (0110)\n"
450 " kill: (0000)\n"
451 "Block 2\n" // loop header
452 " live in: (0110)\n"
453 " live out: (0111)\n"
454 " kill: (0001)\n"
455 "Block 3\n"
456 " live in: (0110)\n"
457 " live out: (0110)\n"
458 " kill: (0000)\n"
459 "Block 4\n" // back edge
460 " live in: (0110)\n"
461 " live out: (0110)\n"
462 " kill: (0000)\n"
463 "Block 5\n" // back edge
464 " live in: (0110)\n"
465 " live out: (0110)\n"
466 " kill: (0000)\n"
467 "Block 6\n" // return block
468 " live in: (0001)\n"
469 " live out: (0000)\n"
470 " kill: (0000)\n"
471 "Block 7\n" // exit block
472 " live in: (0000)\n"
473 " live out: (0000)\n"
474 " kill: (0000)\n";
475
476 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
477 Instruction::CONST_4 | 0 | 0,
478 Instruction::IF_EQ, 8,
479 Instruction::CONST_4 | 4 << 12 | 0,
480 Instruction::IF_EQ, 4,
481 Instruction::CONST_4 | 5 << 12 | 0,
482 Instruction::GOTO | 0xFA00,
483 Instruction::GOTO | 0xF900,
484 Instruction::RETURN | 0 << 8);
485
486 TestCode(data, expected);
487 }
488
489
TEST_F(LivenessTest,Loop7)490 TEST_F(LivenessTest, Loop7) {
491 // Bitsets are made of:
492 // (constant0, constant4, constant5, phi in block 2, phi in block 6)
493 const char* expected =
494 "Block 0\n"
495 " live in: (00000)\n"
496 " live out: (11100)\n"
497 " kill: (11100)\n"
498 "Block 1\n"
499 " live in: (11100)\n"
500 " live out: (01100)\n"
501 " kill: (00000)\n"
502 "Block 2\n" // loop header
503 " live in: (01100)\n"
504 " live out: (01110)\n"
505 " kill: (00010)\n"
506 "Block 3\n"
507 " live in: (01100)\n"
508 " live out: (01100)\n"
509 " kill: (00000)\n"
510 "Block 4\n" // loop exit
511 " live in: (00100)\n"
512 " live out: (00000)\n"
513 " kill: (00000)\n"
514 "Block 5\n" // back edge
515 " live in: (01100)\n"
516 " live out: (01100)\n"
517 " kill: (00000)\n"
518 "Block 6\n" // return block
519 " live in: (00000)\n"
520 " live out: (00000)\n"
521 " kill: (00001)\n"
522 "Block 7\n" // exit block
523 " live in: (00000)\n"
524 " live out: (00000)\n"
525 " kill: (00000)\n"
526 "Block 8\n" // synthesized block to avoid critical edge.
527 " live in: (00010)\n"
528 " live out: (00000)\n"
529 " kill: (00000)\n";
530
531 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
532 Instruction::CONST_4 | 0 | 0,
533 Instruction::IF_EQ, 8,
534 Instruction::CONST_4 | 4 << 12 | 0,
535 Instruction::IF_EQ, 4,
536 Instruction::CONST_4 | 5 << 12 | 0,
537 Instruction::GOTO | 0x0200,
538 Instruction::GOTO | 0xF900,
539 Instruction::RETURN | 0 << 8);
540
541 TestCode(data, expected);
542 }
543
TEST_F(LivenessTest,Loop8)544 TEST_F(LivenessTest, Loop8) {
545 // var a = 0;
546 // while (a == a) {
547 // a = a + a;
548 // }
549 // return a;
550 //
551 // We want to test that the ins of the loop exit
552 // does contain the phi.
553 // Bitsets are made of:
554 // (constant0, phi, add)
555 const char* expected =
556 "Block 0\n"
557 " live in: (000)\n"
558 " live out: (100)\n"
559 " kill: (100)\n"
560 "Block 1\n" // pre loop header
561 " live in: (100)\n"
562 " live out: (000)\n"
563 " kill: (000)\n"
564 "Block 2\n" // loop header
565 " live in: (000)\n"
566 " live out: (010)\n"
567 " kill: (010)\n"
568 "Block 3\n" // back edge
569 " live in: (010)\n"
570 " live out: (000)\n"
571 " kill: (001)\n"
572 "Block 4\n" // return block
573 " live in: (010)\n"
574 " live out: (000)\n"
575 " kill: (000)\n"
576 "Block 5\n" // exit block
577 " live in: (000)\n"
578 " live out: (000)\n"
579 " kill: (000)\n";
580
581 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
582 Instruction::CONST_4 | 0 | 0,
583 Instruction::IF_EQ, 6,
584 Instruction::ADD_INT, 0, 0,
585 Instruction::GOTO | 0xFB00,
586 Instruction::RETURN | 0 << 8);
587
588 TestCode(data, expected);
589 }
590
591 } // namespace art
592