1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/compiler/instruction.h" 6 #include "src/compiler/instruction-codes.h" 7 #include "src/compiler/jump-threading.h" 8 #include "test/cctest/cctest.h" 9 10 namespace v8 { 11 namespace internal { 12 namespace compiler { 13 14 class TestCode : public HandleAndZoneScope { 15 public: 16 TestCode() 17 : HandleAndZoneScope(), 18 blocks_(main_zone()), 19 sequence_(main_isolate(), main_zone(), &blocks_), 20 rpo_number_(RpoNumber::FromInt(0)), 21 current_(NULL) {} 22 23 ZoneVector<InstructionBlock*> blocks_; 24 InstructionSequence sequence_; 25 RpoNumber rpo_number_; 26 InstructionBlock* current_; 27 28 int Jump(int target) { 29 Start(); 30 InstructionOperand ops[] = {UseRpo(target)}; 31 sequence_.AddInstruction( 32 Instruction::New(main_zone(), kArchJmp, 0, NULL, 1, ops, 0, NULL)); 33 int pos = static_cast<int>(sequence_.instructions().size() - 1); 34 End(); 35 return pos; 36 } 37 void Fallthru() { 38 Start(); 39 End(); 40 } 41 int Branch(int ttarget, int ftarget) { 42 Start(); 43 InstructionOperand ops[] = {UseRpo(ttarget), UseRpo(ftarget)}; 44 InstructionCode code = 119 | FlagsModeField::encode(kFlags_branch) | 45 FlagsConditionField::encode(kEqual); 46 sequence_.AddInstruction( 47 Instruction::New(main_zone(), code, 0, NULL, 2, ops, 0, NULL)); 48 int pos = static_cast<int>(sequence_.instructions().size() - 1); 49 End(); 50 return pos; 51 } 52 void Nop() { 53 Start(); 54 sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop)); 55 } 56 void RedundantMoves() { 57 Start(); 58 sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop)); 59 int index = static_cast<int>(sequence_.instructions().size()) - 1; 60 AddGapMove(index, AllocatedOperand(LocationOperand::REGISTER, 61 MachineRepresentation::kWord32, 13), 62 AllocatedOperand(LocationOperand::REGISTER, 63 MachineRepresentation::kWord32, 13)); 64 } 65 void NonRedundantMoves() { 66 Start(); 67 sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop)); 68 int index = static_cast<int>(sequence_.instructions().size()) - 1; 69 AddGapMove(index, ConstantOperand(11), 70 AllocatedOperand(LocationOperand::REGISTER, 71 MachineRepresentation::kWord32, 11)); 72 } 73 void Other() { 74 Start(); 75 sequence_.AddInstruction(Instruction::New(main_zone(), 155)); 76 } 77 void End() { 78 Start(); 79 sequence_.EndBlock(current_->rpo_number()); 80 current_ = NULL; 81 rpo_number_ = RpoNumber::FromInt(rpo_number_.ToInt() + 1); 82 } 83 InstructionOperand UseRpo(int num) { 84 return sequence_.AddImmediate(Constant(RpoNumber::FromInt(num))); 85 } 86 void Start(bool deferred = false) { 87 if (current_ == NULL) { 88 current_ = new (main_zone()) 89 InstructionBlock(main_zone(), rpo_number_, RpoNumber::Invalid(), 90 RpoNumber::Invalid(), deferred, false); 91 blocks_.push_back(current_); 92 sequence_.StartBlock(rpo_number_); 93 } 94 } 95 void Defer() { 96 CHECK(current_ == NULL); 97 Start(true); 98 } 99 void AddGapMove(int index, const InstructionOperand& from, 100 const InstructionOperand& to) { 101 sequence_.InstructionAt(index) 102 ->GetOrCreateParallelMove(Instruction::START, main_zone()) 103 ->AddMove(from, to); 104 } 105 }; 106 107 108 void VerifyForwarding(TestCode& code, int count, int* expected) { 109 Zone local_zone; 110 ZoneVector<RpoNumber> result(&local_zone); 111 JumpThreading::ComputeForwarding(&local_zone, result, &code.sequence_); 112 113 CHECK(count == static_cast<int>(result.size())); 114 for (int i = 0; i < count; i++) { 115 CHECK(expected[i] == result[i].ToInt()); 116 } 117 } 118 119 120 TEST(FwEmpty1) { 121 TestCode code; 122 123 // B0 124 code.Jump(1); 125 // B1 126 code.Jump(2); 127 // B2 128 code.End(); 129 130 static int expected[] = {2, 2, 2}; 131 VerifyForwarding(code, 3, expected); 132 } 133 134 135 TEST(FwEmptyN) { 136 for (int i = 0; i < 9; i++) { 137 TestCode code; 138 139 // B0 140 code.Jump(1); 141 // B1 142 for (int j = 0; j < i; j++) code.Nop(); 143 code.Jump(2); 144 // B2 145 code.End(); 146 147 static int expected[] = {2, 2, 2}; 148 VerifyForwarding(code, 3, expected); 149 } 150 } 151 152 153 TEST(FwNone1) { 154 TestCode code; 155 156 // B0 157 code.End(); 158 159 static int expected[] = {0}; 160 VerifyForwarding(code, 1, expected); 161 } 162 163 164 TEST(FwMoves1) { 165 TestCode code; 166 167 // B0 168 code.RedundantMoves(); 169 code.End(); 170 171 static int expected[] = {0}; 172 VerifyForwarding(code, 1, expected); 173 } 174 175 176 TEST(FwMoves2) { 177 TestCode code; 178 179 // B0 180 code.RedundantMoves(); 181 code.Fallthru(); 182 // B1 183 code.End(); 184 185 static int expected[] = {1, 1}; 186 VerifyForwarding(code, 2, expected); 187 } 188 189 190 TEST(FwMoves2b) { 191 TestCode code; 192 193 // B0 194 code.NonRedundantMoves(); 195 code.Fallthru(); 196 // B1 197 code.End(); 198 199 static int expected[] = {0, 1}; 200 VerifyForwarding(code, 2, expected); 201 } 202 203 204 TEST(FwOther2) { 205 TestCode code; 206 207 // B0 208 code.Other(); 209 code.Fallthru(); 210 // B1 211 code.End(); 212 213 static int expected[] = {0, 1}; 214 VerifyForwarding(code, 2, expected); 215 } 216 217 218 TEST(FwNone2a) { 219 TestCode code; 220 221 // B0 222 code.Fallthru(); 223 // B1 224 code.End(); 225 226 static int expected[] = {1, 1}; 227 VerifyForwarding(code, 2, expected); 228 } 229 230 231 TEST(FwNone2b) { 232 TestCode code; 233 234 // B0 235 code.Jump(1); 236 // B1 237 code.End(); 238 239 static int expected[] = {1, 1}; 240 VerifyForwarding(code, 2, expected); 241 } 242 243 244 TEST(FwLoop1) { 245 TestCode code; 246 247 // B0 248 code.Jump(0); 249 250 static int expected[] = {0}; 251 VerifyForwarding(code, 1, expected); 252 } 253 254 255 TEST(FwLoop2) { 256 TestCode code; 257 258 // B0 259 code.Fallthru(); 260 // B1 261 code.Jump(0); 262 263 static int expected[] = {0, 0}; 264 VerifyForwarding(code, 2, expected); 265 } 266 267 268 TEST(FwLoop3) { 269 TestCode code; 270 271 // B0 272 code.Fallthru(); 273 // B1 274 code.Fallthru(); 275 // B2 276 code.Jump(0); 277 278 static int expected[] = {0, 0, 0}; 279 VerifyForwarding(code, 3, expected); 280 } 281 282 283 TEST(FwLoop1b) { 284 TestCode code; 285 286 // B0 287 code.Fallthru(); 288 // B1 289 code.Jump(1); 290 291 static int expected[] = {1, 1}; 292 VerifyForwarding(code, 2, expected); 293 } 294 295 296 TEST(FwLoop2b) { 297 TestCode code; 298 299 // B0 300 code.Fallthru(); 301 // B1 302 code.Fallthru(); 303 // B2 304 code.Jump(1); 305 306 static int expected[] = {1, 1, 1}; 307 VerifyForwarding(code, 3, expected); 308 } 309 310 311 TEST(FwLoop3b) { 312 TestCode code; 313 314 // B0 315 code.Fallthru(); 316 // B1 317 code.Fallthru(); 318 // B2 319 code.Fallthru(); 320 // B3 321 code.Jump(1); 322 323 static int expected[] = {1, 1, 1, 1}; 324 VerifyForwarding(code, 4, expected); 325 } 326 327 328 TEST(FwLoop2_1a) { 329 TestCode code; 330 331 // B0 332 code.Fallthru(); 333 // B1 334 code.Fallthru(); 335 // B2 336 code.Fallthru(); 337 // B3 338 code.Jump(1); 339 // B4 340 code.Jump(2); 341 342 static int expected[] = {1, 1, 1, 1, 1}; 343 VerifyForwarding(code, 5, expected); 344 } 345 346 347 TEST(FwLoop2_1b) { 348 TestCode code; 349 350 // B0 351 code.Fallthru(); 352 // B1 353 code.Fallthru(); 354 // B2 355 code.Jump(4); 356 // B3 357 code.Jump(1); 358 // B4 359 code.Jump(2); 360 361 static int expected[] = {2, 2, 2, 2, 2}; 362 VerifyForwarding(code, 5, expected); 363 } 364 365 366 TEST(FwLoop2_1c) { 367 TestCode code; 368 369 // B0 370 code.Fallthru(); 371 // B1 372 code.Fallthru(); 373 // B2 374 code.Jump(4); 375 // B3 376 code.Jump(2); 377 // B4 378 code.Jump(1); 379 380 static int expected[] = {1, 1, 1, 1, 1}; 381 VerifyForwarding(code, 5, expected); 382 } 383 384 385 TEST(FwLoop2_1d) { 386 TestCode code; 387 388 // B0 389 code.Fallthru(); 390 // B1 391 code.Fallthru(); 392 // B2 393 code.Jump(1); 394 // B3 395 code.Jump(1); 396 // B4 397 code.Jump(1); 398 399 static int expected[] = {1, 1, 1, 1, 1}; 400 VerifyForwarding(code, 5, expected); 401 } 402 403 404 TEST(FwLoop3_1a) { 405 TestCode code; 406 407 // B0 408 code.Fallthru(); 409 // B1 410 code.Fallthru(); 411 // B2 412 code.Fallthru(); 413 // B3 414 code.Jump(2); 415 // B4 416 code.Jump(1); 417 // B5 418 code.Jump(0); 419 420 static int expected[] = {2, 2, 2, 2, 2, 2}; 421 VerifyForwarding(code, 6, expected); 422 } 423 424 425 TEST(FwDiamonds) { 426 for (int i = 0; i < 2; i++) { 427 for (int j = 0; j < 2; j++) { 428 TestCode code; 429 // B0 430 code.Branch(1, 2); 431 // B1 432 if (i) code.Other(); 433 code.Jump(3); 434 // B2 435 if (j) code.Other(); 436 code.Jump(3); 437 // B3 438 code.End(); 439 440 int expected[] = {0, i ? 1 : 3, j ? 2 : 3, 3}; 441 VerifyForwarding(code, 4, expected); 442 } 443 } 444 } 445 446 447 TEST(FwDiamonds2) { 448 for (int i = 0; i < 2; i++) { 449 for (int j = 0; j < 2; j++) { 450 for (int k = 0; k < 2; k++) { 451 TestCode code; 452 // B0 453 code.Branch(1, 2); 454 // B1 455 if (i) code.Other(); 456 code.Jump(3); 457 // B2 458 if (j) code.Other(); 459 code.Jump(3); 460 // B3 461 if (k) code.NonRedundantMoves(); 462 code.Jump(4); 463 // B4 464 code.End(); 465 466 int merge = k ? 3 : 4; 467 int expected[] = {0, i ? 1 : merge, j ? 2 : merge, merge, 4}; 468 VerifyForwarding(code, 5, expected); 469 } 470 } 471 } 472 } 473 474 475 TEST(FwDoubleDiamonds) { 476 for (int i = 0; i < 2; i++) { 477 for (int j = 0; j < 2; j++) { 478 for (int x = 0; x < 2; x++) { 479 for (int y = 0; y < 2; y++) { 480 TestCode code; 481 // B0 482 code.Branch(1, 2); 483 // B1 484 if (i) code.Other(); 485 code.Jump(3); 486 // B2 487 if (j) code.Other(); 488 code.Jump(3); 489 // B3 490 code.Branch(4, 5); 491 // B4 492 if (x) code.Other(); 493 code.Jump(6); 494 // B5 495 if (y) code.Other(); 496 code.Jump(6); 497 // B6 498 code.End(); 499 500 int expected[] = {0, i ? 1 : 3, j ? 2 : 3, 3, 501 x ? 4 : 6, y ? 5 : 6, 6}; 502 VerifyForwarding(code, 7, expected); 503 } 504 } 505 } 506 } 507 } 508 509 template <int kSize> 510 void RunPermutationsRecursive(int outer[kSize], int start, 511 void (*run)(int*, int)) { 512 int permutation[kSize]; 513 514 for (int i = 0; i < kSize; i++) permutation[i] = outer[i]; 515 516 int count = kSize - start; 517 if (count == 0) return run(permutation, kSize); 518 for (int i = start; i < kSize; i++) { 519 permutation[start] = outer[i]; 520 permutation[i] = outer[start]; 521 RunPermutationsRecursive<kSize>(permutation, start + 1, run); 522 permutation[i] = outer[i]; 523 permutation[start] = outer[start]; 524 } 525 } 526 527 528 template <int kSize> 529 void RunAllPermutations(void (*run)(int*, int)) { 530 int permutation[kSize]; 531 for (int i = 0; i < kSize; i++) permutation[i] = i; 532 RunPermutationsRecursive<kSize>(permutation, 0, run); 533 } 534 535 536 void PrintPermutation(int* permutation, int size) { 537 printf("{ "); 538 for (int i = 0; i < size; i++) { 539 if (i > 0) printf(", "); 540 printf("%d", permutation[i]); 541 } 542 printf(" }\n"); 543 } 544 545 546 int find(int x, int* permutation, int size) { 547 for (int i = 0; i < size; i++) { 548 if (permutation[i] == x) return i; 549 } 550 return size; 551 } 552 553 554 void RunPermutedChain(int* permutation, int size) { 555 TestCode code; 556 int cur = -1; 557 for (int i = 0; i < size; i++) { 558 code.Jump(find(cur + 1, permutation, size) + 1); 559 cur = permutation[i]; 560 } 561 code.Jump(find(cur + 1, permutation, size) + 1); 562 code.End(); 563 564 int expected[] = {size + 1, size + 1, size + 1, size + 1, 565 size + 1, size + 1, size + 1}; 566 VerifyForwarding(code, size + 2, expected); 567 } 568 569 570 TEST(FwPermuted_chain) { 571 RunAllPermutations<3>(RunPermutedChain); 572 RunAllPermutations<4>(RunPermutedChain); 573 RunAllPermutations<5>(RunPermutedChain); 574 } 575 576 577 void RunPermutedDiamond(int* permutation, int size) { 578 TestCode code; 579 int br = 1 + find(0, permutation, size); 580 code.Jump(br); 581 for (int i = 0; i < size; i++) { 582 switch (permutation[i]) { 583 case 0: 584 code.Branch(1 + find(1, permutation, size), 585 1 + find(2, permutation, size)); 586 break; 587 case 1: 588 code.Jump(1 + find(3, permutation, size)); 589 break; 590 case 2: 591 code.Jump(1 + find(3, permutation, size)); 592 break; 593 case 3: 594 code.Jump(5); 595 break; 596 } 597 } 598 code.End(); 599 600 int expected[] = {br, 5, 5, 5, 5, 5}; 601 expected[br] = br; 602 VerifyForwarding(code, 6, expected); 603 } 604 605 606 TEST(FwPermuted_diamond) { RunAllPermutations<4>(RunPermutedDiamond); } 607 608 609 void ApplyForwarding(TestCode& code, int size, int* forward) { 610 ZoneVector<RpoNumber> vector(code.main_zone()); 611 for (int i = 0; i < size; i++) { 612 vector.push_back(RpoNumber::FromInt(forward[i])); 613 } 614 JumpThreading::ApplyForwarding(vector, &code.sequence_); 615 } 616 617 618 void CheckJump(TestCode& code, int pos, int target) { 619 Instruction* instr = code.sequence_.InstructionAt(pos); 620 CHECK_EQ(kArchJmp, instr->arch_opcode()); 621 CHECK_EQ(1, static_cast<int>(instr->InputCount())); 622 CHECK_EQ(0, static_cast<int>(instr->OutputCount())); 623 CHECK_EQ(0, static_cast<int>(instr->TempCount())); 624 CHECK_EQ(target, code.sequence_.InputRpo(instr, 0).ToInt()); 625 } 626 627 628 void CheckNop(TestCode& code, int pos) { 629 Instruction* instr = code.sequence_.InstructionAt(pos); 630 CHECK_EQ(kArchNop, instr->arch_opcode()); 631 CHECK_EQ(0, static_cast<int>(instr->InputCount())); 632 CHECK_EQ(0, static_cast<int>(instr->OutputCount())); 633 CHECK_EQ(0, static_cast<int>(instr->TempCount())); 634 } 635 636 637 void CheckBranch(TestCode& code, int pos, int t1, int t2) { 638 Instruction* instr = code.sequence_.InstructionAt(pos); 639 CHECK_EQ(2, static_cast<int>(instr->InputCount())); 640 CHECK_EQ(0, static_cast<int>(instr->OutputCount())); 641 CHECK_EQ(0, static_cast<int>(instr->TempCount())); 642 CHECK_EQ(t1, code.sequence_.InputRpo(instr, 0).ToInt()); 643 CHECK_EQ(t2, code.sequence_.InputRpo(instr, 1).ToInt()); 644 } 645 646 647 void CheckAssemblyOrder(TestCode& code, int size, int* expected) { 648 int i = 0; 649 for (auto const block : code.sequence_.instruction_blocks()) { 650 CHECK_EQ(expected[i++], block->ao_number().ToInt()); 651 } 652 } 653 654 655 TEST(Rewire1) { 656 TestCode code; 657 658 // B0 659 int j1 = code.Jump(1); 660 // B1 661 int j2 = code.Jump(2); 662 // B2 663 code.End(); 664 665 static int forward[] = {2, 2, 2}; 666 ApplyForwarding(code, 3, forward); 667 CheckJump(code, j1, 2); 668 CheckNop(code, j2); 669 670 static int assembly[] = {0, 1, 1}; 671 CheckAssemblyOrder(code, 3, assembly); 672 } 673 674 675 TEST(Rewire1_deferred) { 676 TestCode code; 677 678 // B0 679 int j1 = code.Jump(1); 680 // B1 681 int j2 = code.Jump(2); 682 // B2 683 code.Defer(); 684 int j3 = code.Jump(3); 685 // B3 686 code.End(); 687 688 static int forward[] = {3, 3, 3, 3}; 689 ApplyForwarding(code, 4, forward); 690 CheckJump(code, j1, 3); 691 CheckNop(code, j2); 692 CheckNop(code, j3); 693 694 static int assembly[] = {0, 1, 2, 1}; 695 CheckAssemblyOrder(code, 4, assembly); 696 } 697 698 699 TEST(Rewire2_deferred) { 700 TestCode code; 701 702 // B0 703 code.Other(); 704 int j1 = code.Jump(1); 705 // B1 706 code.Defer(); 707 code.Fallthru(); 708 // B2 709 code.Defer(); 710 int j2 = code.Jump(3); 711 // B3 712 code.End(); 713 714 static int forward[] = {0, 1, 2, 3}; 715 ApplyForwarding(code, 4, forward); 716 CheckJump(code, j1, 1); 717 CheckJump(code, j2, 3); 718 719 static int assembly[] = {0, 2, 3, 1}; 720 CheckAssemblyOrder(code, 4, assembly); 721 } 722 723 724 TEST(Rewire_diamond) { 725 for (int i = 0; i < 2; i++) { 726 for (int j = 0; j < 2; j++) { 727 TestCode code; 728 // B0 729 int j1 = code.Jump(1); 730 // B1 731 int b1 = code.Branch(2, 3); 732 // B2 733 int j2 = code.Jump(4); 734 // B3 735 int j3 = code.Jump(4); 736 // B5 737 code.End(); 738 739 int forward[] = {0, 1, i ? 4 : 2, j ? 4 : 3, 4}; 740 ApplyForwarding(code, 5, forward); 741 CheckJump(code, j1, 1); 742 CheckBranch(code, b1, i ? 4 : 2, j ? 4 : 3); 743 if (i) { 744 CheckNop(code, j2); 745 } else { 746 CheckJump(code, j2, 4); 747 } 748 if (j) { 749 CheckNop(code, j3); 750 } else { 751 CheckJump(code, j3, 4); 752 } 753 754 int assembly[] = {0, 1, 2, 3, 4}; 755 if (i) { 756 for (int k = 3; k < 5; k++) assembly[k]--; 757 } 758 if (j) { 759 for (int k = 4; k < 5; k++) assembly[k]--; 760 } 761 CheckAssemblyOrder(code, 5, assembly); 762 } 763 } 764 } 765 766 } // namespace compiler 767 } // namespace internal 768 } // namespace v8 769
