Line data Source code
1 : // Copyright 2017 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/builtins/builtins-collections-gen.h"
6 :
7 : #include "src/builtins/builtins-constructor-gen.h"
8 : #include "src/builtins/builtins-iterator-gen.h"
9 : #include "src/builtins/builtins-utils-gen.h"
10 : #include "src/code-stub-assembler.h"
11 : #include "src/heap/factory-inl.h"
12 : #include "src/heap/heap-inl.h"
13 : #include "src/objects/hash-table-inl.h"
14 : #include "src/objects/js-collection.h"
15 : #include "src/objects/ordered-hash-table.h"
16 : #include "torque-generated/builtins-base-from-dsl-gen.h"
17 : #include "torque-generated/builtins-collections-from-dsl-gen.h"
18 :
19 : namespace v8 {
20 : namespace internal {
21 :
22 : using compiler::Node;
23 : template <class T>
24 : using TNode = compiler::TNode<T>;
25 : template <class T>
26 : using TVariable = compiler::TypedCodeAssemblerVariable<T>;
27 :
28 : class BaseCollectionsAssembler : public CodeStubAssembler,
29 : public CollectionsBuiltinsFromDSLAssembler {
30 : public:
31 : explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state)
32 4256 : : CodeStubAssembler(state), CollectionsBuiltinsFromDSLAssembler(state) {}
33 :
34 4256 : virtual ~BaseCollectionsAssembler() = default;
35 :
36 : protected:
37 : enum Variant { kMap, kSet, kWeakMap, kWeakSet };
38 :
39 : // Adds an entry to a collection. For Maps, properly handles extracting the
40 : // key and value from the entry (see LoadKeyValue()).
41 : void AddConstructorEntry(Variant variant, TNode<Context> context,
42 : TNode<Object> collection, TNode<Object> add_function,
43 : TNode<Object> key_value,
44 : Label* if_may_have_side_effects = nullptr,
45 : Label* if_exception = nullptr,
46 : TVariable<Object>* var_exception = nullptr);
47 :
48 : // Adds constructor entries to a collection. Choosing a fast path when
49 : // possible.
50 : void AddConstructorEntries(Variant variant, TNode<Context> context,
51 : TNode<Context> native_context,
52 : TNode<Object> collection,
53 : TNode<Object> initial_entries);
54 :
55 : // Fast path for adding constructor entries. Assumes the entries are a fast
56 : // JS array (see CodeStubAssembler::BranchIfFastJSArray()).
57 : void AddConstructorEntriesFromFastJSArray(Variant variant,
58 : TNode<Context> context,
59 : TNode<Context> native_context,
60 : TNode<Object> collection,
61 : TNode<JSArray> fast_jsarray,
62 : Label* if_may_have_side_effects);
63 :
64 : // Adds constructor entries to a collection using the iterator protocol.
65 : void AddConstructorEntriesFromIterable(Variant variant,
66 : TNode<Context> context,
67 : TNode<Context> native_context,
68 : TNode<Object> collection,
69 : TNode<Object> iterable);
70 :
71 : // Constructs a collection instance. Choosing a fast path when possible.
72 : TNode<Object> AllocateJSCollection(TNode<Context> context,
73 : TNode<JSFunction> constructor,
74 : TNode<Object> new_target);
75 :
76 : // Fast path for constructing a collection instance if the constructor
77 : // function has not been modified.
78 : TNode<Object> AllocateJSCollectionFast(TNode<HeapObject> constructor);
79 :
80 : // Fallback for constructing a collection instance if the constructor function
81 : // has been modified.
82 : TNode<Object> AllocateJSCollectionSlow(TNode<Context> context,
83 : TNode<JSFunction> constructor,
84 : TNode<Object> new_target);
85 :
86 : // Allocates the backing store for a collection.
87 : virtual TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
88 : TNode<IntPtrT> at_least_space_for) = 0;
89 :
90 : // Main entry point for a collection constructor builtin.
91 : void GenerateConstructor(Variant variant,
92 : Handle<String> constructor_function_name,
93 : TNode<Object> new_target, TNode<IntPtrT> argc,
94 : TNode<Context> context);
95 :
96 : // Retrieves the collection function that adds an entry. `set` for Maps and
97 : // `add` for Sets.
98 : TNode<Object> GetAddFunction(Variant variant, TNode<Context> context,
99 : TNode<Object> collection);
100 :
101 : // Retrieves the collection constructor function.
102 : TNode<JSFunction> GetConstructor(Variant variant,
103 : TNode<Context> native_context);
104 :
105 : // Retrieves the initial collection function that adds an entry. Should only
106 : // be called when it is certain that a collection prototype's map hasn't been
107 : // changed.
108 : TNode<JSFunction> GetInitialAddFunction(Variant variant,
109 : TNode<Context> native_context);
110 :
111 : // Checks whether {collection}'s initial add/set function has been modified
112 : // (depending on {variant}, loaded from {native_context}).
113 : void GotoIfInitialAddFunctionModified(Variant variant,
114 : TNode<Context> native_context,
115 : TNode<Object> collection,
116 : Label* if_modified);
117 :
118 : // Gets root index for the name of the add/set function.
119 : RootIndex GetAddFunctionNameIndex(Variant variant);
120 :
121 : // Retrieves the offset to access the backing table from the collection.
122 : int GetTableOffset(Variant variant);
123 :
124 : // Estimates the number of entries the collection will have after adding the
125 : // entries passed in the constructor. AllocateTable() can use this to avoid
126 : // the time of growing/rehashing when adding the constructor entries.
127 : TNode<IntPtrT> EstimatedInitialSize(TNode<Object> initial_entries,
128 : TNode<BoolT> is_fast_jsarray);
129 :
130 : void GotoIfNotJSReceiver(Node* const obj, Label* if_not_receiver);
131 :
132 : // Determines whether the collection's prototype has been modified.
133 : TNode<BoolT> HasInitialCollectionPrototype(Variant variant,
134 : TNode<Context> native_context,
135 : TNode<Object> collection);
136 :
137 : // Gets the initial prototype map for given collection {variant}.
138 : TNode<Map> GetInitialCollectionPrototype(Variant variant,
139 : TNode<Context> native_context);
140 :
141 : // Loads an element from a fixed array. If the element is the hole, returns
142 : // `undefined`.
143 : TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<FixedArray> elements,
144 : TNode<IntPtrT> index);
145 :
146 : // Loads an element from a fixed double array. If the element is the hole,
147 : // returns `undefined`.
148 : TNode<Object> LoadAndNormalizeFixedDoubleArrayElement(
149 : TNode<HeapObject> elements, TNode<IntPtrT> index);
150 : };
151 :
152 560 : void BaseCollectionsAssembler::AddConstructorEntry(
153 : Variant variant, TNode<Context> context, TNode<Object> collection,
154 : TNode<Object> add_function, TNode<Object> key_value,
155 : Label* if_may_have_side_effects, Label* if_exception,
156 : TVariable<Object>* var_exception) {
157 : compiler::CodeAssemblerScopedExceptionHandler handler(this, if_exception,
158 1120 : var_exception);
159 : CSA_ASSERT(this, Word32BinaryNot(IsTheHole(key_value)));
160 560 : if (variant == kMap || variant == kWeakMap) {
161 : BaseBuiltinsFromDSLAssembler::KeyValuePair pair =
162 : if_may_have_side_effects != nullptr
163 : ? LoadKeyValuePairNoSideEffects(context, key_value,
164 112 : if_may_have_side_effects)
165 336 : : LoadKeyValuePair(context, key_value);
166 : Node* key_n = pair.key;
167 : Node* value_n = pair.value;
168 448 : CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
169 224 : key_n, value_n);
170 : } else {
171 : DCHECK(variant == kSet || variant == kWeakSet);
172 672 : CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
173 336 : key_value);
174 : }
175 560 : }
176 :
177 224 : void BaseCollectionsAssembler::AddConstructorEntries(
178 : Variant variant, TNode<Context> context, TNode<Context> native_context,
179 : TNode<Object> collection, TNode<Object> initial_entries) {
180 224 : TVARIABLE(BoolT, use_fast_loop,
181 : IsFastJSArrayWithNoCustomIteration(context, initial_entries));
182 : TNode<IntPtrT> at_least_space_for =
183 224 : EstimatedInitialSize(initial_entries, use_fast_loop.value());
184 224 : Label allocate_table(this, &use_fast_loop), exit(this), fast_loop(this),
185 224 : slow_loop(this, Label::kDeferred);
186 224 : Goto(&allocate_table);
187 224 : BIND(&allocate_table);
188 : {
189 224 : TNode<Object> table = AllocateTable(variant, context, at_least_space_for);
190 224 : StoreObjectField(collection, GetTableOffset(variant), table);
191 448 : GotoIf(IsNullOrUndefined(initial_entries), &exit);
192 : GotoIfInitialAddFunctionModified(variant, native_context, collection,
193 224 : &slow_loop);
194 224 : Branch(use_fast_loop.value(), &fast_loop, &slow_loop);
195 : }
196 224 : BIND(&fast_loop);
197 : {
198 : TNode<JSArray> initial_entries_jsarray =
199 224 : UncheckedCast<JSArray>(initial_entries);
200 : #if DEBUG
201 : CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(
202 : context, initial_entries_jsarray));
203 : TNode<Map> original_initial_entries_map = LoadMap(initial_entries_jsarray);
204 : #endif
205 :
206 224 : Label if_may_have_side_effects(this, Label::kDeferred);
207 : AddConstructorEntriesFromFastJSArray(variant, context, native_context,
208 : collection, initial_entries_jsarray,
209 224 : &if_may_have_side_effects);
210 224 : Goto(&exit);
211 :
212 224 : if (variant == kMap || variant == kWeakMap) {
213 112 : BIND(&if_may_have_side_effects);
214 : #if DEBUG
215 : {
216 : // Check that add/set function has not been modified.
217 : Label if_not_modified(this), if_modified(this);
218 : GotoIfInitialAddFunctionModified(variant, native_context, collection,
219 : &if_modified);
220 : Goto(&if_not_modified);
221 : BIND(&if_modified);
222 : Unreachable();
223 : BIND(&if_not_modified);
224 : }
225 : CSA_ASSERT(this, WordEqual(original_initial_entries_map,
226 : LoadMap(initial_entries_jsarray)));
227 : #endif
228 : use_fast_loop = Int32FalseConstant();
229 112 : Goto(&allocate_table);
230 : }
231 : }
232 224 : BIND(&slow_loop);
233 : {
234 : AddConstructorEntriesFromIterable(variant, context, native_context,
235 224 : collection, initial_entries);
236 224 : Goto(&exit);
237 : }
238 224 : BIND(&exit);
239 224 : }
240 :
241 224 : void BaseCollectionsAssembler::AddConstructorEntriesFromFastJSArray(
242 : Variant variant, TNode<Context> context, TNode<Context> native_context,
243 : TNode<Object> collection, TNode<JSArray> fast_jsarray,
244 : Label* if_may_have_side_effects) {
245 224 : TNode<FixedArrayBase> elements = LoadElements(fast_jsarray);
246 224 : TNode<Int32T> elements_kind = LoadElementsKind(fast_jsarray);
247 224 : TNode<JSFunction> add_func = GetInitialAddFunction(variant, native_context);
248 : CSA_ASSERT(
249 : this,
250 : WordEqual(GetAddFunction(variant, native_context, collection), add_func));
251 : CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(context, fast_jsarray));
252 448 : TNode<IntPtrT> length = SmiUntag(LoadFastJSArrayLength(fast_jsarray));
253 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(length, IntPtrConstant(0)));
254 : CSA_ASSERT(
255 : this, HasInitialCollectionPrototype(variant, native_context, collection));
256 :
257 : #if DEBUG
258 : TNode<Map> original_collection_map = LoadMap(CAST(collection));
259 : TNode<Map> original_fast_js_array_map = LoadMap(fast_jsarray);
260 : #endif
261 448 : Label exit(this), if_doubles(this), if_smiorobjects(this);
262 672 : GotoIf(IntPtrEqual(length, IntPtrConstant(0)), &exit);
263 448 : Branch(IsFastSmiOrTaggedElementsKind(elements_kind), &if_smiorobjects,
264 224 : &if_doubles);
265 224 : BIND(&if_smiorobjects);
266 : {
267 224 : auto set_entry = [&](Node* index) {
268 : TNode<Object> element = LoadAndNormalizeFixedArrayElement(
269 448 : CAST(elements), UncheckedCast<IntPtrT>(index));
270 672 : AddConstructorEntry(variant, context, collection, add_func, element,
271 448 : if_may_have_side_effects);
272 224 : };
273 :
274 : // Instead of using the slower iteration protocol to iterate over the
275 : // elements, a fast loop is used. This assumes that adding an element
276 : // to the collection does not call user code that could mutate the elements
277 : // or collection.
278 672 : BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
279 224 : ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
280 224 : Goto(&exit);
281 : }
282 224 : BIND(&if_doubles);
283 : {
284 : // A Map constructor requires entries to be arrays (ex. [key, value]),
285 : // so a FixedDoubleArray can never succeed.
286 224 : if (variant == kMap || variant == kWeakMap) {
287 : CSA_ASSERT(this, IntPtrGreaterThan(length, IntPtrConstant(0)));
288 : TNode<Object> element =
289 224 : LoadAndNormalizeFixedDoubleArrayElement(elements, IntPtrConstant(0));
290 : ThrowTypeError(context, MessageTemplate::kIteratorValueNotAnObject,
291 112 : element);
292 : } else {
293 : DCHECK(variant == kSet || variant == kWeakSet);
294 112 : auto set_entry = [&](Node* index) {
295 : TNode<Object> entry = LoadAndNormalizeFixedDoubleArrayElement(
296 336 : elements, UncheckedCast<IntPtrT>(index));
297 336 : AddConstructorEntry(variant, context, collection, add_func, entry);
298 112 : };
299 336 : BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
300 112 : ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
301 112 : Goto(&exit);
302 : }
303 : }
304 224 : BIND(&exit);
305 : #if DEBUG
306 : CSA_ASSERT(this,
307 : WordEqual(original_collection_map, LoadMap(CAST(collection))));
308 : CSA_ASSERT(this,
309 : WordEqual(original_fast_js_array_map, LoadMap(fast_jsarray)));
310 : #endif
311 224 : }
312 :
313 224 : void BaseCollectionsAssembler::AddConstructorEntriesFromIterable(
314 : Variant variant, TNode<Context> context, TNode<Context> native_context,
315 : TNode<Object> collection, TNode<Object> iterable) {
316 448 : Label exit(this), loop(this), if_exception(this, Label::kDeferred);
317 : CSA_ASSERT(this, Word32BinaryNot(IsNullOrUndefined(iterable)));
318 :
319 224 : TNode<Object> add_func = GetAddFunction(variant, context, collection);
320 224 : IteratorBuiltinsAssembler iterator_assembler(this->state());
321 : IteratorBuiltinsAssembler::IteratorRecord iterator =
322 224 : iterator_assembler.GetIterator(context, iterable);
323 :
324 : CSA_ASSERT(this, Word32BinaryNot(IsUndefined(iterator.object)));
325 :
326 : TNode<Object> fast_iterator_result_map =
327 224 : LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);
328 : TVARIABLE(Object, var_exception);
329 :
330 224 : Goto(&loop);
331 224 : BIND(&loop);
332 : {
333 : TNode<Object> next = iterator_assembler.IteratorStep(
334 224 : context, iterator, &exit, fast_iterator_result_map);
335 224 : TNode<Object> next_value = CAST(iterator_assembler.IteratorValue(
336 : context, next, fast_iterator_result_map));
337 : AddConstructorEntry(variant, context, collection, add_func, next_value,
338 224 : nullptr, &if_exception, &var_exception);
339 224 : Goto(&loop);
340 : }
341 224 : BIND(&if_exception);
342 : {
343 : iterator_assembler.IteratorCloseOnException(context, iterator,
344 224 : var_exception.value());
345 : }
346 224 : BIND(&exit);
347 224 : }
348 :
349 224 : RootIndex BaseCollectionsAssembler::GetAddFunctionNameIndex(Variant variant) {
350 224 : switch (variant) {
351 : case kMap:
352 : case kWeakMap:
353 : return RootIndex::kset_string;
354 : case kSet:
355 : case kWeakSet:
356 112 : return RootIndex::kadd_string;
357 : }
358 0 : UNREACHABLE();
359 : }
360 :
361 224 : void BaseCollectionsAssembler::GotoIfInitialAddFunctionModified(
362 : Variant variant, TNode<Context> native_context, TNode<Object> collection,
363 : Label* if_modified) {
364 : STATIC_ASSERT(JSCollection::kAddFunctionDescriptorIndex ==
365 : JSWeakCollection::kAddFunctionDescriptorIndex);
366 224 : GotoIfInitialPrototypePropertyModified(
367 : LoadMap(CAST(collection)),
368 : GetInitialCollectionPrototype(variant, native_context),
369 : JSCollection::kAddFunctionDescriptorIndex,
370 224 : GetAddFunctionNameIndex(variant), if_modified);
371 224 : }
372 :
373 224 : TNode<Object> BaseCollectionsAssembler::AllocateJSCollection(
374 : TNode<Context> context, TNode<JSFunction> constructor,
375 : TNode<Object> new_target) {
376 224 : TNode<BoolT> is_target_unmodified = WordEqual(constructor, new_target);
377 :
378 : return Select<Object>(is_target_unmodified,
379 224 : [=] { return AllocateJSCollectionFast(constructor); },
380 : [=] {
381 : return AllocateJSCollectionSlow(context, constructor,
382 224 : new_target);
383 672 : });
384 : }
385 :
386 224 : TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionFast(
387 : TNode<HeapObject> constructor) {
388 : CSA_ASSERT(this, IsConstructorMap(LoadMap(constructor)));
389 : TNode<Object> initial_map =
390 224 : LoadObjectField(constructor, JSFunction::kPrototypeOrInitialMapOffset);
391 224 : return CAST(AllocateJSObjectFromMap(initial_map));
392 : }
393 :
394 224 : TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionSlow(
395 : TNode<Context> context, TNode<JSFunction> constructor,
396 : TNode<Object> new_target) {
397 : ConstructorBuiltinsAssembler constructor_assembler(this->state());
398 448 : return CAST(constructor_assembler.EmitFastNewObject(context, constructor,
399 : new_target));
400 : }
401 :
402 224 : void BaseCollectionsAssembler::GenerateConstructor(
403 : Variant variant, Handle<String> constructor_function_name,
404 : TNode<Object> new_target, TNode<IntPtrT> argc, TNode<Context> context) {
405 : const int kIterableArg = 0;
406 224 : CodeStubArguments args(this, argc);
407 224 : TNode<Object> iterable = args.GetOptionalArgumentValue(kIterableArg);
408 :
409 448 : Label if_undefined(this, Label::kDeferred);
410 448 : GotoIf(IsUndefined(new_target), &if_undefined);
411 :
412 224 : TNode<Context> native_context = LoadNativeContext(context);
413 : TNode<Object> collection = AllocateJSCollection(
414 224 : context, GetConstructor(variant, native_context), new_target);
415 :
416 224 : AddConstructorEntries(variant, context, native_context, collection, iterable);
417 224 : Return(collection);
418 :
419 224 : BIND(&if_undefined);
420 : ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
421 224 : HeapConstant(constructor_function_name));
422 224 : }
423 :
424 224 : TNode<Object> BaseCollectionsAssembler::GetAddFunction(
425 : Variant variant, TNode<Context> context, TNode<Object> collection) {
426 224 : Handle<String> add_func_name = (variant == kMap || variant == kWeakMap)
427 112 : ? isolate()->factory()->set_string()
428 336 : : isolate()->factory()->add_string();
429 224 : TNode<Object> add_func = GetProperty(context, collection, add_func_name);
430 :
431 448 : Label exit(this), if_notcallable(this, Label::kDeferred);
432 448 : GotoIf(TaggedIsSmi(add_func), &if_notcallable);
433 448 : GotoIfNot(IsCallable(CAST(add_func)), &if_notcallable);
434 224 : Goto(&exit);
435 :
436 224 : BIND(&if_notcallable);
437 : ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, add_func,
438 224 : HeapConstant(add_func_name), collection);
439 :
440 224 : BIND(&exit);
441 448 : return add_func;
442 : }
443 :
444 224 : TNode<JSFunction> BaseCollectionsAssembler::GetConstructor(
445 : Variant variant, TNode<Context> native_context) {
446 : int index;
447 224 : switch (variant) {
448 : case kMap:
449 : index = Context::JS_MAP_FUN_INDEX;
450 56 : break;
451 : case kSet:
452 : index = Context::JS_SET_FUN_INDEX;
453 56 : break;
454 : case kWeakMap:
455 : index = Context::JS_WEAK_MAP_FUN_INDEX;
456 56 : break;
457 : case kWeakSet:
458 : index = Context::JS_WEAK_SET_FUN_INDEX;
459 56 : break;
460 : }
461 224 : return CAST(LoadContextElement(native_context, index));
462 : }
463 :
464 224 : TNode<JSFunction> BaseCollectionsAssembler::GetInitialAddFunction(
465 : Variant variant, TNode<Context> native_context) {
466 : int index;
467 224 : switch (variant) {
468 : case kMap:
469 : index = Context::MAP_SET_INDEX;
470 56 : break;
471 : case kSet:
472 : index = Context::SET_ADD_INDEX;
473 56 : break;
474 : case kWeakMap:
475 : index = Context::WEAKMAP_SET_INDEX;
476 56 : break;
477 : case kWeakSet:
478 : index = Context::WEAKSET_ADD_INDEX;
479 56 : break;
480 : }
481 224 : return CAST(LoadContextElement(native_context, index));
482 : }
483 :
484 0 : int BaseCollectionsAssembler::GetTableOffset(Variant variant) {
485 224 : switch (variant) {
486 : case kMap:
487 : return JSMap::kTableOffset;
488 : case kSet:
489 : return JSSet::kTableOffset;
490 : case kWeakMap:
491 : return JSWeakMap::kTableOffset;
492 : case kWeakSet:
493 : return JSWeakSet::kTableOffset;
494 : }
495 0 : UNREACHABLE();
496 : }
497 :
498 0 : TNode<IntPtrT> BaseCollectionsAssembler::EstimatedInitialSize(
499 : TNode<Object> initial_entries, TNode<BoolT> is_fast_jsarray) {
500 : return Select<IntPtrT>(
501 : is_fast_jsarray,
502 448 : [=] { return SmiUntag(LoadFastJSArrayLength(CAST(initial_entries))); },
503 672 : [=] { return IntPtrConstant(0); });
504 : }
505 :
506 224 : void BaseCollectionsAssembler::GotoIfNotJSReceiver(Node* const obj,
507 : Label* if_not_receiver) {
508 448 : GotoIf(TaggedIsSmi(obj), if_not_receiver);
509 448 : GotoIfNot(IsJSReceiver(obj), if_not_receiver);
510 224 : }
511 :
512 224 : TNode<Map> BaseCollectionsAssembler::GetInitialCollectionPrototype(
513 : Variant variant, TNode<Context> native_context) {
514 : int initial_prototype_index;
515 224 : switch (variant) {
516 : case kMap:
517 : initial_prototype_index = Context::INITIAL_MAP_PROTOTYPE_MAP_INDEX;
518 56 : break;
519 : case kSet:
520 : initial_prototype_index = Context::INITIAL_SET_PROTOTYPE_MAP_INDEX;
521 56 : break;
522 : case kWeakMap:
523 : initial_prototype_index = Context::INITIAL_WEAKMAP_PROTOTYPE_MAP_INDEX;
524 56 : break;
525 : case kWeakSet:
526 : initial_prototype_index = Context::INITIAL_WEAKSET_PROTOTYPE_MAP_INDEX;
527 56 : break;
528 : }
529 224 : return CAST(LoadContextElement(native_context, initial_prototype_index));
530 : }
531 :
532 0 : TNode<BoolT> BaseCollectionsAssembler::HasInitialCollectionPrototype(
533 : Variant variant, TNode<Context> native_context, TNode<Object> collection) {
534 : TNode<Map> collection_proto_map =
535 0 : LoadMap(LoadMapPrototype(LoadMap(CAST(collection))));
536 :
537 : return WordEqual(collection_proto_map,
538 0 : GetInitialCollectionPrototype(variant, native_context));
539 : }
540 :
541 224 : TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedArrayElement(
542 : TNode<FixedArray> elements, TNode<IntPtrT> index) {
543 224 : TNode<Object> element = UnsafeLoadFixedArrayElement(elements, index);
544 672 : return Select<Object>(IsTheHole(element), [=] { return UndefinedConstant(); },
545 896 : [=] { return element; });
546 : }
547 :
548 224 : TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedDoubleArrayElement(
549 : TNode<HeapObject> elements, TNode<IntPtrT> index) {
550 224 : TVARIABLE(Object, entry);
551 224 : Label if_hole(this, Label::kDeferred), next(this);
552 : TNode<Float64T> element =
553 : LoadFixedDoubleArrayElement(CAST(elements), index, MachineType::Float64(),
554 224 : 0, INTPTR_PARAMETERS, &if_hole);
555 : { // not hole
556 448 : entry = AllocateHeapNumberWithValue(element);
557 224 : Goto(&next);
558 : }
559 224 : BIND(&if_hole);
560 : {
561 448 : entry = UndefinedConstant();
562 224 : Goto(&next);
563 : }
564 224 : BIND(&next);
565 224 : return entry.value();
566 : }
567 :
568 1568 : class CollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
569 : public:
570 : explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
571 1568 : : BaseCollectionsAssembler(state) {}
572 :
573 : // Check whether |iterable| is a JS_MAP_KEY_ITERATOR_TYPE or
574 : // JS_MAP_VALUE_ITERATOR_TYPE object that is not partially consumed and still
575 : // has original iteration behavior.
576 : void BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterable,
577 : TNode<Context> context,
578 : Label* if_true,
579 : Label* if_false);
580 :
581 : // Check whether |iterable| is a JS_SET_TYPE or JS_SET_VALUE_ITERATOR_TYPE
582 : // object that still has original iteration behavior. In case of the iterator,
583 : // the iterator also must not have been partially consumed.
584 : void BranchIfIterableWithOriginalValueSetIterator(TNode<Object> iterable,
585 : TNode<Context> context,
586 : Label* if_true,
587 : Label* if_false);
588 :
589 : protected:
590 : template <typename IteratorType>
591 : Node* AllocateJSCollectionIterator(Node* context, int map_index,
592 : Node* collection);
593 : TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
594 : TNode<IntPtrT> at_least_space_for) override;
595 : Node* GetHash(Node* const key);
596 : Node* CallGetHashRaw(Node* const key);
597 : Node* CallGetOrCreateHashRaw(Node* const key);
598 :
599 : // Transitions the iterator to the non obsolete backing store.
600 : // This is a NOP if the [table] is not obsolete.
601 : typedef std::function<void(Node* const table, Node* const index)>
602 : UpdateInTransition;
603 : template <typename TableType>
604 : std::pair<TNode<TableType>, TNode<IntPtrT>> Transition(
605 : TNode<TableType> const table, TNode<IntPtrT> const index,
606 : UpdateInTransition const& update_in_transition);
607 : template <typename IteratorType, typename TableType>
608 : std::pair<TNode<TableType>, TNode<IntPtrT>> TransitionAndUpdate(
609 : TNode<IteratorType> const iterator);
610 : template <typename TableType>
611 : std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>> NextSkipHoles(
612 : TNode<TableType> table, TNode<IntPtrT> index, Label* if_end);
613 :
614 : // Specialization for Smi.
615 : // The {result} variable will contain the entry index if the key was found,
616 : // or the hash code otherwise.
617 : template <typename CollectionType>
618 : void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
619 : Variable* result, Label* entry_found,
620 : Label* not_found);
621 : void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
622 : Label* if_not_same);
623 :
624 : // Specialization for heap numbers.
625 : // The {result} variable will contain the entry index if the key was found,
626 : // or the hash code otherwise.
627 : void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
628 : Label* if_same, Label* if_not_same);
629 : template <typename CollectionType>
630 : void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
631 : Node* key_heap_number,
632 : Variable* result,
633 : Label* entry_found,
634 : Label* not_found);
635 :
636 : // Specialization for bigints.
637 : // The {result} variable will contain the entry index if the key was found,
638 : // or the hash code otherwise.
639 : void SameValueZeroBigInt(Node* key, Node* candidate_key, Label* if_same,
640 : Label* if_not_same);
641 : template <typename CollectionType>
642 : void FindOrderedHashTableEntryForBigIntKey(Node* context, Node* table,
643 : Node* key, Variable* result,
644 : Label* entry_found,
645 : Label* not_found);
646 :
647 : // Specialization for string.
648 : // The {result} variable will contain the entry index if the key was found,
649 : // or the hash code otherwise.
650 : template <typename CollectionType>
651 : void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
652 : Node* key_tagged, Variable* result,
653 : Label* entry_found,
654 : Label* not_found);
655 : Node* ComputeStringHash(Node* context, Node* string_key);
656 : void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
657 : Label* if_same, Label* if_not_same);
658 :
659 : // Specialization for non-strings, non-numbers. For those we only need
660 : // reference equality to compare the keys.
661 : // The {result} variable will contain the entry index if the key was found,
662 : // or the hash code otherwise. If the hash-code has not been computed, it
663 : // should be Smi -1.
664 : template <typename CollectionType>
665 : void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
666 : Node* key, Variable* result,
667 : Label* entry_found,
668 : Label* not_found);
669 :
670 : template <typename CollectionType>
671 : void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
672 : Node* const context, Variable* result,
673 : Label* if_entry_found,
674 : Label* if_not_found);
675 :
676 : Node* NormalizeNumberKey(Node* key);
677 : void StoreOrderedHashMapNewEntry(TNode<OrderedHashMap> const table,
678 : Node* const key, Node* const value,
679 : Node* const hash,
680 : Node* const number_of_buckets,
681 : Node* const occupancy);
682 : void StoreOrderedHashSetNewEntry(TNode<OrderedHashSet> const table,
683 : Node* const key, Node* const hash,
684 : Node* const number_of_buckets,
685 : Node* const occupancy);
686 :
687 : // Create a JSArray with PACKED_ELEMENTS kind from a Map.prototype.keys() or
688 : // Map.prototype.values() iterator. The iterator is assumed to satisfy
689 : // IterableWithOriginalKeyOrValueMapIterator. This function will skip the
690 : // iterator and iterate directly on the underlying hash table. In the end it
691 : // will update the state of the iterator to 'exhausted'.
692 : TNode<JSArray> MapIteratorToList(TNode<Context> context,
693 : TNode<JSMapIterator> iterator);
694 :
695 : // Create a JSArray with PACKED_ELEMENTS kind from a Set.prototype.keys() or
696 : // Set.prototype.values() iterator, or a Set. The |iterable| is assumed to
697 : // satisfy IterableWithOriginalValueSetIterator. This function will skip the
698 : // iterator and iterate directly on the underlying hash table. In the end, if
699 : // |iterable| is an iterator, it will update the state of the iterator to
700 : // 'exhausted'.
701 : TNode<JSArray> SetOrSetIteratorToList(TNode<Context> context,
702 : TNode<Object> iterable);
703 :
704 : void BranchIfMapIteratorProtectorValid(Label* if_true, Label* if_false);
705 : void BranchIfSetIteratorProtectorValid(Label* if_true, Label* if_false);
706 : };
707 :
708 : template <typename IteratorType>
709 280 : Node* CollectionsBuiltinsAssembler::AllocateJSCollectionIterator(
710 : Node* context, int map_index, Node* collection) {
711 280 : Node* const table = LoadObjectField(collection, JSCollection::kTableOffset);
712 560 : Node* const native_context = LoadNativeContext(context);
713 560 : Node* const iterator_map = LoadContextElement(native_context, map_index);
714 560 : Node* const iterator = AllocateInNewSpace(IteratorType::kSize);
715 280 : StoreMapNoWriteBarrier(iterator, iterator_map);
716 280 : StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
717 : RootIndex::kEmptyFixedArray);
718 280 : StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
719 : RootIndex::kEmptyFixedArray);
720 280 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
721 560 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
722 280 : SmiConstant(0));
723 280 : return iterator;
724 : }
725 :
726 112 : TNode<Object> CollectionsBuiltinsAssembler::AllocateTable(
727 : Variant variant, TNode<Context> context,
728 : TNode<IntPtrT> at_least_space_for) {
729 112 : return CAST((variant == kMap || variant == kWeakMap)
730 : ? AllocateOrderedHashTable<OrderedHashMap>()
731 : : AllocateOrderedHashTable<OrderedHashSet>());
732 : }
733 :
734 336 : TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler) {
735 56 : TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
736 : TNode<IntPtrT> argc =
737 56 : ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
738 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
739 :
740 112 : GenerateConstructor(kMap, isolate()->factory()->Map_string(), new_target,
741 56 : argc, context);
742 56 : }
743 :
744 336 : TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) {
745 56 : TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
746 : TNode<IntPtrT> argc =
747 56 : ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
748 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
749 :
750 112 : GenerateConstructor(kSet, isolate()->factory()->Set_string(), new_target,
751 56 : argc, context);
752 56 : }
753 :
754 112 : Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key) {
755 : Node* const function_addr =
756 224 : ExternalConstant(ExternalReference::get_or_create_hash_raw());
757 : Node* const isolate_ptr =
758 224 : ExternalConstant(ExternalReference::isolate_address(isolate()));
759 :
760 : MachineType type_ptr = MachineType::Pointer();
761 : MachineType type_tagged = MachineType::AnyTagged();
762 :
763 : Node* const result = CallCFunction(function_addr, type_tagged,
764 : std::make_pair(type_ptr, isolate_ptr),
765 112 : std::make_pair(type_tagged, key));
766 :
767 112 : return result;
768 : }
769 :
770 1344 : Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) {
771 : Node* const function_addr =
772 2688 : ExternalConstant(ExternalReference::orderedhashmap_gethash_raw());
773 : Node* const isolate_ptr =
774 2688 : ExternalConstant(ExternalReference::isolate_address(isolate()));
775 :
776 : MachineType type_ptr = MachineType::Pointer();
777 : MachineType type_tagged = MachineType::AnyTagged();
778 :
779 : Node* const result = CallCFunction(function_addr, type_tagged,
780 : std::make_pair(type_ptr, isolate_ptr),
781 1344 : std::make_pair(type_tagged, key));
782 :
783 2688 : return SmiUntag(result);
784 : }
785 :
786 336 : Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) {
787 672 : VARIABLE(var_hash, MachineType::PointerRepresentation());
788 336 : Label if_receiver(this), if_other(this), done(this);
789 672 : Branch(IsJSReceiver(key), &if_receiver, &if_other);
790 :
791 336 : BIND(&if_receiver);
792 : {
793 672 : var_hash.Bind(LoadJSReceiverIdentityHash(key));
794 336 : Goto(&done);
795 : }
796 :
797 336 : BIND(&if_other);
798 : {
799 336 : var_hash.Bind(CallGetHashRaw(key));
800 336 : Goto(&done);
801 : }
802 :
803 336 : BIND(&done);
804 672 : return var_hash.value();
805 : }
806 :
807 336 : void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
808 : Node* candidate_key,
809 : Label* if_same,
810 : Label* if_not_same) {
811 : // If the key is the same, we are done.
812 672 : GotoIf(WordEqual(candidate_key, key_smi), if_same);
813 :
814 : // If the candidate key is smi, then it must be different (because
815 : // we already checked for equality above).
816 672 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
817 :
818 : // If the candidate key is not smi, we still have to check if it is a
819 : // heap number with the same value.
820 672 : GotoIfNot(IsHeapNumber(candidate_key), if_not_same);
821 :
822 672 : Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
823 672 : Node* const key_number = SmiToFloat64(key_smi);
824 :
825 672 : GotoIf(Float64Equal(candidate_key_number, key_number), if_same);
826 :
827 336 : Goto(if_not_same);
828 336 : }
829 :
830 112 : void CollectionsBuiltinsAssembler::BranchIfMapIteratorProtectorValid(
831 : Label* if_true, Label* if_false) {
832 224 : Node* protector_cell = LoadRoot(RootIndex::kMapIteratorProtector);
833 : DCHECK(isolate()->heap()->map_iterator_protector()->IsPropertyCell());
834 112 : Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
835 112 : SmiConstant(Isolate::kProtectorValid)),
836 112 : if_true, if_false);
837 112 : }
838 :
839 112 : void CollectionsBuiltinsAssembler::
840 : BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterator,
841 : TNode<Context> context,
842 : Label* if_true,
843 : Label* if_false) {
844 224 : Label if_key_or_value_iterator(this), extra_checks(this);
845 :
846 : // Check if iterator is a keys or values JSMapIterator.
847 224 : GotoIf(TaggedIsSmi(iterator), if_false);
848 112 : TNode<Map> iter_map = LoadMap(CAST(iterator));
849 224 : Node* const instance_type = LoadMapInstanceType(iter_map);
850 224 : GotoIf(InstanceTypeEqual(instance_type, JS_MAP_KEY_ITERATOR_TYPE),
851 112 : &if_key_or_value_iterator);
852 224 : Branch(InstanceTypeEqual(instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
853 112 : &if_key_or_value_iterator, if_false);
854 :
855 112 : BIND(&if_key_or_value_iterator);
856 : // Check that the iterator is not partially consumed.
857 : Node* const index =
858 : LoadObjectField(CAST(iterator), JSMapIterator::kIndexOffset);
859 224 : GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);
860 112 : BranchIfMapIteratorProtectorValid(&extra_checks, if_false);
861 :
862 112 : BIND(&extra_checks);
863 : // Check if the iterator object has the original %MapIteratorPrototype%.
864 224 : Node* const native_context = LoadNativeContext(context);
865 224 : Node* const initial_map_iter_proto = LoadContextElement(
866 112 : native_context, Context::INITIAL_MAP_ITERATOR_PROTOTYPE_INDEX);
867 224 : Node* const map_iter_proto = LoadMapPrototype(iter_map);
868 224 : GotoIfNot(WordEqual(map_iter_proto, initial_map_iter_proto), if_false);
869 :
870 : // Check if the original MapIterator prototype has the original
871 : // %IteratorPrototype%.
872 224 : Node* const initial_iter_proto = LoadContextElement(
873 112 : native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
874 336 : Node* const iter_proto = LoadMapPrototype(LoadMap(map_iter_proto));
875 224 : Branch(WordEqual(iter_proto, initial_iter_proto), if_true, if_false);
876 112 : }
877 :
878 112 : void BranchIfIterableWithOriginalKeyOrValueMapIterator(
879 : compiler::CodeAssemblerState* state, TNode<Object> iterable,
880 : TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
881 : compiler::CodeAssemblerLabel* if_false) {
882 : CollectionsBuiltinsAssembler assembler(state);
883 : assembler.BranchIfIterableWithOriginalKeyOrValueMapIterator(
884 112 : iterable, context, if_true, if_false);
885 112 : }
886 :
887 112 : void CollectionsBuiltinsAssembler::BranchIfSetIteratorProtectorValid(
888 : Label* if_true, Label* if_false) {
889 224 : Node* const protector_cell = LoadRoot(RootIndex::kSetIteratorProtector);
890 : DCHECK(isolate()->heap()->set_iterator_protector()->IsPropertyCell());
891 112 : Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
892 112 : SmiConstant(Isolate::kProtectorValid)),
893 112 : if_true, if_false);
894 112 : }
895 :
896 112 : void CollectionsBuiltinsAssembler::BranchIfIterableWithOriginalValueSetIterator(
897 : TNode<Object> iterable, TNode<Context> context, Label* if_true,
898 : Label* if_false) {
899 224 : Label if_set(this), if_value_iterator(this), check_protector(this);
900 : TVARIABLE(BoolT, var_result);
901 :
902 224 : GotoIf(TaggedIsSmi(iterable), if_false);
903 112 : TNode<Map> iterable_map = LoadMap(CAST(iterable));
904 224 : Node* const instance_type = LoadMapInstanceType(iterable_map);
905 :
906 224 : GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set);
907 224 : Branch(InstanceTypeEqual(instance_type, JS_SET_VALUE_ITERATOR_TYPE),
908 112 : &if_value_iterator, if_false);
909 :
910 112 : BIND(&if_set);
911 : // Check if the set object has the original Set prototype.
912 224 : Node* const initial_set_proto = LoadContextElement(
913 224 : LoadNativeContext(context), Context::INITIAL_SET_PROTOTYPE_INDEX);
914 224 : Node* const set_proto = LoadMapPrototype(iterable_map);
915 224 : GotoIfNot(WordEqual(set_proto, initial_set_proto), if_false);
916 112 : Goto(&check_protector);
917 :
918 112 : BIND(&if_value_iterator);
919 : // Check that the iterator is not partially consumed.
920 : Node* const index =
921 : LoadObjectField(CAST(iterable), JSSetIterator::kIndexOffset);
922 224 : GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);
923 :
924 : // Check if the iterator object has the original SetIterator prototype.
925 224 : Node* const native_context = LoadNativeContext(context);
926 224 : Node* const initial_set_iter_proto = LoadContextElement(
927 112 : native_context, Context::INITIAL_SET_ITERATOR_PROTOTYPE_INDEX);
928 224 : Node* const set_iter_proto = LoadMapPrototype(iterable_map);
929 224 : GotoIfNot(WordEqual(set_iter_proto, initial_set_iter_proto), if_false);
930 :
931 : // Check if the original SetIterator prototype has the original
932 : // %IteratorPrototype%.
933 224 : Node* const initial_iter_proto = LoadContextElement(
934 112 : native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
935 336 : Node* const iter_proto = LoadMapPrototype(LoadMap(set_iter_proto));
936 224 : GotoIfNot(WordEqual(iter_proto, initial_iter_proto), if_false);
937 112 : Goto(&check_protector);
938 :
939 112 : BIND(&check_protector);
940 112 : BranchIfSetIteratorProtectorValid(if_true, if_false);
941 112 : }
942 :
943 112 : void BranchIfIterableWithOriginalValueSetIterator(
944 : compiler::CodeAssemblerState* state, TNode<Object> iterable,
945 : TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
946 : compiler::CodeAssemblerLabel* if_false) {
947 : CollectionsBuiltinsAssembler assembler(state);
948 : assembler.BranchIfIterableWithOriginalValueSetIterator(iterable, context,
949 112 : if_true, if_false);
950 112 : }
951 :
952 56 : TNode<JSArray> CollectionsBuiltinsAssembler::MapIteratorToList(
953 : TNode<Context> context, TNode<JSMapIterator> iterator) {
954 : // Transition the {iterator} table if necessary.
955 : TNode<OrderedHashMap> table;
956 : TNode<IntPtrT> index;
957 : std::tie(table, index) =
958 112 : TransitionAndUpdate<JSMapIterator, OrderedHashMap>(iterator);
959 : CSA_ASSERT(this, IntPtrEqual(index, IntPtrConstant(0)));
960 :
961 : TNode<IntPtrT> size =
962 56 : LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());
963 :
964 : const ElementsKind kind = PACKED_ELEMENTS;
965 : TNode<Map> array_map =
966 112 : LoadJSArrayElementsMap(kind, LoadNativeContext(context));
967 : TNode<JSArray> array =
968 : AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
969 112 : INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
970 : TNode<FixedArray> elements = CAST(LoadElements(array));
971 :
972 : const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
973 : TNode<IntPtrT> first_to_element_offset =
974 112 : ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
975 168 : VARIABLE(
976 : var_offset, MachineType::PointerRepresentation(),
977 : IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
978 : TVARIABLE(IntPtrT, var_index, index);
979 112 : VariableList vars({&var_index, &var_offset}, zone());
980 168 : Label done(this, {&var_index}), loop(this, vars), continue_loop(this, vars),
981 56 : write_key(this, vars), write_value(this, vars);
982 :
983 56 : Goto(&loop);
984 :
985 56 : BIND(&loop);
986 : {
987 : // Read the next entry from the {table}, skipping holes.
988 : TNode<Object> entry_key;
989 : TNode<IntPtrT> entry_start_position;
990 : TNode<IntPtrT> cur_index;
991 : std::tie(entry_key, entry_start_position, cur_index) =
992 112 : NextSkipHoles<OrderedHashMap>(table, var_index.value(), &done);
993 :
994 : // Decide to write key or value.
995 56 : Branch(
996 168 : InstanceTypeEqual(LoadInstanceType(iterator), JS_MAP_KEY_ITERATOR_TYPE),
997 56 : &write_key, &write_value);
998 :
999 56 : BIND(&write_key);
1000 : {
1001 56 : Store(elements, var_offset.value(), entry_key);
1002 56 : Goto(&continue_loop);
1003 : }
1004 :
1005 56 : BIND(&write_value);
1006 : {
1007 : CSA_ASSERT(this, InstanceTypeEqual(LoadInstanceType(iterator),
1008 : JS_MAP_VALUE_ITERATOR_TYPE));
1009 : TNode<Object> entry_value =
1010 : UnsafeLoadFixedArrayElement(table, entry_start_position,
1011 : (OrderedHashMap::HashTableStartIndex() +
1012 : OrderedHashMap::kValueOffset) *
1013 : kTaggedSize);
1014 :
1015 56 : Store(elements, var_offset.value(), entry_value);
1016 56 : Goto(&continue_loop);
1017 : }
1018 :
1019 56 : BIND(&continue_loop);
1020 : {
1021 : // Increment the array offset and continue the loop to the next entry.
1022 : var_index = cur_index;
1023 : var_offset.Bind(
1024 224 : IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
1025 56 : Goto(&loop);
1026 : }
1027 : }
1028 :
1029 56 : BIND(&done);
1030 : // Set the {iterator} to exhausted.
1031 : StoreObjectFieldRoot(iterator, JSMapIterator::kTableOffset,
1032 56 : RootIndex::kEmptyOrderedHashMap);
1033 112 : StoreObjectFieldNoWriteBarrier(iterator, JSMapIterator::kIndexOffset,
1034 : SmiTag(var_index.value()));
1035 56 : return UncheckedCast<JSArray>(array);
1036 : }
1037 :
1038 280 : TF_BUILTIN(MapIteratorToList, CollectionsBuiltinsAssembler) {
1039 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
1040 56 : TNode<JSMapIterator> iterator = CAST(Parameter(Descriptor::kSource));
1041 112 : Return(MapIteratorToList(context, iterator));
1042 56 : }
1043 :
1044 56 : TNode<JSArray> CollectionsBuiltinsAssembler::SetOrSetIteratorToList(
1045 : TNode<Context> context, TNode<Object> iterable) {
1046 56 : TVARIABLE(OrderedHashSet, var_table);
1047 56 : Label if_set(this), if_iterator(this), copy(this);
1048 :
1049 112 : Node* const instance_type = LoadInstanceType(CAST(iterable));
1050 112 : Branch(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set, &if_iterator);
1051 :
1052 56 : BIND(&if_set);
1053 : {
1054 : // {iterable} is a JSSet.
1055 : var_table = CAST(LoadObjectField(CAST(iterable), JSSet::kTableOffset));
1056 56 : Goto(©);
1057 : }
1058 :
1059 56 : BIND(&if_iterator);
1060 : {
1061 : // {iterable} is a JSSetIterator.
1062 : // Transition the {iterable} table if necessary.
1063 : TNode<OrderedHashSet> iter_table;
1064 : TNode<IntPtrT> iter_index;
1065 : std::tie(iter_table, iter_index) =
1066 112 : TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(iterable));
1067 : CSA_ASSERT(this, IntPtrEqual(iter_index, IntPtrConstant(0)));
1068 : var_table = iter_table;
1069 56 : Goto(©);
1070 : }
1071 :
1072 56 : BIND(©);
1073 : TNode<OrderedHashSet> table = var_table.value();
1074 : TNode<IntPtrT> size =
1075 56 : LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());
1076 :
1077 : const ElementsKind kind = PACKED_ELEMENTS;
1078 : TNode<Map> array_map =
1079 112 : LoadJSArrayElementsMap(kind, LoadNativeContext(context));
1080 : TNode<JSArray> array =
1081 : AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
1082 112 : INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
1083 : TNode<FixedArray> elements = CAST(LoadElements(array));
1084 :
1085 : const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
1086 : TNode<IntPtrT> first_to_element_offset =
1087 112 : ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
1088 168 : VARIABLE(
1089 : var_offset, MachineType::PointerRepresentation(),
1090 : IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
1091 56 : TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
1092 168 : Label done(this), finalize(this, {&var_index}),
1093 168 : loop(this, {&var_index, &var_offset});
1094 :
1095 56 : Goto(&loop);
1096 :
1097 56 : BIND(&loop);
1098 : {
1099 : // Read the next entry from the {table}, skipping holes.
1100 : TNode<Object> entry_key;
1101 : TNode<IntPtrT> entry_start_position;
1102 : TNode<IntPtrT> cur_index;
1103 : std::tie(entry_key, entry_start_position, cur_index) =
1104 112 : NextSkipHoles<OrderedHashSet>(table, var_index.value(), &finalize);
1105 :
1106 56 : Store(elements, var_offset.value(), entry_key);
1107 :
1108 : var_index = cur_index;
1109 224 : var_offset.Bind(IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
1110 56 : Goto(&loop);
1111 : }
1112 :
1113 56 : BIND(&finalize);
1114 112 : GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &done);
1115 : // Set the {iterable} to exhausted if it's an iterator.
1116 : StoreObjectFieldRoot(iterable, JSSetIterator::kTableOffset,
1117 56 : RootIndex::kEmptyOrderedHashSet);
1118 : StoreObjectFieldNoWriteBarrier(iterable, JSSetIterator::kIndexOffset,
1119 112 : SmiTag(var_index.value()));
1120 56 : Goto(&done);
1121 :
1122 56 : BIND(&done);
1123 56 : return UncheckedCast<JSArray>(array);
1124 : }
1125 :
1126 280 : TF_BUILTIN(SetOrSetIteratorToList, CollectionsBuiltinsAssembler) {
1127 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
1128 56 : TNode<Object> object = CAST(Parameter(Descriptor::kSource));
1129 112 : Return(SetOrSetIteratorToList(context, object));
1130 56 : }
1131 :
1132 : template <typename CollectionType>
1133 336 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
1134 : Node* table, Node* smi_key, Variable* result, Label* entry_found,
1135 : Label* not_found) {
1136 1008 : Node* const key_untagged = SmiUntag(smi_key);
1137 1008 : Node* const hash = ChangeInt32ToIntPtr(ComputeUnseededHash(key_untagged));
1138 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1139 336 : result->Bind(hash);
1140 672 : FindOrderedHashTableEntry<CollectionType>(
1141 : table, hash,
1142 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
1143 336 : SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
1144 : },
1145 : result, entry_found, not_found);
1146 336 : }
1147 :
1148 : template <typename CollectionType>
1149 336 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
1150 : Node* context, Node* table, Node* key_tagged, Variable* result,
1151 : Label* entry_found, Label* not_found) {
1152 336 : Node* const hash = ComputeStringHash(context, key_tagged);
1153 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1154 336 : result->Bind(hash);
1155 672 : FindOrderedHashTableEntry<CollectionType>(
1156 : table, hash,
1157 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
1158 672 : SameValueZeroString(context, key_tagged, other_key, if_same,
1159 336 : if_not_same);
1160 : },
1161 : result, entry_found, not_found);
1162 336 : }
1163 :
1164 : template <typename CollectionType>
1165 336 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
1166 : Node* context, Node* table, Node* key_heap_number, Variable* result,
1167 : Label* entry_found, Label* not_found) {
1168 336 : Node* hash = CallGetHashRaw(key_heap_number);
1169 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1170 336 : result->Bind(hash);
1171 672 : Node* const key_float = LoadHeapNumberValue(key_heap_number);
1172 672 : FindOrderedHashTableEntry<CollectionType>(
1173 : table, hash,
1174 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
1175 336 : SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
1176 : },
1177 : result, entry_found, not_found);
1178 336 : }
1179 :
1180 : template <typename CollectionType>
1181 336 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForBigIntKey(
1182 : Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
1183 : Label* not_found) {
1184 336 : Node* hash = CallGetHashRaw(key);
1185 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1186 336 : result->Bind(hash);
1187 672 : FindOrderedHashTableEntry<CollectionType>(
1188 : table, hash,
1189 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
1190 336 : SameValueZeroBigInt(key, other_key, if_same, if_not_same);
1191 : },
1192 : result, entry_found, not_found);
1193 336 : }
1194 :
1195 : template <typename CollectionType>
1196 336 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
1197 : Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
1198 : Label* not_found) {
1199 336 : Node* hash = GetHash(key);
1200 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1201 336 : result->Bind(hash);
1202 672 : FindOrderedHashTableEntry<CollectionType>(
1203 : table, hash,
1204 336 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
1205 1008 : Branch(WordEqual(key, other_key), if_same, if_not_same);
1206 336 : },
1207 : result, entry_found, not_found);
1208 336 : }
1209 :
1210 336 : Node* CollectionsBuiltinsAssembler::ComputeStringHash(Node* context,
1211 : Node* string_key) {
1212 672 : VARIABLE(var_result, MachineType::PointerRepresentation());
1213 :
1214 336 : Label hash_not_computed(this), done(this, &var_result);
1215 : Node* hash =
1216 1008 : ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
1217 336 : var_result.Bind(hash);
1218 336 : Goto(&done);
1219 :
1220 336 : BIND(&hash_not_computed);
1221 336 : var_result.Bind(CallGetHashRaw(string_key));
1222 336 : Goto(&done);
1223 :
1224 336 : BIND(&done);
1225 672 : return var_result.value();
1226 : }
1227 :
1228 336 : void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
1229 : Node* key_string,
1230 : Node* candidate_key,
1231 : Label* if_same,
1232 : Label* if_not_same) {
1233 : // If the candidate is not a string, the keys are not equal.
1234 672 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
1235 672 : GotoIfNot(IsString(candidate_key), if_not_same);
1236 :
1237 336 : Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
1238 : candidate_key),
1239 1008 : TrueConstant()),
1240 336 : if_same, if_not_same);
1241 336 : }
1242 :
1243 336 : void CollectionsBuiltinsAssembler::SameValueZeroBigInt(Node* key,
1244 : Node* candidate_key,
1245 : Label* if_same,
1246 : Label* if_not_same) {
1247 : CSA_ASSERT(this, IsBigInt(key));
1248 672 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
1249 672 : GotoIfNot(IsBigInt(candidate_key), if_not_same);
1250 :
1251 336 : Branch(WordEqual(CallRuntime(Runtime::kBigIntEqualToBigInt,
1252 672 : NoContextConstant(), key, candidate_key),
1253 336 : TrueConstant()),
1254 336 : if_same, if_not_same);
1255 336 : }
1256 :
1257 336 : void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float,
1258 : Node* candidate_key,
1259 : Label* if_same,
1260 : Label* if_not_same) {
1261 672 : Label if_smi(this), if_keyisnan(this);
1262 :
1263 672 : GotoIf(TaggedIsSmi(candidate_key), &if_smi);
1264 672 : GotoIfNot(IsHeapNumber(candidate_key), if_not_same);
1265 :
1266 : {
1267 : // {candidate_key} is a heap number.
1268 672 : Node* const candidate_float = LoadHeapNumberValue(candidate_key);
1269 672 : GotoIf(Float64Equal(key_float, candidate_float), if_same);
1270 :
1271 : // SameValueZero needs to treat NaNs as equal. First check if {key_float}
1272 : // is NaN.
1273 336 : BranchIfFloat64IsNaN(key_float, &if_keyisnan, if_not_same);
1274 :
1275 336 : BIND(&if_keyisnan);
1276 : {
1277 : // Return true iff {candidate_key} is NaN.
1278 672 : Branch(Float64Equal(candidate_float, candidate_float), if_not_same,
1279 336 : if_same);
1280 : }
1281 : }
1282 :
1283 336 : BIND(&if_smi);
1284 : {
1285 672 : Node* const candidate_float = SmiToFloat64(candidate_key);
1286 672 : Branch(Float64Equal(key_float, candidate_float), if_same, if_not_same);
1287 : }
1288 336 : }
1289 :
1290 224 : TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) {
1291 : TNode<HeapObject> table = CAST(Parameter(Descriptor::kTable));
1292 : TNode<Smi> index = CAST(Parameter(Descriptor::kIndex));
1293 56 : Label return_index(this), return_zero(this);
1294 :
1295 : // Check if we need to update the {index}.
1296 112 : GotoIfNot(SmiLessThan(SmiConstant(0), index), &return_zero);
1297 :
1298 : // Check if the {table} was cleared.
1299 : STATIC_ASSERT(OrderedHashMap::NumberOfDeletedElementsOffset() ==
1300 : OrderedHashSet::NumberOfDeletedElementsOffset());
1301 112 : Node* number_of_deleted_elements = LoadAndUntagObjectField(
1302 56 : table, OrderedHashMap::NumberOfDeletedElementsOffset());
1303 : STATIC_ASSERT(OrderedHashMap::kClearedTableSentinel ==
1304 : OrderedHashSet::kClearedTableSentinel);
1305 112 : GotoIf(WordEqual(number_of_deleted_elements,
1306 112 : IntPtrConstant(OrderedHashMap::kClearedTableSentinel)),
1307 56 : &return_zero);
1308 :
1309 168 : VARIABLE(var_i, MachineType::PointerRepresentation(), IntPtrConstant(0));
1310 112 : VARIABLE(var_index, MachineRepresentation::kTagged, index);
1311 168 : Label loop(this, {&var_i, &var_index});
1312 56 : Goto(&loop);
1313 56 : BIND(&loop);
1314 : {
1315 56 : Node* i = var_i.value();
1316 112 : GotoIfNot(IntPtrLessThan(i, number_of_deleted_elements), &return_index);
1317 : STATIC_ASSERT(OrderedHashMap::RemovedHolesIndex() ==
1318 : OrderedHashSet::RemovedHolesIndex());
1319 56 : TNode<Smi> removed_index = CAST(LoadFixedArrayElement(
1320 : CAST(table), i, OrderedHashMap::RemovedHolesIndex() * kTaggedSize));
1321 112 : GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
1322 : Decrement(&var_index, 1, SMI_PARAMETERS);
1323 56 : Increment(&var_i);
1324 56 : Goto(&loop);
1325 : }
1326 :
1327 56 : BIND(&return_index);
1328 112 : Return(var_index.value());
1329 :
1330 56 : BIND(&return_zero);
1331 112 : Return(SmiConstant(0));
1332 56 : }
1333 :
1334 : template <typename TableType>
1335 : std::pair<TNode<TableType>, TNode<IntPtrT>>
1336 336 : CollectionsBuiltinsAssembler::Transition(
1337 : TNode<TableType> const table, TNode<IntPtrT> const index,
1338 : UpdateInTransition const& update_in_transition) {
1339 336 : TVARIABLE(IntPtrT, var_index, index);
1340 : TVARIABLE(TableType, var_table, table);
1341 336 : Label if_done(this), if_transition(this, Label::kDeferred);
1342 1008 : Branch(TaggedIsSmi(
1343 : LoadObjectField(var_table.value(), TableType::NextTableOffset())),
1344 : &if_done, &if_transition);
1345 :
1346 336 : BIND(&if_transition);
1347 : {
1348 1008 : Label loop(this, {&var_table, &var_index}), done_loop(this);
1349 336 : Goto(&loop);
1350 336 : BIND(&loop);
1351 : {
1352 : TNode<TableType> table = var_table.value();
1353 : TNode<IntPtrT> index = var_index.value();
1354 :
1355 : TNode<Object> next_table =
1356 : LoadObjectField(table, TableType::NextTableOffset());
1357 672 : GotoIf(TaggedIsSmi(next_table), &done_loop);
1358 :
1359 : var_table = CAST(next_table);
1360 1008 : var_index = SmiUntag(
1361 : CAST(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
1362 : NoContextConstant(), table, SmiTag(index))));
1363 336 : Goto(&loop);
1364 : }
1365 336 : BIND(&done_loop);
1366 :
1367 : // Update with the new {table} and {index}.
1368 : update_in_transition(var_table.value(), var_index.value());
1369 336 : Goto(&if_done);
1370 : }
1371 :
1372 336 : BIND(&if_done);
1373 672 : return {var_table.value(), var_index.value()};
1374 : }
1375 :
1376 : template <typename IteratorType, typename TableType>
1377 : std::pair<TNode<TableType>, TNode<IntPtrT>>
1378 224 : CollectionsBuiltinsAssembler::TransitionAndUpdate(
1379 : TNode<IteratorType> const iterator) {
1380 672 : return Transition<TableType>(
1381 : CAST(LoadObjectField(iterator, IteratorType::kTableOffset)),
1382 : LoadAndUntagObjectField(iterator, IteratorType::kIndexOffset),
1383 896 : [this, iterator](Node* const table, Node* const index) {
1384 : // Update the {iterator} with the new state.
1385 224 : StoreObjectField(iterator, IteratorType::kTableOffset, table);
1386 672 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
1387 : SmiTag(index));
1388 672 : });
1389 : }
1390 :
1391 : template <typename TableType>
1392 : std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>
1393 336 : CollectionsBuiltinsAssembler::NextSkipHoles(TNode<TableType> table,
1394 : TNode<IntPtrT> index,
1395 : Label* if_end) {
1396 : // Compute the used capacity for the {table}.
1397 : TNode<IntPtrT> number_of_buckets =
1398 336 : LoadAndUntagObjectField(table, TableType::NumberOfBucketsOffset());
1399 : TNode<IntPtrT> number_of_elements =
1400 336 : LoadAndUntagObjectField(table, TableType::NumberOfElementsOffset());
1401 : TNode<IntPtrT> number_of_deleted_elements = LoadAndUntagObjectField(
1402 336 : table, TableType::NumberOfDeletedElementsOffset());
1403 : TNode<IntPtrT> used_capacity =
1404 336 : IntPtrAdd(number_of_elements, number_of_deleted_elements);
1405 :
1406 : TNode<Object> entry_key;
1407 : TNode<IntPtrT> entry_start_position;
1408 : TVARIABLE(IntPtrT, var_index, index);
1409 336 : Label loop(this, &var_index), done_loop(this);
1410 336 : Goto(&loop);
1411 336 : BIND(&loop);
1412 : {
1413 672 : GotoIfNot(IntPtrLessThan(var_index.value(), used_capacity), if_end);
1414 336 : entry_start_position = IntPtrAdd(
1415 : IntPtrMul(var_index.value(), IntPtrConstant(TableType::kEntrySize)),
1416 : number_of_buckets);
1417 : entry_key = UnsafeLoadFixedArrayElement(
1418 : table, entry_start_position,
1419 : TableType::HashTableStartIndex() * kTaggedSize);
1420 336 : Increment(&var_index);
1421 672 : Branch(IsTheHole(entry_key), &loop, &done_loop);
1422 : }
1423 :
1424 336 : BIND(&done_loop);
1425 : return std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>{
1426 336 : entry_key, entry_start_position, var_index.value()};
1427 : }
1428 :
1429 224 : TF_BUILTIN(MapPrototypeGet, CollectionsBuiltinsAssembler) {
1430 : Node* const receiver = Parameter(Descriptor::kReceiver);
1431 : Node* const key = Parameter(Descriptor::kKey);
1432 : Node* const context = Parameter(Descriptor::kContext);
1433 :
1434 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");
1435 :
1436 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1437 56 : TNode<Smi> index = CAST(
1438 : CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));
1439 :
1440 56 : Label if_found(this), if_not_found(this);
1441 112 : Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
1442 56 : &if_not_found);
1443 :
1444 56 : BIND(&if_found);
1445 56 : Return(LoadFixedArrayElement(
1446 : CAST(table), SmiUntag(index),
1447 : (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1448 168 : kTaggedSize));
1449 :
1450 56 : BIND(&if_not_found);
1451 112 : Return(UndefinedConstant());
1452 56 : }
1453 :
1454 224 : TF_BUILTIN(MapPrototypeHas, CollectionsBuiltinsAssembler) {
1455 : Node* const receiver = Parameter(Descriptor::kReceiver);
1456 : Node* const key = Parameter(Descriptor::kKey);
1457 : Node* const context = Parameter(Descriptor::kContext);
1458 :
1459 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");
1460 :
1461 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1462 56 : TNode<Smi> index = CAST(
1463 : CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));
1464 :
1465 56 : Label if_found(this), if_not_found(this);
1466 112 : Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
1467 56 : &if_not_found);
1468 :
1469 56 : BIND(&if_found);
1470 112 : Return(TrueConstant());
1471 :
1472 56 : BIND(&if_not_found);
1473 112 : Return(FalseConstant());
1474 56 : }
1475 :
1476 112 : Node* CollectionsBuiltinsAssembler::NormalizeNumberKey(Node* const key) {
1477 224 : VARIABLE(result, MachineRepresentation::kTagged, key);
1478 112 : Label done(this);
1479 :
1480 224 : GotoIf(TaggedIsSmi(key), &done);
1481 224 : GotoIfNot(IsHeapNumber(key), &done);
1482 224 : Node* const number = LoadHeapNumberValue(key);
1483 336 : GotoIfNot(Float64Equal(number, Float64Constant(0.0)), &done);
1484 : // We know the value is zero, so we take the key to be Smi 0.
1485 : // Another option would be to normalize to Smi here.
1486 224 : result.Bind(SmiConstant(0));
1487 112 : Goto(&done);
1488 :
1489 112 : BIND(&done);
1490 224 : return result.value();
1491 : }
1492 :
1493 224 : TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) {
1494 : Node* const receiver = Parameter(Descriptor::kReceiver);
1495 : Node* key = Parameter(Descriptor::kKey);
1496 : Node* const value = Parameter(Descriptor::kValue);
1497 : Node* const context = Parameter(Descriptor::kContext);
1498 :
1499 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set");
1500 :
1501 56 : key = NormalizeNumberKey(key);
1502 :
1503 : TNode<OrderedHashMap> const table =
1504 : CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1505 :
1506 168 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1507 : IntPtrConstant(0));
1508 56 : Label entry_found(this), not_found(this);
1509 :
1510 : TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
1511 : &entry_start_position_or_hash,
1512 56 : &entry_found, ¬_found);
1513 :
1514 56 : BIND(&entry_found);
1515 : // If we found the entry, we just store the value there.
1516 112 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value,
1517 : UPDATE_WRITE_BARRIER,
1518 : kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
1519 56 : OrderedHashMap::kValueOffset));
1520 56 : Return(receiver);
1521 :
1522 56 : Label no_hash(this), add_entry(this), store_new_entry(this);
1523 56 : BIND(¬_found);
1524 : {
1525 : // If we have a hash code, we can start adding the new entry.
1526 112 : GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
1527 168 : IntPtrConstant(0)),
1528 56 : &add_entry);
1529 :
1530 : // Otherwise, go to runtime to compute the hash code.
1531 168 : entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1532 56 : Goto(&add_entry);
1533 : }
1534 :
1535 56 : BIND(&add_entry);
1536 112 : VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
1537 112 : VARIABLE(occupancy, MachineType::PointerRepresentation());
1538 : TVARIABLE(OrderedHashMap, table_var, table);
1539 : {
1540 : // Check we have enough space for the entry.
1541 112 : number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1542 56 : table, OrderedHashMap::NumberOfBucketsIndex()))));
1543 :
1544 : STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
1545 168 : Node* const capacity = WordShl(number_of_buckets.value(), 1);
1546 112 : Node* const number_of_elements = SmiUntag(
1547 : CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())));
1548 112 : Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
1549 : table, OrderedHashMap::NumberOfDeletedElementsOffset())));
1550 112 : occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
1551 168 : GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);
1552 :
1553 : // We do not have enough space, grow the table and reload the relevant
1554 : // fields.
1555 : CallRuntime(Runtime::kMapGrow, context, receiver);
1556 : table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1557 112 : number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1558 56 : table_var.value(), OrderedHashMap::NumberOfBucketsIndex()))));
1559 112 : Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1560 : table_var.value(), OrderedHashMap::NumberOfElementsOffset())));
1561 112 : Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1562 : table_var.value(), OrderedHashMap::NumberOfDeletedElementsOffset())));
1563 112 : occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
1564 56 : Goto(&store_new_entry);
1565 : }
1566 56 : BIND(&store_new_entry);
1567 : // Store the key, value and connect the element to the bucket chain.
1568 56 : StoreOrderedHashMapNewEntry(table_var.value(), key, value,
1569 : entry_start_position_or_hash.value(),
1570 56 : number_of_buckets.value(), occupancy.value());
1571 56 : Return(receiver);
1572 56 : }
1573 :
1574 56 : void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(
1575 : TNode<OrderedHashMap> const table, Node* const key, Node* const value,
1576 : Node* const hash, Node* const number_of_buckets, Node* const occupancy) {
1577 : Node* const bucket =
1578 224 : WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1579 : Node* const bucket_entry = UnsafeLoadFixedArrayElement(
1580 56 : table, bucket, OrderedHashMap::HashTableStartIndex() * kTaggedSize);
1581 :
1582 : // Store the entry elements.
1583 112 : Node* const entry_start = IntPtrAdd(
1584 168 : IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
1585 112 : number_of_buckets);
1586 : UnsafeStoreFixedArrayElement(
1587 : table, entry_start, key, UPDATE_WRITE_BARRIER,
1588 : kTaggedSize * OrderedHashMap::HashTableStartIndex());
1589 : UnsafeStoreFixedArrayElement(
1590 : table, entry_start, value, UPDATE_WRITE_BARRIER,
1591 : kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
1592 : OrderedHashMap::kValueOffset));
1593 : UnsafeStoreFixedArrayElement(
1594 : table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
1595 : kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
1596 : OrderedHashMap::kChainOffset));
1597 :
1598 : // Update the bucket head.
1599 : UnsafeStoreFixedArrayElement(
1600 112 : table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
1601 : OrderedHashMap::HashTableStartIndex() * kTaggedSize);
1602 :
1603 : // Bump the elements count.
1604 : TNode<Smi> const number_of_elements =
1605 56 : CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
1606 56 : StoreObjectFieldNoWriteBarrier(table,
1607 : OrderedHashMap::NumberOfElementsOffset(),
1608 : SmiAdd(number_of_elements, SmiConstant(1)));
1609 56 : }
1610 :
1611 224 : TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
1612 : Node* const receiver = Parameter(Descriptor::kReceiver);
1613 : Node* key = Parameter(Descriptor::kKey);
1614 : Node* const context = Parameter(Descriptor::kContext);
1615 :
1616 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1617 56 : "Map.prototype.delete");
1618 :
1619 : TNode<OrderedHashMap> const table =
1620 : CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1621 :
1622 168 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1623 : IntPtrConstant(0));
1624 56 : Label entry_found(this), not_found(this);
1625 :
1626 56 : TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
1627 : &entry_start_position_or_hash,
1628 56 : &entry_found, ¬_found);
1629 :
1630 56 : BIND(¬_found);
1631 112 : Return(FalseConstant());
1632 :
1633 56 : BIND(&entry_found);
1634 : // If we found the entry, mark the entry as deleted.
1635 112 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1636 112 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1637 56 : kTaggedSize * OrderedHashMap::HashTableStartIndex());
1638 112 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1639 112 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1640 : kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
1641 56 : OrderedHashMap::kValueOffset));
1642 :
1643 : // Decrement the number of elements, increment the number of deleted elements.
1644 : TNode<Smi> const number_of_elements = SmiSub(
1645 : CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())),
1646 112 : SmiConstant(1));
1647 : StoreObjectFieldNoWriteBarrier(
1648 : table, OrderedHashMap::NumberOfElementsOffset(), number_of_elements);
1649 : TNode<Smi> const number_of_deleted =
1650 : SmiAdd(CAST(LoadObjectField(
1651 : table, OrderedHashMap::NumberOfDeletedElementsOffset())),
1652 112 : SmiConstant(1));
1653 : StoreObjectFieldNoWriteBarrier(
1654 : table, OrderedHashMap::NumberOfDeletedElementsOffset(),
1655 : number_of_deleted);
1656 :
1657 56 : TNode<Smi> const number_of_buckets = CAST(
1658 : LoadFixedArrayElement(table, OrderedHashMap::NumberOfBucketsIndex()));
1659 :
1660 : // If there fewer elements than #buckets / 2, shrink the table.
1661 56 : Label shrink(this);
1662 112 : GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
1663 56 : number_of_buckets),
1664 56 : &shrink);
1665 112 : Return(TrueConstant());
1666 :
1667 56 : BIND(&shrink);
1668 : CallRuntime(Runtime::kMapShrink, context, receiver);
1669 112 : Return(TrueConstant());
1670 56 : }
1671 :
1672 224 : TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler) {
1673 : Node* const receiver = Parameter(Descriptor::kReceiver);
1674 : Node* key = Parameter(Descriptor::kKey);
1675 : Node* const context = Parameter(Descriptor::kContext);
1676 :
1677 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");
1678 :
1679 56 : key = NormalizeNumberKey(key);
1680 :
1681 : TNode<OrderedHashSet> const table =
1682 : CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1683 :
1684 168 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1685 : IntPtrConstant(0));
1686 56 : Label entry_found(this), not_found(this);
1687 :
1688 : TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
1689 : &entry_start_position_or_hash,
1690 56 : &entry_found, ¬_found);
1691 :
1692 56 : BIND(&entry_found);
1693 : // The entry was found, there is nothing to do.
1694 56 : Return(receiver);
1695 :
1696 56 : Label no_hash(this), add_entry(this), store_new_entry(this);
1697 56 : BIND(¬_found);
1698 : {
1699 : // If we have a hash code, we can start adding the new entry.
1700 112 : GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
1701 168 : IntPtrConstant(0)),
1702 56 : &add_entry);
1703 :
1704 : // Otherwise, go to runtime to compute the hash code.
1705 168 : entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1706 56 : Goto(&add_entry);
1707 : }
1708 :
1709 56 : BIND(&add_entry);
1710 112 : VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
1711 112 : VARIABLE(occupancy, MachineType::PointerRepresentation());
1712 : TVARIABLE(OrderedHashSet, table_var, table);
1713 : {
1714 : // Check we have enough space for the entry.
1715 112 : number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1716 56 : table, OrderedHashSet::NumberOfBucketsIndex()))));
1717 :
1718 : STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
1719 168 : Node* const capacity = WordShl(number_of_buckets.value(), 1);
1720 112 : Node* const number_of_elements = SmiUntag(
1721 : CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())));
1722 112 : Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
1723 : table, OrderedHashSet::NumberOfDeletedElementsOffset())));
1724 112 : occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
1725 168 : GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);
1726 :
1727 : // We do not have enough space, grow the table and reload the relevant
1728 : // fields.
1729 : CallRuntime(Runtime::kSetGrow, context, receiver);
1730 : table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1731 112 : number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1732 56 : table_var.value(), OrderedHashSet::NumberOfBucketsIndex()))));
1733 112 : Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1734 : table_var.value(), OrderedHashSet::NumberOfElementsOffset())));
1735 112 : Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1736 : table_var.value(), OrderedHashSet::NumberOfDeletedElementsOffset())));
1737 112 : occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
1738 56 : Goto(&store_new_entry);
1739 : }
1740 56 : BIND(&store_new_entry);
1741 : // Store the key, value and connect the element to the bucket chain.
1742 56 : StoreOrderedHashSetNewEntry(table_var.value(), key,
1743 : entry_start_position_or_hash.value(),
1744 56 : number_of_buckets.value(), occupancy.value());
1745 56 : Return(receiver);
1746 56 : }
1747 :
1748 56 : void CollectionsBuiltinsAssembler::StoreOrderedHashSetNewEntry(
1749 : TNode<OrderedHashSet> const table, Node* const key, Node* const hash,
1750 : Node* const number_of_buckets, Node* const occupancy) {
1751 : Node* const bucket =
1752 224 : WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1753 : Node* const bucket_entry = UnsafeLoadFixedArrayElement(
1754 56 : table, bucket, OrderedHashSet::HashTableStartIndex() * kTaggedSize);
1755 :
1756 : // Store the entry elements.
1757 112 : Node* const entry_start = IntPtrAdd(
1758 168 : IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
1759 112 : number_of_buckets);
1760 : UnsafeStoreFixedArrayElement(
1761 : table, entry_start, key, UPDATE_WRITE_BARRIER,
1762 : kTaggedSize * OrderedHashSet::HashTableStartIndex());
1763 : UnsafeStoreFixedArrayElement(
1764 : table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
1765 : kTaggedSize * (OrderedHashSet::HashTableStartIndex() +
1766 : OrderedHashSet::kChainOffset));
1767 :
1768 : // Update the bucket head.
1769 : UnsafeStoreFixedArrayElement(
1770 112 : table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
1771 : OrderedHashSet::HashTableStartIndex() * kTaggedSize);
1772 :
1773 : // Bump the elements count.
1774 : TNode<Smi> const number_of_elements =
1775 56 : CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
1776 56 : StoreObjectFieldNoWriteBarrier(table,
1777 : OrderedHashSet::NumberOfElementsOffset(),
1778 : SmiAdd(number_of_elements, SmiConstant(1)));
1779 56 : }
1780 :
1781 224 : TF_BUILTIN(SetPrototypeDelete, CollectionsBuiltinsAssembler) {
1782 : Node* const receiver = Parameter(Descriptor::kReceiver);
1783 : Node* key = Parameter(Descriptor::kKey);
1784 : Node* const context = Parameter(Descriptor::kContext);
1785 :
1786 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
1787 56 : "Set.prototype.delete");
1788 :
1789 : TNode<OrderedHashSet> const table =
1790 : CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1791 :
1792 168 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1793 : IntPtrConstant(0));
1794 56 : Label entry_found(this), not_found(this);
1795 :
1796 56 : TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
1797 : &entry_start_position_or_hash,
1798 56 : &entry_found, ¬_found);
1799 :
1800 56 : BIND(¬_found);
1801 112 : Return(FalseConstant());
1802 :
1803 56 : BIND(&entry_found);
1804 : // If we found the entry, mark the entry as deleted.
1805 112 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1806 112 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1807 56 : kTaggedSize * OrderedHashSet::HashTableStartIndex());
1808 :
1809 : // Decrement the number of elements, increment the number of deleted elements.
1810 : TNode<Smi> const number_of_elements = SmiSub(
1811 : CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())),
1812 112 : SmiConstant(1));
1813 : StoreObjectFieldNoWriteBarrier(
1814 : table, OrderedHashSet::NumberOfElementsOffset(), number_of_elements);
1815 : TNode<Smi> const number_of_deleted =
1816 : SmiAdd(CAST(LoadObjectField(
1817 : table, OrderedHashSet::NumberOfDeletedElementsOffset())),
1818 112 : SmiConstant(1));
1819 : StoreObjectFieldNoWriteBarrier(
1820 : table, OrderedHashSet::NumberOfDeletedElementsOffset(),
1821 : number_of_deleted);
1822 :
1823 56 : TNode<Smi> const number_of_buckets = CAST(
1824 : LoadFixedArrayElement(table, OrderedHashSet::NumberOfBucketsIndex()));
1825 :
1826 : // If there fewer elements than #buckets / 2, shrink the table.
1827 56 : Label shrink(this);
1828 112 : GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
1829 56 : number_of_buckets),
1830 56 : &shrink);
1831 112 : Return(TrueConstant());
1832 :
1833 56 : BIND(&shrink);
1834 : CallRuntime(Runtime::kSetShrink, context, receiver);
1835 112 : Return(TrueConstant());
1836 56 : }
1837 :
1838 224 : TF_BUILTIN(MapPrototypeEntries, CollectionsBuiltinsAssembler) {
1839 : Node* const receiver = Parameter(Descriptor::kReceiver);
1840 : Node* const context = Parameter(Descriptor::kContext);
1841 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1842 56 : "Map.prototype.entries");
1843 112 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1844 56 : context, Context::MAP_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
1845 56 : }
1846 :
1847 224 : TF_BUILTIN(MapPrototypeGetSize, CollectionsBuiltinsAssembler) {
1848 : Node* const receiver = Parameter(Descriptor::kReceiver);
1849 : Node* const context = Parameter(Descriptor::kContext);
1850 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1851 56 : "get Map.prototype.size");
1852 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1853 56 : Return(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
1854 56 : }
1855 :
1856 224 : TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) {
1857 : const char* const kMethodName = "Map.prototype.forEach";
1858 : Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
1859 : Node* const context = Parameter(Descriptor::kContext);
1860 168 : CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
1861 112 : Node* const receiver = args.GetReceiver();
1862 112 : Node* const callback = args.GetOptionalArgumentValue(0);
1863 112 : Node* const this_arg = args.GetOptionalArgumentValue(1);
1864 :
1865 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, kMethodName);
1866 :
1867 : // Ensure that {callback} is actually callable.
1868 56 : Label callback_not_callable(this, Label::kDeferred);
1869 112 : GotoIf(TaggedIsSmi(callback), &callback_not_callable);
1870 112 : GotoIfNot(IsCallable(callback), &callback_not_callable);
1871 :
1872 56 : TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
1873 : TVARIABLE(OrderedHashMap, var_table,
1874 : CAST(LoadObjectField(receiver, JSMap::kTableOffset)));
1875 168 : Label loop(this, {&var_index, &var_table}), done_loop(this);
1876 56 : Goto(&loop);
1877 56 : BIND(&loop);
1878 : {
1879 : // Transition {table} and {index} if there was any modification to
1880 : // the {receiver} while we're iterating.
1881 56 : TNode<IntPtrT> index = var_index.value();
1882 56 : TNode<OrderedHashMap> table = var_table.value();
1883 : std::tie(table, index) =
1884 168 : Transition<OrderedHashMap>(table, index, [](Node*, Node*) {});
1885 :
1886 : // Read the next entry from the {table}, skipping holes.
1887 : TNode<Object> entry_key;
1888 : TNode<IntPtrT> entry_start_position;
1889 : std::tie(entry_key, entry_start_position, index) =
1890 112 : NextSkipHoles<OrderedHashMap>(table, index, &done_loop);
1891 :
1892 : // Load the entry value as well.
1893 : Node* entry_value = LoadFixedArrayElement(
1894 : table, entry_start_position,
1895 : (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1896 : kTaggedSize);
1897 :
1898 : // Invoke the {callback} passing the {entry_key}, {entry_value} and the
1899 : // {receiver}.
1900 112 : CallJS(CodeFactory::Call(isolate()), context, callback, this_arg,
1901 56 : entry_value, entry_key, receiver);
1902 :
1903 : // Continue with the next entry.
1904 : var_index = index;
1905 : var_table = table;
1906 56 : Goto(&loop);
1907 : }
1908 :
1909 56 : BIND(&done_loop);
1910 112 : args.PopAndReturn(UndefinedConstant());
1911 :
1912 56 : BIND(&callback_not_callable);
1913 : {
1914 : CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
1915 56 : Unreachable();
1916 : }
1917 56 : }
1918 :
1919 224 : TF_BUILTIN(MapPrototypeKeys, CollectionsBuiltinsAssembler) {
1920 : Node* const receiver = Parameter(Descriptor::kReceiver);
1921 : Node* const context = Parameter(Descriptor::kContext);
1922 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.keys");
1923 112 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1924 56 : context, Context::MAP_KEY_ITERATOR_MAP_INDEX, receiver));
1925 56 : }
1926 :
1927 224 : TF_BUILTIN(MapPrototypeValues, CollectionsBuiltinsAssembler) {
1928 : Node* const receiver = Parameter(Descriptor::kReceiver);
1929 : Node* const context = Parameter(Descriptor::kContext);
1930 56 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1931 56 : "Map.prototype.values");
1932 112 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1933 56 : context, Context::MAP_VALUE_ITERATOR_MAP_INDEX, receiver));
1934 56 : }
1935 :
1936 224 : TF_BUILTIN(MapIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
1937 : const char* const kMethodName = "Map Iterator.prototype.next";
1938 : Node* const receiver = Parameter(Descriptor::kReceiver);
1939 : Node* const context = Parameter(Descriptor::kContext);
1940 :
1941 : // Ensure that the {receiver} is actually a JSMapIterator.
1942 56 : Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
1943 112 : GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
1944 112 : Node* const receiver_instance_type = LoadInstanceType(receiver);
1945 56 : GotoIf(
1946 112 : InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_VALUE_ITERATOR_TYPE),
1947 56 : &if_receiver_valid);
1948 112 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
1949 56 : &if_receiver_valid);
1950 112 : Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
1951 56 : &if_receiver_valid, &if_receiver_invalid);
1952 56 : BIND(&if_receiver_invalid);
1953 : ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
1954 112 : StringConstant(kMethodName), receiver);
1955 56 : BIND(&if_receiver_valid);
1956 :
1957 : // Check if the {receiver} is exhausted.
1958 168 : VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1959 168 : VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
1960 168 : Label return_value(this, {&var_done, &var_value}), return_entry(this),
1961 56 : return_end(this, Label::kDeferred);
1962 :
1963 : // Transition the {receiver} table if necessary.
1964 : TNode<OrderedHashMap> table;
1965 : TNode<IntPtrT> index;
1966 : std::tie(table, index) =
1967 112 : TransitionAndUpdate<JSMapIterator, OrderedHashMap>(CAST(receiver));
1968 :
1969 : // Read the next entry from the {table}, skipping holes.
1970 : TNode<Object> entry_key;
1971 : TNode<IntPtrT> entry_start_position;
1972 : std::tie(entry_key, entry_start_position, index) =
1973 112 : NextSkipHoles<OrderedHashMap>(table, index, &return_end);
1974 : StoreObjectFieldNoWriteBarrier(receiver, JSMapIterator::kIndexOffset,
1975 112 : SmiTag(index));
1976 56 : var_value.Bind(entry_key);
1977 112 : var_done.Bind(FalseConstant());
1978 :
1979 : // Check how to return the {key} (depending on {receiver} type).
1980 112 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
1981 56 : &return_value);
1982 : var_value.Bind(LoadFixedArrayElement(
1983 : table, entry_start_position,
1984 : (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1985 56 : kTaggedSize));
1986 112 : Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
1987 56 : &return_value, &return_entry);
1988 :
1989 56 : BIND(&return_entry);
1990 : {
1991 : Node* result =
1992 56 : AllocateJSIteratorResultForEntry(context, entry_key, var_value.value());
1993 56 : Return(result);
1994 : }
1995 :
1996 56 : BIND(&return_value);
1997 : {
1998 : Node* result =
1999 56 : AllocateJSIteratorResult(context, var_value.value(), var_done.value());
2000 56 : Return(result);
2001 : }
2002 :
2003 56 : BIND(&return_end);
2004 : {
2005 : StoreObjectFieldRoot(receiver, JSMapIterator::kTableOffset,
2006 56 : RootIndex::kEmptyOrderedHashMap);
2007 56 : Goto(&return_value);
2008 : }
2009 56 : }
2010 :
2011 224 : TF_BUILTIN(SetPrototypeHas, CollectionsBuiltinsAssembler) {
2012 : Node* const receiver = Parameter(Descriptor::kReceiver);
2013 : Node* const key = Parameter(Descriptor::kKey);
2014 : Node* const context = Parameter(Descriptor::kContext);
2015 :
2016 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");
2017 :
2018 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
2019 :
2020 168 : VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
2021 : IntPtrConstant(0));
2022 168 : VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0));
2023 56 : Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
2024 56 : if_key_bigint(this), entry_found(this), not_found(this), done(this);
2025 :
2026 112 : GotoIf(TaggedIsSmi(key), &if_key_smi);
2027 :
2028 112 : Node* key_map = LoadMap(key);
2029 112 : Node* key_instance_type = LoadMapInstanceType(key_map);
2030 :
2031 112 : GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
2032 112 : GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
2033 112 : GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
2034 :
2035 56 : FindOrderedHashTableEntryForOtherKey<OrderedHashSet>(
2036 56 : context, table, key, &entry_start_position, &entry_found, ¬_found);
2037 :
2038 56 : BIND(&if_key_smi);
2039 : {
2040 : FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
2041 56 : table, key, &entry_start_position, &entry_found, ¬_found);
2042 : }
2043 :
2044 56 : BIND(&if_key_string);
2045 : {
2046 : FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
2047 56 : context, table, key, &entry_start_position, &entry_found, ¬_found);
2048 : }
2049 :
2050 56 : BIND(&if_key_heap_number);
2051 : {
2052 : FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
2053 56 : context, table, key, &entry_start_position, &entry_found, ¬_found);
2054 : }
2055 :
2056 56 : BIND(&if_key_bigint);
2057 : {
2058 : FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
2059 56 : context, table, key, &entry_start_position, &entry_found, ¬_found);
2060 : }
2061 :
2062 56 : BIND(&entry_found);
2063 112 : Return(TrueConstant());
2064 :
2065 56 : BIND(¬_found);
2066 112 : Return(FalseConstant());
2067 56 : }
2068 :
2069 224 : TF_BUILTIN(SetPrototypeEntries, CollectionsBuiltinsAssembler) {
2070 : Node* const receiver = Parameter(Descriptor::kReceiver);
2071 : Node* const context = Parameter(Descriptor::kContext);
2072 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
2073 56 : "Set.prototype.entries");
2074 112 : Return(AllocateJSCollectionIterator<JSSetIterator>(
2075 56 : context, Context::SET_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
2076 56 : }
2077 :
2078 224 : TF_BUILTIN(SetPrototypeGetSize, CollectionsBuiltinsAssembler) {
2079 : Node* const receiver = Parameter(Descriptor::kReceiver);
2080 : Node* const context = Parameter(Descriptor::kContext);
2081 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
2082 56 : "get Set.prototype.size");
2083 : Node* const table = LoadObjectField(receiver, JSSet::kTableOffset);
2084 56 : Return(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
2085 56 : }
2086 :
2087 224 : TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) {
2088 : const char* const kMethodName = "Set.prototype.forEach";
2089 : Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
2090 : Node* const context = Parameter(Descriptor::kContext);
2091 168 : CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
2092 112 : Node* const receiver = args.GetReceiver();
2093 112 : Node* const callback = args.GetOptionalArgumentValue(0);
2094 112 : Node* const this_arg = args.GetOptionalArgumentValue(1);
2095 :
2096 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, kMethodName);
2097 :
2098 : // Ensure that {callback} is actually callable.
2099 56 : Label callback_not_callable(this, Label::kDeferred);
2100 112 : GotoIf(TaggedIsSmi(callback), &callback_not_callable);
2101 112 : GotoIfNot(IsCallable(callback), &callback_not_callable);
2102 :
2103 56 : TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
2104 : TVARIABLE(OrderedHashSet, var_table,
2105 : CAST(LoadObjectField(receiver, JSSet::kTableOffset)));
2106 168 : Label loop(this, {&var_index, &var_table}), done_loop(this);
2107 56 : Goto(&loop);
2108 56 : BIND(&loop);
2109 : {
2110 : // Transition {table} and {index} if there was any modification to
2111 : // the {receiver} while we're iterating.
2112 56 : TNode<IntPtrT> index = var_index.value();
2113 56 : TNode<OrderedHashSet> table = var_table.value();
2114 : std::tie(table, index) =
2115 168 : Transition<OrderedHashSet>(table, index, [](Node*, Node*) {});
2116 :
2117 : // Read the next entry from the {table}, skipping holes.
2118 : Node* entry_key;
2119 : Node* entry_start_position;
2120 : std::tie(entry_key, entry_start_position, index) =
2121 112 : NextSkipHoles<OrderedHashSet>(table, index, &done_loop);
2122 :
2123 : // Invoke the {callback} passing the {entry_key} (twice) and the {receiver}.
2124 112 : CallJS(CodeFactory::Call(isolate()), context, callback, this_arg, entry_key,
2125 56 : entry_key, receiver);
2126 :
2127 : // Continue with the next entry.
2128 : var_index = index;
2129 : var_table = table;
2130 56 : Goto(&loop);
2131 : }
2132 :
2133 56 : BIND(&done_loop);
2134 112 : args.PopAndReturn(UndefinedConstant());
2135 :
2136 56 : BIND(&callback_not_callable);
2137 : {
2138 : CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
2139 56 : Unreachable();
2140 : }
2141 56 : }
2142 :
2143 224 : TF_BUILTIN(SetPrototypeValues, CollectionsBuiltinsAssembler) {
2144 : Node* const receiver = Parameter(Descriptor::kReceiver);
2145 : Node* const context = Parameter(Descriptor::kContext);
2146 56 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
2147 56 : "Set.prototype.values");
2148 112 : Return(AllocateJSCollectionIterator<JSSetIterator>(
2149 56 : context, Context::SET_VALUE_ITERATOR_MAP_INDEX, receiver));
2150 56 : }
2151 :
2152 224 : TF_BUILTIN(SetIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
2153 : const char* const kMethodName = "Set Iterator.prototype.next";
2154 : Node* const receiver = Parameter(Descriptor::kReceiver);
2155 : Node* const context = Parameter(Descriptor::kContext);
2156 :
2157 : // Ensure that the {receiver} is actually a JSSetIterator.
2158 56 : Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
2159 112 : GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
2160 112 : Node* const receiver_instance_type = LoadInstanceType(receiver);
2161 112 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
2162 56 : &if_receiver_valid);
2163 56 : Branch(
2164 112 : InstanceTypeEqual(receiver_instance_type, JS_SET_KEY_VALUE_ITERATOR_TYPE),
2165 56 : &if_receiver_valid, &if_receiver_invalid);
2166 56 : BIND(&if_receiver_invalid);
2167 : ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
2168 112 : StringConstant(kMethodName), receiver);
2169 56 : BIND(&if_receiver_valid);
2170 :
2171 : // Check if the {receiver} is exhausted.
2172 168 : VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
2173 168 : VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
2174 168 : Label return_value(this, {&var_done, &var_value}), return_entry(this),
2175 56 : return_end(this, Label::kDeferred);
2176 :
2177 : // Transition the {receiver} table if necessary.
2178 : TNode<OrderedHashSet> table;
2179 : TNode<IntPtrT> index;
2180 : std::tie(table, index) =
2181 112 : TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(receiver));
2182 :
2183 : // Read the next entry from the {table}, skipping holes.
2184 : Node* entry_key;
2185 : Node* entry_start_position;
2186 : std::tie(entry_key, entry_start_position, index) =
2187 112 : NextSkipHoles<OrderedHashSet>(table, index, &return_end);
2188 : StoreObjectFieldNoWriteBarrier(receiver, JSSetIterator::kIndexOffset,
2189 112 : SmiTag(index));
2190 56 : var_value.Bind(entry_key);
2191 112 : var_done.Bind(FalseConstant());
2192 :
2193 : // Check how to return the {key} (depending on {receiver} type).
2194 112 : Branch(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
2195 56 : &return_value, &return_entry);
2196 :
2197 56 : BIND(&return_entry);
2198 : {
2199 56 : Node* result = AllocateJSIteratorResultForEntry(context, var_value.value(),
2200 56 : var_value.value());
2201 56 : Return(result);
2202 : }
2203 :
2204 56 : BIND(&return_value);
2205 : {
2206 : Node* result =
2207 56 : AllocateJSIteratorResult(context, var_value.value(), var_done.value());
2208 56 : Return(result);
2209 : }
2210 :
2211 56 : BIND(&return_end);
2212 : {
2213 : StoreObjectFieldRoot(receiver, JSSetIterator::kTableOffset,
2214 56 : RootIndex::kEmptyOrderedHashSet);
2215 56 : Goto(&return_value);
2216 : }
2217 56 : }
2218 :
2219 : template <typename CollectionType>
2220 280 : void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
2221 : Node* const table, Node* const key, Node* const context, Variable* result,
2222 : Label* if_entry_found, Label* if_not_found) {
2223 560 : Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
2224 280 : if_key_bigint(this);
2225 :
2226 560 : GotoIf(TaggedIsSmi(key), &if_key_smi);
2227 :
2228 560 : Node* key_map = LoadMap(key);
2229 560 : Node* key_instance_type = LoadMapInstanceType(key_map);
2230 :
2231 560 : GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
2232 560 : GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
2233 560 : GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
2234 :
2235 280 : FindOrderedHashTableEntryForOtherKey<CollectionType>(
2236 : context, table, key, result, if_entry_found, if_not_found);
2237 :
2238 280 : BIND(&if_key_smi);
2239 : {
2240 280 : FindOrderedHashTableEntryForSmiKey<CollectionType>(
2241 : table, key, result, if_entry_found, if_not_found);
2242 : }
2243 :
2244 280 : BIND(&if_key_string);
2245 : {
2246 280 : FindOrderedHashTableEntryForStringKey<CollectionType>(
2247 : context, table, key, result, if_entry_found, if_not_found);
2248 : }
2249 :
2250 280 : BIND(&if_key_heap_number);
2251 : {
2252 280 : FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
2253 : context, table, key, result, if_entry_found, if_not_found);
2254 : }
2255 :
2256 280 : BIND(&if_key_bigint);
2257 : {
2258 280 : FindOrderedHashTableEntryForBigIntKey<CollectionType>(
2259 : context, table, key, result, if_entry_found, if_not_found);
2260 : }
2261 280 : }
2262 :
2263 224 : TF_BUILTIN(FindOrderedHashMapEntry, CollectionsBuiltinsAssembler) {
2264 : Node* const table = Parameter(Descriptor::kTable);
2265 : Node* const key = Parameter(Descriptor::kKey);
2266 : Node* const context = Parameter(Descriptor::kContext);
2267 :
2268 168 : VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
2269 : IntPtrConstant(0));
2270 56 : Label entry_found(this), not_found(this);
2271 :
2272 56 : TryLookupOrderedHashTableIndex<OrderedHashMap>(
2273 56 : table, key, context, &entry_start_position, &entry_found, ¬_found);
2274 :
2275 56 : BIND(&entry_found);
2276 168 : Return(SmiTag(entry_start_position.value()));
2277 :
2278 56 : BIND(¬_found);
2279 112 : Return(SmiConstant(-1));
2280 56 : }
2281 :
2282 560 : class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
2283 : public:
2284 : explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
2285 560 : : BaseCollectionsAssembler(state) {}
2286 :
2287 : protected:
2288 : void AddEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2289 : TNode<Object> key, TNode<Object> value,
2290 : TNode<IntPtrT> number_of_elements);
2291 :
2292 : TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
2293 : TNode<IntPtrT> at_least_space_for) override;
2294 :
2295 : // Generates and sets the identity for a JSRececiver.
2296 : TNode<Smi> CreateIdentityHash(TNode<Object> receiver);
2297 : TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity);
2298 :
2299 : // Builds code that finds the EphemeronHashTable entry for a {key} using the
2300 : // comparison code generated by {key_compare}. The key index is returned if
2301 : // the {key} is found.
2302 : typedef std::function<void(TNode<Object> entry_key, Label* if_same)>
2303 : KeyComparator;
2304 : TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash,
2305 : TNode<IntPtrT> entry_mask,
2306 : const KeyComparator& key_compare);
2307 :
2308 : // Builds code that finds an EphemeronHashTable entry available for a new
2309 : // entry.
2310 : TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table,
2311 : TNode<IntPtrT> key_hash,
2312 : TNode<IntPtrT> entry_mask);
2313 :
2314 : // Builds code that finds the EphemeronHashTable entry with key that matches
2315 : // {key} and returns the entry's key index. If {key} cannot be found, jumps to
2316 : // {if_not_found}.
2317 : TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key,
2318 : TNode<IntPtrT> hash,
2319 : TNode<IntPtrT> entry_mask,
2320 : Label* if_not_found);
2321 :
2322 : TNode<Word32T> InsufficientCapacityToAdd(TNode<IntPtrT> capacity,
2323 : TNode<IntPtrT> number_of_elements,
2324 : TNode<IntPtrT> number_of_deleted);
2325 : TNode<IntPtrT> KeyIndexFromEntry(TNode<IntPtrT> entry);
2326 :
2327 : TNode<IntPtrT> LoadNumberOfElements(TNode<EphemeronHashTable> table,
2328 : int offset);
2329 : TNode<IntPtrT> LoadNumberOfDeleted(TNode<EphemeronHashTable> table,
2330 : int offset = 0);
2331 : TNode<EphemeronHashTable> LoadTable(TNode<JSWeakCollection> collection);
2332 : TNode<IntPtrT> LoadTableCapacity(TNode<EphemeronHashTable> table);
2333 :
2334 : void RemoveEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2335 : TNode<IntPtrT> number_of_elements);
2336 : TNode<BoolT> ShouldRehash(TNode<IntPtrT> number_of_elements,
2337 : TNode<IntPtrT> number_of_deleted);
2338 : TNode<Word32T> ShouldShrink(TNode<IntPtrT> capacity,
2339 : TNode<IntPtrT> number_of_elements);
2340 : TNode<IntPtrT> ValueIndexFromKeyIndex(TNode<IntPtrT> key_index);
2341 : };
2342 :
2343 56 : void WeakCollectionsBuiltinsAssembler::AddEntry(
2344 : TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2345 : TNode<Object> key, TNode<Object> value, TNode<IntPtrT> number_of_elements) {
2346 : // See EphemeronHashTable::AddEntry().
2347 56 : TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
2348 56 : UnsafeStoreFixedArrayElement(table, key_index, key,
2349 : UPDATE_EPHEMERON_KEY_WRITE_BARRIER);
2350 : UnsafeStoreFixedArrayElement(table, value_index, value);
2351 :
2352 : // See HashTableBase::ElementAdded().
2353 : UnsafeStoreFixedArrayElement(
2354 : table, EphemeronHashTable::kNumberOfElementsIndex,
2355 : SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2356 56 : }
2357 :
2358 112 : TNode<Object> WeakCollectionsBuiltinsAssembler::AllocateTable(
2359 : Variant variant, TNode<Context> context,
2360 : TNode<IntPtrT> at_least_space_for) {
2361 : // See HashTable::New().
2362 : CSA_ASSERT(this,
2363 : IntPtrLessThanOrEqual(IntPtrConstant(0), at_least_space_for));
2364 112 : TNode<IntPtrT> capacity = HashTableComputeCapacity(at_least_space_for);
2365 :
2366 : // See HashTable::NewInternal().
2367 112 : TNode<IntPtrT> length = KeyIndexFromEntry(capacity);
2368 : TNode<FixedArray> table = CAST(
2369 : AllocateFixedArray(HOLEY_ELEMENTS, length, kAllowLargeObjectAllocation));
2370 :
2371 : RootIndex map_root_index = EphemeronHashTableShape::GetMapRootIndex();
2372 112 : StoreMapNoWriteBarrier(table, map_root_index);
2373 112 : StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2374 336 : SmiConstant(0), SKIP_WRITE_BARRIER);
2375 112 : StoreFixedArrayElement(table,
2376 : EphemeronHashTable::kNumberOfDeletedElementsIndex,
2377 336 : SmiConstant(0), SKIP_WRITE_BARRIER);
2378 112 : StoreFixedArrayElement(table, EphemeronHashTable::kCapacityIndex,
2379 112 : SmiFromIntPtr(capacity), SKIP_WRITE_BARRIER);
2380 :
2381 112 : TNode<IntPtrT> start = KeyIndexFromEntry(IntPtrConstant(0));
2382 : FillFixedArrayWithValue(HOLEY_ELEMENTS, table, start, length,
2383 112 : RootIndex::kUndefinedValue);
2384 112 : return table;
2385 : }
2386 :
2387 56 : TNode<Smi> WeakCollectionsBuiltinsAssembler::CreateIdentityHash(
2388 : TNode<Object> key) {
2389 : TNode<ExternalReference> function_addr =
2390 56 : ExternalConstant(ExternalReference::jsreceiver_create_identity_hash());
2391 : TNode<ExternalReference> isolate_ptr =
2392 56 : ExternalConstant(ExternalReference::isolate_address(isolate()));
2393 :
2394 : MachineType type_ptr = MachineType::Pointer();
2395 : MachineType type_tagged = MachineType::AnyTagged();
2396 :
2397 56 : return CAST(CallCFunction(function_addr, type_tagged,
2398 : std::make_pair(type_ptr, isolate_ptr),
2399 : std::make_pair(type_tagged, key)));
2400 : }
2401 :
2402 168 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::EntryMask(
2403 : TNode<IntPtrT> capacity) {
2404 336 : return IntPtrSub(capacity, IntPtrConstant(1));
2405 : }
2406 :
2407 224 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndex(
2408 : TNode<HeapObject> table, TNode<IntPtrT> key_hash, TNode<IntPtrT> entry_mask,
2409 : const KeyComparator& key_compare) {
2410 : // See HashTable::FirstProbe().
2411 224 : TVARIABLE(IntPtrT, var_entry, WordAnd(key_hash, entry_mask));
2412 224 : TVARIABLE(IntPtrT, var_count, IntPtrConstant(0));
2413 :
2414 224 : Variable* loop_vars[] = {&var_count, &var_entry};
2415 448 : Label loop(this, arraysize(loop_vars), loop_vars), if_found(this);
2416 224 : Goto(&loop);
2417 224 : BIND(&loop);
2418 : TNode<IntPtrT> key_index;
2419 : {
2420 224 : key_index = KeyIndexFromEntry(var_entry.value());
2421 : TNode<Object> entry_key =
2422 : UnsafeLoadFixedArrayElement(CAST(table), key_index);
2423 :
2424 : key_compare(entry_key, &if_found);
2425 :
2426 : // See HashTable::NextProbe().
2427 224 : Increment(&var_count);
2428 : var_entry =
2429 : WordAnd(IntPtrAdd(var_entry.value(), var_count.value()), entry_mask);
2430 224 : Goto(&loop);
2431 : }
2432 :
2433 224 : BIND(&if_found);
2434 448 : return key_index;
2435 : }
2436 :
2437 56 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForInsertion(
2438 : TNode<HeapObject> table, TNode<IntPtrT> key_hash,
2439 : TNode<IntPtrT> entry_mask) {
2440 : // See HashTable::FindInsertionEntry().
2441 56 : auto is_not_live = [&](TNode<Object> entry_key, Label* if_found) {
2442 : // This is the the negative form BaseShape::IsLive().
2443 224 : GotoIf(Word32Or(IsTheHole(entry_key), IsUndefined(entry_key)), if_found);
2444 56 : };
2445 112 : return FindKeyIndex(table, key_hash, entry_mask, is_not_live);
2446 : }
2447 :
2448 168 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForKey(
2449 : TNode<HeapObject> table, TNode<Object> key, TNode<IntPtrT> hash,
2450 : TNode<IntPtrT> entry_mask, Label* if_not_found) {
2451 : // See HashTable::FindEntry().
2452 : auto match_key_or_exit_on_empty = [&](TNode<Object> entry_key,
2453 168 : Label* if_same) {
2454 840 : GotoIf(IsUndefined(entry_key), if_not_found);
2455 504 : GotoIf(WordEqual(entry_key, key), if_same);
2456 168 : };
2457 336 : return FindKeyIndex(table, hash, entry_mask, match_key_or_exit_on_empty);
2458 : }
2459 :
2460 448 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::KeyIndexFromEntry(
2461 : TNode<IntPtrT> entry) {
2462 : // See HashTable::KeyAt().
2463 : // (entry * kEntrySize) + kElementsStartIndex + kEntryKeyIndex
2464 : return IntPtrAdd(
2465 : IntPtrMul(entry, IntPtrConstant(EphemeronHashTable::kEntrySize)),
2466 : IntPtrConstant(EphemeronHashTable::kElementsStartIndex +
2467 896 : EphemeronHashTable::kEntryKeyIndex));
2468 : }
2469 :
2470 112 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfElements(
2471 : TNode<EphemeronHashTable> table, int offset) {
2472 224 : TNode<IntPtrT> number_of_elements = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
2473 112 : table, EphemeronHashTable::kNumberOfElementsIndex)));
2474 224 : return IntPtrAdd(number_of_elements, IntPtrConstant(offset));
2475 : }
2476 :
2477 112 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfDeleted(
2478 : TNode<EphemeronHashTable> table, int offset) {
2479 224 : TNode<IntPtrT> number_of_deleted = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
2480 112 : table, EphemeronHashTable::kNumberOfDeletedElementsIndex)));
2481 224 : return IntPtrAdd(number_of_deleted, IntPtrConstant(offset));
2482 : }
2483 :
2484 0 : TNode<EphemeronHashTable> WeakCollectionsBuiltinsAssembler::LoadTable(
2485 : TNode<JSWeakCollection> collection) {
2486 280 : return CAST(LoadObjectField(collection, JSWeakCollection::kTableOffset));
2487 : }
2488 :
2489 168 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadTableCapacity(
2490 : TNode<EphemeronHashTable> table) {
2491 336 : return SmiUntag(CAST(
2492 336 : UnsafeLoadFixedArrayElement(table, EphemeronHashTable::kCapacityIndex)));
2493 : }
2494 :
2495 56 : TNode<Word32T> WeakCollectionsBuiltinsAssembler::InsufficientCapacityToAdd(
2496 : TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements,
2497 : TNode<IntPtrT> number_of_deleted) {
2498 : // This is the negative form of HashTable::HasSufficientCapacityToAdd().
2499 : // Return true if:
2500 : // - more than 50% of the available space are deleted elements
2501 : // - less than 50% will be available
2502 56 : TNode<IntPtrT> available = IntPtrSub(capacity, number_of_elements);
2503 : TNode<IntPtrT> half_available = WordShr(available, 1);
2504 : TNode<IntPtrT> needed_available = WordShr(number_of_elements, 1);
2505 : return Word32Or(
2506 : // deleted > half
2507 112 : IntPtrGreaterThan(number_of_deleted, half_available),
2508 : // elements + needed available > capacity
2509 112 : IntPtrGreaterThan(IntPtrAdd(number_of_elements, needed_available),
2510 168 : capacity));
2511 : }
2512 :
2513 56 : void WeakCollectionsBuiltinsAssembler::RemoveEntry(
2514 : TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2515 : TNode<IntPtrT> number_of_elements) {
2516 : // See EphemeronHashTable::RemoveEntry().
2517 56 : TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
2518 112 : StoreFixedArrayElement(table, key_index, TheHoleConstant());
2519 112 : StoreFixedArrayElement(table, value_index, TheHoleConstant());
2520 :
2521 : // See HashTableBase::ElementRemoved().
2522 56 : TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table, 1);
2523 56 : StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2524 56 : SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2525 56 : StoreFixedArrayElement(table,
2526 : EphemeronHashTable::kNumberOfDeletedElementsIndex,
2527 56 : SmiFromIntPtr(number_of_deleted), SKIP_WRITE_BARRIER);
2528 56 : }
2529 :
2530 56 : TNode<BoolT> WeakCollectionsBuiltinsAssembler::ShouldRehash(
2531 : TNode<IntPtrT> number_of_elements, TNode<IntPtrT> number_of_deleted) {
2532 : // Rehash if more than 33% of the entries are deleted.
2533 112 : return IntPtrGreaterThanOrEqual(WordShl(number_of_deleted, 1),
2534 112 : number_of_elements);
2535 : }
2536 :
2537 56 : TNode<Word32T> WeakCollectionsBuiltinsAssembler::ShouldShrink(
2538 : TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements) {
2539 : // See HashTable::Shrink().
2540 56 : TNode<IntPtrT> quarter_capacity = WordShr(capacity, 2);
2541 : return Word32And(
2542 : // Shrink to fit the number of elements if only a quarter of the
2543 : // capacity is filled with elements.
2544 112 : IntPtrLessThanOrEqual(number_of_elements, quarter_capacity),
2545 :
2546 : // Allocate a new dictionary with room for at least the current
2547 : // number of elements. The allocation method will make sure that
2548 : // there is extra room in the dictionary for additions. Don't go
2549 : // lower than room for 16 elements.
2550 224 : IntPtrGreaterThanOrEqual(number_of_elements, IntPtrConstant(16)));
2551 : }
2552 :
2553 224 : TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::ValueIndexFromKeyIndex(
2554 : TNode<IntPtrT> key_index) {
2555 : return IntPtrAdd(key_index,
2556 : IntPtrConstant(EphemeronHashTableShape::kEntryValueIndex -
2557 448 : EphemeronHashTable::kEntryKeyIndex));
2558 : }
2559 :
2560 336 : TF_BUILTIN(WeakMapConstructor, WeakCollectionsBuiltinsAssembler) {
2561 56 : TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2562 : TNode<IntPtrT> argc =
2563 56 : ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
2564 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2565 :
2566 112 : GenerateConstructor(kWeakMap, isolate()->factory()->WeakMap_string(),
2567 56 : new_target, argc, context);
2568 56 : }
2569 :
2570 336 : TF_BUILTIN(WeakSetConstructor, WeakCollectionsBuiltinsAssembler) {
2571 56 : TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2572 : TNode<IntPtrT> argc =
2573 56 : ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
2574 56 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2575 :
2576 112 : GenerateConstructor(kWeakSet, isolate()->factory()->WeakSet_string(),
2577 56 : new_target, argc, context);
2578 56 : }
2579 :
2580 224 : TF_BUILTIN(WeakMapLookupHashIndex, WeakCollectionsBuiltinsAssembler) {
2581 : TNode<EphemeronHashTable> table = CAST(Parameter(Descriptor::kTable));
2582 : TNode<Object> key = CAST(Parameter(Descriptor::kKey));
2583 :
2584 56 : Label if_not_found(this);
2585 :
2586 56 : GotoIfNotJSReceiver(key, &if_not_found);
2587 :
2588 56 : TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
2589 56 : TNode<IntPtrT> capacity = LoadTableCapacity(table);
2590 : TNode<IntPtrT> key_index =
2591 112 : FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
2592 168 : Return(SmiTag(ValueIndexFromKeyIndex(key_index)));
2593 :
2594 56 : BIND(&if_not_found);
2595 112 : Return(SmiConstant(-1));
2596 56 : }
2597 :
2598 224 : TF_BUILTIN(WeakMapGet, WeakCollectionsBuiltinsAssembler) {
2599 : Node* const receiver = Parameter(Descriptor::kReceiver);
2600 : Node* const key = Parameter(Descriptor::kKey);
2601 : Node* const context = Parameter(Descriptor::kContext);
2602 :
2603 56 : Label return_undefined(this);
2604 :
2605 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
2606 56 : "WeakMap.prototype.get");
2607 :
2608 : TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
2609 : TNode<Smi> const index =
2610 56 : CAST(CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key));
2611 :
2612 112 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_undefined);
2613 :
2614 112 : Return(LoadFixedArrayElement(table, SmiUntag(index)));
2615 :
2616 56 : BIND(&return_undefined);
2617 112 : Return(UndefinedConstant());
2618 56 : }
2619 :
2620 224 : TF_BUILTIN(WeakMapPrototypeHas, WeakCollectionsBuiltinsAssembler) {
2621 : Node* const receiver = Parameter(Descriptor::kReceiver);
2622 : Node* const key = Parameter(Descriptor::kKey);
2623 : Node* const context = Parameter(Descriptor::kContext);
2624 :
2625 56 : Label return_false(this);
2626 :
2627 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
2628 56 : "WeakMap.prototype.has");
2629 :
2630 56 : TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
2631 : Node* const index =
2632 112 : CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);
2633 :
2634 112 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);
2635 :
2636 112 : Return(TrueConstant());
2637 :
2638 56 : BIND(&return_false);
2639 112 : Return(FalseConstant());
2640 56 : }
2641 :
2642 : // Helper that removes the entry with a given key from the backing store
2643 : // (EphemeronHashTable) of a WeakMap or WeakSet.
2644 224 : TF_BUILTIN(WeakCollectionDelete, WeakCollectionsBuiltinsAssembler) {
2645 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2646 : TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
2647 : TNode<Object> key = CAST(Parameter(Descriptor::kKey));
2648 :
2649 56 : Label call_runtime(this), if_not_found(this);
2650 :
2651 56 : GotoIfNotJSReceiver(key, &if_not_found);
2652 :
2653 56 : TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
2654 : TNode<EphemeronHashTable> table = LoadTable(collection);
2655 56 : TNode<IntPtrT> capacity = LoadTableCapacity(table);
2656 : TNode<IntPtrT> key_index =
2657 112 : FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
2658 56 : TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, -1);
2659 112 : GotoIf(ShouldShrink(capacity, number_of_elements), &call_runtime);
2660 :
2661 56 : RemoveEntry(table, key_index, number_of_elements);
2662 112 : Return(TrueConstant());
2663 :
2664 56 : BIND(&if_not_found);
2665 112 : Return(FalseConstant());
2666 :
2667 56 : BIND(&call_runtime);
2668 56 : Return(CallRuntime(Runtime::kWeakCollectionDelete, context, collection, key,
2669 168 : SmiTag(hash)));
2670 56 : }
2671 :
2672 : // Helper that sets the key and value to the backing store (EphemeronHashTable)
2673 : // of a WeakMap or WeakSet.
2674 224 : TF_BUILTIN(WeakCollectionSet, WeakCollectionsBuiltinsAssembler) {
2675 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2676 : TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
2677 : TNode<JSReceiver> key = CAST(Parameter(Descriptor::kKey));
2678 : TNode<Object> value = CAST(Parameter(Descriptor::kValue));
2679 :
2680 : CSA_ASSERT(this, IsJSReceiver(key));
2681 :
2682 56 : Label call_runtime(this), if_no_hash(this), if_not_found(this);
2683 :
2684 : TNode<EphemeronHashTable> table = LoadTable(collection);
2685 56 : TNode<IntPtrT> capacity = LoadTableCapacity(table);
2686 56 : TNode<IntPtrT> entry_mask = EntryMask(capacity);
2687 :
2688 112 : TVARIABLE(IntPtrT, var_hash, LoadJSReceiverIdentityHash(key, &if_no_hash));
2689 : TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, var_hash.value(),
2690 56 : entry_mask, &if_not_found);
2691 :
2692 112 : StoreFixedArrayElement(table, ValueIndexFromKeyIndex(key_index), value);
2693 56 : Return(collection);
2694 :
2695 56 : BIND(&if_no_hash);
2696 : {
2697 168 : var_hash = SmiUntag(CreateIdentityHash(key));
2698 56 : Goto(&if_not_found);
2699 : }
2700 56 : BIND(&if_not_found);
2701 : {
2702 56 : TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table);
2703 56 : TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, 1);
2704 :
2705 : // TODO(pwong): Port HashTable's Rehash() and EnsureCapacity() to CSA.
2706 224 : GotoIf(Word32Or(ShouldRehash(number_of_elements, number_of_deleted),
2707 112 : InsufficientCapacityToAdd(capacity, number_of_elements,
2708 112 : number_of_deleted)),
2709 56 : &call_runtime);
2710 :
2711 : TNode<IntPtrT> insertion_key_index =
2712 56 : FindKeyIndexForInsertion(table, var_hash.value(), entry_mask);
2713 56 : AddEntry(table, insertion_key_index, key, value, number_of_elements);
2714 56 : Return(collection);
2715 : }
2716 56 : BIND(&call_runtime);
2717 : {
2718 : CallRuntime(Runtime::kWeakCollectionSet, context, collection, key, value,
2719 112 : SmiTag(var_hash.value()));
2720 56 : Return(collection);
2721 : }
2722 56 : }
2723 :
2724 168 : TF_BUILTIN(WeakMapPrototypeDelete, CodeStubAssembler) {
2725 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2726 : TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
2727 56 : TNode<Object> key = CAST(Parameter(Descriptor::kKey));
2728 :
2729 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
2730 56 : "WeakMap.prototype.delete");
2731 :
2732 112 : Return(CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, key));
2733 56 : }
2734 :
2735 224 : TF_BUILTIN(WeakMapPrototypeSet, WeakCollectionsBuiltinsAssembler) {
2736 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2737 : TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
2738 : TNode<Object> key = CAST(Parameter(Descriptor::kKey));
2739 56 : TNode<Object> value = CAST(Parameter(Descriptor::kValue));
2740 :
2741 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
2742 56 : "WeakMap.prototype.set");
2743 :
2744 56 : Label throw_invalid_key(this);
2745 56 : GotoIfNotJSReceiver(key, &throw_invalid_key);
2746 :
2747 56 : Return(
2748 168 : CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, key, value));
2749 :
2750 56 : BIND(&throw_invalid_key);
2751 56 : ThrowTypeError(context, MessageTemplate::kInvalidWeakMapKey, key);
2752 56 : }
2753 :
2754 224 : TF_BUILTIN(WeakSetPrototypeAdd, WeakCollectionsBuiltinsAssembler) {
2755 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2756 : TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
2757 : TNode<Object> value = CAST(Parameter(Descriptor::kValue));
2758 :
2759 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
2760 56 : "WeakSet.prototype.add");
2761 :
2762 56 : Label throw_invalid_value(this);
2763 56 : GotoIfNotJSReceiver(value, &throw_invalid_value);
2764 :
2765 112 : Return(CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, value,
2766 168 : TrueConstant()));
2767 :
2768 56 : BIND(&throw_invalid_value);
2769 56 : ThrowTypeError(context, MessageTemplate::kInvalidWeakSetValue, value);
2770 56 : }
2771 :
2772 168 : TF_BUILTIN(WeakSetPrototypeDelete, CodeStubAssembler) {
2773 : TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2774 : TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
2775 56 : TNode<Object> value = CAST(Parameter(Descriptor::kValue));
2776 :
2777 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
2778 56 : "WeakSet.prototype.delete");
2779 :
2780 56 : Return(
2781 168 : CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, value));
2782 56 : }
2783 :
2784 224 : TF_BUILTIN(WeakSetPrototypeHas, WeakCollectionsBuiltinsAssembler) {
2785 : Node* const receiver = Parameter(Descriptor::kReceiver);
2786 : Node* const key = Parameter(Descriptor::kKey);
2787 : Node* const context = Parameter(Descriptor::kContext);
2788 :
2789 56 : Label return_false(this);
2790 :
2791 56 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
2792 56 : "WeakSet.prototype.has");
2793 :
2794 : Node* const table = LoadTable(CAST(receiver));
2795 : Node* const index =
2796 112 : CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);
2797 :
2798 112 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);
2799 :
2800 112 : Return(TrueConstant());
2801 :
2802 56 : BIND(&return_false);
2803 112 : Return(FalseConstant());
2804 56 : }
2805 :
2806 : } // namespace internal
2807 59456 : } // namespace v8
|
