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:
TestCode()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
Jump(int target)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 }
Fallthru()37 void Fallthru() {
38 Start();
39 End();
40 }
Branch(int ttarget,int ftarget)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 }
Nop()52 void Nop() {
53 Start();
54 sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop));
55 }
RedundantMoves()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 }
NonRedundantMoves()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 }
Other()73 void Other() {
74 Start();
75 sequence_.AddInstruction(Instruction::New(main_zone(), 155));
76 }
End()77 void End() {
78 Start();
79 sequence_.EndBlock(current_->rpo_number());
80 current_ = NULL;
81 rpo_number_ = RpoNumber::FromInt(rpo_number_.ToInt() + 1);
82 }
UseRpo(int num)83 InstructionOperand UseRpo(int num) {
84 return sequence_.AddImmediate(Constant(RpoNumber::FromInt(num)));
85 }
Start(bool deferred=false)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 }
Defer()95 void Defer() {
96 CHECK(current_ == NULL);
97 Start(true);
98 }
AddGapMove(int index,const InstructionOperand & from,const InstructionOperand & to)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
VerifyForwarding(TestCode & code,int count,int * expected)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
TEST(FwEmpty1)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
TEST(FwEmptyN)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
TEST(FwNone1)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
TEST(FwMoves1)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
TEST(FwMoves2)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
TEST(FwMoves2b)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
TEST(FwOther2)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
TEST(FwNone2a)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
TEST(FwNone2b)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
TEST(FwLoop1)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
TEST(FwLoop2)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
TEST(FwLoop3)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
TEST(FwLoop1b)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
TEST(FwLoop2b)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
TEST(FwLoop3b)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
TEST(FwLoop2_1a)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
TEST(FwLoop2_1b)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
TEST(FwLoop2_1c)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
TEST(FwLoop2_1d)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
TEST(FwLoop3_1a)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
TEST(FwDiamonds)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
TEST(FwDiamonds2)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
TEST(FwDoubleDiamonds)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>
RunPermutationsRecursive(int outer[kSize],int start,void (* run)(int *,int))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>
RunAllPermutations(void (* run)(int *,int))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
PrintPermutation(int * permutation,int size)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
find(int x,int * permutation,int size)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
RunPermutedChain(int * permutation,int size)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
TEST(FwPermuted_chain)570 TEST(FwPermuted_chain) {
571 RunAllPermutations<3>(RunPermutedChain);
572 RunAllPermutations<4>(RunPermutedChain);
573 RunAllPermutations<5>(RunPermutedChain);
574 }
575
576
RunPermutedDiamond(int * permutation,int size)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
TEST(FwPermuted_diamond)606 TEST(FwPermuted_diamond) { RunAllPermutations<4>(RunPermutedDiamond); }
607
608
ApplyForwarding(TestCode & code,int size,int * forward)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
CheckJump(TestCode & code,int pos,int target)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
CheckNop(TestCode & code,int pos)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
CheckBranch(TestCode & code,int pos,int t1,int t2)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
CheckAssemblyOrder(TestCode & code,int size,int * expected)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
TEST(Rewire1)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
TEST(Rewire1_deferred)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
TEST(Rewire2_deferred)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
TEST(Rewire_diamond)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