[turbofan] Initial version of ValueNumberingReducer.

src/compiler/value-numbering-reducer.cc

Index: src/compiler/value-numbering-reducer.cc
diff --git a/src/compiler/value-numbering-reducer.cc b/src/compiler/value-numbering-reducer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..fe9ae94da0aa5323a4487a97704bcffeeec0b6d0
--- /dev/null
+++ b/src/compiler/value-numbering-reducer.cc
@@ -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() { return next_; }

[Michael Starzinger, 2014/09/04 11:07:40]

nit: const?

+
+ 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