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 namespace art { 31 32 class LivenessTest : public CommonCompilerTest {}; 33 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 46 static void TestCode(const uint16_t* data, const char* expected) { 47 ArenaPool pool; 48 ArenaAllocator allocator(&pool); 49 HGraph* graph = CreateCFG(&allocator, data); 50 // `Inline` conditions into ifs. 51 PrepareForRegisterAllocation(graph).Run(); 52 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 53 X86InstructionSetFeatures::FromCppDefines()); 54 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 55 SsaLivenessAnalysis liveness(graph, &codegen); 56 liveness.Analyze(); 57 58 std::ostringstream buffer; 59 for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) { 60 HBasicBlock* block = it.Current(); 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 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 uint16_t data[] = ONE_REGISTER_CODE_ITEM( 90 Instruction::CONST_4 | 0 | 0, 91 Instruction::RETURN_VOID); 92 93 TestCode(data, expected); 94 } 95 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 uint16_t data[] = ONE_REGISTER_CODE_ITEM( 112 Instruction::CONST_4 | 0 | 0, 113 Instruction::RETURN); 114 115 TestCode(data, expected); 116 } 117 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
