• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/compiler/value-numbering-reducer.h"
6 
7 #include "src/compiler/node.h"
8 
9 namespace v8 {
10 namespace internal {
11 namespace compiler {
12 
13 namespace {
14 
HashCode(Node * node)15 size_t HashCode(Node* node) { return node->op()->HashCode(); }
16 
17 
Equals(Node * a,Node * b)18 bool Equals(Node* a, Node* b) {
19   DCHECK_NOT_NULL(a);
20   DCHECK_NOT_NULL(b);
21   DCHECK_NOT_NULL(a->op());
22   DCHECK_NOT_NULL(b->op());
23   if (!a->op()->Equals(b->op())) return false;
24   if (a->InputCount() != b->InputCount()) return false;
25   for (int j = 0; j < a->InputCount(); ++j) {
26     DCHECK_NOT_NULL(a->InputAt(j));
27     DCHECK_NOT_NULL(b->InputAt(j));
28     if (a->InputAt(j)->id() != b->InputAt(j)->id()) return false;
29   }
30   return true;
31 }
32 
33 }  // namespace
34 
35 
36 class ValueNumberingReducer::Entry FINAL : public ZoneObject {
37  public:
Entry(Node * node,Entry * next)38   Entry(Node* node, Entry* next) : node_(node), next_(next) {}
39 
node() const40   Node* node() const { return node_; }
next() const41   Entry* next() const { return next_; }
42 
43  private:
44   Node* node_;
45   Entry* next_;
46 };
47 
48 
ValueNumberingReducer(Zone * zone)49 ValueNumberingReducer::ValueNumberingReducer(Zone* zone) : zone_(zone) {
50   for (size_t i = 0; i < arraysize(buckets_); ++i) {
51     buckets_[i] = NULL;
52   }
53 }
54 
55 
~ValueNumberingReducer()56 ValueNumberingReducer::~ValueNumberingReducer() {}
57 
58 
Reduce(Node * node)59 Reduction ValueNumberingReducer::Reduce(Node* node) {
60   Entry** head = &buckets_[HashCode(node) % arraysize(buckets_)];
61   for (Entry* entry = *head; entry; entry = entry->next()) {
62     if (entry->node()->IsDead()) continue;
63     if (entry->node() == node) return NoChange();
64     if (Equals(node, entry->node())) {
65       return Replace(entry->node());
66     }
67   }
68   *head = new (zone()) Entry(node, *head);
69   return NoChange();
70 }
71 
72 }  // namespace compiler
73 }  // namespace internal
74 }  // namespace v8
75