[turbofan] Optimize division/modulus by constant.

src/compiler/machine-operator-reducer.cc

Index: src/compiler/machine-operator-reducer.cc
diff --git a/src/compiler/machine-operator-reducer.cc b/src/compiler/machine-operator-reducer.cc
index cdb21822a8fe5d66c6dbf8e368d122851256e893..6d02272a3405baac24f6a9da1018867157de82de 100644
--- a/src/compiler/machine-operator-reducer.cc
+++ b/src/compiler/machine-operator-reducer.cc
@@ -5,6 +5,7 @@
 #include "src/compiler/machine-operator-reducer.h"
 
 #include "src/base/bits.h"
+#include "src/base/division-by-constant.h"
 #include "src/codegen.h"
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/graph.h"
@@ -42,6 +43,54 @@ Node* MachineOperatorReducer::Int64Constant(int64_t value) {
 }
 
 
+Node* MachineOperatorReducer::Word32And(Node* lhs, uint32_t rhs) {
+  return graph()->NewNode(machine()->Word32And(), lhs, Uint32Constant(rhs));
+}
+
+
+Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) {
+  return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs));
+}
+
+
+Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) {
+  return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs));
+}
+
+
+Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) {
+  return graph()->NewNode(machine()->Int32Add(), lhs, rhs);
+}
+
+
+Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) {
+  return graph()->NewNode(machine()->Int32Sub(), lhs, rhs);
+}
+
+
+Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) {
+  return graph()->NewNode(machine()->Int32Mul(), lhs, rhs);
+}
+
+
+Node* MachineOperatorReducer::TruncatingDiv(Node* dividend, int32_t divisor) {
+  DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor);
+  base::MagicNumbersForDivision<uint32_t> const mag =
+      base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor));
+  Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend,
+                                    Uint32Constant(mag.multiplier));
+  if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) {
+    quotient = Int32Add(quotient, dividend);
+  } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) {
+    quotient = Int32Sub(quotient, dividend);
+  }
+  if (mag.shift) {
+    quotient = Word32Sar(quotient, mag.shift);
+  }
+  return Int32Add(quotient, Word32Shr(dividend, 31));
+}
+
+
 // Perform constant folding and strength reduction on machine operators.
 Reduction MachineOperatorReducer::Reduce(Node* node) {
   switch (node->opcode()) {
@@ -227,25 +276,8 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
       }
       break;
     }
-    case IrOpcode::kInt32Div: {
-      Int32BinopMatcher m(node);
-      if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
-      // TODO(turbofan): if (m.left().Is(0))
-      // TODO(turbofan): if (m.right().IsPowerOf2())
-      // TODO(turbofan): if (m.right().Is(0))
-      // TODO(turbofan): if (m.LeftEqualsRight())
-      if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
-        if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value());
-        return ReplaceInt32(m.left().Value() / m.right().Value());
-      }
-      if (m.right().Is(-1)) {  // x / -1 => 0 - x
-        node->set_op(machine()->Int32Sub());
-        node->ReplaceInput(0, Int32Constant(0));
-        node->ReplaceInput(1, m.left().node());
-        return Changed(node);
-      }
-      break;
-    }
+    case IrOpcode::kInt32Div:
+      return ReduceInt32Div(node);
     case IrOpcode::kUint32Div: {
       Uint32BinopMatcher m(node);
       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
@@ -499,7 +531,50 @@ Reduction MachineOperatorReducer::Reduce(Node* node) {
 }
 
 
-Reduction MachineOperatorReducer::ReduceInt32Mod(Node* const node) {
+Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
+  Int32BinopMatcher m(node);
+  if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
+  if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
+  // TODO(turbofan): if (m.left().Is(0))
+  // TODO(turbofan): if (m.LeftEqualsRight())
+  if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
+    if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value());
+    return ReplaceInt32(m.left().Value() / m.right().Value());
+  }
+  if (m.right().Is(-1)) {  // x / -1 => 0 - x
+    node->set_op(machine()->Int32Sub());
+    node->ReplaceInput(0, Int32Constant(0));
+    node->ReplaceInput(1, m.left().node());
+    return Changed(node);
+  }
+  if (m.right().HasValue()) {
+    int32_t const divisor = m.right().Value();
+    Node* const dividend = m.left().node();
+    Node* quotient = dividend;
+    if (base::bits::IsPowerOfTwo32(Abs(divisor))) {
+      uint32_t const shift = WhichPowerOf2Abs(divisor);
+      DCHECK_NE(0, shift);
+      if (shift > 1) {
+        quotient = Word32Sar(quotient, 31);
+      }
+      quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend);
+      quotient = Word32Sar(quotient, shift);
+    } else {
+      quotient = TruncatingDiv(quotient, Abs(divisor));
+    }
+    if (divisor < 0) {
+      node->set_op(machine()->Int32Sub());
+      node->ReplaceInput(0, Int32Constant(0));
+      node->ReplaceInput(1, quotient);
+      return Changed(node);
+    }
+    return Replace(quotient);
+  }
+  return NoChange();
+}
+
+
+Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
   Int32BinopMatcher m(node);
   if (m.right().Is(1)) return ReplaceInt32(0);   // x % 1  => 0
   if (m.right().Is(-1)) return ReplaceInt32(0);  // x % -1 => 0
@@ -509,29 +584,35 @@ Reduction MachineOperatorReducer::ReduceInt32Mod(Node* const node) {
   if (m.IsFoldable() && !m.right().Is(0)) {  // K % K => K
     return ReplaceInt32(m.left().Value() % m.right().Value());
   }
-  if (m.right().IsPowerOf2()) {
-    int32_t const divisor = m.right().Value();
-    Node* zero = Int32Constant(0);
-    Node* mask = Int32Constant(divisor - 1);
-    Node* dividend = m.left().node();
-
-    Node* check = graph()->NewNode(machine()->Int32LessThan(), dividend, zero);
-    Node* branch =
-        graph()->NewNode(common()->Branch(), check, graph()->start());
-
-    Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
-    Node* neg = graph()->NewNode(
-        machine()->Int32Sub(), zero,
-        graph()->NewNode(
-            machine()->Word32And(),
-            graph()->NewNode(machine()->Int32Sub(), zero, dividend), mask));
-
-    Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
-    Node* pos = graph()->NewNode(machine()->Word32And(), dividend, mask);
-
-    Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
-    Node* phi = graph()->NewNode(common()->Phi(kMachInt32, 2), neg, pos, merge);
-    return Replace(phi);
+  if (m.right().HasValue()) {
+    Node* const dividend = m.left().node();
+    int32_t const divisor = Abs(m.right().Value());
+    if (base::bits::IsPowerOfTwo32(divisor)) {
+      uint32_t const mask = divisor - 1;
+      Node* const zero = Int32Constant(0);
+
+      Node* check =
+          graph()->NewNode(machine()->Int32LessThan(), dividend, zero);
+      Node* branch =
+          graph()->NewNode(common()->Branch(), check, graph()->start());
+
+      Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
+      Node* neg = Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask));
+
+      Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
+      Node* pos = Word32And(dividend, mask);
+
+      Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
+      Node* phi =
+          graph()->NewNode(common()->Phi(kMachInt32, 2), neg, pos, merge);
+      return Replace(phi);
+    } else {
+      Node* quotient = TruncatingDiv(dividend, divisor);
+      node->set_op(machine()->Int32Sub());
+      DCHECK_EQ(dividend, node->InputAt(0));
+      node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
+      return Changed(node);
+    }
   }
   return NoChange();
 }