OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/machine-operator-reducer.h" | 5 #include "src/compiler/machine-operator-reducer.h" |
6 | 6 |
7 #include "src/base/bits.h" | 7 #include "src/base/bits.h" |
8 #include "src/base/division-by-constant.h" | 8 #include "src/base/division-by-constant.h" |
9 #include "src/codegen.h" | 9 #include "src/codegen.h" |
10 #include "src/compiler/generic-node-inl.h" | 10 #include "src/compiler/generic-node-inl.h" |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
42 return graph()->NewNode(common()->Int64Constant(value)); | 42 return graph()->NewNode(common()->Int64Constant(value)); |
43 } | 43 } |
44 | 44 |
45 | 45 |
46 Node* MachineOperatorReducer::Word32And(Node* lhs, uint32_t rhs) { | 46 Node* MachineOperatorReducer::Word32And(Node* lhs, uint32_t rhs) { |
47 return graph()->NewNode(machine()->Word32And(), lhs, Uint32Constant(rhs)); | 47 return graph()->NewNode(machine()->Word32And(), lhs, Uint32Constant(rhs)); |
48 } | 48 } |
49 | 49 |
50 | 50 |
51 Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) { | 51 Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) { |
| 52 if (rhs == 0) return lhs; |
52 return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs)); | 53 return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs)); |
53 } | 54 } |
54 | 55 |
55 | 56 |
56 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) { | 57 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) { |
| 58 if (rhs == 0) return lhs; |
57 return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs)); | 59 return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs)); |
58 } | 60 } |
59 | 61 |
60 | 62 |
61 Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) { | 63 Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) { |
62 return graph()->NewNode(machine()->Word32Equal(), lhs, rhs); | 64 return graph()->NewNode(machine()->Word32Equal(), lhs, rhs); |
63 } | 65 } |
64 | 66 |
65 | 67 |
66 Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) { | 68 Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) { |
67 return graph()->NewNode(machine()->Int32Add(), lhs, rhs); | 69 return graph()->NewNode(machine()->Int32Add(), lhs, rhs); |
68 } | 70 } |
69 | 71 |
70 | 72 |
71 Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) { | 73 Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) { |
72 return graph()->NewNode(machine()->Int32Sub(), lhs, rhs); | 74 return graph()->NewNode(machine()->Int32Sub(), lhs, rhs); |
73 } | 75 } |
74 | 76 |
75 | 77 |
76 Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) { | 78 Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) { |
77 return graph()->NewNode(machine()->Int32Mul(), lhs, rhs); | 79 return graph()->NewNode(machine()->Int32Mul(), lhs, rhs); |
78 } | 80 } |
79 | 81 |
80 | 82 |
81 Node* MachineOperatorReducer::TruncatingDiv(Node* dividend, int32_t divisor) { | 83 Node* MachineOperatorReducer::Int32Div(Node* dividend, int32_t divisor) { |
| 84 DCHECK_NE(0, divisor); |
82 DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor); | 85 DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor); |
83 base::MagicNumbersForDivision<uint32_t> const mag = | 86 base::MagicNumbersForDivision<uint32_t> const mag = |
84 base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor)); | 87 base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor)); |
85 Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend, | 88 Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend, |
86 Uint32Constant(mag.multiplier)); | 89 Uint32Constant(mag.multiplier)); |
87 if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) { | 90 if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) { |
88 quotient = Int32Add(quotient, dividend); | 91 quotient = Int32Add(quotient, dividend); |
89 } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) { | 92 } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) { |
90 quotient = Int32Sub(quotient, dividend); | 93 quotient = Int32Sub(quotient, dividend); |
91 } | 94 } |
92 if (mag.shift) { | 95 return Int32Add(Word32Sar(quotient, mag.shift), Word32Shr(dividend, 31)); |
93 quotient = Word32Sar(quotient, mag.shift); | |
94 } | |
95 return Int32Add(quotient, Word32Shr(dividend, 31)); | |
96 } | 96 } |
97 | 97 |
98 | 98 |
| 99 Node* MachineOperatorReducer::Uint32Div(Node* dividend, uint32_t divisor) { |
| 100 DCHECK_LT(0, divisor); |
| 101 base::MagicNumbersForDivision<uint32_t> const mag = |
| 102 base::UnsignedDivisionByConstant(bit_cast<uint32_t>(divisor)); |
| 103 Node* quotient = graph()->NewNode(machine()->Uint32MulHigh(), dividend, |
| 104 Uint32Constant(mag.multiplier)); |
| 105 if (mag.add) { |
| 106 DCHECK_LE(1, mag.shift); |
| 107 quotient = Word32Shr( |
| 108 Int32Add(Word32Shr(Int32Sub(dividend, quotient), 1), quotient), |
| 109 mag.shift - 1); |
| 110 } else { |
| 111 quotient = Word32Shr(quotient, mag.shift); |
| 112 } |
| 113 return quotient; |
| 114 } |
| 115 |
| 116 |
99 // Perform constant folding and strength reduction on machine operators. | 117 // Perform constant folding and strength reduction on machine operators. |
100 Reduction MachineOperatorReducer::Reduce(Node* node) { | 118 Reduction MachineOperatorReducer::Reduce(Node* node) { |
101 switch (node->opcode()) { | 119 switch (node->opcode()) { |
102 case IrOpcode::kProjection: | 120 case IrOpcode::kProjection: |
103 return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0)); | 121 return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0)); |
104 case IrOpcode::kWord32And: { | 122 case IrOpcode::kWord32And: { |
105 Int32BinopMatcher m(node); | 123 Int32BinopMatcher m(node); |
106 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0 | 124 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0 |
107 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x | 125 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x |
108 if (m.IsFoldable()) { // K & K => K | 126 if (m.IsFoldable()) { // K & K => K |
(...skipping 456 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
565 Node* quotient = dividend; | 583 Node* quotient = dividend; |
566 if (base::bits::IsPowerOfTwo32(Abs(divisor))) { | 584 if (base::bits::IsPowerOfTwo32(Abs(divisor))) { |
567 uint32_t const shift = WhichPowerOf2Abs(divisor); | 585 uint32_t const shift = WhichPowerOf2Abs(divisor); |
568 DCHECK_NE(0, shift); | 586 DCHECK_NE(0, shift); |
569 if (shift > 1) { | 587 if (shift > 1) { |
570 quotient = Word32Sar(quotient, 31); | 588 quotient = Word32Sar(quotient, 31); |
571 } | 589 } |
572 quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend); | 590 quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend); |
573 quotient = Word32Sar(quotient, shift); | 591 quotient = Word32Sar(quotient, shift); |
574 } else { | 592 } else { |
575 quotient = TruncatingDiv(quotient, Abs(divisor)); | 593 quotient = Int32Div(quotient, Abs(divisor)); |
576 } | 594 } |
577 if (divisor < 0) { | 595 if (divisor < 0) { |
578 node->set_op(machine()->Int32Sub()); | 596 node->set_op(machine()->Int32Sub()); |
579 node->ReplaceInput(0, Int32Constant(0)); | 597 node->ReplaceInput(0, Int32Constant(0)); |
580 node->ReplaceInput(1, quotient); | 598 node->ReplaceInput(1, quotient); |
581 node->TrimInputCount(2); | 599 node->TrimInputCount(2); |
582 return Changed(node); | 600 return Changed(node); |
583 } | 601 } |
584 return Replace(quotient); | 602 return Replace(quotient); |
585 } | 603 } |
586 return NoChange(); | 604 return NoChange(); |
587 } | 605 } |
588 | 606 |
589 | 607 |
590 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) { | 608 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) { |
591 Uint32BinopMatcher m(node); | 609 Uint32BinopMatcher m(node); |
592 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0 | 610 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0 |
593 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0 | 611 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0 |
594 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x | 612 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x |
595 if (m.IsFoldable()) { // K / K => K | 613 if (m.IsFoldable()) { // K / K => K |
596 return ReplaceUint32( | 614 return ReplaceUint32( |
597 base::bits::UnsignedDiv32(m.left().Value(), m.right().Value())); | 615 base::bits::UnsignedDiv32(m.left().Value(), m.right().Value())); |
598 } | 616 } |
599 if (m.LeftEqualsRight()) { // x / x => x != 0 | 617 if (m.LeftEqualsRight()) { // x / x => x != 0 |
600 Node* const zero = Int32Constant(0); | 618 Node* const zero = Int32Constant(0); |
601 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero)); | 619 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero)); |
602 } | 620 } |
603 if (m.right().IsPowerOf2()) { // x / 2^n => x >> n | 621 if (m.right().HasValue()) { |
604 node->TrimInputCount(2); | 622 Node* const dividend = m.left().node(); |
605 node->set_op(machine()->Word32Shr()); | 623 uint32_t const divisor = m.right().Value(); |
606 node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value()))); | 624 if (base::bits::IsPowerOfTwo32(divisor)) { // x / 2^n => x >> n |
607 return Changed(node); | 625 node->set_op(machine()->Word32Shr()); |
| 626 node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value()))); |
| 627 node->TrimInputCount(2); |
| 628 return Changed(node); |
| 629 } else { |
| 630 return Replace(Uint32Div(dividend, divisor)); |
| 631 } |
608 } | 632 } |
609 return NoChange(); | 633 return NoChange(); |
610 } | 634 } |
611 | 635 |
612 | 636 |
613 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) { | 637 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) { |
614 Int32BinopMatcher m(node); | 638 Int32BinopMatcher m(node); |
615 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 | 639 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 |
616 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 | 640 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 |
617 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0 | 641 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0 |
(...skipping 15 matching lines...) Expand all Loading... |
633 Node* branch = | 657 Node* branch = |
634 graph()->NewNode(common()->Branch(), check, graph()->start()); | 658 graph()->NewNode(common()->Branch(), check, graph()->start()); |
635 | 659 |
636 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); | 660 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); |
637 Node* neg = Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)); | 661 Node* neg = Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)); |
638 | 662 |
639 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); | 663 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); |
640 Node* pos = Word32And(dividend, mask); | 664 Node* pos = Word32And(dividend, mask); |
641 | 665 |
642 Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false); | 666 Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false); |
643 Node* phi = | 667 |
644 graph()->NewNode(common()->Phi(kMachInt32, 2), neg, pos, merge); | 668 DCHECK_EQ(3, node->InputCount()); |
645 return Replace(phi); | 669 node->set_op(common()->Phi(kMachInt32, 2)); |
| 670 node->ReplaceInput(0, neg); |
| 671 node->ReplaceInput(1, pos); |
| 672 node->ReplaceInput(2, merge); |
646 } else { | 673 } else { |
647 Node* quotient = TruncatingDiv(dividend, divisor); | 674 Node* quotient = Int32Div(dividend, divisor); |
648 node->set_op(machine()->Int32Sub()); | 675 node->set_op(machine()->Int32Sub()); |
649 DCHECK_EQ(dividend, node->InputAt(0)); | 676 DCHECK_EQ(dividend, node->InputAt(0)); |
650 node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor))); | 677 node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor))); |
651 node->TrimInputCount(2); | 678 node->TrimInputCount(2); |
652 return Changed(node); | |
653 } | 679 } |
| 680 return Changed(node); |
654 } | 681 } |
655 return NoChange(); | 682 return NoChange(); |
656 } | 683 } |
657 | 684 |
658 | 685 |
659 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) { | 686 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) { |
660 Uint32BinopMatcher m(node); | 687 Uint32BinopMatcher m(node); |
661 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 | 688 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 |
662 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 | 689 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 |
663 if (m.right().Is(1)) return ReplaceUint32(0); // x % 1 => 0 | 690 if (m.right().Is(1)) return ReplaceUint32(0); // x % 1 => 0 |
664 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0 | 691 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0 |
665 if (m.IsFoldable()) { // K % K => K | 692 if (m.IsFoldable()) { // K % K => K |
666 return ReplaceUint32( | 693 return ReplaceUint32( |
667 base::bits::UnsignedMod32(m.left().Value(), m.right().Value())); | 694 base::bits::UnsignedMod32(m.left().Value(), m.right().Value())); |
668 } | 695 } |
669 if (m.right().IsPowerOf2()) { // x % 2^n => x & 2^n-1 | 696 if (m.right().HasValue()) { |
| 697 Node* const dividend = m.left().node(); |
| 698 uint32_t const divisor = m.right().Value(); |
| 699 if (base::bits::IsPowerOfTwo32(divisor)) { // x % 2^n => x & 2^n-1 |
| 700 node->set_op(machine()->Word32And()); |
| 701 node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1)); |
| 702 } else { |
| 703 Node* quotient = Uint32Div(dividend, divisor); |
| 704 node->set_op(machine()->Int32Sub()); |
| 705 DCHECK_EQ(dividend, node->InputAt(0)); |
| 706 node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor))); |
| 707 } |
670 node->TrimInputCount(2); | 708 node->TrimInputCount(2); |
671 node->set_op(machine()->Word32And()); | |
672 node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1)); | |
673 return Changed(node); | 709 return Changed(node); |
674 } | 710 } |
675 return NoChange(); | 711 return NoChange(); |
676 } | 712 } |
677 | 713 |
678 | 714 |
679 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) { | 715 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) { |
680 switch (node->opcode()) { | 716 switch (node->opcode()) { |
681 case IrOpcode::kInt32AddWithOverflow: { | 717 case IrOpcode::kInt32AddWithOverflow: { |
682 DCHECK(index == 0 || index == 1); | 718 DCHECK(index == 0 || index == 1); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
721 MachineOperatorBuilder* MachineOperatorReducer::machine() const { | 757 MachineOperatorBuilder* MachineOperatorReducer::machine() const { |
722 return jsgraph()->machine(); | 758 return jsgraph()->machine(); |
723 } | 759 } |
724 | 760 |
725 | 761 |
726 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); } | 762 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); } |
727 | 763 |
728 } // namespace compiler | 764 } // namespace compiler |
729 } // namespace internal | 765 } // namespace internal |
730 } // namespace v8 | 766 } // namespace v8 |
OLD | NEW |