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
19namespace v8 {
20namespace internal {
21
22template <class T>
23using TVariable = compiler::TypedCodeAssemblerVariable<T>;
24
25void 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
47void 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
111void 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
183void 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
223RootIndex 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
235void 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
270TNode<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
283TNode<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
291TNode<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
298void 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
320TNode<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
340TNode<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
360TNode<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
380int 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
394TNode<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
403void 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
423TNode<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
443TNode<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
452TNode<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
459TNode<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
478class CollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
479 public:
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
646template <typename CollectionType>
647void 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
715template <typename IteratorType>
716TNode<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
737TNode<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
746TF_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
756TF_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
766TNode<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
783TNode<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
800TNode<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
822void 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
846void 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
856void CollectionsBuiltinsAssembler::
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
896void 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
905void 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
915void 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
963void 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
972TNode<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
1057TF_BUILTIN(MapIteratorToList, CollectionsBuiltinsAssembler) {
1058  auto context = Parameter<Context>(Descriptor::kContext);
1059  auto iterator = Parameter<JSMapIterator>(Descriptor::kSource);
1060  Return(MapIteratorToList(context, iterator));
1061}
1062
1063TNode<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(&copy);
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(&copy);
1089  }
1090
1091  BIND(&copy);
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
1145TF_BUILTIN(SetOrSetIteratorToList, CollectionsBuiltinsAssembler) {
1146  auto context = Parameter<Context>(Descriptor::kContext);
1147  auto object = Parameter<HeapObject>(Descriptor::kSource);
1148  Return(SetOrSetIteratorToList(context, object));
1149}
1150
1151TNode<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
1165template <typename CollectionType>
1166void 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
1182template <typename CollectionType>
1183void 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
1197template <typename CollectionType>
1198void 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
1213template <typename CollectionType>
1214void 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
1228template <typename CollectionType>
1229void 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
1243TNode<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
1261void 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
1274void 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
1286void 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
1319TF_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
1363template <typename TableType>
1364std::pair<TNode<TableType>, TNode<IntPtrT>>
1365CollectionsBuiltinsAssembler::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
1405template <typename IteratorType, typename TableType>
1406std::pair<TNode<TableType>, TNode<IntPtrT>>
1407CollectionsBuiltinsAssembler::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
1421template <typename TableType>
1422std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>
1423CollectionsBuiltinsAssembler::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
1459TF_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
1485TF_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
1508const 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
1526TF_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, &not_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(&not_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
1606void 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
1644TF_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, &not_found);
1660
1661  BIND(&not_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
1703TF_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, &not_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(&not_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
1778void 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
1812TF_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, &not_found);
1828
1829  BIND(&not_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
1867TF_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
1876TF_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
1886TF_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
1948TF_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
1956TF_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
1965TF_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
2042TF_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, &not_found);
2067
2068  BIND(&if_key_smi);
2069  {
2070    FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
2071        CAST(table), CAST(key), &entry_start_position, &entry_found,
2072        &not_found);
2073  }
2074
2075  BIND(&if_key_string);
2076  {
2077    FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
2078        CAST(table), CAST(key), &entry_start_position, &entry_found,
2079        &not_found);
2080  }
2081
2082  BIND(&if_key_heap_number);
2083  {
2084    FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
2085        CAST(table), CAST(key), &entry_start_position, &entry_found,
2086        &not_found);
2087  }
2088
2089  BIND(&if_key_bigint);
2090  {
2091    FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
2092        CAST(table), CAST(key), &entry_start_position, &entry_found,
2093        &not_found);
2094  }
2095
2096  BIND(&entry_found);
2097  Return(TrueConstant());
2098
2099  BIND(&not_found);
2100  Return(FalseConstant());
2101}
2102
2103TF_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
2112TF_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
2122TF_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
2177TF_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
2186TF_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
2256template <typename CollectionType>
2257void 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
2300TF_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, &not_found);
2309
2310  BIND(&entry_found);
2311  Return(SmiTag(entry_start_position.value()));
2312
2313  BIND(&not_found);
2314  Return(SmiConstant(-1));
2315}
2316
2317void 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
2332TNode<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
2351TNode<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
2380TNode<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
2395TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::EntryMask(
2396    TNode<IntPtrT> capacity) {
2397  return IntPtrSub(capacity, IntPtrConstant(1));
2398}
2399
2400TNode<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
2429TNode<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
2440TNode<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
2452TNode<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
2462TNode<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
2469TNode<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
2476TNode<EphemeronHashTable> WeakCollectionsBuiltinsAssembler::LoadTable(
2477    TNode<JSWeakCollection> collection) {
2478  return CAST(LoadObjectField(collection, JSWeakCollection::kTableOffset));
2479}
2480
2481TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadTableCapacity(
2482    TNode<EphemeronHashTable> table) {
2483  return SmiUntag(CAST(
2484      UnsafeLoadFixedArrayElement(table, EphemeronHashTable::kCapacityIndex)));
2485}
2486
2487TNode<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
2505void 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
2522TNode<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
2529TNode<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
2545TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::ValueIndexFromKeyIndex(
2546    TNode<IntPtrT> key_index) {
2547  return IntPtrAdd(key_index,
2548                   IntPtrConstant(EphemeronHashTable::ShapeT::kEntryValueIndex -
2549                                  EphemeronHashTable::kEntryKeyIndex));
2550}
2551
2552TF_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
2562TF_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
2572TF_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
2590TF_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
2612TF_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.
2636TF_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.
2666TF_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
2717TF_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
2728TF_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
2747TF_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
2765TF_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
2776TF_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