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