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 <cstring>
8
9 #include "src/base/functional.h"
10 #include "src/compiler/node.h"
11
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
16 namespace {
17
HashCode(Node * node)18 size_t HashCode(Node* node) {
19 size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
20 for (int j = 0; j < node->InputCount(); ++j) {
21 h = base::hash_combine(h, node->InputAt(j)->id());
22 }
23 return h;
24 }
25
26
Equals(Node * a,Node * b)27 bool Equals(Node* a, Node* b) {
28 DCHECK_NOT_NULL(a);
29 DCHECK_NOT_NULL(b);
30 DCHECK_NOT_NULL(a->op());
31 DCHECK_NOT_NULL(b->op());
32 if (!a->op()->Equals(b->op())) return false;
33 if (a->InputCount() != b->InputCount()) return false;
34 for (int j = 0; j < a->InputCount(); ++j) {
35 DCHECK_NOT_NULL(a->InputAt(j));
36 DCHECK_NOT_NULL(b->InputAt(j));
37 if (a->InputAt(j)->id() != b->InputAt(j)->id()) return false;
38 }
39 return true;
40 }
41
42 } // namespace
43
44
ValueNumberingReducer(Zone * zone)45 ValueNumberingReducer::ValueNumberingReducer(Zone* zone)
46 : entries_(nullptr), capacity_(0), size_(0), zone_(zone) {}
47
48
~ValueNumberingReducer()49 ValueNumberingReducer::~ValueNumberingReducer() {}
50
51
Reduce(Node * node)52 Reduction ValueNumberingReducer::Reduce(Node* node) {
53 if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
54
55 const size_t hash = HashCode(node);
56 if (!entries_) {
57 DCHECK(size_ == 0);
58 DCHECK(capacity_ == 0);
59 // Allocate the initial entries and insert the first entry.
60 capacity_ = kInitialCapacity;
61 entries_ = zone()->NewArray<Node*>(kInitialCapacity);
62 memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
63 entries_[hash & (kInitialCapacity - 1)] = node;
64 size_ = 1;
65 return NoChange();
66 }
67
68 DCHECK(size_ < capacity_);
69 DCHECK(size_ * kCapacityToSizeRatio < capacity_);
70
71 const size_t mask = capacity_ - 1;
72 size_t dead = capacity_;
73
74 for (size_t i = hash & mask;; i = (i + 1) & mask) {
75 Node* entry = entries_[i];
76 if (!entry) {
77 if (dead != capacity_) {
78 // Reuse dead entry that we discovered on the way.
79 entries_[dead] = node;
80 } else {
81 // Have to insert a new entry.
82 entries_[i] = node;
83 size_++;
84
85 // Resize to keep load factor below 1/kCapacityToSizeRatio.
86 if (size_ * kCapacityToSizeRatio >= capacity_) Grow();
87 }
88 DCHECK(size_ * kCapacityToSizeRatio < capacity_);
89 return NoChange();
90 }
91
92 if (entry == node) {
93 // We need to check for a certain class of collisions here. Imagine the
94 // following scenario:
95 //
96 // 1. We insert node1 with op1 and certain inputs at index i.
97 // 2. We insert node2 with op2 and certain inputs at index i+1.
98 // 3. Some other reducer changes node1 to op2 and the inputs from node2.
99 //
100 // Now we are called again to reduce node1, and we would return NoChange
101 // in this case because we find node1 first, but what we should actually
102 // do is return Replace(node2) instead.
103 for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
104 Node* entry = entries_[j];
105 if (!entry) {
106 // No collision, {node} is fine.
107 return NoChange();
108 }
109 if (entry->IsDead()) {
110 continue;
111 }
112 if (Equals(entry, node)) {
113 // Overwrite the colliding entry with the actual entry.
114 entries_[i] = entry;
115 return Replace(entry);
116 }
117 }
118 }
119
120 // Skip dead entries, but remember their indices so we can reuse them.
121 if (entry->IsDead()) {
122 dead = i;
123 continue;
124 }
125 if (Equals(entry, node)) {
126 return Replace(entry);
127 }
128 }
129 }
130
131
Grow()132 void ValueNumberingReducer::Grow() {
133 // Allocate a new block of entries kCapacityToSizeRatio times the previous
134 // capacity.
135 Node** const old_entries = entries_;
136 size_t const old_capacity = capacity_;
137 capacity_ *= kCapacityToSizeRatio;
138 entries_ = zone()->NewArray<Node*>(capacity_);
139 memset(entries_, 0, sizeof(*entries_) * capacity_);
140 size_ = 0;
141 size_t const mask = capacity_ - 1;
142
143 // Insert the old entries into the new block (skipping dead nodes).
144 for (size_t i = 0; i < old_capacity; ++i) {
145 Node* const old_entry = old_entries[i];
146 if (!old_entry || old_entry->IsDead()) continue;
147 for (size_t j = HashCode(old_entry) & mask;; j = (j + 1) & mask) {
148 Node* const entry = entries_[j];
149 if (entry == old_entry) {
150 // Skip duplicate of the old entry.
151 break;
152 }
153 if (!entry) {
154 entries_[j] = old_entry;
155 size_++;
156 break;
157 }
158 }
159 }
160 }
161
162 } // namespace compiler
163 } // namespace internal
164 } // namespace v8
165