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 530234 : StateValuesCache::StateValuesCache(JSGraph* js_graph)
14 : : js_graph_(js_graph),
15 : hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
16 : ZoneAllocationPolicy(zone())),
17 : working_space_(zone()),
18 1060469 : empty_state_values_(nullptr) {}
19 :
20 :
21 : // static
22 5997745 : 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 5997745 : if (node_key1->node == nullptr) {
27 5972234 : if (node_key2->node == nullptr) {
28 : return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
29 139423 : reinterpret_cast<StateValuesKey*>(key2));
30 : } else {
31 : return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
32 5832811 : node_key2->node);
33 : }
34 : } else {
35 25511 : 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 379 : node_key1->node);
39 : } else {
40 25132 : return node_key1->node == node_key2->node;
41 : }
42 : }
43 : UNREACHABLE();
44 : }
45 :
46 :
47 : // static
48 5833188 : bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
49 11666376 : if (key->count != static_cast<size_t>(node->InputCount())) {
50 : return false;
51 : }
52 :
53 : DCHECK_EQ(IrOpcode::kStateValues, node->opcode());
54 5833143 : SparseInputMask node_mask = SparseInputMaskOf(node->op());
55 :
56 5833142 : 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 22995245 : for (size_t i = 0; i < key->count; i++) {
63 17466930 : if (key->values[i] != node->InputAt(static_cast<int>(i))) {
64 : return false;
65 : }
66 : }
67 : return true;
68 : }
69 :
70 :
71 : // static
72 139423 : bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
73 : StateValuesKey* key2) {
74 139423 : if (key1->count != key2->count) {
75 : return false;
76 : }
77 139423 : if (key1->mask != key2->mask) {
78 : return false;
79 : }
80 1030653 : for (size_t i = 0; i < key1->count; i++) {
81 445615 : if (key1->values[i] != key2->values[i]) {
82 : return false;
83 : }
84 : }
85 : return true;
86 : }
87 :
88 :
89 281083 : Node* StateValuesCache::GetEmptyStateValues() {
90 281083 : if (empty_state_values_ == nullptr) {
91 : empty_state_values_ =
92 179684 : graph()->NewNode(common()->StateValues(0, SparseInputMask::Dense()));
93 : }
94 281085 : return empty_state_values_;
95 : }
96 :
97 9906633 : StateValuesCache::WorkingBuffer* StateValuesCache::GetWorkingSpace(
98 : size_t level) {
99 9906633 : if (working_space_.size() <= level) {
100 438410 : working_space_.resize(level + 1);
101 : }
102 9906634 : return &working_space_[level];
103 : }
104 :
105 : namespace {
106 :
107 : int StateValuesHashKey(Node** nodes, size_t count) {
108 : size_t hash = count;
109 41198089 : for (size_t i = 0; i < count; i++) {
110 32629130 : hash = hash * 23 + (nodes[i] == nullptr ? 0 : nodes[i]->id());
111 : }
112 8568959 : return static_cast<int>(hash & 0x7FFFFFFF);
113 : }
114 :
115 : } // namespace
116 :
117 8568959 : 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 17137892 : hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
123 : DCHECK_NOT_NULL(lookup);
124 : Node* node;
125 8568933 : if (lookup->value == nullptr) {
126 3040612 : int node_count = static_cast<int>(count);
127 3040612 : node = graph()->NewNode(common()->StateValues(node_count, mask), node_count,
128 3040604 : nodes);
129 3040607 : NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
130 3040607 : lookup->key = new_key;
131 3040607 : lookup->value = node;
132 : } else {
133 : node = reinterpret_cast<Node*>(lookup->value);
134 : }
135 8568928 : return node;
136 : }
137 :
138 8213188 : 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 8213188 : size_t virtual_node_count = *node_count;
147 :
148 150946838 : 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 140718038 : if (liveness == nullptr ||
153 69351213 : liveness->Contains(liveness_offset + static_cast<int>(*values_idx))) {
154 14923366 : input_mask |= 1 << (virtual_node_count);
155 14923366 : (*node_buffer)[(*node_count)++] = values[*values_idx];
156 : }
157 71366825 : virtual_node_count++;
158 :
159 71366825 : (*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 8213188 : input_mask |= SparseInputMask::kEndMarker << virtual_node_count;
167 :
168 8213188 : return input_mask;
169 : }
170 :
171 9906629 : Node* StateValuesCache::BuildTree(size_t* values_idx, Node** values,
172 : size_t count, const BitVector* liveness,
173 : int liveness_offset, size_t level) {
174 9906629 : WorkingBuffer* node_buffer = GetWorkingSpace(level);
175 9906657 : size_t node_count = 0;
176 : SparseInputMask::BitMaskType input_mask = SparseInputMask::kDenseBitMask;
177 :
178 9906657 : if (level == 0) {
179 : input_mask = FillBufferWithValues(node_buffer, &node_count, values_idx,
180 8032883 : values, count, liveness, liveness_offset);
181 : // Make sure we returned a sparse input mask.
182 : DCHECK_NE(input_mask, SparseInputMask::kDenseBitMask);
183 : } else {
184 7331298 : while (*values_idx < count && node_count < kMaxInputCount) {
185 2909085 : 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 180315 : 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 180315 : input_mask |= ((1 << previous_input_count) - 1);
205 :
206 180315 : break;
207 :
208 : } else {
209 : // Otherwise, add the values to a subtree and add that as an input.
210 2728770 : Node* subtree = BuildTree(values_idx, values, count, liveness,
211 2728770 : liveness_offset, level - 1);
212 2728762 : (*node_buffer)[node_count++] = subtree;
213 : // Don't touch the bitmask, so that it stays dense.
214 : }
215 : }
216 : }
217 :
218 9906677 : 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 1337719 : return (*node_buffer)[0];
224 : } else {
225 8568920 : return GetValuesNodeFromCache(node_buffer->data(), node_count,
226 8568958 : 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 7458961 : 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 7458961 : if (count == 0) {
277 281083 : 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 10778188 : while (count > max_inputs) {
287 1800155 : height++;
288 1800155 : max_inputs *= kMaxInputCount;
289 : }
290 :
291 7177878 : size_t values_idx = 0;
292 : Node* tree =
293 7177878 : 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 7177878 : return tree;
305 : }
306 :
307 11071102 : StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
308 : stack_[current_depth_] =
309 11071102 : SparseInputMaskOf(node->op()).IterateOverInputs(node);
310 11071126 : EnsureValid();
311 11071115 : }
312 :
313 0 : SparseInputMask::InputIterator* StateValuesAccess::iterator::Top() {
314 : DCHECK_LE(0, current_depth_);
315 : DCHECK_GT(kMaxInlineDepth, current_depth_);
316 198411356 : return &(stack_[current_depth_]);
317 : }
318 :
319 539205 : void StateValuesAccess::iterator::Push(Node* node) {
320 539205 : current_depth_++;
321 539205 : CHECK_GT(kMaxInlineDepth, current_depth_);
322 : stack_[current_depth_] =
323 539205 : SparseInputMaskOf(node->op()).IterateOverInputs(node);
324 539205 : }
325 :
326 :
327 0 : void StateValuesAccess::iterator::Pop() {
328 : DCHECK_LE(0, current_depth_);
329 11610332 : current_depth_--;
330 0 : }
331 :
332 :
333 107556838 : bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
334 :
335 :
336 0 : void StateValuesAccess::iterator::Advance() {
337 42713492 : Top()->Advance();
338 42713382 : EnsureValid();
339 0 : }
340 :
341 53784224 : void StateValuesAccess::iterator::EnsureValid() {
342 : while (true) {
343 : SparseInputMask::InputIterator* top = Top();
344 :
345 54862588 : if (top->IsEmpty()) {
346 : // We are on a valid (albeit optimized out) node.
347 : return;
348 : }
349 :
350 27074115 : 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 11610332 : if (done()) {
355 : // Stack is exhausted, we have reached the end.
356 : return;
357 : }
358 539207 : Top()->Advance();
359 539206 : continue;
360 : }
361 :
362 : // At this point the value is known to be live and within our input nodes.
363 15463936 : Node* value_node = top->GetReal();
364 :
365 15463931 : if (value_node->opcode() == IrOpcode::kStateValues ||
366 : value_node->opcode() == IrOpcode::kTypedStateValues) {
367 : // Nested state, we need to push to the stack.
368 539205 : Push(value_node);
369 539205 : continue;
370 : }
371 :
372 : // We are on a valid node, we can stop the iteration.
373 : return;
374 : }
375 : }
376 :
377 85422115 : Node* StateValuesAccess::iterator::node() { return Top()->Get(nullptr); }
378 :
379 42711248 : MachineType StateValuesAccess::iterator::type() {
380 : Node* parent = Top()->parent();
381 42711248 : if (parent->opcode() == IrOpcode::kStateValues) {
382 : return MachineType::AnyTagged();
383 : } else {
384 : DCHECK_EQ(IrOpcode::kTypedStateValues, parent->opcode());
385 :
386 42639083 : if (Top()->IsEmpty()) {
387 : return MachineType::None();
388 : } else {
389 14873619 : ZoneVector<MachineType> const* types = MachineTypesOf(parent->op());
390 29747238 : return (*types)[Top()->real_index()];
391 : }
392 : }
393 : }
394 :
395 :
396 53778419 : bool StateValuesAccess::iterator::operator!=(iterator& other) {
397 : // We only allow comparison with end().
398 53778419 : CHECK(other.done());
399 53778419 : return !done();
400 : }
401 :
402 :
403 42713492 : StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
404 : Advance();
405 42713217 : return *this;
406 : }
407 :
408 :
409 42711247 : StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
410 42711247 : return TypedNode(node(), type());
411 : }
412 :
413 :
414 11602251 : size_t StateValuesAccess::size() {
415 : size_t count = 0;
416 11602251 : SparseInputMask mask = SparseInputMaskOf(node_->op());
417 :
418 11602255 : SparseInputMask::InputIterator iterator = mask.IterateOverInputs(node_);
419 :
420 97945764 : for (; !iterator.IsEnd(); iterator.Advance()) {
421 43171805 : if (iterator.IsEmpty()) {
422 27765596 : count++;
423 : } else {
424 15406209 : Node* value = iterator.GetReal();
425 15406222 : if (value->opcode() == IrOpcode::kStateValues ||
426 : value->opcode() == IrOpcode::kTypedStateValues) {
427 532514 : count += StateValuesAccess(value).size();
428 : } else {
429 14873708 : count++;
430 : }
431 : }
432 : }
433 :
434 11602262 : return count;
435 : }
436 :
437 : } // namespace compiler
438 : } // namespace internal
439 122004 : } // namespace v8
|
