Line data Source code
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 : #include "src/bit-vector.h"
8 :
9 : namespace v8 {
10 : namespace internal {
11 : namespace compiler {
12 :
13 529007 : StateValuesCache::StateValuesCache(JSGraph* js_graph)
14 : : js_graph_(js_graph),
15 : hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
16 : ZoneAllocationPolicy(zone())),
17 : working_space_(zone()),
18 1058014 : empty_state_values_(nullptr) {}
19 :
20 :
21 : // static
22 6562768 : bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
23 : NodeKey* node_key1 = reinterpret_cast<NodeKey*>(key1);
24 : NodeKey* node_key2 = reinterpret_cast<NodeKey*>(key2);
25 :
26 6562768 : if (node_key1->node == nullptr) {
27 6537865 : if (node_key2->node == nullptr) {
28 : return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
29 138192 : reinterpret_cast<StateValuesKey*>(key2));
30 : } else {
31 : return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
32 6399673 : node_key2->node);
33 : }
34 : } else {
35 24903 : if (node_key2->node == nullptr) {
36 : // If the nodes are already processed, they must be the same.
37 : return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key2),
38 376 : node_key1->node);
39 : } else {
40 24527 : return node_key1->node == node_key2->node;
41 : }
42 : }
43 : UNREACHABLE();
44 : }
45 :
46 :
47 : // static
48 6400048 : bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
49 12800096 : if (key->count != static_cast<size_t>(node->InputCount())) {
50 : return false;
51 : }
52 :
53 : DCHECK_EQ(IrOpcode::kStateValues, node->opcode());
54 6399948 : SparseInputMask node_mask = SparseInputMaskOf(node->op());
55 :
56 6399941 : if (node_mask != key->mask) {
57 : return false;
58 : }
59 :
60 : // Comparing real inputs rather than sparse inputs, since we already know the
61 : // sparse input masks are the same.
62 24746163 : for (size_t i = 0; i < key->count; i++) {
63 18648762 : if (key->values[i] != node->InputAt(static_cast<int>(i))) {
64 : return false;
65 : }
66 : }
67 : return true;
68 : }
69 :
70 :
71 : // static
72 138192 : bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
73 : StateValuesKey* key2) {
74 138192 : if (key1->count != key2->count) {
75 : return false;
76 : }
77 138192 : if (key1->mask != key2->mask) {
78 : return false;
79 : }
80 1023337 : for (size_t i = 0; i < key1->count; i++) {
81 442574 : if (key1->values[i] != key2->values[i]) {
82 : return false;
83 : }
84 : }
85 : return true;
86 : }
87 :
88 :
89 282168 : Node* StateValuesCache::GetEmptyStateValues() {
90 282168 : if (empty_state_values_ == nullptr) {
91 : empty_state_values_ =
92 180598 : graph()->NewNode(common()->StateValues(0, SparseInputMask::Dense()));
93 : }
94 282178 : return empty_state_values_;
95 : }
96 :
97 10520484 : StateValuesCache::WorkingBuffer* StateValuesCache::GetWorkingSpace(
98 : size_t level) {
99 10520484 : if (working_space_.size() <= level) {
100 436728 : working_space_.resize(level + 1);
101 : }
102 10520484 : return &working_space_[level];
103 : }
104 :
105 : namespace {
106 :
107 : int StateValuesHashKey(Node** nodes, size_t count) {
108 : size_t hash = count;
109 43402505 : for (size_t i = 0; i < count; i++) {
110 34239794 : hash = hash * 23 + (nodes[i] == nullptr ? 0 : nodes[i]->id());
111 : }
112 9162711 : return static_cast<int>(hash & 0x7FFFFFFF);
113 : }
114 :
115 : } // namespace
116 :
117 9162711 : Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count,
118 : SparseInputMask mask) {
119 : StateValuesKey key(count, mask, nodes);
120 : int hash = StateValuesHashKey(nodes, count);
121 : ZoneHashMap::Entry* lookup =
122 18325410 : hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
123 : DCHECK_NOT_NULL(lookup);
124 : Node* node;
125 9162699 : if (lookup->value == nullptr) {
126 3065279 : int node_count = static_cast<int>(count);
127 3065279 : node = graph()->NewNode(common()->StateValues(node_count, mask), node_count,
128 3065277 : nodes);
129 3065281 : NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
130 3065281 : lookup->key = new_key;
131 3065281 : lookup->value = node;
132 : } else {
133 : node = reinterpret_cast<Node*>(lookup->value);
134 : }
135 9162701 : return node;
136 : }
137 :
138 8809533 : SparseInputMask::BitMaskType StateValuesCache::FillBufferWithValues(
139 : WorkingBuffer* node_buffer, size_t* node_count, size_t* values_idx,
140 : Node** values, size_t count, const BitVector* liveness,
141 : int liveness_offset) {
142 : SparseInputMask::BitMaskType input_mask = 0;
143 :
144 : // Virtual nodes are the live nodes plus the implicit optimized out nodes,
145 : // which are implied by the liveness mask.
146 8809533 : size_t virtual_node_count = *node_count;
147 :
148 155033653 : while (*values_idx < count && *node_count < kMaxInputCount &&
149 : virtual_node_count < SparseInputMask::kMaxSparseInputs) {
150 : DCHECK_LE(*values_idx, static_cast<size_t>(INT_MAX));
151 :
152 144209174 : if (liveness == nullptr ||
153 71097114 : liveness->Contains(liveness_offset + static_cast<int>(*values_idx))) {
154 15692281 : input_mask |= 1 << (virtual_node_count);
155 15692281 : (*node_buffer)[(*node_count)++] = values[*values_idx];
156 : }
157 73112060 : virtual_node_count++;
158 :
159 73112060 : (*values_idx)++;
160 : }
161 :
162 : DCHECK_GE(StateValuesCache::kMaxInputCount, *node_count);
163 : DCHECK_GE(SparseInputMask::kMaxSparseInputs, virtual_node_count);
164 :
165 : // Add the end marker at the end of the mask.
166 8809533 : input_mask |= SparseInputMask::kEndMarker << virtual_node_count;
167 :
168 8809533 : return input_mask;
169 : }
170 :
171 10520484 : Node* StateValuesCache::BuildTree(size_t* values_idx, Node** values,
172 : size_t count, const BitVector* liveness,
173 : int liveness_offset, size_t level) {
174 10520484 : WorkingBuffer* node_buffer = GetWorkingSpace(level);
175 10520506 : size_t node_count = 0;
176 : SparseInputMask::BitMaskType input_mask = SparseInputMask::kDenseBitMask;
177 :
178 10520506 : if (level == 0) {
179 : input_mask = FillBufferWithValues(node_buffer, &node_count, values_idx,
180 8631330 : values, count, liveness, liveness_offset);
181 : // Make sure we returned a sparse input mask.
182 : DCHECK_NE(input_mask, SparseInputMask::kDenseBitMask);
183 : } else {
184 7459632 : while (*values_idx < count && node_count < kMaxInputCount) {
185 2963436 : if (count - *values_idx < kMaxInputCount - node_count) {
186 : // If we have fewer values remaining than inputs remaining, dump the
187 : // remaining values into this node.
188 : // TODO(leszeks): We could optimise this further by only counting
189 : // remaining live nodes.
190 :
191 : size_t previous_input_count = node_count;
192 : input_mask =
193 : FillBufferWithValues(node_buffer, &node_count, values_idx, values,
194 178205 : count, liveness, liveness_offset);
195 : // Make sure we have exhausted our values.
196 : DCHECK_EQ(*values_idx, count);
197 : // Make sure we returned a sparse input mask.
198 : DCHECK_NE(input_mask, SparseInputMask::kDenseBitMask);
199 :
200 : // Make sure we haven't touched inputs below previous_input_count in the
201 : // mask.
202 : DCHECK_EQ(input_mask & ((1 << previous_input_count) - 1), 0u);
203 : // Mark all previous inputs as live.
204 178204 : input_mask |= ((1 << previous_input_count) - 1);
205 :
206 178204 : break;
207 :
208 : } else {
209 : // Otherwise, add the values to a subtree and add that as an input.
210 2785231 : Node* subtree = BuildTree(values_idx, values, count, liveness,
211 2785231 : liveness_offset, level - 1);
212 2785228 : (*node_buffer)[node_count++] = subtree;
213 : // Don't touch the bitmask, so that it stays dense.
214 : }
215 : }
216 : }
217 :
218 10520519 : if (node_count == 1 && input_mask == SparseInputMask::kDenseBitMask) {
219 : // Elide the StateValue node if there is only one, dense input. This will
220 : // only happen if we built a single subtree (as nodes with values are always
221 : // sparse), and so we can replace ourselves with it.
222 : DCHECK_EQ((*node_buffer)[0]->opcode(), IrOpcode::kStateValues);
223 1357804 : return (*node_buffer)[0];
224 : } else {
225 9162699 : return GetValuesNodeFromCache(node_buffer->data(), node_count,
226 9162715 : SparseInputMask(input_mask));
227 : }
228 : }
229 :
230 : #if DEBUG
231 : namespace {
232 :
233 : void CheckTreeContainsValues(Node* tree, Node** values, size_t count,
234 : const BitVector* liveness, int liveness_offset) {
235 : DCHECK_EQ(count, StateValuesAccess(tree).size());
236 :
237 : int i;
238 : auto access = StateValuesAccess(tree);
239 : auto it = access.begin();
240 : auto itend = access.end();
241 : for (i = 0; it != itend; ++it, ++i) {
242 : if (liveness == nullptr || liveness->Contains(liveness_offset + i)) {
243 : DCHECK_EQ((*it).node, values[i]);
244 : } else {
245 : DCHECK_NULL((*it).node);
246 : }
247 : }
248 : DCHECK_EQ(static_cast<size_t>(i), count);
249 : }
250 :
251 : } // namespace
252 : #endif
253 :
254 8017437 : Node* StateValuesCache::GetNodeForValues(Node** values, size_t count,
255 : const BitVector* liveness,
256 : int liveness_offset) {
257 : #if DEBUG
258 : // Check that the values represent actual values, and not a tree of values.
259 : for (size_t i = 0; i < count; i++) {
260 : if (values[i] != nullptr) {
261 : DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
262 : DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
263 : }
264 : }
265 : if (liveness != nullptr) {
266 : DCHECK_LE(liveness_offset + count, static_cast<size_t>(liveness->length()));
267 :
268 : for (size_t i = 0; i < count; i++) {
269 : if (liveness->Contains(liveness_offset + static_cast<int>(i))) {
270 : DCHECK_NOT_NULL(values[i]);
271 : }
272 : }
273 : }
274 : #endif
275 :
276 8017437 : if (count == 0) {
277 282168 : return GetEmptyStateValues();
278 : }
279 :
280 : // This is a worst-case tree height estimate, assuming that all values are
281 : // live. We could get a better estimate by counting zeroes in the liveness
282 : // vector, but there's no point -- any excess height in the tree will be
283 : // collapsed by the single-input elision at the end of BuildTree.
284 : size_t height = 0;
285 : size_t max_inputs = kMaxInputCount;
286 11351869 : while (count > max_inputs) {
287 1808300 : height++;
288 1808300 : max_inputs *= kMaxInputCount;
289 : }
290 :
291 7735269 : size_t values_idx = 0;
292 : Node* tree =
293 7735269 : BuildTree(&values_idx, values, count, liveness, liveness_offset, height);
294 : // The values should be exhausted by the end of BuildTree.
295 : DCHECK_EQ(values_idx, count);
296 :
297 : // The 'tree' must be rooted with a state value node.
298 : DCHECK_EQ(tree->opcode(), IrOpcode::kStateValues);
299 :
300 : #if DEBUG
301 : CheckTreeContainsValues(tree, values, count, liveness, liveness_offset);
302 : #endif
303 :
304 7735276 : return tree;
305 : }
306 :
307 11868774 : StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
308 : stack_[current_depth_] =
309 11868774 : SparseInputMaskOf(node->op()).IterateOverInputs(node);
310 11868812 : EnsureValid();
311 11868747 : }
312 :
313 0 : SparseInputMask::InputIterator* StateValuesAccess::iterator::Top() {
314 : DCHECK_LE(0, current_depth_);
315 : DCHECK_GT(kMaxInlineDepth, current_depth_);
316 206323947 : return &(stack_[current_depth_]);
317 : }
318 :
319 553876 : void StateValuesAccess::iterator::Push(Node* node) {
320 553876 : current_depth_++;
321 553876 : CHECK_GT(kMaxInlineDepth, current_depth_);
322 : stack_[current_depth_] =
323 553876 : SparseInputMaskOf(node->op()).IterateOverInputs(node);
324 553878 : }
325 :
326 :
327 0 : void StateValuesAccess::iterator::Pop() {
328 : DCHECK_LE(0, current_depth_);
329 12422640 : current_depth_--;
330 0 : }
331 :
332 :
333 112298770 : bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
334 :
335 :
336 0 : void StateValuesAccess::iterator::Advance() {
337 44288375 : Top()->Advance();
338 44287969 : EnsureValid();
339 0 : }
340 :
341 56155680 : void StateValuesAccess::iterator::EnsureValid() {
342 : while (true) {
343 : SparseInputMask::InputIterator* top = Top();
344 :
345 57263014 : if (top->IsEmpty()) {
346 : // We are on a valid (albeit optimized out) node.
347 : return;
348 : }
349 :
350 28675636 : if (top->IsEnd()) {
351 : // We have hit the end of this iterator. Pop the stack and move to the
352 : // next sibling iterator.
353 : Pop();
354 12422640 : if (done()) {
355 : // Stack is exhausted, we have reached the end.
356 : return;
357 : }
358 553878 : Top()->Advance();
359 553878 : continue;
360 : }
361 :
362 : // At this point the value is known to be live and within our input nodes.
363 16253497 : Node* value_node = top->GetReal();
364 :
365 16253404 : if (value_node->opcode() == IrOpcode::kStateValues ||
366 : value_node->opcode() == IrOpcode::kTypedStateValues) {
367 : // Nested state, we need to push to the stack.
368 553876 : Push(value_node);
369 553878 : continue;
370 : }
371 :
372 : // We are on a valid node, we can stop the iteration.
373 : return;
374 : }
375 : }
376 :
377 88568436 : Node* StateValuesAccess::iterator::node() { return Top()->Get(nullptr); }
378 :
379 44285029 : MachineType StateValuesAccess::iterator::type() {
380 : Node* parent = Top()->parent();
381 44285029 : if (parent->opcode() == IrOpcode::kStateValues) {
382 : return MachineType::AnyTagged();
383 : } else {
384 : DCHECK_EQ(IrOpcode::kTypedStateValues, parent->opcode());
385 :
386 44214124 : if (Top()->IsEmpty()) {
387 : return MachineType::None();
388 : } else {
389 15648673 : ZoneVector<MachineType> const* types = MachineTypesOf(parent->op());
390 31297282 : return (*types)[Top()->real_index()];
391 : }
392 : }
393 : }
394 :
395 :
396 56149385 : bool StateValuesAccess::iterator::operator!=(iterator& other) {
397 : // We only allow comparison with end().
398 56149385 : CHECK(other.done());
399 56149385 : return !done();
400 : }
401 :
402 :
403 44288375 : StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
404 : Advance();
405 44287033 : return *this;
406 : }
407 :
408 :
409 44285038 : StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
410 44285038 : return TypedNode(node(), type());
411 : }
412 :
413 :
414 12414637 : size_t StateValuesAccess::size() {
415 : size_t count = 0;
416 12414637 : SparseInputMask mask = SparseInputMaskOf(node_->op());
417 :
418 12414665 : SparseInputMask::InputIterator iterator = mask.IterateOverInputs(node_);
419 :
420 101937886 : for (; !iterator.IsEnd(); iterator.Advance()) {
421 44761864 : if (iterator.IsEmpty()) {
422 28565634 : count++;
423 : } else {
424 16196230 : Node* value = iterator.GetReal();
425 16196288 : if (value->opcode() == IrOpcode::kStateValues ||
426 : value->opcode() == IrOpcode::kTypedStateValues) {
427 547185 : count += StateValuesAccess(value).size();
428 : } else {
429 15649103 : count++;
430 : }
431 : }
432 : }
433 :
434 12414653 : return count;
435 : }
436 :
437 : } // namespace compiler
438 : } // namespace internal
439 120216 : } // namespace v8
|
