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