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..f08924a6e2d0132a24c5b5566a9e63bd48c01fef
--- /dev/null
+++ b/src/compiler/binary-operator-reducer.cc
@@ -0,0 +1,140 @@
+// 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"
+#include "src/types-inl.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 ReduceFloat52Mul(node);
+    case IrOpcode::kFloat64Div:
+      return ReduceFloat52Div(node);
+    case IrOpcode::kTruncateFloat64ToInt32:
+      return ReduceTruncateFloat64ToInt32(node);
+    default:
+      break;
+  }
+  return NoChange();
+}
+
+
+Reduction BinaryOperatorReducer::ReduceFloat52Mul(Node* node) {
+  if (!machine()->Is64()) return NoChange();

[titzer, 2015/10/16 18:44:06]

You can use a BinopMatcher here to make this a bit shorter.

[fedor.indutny, 2015/10/16 22:30:38]

I wasn't able to use BinopMatcher, but I have declared `left` and `right`
variables. To use `BinopMatcher`, I will need to write some kind of custom
`NodeMatcher`s, that have `HasValue` (not sure if `ValueMatcher` will work for
this purpose, because of the parameter casting).

Hope it works.

+
+  if (node->InputAt(0)->opcode() != IrOpcode::kChangeInt32ToFloat64 ||
+      node->InputAt(1)->opcode() != IrOpcode::kChangeInt32ToFloat64) {

[titzer, 2015/10/16 18:44:06]

My earlier comment about using the range types applied to the inputs. So if you
check the input ranges, you won't need to pattern match on the opcodes. Range
types are always integers in the type system.

[fedor.indutny, 2015/10/16 18:52:35]

But the idea here is that the original values were integers, and not floats.
Otherwise I will need to cast them to ints to do Int64Mul, right? This cast will
make this code slower for the case, where the multiplication is not fed into
truncation, or division.

+    return NoChange();
+  }
+
+  Type* type = NodeProperties::GetType(node);
+  Type::RangeType* range = type->GetRange();
+
+  // JavaScript has 52 bit precision in multiplication
+  if (range == nullptr || range->Min() < 0.0 ||
+      range->Max() > 0xFFFFFFFFFFFFFULL) {
+    return NoChange();
+  }
+
+  Node* mul =
+      graph()->NewNode(machine()->Int64Mul(), node->InputAt(0)->InputAt(0),
+                       node->InputAt(1)->InputAt(0));
+  Revisit(mul);
+
+  Type* range_type = Type::Range(range->Min(), range->Max(), graph()->zone());
+
+  // TODO(indutny): Is Type::Number() a proper thing here? It looks like
+  // every other place is using Type:Internal() for int64 values.
+  // Should we off-load range propagation to Typer?
+  NodeProperties::SetType(
+      mul, Type::Intersect(range_type, Type::Number(), graph()->zone()));
+
+  Node* out = graph()->NewNode(machine()->TruncateInt64ToFloat64(), mul);
+  Revisit(out);

[titzer, 2015/10/16 18:44:06]

No need for revisits; the graph reducer takes care of that for you.

[fedor.indutny, 2015/10/16 18:52:35]

Acknowledged.

+  return Replace(out);
+}
+
+
+Reduction BinaryOperatorReducer::ReduceFloat52Div(Node* node) {

[titzer, 2015/10/16 18:44:06]

The optimization here with division is only sound if it is fed into a truncation
(i.e. conversion to integer), so you'll need to match that at the bottom of the
pattern.

[fedor.indutny, 2015/10/16 18:52:35]

Hm... Not sure I understand why. I have modeled it that way that it should be
semantically correct on every step of reduction.

Div(Int64ToFloat64(A), POWER_OF_TWO) is replaced with Int64ToFloat(SHR(A),
SHIFT). So the result is correct, I think?

[titzer, 2015/10/16 19:51:54]

Because the fractional bits would be lost. Which is OK if the operation feeds
into another truncation, which discards those bits anyway.

[fedor.indutny, 2015/10/16 19:54:19]

Oooh, this makes sense! However this is not going to play very nicely with the
reducer, isn't it?

+  if (!machine()->Is64()) return NoChange();
+  if (node->InputAt(0)->opcode() != IrOpcode::kTruncateInt64ToFloat64) {
+    return NoChange();
+  }
+
+  Float64BinopMatcher m(node);
+
+  // Right value should be positive...
+  if (!m.right().HasValue() || m.right().Value() <= 0) return NoChange();
+
+  // ...integer...
+  int64_t value = static_cast<int64_t>(m.right().Value());
+  if (value != static_cast<int64_t>(m.right().Value())) return NoChange();
+
+  // ...and should be a power of two.
+  if (!base::bits::IsPowerOfTwo64(value)) return NoChange();
+
+  Node* left = node->InputAt(0)->InputAt(0);
+  Type::RangeType* range = NodeProperties::GetType(left)->GetRange();
+
+  // The result should fit into 32bit word
+  if ((static_cast<int64_t>(range->Max()) / value) > 0xFFFFFFFULL) {
+    return NoChange();
+  }
+
+  int64_t shift = WhichPowerOf2_64(static_cast<int64_t>(m.right().Value()));
+
+  // Replace division with 64bit right shift
+  Node* shr =
+      graph()->NewNode(machine()->Word64Shr(), left,
+                       graph()->NewNode(common()->Int64Constant(shift)));
+  Revisit(shr);
+
+  Node* out = graph()->NewNode(machine()->TruncateInt64ToFloat64(), shr);
+  Revisit(out);
+  return Replace(out);
+}
+
+
+Reduction BinaryOperatorReducer::ReduceTruncateFloat64ToInt32(Node* node) {
+  Node* input = node->InputAt(0);
+  if (input->opcode() != IrOpcode::kTruncateInt64ToFloat64) return NoChange();
+
+  return Replace(input->InputAt(0));
+}
+
+
+Reduction BinaryOperatorReducer::Change(Node* node, Operator const* op,
+                                        Node* a) {
+  node->set_op(op);
+  node->ReplaceInput(0, a);
+  node->TrimInputCount(1);
+  return Changed(node);
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8