Revision: 23686
Author: [email protected]
Date: Thu Sep 4 11:13:35 2014 UTC
Log: [turbofan] Initial version of ValueNumberingReducer.
TEST=compiler-unittests,cctest,mjsunit
[email protected], [email protected]
Review URL: https://codereview.chromium.org/539503002
https://code.google.com/p/v8/source/detail?r=23686
Added:
/branches/bleeding_edge/src/compiler/value-numbering-reducer-unittest.cc
/branches/bleeding_edge/src/compiler/value-numbering-reducer.cc
/branches/bleeding_edge/src/compiler/value-numbering-reducer.h
Modified:
/branches/bleeding_edge/BUILD.gn
/branches/bleeding_edge/src/compiler/compiler.gyp
/branches/bleeding_edge/src/compiler/js-graph.cc
/branches/bleeding_edge/src/compiler/machine-operator.h
/branches/bleeding_edge/src/compiler/pipeline.cc
/branches/bleeding_edge/tools/gyp/v8.gyp
=======================================
--- /dev/null
+++
/branches/bleeding_edge/src/compiler/value-numbering-reducer-unittest.cc
Thu Sep 4 11:13:35 2014 UTC
@@ -0,0 +1,108 @@
+// 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 <limits>
+
+#include "src/compiler/graph.h"
+#include "src/compiler/value-numbering-reducer.h"
+#include "src/test/test-utils.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+namespace {
+
+const SimpleOperator kOp0(0, Operator::kNoProperties, 0, 1, "op0");
+
+} // namespace
+
+
+class ValueNumberingReducerTest : public TestWithZone {
+ public:
+ ValueNumberingReducerTest() : graph_(zone()), reducer_(zone()) {}
+
+ protected:
+ Reduction Reduce(Node* node) { return reducer_.Reduce(node); }
+
+ Graph* graph() { return &graph_; }
+
+ private:
+ Graph graph_;
+ ValueNumberingReducer reducer_;
+};
+
+
+TEST_F(ValueNumberingReducerTest, AllInputsAreChecked) {
+ Node* na = graph()->NewNode(&kOp0);
+ Node* nb = graph()->NewNode(&kOp0);
+ Node* n1 = graph()->NewNode(&kOp0, na);
+ Node* n2 = graph()->NewNode(&kOp0, nb);
+ EXPECT_FALSE(Reduce(n1).Changed());
+ EXPECT_FALSE(Reduce(n2).Changed());
+}
+
+
+TEST_F(ValueNumberingReducerTest, KilledNodesAreNeverReturned) {
+ Node* n1 = graph()->NewNode(&kOp0);
+ EXPECT_FALSE(Reduce(n1).Changed());
+ n1->Kill();
+ EXPECT_FALSE(Reduce(graph()->NewNode(&kOp0)).Changed());
+}
+
+
+TEST_F(ValueNumberingReducerTest, OperatorEqualityNotIdentity) {
+ static const size_t kMaxInputCount = 16;
+ Node* inputs[kMaxInputCount];
+ for (size_t i = 0; i < arraysize(inputs); ++i) {
+ Operator::Opcode opcode = static_cast<Operator::Opcode>(
+ std::numeric_limits<Operator::Opcode>::max() - i);
+ inputs[i] = graph()->NewNode(new (zone()) SimpleOperator(
+ opcode, Operator::kNoProperties, 0, 1, "Operator"));
+ }
+ TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) {
+ const SimpleOperator op1(static_cast<Operator::Opcode>(input_count),
+ Operator::kNoProperties, input_count,
1, "op");
+ Node* n1 = graph()->NewNode(&op1, input_count, inputs);
+ Reduction r1 = Reduce(n1);
+ EXPECT_FALSE(r1.Changed());
+
+ const SimpleOperator op2(static_cast<Operator::Opcode>(input_count),
+ Operator::kNoProperties, input_count,
1, "op");
+ Node* n2 = graph()->NewNode(&op2, input_count, inputs);
+ Reduction r2 = Reduce(n2);
+ EXPECT_TRUE(r2.Changed());
+ EXPECT_EQ(n1, r2.replacement());
+ }
+}
+
+
+TEST_F(ValueNumberingReducerTest, SubsequentReductionsYieldTheSameNode) {
+ static const size_t kMaxInputCount = 16;
+ Node* inputs[kMaxInputCount];
+ for (size_t i = 0; i < arraysize(inputs); ++i) {
+ Operator::Opcode opcode = static_cast<Operator::Opcode>(
+ std::numeric_limits<Operator::Opcode>::max() - i);
+ inputs[i] = graph()->NewNode(new (zone()) SimpleOperator(
+ opcode, Operator::kNoProperties, 0, 1, "Operator"));
+ }
+ TRACED_FORRANGE(size_t, input_count, 0, arraysize(inputs)) {
+ const SimpleOperator op1(1, Operator::kNoProperties, input_count,
1, "op1");
+ Node* n = graph()->NewNode(&op1, input_count, inputs);
+ Reduction r = Reduce(n);
+ EXPECT_FALSE(r.Changed());
+
+ r = Reduce(graph()->NewNode(&op1, input_count, inputs));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_EQ(n, r.replacement());
+
+ r = Reduce(graph()->NewNode(&op1, input_count, inputs));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_EQ(n, r.replacement());
+ }
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/compiler/value-numbering-reducer.cc Thu
Sep 4 11:13:35 2014 UTC
@@ -0,0 +1,73 @@
+// 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/value-numbering-reducer.h"
+
+#include "src/compiler/node.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+namespace {
+
+size_t HashCode(Node* node) { return node->op()->HashCode(); }
+
+
+bool Equals(Node* a, Node* b) {
+ DCHECK_NOT_NULL(a);
+ DCHECK_NOT_NULL(b);
+ DCHECK_NOT_NULL(a->op());
+ DCHECK_NOT_NULL(b->op());
+ if (!a->op()->Equals(b->op())) return false;
+ if (a->InputCount() != b->InputCount()) return false;
+ for (int j = 0; j < a->InputCount(); ++j) {
+ DCHECK_NOT_NULL(a->InputAt(j));
+ DCHECK_NOT_NULL(b->InputAt(j));
+ if (a->InputAt(j)->id() != b->InputAt(j)->id()) return false;
+ }
+ return true;
+}
+
+} // namespace
+
+
+class ValueNumberingReducer::Entry FINAL : public ZoneObject {
+ public:
+ Entry(Node* node, Entry* next) : node_(node), next_(next) {}
+
+ Node* node() const { return node_; }
+ Entry* next() const { return next_; }
+
+ private:
+ Node* node_;
+ Entry* next_;
+};
+
+
+ValueNumberingReducer::ValueNumberingReducer(Zone* zone) : zone_(zone) {
+ for (size_t i = 0; i < arraysize(buckets_); ++i) {
+ buckets_[i] = NULL;
+ }
+}
+
+
+ValueNumberingReducer::~ValueNumberingReducer() {}
+
+
+Reduction ValueNumberingReducer::Reduce(Node* node) {
+ Entry** head = &buckets_[HashCode(node) % arraysize(buckets_)];
+ for (Entry* entry = *head; entry; entry = entry->next()) {
+ if (entry->node()->op() == NULL) continue;
+ if (Equals(node, entry->node())) {
+ return Replace(entry->node());
+ }
+ }
+ *head = new (zone()) Entry(node, *head);
+ return NoChange();
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/compiler/value-numbering-reducer.h Thu Sep
4 11:13:35 2014 UTC
@@ -0,0 +1,36 @@
+// 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.
+
+#ifndef V8_COMPILER_VALUE_NUMBERING_REDUCER_H_
+#define V8_COMPILER_VALUE_NUMBERING_REDUCER_H_
+
+#include "src/compiler/graph-reducer.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class ValueNumberingReducer FINAL : public Reducer {
+ public:
+ explicit ValueNumberingReducer(Zone* zone);
+ ~ValueNumberingReducer();
+
+ virtual Reduction Reduce(Node* node) OVERRIDE;
+
+ private:
+ Zone* zone() const { return zone_; }
+
+ // TODO(turbofan): We currently use separate chaining with linked lists
here,
+ // we may want to replace that with a more sophisticated data structure
at
+ // some point in the future.
+ class Entry;
+ Entry* buckets_[117u];
+ Zone* zone_;
+};
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+
+#endif // V8_COMPILER_VALUE_NUMBERING_REDUCER_H_
=======================================
--- /branches/bleeding_edge/BUILD.gn Thu Sep 4 10:23:51 2014 UTC
+++ /branches/bleeding_edge/BUILD.gn Thu Sep 4 11:13:35 2014 UTC
@@ -554,6 +554,8 @@
"src/compiler/source-position.h",
"src/compiler/typer.cc",
"src/compiler/typer.h",
+ "src/compiler/value-numbering-reducer.cc",
+ "src/compiler/value-numbering-reducer.h",
"src/compiler/verifier.cc",
"src/compiler/verifier.h",
"src/compiler.cc",
=======================================
--- /branches/bleeding_edge/src/compiler/compiler.gyp Thu Sep 4 09:22:10
2014 UTC
+++ /branches/bleeding_edge/src/compiler/compiler.gyp Thu Sep 4 11:13:35
2014 UTC
@@ -29,6 +29,7 @@
'machine-operator-reducer-unittest.cc',
'machine-operator-unittest.cc',
'simplified-operator-reducer-unittest.cc',
+ 'value-numbering-reducer-unittest.cc',
],
'conditions': [
['v8_target_arch=="arm"', {
=======================================
--- /branches/bleeding_edge/src/compiler/js-graph.cc Mon Aug 18 06:54:07
2014 UTC
+++ /branches/bleeding_edge/src/compiler/js-graph.cc Thu Sep 4 11:13:35
2014 UTC
@@ -104,8 +104,14 @@
// TODO(titzer): We could also match against the addresses of immortable
// immovables here, even without access to the heap, thus always
// canonicalizing references to them.
- return HeapConstant(
- PrintableUnique<Object>::CreateUninitialized(zone(), value));
+ // return HeapConstant(
+ // PrintableUnique<Object>::CreateUninitialized(zone(), value));
+ // TODO(turbofan): This is a work-around to make Unique::HashCode() work
for
+ // value numbering. We need some sane way to compute a unique hash code
for
+ // arbitrary handles here.
+ PrintableUnique<Object> unique(
+ zone(), reinterpret_cast<Address>(*value.location()), value);
+ return HeapConstant(unique);
}
=======================================
--- /branches/bleeding_edge/src/compiler/machine-operator.h Wed Sep 3
12:43:41 2014 UTC
+++ /branches/bleeding_edge/src/compiler/machine-operator.h Thu Sep 4
11:13:35 2014 UTC
@@ -26,6 +26,17 @@
};
+// TODO(bmeurer): Phi will probably also need this in the future.
+template <>
+struct StaticParameterTraits<MachineType> {
+ static OStream& PrintTo(OStream& os, MachineType type) { // NOLINT
+ return os << type;
+ }
+ static int HashCode(MachineType type) { return type; }
+ static bool Equals(MachineType lhs, MachineType rhs) { return lhs ==
rhs; }
+};
+
+
// Interface for building machine-level operators. These operators are
// machine-level but machine-independent and thus define a language
suitable
// for generating code to run on architectures such as ia32, x64, arm, etc.
=======================================
--- /branches/bleeding_edge/src/compiler/pipeline.cc Tue Sep 2 07:07:52
2014 UTC
+++ /branches/bleeding_edge/src/compiler/pipeline.cc Thu Sep 4 11:13:35
2014 UTC
@@ -24,6 +24,7 @@
#include "src/compiler/simplified-lowering.h"
#include "src/compiler/simplified-operator-reducer.h"
#include "src/compiler/typer.h"
+#include "src/compiler/value-numbering-reducer.h"
#include "src/compiler/verifier.h"
#include "src/hydrogen.h"
#include "src/ostreams.h"
@@ -255,11 +256,13 @@
SourcePosition::Unknown());
Linkage linkage(info());
MachineOperatorBuilder machine(zone());
+ ValueNumberingReducer vn_reducer(zone());
SimplifiedOperatorReducer simple_reducer(&jsgraph, &machine);
ChangeLowering lowering(&jsgraph, &linkage, &machine);
MachineOperatorReducer mach_reducer(&jsgraph);
GraphReducer graph_reducer(&graph);
// TODO(titzer): Figure out if we should run all reducers at once
here.
+ graph_reducer.AddReducer(&vn_reducer);
graph_reducer.AddReducer(&simple_reducer);
graph_reducer.AddReducer(&lowering);
graph_reducer.AddReducer(&mach_reducer);
=======================================
--- /branches/bleeding_edge/tools/gyp/v8.gyp Thu Sep 4 10:23:51 2014 UTC
+++ /branches/bleeding_edge/tools/gyp/v8.gyp Thu Sep 4 11:13:35 2014 UTC
@@ -466,6 +466,8 @@
'../../src/compiler/source-position.h',
'../../src/compiler/typer.cc',
'../../src/compiler/typer.h',
+ '../../src/compiler/value-numbering-reducer.cc',
+ '../../src/compiler/value-numbering-reducer.h',
'../../src/compiler/verifier.cc',
'../../src/compiler/verifier.h',
'../../src/compiler.cc',
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
