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-constructor-gen.h"
6 : #include "src/builtins/builtins-iterator-gen.h"
7 : #include "src/builtins/builtins-utils-gen.h"
8 : #include "src/code-stub-assembler.h"
9 : #include "src/factory-inl.h"
10 : #include "src/objects/hash-table.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 : using compiler::Node;
16 :
17 : class CollectionsBuiltinsAssembler : public CodeStubAssembler {
18 : public:
19 : explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
20 806 : : CodeStubAssembler(state) {}
21 :
22 : protected:
23 : Node* AllocateJSMap(Node* js_map_function);
24 :
25 : template <typename CollectionType>
26 : Node* AllocateOrderedHashTable();
27 : Node* AllocateJSCollection(Node* js_map_function);
28 : template <typename IteratorType>
29 : Node* AllocateJSCollectionIterator(Node* context, int map_index,
30 : Node* collection);
31 :
32 : Node* GetHash(Node* const key);
33 : Node* CallGetHashRaw(Node* const key);
34 : Node* CallGetOrCreateHashRaw(Node* const key);
35 :
36 : // Transitions the iterator to the non obsolete backing store.
37 : // This is a NOP if the [table] is not obsolete.
38 : typedef std::function<void(Node* const table, Node* const index)>
39 : UpdateInTransition;
40 : template <typename TableType>
41 : std::tuple<Node*, Node*> Transition(
42 : Node* const table, Node* const index,
43 : UpdateInTransition const& update_in_transition);
44 : template <typename IteratorType, typename TableType>
45 : std::tuple<Node*, Node*> TransitionAndUpdate(Node* const iterator);
46 : template <typename TableType>
47 : std::tuple<Node*, Node*, Node*> NextSkipHoles(Node* table, Node* index,
48 : Label* if_end);
49 :
50 : // Builds code that finds OrderedHashTable entry for a key with hash code
51 : // {hash} with using the comparison code generated by {key_compare}. The code
52 : // jumps to {entry_found} if the key is found, or to {not_found} if the key
53 : // was not found. In the {entry_found} branch, the variable
54 : // entry_start_position will be bound to the index of the entry (relative to
55 : // OrderedHashTable::kHashTableStartIndex).
56 : //
57 : // The {CollectionType} template parameter stands for the particular instance
58 : // of OrderedHashTable, it should be OrderedHashMap or OrderedHashSet.
59 : template <typename CollectionType>
60 : void FindOrderedHashTableEntry(
61 : Node* table, Node* hash,
62 : std::function<void(Node* other, Label* if_same, Label* if_not_same)>
63 : key_compare,
64 : Variable* entry_start_position, Label* entry_found, Label* not_found);
65 :
66 : // Specialization for Smi.
67 : // The {result} variable will contain the entry index if the key was found,
68 : // or the hash code otherwise.
69 : template <typename CollectionType>
70 : void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
71 : Variable* result, Label* entry_found,
72 : Label* not_found);
73 : void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
74 : Label* if_not_same);
75 :
76 : // Specialization for heap numbers.
77 : // The {result} variable will contain the entry index if the key was found,
78 : // or the hash code otherwise.
79 : void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
80 : Label* if_same, Label* if_not_same);
81 : template <typename CollectionType>
82 : void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
83 : Node* key_heap_number,
84 : Variable* result,
85 : Label* entry_found,
86 : Label* not_found);
87 :
88 : // Specialization for bigints.
89 : // The {result} variable will contain the entry index if the key was found,
90 : // or the hash code otherwise.
91 : void SameValueZeroBigInt(Node* key, Node* candidate_key, Label* if_same,
92 : Label* if_not_same);
93 : template <typename CollectionType>
94 : void FindOrderedHashTableEntryForBigIntKey(Node* context, Node* table,
95 : Node* key, Variable* result,
96 : Label* entry_found,
97 : Label* not_found);
98 :
99 : // Specialization for string.
100 : // The {result} variable will contain the entry index if the key was found,
101 : // or the hash code otherwise.
102 : template <typename CollectionType>
103 : void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
104 : Node* key_tagged, Variable* result,
105 : Label* entry_found,
106 : Label* not_found);
107 : Node* ComputeIntegerHashForString(Node* context, Node* string_key);
108 : void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
109 : Label* if_same, Label* if_not_same);
110 :
111 : // Specialization for non-strings, non-numbers. For those we only need
112 : // reference equality to compare the keys.
113 : // The {result} variable will contain the entry index if the key was found,
114 : // or the hash code otherwise. If the hash-code has not been computed, it
115 : // should be Smi -1.
116 : template <typename CollectionType>
117 : void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
118 : Node* key, Variable* result,
119 : Label* entry_found,
120 : Label* not_found);
121 :
122 : template <typename CollectionType>
123 : void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
124 : Node* const context, Variable* result,
125 : Label* if_entry_found,
126 : Label* if_not_found);
127 :
128 : Node* NormalizeNumberKey(Node* key);
129 : void StoreOrderedHashMapNewEntry(Node* const table, Node* const key,
130 : Node* const value, Node* const hash,
131 : Node* const number_of_buckets,
132 : Node* const occupancy);
133 : void StoreOrderedHashSetNewEntry(Node* const table, Node* const key,
134 : Node* const hash,
135 : Node* const number_of_buckets,
136 : Node* const occupancy);
137 : };
138 :
139 : template <typename CollectionType>
140 62 : Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() {
141 : static const int kCapacity = CollectionType::kMinCapacity;
142 : static const int kBucketCount = kCapacity / CollectionType::kLoadFactor;
143 : static const int kDataTableLength = kCapacity * CollectionType::kEntrySize;
144 : static const int kFixedArrayLength =
145 : CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength;
146 : static const int kDataTableStartIndex =
147 : CollectionType::kHashTableStartIndex + kBucketCount;
148 :
149 : STATIC_ASSERT(base::bits::IsPowerOfTwo(kCapacity));
150 : STATIC_ASSERT(kCapacity <= CollectionType::kMaxCapacity);
151 :
152 : // Allocate the table and add the proper map.
153 : const ElementsKind elements_kind = HOLEY_ELEMENTS;
154 124 : Node* const length_intptr = IntPtrConstant(kFixedArrayLength);
155 62 : Node* const table = AllocateFixedArray(elements_kind, length_intptr);
156 : CSA_ASSERT(this,
157 : IntPtrLessThanOrEqual(
158 : length_intptr, IntPtrConstant(FixedArray::kMaxRegularLength)));
159 : Heap::RootListIndex map_index = Heap::kOrderedHashTableMapRootIndex;
160 : // TODO(gsathya): Directly store correct in AllocateFixedArray,
161 : // instead of overwriting here.
162 62 : StoreMapNoWriteBarrier(table, map_index);
163 :
164 : // Initialize the OrderedHashTable fields.
165 : const WriteBarrierMode barrier_mode = SKIP_WRITE_BARRIER;
166 124 : StoreFixedArrayElement(table, CollectionType::kNumberOfElementsIndex,
167 : SmiConstant(0), barrier_mode);
168 124 : StoreFixedArrayElement(table, CollectionType::kNumberOfDeletedElementsIndex,
169 : SmiConstant(0), barrier_mode);
170 124 : StoreFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex,
171 : SmiConstant(kBucketCount), barrier_mode);
172 :
173 : // Fill the buckets with kNotFound.
174 124 : Node* const not_found = SmiConstant(CollectionType::kNotFound);
175 : STATIC_ASSERT(CollectionType::kHashTableStartIndex ==
176 : CollectionType::kNumberOfBucketsIndex + 1);
177 : STATIC_ASSERT((CollectionType::kHashTableStartIndex + kBucketCount) ==
178 : kDataTableStartIndex);
179 186 : for (int i = 0; i < kBucketCount; i++) {
180 124 : StoreFixedArrayElement(table, CollectionType::kHashTableStartIndex + i,
181 : not_found, barrier_mode);
182 : }
183 :
184 : // Fill the data table with undefined.
185 : STATIC_ASSERT(kDataTableStartIndex + kDataTableLength == kFixedArrayLength);
186 620 : for (int i = 0; i < kDataTableLength; i++) {
187 620 : StoreFixedArrayElement(table, kDataTableStartIndex + i, UndefinedConstant(),
188 1860 : barrier_mode);
189 : }
190 :
191 62 : return table;
192 : }
193 :
194 62 : Node* CollectionsBuiltinsAssembler::AllocateJSCollection(
195 : Node* js_map_function) {
196 : CSA_ASSERT(this, IsConstructorMap(LoadMap(js_map_function)));
197 : Node* const initial_map = LoadObjectField(
198 62 : js_map_function, JSFunction::kPrototypeOrInitialMapOffset);
199 62 : Node* const instance = AllocateJSObjectFromMap(initial_map);
200 :
201 : StoreObjectFieldRoot(instance, JSMap::kTableOffset,
202 62 : Heap::kUndefinedValueRootIndex);
203 :
204 62 : return instance;
205 : }
206 :
207 : template <typename IteratorType>
208 155 : Node* CollectionsBuiltinsAssembler::AllocateJSCollectionIterator(
209 : Node* context, int map_index, Node* collection) {
210 155 : Node* const table = LoadObjectField(collection, JSCollection::kTableOffset);
211 310 : Node* const native_context = LoadNativeContext(context);
212 310 : Node* const iterator_map = LoadContextElement(native_context, map_index);
213 155 : Node* const iterator = AllocateInNewSpace(IteratorType::kSize);
214 155 : StoreMapNoWriteBarrier(iterator, iterator_map);
215 155 : StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
216 : Heap::kEmptyFixedArrayRootIndex);
217 155 : StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
218 : Heap::kEmptyFixedArrayRootIndex);
219 155 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
220 310 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
221 155 : SmiConstant(0));
222 155 : return iterator;
223 : }
224 :
225 155 : TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler) {
226 : const int kIterableArg = 0;
227 :
228 : Node* argc =
229 62 : ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
230 31 : CodeStubArguments args(this, argc);
231 :
232 62 : Node* const iterable = args.GetOptionalArgumentValue(kIterableArg);
233 : Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget);
234 : Node* const context = Parameter(BuiltinDescriptor::kContext);
235 :
236 : Label if_target_is_undefined(this, Label::kDeferred);
237 62 : GotoIf(IsUndefined(new_target), &if_target_is_undefined);
238 :
239 62 : Node* const native_context = LoadNativeContext(context);
240 : Node* const js_map_fun =
241 62 : LoadContextElement(native_context, Context::JS_MAP_FUN_INDEX);
242 :
243 62 : VARIABLE(var_result, MachineRepresentation::kTagged);
244 :
245 31 : Label init(this), exit(this), if_targetisnotmodified(this),
246 31 : if_targetismodified(this);
247 31 : Branch(WordEqual(js_map_fun, new_target), &if_targetisnotmodified,
248 62 : &if_targetismodified);
249 :
250 31 : BIND(&if_targetisnotmodified);
251 : {
252 31 : Node* const instance = AllocateJSCollection(js_map_fun);
253 31 : var_result.Bind(instance);
254 31 : Goto(&init);
255 : }
256 :
257 31 : BIND(&if_targetismodified);
258 : {
259 : ConstructorBuiltinsAssembler constructor_assembler(this->state());
260 : Node* const instance = constructor_assembler.EmitFastNewObject(
261 31 : context, js_map_fun, new_target);
262 31 : var_result.Bind(instance);
263 31 : Goto(&init);
264 : }
265 :
266 31 : BIND(&init);
267 31 : Node* table = AllocateOrderedHashTable<OrderedHashMap>();
268 31 : StoreObjectField(var_result.value(), JSMap::kTableOffset, table);
269 :
270 124 : GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit);
271 :
272 31 : Label if_notcallable(this);
273 : // TODO(gsathya): Add fast path for unmodified maps.
274 : Node* const adder = GetProperty(context, var_result.value(),
275 62 : isolate()->factory()->set_string());
276 62 : GotoIf(TaggedIsSmi(adder), &if_notcallable);
277 62 : GotoIfNot(IsCallable(adder), &if_notcallable);
278 :
279 : IteratorBuiltinsAssembler iterator_assembler(this->state());
280 31 : Node* const iterator = iterator_assembler.GetIterator(context, iterable);
281 62 : GotoIf(IsUndefined(iterator), &exit);
282 :
283 : Node* const fast_iterator_result_map =
284 62 : LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);
285 :
286 93 : VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant());
287 :
288 31 : Label loop(this), if_notobject(this), if_exception(this);
289 31 : Goto(&loop);
290 :
291 31 : BIND(&loop);
292 : {
293 : Node* const next = iterator_assembler.IteratorStep(
294 31 : context, iterator, &exit, fast_iterator_result_map);
295 :
296 : Node* const next_value = iterator_assembler.IteratorValue(
297 31 : context, next, fast_iterator_result_map);
298 :
299 62 : GotoIf(TaggedIsSmi(next_value), &if_notobject);
300 62 : GotoIfNot(IsJSReceiver(next_value), &if_notobject);
301 :
302 : Node* const k =
303 62 : GetProperty(context, next_value, isolate()->factory()->zero_string());
304 31 : GotoIfException(k, &if_exception, &var_exception);
305 :
306 : Node* const v =
307 62 : GetProperty(context, next_value, isolate()->factory()->one_string());
308 31 : GotoIfException(v, &if_exception, &var_exception);
309 :
310 : Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder,
311 62 : var_result.value(), k, v);
312 31 : GotoIfException(add_call, &if_exception, &var_exception);
313 31 : Goto(&loop);
314 :
315 31 : BIND(&if_notobject);
316 : {
317 : Node* const exception = MakeTypeError(
318 31 : MessageTemplate::kIteratorValueNotAnObject, context, next_value);
319 31 : var_exception.Bind(exception);
320 31 : Goto(&if_exception);
321 : }
322 : }
323 :
324 31 : BIND(&if_exception);
325 : {
326 : iterator_assembler.IteratorCloseOnException(context, iterator,
327 31 : &var_exception);
328 : }
329 :
330 31 : BIND(&if_notcallable);
331 : {
332 31 : Node* const receiver_str = HeapConstant(isolate()->factory()->add_string());
333 : ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder,
334 31 : receiver_str, var_result.value());
335 : }
336 :
337 31 : BIND(&if_target_is_undefined);
338 : ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
339 62 : HeapConstant(isolate()->factory()->Map_string()));
340 :
341 31 : BIND(&exit);
342 62 : args.PopAndReturn(var_result.value());
343 31 : }
344 :
345 155 : TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) {
346 : const int kIterableArg = 0;
347 :
348 : Node* argc =
349 62 : ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount));
350 31 : CodeStubArguments args(this, argc);
351 :
352 62 : Node* const iterable = args.GetOptionalArgumentValue(kIterableArg);
353 : Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget);
354 : Node* const context = Parameter(BuiltinDescriptor::kContext);
355 :
356 : Label if_target_is_undefined(this, Label::kDeferred);
357 62 : GotoIf(IsUndefined(new_target), &if_target_is_undefined);
358 :
359 62 : Node* const native_context = LoadNativeContext(context);
360 : Node* const js_set_fun =
361 62 : LoadContextElement(native_context, Context::JS_SET_FUN_INDEX);
362 :
363 62 : VARIABLE(var_result, MachineRepresentation::kTagged);
364 :
365 31 : Label init(this), exit(this), if_targetisnotmodified(this),
366 31 : if_targetismodified(this);
367 31 : Branch(WordEqual(js_set_fun, new_target), &if_targetisnotmodified,
368 62 : &if_targetismodified);
369 :
370 31 : BIND(&if_targetisnotmodified);
371 : {
372 31 : Node* const instance = AllocateJSCollection(js_set_fun);
373 31 : var_result.Bind(instance);
374 31 : Goto(&init);
375 : }
376 :
377 31 : BIND(&if_targetismodified);
378 : {
379 : ConstructorBuiltinsAssembler constructor_assembler(this->state());
380 : Node* const instance = constructor_assembler.EmitFastNewObject(
381 31 : context, js_set_fun, new_target);
382 31 : var_result.Bind(instance);
383 31 : Goto(&init);
384 : }
385 :
386 31 : BIND(&init);
387 31 : Node* table = AllocateOrderedHashTable<OrderedHashSet>();
388 31 : StoreObjectField(var_result.value(), JSSet::kTableOffset, table);
389 :
390 124 : GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit);
391 :
392 31 : Label if_notcallable(this);
393 : // TODO(gsathya): Add fast path for unmodified maps.
394 : Node* const adder = GetProperty(context, var_result.value(),
395 62 : isolate()->factory()->add_string());
396 62 : GotoIf(TaggedIsSmi(adder), &if_notcallable);
397 62 : GotoIfNot(IsCallable(adder), &if_notcallable);
398 :
399 : IteratorBuiltinsAssembler iterator_assembler(this->state());
400 31 : Node* const iterator = iterator_assembler.GetIterator(context, iterable);
401 62 : GotoIf(IsUndefined(iterator), &exit);
402 :
403 : Node* const fast_iterator_result_map =
404 62 : LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);
405 :
406 93 : VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant());
407 :
408 31 : Label loop(this), if_notobject(this), if_exception(this);
409 31 : Goto(&loop);
410 :
411 31 : BIND(&loop);
412 : {
413 : Node* const next = iterator_assembler.IteratorStep(
414 31 : context, iterator, &exit, fast_iterator_result_map);
415 :
416 : Node* const next_value = iterator_assembler.IteratorValue(
417 31 : context, next, fast_iterator_result_map);
418 :
419 : Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder,
420 62 : var_result.value(), next_value);
421 :
422 31 : GotoIfException(add_call, &if_exception, &var_exception);
423 31 : Goto(&loop);
424 : }
425 :
426 31 : BIND(&if_exception);
427 : {
428 : iterator_assembler.IteratorCloseOnException(context, iterator,
429 31 : &var_exception);
430 : }
431 :
432 31 : BIND(&if_notcallable);
433 : ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder,
434 31 : HeapConstant(isolate()->factory()->add_string()),
435 62 : var_result.value());
436 :
437 31 : BIND(&if_target_is_undefined);
438 : ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
439 62 : HeapConstant(isolate()->factory()->Set_string()));
440 :
441 31 : BIND(&exit);
442 62 : args.PopAndReturn(var_result.value());
443 31 : }
444 :
445 62 : Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key) {
446 : Node* const function_addr =
447 124 : ExternalConstant(ExternalReference::get_or_create_hash_raw(isolate()));
448 : Node* const isolate_ptr =
449 124 : ExternalConstant(ExternalReference::isolate_address(isolate()));
450 :
451 62 : MachineType type_ptr = MachineType::Pointer();
452 62 : MachineType type_tagged = MachineType::AnyTagged();
453 :
454 : Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
455 62 : function_addr, isolate_ptr, key);
456 :
457 62 : return result;
458 : }
459 :
460 775 : Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) {
461 : Node* const function_addr = ExternalConstant(
462 1550 : ExternalReference::orderedhashmap_gethash_raw(isolate()));
463 : Node* const isolate_ptr =
464 1550 : ExternalConstant(ExternalReference::isolate_address(isolate()));
465 :
466 775 : MachineType type_ptr = MachineType::Pointer();
467 775 : MachineType type_tagged = MachineType::AnyTagged();
468 :
469 : Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
470 775 : function_addr, isolate_ptr, key);
471 1550 : return SmiUntag(result);
472 : }
473 :
474 217 : Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) {
475 217 : VARIABLE(var_result, MachineType::PointerRepresentation());
476 217 : Label if_jsobject(this), other(this), done(this);
477 651 : Node* instance_type = LoadMapInstanceType(LoadMap(key));
478 434 : Branch(IsJSObjectInstanceType(instance_type), &if_jsobject, &other);
479 :
480 217 : BIND(&if_jsobject);
481 : {
482 434 : Node* hash = LoadHashForJSObject(key, instance_type);
483 : // TODO(gsathya): Change all uses of -1 to PropertyArray::kNoHashSentinel.
484 : var_result.Bind(SelectConstant(
485 : Word32Equal(hash, Int32Constant(PropertyArray::kNoHashSentinel)),
486 : IntPtrConstant(-1), ChangeInt32ToIntPtr(hash),
487 651 : MachineType::PointerRepresentation()));
488 217 : Goto(&done);
489 : }
490 :
491 217 : BIND(&other);
492 : {
493 217 : var_result.Bind(CallGetHashRaw(key));
494 217 : Goto(&done);
495 : }
496 :
497 217 : BIND(&done);
498 434 : return var_result.value();
499 : }
500 :
501 186 : void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
502 : Node* candidate_key,
503 : Label* if_same,
504 : Label* if_not_same) {
505 : // If the key is the same, we are done.
506 372 : GotoIf(WordEqual(candidate_key, key_smi), if_same);
507 :
508 : // If the candidate key is smi, then it must be different (because
509 : // we already checked for equality above).
510 372 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
511 :
512 : // If the candidate key is not smi, we still have to check if it is a
513 : // heap number with the same value.
514 372 : GotoIfNot(IsHeapNumber(candidate_key), if_not_same);
515 :
516 372 : Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
517 372 : Node* const key_number = SmiToFloat64(key_smi);
518 :
519 372 : GotoIf(Float64Equal(candidate_key_number, key_number), if_same);
520 :
521 186 : Goto(if_not_same);
522 186 : }
523 :
524 : template <typename CollectionType>
525 186 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
526 : Node* table, Node* smi_key, Variable* result, Label* entry_found,
527 : Label* not_found) {
528 558 : Node* const key_untagged = SmiUntag(smi_key);
529 : Node* const hash =
530 744 : ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0)));
531 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
532 186 : result->Bind(hash);
533 186 : FindOrderedHashTableEntry<CollectionType>(
534 : table, hash,
535 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
536 186 : SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
537 : },
538 186 : result, entry_found, not_found);
539 186 : }
540 :
541 : template <typename CollectionType>
542 186 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
543 : Node* context, Node* table, Node* key_tagged, Variable* result,
544 : Label* entry_found, Label* not_found) {
545 186 : Node* const hash = ComputeIntegerHashForString(context, key_tagged);
546 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
547 186 : result->Bind(hash);
548 186 : FindOrderedHashTableEntry<CollectionType>(
549 : table, hash,
550 186 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
551 186 : SameValueZeroString(context, key_tagged, other_key, if_same,
552 186 : if_not_same);
553 186 : },
554 186 : result, entry_found, not_found);
555 186 : }
556 :
557 : template <typename CollectionType>
558 186 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
559 : Node* context, Node* table, Node* key_heap_number, Variable* result,
560 : Label* entry_found, Label* not_found) {
561 186 : Node* hash = CallGetHashRaw(key_heap_number);
562 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
563 186 : result->Bind(hash);
564 372 : Node* const key_float = LoadHeapNumberValue(key_heap_number);
565 186 : FindOrderedHashTableEntry<CollectionType>(
566 : table, hash,
567 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
568 186 : SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
569 : },
570 186 : result, entry_found, not_found);
571 186 : }
572 :
573 : template <typename CollectionType>
574 186 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForBigIntKey(
575 : Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
576 : Label* not_found) {
577 186 : Node* hash = CallGetHashRaw(key);
578 : CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
579 186 : result->Bind(hash);
580 186 : FindOrderedHashTableEntry<CollectionType>(
581 : table, hash,
582 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
583 186 : SameValueZeroBigInt(key, other_key, if_same, if_not_same);
584 : },
585 186 : result, entry_found, not_found);
586 186 : }
587 :
588 : template <typename CollectionType>
589 186 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
590 : Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
591 : Label* not_found) {
592 186 : Node* hash = GetHash(key);
593 186 : result->Bind(hash);
594 186 : FindOrderedHashTableEntry<CollectionType>(
595 : table, hash,
596 186 : [&](Node* other_key, Label* if_same, Label* if_not_same) {
597 558 : Branch(WordEqual(key, other_key), if_same, if_not_same);
598 186 : },
599 186 : result, entry_found, not_found);
600 186 : }
601 :
602 186 : Node* CollectionsBuiltinsAssembler::ComputeIntegerHashForString(
603 : Node* context, Node* string_key) {
604 186 : VARIABLE(var_result, MachineType::PointerRepresentation());
605 :
606 186 : Label hash_not_computed(this), done(this, &var_result);
607 : Node* hash =
608 558 : ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
609 186 : var_result.Bind(hash);
610 186 : Goto(&done);
611 :
612 186 : BIND(&hash_not_computed);
613 186 : var_result.Bind(CallGetHashRaw(string_key));
614 186 : Goto(&done);
615 :
616 186 : BIND(&done);
617 372 : return var_result.value();
618 : }
619 :
620 186 : void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
621 : Node* key_string,
622 : Node* candidate_key,
623 : Label* if_same,
624 : Label* if_not_same) {
625 : // If the candidate is not a string, the keys are not equal.
626 372 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
627 372 : GotoIfNot(IsString(candidate_key), if_not_same);
628 :
629 : Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
630 : candidate_key),
631 558 : TrueConstant()),
632 186 : if_same, if_not_same);
633 186 : }
634 :
635 186 : void CollectionsBuiltinsAssembler::SameValueZeroBigInt(Node* key,
636 : Node* candidate_key,
637 : Label* if_same,
638 : Label* if_not_same) {
639 : CSA_ASSERT(this, IsBigInt(key));
640 372 : GotoIf(TaggedIsSmi(candidate_key), if_not_same);
641 372 : GotoIfNot(IsBigInt(candidate_key), if_not_same);
642 :
643 : Branch(WordEqual(CallRuntime(Runtime::kBigIntEqual, NoContextConstant(), key,
644 : candidate_key),
645 186 : TrueConstant()),
646 186 : if_same, if_not_same);
647 186 : }
648 :
649 186 : void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float,
650 : Node* candidate_key,
651 : Label* if_same,
652 : Label* if_not_same) {
653 372 : Label if_smi(this), if_keyisnan(this);
654 :
655 372 : GotoIf(TaggedIsSmi(candidate_key), &if_smi);
656 372 : GotoIfNot(IsHeapNumber(candidate_key), if_not_same);
657 :
658 : {
659 : // {candidate_key} is a heap number.
660 372 : Node* const candidate_float = LoadHeapNumberValue(candidate_key);
661 372 : GotoIf(Float64Equal(key_float, candidate_float), if_same);
662 :
663 : // SameValueZero needs to treat NaNs as equal. First check if {key_float}
664 : // is NaN.
665 186 : BranchIfFloat64IsNaN(key_float, &if_keyisnan, if_not_same);
666 :
667 186 : BIND(&if_keyisnan);
668 : {
669 : // Return true iff {candidate_key} is NaN.
670 186 : Branch(Float64Equal(candidate_float, candidate_float), if_not_same,
671 372 : if_same);
672 : }
673 : }
674 :
675 186 : BIND(&if_smi);
676 : {
677 372 : Node* const candidate_float = SmiToFloat64(candidate_key);
678 372 : Branch(Float64Equal(key_float, candidate_float), if_same, if_not_same);
679 186 : }
680 186 : }
681 :
682 : template <typename CollectionType>
683 930 : void CollectionsBuiltinsAssembler::FindOrderedHashTableEntry(
684 : Node* table, Node* hash,
685 : std::function<void(Node*, Label*, Label*)> key_compare,
686 : Variable* entry_start_position, Label* entry_found, Label* not_found) {
687 : // Get the index of the bucket.
688 : Node* const number_of_buckets = SmiUntag(
689 2790 : LoadFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex));
690 : Node* const bucket =
691 3720 : WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
692 : Node* const first_entry = SmiUntag(LoadFixedArrayElement(
693 2790 : table, bucket, CollectionType::kHashTableStartIndex * kPointerSize));
694 :
695 : // Walk the bucket chain.
696 : Node* entry_start;
697 : Label if_key_found(this);
698 : {
699 930 : VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry);
700 2790 : Label loop(this, {&var_entry, entry_start_position}),
701 930 : continue_next_entry(this);
702 930 : Goto(&loop);
703 930 : BIND(&loop);
704 :
705 : // If the entry index is the not-found sentinel, we are done.
706 3720 : GotoIf(
707 : WordEqual(var_entry.value(), IntPtrConstant(CollectionType::kNotFound)),
708 : not_found);
709 :
710 : // Make sure the entry index is within range.
711 : CSA_ASSERT(
712 : this,
713 : UintPtrLessThan(
714 : var_entry.value(),
715 : SmiUntag(SmiAdd(
716 : LoadFixedArrayElement(table,
717 : CollectionType::kNumberOfElementsIndex),
718 : LoadFixedArrayElement(
719 : table, CollectionType::kNumberOfDeletedElementsIndex)))));
720 :
721 : // Compute the index of the entry relative to kHashTableStartIndex.
722 4650 : entry_start =
723 : IntPtrAdd(IntPtrMul(var_entry.value(),
724 : IntPtrConstant(CollectionType::kEntrySize)),
725 : number_of_buckets);
726 :
727 : // Load the key from the entry.
728 : Node* const candidate_key = LoadFixedArrayElement(
729 : table, entry_start,
730 930 : CollectionType::kHashTableStartIndex * kPointerSize);
731 :
732 930 : key_compare(candidate_key, &if_key_found, &continue_next_entry);
733 :
734 930 : BIND(&continue_next_entry);
735 : // Load the index of the next entry in the bucket chain.
736 2790 : var_entry.Bind(SmiUntag(LoadFixedArrayElement(
737 : table, entry_start,
738 : (CollectionType::kHashTableStartIndex + CollectionType::kChainOffset) *
739 : kPointerSize)));
740 :
741 1860 : Goto(&loop);
742 : }
743 :
744 930 : BIND(&if_key_found);
745 930 : entry_start_position->Bind(entry_start);
746 930 : Goto(entry_found);
747 930 : }
748 :
749 124 : TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) {
750 : Node* table = Parameter(Descriptor::kTable);
751 : Node* index = Parameter(Descriptor::kIndex);
752 : CSA_ASSERT(this, TaggedIsNotSmi(table));
753 : CSA_ASSERT(this, TaggedIsSmi(index));
754 31 : Label return_index(this), return_zero(this);
755 :
756 : // Check if we need to update the {index}.
757 93 : GotoIfNot(SmiLessThan(SmiConstant(0), index), &return_zero);
758 :
759 : // Check if the {table} was cleared.
760 : Node* number_of_deleted_elements = LoadAndUntagObjectField(
761 62 : table, OrderedHashTableBase::kNumberOfDeletedElementsOffset);
762 : GotoIf(WordEqual(number_of_deleted_elements,
763 62 : IntPtrConstant(OrderedHashTableBase::kClearedTableSentinel)),
764 62 : &return_zero);
765 :
766 93 : VARIABLE(var_i, MachineType::PointerRepresentation(), IntPtrConstant(0));
767 62 : VARIABLE(var_index, MachineRepresentation::kTagged, index);
768 93 : Label loop(this, {&var_i, &var_index});
769 31 : Goto(&loop);
770 31 : BIND(&loop);
771 : {
772 31 : Node* i = var_i.value();
773 62 : GotoIfNot(IntPtrLessThan(i, number_of_deleted_elements), &return_index);
774 : Node* removed_index = LoadFixedArrayElement(
775 31 : table, i, OrderedHashTableBase::kRemovedHolesIndex * kPointerSize);
776 62 : GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
777 : Decrement(&var_index, 1, SMI_PARAMETERS);
778 31 : Increment(&var_i);
779 31 : Goto(&loop);
780 : }
781 :
782 31 : BIND(&return_index);
783 62 : Return(var_index.value());
784 :
785 31 : BIND(&return_zero);
786 93 : Return(SmiConstant(0));
787 31 : }
788 :
789 : template <typename TableType>
790 124 : std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::Transition(
791 : Node* const table, Node* const index,
792 : UpdateInTransition const& update_in_transition) {
793 124 : VARIABLE(var_index, MachineType::PointerRepresentation(), index);
794 248 : VARIABLE(var_table, MachineRepresentation::kTagged, table);
795 124 : Label if_done(this), if_transition(this, Label::kDeferred);
796 372 : Branch(TaggedIsSmi(
797 : LoadObjectField(var_table.value(), TableType::kNextTableOffset)),
798 : &if_done, &if_transition);
799 :
800 124 : BIND(&if_transition);
801 : {
802 372 : Label loop(this, {&var_table, &var_index}), done_loop(this);
803 124 : Goto(&loop);
804 124 : BIND(&loop);
805 : {
806 124 : Node* table = var_table.value();
807 124 : Node* index = var_index.value();
808 :
809 : Node* next_table = LoadObjectField(table, TableType::kNextTableOffset);
810 248 : GotoIf(TaggedIsSmi(next_table), &done_loop);
811 :
812 124 : var_table.Bind(next_table);
813 124 : var_index.Bind(
814 : SmiUntag(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
815 372 : NoContextConstant(), table, SmiTag(index))));
816 124 : Goto(&loop);
817 : }
818 124 : BIND(&done_loop);
819 :
820 : // Update with the new {table} and {index}.
821 124 : update_in_transition(var_table.value(), var_index.value());
822 248 : Goto(&if_done);
823 : }
824 :
825 124 : BIND(&if_done);
826 248 : return std::tuple<Node*, Node*>(var_table.value(), var_index.value());
827 : }
828 :
829 : template <typename IteratorType, typename TableType>
830 62 : std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::TransitionAndUpdate(
831 : Node* const iterator) {
832 : return Transition<TableType>(
833 : LoadObjectField(iterator, IteratorType::kTableOffset),
834 : LoadAndUntagObjectField(iterator, IteratorType::kIndexOffset),
835 62 : [this, iterator](Node* const table, Node* const index) {
836 : // Update the {iterator} with the new state.
837 62 : StoreObjectField(iterator, IteratorType::kTableOffset, table);
838 124 : StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
839 124 : SmiTag(index));
840 248 : });
841 : }
842 :
843 : template <typename TableType>
844 124 : std::tuple<Node*, Node*, Node*> CollectionsBuiltinsAssembler::NextSkipHoles(
845 : Node* table, Node* index, Label* if_end) {
846 : // Compute the used capacity for the {table}.
847 : Node* number_of_buckets =
848 248 : LoadAndUntagObjectField(table, TableType::kNumberOfBucketsOffset);
849 : Node* number_of_elements =
850 248 : LoadAndUntagObjectField(table, TableType::kNumberOfElementsOffset);
851 : Node* number_of_deleted_elements =
852 248 : LoadAndUntagObjectField(table, TableType::kNumberOfDeletedElementsOffset);
853 : Node* used_capacity =
854 248 : IntPtrAdd(number_of_elements, number_of_deleted_elements);
855 :
856 : Node* entry_key;
857 : Node* entry_start_position;
858 124 : VARIABLE(var_index, MachineType::PointerRepresentation(), index);
859 124 : Label loop(this, &var_index), done_loop(this);
860 124 : Goto(&loop);
861 124 : BIND(&loop);
862 : {
863 372 : GotoIfNot(IntPtrLessThan(var_index.value(), used_capacity), if_end);
864 620 : entry_start_position = IntPtrAdd(
865 : IntPtrMul(var_index.value(), IntPtrConstant(TableType::kEntrySize)),
866 : number_of_buckets);
867 124 : entry_key =
868 : LoadFixedArrayElement(table, entry_start_position,
869 : TableType::kHashTableStartIndex * kPointerSize);
870 124 : Increment(&var_index);
871 248 : Branch(IsTheHole(entry_key), &loop, &done_loop);
872 : }
873 :
874 124 : BIND(&done_loop);
875 : return std::tuple<Node*, Node*, Node*>(entry_key, entry_start_position,
876 248 : var_index.value());
877 : }
878 :
879 124 : TF_BUILTIN(MapPrototypeGet, CollectionsBuiltinsAssembler) {
880 : Node* const receiver = Parameter(Descriptor::kReceiver);
881 : Node* const key = Parameter(Descriptor::kKey);
882 : Node* const context = Parameter(Descriptor::kContext);
883 :
884 31 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");
885 :
886 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
887 : Node* index =
888 31 : CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key);
889 :
890 31 : Label if_found(this), if_not_found(this);
891 : Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
892 93 : &if_not_found);
893 :
894 31 : BIND(&if_found);
895 : Return(LoadFixedArrayElement(
896 31 : table, SmiUntag(index),
897 : (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
898 93 : kPointerSize));
899 :
900 31 : BIND(&if_not_found);
901 93 : Return(UndefinedConstant());
902 31 : }
903 :
904 124 : TF_BUILTIN(MapPrototypeHas, CollectionsBuiltinsAssembler) {
905 : Node* const receiver = Parameter(Descriptor::kReceiver);
906 : Node* const key = Parameter(Descriptor::kKey);
907 : Node* const context = Parameter(Descriptor::kContext);
908 :
909 31 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");
910 :
911 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
912 : Node* index =
913 31 : CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key);
914 :
915 31 : Label if_found(this), if_not_found(this);
916 : Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
917 93 : &if_not_found);
918 :
919 31 : BIND(&if_found);
920 62 : Return(TrueConstant());
921 :
922 31 : BIND(&if_not_found);
923 93 : Return(FalseConstant());
924 31 : }
925 :
926 62 : Node* CollectionsBuiltinsAssembler::NormalizeNumberKey(Node* const key) {
927 62 : VARIABLE(result, MachineRepresentation::kTagged, key);
928 62 : Label done(this);
929 :
930 124 : GotoIf(TaggedIsSmi(key), &done);
931 124 : GotoIfNot(IsHeapNumber(key), &done);
932 124 : Node* const number = LoadHeapNumberValue(key);
933 186 : GotoIfNot(Float64Equal(number, Float64Constant(0.0)), &done);
934 : // We know the value is zero, so we take the key to be Smi 0.
935 : // Another option would be to normalize to Smi here.
936 124 : result.Bind(SmiConstant(0));
937 62 : Goto(&done);
938 :
939 62 : BIND(&done);
940 124 : return result.value();
941 : }
942 :
943 124 : TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) {
944 : Node* const receiver = Parameter(Descriptor::kReceiver);
945 : Node* key = Parameter(Descriptor::kKey);
946 : Node* const value = Parameter(Descriptor::kValue);
947 : Node* const context = Parameter(Descriptor::kContext);
948 :
949 31 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set");
950 :
951 31 : key = NormalizeNumberKey(key);
952 :
953 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
954 :
955 62 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
956 : IntPtrConstant(0));
957 31 : Label entry_found(this), not_found(this);
958 :
959 : TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
960 : &entry_start_position_or_hash,
961 31 : &entry_found, ¬_found);
962 :
963 31 : BIND(&entry_found);
964 : // If we found the entry, we just store the value there.
965 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value,
966 : UPDATE_WRITE_BARRIER,
967 : kPointerSize * (OrderedHashMap::kHashTableStartIndex +
968 31 : OrderedHashMap::kValueOffset));
969 31 : Return(receiver);
970 :
971 31 : Label no_hash(this), add_entry(this), store_new_entry(this);
972 31 : BIND(¬_found);
973 : {
974 : // If we have a hash code, we can start adding the new entry.
975 : GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(),
976 93 : IntPtrConstant(0)),
977 62 : &add_entry);
978 :
979 : // Otherwise, go to runtime to compute the hash code.
980 93 : entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
981 31 : Goto(&add_entry);
982 : }
983 :
984 31 : BIND(&add_entry);
985 62 : VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
986 62 : VARIABLE(occupancy, MachineType::PointerRepresentation());
987 62 : VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
988 : {
989 : // Check we have enough space for the entry.
990 : number_of_buckets.Bind(SmiUntag(
991 93 : LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)));
992 :
993 : STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
994 93 : Node* const capacity = WordShl(number_of_buckets.value(), 1);
995 : Node* const number_of_elements = SmiUntag(
996 62 : CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)));
997 : Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
998 62 : table, OrderedHashMap::kNumberOfDeletedElementsOffset)));
999 62 : occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
1000 93 : GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);
1001 :
1002 : // We do not have enough space, grow the table and reload the relevant
1003 : // fields.
1004 : CallRuntime(Runtime::kMapGrow, context, receiver);
1005 31 : table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
1006 : number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement(
1007 93 : table_var.value(), OrderedHashMap::kNumberOfBucketsIndex)));
1008 31 : Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1009 62 : table_var.value(), OrderedHashMap::kNumberOfElementsOffset)));
1010 31 : Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1011 62 : table_var.value(), OrderedHashMap::kNumberOfDeletedElementsOffset)));
1012 62 : occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
1013 31 : Goto(&store_new_entry);
1014 : }
1015 31 : BIND(&store_new_entry);
1016 : // Store the key, value and connect the element to the bucket chain.
1017 : StoreOrderedHashMapNewEntry(table_var.value(), key, value,
1018 : entry_start_position_or_hash.value(),
1019 31 : number_of_buckets.value(), occupancy.value());
1020 62 : Return(receiver);
1021 31 : }
1022 :
1023 31 : void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(
1024 : Node* const table, Node* const key, Node* const value, Node* const hash,
1025 : Node* const number_of_buckets, Node* const occupancy) {
1026 : Node* const bucket =
1027 124 : WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1028 : Node* const bucket_entry = LoadFixedArrayElement(
1029 31 : table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize);
1030 :
1031 : // Store the entry elements.
1032 : Node* const entry_start = IntPtrAdd(
1033 62 : IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
1034 124 : number_of_buckets);
1035 : StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
1036 31 : kPointerSize * OrderedHashMap::kHashTableStartIndex);
1037 : StoreFixedArrayElement(table, entry_start, value, UPDATE_WRITE_BARRIER,
1038 : kPointerSize * (OrderedHashMap::kHashTableStartIndex +
1039 31 : OrderedHashMap::kValueOffset));
1040 : StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
1041 : kPointerSize * (OrderedHashMap::kHashTableStartIndex +
1042 31 : OrderedHashMap::kChainOffset));
1043 :
1044 : // Update the bucket head.
1045 31 : StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
1046 62 : OrderedHashMap::kHashTableStartIndex * kPointerSize);
1047 :
1048 : // Bump the elements count.
1049 : Node* const number_of_elements =
1050 : LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset);
1051 : StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
1052 93 : SmiAdd(number_of_elements, SmiConstant(1)));
1053 31 : }
1054 :
1055 124 : TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
1056 : Node* const receiver = Parameter(Descriptor::kReceiver);
1057 : Node* key = Parameter(Descriptor::kKey);
1058 : Node* const context = Parameter(Descriptor::kContext);
1059 :
1060 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1061 31 : "Map.prototype.delete");
1062 :
1063 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1064 :
1065 62 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1066 : IntPtrConstant(0));
1067 31 : Label entry_found(this), not_found(this);
1068 :
1069 : TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
1070 : &entry_start_position_or_hash,
1071 31 : &entry_found, ¬_found);
1072 :
1073 31 : BIND(¬_found);
1074 62 : Return(FalseConstant());
1075 :
1076 31 : BIND(&entry_found);
1077 : // If we found the entry, mark the entry as deleted.
1078 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1079 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1080 62 : kPointerSize * OrderedHashMap::kHashTableStartIndex);
1081 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1082 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1083 : kPointerSize * (OrderedHashMap::kHashTableStartIndex +
1084 62 : OrderedHashMap::kValueOffset));
1085 :
1086 : // Decrement the number of elements, increment the number of deleted elements.
1087 : Node* const number_of_elements = SmiSub(
1088 : CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)),
1089 93 : SmiConstant(1));
1090 : StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
1091 31 : number_of_elements);
1092 : Node* const number_of_deleted =
1093 : SmiAdd(CAST(LoadObjectField(
1094 : table, OrderedHashMap::kNumberOfDeletedElementsOffset)),
1095 93 : SmiConstant(1));
1096 : StoreObjectFieldNoWriteBarrier(
1097 31 : table, OrderedHashMap::kNumberOfDeletedElementsOffset, number_of_deleted);
1098 :
1099 : Node* const number_of_buckets =
1100 31 : LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex);
1101 :
1102 : // If there fewer elements than #buckets / 2, shrink the table.
1103 31 : Label shrink(this);
1104 31 : GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
1105 : number_of_buckets),
1106 93 : &shrink);
1107 62 : Return(TrueConstant());
1108 :
1109 31 : BIND(&shrink);
1110 : CallRuntime(Runtime::kMapShrink, context, receiver);
1111 93 : Return(TrueConstant());
1112 31 : }
1113 :
1114 124 : TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler) {
1115 : Node* const receiver = Parameter(Descriptor::kReceiver);
1116 : Node* key = Parameter(Descriptor::kKey);
1117 : Node* const context = Parameter(Descriptor::kContext);
1118 :
1119 31 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");
1120 :
1121 31 : key = NormalizeNumberKey(key);
1122 :
1123 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1124 :
1125 62 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1126 : IntPtrConstant(0));
1127 31 : Label entry_found(this), not_found(this);
1128 :
1129 : TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
1130 : &entry_start_position_or_hash,
1131 31 : &entry_found, ¬_found);
1132 :
1133 31 : BIND(&entry_found);
1134 : // The entry was found, there is nothing to do.
1135 31 : Return(receiver);
1136 :
1137 31 : Label no_hash(this), add_entry(this), store_new_entry(this);
1138 31 : BIND(¬_found);
1139 : {
1140 : // If we have a hash code, we can start adding the new entry.
1141 : GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(),
1142 93 : IntPtrConstant(0)),
1143 62 : &add_entry);
1144 :
1145 : // Otherwise, go to runtime to compute the hash code.
1146 93 : entry_start_position_or_hash.Bind(SmiUntag((CallGetOrCreateHashRaw(key))));
1147 31 : Goto(&add_entry);
1148 : }
1149 :
1150 31 : BIND(&add_entry);
1151 62 : VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
1152 62 : VARIABLE(occupancy, MachineType::PointerRepresentation());
1153 62 : VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
1154 : {
1155 : // Check we have enough space for the entry.
1156 : number_of_buckets.Bind(SmiUntag(
1157 93 : LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex)));
1158 :
1159 : STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
1160 93 : Node* const capacity = WordShl(number_of_buckets.value(), 1);
1161 : Node* const number_of_elements = SmiUntag(
1162 62 : CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)));
1163 : Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
1164 62 : table, OrderedHashSet::kNumberOfDeletedElementsOffset)));
1165 62 : occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
1166 93 : GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);
1167 :
1168 : // We do not have enough space, grow the table and reload the relevant
1169 : // fields.
1170 : CallRuntime(Runtime::kSetGrow, context, receiver);
1171 31 : table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
1172 : number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement(
1173 93 : table_var.value(), OrderedHashSet::kNumberOfBucketsIndex)));
1174 31 : Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1175 62 : table_var.value(), OrderedHashSet::kNumberOfElementsOffset)));
1176 31 : Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1177 62 : table_var.value(), OrderedHashSet::kNumberOfDeletedElementsOffset)));
1178 62 : occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
1179 31 : Goto(&store_new_entry);
1180 : }
1181 31 : BIND(&store_new_entry);
1182 : // Store the key, value and connect the element to the bucket chain.
1183 : StoreOrderedHashSetNewEntry(table_var.value(), key,
1184 : entry_start_position_or_hash.value(),
1185 31 : number_of_buckets.value(), occupancy.value());
1186 62 : Return(receiver);
1187 31 : }
1188 :
1189 31 : void CollectionsBuiltinsAssembler::StoreOrderedHashSetNewEntry(
1190 : Node* const table, Node* const key, Node* const hash,
1191 : Node* const number_of_buckets, Node* const occupancy) {
1192 : Node* const bucket =
1193 124 : WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1194 : Node* const bucket_entry = LoadFixedArrayElement(
1195 31 : table, bucket, OrderedHashSet::kHashTableStartIndex * kPointerSize);
1196 :
1197 : // Store the entry elements.
1198 : Node* const entry_start = IntPtrAdd(
1199 62 : IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
1200 124 : number_of_buckets);
1201 : StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
1202 31 : kPointerSize * OrderedHashSet::kHashTableStartIndex);
1203 : StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
1204 : kPointerSize * (OrderedHashSet::kHashTableStartIndex +
1205 31 : OrderedHashSet::kChainOffset));
1206 :
1207 : // Update the bucket head.
1208 31 : StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
1209 62 : OrderedHashSet::kHashTableStartIndex * kPointerSize);
1210 :
1211 : // Bump the elements count.
1212 : Node* const number_of_elements =
1213 : LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset);
1214 : StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
1215 93 : SmiAdd(number_of_elements, SmiConstant(1)));
1216 31 : }
1217 :
1218 124 : TF_BUILTIN(SetPrototypeDelete, CollectionsBuiltinsAssembler) {
1219 : Node* const receiver = Parameter(Descriptor::kReceiver);
1220 : Node* key = Parameter(Descriptor::kKey);
1221 : Node* const context = Parameter(Descriptor::kContext);
1222 :
1223 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
1224 31 : "Set.prototype.delete");
1225 :
1226 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1227 :
1228 62 : VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
1229 : IntPtrConstant(0));
1230 31 : Label entry_found(this), not_found(this);
1231 :
1232 : TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
1233 : &entry_start_position_or_hash,
1234 31 : &entry_found, ¬_found);
1235 :
1236 31 : BIND(¬_found);
1237 62 : Return(FalseConstant());
1238 :
1239 31 : BIND(&entry_found);
1240 : // If we found the entry, mark the entry as deleted.
1241 : StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
1242 : TheHoleConstant(), UPDATE_WRITE_BARRIER,
1243 62 : kPointerSize * OrderedHashSet::kHashTableStartIndex);
1244 :
1245 : // Decrement the number of elements, increment the number of deleted elements.
1246 : Node* const number_of_elements = SmiSub(
1247 : CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)),
1248 93 : SmiConstant(1));
1249 : StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
1250 31 : number_of_elements);
1251 : Node* const number_of_deleted =
1252 : SmiAdd(CAST(LoadObjectField(
1253 : table, OrderedHashSet::kNumberOfDeletedElementsOffset)),
1254 93 : SmiConstant(1));
1255 : StoreObjectFieldNoWriteBarrier(
1256 31 : table, OrderedHashSet::kNumberOfDeletedElementsOffset, number_of_deleted);
1257 :
1258 : Node* const number_of_buckets =
1259 31 : LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex);
1260 :
1261 : // If there fewer elements than #buckets / 2, shrink the table.
1262 31 : Label shrink(this);
1263 31 : GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
1264 : number_of_buckets),
1265 93 : &shrink);
1266 62 : Return(TrueConstant());
1267 :
1268 31 : BIND(&shrink);
1269 : CallRuntime(Runtime::kSetShrink, context, receiver);
1270 93 : Return(TrueConstant());
1271 31 : }
1272 :
1273 124 : TF_BUILTIN(MapPrototypeEntries, CollectionsBuiltinsAssembler) {
1274 : Node* const receiver = Parameter(Descriptor::kReceiver);
1275 : Node* const context = Parameter(Descriptor::kContext);
1276 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1277 31 : "Map.prototype.entries");
1278 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1279 62 : context, Context::MAP_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
1280 31 : }
1281 :
1282 124 : TF_BUILTIN(MapPrototypeGetSize, CollectionsBuiltinsAssembler) {
1283 : Node* const receiver = Parameter(Descriptor::kReceiver);
1284 : Node* const context = Parameter(Descriptor::kContext);
1285 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1286 31 : "get Map.prototype.size");
1287 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1288 31 : Return(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset));
1289 31 : }
1290 :
1291 124 : TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) {
1292 : const char* const kMethodName = "Map.prototype.forEach";
1293 : Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount);
1294 : Node* const context = Parameter(BuiltinDescriptor::kContext);
1295 93 : CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
1296 62 : Node* const receiver = args.GetReceiver();
1297 62 : Node* const callback = args.GetOptionalArgumentValue(0);
1298 62 : Node* const this_arg = args.GetOptionalArgumentValue(1);
1299 :
1300 31 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, kMethodName);
1301 :
1302 : // Ensure that {callback} is actually callable.
1303 : Label callback_not_callable(this, Label::kDeferred);
1304 62 : GotoIf(TaggedIsSmi(callback), &callback_not_callable);
1305 62 : GotoIfNot(IsCallable(callback), &callback_not_callable);
1306 :
1307 93 : VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
1308 62 : VARIABLE(var_table, MachineRepresentation::kTagged,
1309 : LoadObjectField(receiver, JSMap::kTableOffset));
1310 93 : Label loop(this, {&var_index, &var_table}), done_loop(this);
1311 31 : Goto(&loop);
1312 31 : BIND(&loop);
1313 : {
1314 : // Transition {table} and {index} if there was any modification to
1315 : // the {receiver} while we're iterating.
1316 31 : Node* index = var_index.value();
1317 31 : Node* table = var_table.value();
1318 93 : std::tie(table, index) =
1319 : Transition<OrderedHashMap>(table, index, [](Node*, Node*) {});
1320 :
1321 : // Read the next entry from the {table}, skipping holes.
1322 : Node* entry_key;
1323 : Node* entry_start_position;
1324 62 : std::tie(entry_key, entry_start_position, index) =
1325 : NextSkipHoles<OrderedHashMap>(table, index, &done_loop);
1326 :
1327 : // Load the entry value as well.
1328 : Node* entry_value = LoadFixedArrayElement(
1329 : table, entry_start_position,
1330 : (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
1331 31 : kPointerSize);
1332 :
1333 : // Invoke the {callback} passing the {entry_key}, {entry_value} and the
1334 : // {receiver}.
1335 : CallJS(CodeFactory::Call(isolate()), context, callback, this_arg,
1336 62 : entry_value, entry_key, receiver);
1337 :
1338 : // Continue with the next entry.
1339 31 : var_index.Bind(index);
1340 31 : var_table.Bind(table);
1341 31 : Goto(&loop);
1342 : }
1343 :
1344 31 : BIND(&done_loop);
1345 62 : args.PopAndReturn(UndefinedConstant());
1346 :
1347 31 : BIND(&callback_not_callable);
1348 : {
1349 : CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
1350 31 : Unreachable();
1351 31 : }
1352 31 : }
1353 :
1354 124 : TF_BUILTIN(MapPrototypeKeys, CollectionsBuiltinsAssembler) {
1355 : Node* const receiver = Parameter(Descriptor::kReceiver);
1356 : Node* const context = Parameter(Descriptor::kContext);
1357 31 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.keys");
1358 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1359 62 : context, Context::MAP_KEY_ITERATOR_MAP_INDEX, receiver));
1360 31 : }
1361 :
1362 124 : TF_BUILTIN(MapPrototypeValues, CollectionsBuiltinsAssembler) {
1363 : Node* const receiver = Parameter(Descriptor::kReceiver);
1364 : Node* const context = Parameter(Descriptor::kContext);
1365 : ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
1366 31 : "Map.prototype.values");
1367 : Return(AllocateJSCollectionIterator<JSMapIterator>(
1368 62 : context, Context::MAP_VALUE_ITERATOR_MAP_INDEX, receiver));
1369 31 : }
1370 :
1371 124 : TF_BUILTIN(MapIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
1372 : const char* const kMethodName = "Map Iterator.prototype.next";
1373 : Node* const receiver = Parameter(Descriptor::kReceiver);
1374 : Node* const context = Parameter(Descriptor::kContext);
1375 :
1376 : // Ensure that the {receiver} is actually a JSMapIterator.
1377 31 : Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
1378 62 : GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
1379 62 : Node* const receiver_instance_type = LoadInstanceType(receiver);
1380 : GotoIf(
1381 : InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_VALUE_ITERATOR_TYPE),
1382 62 : &if_receiver_valid);
1383 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
1384 62 : &if_receiver_valid);
1385 : Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
1386 62 : &if_receiver_valid, &if_receiver_invalid);
1387 31 : BIND(&if_receiver_invalid);
1388 31 : ThrowIncompatibleMethodReceiver(context, kMethodName, receiver);
1389 31 : BIND(&if_receiver_valid);
1390 :
1391 : // Check if the {receiver} is exhausted.
1392 93 : VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1393 93 : VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
1394 93 : Label return_value(this, {&var_done, &var_value}), return_entry(this),
1395 31 : return_end(this, Label::kDeferred);
1396 :
1397 : // Transition the {receiver} table if necessary.
1398 : Node* table;
1399 : Node* index;
1400 62 : std::tie(table, index) =
1401 : TransitionAndUpdate<JSMapIterator, OrderedHashMap>(receiver);
1402 :
1403 : // Read the next entry from the {table}, skipping holes.
1404 : Node* entry_key;
1405 : Node* entry_start_position;
1406 62 : std::tie(entry_key, entry_start_position, index) =
1407 : NextSkipHoles<OrderedHashMap>(table, index, &return_end);
1408 : StoreObjectFieldNoWriteBarrier(receiver, JSMapIterator::kIndexOffset,
1409 62 : SmiTag(index));
1410 31 : var_value.Bind(entry_key);
1411 62 : var_done.Bind(FalseConstant());
1412 :
1413 : // Check how to return the {key} (depending on {receiver} type).
1414 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
1415 62 : &return_value);
1416 : var_value.Bind(LoadFixedArrayElement(
1417 : table, entry_start_position,
1418 : (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
1419 31 : kPointerSize));
1420 : Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
1421 62 : &return_value, &return_entry);
1422 :
1423 31 : BIND(&return_entry);
1424 : {
1425 : Node* result =
1426 31 : AllocateJSIteratorResultForEntry(context, entry_key, var_value.value());
1427 31 : Return(result);
1428 : }
1429 :
1430 31 : BIND(&return_value);
1431 : {
1432 : Node* result =
1433 31 : AllocateJSIteratorResult(context, var_value.value(), var_done.value());
1434 31 : Return(result);
1435 : }
1436 :
1437 31 : BIND(&return_end);
1438 : {
1439 : StoreObjectFieldRoot(receiver, JSMapIterator::kTableOffset,
1440 31 : Heap::kEmptyOrderedHashTableRootIndex);
1441 31 : Goto(&return_value);
1442 31 : }
1443 31 : }
1444 :
1445 124 : TF_BUILTIN(SetPrototypeHas, CollectionsBuiltinsAssembler) {
1446 : Node* const receiver = Parameter(Descriptor::kReceiver);
1447 : Node* const key = Parameter(Descriptor::kKey);
1448 : Node* const context = Parameter(Descriptor::kContext);
1449 :
1450 31 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");
1451 :
1452 : Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1453 :
1454 62 : VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
1455 : IntPtrConstant(0));
1456 93 : VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0));
1457 31 : Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
1458 31 : if_key_bigint(this), entry_found(this), not_found(this), done(this);
1459 :
1460 62 : GotoIf(TaggedIsSmi(key), &if_key_smi);
1461 :
1462 62 : Node* key_map = LoadMap(key);
1463 62 : Node* key_instance_type = LoadMapInstanceType(key_map);
1464 :
1465 62 : GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
1466 62 : GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
1467 62 : GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
1468 :
1469 : FindOrderedHashTableEntryForOtherKey<OrderedHashSet>(
1470 31 : context, table, key, &entry_start_position, &entry_found, ¬_found);
1471 :
1472 31 : BIND(&if_key_smi);
1473 : {
1474 : FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
1475 31 : table, key, &entry_start_position, &entry_found, ¬_found);
1476 : }
1477 :
1478 31 : BIND(&if_key_string);
1479 : {
1480 : FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
1481 31 : context, table, key, &entry_start_position, &entry_found, ¬_found);
1482 : }
1483 :
1484 31 : BIND(&if_key_heap_number);
1485 : {
1486 : FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
1487 31 : context, table, key, &entry_start_position, &entry_found, ¬_found);
1488 : }
1489 :
1490 31 : BIND(&if_key_bigint);
1491 : {
1492 : FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
1493 31 : context, table, key, &entry_start_position, &entry_found, ¬_found);
1494 : }
1495 :
1496 31 : BIND(&entry_found);
1497 62 : Return(TrueConstant());
1498 :
1499 31 : BIND(¬_found);
1500 93 : Return(FalseConstant());
1501 31 : }
1502 :
1503 124 : TF_BUILTIN(SetPrototypeEntries, CollectionsBuiltinsAssembler) {
1504 : Node* const receiver = Parameter(Descriptor::kReceiver);
1505 : Node* const context = Parameter(Descriptor::kContext);
1506 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
1507 31 : "Set.prototype.entries");
1508 : Return(AllocateJSCollectionIterator<JSSetIterator>(
1509 62 : context, Context::SET_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
1510 31 : }
1511 :
1512 124 : TF_BUILTIN(SetPrototypeGetSize, CollectionsBuiltinsAssembler) {
1513 : Node* const receiver = Parameter(Descriptor::kReceiver);
1514 : Node* const context = Parameter(Descriptor::kContext);
1515 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
1516 31 : "get Set.prototype.size");
1517 : Node* const table = LoadObjectField(receiver, JSSet::kTableOffset);
1518 31 : Return(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset));
1519 31 : }
1520 :
1521 124 : TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) {
1522 : const char* const kMethodName = "Set.prototype.forEach";
1523 : Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount);
1524 : Node* const context = Parameter(BuiltinDescriptor::kContext);
1525 93 : CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
1526 62 : Node* const receiver = args.GetReceiver();
1527 62 : Node* const callback = args.GetOptionalArgumentValue(0);
1528 62 : Node* const this_arg = args.GetOptionalArgumentValue(1);
1529 :
1530 31 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, kMethodName);
1531 :
1532 : // Ensure that {callback} is actually callable.
1533 : Label callback_not_callable(this, Label::kDeferred);
1534 62 : GotoIf(TaggedIsSmi(callback), &callback_not_callable);
1535 62 : GotoIfNot(IsCallable(callback), &callback_not_callable);
1536 :
1537 93 : VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
1538 62 : VARIABLE(var_table, MachineRepresentation::kTagged,
1539 : LoadObjectField(receiver, JSSet::kTableOffset));
1540 93 : Label loop(this, {&var_index, &var_table}), done_loop(this);
1541 31 : Goto(&loop);
1542 31 : BIND(&loop);
1543 : {
1544 : // Transition {table} and {index} if there was any modification to
1545 : // the {receiver} while we're iterating.
1546 31 : Node* index = var_index.value();
1547 31 : Node* table = var_table.value();
1548 93 : std::tie(table, index) =
1549 : Transition<OrderedHashSet>(table, index, [](Node*, Node*) {});
1550 :
1551 : // Read the next entry from the {table}, skipping holes.
1552 : Node* entry_key;
1553 : Node* entry_start_position;
1554 62 : std::tie(entry_key, entry_start_position, index) =
1555 : NextSkipHoles<OrderedHashSet>(table, index, &done_loop);
1556 :
1557 : // Invoke the {callback} passing the {entry_key} (twice) and the {receiver}.
1558 : CallJS(CodeFactory::Call(isolate()), context, callback, this_arg, entry_key,
1559 62 : entry_key, receiver);
1560 :
1561 : // Continue with the next entry.
1562 31 : var_index.Bind(index);
1563 31 : var_table.Bind(table);
1564 31 : Goto(&loop);
1565 : }
1566 :
1567 31 : BIND(&done_loop);
1568 62 : args.PopAndReturn(UndefinedConstant());
1569 :
1570 31 : BIND(&callback_not_callable);
1571 : {
1572 : CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
1573 31 : Unreachable();
1574 31 : }
1575 31 : }
1576 :
1577 124 : TF_BUILTIN(SetPrototypeValues, CollectionsBuiltinsAssembler) {
1578 : Node* const receiver = Parameter(Descriptor::kReceiver);
1579 : Node* const context = Parameter(Descriptor::kContext);
1580 : ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
1581 31 : "Set.prototype.values");
1582 : Return(AllocateJSCollectionIterator<JSSetIterator>(
1583 62 : context, Context::SET_VALUE_ITERATOR_MAP_INDEX, receiver));
1584 31 : }
1585 :
1586 124 : TF_BUILTIN(SetIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
1587 : const char* const kMethodName = "Set Iterator.prototype.next";
1588 : Node* const receiver = Parameter(Descriptor::kReceiver);
1589 : Node* const context = Parameter(Descriptor::kContext);
1590 :
1591 : // Ensure that the {receiver} is actually a JSSetIterator.
1592 31 : Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
1593 62 : GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
1594 62 : Node* const receiver_instance_type = LoadInstanceType(receiver);
1595 : GotoIf(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
1596 62 : &if_receiver_valid);
1597 : Branch(
1598 : InstanceTypeEqual(receiver_instance_type, JS_SET_KEY_VALUE_ITERATOR_TYPE),
1599 62 : &if_receiver_valid, &if_receiver_invalid);
1600 31 : BIND(&if_receiver_invalid);
1601 31 : ThrowIncompatibleMethodReceiver(context, kMethodName, receiver);
1602 31 : BIND(&if_receiver_valid);
1603 :
1604 : // Check if the {receiver} is exhausted.
1605 93 : VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1606 93 : VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
1607 93 : Label return_value(this, {&var_done, &var_value}), return_entry(this),
1608 31 : return_end(this, Label::kDeferred);
1609 :
1610 : // Transition the {receiver} table if necessary.
1611 : Node* table;
1612 : Node* index;
1613 62 : std::tie(table, index) =
1614 : TransitionAndUpdate<JSSetIterator, OrderedHashSet>(receiver);
1615 :
1616 : // Read the next entry from the {table}, skipping holes.
1617 : Node* entry_key;
1618 : Node* entry_start_position;
1619 62 : std::tie(entry_key, entry_start_position, index) =
1620 : NextSkipHoles<OrderedHashSet>(table, index, &return_end);
1621 : StoreObjectFieldNoWriteBarrier(receiver, JSSetIterator::kIndexOffset,
1622 62 : SmiTag(index));
1623 31 : var_value.Bind(entry_key);
1624 62 : var_done.Bind(FalseConstant());
1625 :
1626 : // Check how to return the {key} (depending on {receiver} type).
1627 : Branch(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
1628 62 : &return_value, &return_entry);
1629 :
1630 31 : BIND(&return_entry);
1631 : {
1632 : Node* result = AllocateJSIteratorResultForEntry(context, var_value.value(),
1633 31 : var_value.value());
1634 31 : Return(result);
1635 : }
1636 :
1637 31 : BIND(&return_value);
1638 : {
1639 : Node* result =
1640 31 : AllocateJSIteratorResult(context, var_value.value(), var_done.value());
1641 31 : Return(result);
1642 : }
1643 :
1644 31 : BIND(&return_end);
1645 : {
1646 : StoreObjectFieldRoot(receiver, JSSetIterator::kTableOffset,
1647 31 : Heap::kEmptyOrderedHashTableRootIndex);
1648 31 : Goto(&return_value);
1649 31 : }
1650 31 : }
1651 :
1652 : template <typename CollectionType>
1653 155 : void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
1654 : Node* const table, Node* const key, Node* const context, Variable* result,
1655 : Label* if_entry_found, Label* if_not_found) {
1656 310 : Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
1657 155 : if_key_bigint(this);
1658 :
1659 310 : GotoIf(TaggedIsSmi(key), &if_key_smi);
1660 :
1661 310 : Node* key_map = LoadMap(key);
1662 310 : Node* key_instance_type = LoadMapInstanceType(key_map);
1663 :
1664 310 : GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
1665 310 : GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
1666 310 : GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
1667 :
1668 155 : FindOrderedHashTableEntryForOtherKey<CollectionType>(
1669 : context, table, key, result, if_entry_found, if_not_found);
1670 :
1671 155 : BIND(&if_key_smi);
1672 : {
1673 155 : FindOrderedHashTableEntryForSmiKey<CollectionType>(
1674 : table, key, result, if_entry_found, if_not_found);
1675 : }
1676 :
1677 155 : BIND(&if_key_string);
1678 : {
1679 155 : FindOrderedHashTableEntryForStringKey<CollectionType>(
1680 : context, table, key, result, if_entry_found, if_not_found);
1681 : }
1682 :
1683 155 : BIND(&if_key_heap_number);
1684 : {
1685 155 : FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
1686 : context, table, key, result, if_entry_found, if_not_found);
1687 : }
1688 :
1689 155 : BIND(&if_key_bigint);
1690 : {
1691 155 : FindOrderedHashTableEntryForBigIntKey<CollectionType>(
1692 : context, table, key, result, if_entry_found, if_not_found);
1693 155 : }
1694 155 : }
1695 :
1696 124 : TF_BUILTIN(FindOrderedHashMapEntry, CollectionsBuiltinsAssembler) {
1697 : Node* const table = Parameter(Descriptor::kTable);
1698 : Node* const key = Parameter(Descriptor::kKey);
1699 : Node* const context = Parameter(Descriptor::kContext);
1700 :
1701 62 : VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
1702 : IntPtrConstant(0));
1703 31 : Label entry_found(this), not_found(this);
1704 :
1705 : TryLookupOrderedHashTableIndex<OrderedHashMap>(
1706 31 : table, key, context, &entry_start_position, &entry_found, ¬_found);
1707 :
1708 31 : BIND(&entry_found);
1709 93 : Return(SmiTag(entry_start_position.value()));
1710 :
1711 31 : BIND(¬_found);
1712 93 : Return(SmiConstant(-1));
1713 31 : }
1714 :
1715 124 : TF_BUILTIN(WeakMapLookupHashIndex, CollectionsBuiltinsAssembler) {
1716 : Node* const table = Parameter(Descriptor::kTable);
1717 : Node* const key = Parameter(Descriptor::kKey);
1718 :
1719 31 : Label if_found(this), if_not_found(this);
1720 :
1721 : Node* const capacity =
1722 93 : SmiUntag(LoadFixedArrayElement(table, WeakHashTable::kCapacityIndex));
1723 93 : Node* const mask = IntPtrSub(capacity, IntPtrConstant(1));
1724 :
1725 31 : Node* const hash = GetHash(key);
1726 :
1727 93 : GotoIf(IntPtrLessThan(hash, IntPtrConstant(0)), &if_not_found);
1728 :
1729 : // See HashTable::FirstProbe().
1730 62 : Node* entry = WordAnd(hash, mask);
1731 :
1732 93 : VARIABLE(var_count, MachineType::PointerRepresentation(), IntPtrConstant(0));
1733 62 : VARIABLE(var_entry, MachineType::PointerRepresentation(), entry);
1734 31 : Variable* loop_vars[] = {&var_count, &var_entry};
1735 62 : Label loop(this, arraysize(loop_vars), loop_vars);
1736 31 : Goto(&loop);
1737 31 : BIND(&loop);
1738 : Node* index;
1739 : {
1740 31 : Node* entry = var_entry.value();
1741 :
1742 93 : index = IntPtrMul(entry, IntPtrConstant(WeakHashTable::kEntrySize));
1743 62 : index =
1744 62 : IntPtrAdd(index, IntPtrConstant(WeakHashTable::kElementsStartIndex));
1745 :
1746 31 : Node* current = LoadFixedArrayElement(table, index);
1747 62 : GotoIf(WordEqual(current, UndefinedConstant()), &if_not_found);
1748 62 : GotoIf(WordEqual(current, key), &if_found);
1749 :
1750 : // See HashTable::NextProbe().
1751 31 : Increment(&var_count);
1752 124 : entry = WordAnd(IntPtrAdd(entry, var_count.value()), mask);
1753 :
1754 31 : var_entry.Bind(entry);
1755 31 : Goto(&loop);
1756 : }
1757 :
1758 31 : BIND(&if_not_found);
1759 62 : Return(SmiConstant(-1));
1760 :
1761 31 : BIND(&if_found);
1762 155 : Return(SmiTag(Signed(IntPtrAdd(index, IntPtrConstant(1)))));
1763 31 : }
1764 :
1765 124 : TF_BUILTIN(WeakMapGet, CollectionsBuiltinsAssembler) {
1766 : Node* const receiver = Parameter(Descriptor::kReceiver);
1767 : Node* const key = Parameter(Descriptor::kKey);
1768 : Node* const context = Parameter(Descriptor::kContext);
1769 :
1770 : Label return_undefined(this);
1771 :
1772 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
1773 31 : "WeakMap.prototype.get");
1774 :
1775 62 : GotoIf(TaggedIsSmi(key), &return_undefined);
1776 62 : GotoIfNot(IsJSReceiver(key), &return_undefined);
1777 :
1778 : Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);
1779 :
1780 : Node* const index =
1781 31 : CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);
1782 :
1783 62 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_undefined);
1784 :
1785 93 : Return(LoadFixedArrayElement(table, SmiUntag(index)));
1786 :
1787 31 : BIND(&return_undefined);
1788 62 : Return(UndefinedConstant());
1789 31 : }
1790 :
1791 124 : TF_BUILTIN(WeakMapHas, CollectionsBuiltinsAssembler) {
1792 : Node* const receiver = Parameter(Descriptor::kReceiver);
1793 : Node* const key = Parameter(Descriptor::kKey);
1794 : Node* const context = Parameter(Descriptor::kContext);
1795 :
1796 : Label return_false(this);
1797 :
1798 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
1799 31 : "WeakMap.prototype.has");
1800 :
1801 62 : GotoIf(TaggedIsSmi(key), &return_false);
1802 62 : GotoIfNot(IsJSReceiver(key), &return_false);
1803 :
1804 : Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);
1805 :
1806 : Node* const index =
1807 31 : CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);
1808 :
1809 62 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);
1810 :
1811 62 : Return(TrueConstant());
1812 :
1813 31 : BIND(&return_false);
1814 62 : Return(FalseConstant());
1815 31 : }
1816 :
1817 124 : TF_BUILTIN(WeakSetHas, CollectionsBuiltinsAssembler) {
1818 : Node* const receiver = Parameter(Descriptor::kReceiver);
1819 : Node* const key = Parameter(Descriptor::kKey);
1820 : Node* const context = Parameter(Descriptor::kContext);
1821 :
1822 : Label return_false(this);
1823 :
1824 : ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
1825 31 : "WeakSet.prototype.has");
1826 :
1827 62 : GotoIf(TaggedIsSmi(key), &return_false);
1828 62 : GotoIfNot(IsJSReceiver(key), &return_false);
1829 :
1830 : Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset);
1831 :
1832 : Node* const index =
1833 31 : CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);
1834 :
1835 62 : GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);
1836 :
1837 62 : Return(TrueConstant());
1838 :
1839 31 : BIND(&return_false);
1840 62 : Return(FalseConstant());
1841 31 : }
1842 :
1843 : } // namespace internal
1844 : } // namespace v8
|
