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
7namespace v8 {
8namespace internal {
9namespace compiler {
10
11StateValuesCache::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
20bool 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
46bool 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
60bool 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
74Node* 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
82NodeVector* 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
91namespace {
92
93int 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
104Node* 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
125class StateValuesCache::ValueArrayIterator {
126 public:
127  ValueArrayIterator(Node** values, size_t count)
128      : values_(values), count_(count), current_(0) {}
129
130  void Advance() {
131    if (!done()) {
132      current_++;
133    }
134  }
135
136  bool done() { return current_ >= count_; }
137
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
150Node* 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
172Node* 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
203StateValuesAccess::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
212StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
213  DCHECK(current_depth_ >= 0);
214  DCHECK(current_depth_ < kMaxInlineDepth);
215  return &(stack_[current_depth_]);
216}
217
218
219void 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
227void StateValuesAccess::iterator::Pop() {
228  DCHECK(current_depth_ >= 0);
229  current_depth_--;
230}
231
232
233bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
234
235
236void 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
266Node* StateValuesAccess::iterator::node() {
267  return Top()->node->InputAt(Top()->index);
268}
269
270
271MachineType 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
284bool StateValuesAccess::iterator::operator!=(iterator& other) {
285  // We only allow comparison with end().
286  CHECK(other.done());
287  return !done();
288}
289
290
291StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
292  Advance();
293  return *this;
294}
295
296
297StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
298  return TypedNode(node(), type());
299}
300
301
302size_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