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