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