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/codegen.h" | 9 #include "src/codegen.h" |
9 #include "src/compiler/generic-node-inl.h" | 10 #include "src/compiler/generic-node-inl.h" |
10 #include "src/compiler/graph.h" | 11 #include "src/compiler/graph.h" |
11 #include "src/compiler/js-graph.h" | 12 #include "src/compiler/js-graph.h" |
12 #include "src/compiler/node-matchers.h" | 13 #include "src/compiler/node-matchers.h" |
13 | 14 |
14 namespace v8 { | 15 namespace v8 { |
15 namespace internal { | 16 namespace internal { |
16 namespace compiler { | 17 namespace compiler { |
17 | 18 |
(...skipping 17 matching lines...) Expand all Loading... |
35 Node* MachineOperatorReducer::Int32Constant(int32_t value) { | 36 Node* MachineOperatorReducer::Int32Constant(int32_t value) { |
36 return jsgraph()->Int32Constant(value); | 37 return jsgraph()->Int32Constant(value); |
37 } | 38 } |
38 | 39 |
39 | 40 |
40 Node* MachineOperatorReducer::Int64Constant(int64_t value) { | 41 Node* MachineOperatorReducer::Int64Constant(int64_t value) { |
41 return graph()->NewNode(common()->Int64Constant(value)); | 42 return graph()->NewNode(common()->Int64Constant(value)); |
42 } | 43 } |
43 | 44 |
44 | 45 |
| 46 Node* MachineOperatorReducer::Word32And(Node* lhs, uint32_t rhs) { |
| 47 return graph()->NewNode(machine()->Word32And(), lhs, Uint32Constant(rhs)); |
| 48 } |
| 49 |
| 50 |
| 51 Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) { |
| 52 return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs)); |
| 53 } |
| 54 |
| 55 |
| 56 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) { |
| 57 return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs)); |
| 58 } |
| 59 |
| 60 |
| 61 Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) { |
| 62 return graph()->NewNode(machine()->Int32Add(), lhs, rhs); |
| 63 } |
| 64 |
| 65 |
| 66 Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) { |
| 67 return graph()->NewNode(machine()->Int32Sub(), lhs, rhs); |
| 68 } |
| 69 |
| 70 |
| 71 Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) { |
| 72 return graph()->NewNode(machine()->Int32Mul(), lhs, rhs); |
| 73 } |
| 74 |
| 75 |
| 76 Node* MachineOperatorReducer::TruncatingDiv(Node* dividend, int32_t divisor) { |
| 77 DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor); |
| 78 base::MagicNumbersForDivision<uint32_t> const mag = |
| 79 base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor)); |
| 80 Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend, |
| 81 Uint32Constant(mag.multiplier)); |
| 82 if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) { |
| 83 quotient = Int32Add(quotient, dividend); |
| 84 } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) { |
| 85 quotient = Int32Sub(quotient, dividend); |
| 86 } |
| 87 if (mag.shift) { |
| 88 quotient = Word32Sar(quotient, mag.shift); |
| 89 } |
| 90 return Int32Add(quotient, Word32Shr(dividend, 31)); |
| 91 } |
| 92 |
| 93 |
45 // Perform constant folding and strength reduction on machine operators. | 94 // Perform constant folding and strength reduction on machine operators. |
46 Reduction MachineOperatorReducer::Reduce(Node* node) { | 95 Reduction MachineOperatorReducer::Reduce(Node* node) { |
47 switch (node->opcode()) { | 96 switch (node->opcode()) { |
48 case IrOpcode::kProjection: | 97 case IrOpcode::kProjection: |
49 return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0)); | 98 return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0)); |
50 case IrOpcode::kWord32And: { | 99 case IrOpcode::kWord32And: { |
51 Int32BinopMatcher m(node); | 100 Int32BinopMatcher m(node); |
52 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0 | 101 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0 |
53 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x | 102 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x |
54 if (m.IsFoldable()) { // K & K => K | 103 if (m.IsFoldable()) { // K & K => K |
(...skipping 165 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
220 node->ReplaceInput(1, m.left().node()); | 269 node->ReplaceInput(1, m.left().node()); |
221 return Changed(node); | 270 return Changed(node); |
222 } | 271 } |
223 if (m.right().IsPowerOf2()) { // x * 2^n => x << n | 272 if (m.right().IsPowerOf2()) { // x * 2^n => x << n |
224 node->set_op(machine()->Word32Shl()); | 273 node->set_op(machine()->Word32Shl()); |
225 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value()))); | 274 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value()))); |
226 return Changed(node); | 275 return Changed(node); |
227 } | 276 } |
228 break; | 277 break; |
229 } | 278 } |
230 case IrOpcode::kInt32Div: { | 279 case IrOpcode::kInt32Div: |
231 Int32BinopMatcher m(node); | 280 return ReduceInt32Div(node); |
232 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x | |
233 // TODO(turbofan): if (m.left().Is(0)) | |
234 // TODO(turbofan): if (m.right().IsPowerOf2()) | |
235 // TODO(turbofan): if (m.right().Is(0)) | |
236 // TODO(turbofan): if (m.LeftEqualsRight()) | |
237 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K | |
238 if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value()); | |
239 return ReplaceInt32(m.left().Value() / m.right().Value()); | |
240 } | |
241 if (m.right().Is(-1)) { // x / -1 => 0 - x | |
242 node->set_op(machine()->Int32Sub()); | |
243 node->ReplaceInput(0, Int32Constant(0)); | |
244 node->ReplaceInput(1, m.left().node()); | |
245 return Changed(node); | |
246 } | |
247 break; | |
248 } | |
249 case IrOpcode::kUint32Div: { | 281 case IrOpcode::kUint32Div: { |
250 Uint32BinopMatcher m(node); | 282 Uint32BinopMatcher m(node); |
251 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x | 283 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x |
252 // TODO(turbofan): if (m.left().Is(0)) | 284 // TODO(turbofan): if (m.left().Is(0)) |
253 // TODO(turbofan): if (m.right().Is(0)) | 285 // TODO(turbofan): if (m.right().Is(0)) |
254 // TODO(turbofan): if (m.LeftEqualsRight()) | 286 // TODO(turbofan): if (m.LeftEqualsRight()) |
255 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K | 287 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K |
256 return ReplaceInt32(m.left().Value() / m.right().Value()); | 288 return ReplaceInt32(m.left().Value() / m.right().Value()); |
257 } | 289 } |
258 if (m.right().IsPowerOf2()) { // x / 2^n => x >> n | 290 if (m.right().IsPowerOf2()) { // x / 2^n => x >> n |
(...skipping 233 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
492 } | 524 } |
493 break; | 525 break; |
494 } | 526 } |
495 default: | 527 default: |
496 break; | 528 break; |
497 } | 529 } |
498 return NoChange(); | 530 return NoChange(); |
499 } | 531 } |
500 | 532 |
501 | 533 |
502 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* const node) { | 534 Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) { |
| 535 Int32BinopMatcher m(node); |
| 536 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0 |
| 537 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x |
| 538 // TODO(turbofan): if (m.left().Is(0)) |
| 539 // TODO(turbofan): if (m.LeftEqualsRight()) |
| 540 if (m.IsFoldable() && !m.right().Is(0)) { // K / K => K |
| 541 if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value()); |
| 542 return ReplaceInt32(m.left().Value() / m.right().Value()); |
| 543 } |
| 544 if (m.right().Is(-1)) { // x / -1 => 0 - x |
| 545 node->set_op(machine()->Int32Sub()); |
| 546 node->ReplaceInput(0, Int32Constant(0)); |
| 547 node->ReplaceInput(1, m.left().node()); |
| 548 return Changed(node); |
| 549 } |
| 550 if (m.right().HasValue()) { |
| 551 int32_t const divisor = m.right().Value(); |
| 552 Node* const dividend = m.left().node(); |
| 553 Node* quotient = dividend; |
| 554 if (base::bits::IsPowerOfTwo32(Abs(divisor))) { |
| 555 uint32_t const shift = WhichPowerOf2Abs(divisor); |
| 556 DCHECK_NE(0, shift); |
| 557 if (shift > 1) { |
| 558 quotient = Word32Sar(quotient, 31); |
| 559 } |
| 560 quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend); |
| 561 quotient = Word32Sar(quotient, shift); |
| 562 } else { |
| 563 quotient = TruncatingDiv(quotient, Abs(divisor)); |
| 564 } |
| 565 if (divisor < 0) { |
| 566 node->set_op(machine()->Int32Sub()); |
| 567 node->ReplaceInput(0, Int32Constant(0)); |
| 568 node->ReplaceInput(1, quotient); |
| 569 return Changed(node); |
| 570 } |
| 571 return Replace(quotient); |
| 572 } |
| 573 return NoChange(); |
| 574 } |
| 575 |
| 576 |
| 577 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) { |
503 Int32BinopMatcher m(node); | 578 Int32BinopMatcher m(node); |
504 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0 | 579 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0 |
505 if (m.right().Is(-1)) return ReplaceInt32(0); // x % -1 => 0 | 580 if (m.right().Is(-1)) return ReplaceInt32(0); // x % -1 => 0 |
506 // TODO(turbofan): if (m.left().Is(0)) | 581 // TODO(turbofan): if (m.left().Is(0)) |
507 // TODO(turbofan): if (m.right().Is(0)) | 582 // TODO(turbofan): if (m.right().Is(0)) |
508 // TODO(turbofan): if (m.LeftEqualsRight()) | 583 // TODO(turbofan): if (m.LeftEqualsRight()) |
509 if (m.IsFoldable() && !m.right().Is(0)) { // K % K => K | 584 if (m.IsFoldable() && !m.right().Is(0)) { // K % K => K |
510 return ReplaceInt32(m.left().Value() % m.right().Value()); | 585 return ReplaceInt32(m.left().Value() % m.right().Value()); |
511 } | 586 } |
512 if (m.right().IsPowerOf2()) { | 587 if (m.right().HasValue()) { |
513 int32_t const divisor = m.right().Value(); | 588 Node* const dividend = m.left().node(); |
514 Node* zero = Int32Constant(0); | 589 int32_t const divisor = Abs(m.right().Value()); |
515 Node* mask = Int32Constant(divisor - 1); | 590 if (base::bits::IsPowerOfTwo32(divisor)) { |
516 Node* dividend = m.left().node(); | 591 uint32_t const mask = divisor - 1; |
| 592 Node* const zero = Int32Constant(0); |
517 | 593 |
518 Node* check = graph()->NewNode(machine()->Int32LessThan(), dividend, zero); | 594 Node* check = |
519 Node* branch = | 595 graph()->NewNode(machine()->Int32LessThan(), dividend, zero); |
520 graph()->NewNode(common()->Branch(), check, graph()->start()); | 596 Node* branch = |
| 597 graph()->NewNode(common()->Branch(), check, graph()->start()); |
521 | 598 |
522 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); | 599 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); |
523 Node* neg = graph()->NewNode( | 600 Node* neg = Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)); |
524 machine()->Int32Sub(), zero, | |
525 graph()->NewNode( | |
526 machine()->Word32And(), | |
527 graph()->NewNode(machine()->Int32Sub(), zero, dividend), mask)); | |
528 | 601 |
529 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); | 602 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); |
530 Node* pos = graph()->NewNode(machine()->Word32And(), dividend, mask); | 603 Node* pos = Word32And(dividend, mask); |
531 | 604 |
532 Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false); | 605 Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false); |
533 Node* phi = graph()->NewNode(common()->Phi(kMachInt32, 2), neg, pos, merge); | 606 Node* phi = |
534 return Replace(phi); | 607 graph()->NewNode(common()->Phi(kMachInt32, 2), neg, pos, merge); |
| 608 return Replace(phi); |
| 609 } else { |
| 610 Node* quotient = TruncatingDiv(dividend, divisor); |
| 611 node->set_op(machine()->Int32Sub()); |
| 612 DCHECK_EQ(dividend, node->InputAt(0)); |
| 613 node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor))); |
| 614 return Changed(node); |
| 615 } |
535 } | 616 } |
536 return NoChange(); | 617 return NoChange(); |
537 } | 618 } |
538 | 619 |
539 | 620 |
540 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) { | 621 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) { |
541 switch (node->opcode()) { | 622 switch (node->opcode()) { |
542 case IrOpcode::kInt32AddWithOverflow: { | 623 case IrOpcode::kInt32AddWithOverflow: { |
543 DCHECK(index == 0 || index == 1); | 624 DCHECK(index == 0 || index == 1); |
544 Int32BinopMatcher m(node); | 625 Int32BinopMatcher m(node); |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
582 MachineOperatorBuilder* MachineOperatorReducer::machine() const { | 663 MachineOperatorBuilder* MachineOperatorReducer::machine() const { |
583 return jsgraph()->machine(); | 664 return jsgraph()->machine(); |
584 } | 665 } |
585 | 666 |
586 | 667 |
587 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); } | 668 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); } |
588 | 669 |
589 } // namespace compiler | 670 } // namespace compiler |
590 } // namespace internal | 671 } // namespace internal |
591 } // namespace v8 | 672 } // namespace v8 |
OLD | NEW |