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