deps/v8/test/cctest/compiler/test-jump-threading.cc

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