1 // Copyright 2015 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/state-values-utils.h"
6
7 namespace v8 {
8 namespace internal {
9 namespace compiler {
10
StateValuesCache(JSGraph * js_graph)11 StateValuesCache::StateValuesCache(JSGraph* js_graph)
12 : js_graph_(js_graph),
13 hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
14 ZoneAllocationPolicy(zone())),
15 working_space_(zone()),
16 empty_state_values_(nullptr) {}
17
18
19 // static
AreKeysEqual(void * key1,void * key2)20 bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
21 NodeKey* node_key1 = reinterpret_cast<NodeKey*>(key1);
22 NodeKey* node_key2 = reinterpret_cast<NodeKey*>(key2);
23
24 if (node_key1->node == nullptr) {
25 if (node_key2->node == nullptr) {
26 return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
27 reinterpret_cast<StateValuesKey*>(key2));
28 } else {
29 return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
30 node_key2->node);
31 }
32 } else {
33 if (node_key2->node == nullptr) {
34 // If the nodes are already processed, they must be the same.
35 return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key2),
36 node_key1->node);
37 } else {
38 return node_key1->node == node_key2->node;
39 }
40 }
41 UNREACHABLE();
42 }
43
44
45 // static
IsKeysEqualToNode(StateValuesKey * key,Node * node)46 bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
47 if (key->count != static_cast<size_t>(node->InputCount())) {
48 return false;
49 }
50 for (size_t i = 0; i < key->count; i++) {
51 if (key->values[i] != node->InputAt(static_cast<int>(i))) {
52 return false;
53 }
54 }
55 return true;
56 }
57
58
59 // static
AreValueKeysEqual(StateValuesKey * key1,StateValuesKey * key2)60 bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
61 StateValuesKey* key2) {
62 if (key1->count != key2->count) {
63 return false;
64 }
65 for (size_t i = 0; i < key1->count; i++) {
66 if (key1->values[i] != key2->values[i]) {
67 return false;
68 }
69 }
70 return true;
71 }
72
73
GetEmptyStateValues()74 Node* StateValuesCache::GetEmptyStateValues() {
75 if (empty_state_values_ == nullptr) {
76 empty_state_values_ = graph()->NewNode(common()->StateValues(0));
77 }
78 return empty_state_values_;
79 }
80
81
GetWorkingSpace(size_t level)82 NodeVector* StateValuesCache::GetWorkingSpace(size_t level) {
83 while (working_space_.size() <= level) {
84 void* space = zone()->New(sizeof(NodeVector));
85 working_space_.push_back(new (space)
86 NodeVector(kMaxInputCount, nullptr, zone()));
87 }
88 return working_space_[level];
89 }
90
91 namespace {
92
StateValuesHashKey(Node ** nodes,size_t count)93 int StateValuesHashKey(Node** nodes, size_t count) {
94 size_t hash = count;
95 for (size_t i = 0; i < count; i++) {
96 hash = hash * 23 + nodes[i]->id();
97 }
98 return static_cast<int>(hash & 0x7fffffff);
99 }
100
101 } // namespace
102
103
GetValuesNodeFromCache(Node ** nodes,size_t count)104 Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
105 StateValuesKey key(count, nodes);
106 int hash = StateValuesHashKey(nodes, count);
107 ZoneHashMap::Entry* lookup =
108 hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
109 DCHECK_NOT_NULL(lookup);
110 Node* node;
111 if (lookup->value == nullptr) {
112 int input_count = static_cast<int>(count);
113 node = graph()->NewNode(common()->StateValues(input_count), input_count,
114 nodes);
115 NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
116 lookup->key = new_key;
117 lookup->value = node;
118 } else {
119 node = reinterpret_cast<Node*>(lookup->value);
120 }
121 return node;
122 }
123
124
125 class StateValuesCache::ValueArrayIterator {
126 public:
ValueArrayIterator(Node ** values,size_t count)127 ValueArrayIterator(Node** values, size_t count)
128 : values_(values), count_(count), current_(0) {}
129
Advance()130 void Advance() {
131 if (!done()) {
132 current_++;
133 }
134 }
135
done()136 bool done() { return current_ >= count_; }
137
node()138 Node* node() {
139 DCHECK(!done());
140 return values_[current_];
141 }
142
143 private:
144 Node** values_;
145 size_t count_;
146 size_t current_;
147 };
148
149
BuildTree(ValueArrayIterator * it,size_t max_height)150 Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
151 if (max_height == 0) {
152 Node* node = it->node();
153 it->Advance();
154 return node;
155 }
156 DCHECK(!it->done());
157
158 NodeVector* buffer = GetWorkingSpace(max_height);
159 size_t count = 0;
160 for (; count < kMaxInputCount; count++) {
161 if (it->done()) break;
162 (*buffer)[count] = BuildTree(it, max_height - 1);
163 }
164 if (count == 1) {
165 return (*buffer)[0];
166 } else {
167 return GetValuesNodeFromCache(&(buffer->front()), count);
168 }
169 }
170
171
GetNodeForValues(Node ** values,size_t count)172 Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
173 #if DEBUG
174 for (size_t i = 0; i < count; i++) {
175 DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
176 DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
177 }
178 #endif
179 if (count == 0) {
180 return GetEmptyStateValues();
181 }
182 size_t height = 0;
183 size_t max_nodes = 1;
184 while (count > max_nodes) {
185 height++;
186 max_nodes *= kMaxInputCount;
187 }
188
189 ValueArrayIterator it(values, count);
190
191 Node* tree = BuildTree(&it, height);
192
193 // If the 'tree' is a single node, equip it with a StateValues wrapper.
194 if (tree->opcode() != IrOpcode::kStateValues &&
195 tree->opcode() != IrOpcode::kTypedStateValues) {
196 tree = GetValuesNodeFromCache(&tree, 1);
197 }
198
199 return tree;
200 }
201
202
iterator(Node * node)203 StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
204 // A hacky way initialize - just set the index before the node we want
205 // to process and then advance to it.
206 stack_[current_depth_].node = node;
207 stack_[current_depth_].index = -1;
208 Advance();
209 }
210
211
Top()212 StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
213 DCHECK(current_depth_ >= 0);
214 DCHECK(current_depth_ < kMaxInlineDepth);
215 return &(stack_[current_depth_]);
216 }
217
218
Push(Node * node)219 void StateValuesAccess::iterator::Push(Node* node) {
220 current_depth_++;
221 CHECK(current_depth_ < kMaxInlineDepth);
222 stack_[current_depth_].node = node;
223 stack_[current_depth_].index = 0;
224 }
225
226
Pop()227 void StateValuesAccess::iterator::Pop() {
228 DCHECK(current_depth_ >= 0);
229 current_depth_--;
230 }
231
232
done()233 bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
234
235
Advance()236 void StateValuesAccess::iterator::Advance() {
237 // Advance the current index.
238 Top()->index++;
239
240 // Fix up the position to point to a valid node.
241 while (true) {
242 // TODO(jarin): Factor to a separate method.
243 Node* node = Top()->node;
244 int index = Top()->index;
245
246 if (index >= node->InputCount()) {
247 // Pop stack and move to the next sibling.
248 Pop();
249 if (done()) {
250 // Stack is exhausted, we have reached the end.
251 return;
252 }
253 Top()->index++;
254 } else if (node->InputAt(index)->opcode() == IrOpcode::kStateValues ||
255 node->InputAt(index)->opcode() == IrOpcode::kTypedStateValues) {
256 // Nested state, we need to push to the stack.
257 Push(node->InputAt(index));
258 } else {
259 // We are on a valid node, we can stop the iteration.
260 return;
261 }
262 }
263 }
264
265
node()266 Node* StateValuesAccess::iterator::node() {
267 return Top()->node->InputAt(Top()->index);
268 }
269
270
type()271 MachineType StateValuesAccess::iterator::type() {
272 Node* state = Top()->node;
273 if (state->opcode() == IrOpcode::kStateValues) {
274 return MachineType::AnyTagged();
275 } else {
276 DCHECK_EQ(IrOpcode::kTypedStateValues, state->opcode());
277 const ZoneVector<MachineType>* types =
278 OpParameter<const ZoneVector<MachineType>*>(state);
279 return (*types)[Top()->index];
280 }
281 }
282
283
operator !=(iterator & other)284 bool StateValuesAccess::iterator::operator!=(iterator& other) {
285 // We only allow comparison with end().
286 CHECK(other.done());
287 return !done();
288 }
289
290
operator ++()291 StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
292 Advance();
293 return *this;
294 }
295
296
operator *()297 StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
298 return TypedNode(node(), type());
299 }
300
301
size()302 size_t StateValuesAccess::size() {
303 size_t count = 0;
304 for (int i = 0; i < node_->InputCount(); i++) {
305 if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
306 node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
307 count += StateValuesAccess(node_->InputAt(i)).size();
308 } else {
309 count++;
310 }
311 }
312 return count;
313 }
314
315 } // namespace compiler
316 } // namespace internal
317 } // namespace v8
318