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