binary-operator-reducer: reduce mul+div(shift)

src/compiler/binary-operator-reducer.cc

Index: src/compiler/binary-operator-reducer.cc
diff --git a/src/compiler/binary-operator-reducer.cc b/src/compiler/binary-operator-reducer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..a9a5d4fe5e301a5de2fcdf7d72a9a147cfb7069c
--- /dev/null
+++ b/src/compiler/binary-operator-reducer.cc
@@ -0,0 +1,143 @@
+// Copyright 2015 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/binary-operator-reducer.h"
+
+#include <algorithm>
+
+#include "src/compiler/common-operator.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/machine-operator.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/node-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+BinaryOperatorReducer::BinaryOperatorReducer(Editor* editor, Graph* graph,
+                                             CommonOperatorBuilder* common,
+                                             MachineOperatorBuilder* machine)
+    : AdvancedReducer(editor),
+      graph_(graph),
+      common_(common),
+      machine_(machine),
+      dead_(graph->NewNode(common->Dead())) {}
+
+
+Reduction BinaryOperatorReducer::Reduce(Node* node) {
+  switch (node->opcode()) {
+    case IrOpcode::kFloat64Mul:
+      return ReduceFloat64Mul(node);
+    default:
+      break;
+  }
+  return NoChange();
+}
+
+
+Reduction BinaryOperatorReducer::ReduceFloat64Mul(Node* node) {

[titzer, 2015/09/29 11:18:06]

If you do this optimization at the site of the division, then you won't have to
hunt through uses of this multiply.

[fedor.indutny, 2015/10/02 02:54:30]

On one hand - yes, on other hand - doing it at the multiplication means more
flexibility, and more general optimization. While bn.js use case does both
division and cast to int (via `num | 0`), some code may be doing just the latter
one without dividing it all. I would rather keep it working at multiplication
node.

+  if (node->InputAt(0)->opcode() != IrOpcode::kChangeInt32ToFloat64) {
+    return NoChange();
+  }
+  if (node->InputAt(1)->opcode() != IrOpcode::kChangeInt32ToFloat64) {
+    return NoChange();
+  }
+
+  Type::RangeType* range = NodeProperties::GetType(node)->GetRange();
+
+  // JavaScript has 52 bit precision in multiplication
+  if (range == nullptr || range->Min() < 0.0 ||
+      range->Max() > 0xFFFFFFFFFFFFFULL) {
+    return NoChange();
+  }
+
+  // Verify that the uses cast result to Int32
+  for (Node* use : node->uses()) {

[titzer, 2015/09/29 11:18:06]

Generally reductions shouldn't be iterating over the uses of an instruction. You
should match the "root" of the graph of nodes that you want to transform.

[fedor.indutny, 2015/10/02 02:54:30]

I'm looking both up in the tree and down in the tree. Not sure if it could be
done differently. Perhaps you have more exact suggestions for me?

[titzer, 2015/10/06 23:14:10]

Yes. What I meant is that reductions are applied in a specific order to the
nodes in the graph, and work best when reducing the "root" of a tree _after_
having first reduced the inputs. The GraphReducer algorithm gives you this order
for free. When you are looking at uses of a node, you are generally look at
unreduced nodes and may miss an opportunity; or you might see some uses that
will later get trimmed away. That's why it's usually better to apply your
matching/optimization at the so called "root" of the graph of nodes you want to
match; it will interact better with the order of visitation and generally be
safer.

+    // XXX: How to handle this properly?
+    if (use->opcode() == IrOpcode::kStateValues) continue;
+
+    if (use->opcode() == IrOpcode::kTruncateFloat64ToInt32) continue;
+    if (use->opcode() != IrOpcode::kFloat64Div) return NoChange();
+
+    // Verify division
+    //
+    // The RHS value should be positive integer
+    Float64BinopMatcher m(use);
+    if (!m.right().HasValue() || m.right().Value() <= 0) return NoChange();
+
+    int64_t value = static_cast<int64_t>(m.right().Value());
+    if (value != static_cast<int64_t>(m.right().Value())) return NoChange();
+    if (!base::bits::IsPowerOfTwo64(value)) return NoChange();
+
+    // The result should fit into 32bit word
+    if ((static_cast<int64_t>(range->Max()) / value) > 0xFFFFFFFULL) {
+      return NoChange();
+    }
+
+    // Check that uses of division are cast to Int32
+    for (Node* subuse : use->uses()) {
+      // XXX: How to handle this properly?
+      if (subuse->opcode() == IrOpcode::kStateValues) continue;
+
+      if (subuse->opcode() != IrOpcode::kTruncateFloat64ToInt32) {
+        return NoChange();
+      }
+    }
+  }
+
+  // The mul+div can be optimized
+  for (Node* use : node->uses()) {
+    // XXX: How to handle this properly?
+    if (use->opcode() == IrOpcode::kStateValues) continue;
+
+    if (use->opcode() == IrOpcode::kTruncateFloat64ToInt32) {
+      use->set_op(machine()->TruncateInt64ToInt32());
+      Revisit(use);
+      continue;
+    }
+
+    Float64BinopMatcher m(use);
+    int64_t shift = WhichPowerOf2_64(static_cast<int64_t>(m.right().Value()));
+
+    use->set_op(machine()->Word64Shr());
+    use->ReplaceInput(1, graph()->NewNode(common()->Int64Constant(shift)));
+    Revisit(use);
+
+    for (Node* subuse : use->uses()) {
+      // XXX: How to handle this properly?
+      if (subuse->opcode() == IrOpcode::kStateValues) continue;
+
+      subuse->set_op(machine()->TruncateInt64ToInt32());
+      Revisit(subuse);
+    }
+  }
+
+  return Change(node, machine()->Int64Mul(), node->InputAt(0)->InputAt(0),
+                node->InputAt(1)->InputAt(0));

[titzer, 2015/09/29 11:21:59]

TurboFan also only supports Int64Mul on 64-bit platforms (for the moment; we
will probably fill in 32-bit support, but it won't be as fast as a Float64Mul,
likely).

[fedor.indutny, 2015/10/02 02:54:30]

What would be the best way to make this a platform specific reduction then?

[titzer, 2015/10/06 23:14:10]

Just check machine()->Is64()

+}
+
+
+Reduction BinaryOperatorReducer::Change(Node* node, Operator const* op,
+                                        Node* a) {
+  node->set_op(op);
+  node->ReplaceInput(0, a);
+  node->TrimInputCount(1);
+  return Changed(node);
+}
+
+
+Reduction BinaryOperatorReducer::Change(Node* node, Operator const* op, Node* a,
+                                        Node* b) {
+  node->set_op(op);
+  node->ReplaceInput(0, a);
+  node->ReplaceInput(1, b);
+  node->TrimInputCount(2);
+  return Changed(node);
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8