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