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