[turbofan] Also optimize unsigned division by constant.

src/compiler/machine-operator-reducer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #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"
@@ skipping 31 matching lines @@
   return graph()->NewNode(common()->Int64Constant(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) {
+  if (rhs == 0) return lhs;
   return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs));
 }
 
 
 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) {
+  if (rhs == 0) return lhs;
   return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs));
 }
 
 
 Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) {
   return graph()->NewNode(machine()->Word32Equal(), lhs, 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) {
+Node* MachineOperatorReducer::Int32Div(Node* dividend, int32_t divisor) {
+  DCHECK_NE(0, 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));
+  return Int32Add(Word32Sar(quotient, mag.shift), Word32Shr(dividend, 31));
 }
 
 
+Node* MachineOperatorReducer::Uint32Div(Node* dividend, uint32_t divisor) {
+  DCHECK_LT(0, divisor);
+  base::MagicNumbersForDivision<uint32_t> const mag =
+      base::UnsignedDivisionByConstant(bit_cast<uint32_t>(divisor));
+  Node* quotient = graph()->NewNode(machine()->Uint32MulHigh(), dividend,
+                                    Uint32Constant(mag.multiplier));
+  if (mag.add) {
+    DCHECK_LE(1, mag.shift);
+    quotient = Word32Shr(
+        Int32Add(Word32Shr(Int32Sub(dividend, quotient), 1), quotient),
+        mag.shift - 1);
+  } else {
+    quotient = Word32Shr(quotient, mag.shift);
+  }
+  return quotient;
+}
+
+
 // Perform constant folding and strength reduction on machine operators.
 Reduction MachineOperatorReducer::Reduce(Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kProjection:
       return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0));
     case IrOpcode::kWord32And: {
       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
       if (m.IsFoldable()) {                                   // K & K  => K
@@ skipping 456 matching lines @@
     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));
+      quotient = Int32Div(quotient, Abs(divisor));
     }
     if (divisor < 0) {
       node->set_op(machine()->Int32Sub());
       node->ReplaceInput(0, Int32Constant(0));
       node->ReplaceInput(1, quotient);
       node->TrimInputCount(2);
       return Changed(node);
     }
     return Replace(quotient);
   }
   return NoChange();
 }
 
 
 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) {
   Uint32BinopMatcher m(node);
   if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
   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
   if (m.IsFoldable()) {                                   // K / K => K
     return ReplaceUint32(
         base::bits::UnsignedDiv32(m.left().Value(), m.right().Value()));
   }
   if (m.LeftEqualsRight()) {  // x / x => x != 0
     Node* const zero = Int32Constant(0);
     return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
   }
-  if (m.right().IsPowerOf2()) {  // x / 2^n => x >> n
-    node->TrimInputCount(2);
-    node->set_op(machine()->Word32Shr());
-    node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value())));
-    return Changed(node);
+  if (m.right().HasValue()) {
+    Node* const dividend = m.left().node();
+    uint32_t const divisor = m.right().Value();
+    if (base::bits::IsPowerOfTwo32(divisor)) {  // x / 2^n => x >> n
+      node->set_op(machine()->Word32Shr());
+      node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value())));
+      node->TrimInputCount(2);
+      return Changed(node);
+    } else {
+      return Replace(Uint32Div(dividend, divisor));
+    }
   }
   return NoChange();
 }
 
 
 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
   Int32BinopMatcher m(node);
   if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x  => 0
   if (m.right().Is(0)) return Replace(m.right().node());  // x % 0  => 0
   if (m.right().Is(1)) return ReplaceInt32(0);            // x % 1  => 0
@@ skipping 15 matching lines @@
       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);
+
+      DCHECK_EQ(3, node->InputCount());
+      node->set_op(common()->Phi(kMachInt32, 2));
+      node->ReplaceInput(0, neg);
+      node->ReplaceInput(1, pos);
+      node->ReplaceInput(2, merge);
     } else {
-      Node* quotient = TruncatingDiv(dividend, divisor);
+      Node* quotient = Int32Div(dividend, divisor);
       node->set_op(machine()->Int32Sub());
       DCHECK_EQ(dividend, node->InputAt(0));
       node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
       node->TrimInputCount(2);
-      return Changed(node);
     }
+    return Changed(node);
   }
   return NoChange();
 }
 
 
 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) {
   Uint32BinopMatcher m(node);
   if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x => 0
   if (m.right().Is(0)) return Replace(m.right().node());  // x % 0 => 0
   if (m.right().Is(1)) return ReplaceUint32(0);           // x % 1 => 0
   if (m.LeftEqualsRight()) return ReplaceInt32(0);        // x % x  => 0
   if (m.IsFoldable()) {                                   // K % K => K
     return ReplaceUint32(
         base::bits::UnsignedMod32(m.left().Value(), m.right().Value()));
   }
-  if (m.right().IsPowerOf2()) {  // x % 2^n => x & 2^n-1
+  if (m.right().HasValue()) {
+    Node* const dividend = m.left().node();
+    uint32_t const divisor = m.right().Value();
+    if (base::bits::IsPowerOfTwo32(divisor)) {  // x % 2^n => x & 2^n-1
+      node->set_op(machine()->Word32And());
+      node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1));
+    } else {
+      Node* quotient = Uint32Div(dividend, divisor);
+      node->set_op(machine()->Int32Sub());
+      DCHECK_EQ(dividend, node->InputAt(0));
+      node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor)));
+    }
     node->TrimInputCount(2);
-    node->set_op(machine()->Word32And());
-    node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1));
     return Changed(node);
   }
   return NoChange();
 }
 
 
 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kInt32AddWithOverflow: {
       DCHECK(index == 0 || index == 1);
@@ skipping 38 matching lines @@
 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
   return jsgraph()->machine();
 }
 
 
 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8