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 (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 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 uint16_t data[] = ONE_REGISTER_CODE_ITEM( 89 Instruction::CONST_4 | 0 | 0, 90 Instruction::RETURN_VOID); 91 92 TestCode(data, expected); 93 } 94 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 uint16_t data[] = ONE_REGISTER_CODE_ITEM( 111 Instruction::CONST_4 | 0 | 0, 112 Instruction::RETURN); 113 114 TestCode(data, expected); 115 } 116 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
