builtins-collections-gen.cc 112 KB
Newer Older
1 2 3 4
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#include "src/builtins/builtins-collections-gen.h"

7 8 9
#include "src/builtins/builtins-constructor-gen.h"
#include "src/builtins/builtins-iterator-gen.h"
#include "src/builtins/builtins-utils-gen.h"
10
#include "src/codegen/code-stub-assembler.h"
11
#include "src/heap/factory-inl.h"
12
#include "src/heap/heap-inl.h"
13
#include "src/objects/hash-table-inl.h"
14
#include "src/objects/js-collection.h"
15
#include "src/objects/ordered-hash-table.h"
16 17
#include "torque-generated/builtins-base-gen-tq.h"
#include "torque-generated/builtins-collections-gen-tq.h"
18 19 20 21

namespace v8 {
namespace internal {

22 23 24
using compiler::Node;
template <class T>
using TNode = compiler::TNode<T>;
25 26
template <class T>
using TVariable = compiler::TypedCodeAssemblerVariable<T>;
27

28 29 30
class BaseCollectionsAssembler
    : public CodeStubAssembler,
      public TorqueGeneratedCollectionsBuiltinsAssembler {
31
 public:
32
  explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state)
33 34
      : CodeStubAssembler(state),
        TorqueGeneratedCollectionsBuiltinsAssembler(state) {}
35

36
  virtual ~BaseCollectionsAssembler() = default;
37

38
 protected:
39
  enum Variant { kMap, kSet, kWeakMap, kWeakSet };
40 41 42

  // Adds an entry to a collection.  For Maps, properly handles extracting the
  // key and value from the entry (see LoadKeyValue()).
43
  void AddConstructorEntry(Variant variant, TNode<Context> context,
44
                           TNode<Object> collection, TNode<Object> add_function,
45 46 47 48
                           TNode<Object> key_value,
                           Label* if_may_have_side_effects = nullptr,
                           Label* if_exception = nullptr,
                           TVariable<Object>* var_exception = nullptr);
49 50 51 52 53 54

  // Adds constructor entries to a collection.  Choosing a fast path when
  // possible.
  void AddConstructorEntries(Variant variant, TNode<Context> context,
                             TNode<Context> native_context,
                             TNode<Object> collection,
55
                             TNode<Object> initial_entries);
56 57 58 59 60

  // Fast path for adding constructor entries.  Assumes the entries are a fast
  // JS array (see CodeStubAssembler::BranchIfFastJSArray()).
  void AddConstructorEntriesFromFastJSArray(Variant variant,
                                            TNode<Context> context,
61
                                            TNode<Context> native_context,
62
                                            TNode<Object> collection,
63 64
                                            TNode<JSArray> fast_jsarray,
                                            Label* if_may_have_side_effects);
65 66 67 68 69 70 71 72 73 74

  // Adds constructor entries to a collection using the iterator protocol.
  void AddConstructorEntriesFromIterable(Variant variant,
                                         TNode<Context> context,
                                         TNode<Context> native_context,
                                         TNode<Object> collection,
                                         TNode<Object> iterable);

  // Constructs a collection instance. Choosing a fast path when possible.
  TNode<Object> AllocateJSCollection(TNode<Context> context,
75
                                     TNode<JSFunction> constructor,
76 77 78 79 80 81 82 83 84
                                     TNode<Object> new_target);

  // Fast path for constructing a collection instance if the constructor
  // function has not been modified.
  TNode<Object> AllocateJSCollectionFast(TNode<HeapObject> constructor);

  // Fallback for constructing a collection instance if the constructor function
  // has been modified.
  TNode<Object> AllocateJSCollectionSlow(TNode<Context> context,
85
                                         TNode<JSFunction> constructor,
86 87 88 89 90 91 92 93
                                         TNode<Object> new_target);

  // Allocates the backing store for a collection.
  virtual TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
                                      TNode<IntPtrT> at_least_space_for) = 0;

  // Main entry point for a collection constructor builtin.
  void GenerateConstructor(Variant variant,
94 95 96
                           Handle<String> constructor_function_name,
                           TNode<Object> new_target, TNode<IntPtrT> argc,
                           TNode<Context> context);
97 98 99

  // Retrieves the collection function that adds an entry. `set` for Maps and
  // `add` for Sets.
100 101
  TNode<Object> GetAddFunction(Variant variant, TNode<Context> context,
                               TNode<Object> collection);
102 103 104 105 106 107 108 109 110 111 112

  // Retrieves the collection constructor function.
  TNode<JSFunction> GetConstructor(Variant variant,
                                   TNode<Context> native_context);

  // Retrieves the initial collection function that adds an entry. Should only
  // be called when it is certain that a collection prototype's map hasn't been
  // changed.
  TNode<JSFunction> GetInitialAddFunction(Variant variant,
                                          TNode<Context> native_context);

113 114
  // Checks whether {collection}'s initial add/set function has been modified
  // (depending on {variant}, loaded from {native_context}).
115 116 117 118
  void GotoIfInitialAddFunctionModified(Variant variant,
                                        TNode<Context> native_context,
                                        TNode<Object> collection,
                                        Label* if_modified);
119 120

  // Gets root index for the name of the add/set function.
121
  RootIndex GetAddFunctionNameIndex(Variant variant);
122

123 124
  // Retrieves the offset to access the backing table from the collection.
  int GetTableOffset(Variant variant);
125 126 127 128 129 130 131 132 133

  // Estimates the number of entries the collection will have after adding the
  // entries passed in the constructor. AllocateTable() can use this to avoid
  // the time of growing/rehashing when adding the constructor entries.
  TNode<IntPtrT> EstimatedInitialSize(TNode<Object> initial_entries,
                                      TNode<BoolT> is_fast_jsarray);

  void GotoIfNotJSReceiver(Node* const obj, Label* if_not_receiver);

134 135 136 137 138
  // Determines whether the collection's prototype has been modified.
  TNode<BoolT> HasInitialCollectionPrototype(Variant variant,
                                             TNode<Context> native_context,
                                             TNode<Object> collection);

139 140 141 142
  // Gets the initial prototype map for given collection {variant}.
  TNode<Map> GetInitialCollectionPrototype(Variant variant,
                                           TNode<Context> native_context);

143 144
  // Loads an element from a fixed array.  If the element is the hole, returns
  // `undefined`.
145
  TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<FixedArray> elements,
146 147 148 149
                                                  TNode<IntPtrT> index);

  // Loads an element from a fixed double array.  If the element is the hole,
  // returns `undefined`.
150 151
  TNode<Object> LoadAndNormalizeFixedDoubleArrayElement(
      TNode<HeapObject> elements, TNode<IntPtrT> index);
152 153
};

154
void BaseCollectionsAssembler::AddConstructorEntry(
155
    Variant variant, TNode<Context> context, TNode<Object> collection,
156
    TNode<Object> add_function, TNode<Object> key_value,
157 158
    Label* if_may_have_side_effects, Label* if_exception,
    TVariable<Object>* var_exception) {
159 160
  compiler::CodeAssemblerScopedExceptionHandler handler(this, if_exception,
                                                        var_exception);
161
  CSA_ASSERT(this, Word32BinaryNot(IsTheHole(key_value)));
162
  if (variant == kMap || variant == kWeakMap) {
163
    TorqueGeneratedBaseBuiltinsAssembler::KeyValuePair pair =
164 165 166 167 168 169 170 171
        if_may_have_side_effects != nullptr
            ? LoadKeyValuePairNoSideEffects(context, key_value,
                                            if_may_have_side_effects)
            : LoadKeyValuePair(context, key_value);
    Node* key_n = pair.key;
    Node* value_n = pair.value;
    CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
           key_n, value_n);
172 173
  } else {
    DCHECK(variant == kSet || variant == kWeakSet);
174 175
    CallJS(CodeFactory::Call(isolate()), context, add_function, collection,
           key_value);
176 177 178 179 180
  }
}

void BaseCollectionsAssembler::AddConstructorEntries(
    Variant variant, TNode<Context> context, TNode<Context> native_context,
181 182
    TNode<Object> collection, TNode<Object> initial_entries) {
  TVARIABLE(BoolT, use_fast_loop,
183
            IsFastJSArrayWithNoCustomIteration(context, initial_entries));
184
  TNode<IntPtrT> at_least_space_for =
185
      EstimatedInitialSize(initial_entries, use_fast_loop.value());
186 187 188 189 190 191 192 193
  Label allocate_table(this, &use_fast_loop), exit(this), fast_loop(this),
      slow_loop(this, Label::kDeferred);
  Goto(&allocate_table);
  BIND(&allocate_table);
  {
    TNode<Object> table = AllocateTable(variant, context, at_least_space_for);
    StoreObjectField(collection, GetTableOffset(variant), table);
    GotoIf(IsNullOrUndefined(initial_entries), &exit);
194 195
    GotoIfInitialAddFunctionModified(variant, native_context, collection,
                                     &slow_loop);
196
    Branch(use_fast_loop.value(), &fast_loop, &slow_loop);
197 198 199
  }
  BIND(&fast_loop);
  {
200 201
    TNode<JSArray> initial_entries_jsarray =
        UncheckedCast<JSArray>(initial_entries);
202
#if DEBUG
203 204
    CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(
                         context, initial_entries_jsarray));
205
    TNode<Map> original_initial_entries_map = LoadMap(initial_entries_jsarray);
206 207 208
#endif

    Label if_may_have_side_effects(this, Label::kDeferred);
209 210 211
    AddConstructorEntriesFromFastJSArray(variant, context, native_context,
                                         collection, initial_entries_jsarray,
                                         &if_may_have_side_effects);
212
    Goto(&exit);
213

214 215 216
    if (variant == kMap || variant == kWeakMap) {
      BIND(&if_may_have_side_effects);
#if DEBUG
217 218 219
      {
        // Check that add/set function has not been modified.
        Label if_not_modified(this), if_modified(this);
220 221
        GotoIfInitialAddFunctionModified(variant, native_context, collection,
                                         &if_modified);
222 223 224 225 226
        Goto(&if_not_modified);
        BIND(&if_modified);
        Unreachable();
        BIND(&if_not_modified);
      }
227
      CSA_ASSERT(this, WordEqual(original_initial_entries_map,
228
                                 LoadMap(initial_entries_jsarray)));
229
#endif
230
      use_fast_loop = Int32FalseConstant();
231
      Goto(&allocate_table);
232
    }
233
  }
234 235 236 237 238 239
  BIND(&slow_loop);
  {
    AddConstructorEntriesFromIterable(variant, context, native_context,
                                      collection, initial_entries);
    Goto(&exit);
  }
240 241 242 243
  BIND(&exit);
}

void BaseCollectionsAssembler::AddConstructorEntriesFromFastJSArray(
244
    Variant variant, TNode<Context> context, TNode<Context> native_context,
245 246
    TNode<Object> collection, TNode<JSArray> fast_jsarray,
    Label* if_may_have_side_effects) {
247
  TNode<FixedArrayBase> elements = LoadElements(fast_jsarray);
248
  TNode<Int32T> elements_kind = LoadElementsKind(fast_jsarray);
249
  TNode<JSFunction> add_func = GetInitialAddFunction(variant, native_context);
250 251 252
  CSA_ASSERT(
      this,
      WordEqual(GetAddFunction(variant, native_context, collection), add_func));
253
  CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(context, fast_jsarray));
254
  TNode<IntPtrT> length = SmiUntag(LoadFastJSArrayLength(fast_jsarray));
255
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(length, IntPtrConstant(0)));
256 257
  CSA_ASSERT(
      this, HasInitialCollectionPrototype(variant, native_context, collection));
258

259 260 261 262
#if DEBUG
  TNode<Map> original_collection_map = LoadMap(CAST(collection));
  TNode<Map> original_fast_js_array_map = LoadMap(fast_jsarray);
#endif
263
  Label exit(this), if_doubles(this), if_smiorobjects(this);
264
  GotoIf(IntPtrEqual(length, IntPtrConstant(0)), &exit);
265 266 267 268 269
  Branch(IsFastSmiOrTaggedElementsKind(elements_kind), &if_smiorobjects,
         &if_doubles);
  BIND(&if_smiorobjects);
  {
    auto set_entry = [&](Node* index) {
270
      TNode<Object> element = LoadAndNormalizeFixedArrayElement(
271
          CAST(elements), UncheckedCast<IntPtrT>(index));
272 273
      AddConstructorEntry(variant, context, collection, add_func, element,
                          if_may_have_side_effects);
274
    };
275 276 277 278 279

    // Instead of using the slower iteration protocol to iterate over the
    // elements, a fast loop is used.  This assumes that adding an element
    // to the collection does not call user code that could mutate the elements
    // or collection.
280 281 282 283 284 285 286 287
    BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
                  ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
    Goto(&exit);
  }
  BIND(&if_doubles);
  {
    // A Map constructor requires entries to be arrays (ex. [key, value]),
    // so a FixedDoubleArray can never succeed.
288
    if (variant == kMap || variant == kWeakMap) {
289 290 291
      CSA_ASSERT(this, IntPtrGreaterThan(length, IntPtrConstant(0)));
      TNode<Object> element =
          LoadAndNormalizeFixedDoubleArrayElement(elements, IntPtrConstant(0));
292
      ThrowTypeError(context, MessageTemplate::kIteratorValueNotAnObject,
293
                     element);
294
    } else {
295
      DCHECK(variant == kSet || variant == kWeakSet);
296
      auto set_entry = [&](Node* index) {
297 298
        TNode<Object> entry = LoadAndNormalizeFixedDoubleArrayElement(
            elements, UncheckedCast<IntPtrT>(index));
299
        AddConstructorEntry(variant, context, collection, add_func, entry);
300 301 302 303 304 305 306
      };
      BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
                    ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
      Goto(&exit);
    }
  }
  BIND(&exit);
307 308 309 310 311 312
#if DEBUG
  CSA_ASSERT(this,
             WordEqual(original_collection_map, LoadMap(CAST(collection))));
  CSA_ASSERT(this,
             WordEqual(original_fast_js_array_map, LoadMap(fast_jsarray)));
#endif
313 314 315 316 317 318 319 320
}

void BaseCollectionsAssembler::AddConstructorEntriesFromIterable(
    Variant variant, TNode<Context> context, TNode<Context> native_context,
    TNode<Object> collection, TNode<Object> iterable) {
  Label exit(this), loop(this), if_exception(this, Label::kDeferred);
  CSA_ASSERT(this, Word32BinaryNot(IsNullOrUndefined(iterable)));

321
  TNode<Object> add_func = GetAddFunction(variant, context, collection);
322
  IteratorBuiltinsAssembler iterator_assembler(this->state());
323
  IteratorBuiltinsAssembler::IteratorRecord iterator =
324
      iterator_assembler.GetIterator(context, iterable);
325

326
  CSA_ASSERT(this, Word32BinaryNot(IsUndefined(iterator.object)));
327 328 329 330 331 332 333 334

  TNode<Object> fast_iterator_result_map =
      LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX);
  TVARIABLE(Object, var_exception);

  Goto(&loop);
  BIND(&loop);
  {
335 336
    TNode<Object> next = iterator_assembler.IteratorStep(
        context, iterator, &exit, fast_iterator_result_map);
337 338
    TNode<Object> next_value = CAST(iterator_assembler.IteratorValue(
        context, next, fast_iterator_result_map));
339 340
    AddConstructorEntry(variant, context, collection, add_func, next_value,
                        nullptr, &if_exception, &var_exception);
341 342 343 344 345
    Goto(&loop);
  }
  BIND(&if_exception);
  {
    iterator_assembler.IteratorCloseOnException(context, iterator,
346
                                                var_exception.value());
347 348 349 350
  }
  BIND(&exit);
}

351
RootIndex BaseCollectionsAssembler::GetAddFunctionNameIndex(Variant variant) {
352 353 354
  switch (variant) {
    case kMap:
    case kWeakMap:
355
      return RootIndex::kset_string;
356 357
    case kSet:
    case kWeakSet:
358
      return RootIndex::kadd_string;
359 360 361 362
  }
  UNREACHABLE();
}

363
void BaseCollectionsAssembler::GotoIfInitialAddFunctionModified(
364 365
    Variant variant, TNode<Context> native_context, TNode<Object> collection,
    Label* if_modified) {
366 367 368 369 370 371 372
  STATIC_ASSERT(JSCollection::kAddFunctionDescriptorIndex ==
                JSWeakCollection::kAddFunctionDescriptorIndex);
  GotoIfInitialPrototypePropertyModified(
      LoadMap(CAST(collection)),
      GetInitialCollectionPrototype(variant, native_context),
      JSCollection::kAddFunctionDescriptorIndex,
      GetAddFunctionNameIndex(variant), if_modified);
373 374
}

375
TNode<Object> BaseCollectionsAssembler::AllocateJSCollection(
376 377
    TNode<Context> context, TNode<JSFunction> constructor,
    TNode<Object> new_target) {
378 379 380 381 382 383 384
  TNode<BoolT> is_target_unmodified = WordEqual(constructor, new_target);

  return Select<Object>(is_target_unmodified,
                        [=] { return AllocateJSCollectionFast(constructor); },
                        [=] {
                          return AllocateJSCollectionSlow(context, constructor,
                                                          new_target);
385
                        });
386
}
387

388 389 390 391 392 393 394 395 396
TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionFast(
    TNode<HeapObject> constructor) {
  CSA_ASSERT(this, IsConstructorMap(LoadMap(constructor)));
  TNode<Object> initial_map =
      LoadObjectField(constructor, JSFunction::kPrototypeOrInitialMapOffset);
  return CAST(AllocateJSObjectFromMap(initial_map));
}

TNode<Object> BaseCollectionsAssembler::AllocateJSCollectionSlow(
397
    TNode<Context> context, TNode<JSFunction> constructor,
398 399 400 401 402 403 404
    TNode<Object> new_target) {
  ConstructorBuiltinsAssembler constructor_assembler(this->state());
  return CAST(constructor_assembler.EmitFastNewObject(context, constructor,
                                                      new_target));
}

void BaseCollectionsAssembler::GenerateConstructor(
405 406
    Variant variant, Handle<String> constructor_function_name,
    TNode<Object> new_target, TNode<IntPtrT> argc, TNode<Context> context) {
407
  const int kIterableArg = 0;
408
  CodeStubArguments args(this, argc);
409 410 411 412 413
  TNode<Object> iterable = args.GetOptionalArgumentValue(kIterableArg);

  Label if_undefined(this, Label::kDeferred);
  GotoIf(IsUndefined(new_target), &if_undefined);

414
  TNode<Context> native_context = LoadNativeContext(context);
415
  TNode<Object> collection = AllocateJSCollection(
416
      context, GetConstructor(variant, native_context), new_target);
417

418
  AddConstructorEntries(variant, context, native_context, collection, iterable);
419 420 421 422 423 424 425
  Return(collection);

  BIND(&if_undefined);
  ThrowTypeError(context, MessageTemplate::kConstructorNotFunction,
                 HeapConstant(constructor_function_name));
}

426
TNode<Object> BaseCollectionsAssembler::GetAddFunction(
427
    Variant variant, TNode<Context> context, TNode<Object> collection) {
428
  Handle<String> add_func_name = (variant == kMap || variant == kWeakMap)
429 430
                                     ? isolate()->factory()->set_string()
                                     : isolate()->factory()->add_string();
431
  TNode<Object> add_func = GetProperty(context, collection, add_func_name);
432 433 434

  Label exit(this), if_notcallable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(add_func), &if_notcallable);
435
  GotoIfNot(IsCallable(CAST(add_func)), &if_notcallable);
436 437 438 439 440 441 442
  Goto(&exit);

  BIND(&if_notcallable);
  ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, add_func,
                 HeapConstant(add_func_name), collection);

  BIND(&exit);
443
  return add_func;
444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
}

TNode<JSFunction> BaseCollectionsAssembler::GetConstructor(
    Variant variant, TNode<Context> native_context) {
  int index;
  switch (variant) {
    case kMap:
      index = Context::JS_MAP_FUN_INDEX;
      break;
    case kSet:
      index = Context::JS_SET_FUN_INDEX;
      break;
    case kWeakMap:
      index = Context::JS_WEAK_MAP_FUN_INDEX;
      break;
    case kWeakSet:
      index = Context::JS_WEAK_SET_FUN_INDEX;
      break;
  }
  return CAST(LoadContextElement(native_context, index));
}

TNode<JSFunction> BaseCollectionsAssembler::GetInitialAddFunction(
    Variant variant, TNode<Context> native_context) {
  int index;
  switch (variant) {
    case kMap:
      index = Context::MAP_SET_INDEX;
      break;
    case kSet:
      index = Context::SET_ADD_INDEX;
      break;
    case kWeakMap:
      index = Context::WEAKMAP_SET_INDEX;
      break;
    case kWeakSet:
      index = Context::WEAKSET_ADD_INDEX;
      break;
  }
  return CAST(LoadContextElement(native_context, index));
}

int BaseCollectionsAssembler::GetTableOffset(Variant variant) {
  switch (variant) {
    case kMap:
      return JSMap::kTableOffset;
    case kSet:
      return JSSet::kTableOffset;
    case kWeakMap:
      return JSWeakMap::kTableOffset;
    case kWeakSet:
      return JSWeakSet::kTableOffset;
  }
  UNREACHABLE();
498 499 500 501 502 503 504
}

TNode<IntPtrT> BaseCollectionsAssembler::EstimatedInitialSize(
    TNode<Object> initial_entries, TNode<BoolT> is_fast_jsarray) {
  return Select<IntPtrT>(
      is_fast_jsarray,
      [=] { return SmiUntag(LoadFastJSArrayLength(CAST(initial_entries))); },
505
      [=] { return IntPtrConstant(0); });
506 507 508 509 510 511 512 513
}

void BaseCollectionsAssembler::GotoIfNotJSReceiver(Node* const obj,
                                                   Label* if_not_receiver) {
  GotoIf(TaggedIsSmi(obj), if_not_receiver);
  GotoIfNot(IsJSReceiver(obj), if_not_receiver);
}

514 515
TNode<Map> BaseCollectionsAssembler::GetInitialCollectionPrototype(
    Variant variant, TNode<Context> native_context) {
516 517 518 519 520 521 522 523 524 525 526 527 528 529 530
  int initial_prototype_index;
  switch (variant) {
    case kMap:
      initial_prototype_index = Context::INITIAL_MAP_PROTOTYPE_MAP_INDEX;
      break;
    case kSet:
      initial_prototype_index = Context::INITIAL_SET_PROTOTYPE_MAP_INDEX;
      break;
    case kWeakMap:
      initial_prototype_index = Context::INITIAL_WEAKMAP_PROTOTYPE_MAP_INDEX;
      break;
    case kWeakSet:
      initial_prototype_index = Context::INITIAL_WEAKSET_PROTOTYPE_MAP_INDEX;
      break;
  }
531 532 533 534 535
  return CAST(LoadContextElement(native_context, initial_prototype_index));
}

TNode<BoolT> BaseCollectionsAssembler::HasInitialCollectionPrototype(
    Variant variant, TNode<Context> native_context, TNode<Object> collection) {
536
  TNode<Map> collection_proto_map =
537
      LoadMap(LoadMapPrototype(LoadMap(CAST(collection))));
538

539 540
  return WordEqual(collection_proto_map,
                   GetInitialCollectionPrototype(variant, native_context));
541 542
}

543
TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedArrayElement(
544
    TNode<FixedArray> elements, TNode<IntPtrT> index) {
545
  TNode<Object> element = UnsafeLoadFixedArrayElement(elements, index);
546
  return Select<Object>(IsTheHole(element), [=] { return UndefinedConstant(); },
547
                        [=] { return element; });
548 549 550
}

TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedDoubleArrayElement(
551
    TNode<HeapObject> elements, TNode<IntPtrT> index) {
552 553
  TVARIABLE(Object, entry);
  Label if_hole(this, Label::kDeferred), next(this);
554 555 556
  TNode<Float64T> element =
      LoadFixedDoubleArrayElement(CAST(elements), index, MachineType::Float64(),
                                  0, INTPTR_PARAMETERS, &if_hole);
557 558 559 560 561 562 563 564 565 566
  {  // not hole
    entry = AllocateHeapNumberWithValue(element);
    Goto(&next);
  }
  BIND(&if_hole);
  {
    entry = UndefinedConstant();
    Goto(&next);
  }
  BIND(&next);
567
  return entry.value();
568 569
}

570 571 572 573 574
class CollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
 public:
  explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
      : BaseCollectionsAssembler(state) {}

575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590
  // Check whether |iterable| is a JS_MAP_KEY_ITERATOR_TYPE or
  // JS_MAP_VALUE_ITERATOR_TYPE object that is not partially consumed and still
  // has original iteration behavior.
  void BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterable,
                                                         TNode<Context> context,
                                                         Label* if_true,
                                                         Label* if_false);

  // Check whether |iterable| is a JS_SET_TYPE or JS_SET_VALUE_ITERATOR_TYPE
  // object that still has original iteration behavior. In case of the iterator,
  // the iterator also must not have been partially consumed.
  void BranchIfIterableWithOriginalValueSetIterator(TNode<Object> iterable,
                                                    TNode<Context> context,
                                                    Label* if_true,
                                                    Label* if_false);

591
 protected:
592 593 594
  template <typename IteratorType>
  Node* AllocateJSCollectionIterator(Node* context, int map_index,
                                     Node* collection);
595
  TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
596
                              TNode<IntPtrT> at_least_space_for) override;
597
  Node* GetHash(Node* const key);
598
  Node* CallGetHashRaw(Node* const key);
599
  Node* CallGetOrCreateHashRaw(Node* const key);
600

601 602 603 604 605
  // Transitions the iterator to the non obsolete backing store.
  // This is a NOP if the [table] is not obsolete.
  typedef std::function<void(Node* const table, Node* const index)>
      UpdateInTransition;
  template <typename TableType>
606 607
  std::pair<TNode<TableType>, TNode<IntPtrT>> Transition(
      TNode<TableType> const table, TNode<IntPtrT> const index,
608
      UpdateInTransition const& update_in_transition);
609
  template <typename IteratorType, typename TableType>
610 611
  std::pair<TNode<TableType>, TNode<IntPtrT>> TransitionAndUpdate(
      TNode<IteratorType> const iterator);
612
  template <typename TableType>
613 614
  std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>> NextSkipHoles(
      TNode<TableType> table, TNode<IntPtrT> index, Label* if_end);
615

616
  // Specialization for Smi.
617 618
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
619 620
  template <typename CollectionType>
  void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
621 622
                                          Variable* result, Label* entry_found,
                                          Label* not_found);
623 624 625
  void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
                        Label* if_not_same);

626
  // Specialization for heap numbers.
627 628
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
629 630
  void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
                               Label* if_same, Label* if_not_same);
631 632 633
  template <typename CollectionType>
  void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
                                                 Node* key_heap_number,
634
                                                 Variable* result,
635 636
                                                 Label* entry_found,
                                                 Label* not_found);
637

638 639 640 641 642 643 644 645 646 647 648
  // Specialization for bigints.
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
  void SameValueZeroBigInt(Node* key, Node* candidate_key, Label* if_same,
                           Label* if_not_same);
  template <typename CollectionType>
  void FindOrderedHashTableEntryForBigIntKey(Node* context, Node* table,
                                             Node* key, Variable* result,
                                             Label* entry_found,
                                             Label* not_found);

649
  // Specialization for string.
650 651
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
652 653
  template <typename CollectionType>
  void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
654
                                             Node* key_tagged, Variable* result,
655 656
                                             Label* entry_found,
                                             Label* not_found);
657
  Node* ComputeStringHash(Node* context, Node* string_key);
658 659
  void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
                           Label* if_same, Label* if_not_same);
660 661 662

  // Specialization for non-strings, non-numbers. For those we only need
  // reference equality to compare the keys.
663 664 665
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise. If the hash-code has not been computed, it
  // should be Smi -1.
666 667
  template <typename CollectionType>
  void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
668
                                            Node* key, Variable* result,
669 670
                                            Label* entry_found,
                                            Label* not_found);
671 672 673 674 675 676

  template <typename CollectionType>
  void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
                                      Node* const context, Variable* result,
                                      Label* if_entry_found,
                                      Label* if_not_found);
677 678

  Node* NormalizeNumberKey(Node* key);
679 680 681
  void StoreOrderedHashMapNewEntry(TNode<OrderedHashMap> const table,
                                   Node* const key, Node* const value,
                                   Node* const hash,
682 683
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
684 685
  void StoreOrderedHashSetNewEntry(TNode<OrderedHashSet> const table,
                                   Node* const key, Node* const hash,
686 687
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707

  // Create a JSArray with PACKED_ELEMENTS kind from a Map.prototype.keys() or
  // Map.prototype.values() iterator. The iterator is assumed to satisfy
  // IterableWithOriginalKeyOrValueMapIterator. This function will skip the
  // iterator and iterate directly on the underlying hash table. In the end it
  // will update the state of the iterator to 'exhausted'.
  TNode<JSArray> MapIteratorToList(TNode<Context> context,
                                   TNode<JSMapIterator> iterator);

  // Create a JSArray with PACKED_ELEMENTS kind from a Set.prototype.keys() or
  // Set.prototype.values() iterator, or a Set. The |iterable| is assumed to
  // satisfy IterableWithOriginalValueSetIterator. This function will skip the
  // iterator and iterate directly on the underlying hash table. In the end, if
  // |iterable| is an iterator, it will update the state of the iterator to
  // 'exhausted'.
  TNode<JSArray> SetOrSetIteratorToList(TNode<Context> context,
                                        TNode<Object> iterable);

  void BranchIfMapIteratorProtectorValid(Label* if_true, Label* if_false);
  void BranchIfSetIteratorProtectorValid(Label* if_true, Label* if_false);
708 709
};

710 711 712 713 714 715 716 717
template <typename IteratorType>
Node* CollectionsBuiltinsAssembler::AllocateJSCollectionIterator(
    Node* context, int map_index, Node* collection) {
  Node* const table = LoadObjectField(collection, JSCollection::kTableOffset);
  Node* const native_context = LoadNativeContext(context);
  Node* const iterator_map = LoadContextElement(native_context, map_index);
  Node* const iterator = AllocateInNewSpace(IteratorType::kSize);
  StoreMapNoWriteBarrier(iterator, iterator_map);
718
  StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
719
                       RootIndex::kEmptyFixedArray);
720
  StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
721
                       RootIndex::kEmptyFixedArray);
722 723 724 725 726 727
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                                 SmiConstant(0));
  return iterator;
}

728 729 730
TNode<Object> CollectionsBuiltinsAssembler::AllocateTable(
    Variant variant, TNode<Context> context,
    TNode<IntPtrT> at_least_space_for) {
731 732 733
  return CAST((variant == kMap || variant == kWeakMap)
                  ? AllocateOrderedHashTable<OrderedHashMap>()
                  : AllocateOrderedHashTable<OrderedHashSet>());
734
}
735

736
TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler) {
737
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
738
  TNode<IntPtrT> argc =
739 740
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
741 742 743

  GenerateConstructor(kMap, isolate()->factory()->Map_string(), new_target,
                      argc, context);
744 745 746
}

TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) {
747
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
748
  TNode<IntPtrT> argc =
749 750
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
751 752 753

  GenerateConstructor(kSet, isolate()->factory()->Set_string(), new_target,
                      argc, context);
754 755
}

756 757
Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key) {
  Node* const function_addr =
758
      ExternalConstant(ExternalReference::get_or_create_hash_raw());
759 760 761 762 763 764
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();

765 766 767
  Node* const result = CallCFunction(function_addr, type_tagged,
                                     std::make_pair(type_ptr, isolate_ptr),
                                     std::make_pair(type_tagged, key));
768 769 770 771

  return result;
}

772
Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) {
773 774
  Node* const function_addr =
      ExternalConstant(ExternalReference::orderedhashmap_gethash_raw());
775 776 777 778 779 780
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();

781 782 783 784
  Node* const result = CallCFunction(function_addr, type_tagged,
                                     std::make_pair(type_ptr, isolate_ptr),
                                     std::make_pair(type_tagged, key));

785 786 787 788
  return SmiUntag(result);
}

Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) {
789 790 791
  VARIABLE(var_hash, MachineType::PointerRepresentation());
  Label if_receiver(this), if_other(this), done(this);
  Branch(IsJSReceiver(key), &if_receiver, &if_other);
792

793
  BIND(&if_receiver);
794
  {
795
    var_hash.Bind(LoadJSReceiverIdentityHash(key));
796 797
    Goto(&done);
  }
798

799
  BIND(&if_other);
800
  {
801
    var_hash.Bind(CallGetHashRaw(key));
802 803 804 805
    Goto(&done);
  }

  BIND(&done);
806
  return var_hash.value();
807 808
}

809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
                                                    Node* candidate_key,
                                                    Label* if_same,
                                                    Label* if_not_same) {
  // If the key is the same, we are done.
  GotoIf(WordEqual(candidate_key, key_smi), if_same);

  // If the candidate key is smi, then it must be different (because
  // we already checked for equality above).
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);

  // If the candidate key is not smi, we still have to check if it is a
  // heap number with the same value.
  GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

  Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
  Node* const key_number = SmiToFloat64(key_smi);

  GotoIf(Float64Equal(candidate_key_number, key_number), if_same);

  Goto(if_not_same);
}

832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963
void CollectionsBuiltinsAssembler::BranchIfMapIteratorProtectorValid(
    Label* if_true, Label* if_false) {
  Node* protector_cell = LoadRoot(RootIndex::kMapIteratorProtector);
  DCHECK(isolate()->heap()->map_iterator_protector()->IsPropertyCell());
  Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
                   SmiConstant(Isolate::kProtectorValid)),
         if_true, if_false);
}

void CollectionsBuiltinsAssembler::
    BranchIfIterableWithOriginalKeyOrValueMapIterator(TNode<Object> iterator,
                                                      TNode<Context> context,
                                                      Label* if_true,
                                                      Label* if_false) {
  Label if_key_or_value_iterator(this), extra_checks(this);

  // Check if iterator is a keys or values JSMapIterator.
  GotoIf(TaggedIsSmi(iterator), if_false);
  TNode<Map> iter_map = LoadMap(CAST(iterator));
  Node* const instance_type = LoadMapInstanceType(iter_map);
  GotoIf(InstanceTypeEqual(instance_type, JS_MAP_KEY_ITERATOR_TYPE),
         &if_key_or_value_iterator);
  Branch(InstanceTypeEqual(instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
         &if_key_or_value_iterator, if_false);

  BIND(&if_key_or_value_iterator);
  // Check that the iterator is not partially consumed.
  Node* const index =
      LoadObjectField(CAST(iterator), JSMapIterator::kIndexOffset);
  GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);
  BranchIfMapIteratorProtectorValid(&extra_checks, if_false);

  BIND(&extra_checks);
  // Check if the iterator object has the original %MapIteratorPrototype%.
  Node* const native_context = LoadNativeContext(context);
  Node* const initial_map_iter_proto = LoadContextElement(
      native_context, Context::INITIAL_MAP_ITERATOR_PROTOTYPE_INDEX);
  Node* const map_iter_proto = LoadMapPrototype(iter_map);
  GotoIfNot(WordEqual(map_iter_proto, initial_map_iter_proto), if_false);

  // Check if the original MapIterator prototype has the original
  // %IteratorPrototype%.
  Node* const initial_iter_proto = LoadContextElement(
      native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
  Node* const iter_proto = LoadMapPrototype(LoadMap(map_iter_proto));
  Branch(WordEqual(iter_proto, initial_iter_proto), if_true, if_false);
}

void BranchIfIterableWithOriginalKeyOrValueMapIterator(
    compiler::CodeAssemblerState* state, TNode<Object> iterable,
    TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
    compiler::CodeAssemblerLabel* if_false) {
  CollectionsBuiltinsAssembler assembler(state);
  assembler.BranchIfIterableWithOriginalKeyOrValueMapIterator(
      iterable, context, if_true, if_false);
}

void CollectionsBuiltinsAssembler::BranchIfSetIteratorProtectorValid(
    Label* if_true, Label* if_false) {
  Node* const protector_cell = LoadRoot(RootIndex::kSetIteratorProtector);
  DCHECK(isolate()->heap()->set_iterator_protector()->IsPropertyCell());
  Branch(WordEqual(LoadObjectField(protector_cell, PropertyCell::kValueOffset),
                   SmiConstant(Isolate::kProtectorValid)),
         if_true, if_false);
}

void CollectionsBuiltinsAssembler::BranchIfIterableWithOriginalValueSetIterator(
    TNode<Object> iterable, TNode<Context> context, Label* if_true,
    Label* if_false) {
  Label if_set(this), if_value_iterator(this), check_protector(this);
  TVARIABLE(BoolT, var_result);

  GotoIf(TaggedIsSmi(iterable), if_false);
  TNode<Map> iterable_map = LoadMap(CAST(iterable));
  Node* const instance_type = LoadMapInstanceType(iterable_map);

  GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set);
  Branch(InstanceTypeEqual(instance_type, JS_SET_VALUE_ITERATOR_TYPE),
         &if_value_iterator, if_false);

  BIND(&if_set);
  // Check if the set object has the original Set prototype.
  Node* const initial_set_proto = LoadContextElement(
      LoadNativeContext(context), Context::INITIAL_SET_PROTOTYPE_INDEX);
  Node* const set_proto = LoadMapPrototype(iterable_map);
  GotoIfNot(WordEqual(set_proto, initial_set_proto), if_false);
  Goto(&check_protector);

  BIND(&if_value_iterator);
  // Check that the iterator is not partially consumed.
  Node* const index =
      LoadObjectField(CAST(iterable), JSSetIterator::kIndexOffset);
  GotoIfNot(WordEqual(index, SmiConstant(0)), if_false);

  // Check if the iterator object has the original SetIterator prototype.
  Node* const native_context = LoadNativeContext(context);
  Node* const initial_set_iter_proto = LoadContextElement(
      native_context, Context::INITIAL_SET_ITERATOR_PROTOTYPE_INDEX);
  Node* const set_iter_proto = LoadMapPrototype(iterable_map);
  GotoIfNot(WordEqual(set_iter_proto, initial_set_iter_proto), if_false);

  // Check if the original SetIterator prototype has the original
  // %IteratorPrototype%.
  Node* const initial_iter_proto = LoadContextElement(
      native_context, Context::INITIAL_ITERATOR_PROTOTYPE_INDEX);
  Node* const iter_proto = LoadMapPrototype(LoadMap(set_iter_proto));
  GotoIfNot(WordEqual(iter_proto, initial_iter_proto), if_false);
  Goto(&check_protector);

  BIND(&check_protector);
  BranchIfSetIteratorProtectorValid(if_true, if_false);
}

void BranchIfIterableWithOriginalValueSetIterator(
    compiler::CodeAssemblerState* state, TNode<Object> iterable,
    TNode<Context> context, compiler::CodeAssemblerLabel* if_true,
    compiler::CodeAssemblerLabel* if_false) {
  CollectionsBuiltinsAssembler assembler(state);
  assembler.BranchIfIterableWithOriginalValueSetIterator(iterable, context,
                                                         if_true, if_false);
}

TNode<JSArray> CollectionsBuiltinsAssembler::MapIteratorToList(
    TNode<Context> context, TNode<JSMapIterator> iterator) {
  // Transition the {iterator} table if necessary.
  TNode<OrderedHashMap> table;
  TNode<IntPtrT> index;
  std::tie(table, index) =
      TransitionAndUpdate<JSMapIterator, OrderedHashMap>(iterator);
  CSA_ASSERT(this, IntPtrEqual(index, IntPtrConstant(0)));

  TNode<IntPtrT> size =
964
      LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());
965 966

  const ElementsKind kind = PACKED_ELEMENTS;
967
  TNode<Map> array_map =
968
      LoadJSArrayElementsMap(kind, LoadNativeContext(context));
969 970 971
  TNode<JSArray> array =
      AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
                      INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011
  TNode<FixedArray> elements = CAST(LoadElements(array));

  const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
  TNode<IntPtrT> first_to_element_offset =
      ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
  VARIABLE(
      var_offset, MachineType::PointerRepresentation(),
      IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
  TVARIABLE(IntPtrT, var_index, index);
  VariableList vars({&var_index, &var_offset}, zone());
  Label done(this, {&var_index}), loop(this, vars), continue_loop(this, vars),
      write_key(this, vars), write_value(this, vars);

  Goto(&loop);

  BIND(&loop);
  {
    // Read the next entry from the {table}, skipping holes.
    TNode<Object> entry_key;
    TNode<IntPtrT> entry_start_position;
    TNode<IntPtrT> cur_index;
    std::tie(entry_key, entry_start_position, cur_index) =
        NextSkipHoles<OrderedHashMap>(table, var_index.value(), &done);

    // Decide to write key or value.
    Branch(
        InstanceTypeEqual(LoadInstanceType(iterator), JS_MAP_KEY_ITERATOR_TYPE),
        &write_key, &write_value);

    BIND(&write_key);
    {
      Store(elements, var_offset.value(), entry_key);
      Goto(&continue_loop);
    }

    BIND(&write_value);
    {
      CSA_ASSERT(this, InstanceTypeEqual(LoadInstanceType(iterator),
                                         JS_MAP_VALUE_ITERATOR_TYPE));
      TNode<Object> entry_value =
1012 1013 1014 1015
          UnsafeLoadFixedArrayElement(table, entry_start_position,
                                      (OrderedHashMap::HashTableStartIndex() +
                                       OrderedHashMap::kValueOffset) *
                                          kTaggedSize);
1016 1017 1018 1019 1020 1021 1022 1023 1024 1025

      Store(elements, var_offset.value(), entry_value);
      Goto(&continue_loop);
    }

    BIND(&continue_loop);
    {
      // Increment the array offset and continue the loop to the next entry.
      var_index = cur_index;
      var_offset.Bind(
1026
          IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076
      Goto(&loop);
    }
  }

  BIND(&done);
  // Set the {iterator} to exhausted.
  StoreObjectFieldRoot(iterator, JSMapIterator::kTableOffset,
                       RootIndex::kEmptyOrderedHashMap);
  StoreObjectFieldNoWriteBarrier(iterator, JSMapIterator::kIndexOffset,
                                 SmiTag(var_index.value()));
  return UncheckedCast<JSArray>(array);
}

TF_BUILTIN(MapIteratorToList, CollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<JSMapIterator> iterator = CAST(Parameter(Descriptor::kSource));
  Return(MapIteratorToList(context, iterator));
}

TNode<JSArray> CollectionsBuiltinsAssembler::SetOrSetIteratorToList(
    TNode<Context> context, TNode<Object> iterable) {
  TVARIABLE(OrderedHashSet, var_table);
  Label if_set(this), if_iterator(this), copy(this);

  Node* const instance_type = LoadInstanceType(CAST(iterable));
  Branch(InstanceTypeEqual(instance_type, JS_SET_TYPE), &if_set, &if_iterator);

  BIND(&if_set);
  {
    // {iterable} is a JSSet.
    var_table = CAST(LoadObjectField(CAST(iterable), JSSet::kTableOffset));
    Goto(&copy);
  }

  BIND(&if_iterator);
  {
    // {iterable} is a JSSetIterator.
    // Transition the {iterable} table if necessary.
    TNode<OrderedHashSet> iter_table;
    TNode<IntPtrT> iter_index;
    std::tie(iter_table, iter_index) =
        TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(iterable));
    CSA_ASSERT(this, IntPtrEqual(iter_index, IntPtrConstant(0)));
    var_table = iter_table;
    Goto(&copy);
  }

  BIND(&copy);
  TNode<OrderedHashSet> table = var_table.value();
  TNode<IntPtrT> size =
1077
      LoadAndUntagObjectField(table, OrderedHashMap::NumberOfElementsOffset());
1078 1079

  const ElementsKind kind = PACKED_ELEMENTS;
1080
  TNode<Map> array_map =
1081
      LoadJSArrayElementsMap(kind, LoadNativeContext(context));
1082 1083 1084
  TNode<JSArray> array =
      AllocateJSArray(kind, array_map, size, SmiTag(size), nullptr,
                      INTPTR_PARAMETERS, kAllowLargeObjectAllocation);
1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
  TNode<FixedArray> elements = CAST(LoadElements(array));

  const int first_element_offset = FixedArray::kHeaderSize - kHeapObjectTag;
  TNode<IntPtrT> first_to_element_offset =
      ElementOffsetFromIndex(IntPtrConstant(0), kind, INTPTR_PARAMETERS, 0);
  VARIABLE(
      var_offset, MachineType::PointerRepresentation(),
      IntPtrAdd(first_to_element_offset, IntPtrConstant(first_element_offset)));
  TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
  Label done(this), finalize(this, {&var_index}),
      loop(this, {&var_index, &var_offset});

  Goto(&loop);

  BIND(&loop);
  {
    // Read the next entry from the {table}, skipping holes.
    TNode<Object> entry_key;
    TNode<IntPtrT> entry_start_position;
    TNode<IntPtrT> cur_index;
    std::tie(entry_key, entry_start_position, cur_index) =
        NextSkipHoles<OrderedHashSet>(table, var_index.value(), &finalize);

    Store(elements, var_offset.value(), entry_key);

    var_index = cur_index;
1111
    var_offset.Bind(IntPtrAdd(var_offset.value(), IntPtrConstant(kTaggedSize)));
1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
    Goto(&loop);
  }

  BIND(&finalize);
  GotoIf(InstanceTypeEqual(instance_type, JS_SET_TYPE), &done);
  // Set the {iterable} to exhausted if it's an iterator.
  StoreObjectFieldRoot(iterable, JSSetIterator::kTableOffset,
                       RootIndex::kEmptyOrderedHashSet);
  StoreObjectFieldNoWriteBarrier(iterable, JSSetIterator::kIndexOffset,
                                 SmiTag(var_index.value()));
  Goto(&done);

  BIND(&done);
  return UncheckedCast<JSArray>(array);
}

TF_BUILTIN(SetOrSetIteratorToList, CollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<Object> object = CAST(Parameter(Descriptor::kSource));
  Return(SetOrSetIteratorToList(context, object));
}

1134 1135
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
1136 1137
    Node* table, Node* smi_key, Variable* result, Label* entry_found,
    Label* not_found) {
1138
  Node* const key_untagged = SmiUntag(smi_key);
1139
  Node* const hash = ChangeInt32ToIntPtr(ComputeUnseededHash(key_untagged));
1140 1141
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
1142
  FindOrderedHashTableEntry<CollectionType>(
1143
      table, hash,
1144 1145 1146
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
      },
1147
      result, entry_found, not_found);
1148 1149
}

1150 1151
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
1152 1153
    Node* context, Node* table, Node* key_tagged, Variable* result,
    Label* entry_found, Label* not_found) {
1154
  Node* const hash = ComputeStringHash(context, key_tagged);
1155 1156
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
1157
  FindOrderedHashTableEntry<CollectionType>(
1158
      table, hash,
1159 1160 1161 1162
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroString(context, key_tagged, other_key, if_same,
                            if_not_same);
      },
1163
      result, entry_found, not_found);
1164 1165
}

1166 1167
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
1168 1169
    Node* context, Node* table, Node* key_heap_number, Variable* result,
    Label* entry_found, Label* not_found) {
1170
  Node* hash = CallGetHashRaw(key_heap_number);
1171 1172
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
1173
  Node* const key_float = LoadHeapNumberValue(key_heap_number);
1174
  FindOrderedHashTableEntry<CollectionType>(
1175
      table, hash,
1176 1177 1178
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
      },
1179
      result, entry_found, not_found);
1180 1181
}

1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForBigIntKey(
    Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
    Label* not_found) {
  Node* hash = CallGetHashRaw(key);
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroBigInt(key, other_key, if_same, if_not_same);
      },
      result, entry_found, not_found);
}

1197 1198
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
1199 1200
    Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
    Label* not_found) {
1201
  Node* hash = GetHash(key);
1202
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
1203
  result->Bind(hash);
1204
  FindOrderedHashTableEntry<CollectionType>(
1205
      table, hash,
1206 1207 1208
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        Branch(WordEqual(key, other_key), if_same, if_not_same);
      },
1209
      result, entry_found, not_found);
1210 1211
}

1212 1213
Node* CollectionsBuiltinsAssembler::ComputeStringHash(Node* context,
                                                      Node* string_key) {
1214 1215 1216 1217 1218 1219 1220 1221 1222
  VARIABLE(var_result, MachineType::PointerRepresentation());

  Label hash_not_computed(this), done(this, &var_result);
  Node* hash =
      ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
  var_result.Bind(hash);
  Goto(&done);

  BIND(&hash_not_computed);
1223
  var_result.Bind(CallGetHashRaw(string_key));
1224
  Goto(&done);
1225

1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244
  BIND(&done);
  return var_result.value();
}

void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
                                                       Node* key_string,
                                                       Node* candidate_key,
                                                       Label* if_same,
                                                       Label* if_not_same) {
  // If the candidate is not a string, the keys are not equal.
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
  GotoIfNot(IsString(candidate_key), if_not_same);

  Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
                               candidate_key),
                   TrueConstant()),
         if_same, if_not_same);
}

1245 1246 1247 1248 1249 1250 1251 1252
void CollectionsBuiltinsAssembler::SameValueZeroBigInt(Node* key,
                                                       Node* candidate_key,
                                                       Label* if_same,
                                                       Label* if_not_same) {
  CSA_ASSERT(this, IsBigInt(key));
  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
  GotoIfNot(IsBigInt(candidate_key), if_not_same);

1253 1254
  Branch(WordEqual(CallRuntime(Runtime::kBigIntEqualToBigInt,
                               NoContextConstant(), key, candidate_key),
1255 1256 1257 1258
                   TrueConstant()),
         if_same, if_not_same);
}

1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291
void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float,
                                                           Node* candidate_key,
                                                           Label* if_same,
                                                           Label* if_not_same) {
  Label if_smi(this), if_keyisnan(this);

  GotoIf(TaggedIsSmi(candidate_key), &if_smi);
  GotoIfNot(IsHeapNumber(candidate_key), if_not_same);

  {
    // {candidate_key} is a heap number.
    Node* const candidate_float = LoadHeapNumberValue(candidate_key);
    GotoIf(Float64Equal(key_float, candidate_float), if_same);

    // SameValueZero needs to treat NaNs as equal. First check if {key_float}
    // is NaN.
    BranchIfFloat64IsNaN(key_float, &if_keyisnan, if_not_same);

    BIND(&if_keyisnan);
    {
      // Return true iff {candidate_key} is NaN.
      Branch(Float64Equal(candidate_float, candidate_float), if_not_same,
             if_same);
    }
  }

  BIND(&if_smi);
  {
    Node* const candidate_float = SmiToFloat64(candidate_key);
    Branch(Float64Equal(key_float, candidate_float), if_same, if_not_same);
  }
}

1292
TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) {
1293 1294
  TNode<HeapObject> table = CAST(Parameter(Descriptor::kTable));
  TNode<Smi> index = CAST(Parameter(Descriptor::kIndex));
1295 1296 1297
  Label return_index(this), return_zero(this);

  // Check if we need to update the {index}.
1298
  GotoIfNot(SmiLessThan(SmiConstant(0), index), &return_zero);
1299 1300

  // Check if the {table} was cleared.
1301 1302
  STATIC_ASSERT(OrderedHashMap::NumberOfDeletedElementsOffset() ==
                OrderedHashSet::NumberOfDeletedElementsOffset());
1303
  Node* number_of_deleted_elements = LoadAndUntagObjectField(
1304
      table, OrderedHashMap::NumberOfDeletedElementsOffset());
1305 1306
  STATIC_ASSERT(OrderedHashMap::kClearedTableSentinel ==
                OrderedHashSet::kClearedTableSentinel);
1307
  GotoIf(WordEqual(number_of_deleted_elements,
1308
                   IntPtrConstant(OrderedHashMap::kClearedTableSentinel)),
1309 1310 1311 1312 1313 1314 1315 1316 1317 1318
         &return_zero);

  VARIABLE(var_i, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_index, MachineRepresentation::kTagged, index);
  Label loop(this, {&var_i, &var_index});
  Goto(&loop);
  BIND(&loop);
  {
    Node* i = var_i.value();
    GotoIfNot(IntPtrLessThan(i, number_of_deleted_elements), &return_index);
1319 1320
    STATIC_ASSERT(OrderedHashMap::RemovedHolesIndex() ==
                  OrderedHashSet::RemovedHolesIndex());
1321
    TNode<Smi> removed_index = CAST(LoadFixedArrayElement(
1322
        CAST(table), i, OrderedHashMap::RemovedHolesIndex() * kTaggedSize));
1323
    GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
1324 1325
    Decrement(&var_index, 1, SMI_PARAMETERS);
    Increment(&var_i);
1326 1327 1328 1329 1330 1331 1332
    Goto(&loop);
  }

  BIND(&return_index);
  Return(var_index.value());

  BIND(&return_zero);
1333
  Return(SmiConstant(0));
1334 1335
}

1336
template <typename TableType>
1337 1338 1339
std::pair<TNode<TableType>, TNode<IntPtrT>>
CollectionsBuiltinsAssembler::Transition(
    TNode<TableType> const table, TNode<IntPtrT> const index,
1340
    UpdateInTransition const& update_in_transition) {
1341 1342
  TVARIABLE(IntPtrT, var_index, index);
  TVARIABLE(TableType, var_table, table);
1343 1344
  Label if_done(this), if_transition(this, Label::kDeferred);
  Branch(TaggedIsSmi(
1345
             LoadObjectField(var_table.value(), TableType::NextTableOffset())),
1346 1347 1348 1349 1350 1351 1352 1353
         &if_done, &if_transition);

  BIND(&if_transition);
  {
    Label loop(this, {&var_table, &var_index}), done_loop(this);
    Goto(&loop);
    BIND(&loop);
    {
1354 1355
      TNode<TableType> table = var_table.value();
      TNode<IntPtrT> index = var_index.value();
1356

1357
      TNode<Object> next_table =
1358
          LoadObjectField(table, TableType::NextTableOffset());
1359 1360
      GotoIf(TaggedIsSmi(next_table), &done_loop);

1361 1362
      var_table = CAST(next_table);
      var_index = SmiUntag(
1363
          CAST(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
1364
                           NoContextConstant(), table, SmiTag(index))));
1365
      Goto(&loop);
1366 1367 1368
    }
    BIND(&done_loop);

1369 1370
    // Update with the new {table} and {index}.
    update_in_transition(var_table.value(), var_index.value());
1371 1372 1373 1374
    Goto(&if_done);
  }

  BIND(&if_done);
1375
  return {var_table.value(), var_index.value()};
1376 1377
}

1378
template <typename IteratorType, typename TableType>
1379 1380 1381
std::pair<TNode<TableType>, TNode<IntPtrT>>
CollectionsBuiltinsAssembler::TransitionAndUpdate(
    TNode<IteratorType> const iterator) {
1382
  return Transition<TableType>(
1383
      CAST(LoadObjectField(iterator, IteratorType::kTableOffset)),
1384 1385 1386 1387 1388 1389 1390 1391 1392
      LoadAndUntagObjectField(iterator, IteratorType::kIndexOffset),
      [this, iterator](Node* const table, Node* const index) {
        // Update the {iterator} with the new state.
        StoreObjectField(iterator, IteratorType::kTableOffset, table);
        StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                                       SmiTag(index));
      });
}

1393
template <typename TableType>
1394 1395 1396 1397
std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>
CollectionsBuiltinsAssembler::NextSkipHoles(TNode<TableType> table,
                                            TNode<IntPtrT> index,
                                            Label* if_end) {
1398
  // Compute the used capacity for the {table}.
1399
  TNode<IntPtrT> number_of_buckets =
1400
      LoadAndUntagObjectField(table, TableType::NumberOfBucketsOffset());
1401
  TNode<IntPtrT> number_of_elements =
1402 1403 1404
      LoadAndUntagObjectField(table, TableType::NumberOfElementsOffset());
  TNode<IntPtrT> number_of_deleted_elements = LoadAndUntagObjectField(
      table, TableType::NumberOfDeletedElementsOffset());
1405
  TNode<IntPtrT> used_capacity =
1406 1407
      IntPtrAdd(number_of_elements, number_of_deleted_elements);

1408 1409 1410
  TNode<Object> entry_key;
  TNode<IntPtrT> entry_start_position;
  TVARIABLE(IntPtrT, var_index, index);
1411 1412 1413 1414 1415 1416 1417 1418
  Label loop(this, &var_index), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    GotoIfNot(IntPtrLessThan(var_index.value(), used_capacity), if_end);
    entry_start_position = IntPtrAdd(
        IntPtrMul(var_index.value(), IntPtrConstant(TableType::kEntrySize)),
        number_of_buckets);
1419 1420 1421
    entry_key = UnsafeLoadFixedArrayElement(
        table, entry_start_position,
        TableType::HashTableStartIndex() * kTaggedSize);
1422
    Increment(&var_index);
1423 1424 1425 1426
    Branch(IsTheHole(entry_key), &loop, &done_loop);
  }

  BIND(&done_loop);
1427 1428
  return std::tuple<TNode<Object>, TNode<IntPtrT>, TNode<IntPtrT>>{
      entry_key, entry_start_position, var_index.value()};
1429 1430
}

1431
TF_BUILTIN(MapPrototypeGet, CollectionsBuiltinsAssembler) {
1432
  Node* const receiver = Parameter(Descriptor::kReceiver);
1433
  Node* const key = Parameter(Descriptor::kKey);
1434 1435 1436 1437 1438
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1439 1440
  TNode<Smi> index = CAST(
      CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));
1441

1442 1443 1444
  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);
1445

1446
  BIND(&if_found);
1447
  Return(LoadFixedArrayElement(
1448
      CAST(table), SmiUntag(index),
1449
      (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1450
          kTaggedSize));
1451

1452
  BIND(&if_not_found);
1453
  Return(UndefinedConstant());
1454
}
1455

1456
TF_BUILTIN(MapPrototypeHas, CollectionsBuiltinsAssembler) {
1457
  Node* const receiver = Parameter(Descriptor::kReceiver);
1458
  Node* const key = Parameter(Descriptor::kKey);
1459 1460 1461 1462 1463
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1464 1465
  TNode<Smi> index = CAST(
      CallBuiltin(Builtins::kFindOrderedHashMapEntry, context, table, key));
1466

1467 1468 1469
  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);
1470

1471
  BIND(&if_found);
1472 1473
  Return(TrueConstant());

1474
  BIND(&if_not_found);
1475
  Return(FalseConstant());
1476 1477
}

1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494
Node* CollectionsBuiltinsAssembler::NormalizeNumberKey(Node* const key) {
  VARIABLE(result, MachineRepresentation::kTagged, key);
  Label done(this);

  GotoIf(TaggedIsSmi(key), &done);
  GotoIfNot(IsHeapNumber(key), &done);
  Node* const number = LoadHeapNumberValue(key);
  GotoIfNot(Float64Equal(number, Float64Constant(0.0)), &done);
  // We know the value is zero, so we take the key to be Smi 0.
  // Another option would be to normalize to Smi here.
  result.Bind(SmiConstant(0));
  Goto(&done);

  BIND(&done);
  return result.value();
}

1495
TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) {
1496 1497 1498 1499 1500 1501 1502 1503 1504
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const value = Parameter(Descriptor::kValue);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set");

  key = NormalizeNumberKey(key);

1505 1506
  TNode<OrderedHashMap> const table =
      CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1507 1508 1509 1510 1511

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

1512 1513 1514
  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);
1515 1516 1517 1518 1519

  BIND(&entry_found);
  // If we found the entry, we just store the value there.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value,
                         UPDATE_WRITE_BARRIER,
1520 1521
                         kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
                                        OrderedHashMap::kValueOffset));
1522 1523 1524 1525 1526 1527
  Return(receiver);

  Label no_hash(this), add_entry(this), store_new_entry(this);
  BIND(&not_found);
  {
    // If we have a hash code, we can start adding the new entry.
1528 1529
    GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                             IntPtrConstant(0)),
1530 1531 1532
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
1533
    entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1534 1535 1536 1537 1538 1539
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
1540
  TVARIABLE(OrderedHashMap, table_var, table);
1541 1542
  {
    // Check we have enough space for the entry.
1543 1544
    number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
        table, OrderedHashMap::NumberOfBucketsIndex()))));
1545 1546 1547 1548

    STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
1549
        CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())));
1550
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
1551
        table, OrderedHashMap::NumberOfDeletedElementsOffset())));
1552 1553 1554 1555 1556 1557
    occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
    GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

    // We do not have enough space, grow the table and reload the relevant
    // fields.
    CallRuntime(Runtime::kMapGrow, context, receiver);
1558
    table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1559
    number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1560
        table_var.value(), OrderedHashMap::NumberOfBucketsIndex()))));
1561
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1562
        table_var.value(), OrderedHashMap::NumberOfElementsOffset())));
1563
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1564
        table_var.value(), OrderedHashMap::NumberOfDeletedElementsOffset())));
1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576
    occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
    Goto(&store_new_entry);
  }
  BIND(&store_new_entry);
  // Store the key, value and connect the element to the bucket chain.
  StoreOrderedHashMapNewEntry(table_var.value(), key, value,
                              entry_start_position_or_hash.value(),
                              number_of_buckets.value(), occupancy.value());
  Return(receiver);
}

void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry(
1577 1578
    TNode<OrderedHashMap> const table, Node* const key, Node* const value,
    Node* const hash, Node* const number_of_buckets, Node* const occupancy) {
1579 1580
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1581 1582
  TNode<Smi> bucket_entry = CAST(UnsafeLoadFixedArrayElement(
      table, bucket, OrderedHashMap::HashTableStartIndex() * kTaggedSize));
1583 1584 1585 1586 1587

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
      number_of_buckets);
1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598
  UnsafeStoreFixedArrayElement(
      table, entry_start, key, UPDATE_WRITE_BARRIER,
      kTaggedSize * OrderedHashMap::HashTableStartIndex());
  UnsafeStoreFixedArrayElement(
      table, entry_start, value, UPDATE_WRITE_BARRIER,
      kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
                     OrderedHashMap::kValueOffset));
  UnsafeStoreFixedArrayElement(
      table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
      kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
                     OrderedHashMap::kChainOffset));
1599 1600

  // Update the bucket head.
1601 1602 1603
  UnsafeStoreFixedArrayElement(
      table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
      OrderedHashMap::HashTableStartIndex() * kTaggedSize);
1604 1605

  // Bump the elements count.
1606
  TNode<Smi> const number_of_elements =
1607 1608 1609
      CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
  StoreObjectFieldNoWriteBarrier(table,
                                 OrderedHashMap::NumberOfElementsOffset(),
1610 1611 1612
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

1613
TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
1614 1615 1616 1617 1618 1619 1620
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.delete");

1621 1622
  TNode<OrderedHashMap> const table =
      CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1623 1624 1625 1626 1627

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

1628 1629 1630
  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);
1631 1632 1633 1634 1635 1636 1637 1638

  BIND(&not_found);
  Return(FalseConstant());

  BIND(&entry_found);
  // If we found the entry, mark the entry as deleted.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
1639
                         kTaggedSize * OrderedHashMap::HashTableStartIndex());
1640 1641
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
1642 1643
                         kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
                                        OrderedHashMap::kValueOffset));
1644 1645

  // Decrement the number of elements, increment the number of deleted elements.
1646
  TNode<Smi> const number_of_elements = SmiSub(
1647
      CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())),
1648
      SmiConstant(1));
1649 1650
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashMap::NumberOfElementsOffset(), number_of_elements);
1651
  TNode<Smi> const number_of_deleted =
1652
      SmiAdd(CAST(LoadObjectField(
1653
                 table, OrderedHashMap::NumberOfDeletedElementsOffset())),
1654
             SmiConstant(1));
1655
  StoreObjectFieldNoWriteBarrier(
1656 1657
      table, OrderedHashMap::NumberOfDeletedElementsOffset(),
      number_of_deleted);
1658

1659 1660
  TNode<Smi> const number_of_buckets = CAST(
      LoadFixedArrayElement(table, OrderedHashMap::NumberOfBucketsIndex()));
1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673

  // If there fewer elements than #buckets / 2, shrink the table.
  Label shrink(this);
  GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                     number_of_buckets),
         &shrink);
  Return(TrueConstant());

  BIND(&shrink);
  CallRuntime(Runtime::kMapShrink, context, receiver);
  Return(TrueConstant());
}

1674
TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler) {
1675 1676 1677 1678 1679 1680 1681 1682
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");

  key = NormalizeNumberKey(key);

1683 1684
  TNode<OrderedHashSet> const table =
      CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&entry_found);
  // The entry was found, there is nothing to do.
  Return(receiver);

  Label no_hash(this), add_entry(this), store_new_entry(this);
  BIND(&not_found);
  {
    // If we have a hash code, we can start adding the new entry.
1702 1703
    GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                             IntPtrConstant(0)),
1704 1705 1706
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
1707
    entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1708 1709 1710 1711 1712 1713
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
1714
  TVARIABLE(OrderedHashSet, table_var, table);
1715 1716
  {
    // Check we have enough space for the entry.
1717 1718
    number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
        table, OrderedHashSet::NumberOfBucketsIndex()))));
1719 1720 1721 1722

    STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
1723
        CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())));
1724
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
1725
        table, OrderedHashSet::NumberOfDeletedElementsOffset())));
1726 1727 1728 1729 1730 1731
    occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted));
    GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

    // We do not have enough space, grow the table and reload the relevant
    // fields.
    CallRuntime(Runtime::kSetGrow, context, receiver);
1732
    table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1733
    number_of_buckets.Bind(SmiUntag(CAST(UnsafeLoadFixedArrayElement(
1734
        table_var.value(), OrderedHashSet::NumberOfBucketsIndex()))));
1735
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
1736
        table_var.value(), OrderedHashSet::NumberOfElementsOffset())));
1737
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
1738
        table_var.value(), OrderedHashSet::NumberOfDeletedElementsOffset())));
1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750
    occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted));
    Goto(&store_new_entry);
  }
  BIND(&store_new_entry);
  // Store the key, value and connect the element to the bucket chain.
  StoreOrderedHashSetNewEntry(table_var.value(), key,
                              entry_start_position_or_hash.value(),
                              number_of_buckets.value(), occupancy.value());
  Return(receiver);
}

void CollectionsBuiltinsAssembler::StoreOrderedHashSetNewEntry(
1751
    TNode<OrderedHashSet> const table, Node* const key, Node* const hash,
1752 1753 1754
    Node* const number_of_buckets, Node* const occupancy) {
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
1755 1756
  TNode<Smi> bucket_entry = CAST(UnsafeLoadFixedArrayElement(
      table, bucket, OrderedHashSet::HashTableStartIndex() * kTaggedSize));
1757 1758 1759 1760 1761

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
      number_of_buckets);
1762 1763 1764 1765 1766 1767 1768
  UnsafeStoreFixedArrayElement(
      table, entry_start, key, UPDATE_WRITE_BARRIER,
      kTaggedSize * OrderedHashSet::HashTableStartIndex());
  UnsafeStoreFixedArrayElement(
      table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
      kTaggedSize * (OrderedHashSet::HashTableStartIndex() +
                     OrderedHashSet::kChainOffset));
1769 1770

  // Update the bucket head.
1771 1772 1773
  UnsafeStoreFixedArrayElement(
      table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
      OrderedHashSet::HashTableStartIndex() * kTaggedSize);
1774 1775

  // Bump the elements count.
1776
  TNode<Smi> const number_of_elements =
1777 1778 1779
      CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
  StoreObjectFieldNoWriteBarrier(table,
                                 OrderedHashSet::NumberOfElementsOffset(),
1780 1781 1782
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

1783
TF_BUILTIN(SetPrototypeDelete, CollectionsBuiltinsAssembler) {
1784 1785 1786 1787 1788 1789 1790
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.delete");

1791 1792
  TNode<OrderedHashSet> const table =
      CAST(LoadObjectField(receiver, JSMap::kTableOffset));
1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808

  VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

  TryLookupOrderedHashTableIndex<OrderedHashSet>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);

  BIND(&not_found);
  Return(FalseConstant());

  BIND(&entry_found);
  // If we found the entry, mark the entry as deleted.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
1809
                         kTaggedSize * OrderedHashSet::HashTableStartIndex());
1810 1811

  // Decrement the number of elements, increment the number of deleted elements.
1812
  TNode<Smi> const number_of_elements = SmiSub(
1813
      CAST(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset())),
1814
      SmiConstant(1));
1815 1816
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashSet::NumberOfElementsOffset(), number_of_elements);
1817
  TNode<Smi> const number_of_deleted =
1818
      SmiAdd(CAST(LoadObjectField(
1819
                 table, OrderedHashSet::NumberOfDeletedElementsOffset())),
1820
             SmiConstant(1));
1821
  StoreObjectFieldNoWriteBarrier(
1822 1823
      table, OrderedHashSet::NumberOfDeletedElementsOffset(),
      number_of_deleted);
1824

1825 1826
  TNode<Smi> const number_of_buckets = CAST(
      LoadFixedArrayElement(table, OrderedHashSet::NumberOfBucketsIndex()));
1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839

  // If there fewer elements than #buckets / 2, shrink the table.
  Label shrink(this);
  GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                     number_of_buckets),
         &shrink);
  Return(TrueConstant());

  BIND(&shrink);
  CallRuntime(Runtime::kSetShrink, context, receiver);
  Return(TrueConstant());
}

1840 1841 1842 1843 1844 1845 1846 1847 1848
TF_BUILTIN(MapPrototypeEntries, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.entries");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
}

1849 1850 1851 1852 1853 1854
TF_BUILTIN(MapPrototypeGetSize, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "get Map.prototype.size");
  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
1855
  Return(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset()));
1856 1857
}

1858 1859
TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Map.prototype.forEach";
1860 1861
  Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
  Node* const context = Parameter(Descriptor::kContext);
1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873
  CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
  Node* const receiver = args.GetReceiver();
  Node* const callback = args.GetOptionalArgumentValue(0);
  Node* const this_arg = args.GetOptionalArgumentValue(1);

  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, kMethodName);

  // Ensure that {callback} is actually callable.
  Label callback_not_callable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(callback), &callback_not_callable);
  GotoIfNot(IsCallable(callback), &callback_not_callable);

1874 1875 1876
  TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
  TVARIABLE(OrderedHashMap, var_table,
            CAST(LoadObjectField(receiver, JSMap::kTableOffset)));
1877 1878 1879 1880 1881 1882
  Label loop(this, {&var_index, &var_table}), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    // Transition {table} and {index} if there was any modification to
    // the {receiver} while we're iterating.
1883 1884
    TNode<IntPtrT> index = var_index.value();
    TNode<OrderedHashMap> table = var_table.value();
1885 1886 1887 1888
    std::tie(table, index) =
        Transition<OrderedHashMap>(table, index, [](Node*, Node*) {});

    // Read the next entry from the {table}, skipping holes.
1889 1890
    TNode<Object> entry_key;
    TNode<IntPtrT> entry_start_position;
1891 1892 1893 1894 1895 1896
    std::tie(entry_key, entry_start_position, index) =
        NextSkipHoles<OrderedHashMap>(table, index, &done_loop);

    // Load the entry value as well.
    Node* entry_value = LoadFixedArrayElement(
        table, entry_start_position,
1897
        (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1898
            kTaggedSize);
1899 1900 1901 1902 1903 1904 1905

    // Invoke the {callback} passing the {entry_key}, {entry_value} and the
    // {receiver}.
    CallJS(CodeFactory::Call(isolate()), context, callback, this_arg,
           entry_value, entry_key, receiver);

    // Continue with the next entry.
1906 1907
    var_index = index;
    var_table = table;
1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920
    Goto(&loop);
  }

  BIND(&done_loop);
  args.PopAndReturn(UndefinedConstant());

  BIND(&callback_not_callable);
  {
    CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
    Unreachable();
  }
}

1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
TF_BUILTIN(MapPrototypeKeys, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.keys");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_KEY_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(MapPrototypeValues, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE,
                         "Map.prototype.values");
  Return(AllocateJSCollectionIterator<JSMapIterator>(
      context, Context::MAP_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(MapIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Map Iterator.prototype.next";
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);

  // Ensure that the {receiver} is actually a JSMapIterator.
  Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
  Node* const receiver_instance_type = LoadInstanceType(receiver);
  GotoIf(
      InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_VALUE_ITERATOR_TYPE),
      &if_receiver_valid);
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
         &if_receiver_valid);
  Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
         &if_receiver_valid, &if_receiver_invalid);
  BIND(&if_receiver_invalid);
1955 1956
  ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
                 StringConstant(kMethodName), receiver);
1957 1958 1959 1960
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1961 1962 1963
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);
1964 1965

  // Transition the {receiver} table if necessary.
1966 1967
  TNode<OrderedHashMap> table;
  TNode<IntPtrT> index;
1968
  std::tie(table, index) =
1969
      TransitionAndUpdate<JSMapIterator, OrderedHashMap>(CAST(receiver));
1970 1971

  // Read the next entry from the {table}, skipping holes.
1972 1973
  TNode<Object> entry_key;
  TNode<IntPtrT> entry_start_position;
1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985
  std::tie(entry_key, entry_start_position, index) =
      NextSkipHoles<OrderedHashMap>(table, index, &return_end);
  StoreObjectFieldNoWriteBarrier(receiver, JSMapIterator::kIndexOffset,
                                 SmiTag(index));
  var_value.Bind(entry_key);
  var_done.Bind(FalseConstant());

  // Check how to return the {key} (depending on {receiver} type).
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_MAP_KEY_ITERATOR_TYPE),
         &return_value);
  var_value.Bind(LoadFixedArrayElement(
      table, entry_start_position,
1986
      (OrderedHashMap::HashTableStartIndex() + OrderedHashMap::kValueOffset) *
1987
          kTaggedSize));
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007
  Branch(InstanceTypeEqual(receiver_instance_type, JS_MAP_VALUE_ITERATOR_TYPE),
         &return_value, &return_entry);

  BIND(&return_entry);
  {
    Node* result =
        AllocateJSIteratorResultForEntry(context, entry_key, var_value.value());
    Return(result);
  }

  BIND(&return_value);
  {
    Node* result =
        AllocateJSIteratorResult(context, var_value.value(), var_done.value());
    Return(result);
  }

  BIND(&return_end);
  {
    StoreObjectFieldRoot(receiver, JSMapIterator::kTableOffset,
2008
                         RootIndex::kEmptyOrderedHashMap);
2009 2010 2011 2012
    Goto(&return_value);
  }
}

2013
TF_BUILTIN(SetPrototypeHas, CollectionsBuiltinsAssembler) {
2014 2015 2016 2017 2018 2019 2020
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
2021 2022 2023 2024 2025

  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0));
  Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
2026
      if_key_bigint(this), entry_found(this), not_found(this), done(this);
2027 2028

  GotoIf(TaggedIsSmi(key), &if_key_smi);
2029 2030 2031 2032 2033 2034 2035

  Node* key_map = LoadMap(key);
  Node* key_instance_type = LoadMapInstanceType(key_map);

  GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
  GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
  GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057

  FindOrderedHashTableEntryForOtherKey<OrderedHashSet>(
      context, table, key, &entry_start_position, &entry_found, &not_found);

  BIND(&if_key_smi);
  {
    FindOrderedHashTableEntryForSmiKey<OrderedHashSet>(
        table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&if_key_string);
  {
    FindOrderedHashTableEntryForStringKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

  BIND(&if_key_heap_number);
  {
    FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

2058 2059 2060 2061 2062 2063
  BIND(&if_key_bigint);
  {
    FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

2064 2065 2066 2067 2068
  BIND(&entry_found);
  Return(TrueConstant());

  BIND(&not_found);
  Return(FalseConstant());
2069 2070
}

2071 2072 2073 2074 2075 2076 2077 2078 2079
TF_BUILTIN(SetPrototypeEntries, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.entries");
  Return(AllocateJSCollectionIterator<JSSetIterator>(
      context, Context::SET_KEY_VALUE_ITERATOR_MAP_INDEX, receiver));
}

2080 2081 2082 2083 2084 2085
TF_BUILTIN(SetPrototypeGetSize, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "get Set.prototype.size");
  Node* const table = LoadObjectField(receiver, JSSet::kTableOffset);
2086
  Return(LoadObjectField(table, OrderedHashSet::NumberOfElementsOffset()));
2087 2088
}

2089 2090
TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Set.prototype.forEach";
2091 2092
  Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
  Node* const context = Parameter(Descriptor::kContext);
2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104
  CodeStubArguments args(this, ChangeInt32ToIntPtr(argc));
  Node* const receiver = args.GetReceiver();
  Node* const callback = args.GetOptionalArgumentValue(0);
  Node* const this_arg = args.GetOptionalArgumentValue(1);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, kMethodName);

  // Ensure that {callback} is actually callable.
  Label callback_not_callable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(callback), &callback_not_callable);
  GotoIfNot(IsCallable(callback), &callback_not_callable);

2105 2106 2107
  TVARIABLE(IntPtrT, var_index, IntPtrConstant(0));
  TVARIABLE(OrderedHashSet, var_table,
            CAST(LoadObjectField(receiver, JSSet::kTableOffset)));
2108 2109 2110 2111 2112 2113
  Label loop(this, {&var_index, &var_table}), done_loop(this);
  Goto(&loop);
  BIND(&loop);
  {
    // Transition {table} and {index} if there was any modification to
    // the {receiver} while we're iterating.
2114 2115
    TNode<IntPtrT> index = var_index.value();
    TNode<OrderedHashSet> table = var_table.value();
2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129
    std::tie(table, index) =
        Transition<OrderedHashSet>(table, index, [](Node*, Node*) {});

    // Read the next entry from the {table}, skipping holes.
    Node* entry_key;
    Node* entry_start_position;
    std::tie(entry_key, entry_start_position, index) =
        NextSkipHoles<OrderedHashSet>(table, index, &done_loop);

    // Invoke the {callback} passing the {entry_key} (twice) and the {receiver}.
    CallJS(CodeFactory::Call(isolate()), context, callback, this_arg, entry_key,
           entry_key, receiver);

    // Continue with the next entry.
2130 2131
    var_index = index;
    var_table = table;
2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144
    Goto(&loop);
  }

  BIND(&done_loop);
  args.PopAndReturn(UndefinedConstant());

  BIND(&callback_not_callable);
  {
    CallRuntime(Runtime::kThrowCalledNonCallable, context, callback);
    Unreachable();
  }
}

2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168
TF_BUILTIN(SetPrototypeValues, CollectionsBuiltinsAssembler) {
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);
  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE,
                         "Set.prototype.values");
  Return(AllocateJSCollectionIterator<JSSetIterator>(
      context, Context::SET_VALUE_ITERATOR_MAP_INDEX, receiver));
}

TF_BUILTIN(SetIteratorPrototypeNext, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Set Iterator.prototype.next";
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const context = Parameter(Descriptor::kContext);

  // Ensure that the {receiver} is actually a JSSetIterator.
  Label if_receiver_valid(this), if_receiver_invalid(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(receiver), &if_receiver_invalid);
  Node* const receiver_instance_type = LoadInstanceType(receiver);
  GotoIf(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
         &if_receiver_valid);
  Branch(
      InstanceTypeEqual(receiver_instance_type, JS_SET_KEY_VALUE_ITERATOR_TYPE),
      &if_receiver_valid, &if_receiver_invalid);
  BIND(&if_receiver_invalid);
2169 2170
  ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
                 StringConstant(kMethodName), receiver);
2171 2172 2173 2174
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
2175 2176 2177
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);
2178 2179

  // Transition the {receiver} table if necessary.
2180 2181
  TNode<OrderedHashSet> table;
  TNode<IntPtrT> index;
2182
  std::tie(table, index) =
2183
      TransitionAndUpdate<JSSetIterator, OrderedHashSet>(CAST(receiver));
2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215

  // Read the next entry from the {table}, skipping holes.
  Node* entry_key;
  Node* entry_start_position;
  std::tie(entry_key, entry_start_position, index) =
      NextSkipHoles<OrderedHashSet>(table, index, &return_end);
  StoreObjectFieldNoWriteBarrier(receiver, JSSetIterator::kIndexOffset,
                                 SmiTag(index));
  var_value.Bind(entry_key);
  var_done.Bind(FalseConstant());

  // Check how to return the {key} (depending on {receiver} type).
  Branch(InstanceTypeEqual(receiver_instance_type, JS_SET_VALUE_ITERATOR_TYPE),
         &return_value, &return_entry);

  BIND(&return_entry);
  {
    Node* result = AllocateJSIteratorResultForEntry(context, var_value.value(),
                                                    var_value.value());
    Return(result);
  }

  BIND(&return_value);
  {
    Node* result =
        AllocateJSIteratorResult(context, var_value.value(), var_done.value());
    Return(result);
  }

  BIND(&return_end);
  {
    StoreObjectFieldRoot(receiver, JSSetIterator::kTableOffset,
2216
                         RootIndex::kEmptyOrderedHashSet);
2217 2218 2219 2220
    Goto(&return_value);
  }
}

2221 2222
template <typename CollectionType>
void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
2223 2224
    Node* const table, Node* const key, Node* const context, Variable* result,
    Label* if_entry_found, Label* if_not_found) {
2225 2226
  Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
      if_key_bigint(this);
2227 2228

  GotoIf(TaggedIsSmi(key), &if_key_smi);
2229 2230 2231 2232 2233 2234 2235

  Node* key_map = LoadMap(key);
  Node* key_instance_type = LoadMapInstanceType(key_map);

  GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
  GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
  GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);
2236

2237
  FindOrderedHashTableEntryForOtherKey<CollectionType>(
2238
      context, table, key, result, if_entry_found, if_not_found);
2239 2240 2241

  BIND(&if_key_smi);
  {
2242
    FindOrderedHashTableEntryForSmiKey<CollectionType>(
2243
        table, key, result, if_entry_found, if_not_found);
2244 2245 2246 2247
  }

  BIND(&if_key_string);
  {
2248
    FindOrderedHashTableEntryForStringKey<CollectionType>(
2249
        context, table, key, result, if_entry_found, if_not_found);
2250 2251 2252 2253
  }

  BIND(&if_key_heap_number);
  {
2254
    FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
2255
        context, table, key, result, if_entry_found, if_not_found);
2256
  }
2257 2258 2259 2260 2261 2262

  BIND(&if_key_bigint);
  {
    FindOrderedHashTableEntryForBigIntKey<CollectionType>(
        context, table, key, result, if_entry_found, if_not_found);
  }
2263 2264
}

2265
TF_BUILTIN(FindOrderedHashMapEntry, CollectionsBuiltinsAssembler) {
2266 2267 2268 2269 2270 2271 2272 2273
  Node* const table = Parameter(Descriptor::kTable);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
           IntPtrConstant(0));
  Label entry_found(this), not_found(this);

2274 2275
  TryLookupOrderedHashTableIndex<OrderedHashMap>(
      table, key, context, &entry_start_position, &entry_found, &not_found);
2276 2277

  BIND(&entry_found);
2278
  Return(SmiTag(entry_start_position.value()));
2279 2280

  BIND(&not_found);
2281
  Return(SmiConstant(-1));
2282 2283
}

2284
class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
2285 2286
 public:
  explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
2287
      : BaseCollectionsAssembler(state) {}
2288

2289
 protected:
2290
  void AddEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2291 2292 2293
                TNode<Object> key, TNode<Object> value,
                TNode<IntPtrT> number_of_elements);

2294
  TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
2295
                              TNode<IntPtrT> at_least_space_for) override;
2296

2297 2298 2299 2300
  // Generates and sets the identity for a JSRececiver.
  TNode<Smi> CreateIdentityHash(TNode<Object> receiver);
  TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity);

2301
  // Builds code that finds the EphemeronHashTable entry for a {key} using the
2302 2303 2304 2305
  // comparison code generated by {key_compare}. The key index is returned if
  // the {key} is found.
  typedef std::function<void(TNode<Object> entry_key, Label* if_same)>
      KeyComparator;
2306
  TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash,
2307 2308 2309
                              TNode<IntPtrT> entry_mask,
                              const KeyComparator& key_compare);

2310 2311
  // Builds code that finds an EphemeronHashTable entry available for a new
  // entry.
2312
  TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table,
2313 2314 2315
                                          TNode<IntPtrT> key_hash,
                                          TNode<IntPtrT> entry_mask);

2316
  // Builds code that finds the EphemeronHashTable entry with key that matches
2317 2318
  // {key} and returns the entry's key index. If {key} cannot be found, jumps to
  // {if_not_found}.
2319
  TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key,
2320 2321 2322 2323 2324 2325 2326 2327 2328
                                    TNode<IntPtrT> hash,
                                    TNode<IntPtrT> entry_mask,
                                    Label* if_not_found);

  TNode<Word32T> InsufficientCapacityToAdd(TNode<IntPtrT> capacity,
                                           TNode<IntPtrT> number_of_elements,
                                           TNode<IntPtrT> number_of_deleted);
  TNode<IntPtrT> KeyIndexFromEntry(TNode<IntPtrT> entry);

2329 2330 2331 2332 2333 2334
  TNode<IntPtrT> LoadNumberOfElements(TNode<EphemeronHashTable> table,
                                      int offset);
  TNode<IntPtrT> LoadNumberOfDeleted(TNode<EphemeronHashTable> table,
                                     int offset = 0);
  TNode<EphemeronHashTable> LoadTable(TNode<JSWeakCollection> collection);
  TNode<IntPtrT> LoadTableCapacity(TNode<EphemeronHashTable> table);
2335

2336
  void RemoveEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2337 2338 2339 2340 2341 2342 2343
                   TNode<IntPtrT> number_of_elements);
  TNode<BoolT> ShouldRehash(TNode<IntPtrT> number_of_elements,
                            TNode<IntPtrT> number_of_deleted);
  TNode<Word32T> ShouldShrink(TNode<IntPtrT> capacity,
                              TNode<IntPtrT> number_of_elements);
  TNode<IntPtrT> ValueIndexFromKeyIndex(TNode<IntPtrT> key_index);
};
2344

2345
void WeakCollectionsBuiltinsAssembler::AddEntry(
2346 2347
    TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
    TNode<Object> key, TNode<Object> value, TNode<IntPtrT> number_of_elements) {
2348
  // See EphemeronHashTable::AddEntry().
2349
  TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
2350 2351
  UnsafeStoreFixedArrayElement(table, key_index, key,
                               UPDATE_EPHEMERON_KEY_WRITE_BARRIER);
2352
  UnsafeStoreFixedArrayElement(table, value_index, value);
2353 2354

  // See HashTableBase::ElementAdded().
2355 2356 2357
  UnsafeStoreFixedArrayElement(
      table, EphemeronHashTable::kNumberOfElementsIndex,
      SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2358
}
2359

2360 2361 2362 2363 2364 2365 2366 2367 2368 2369
TNode<Object> WeakCollectionsBuiltinsAssembler::AllocateTable(
    Variant variant, TNode<Context> context,
    TNode<IntPtrT> at_least_space_for) {
  // See HashTable::New().
  CSA_ASSERT(this,
             IntPtrLessThanOrEqual(IntPtrConstant(0), at_least_space_for));
  TNode<IntPtrT> capacity = HashTableComputeCapacity(at_least_space_for);

  // See HashTable::NewInternal().
  TNode<IntPtrT> length = KeyIndexFromEntry(capacity);
2370 2371
  TNode<FixedArray> table = CAST(
      AllocateFixedArray(HOLEY_ELEMENTS, length, kAllowLargeObjectAllocation));
2372

2373
  RootIndex map_root_index = EphemeronHashTableShape::GetMapRootIndex();
2374
  StoreMapNoWriteBarrier(table, map_root_index);
2375
  StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2376
                         SmiConstant(0), SKIP_WRITE_BARRIER);
2377 2378
  StoreFixedArrayElement(table,
                         EphemeronHashTable::kNumberOfDeletedElementsIndex,
2379
                         SmiConstant(0), SKIP_WRITE_BARRIER);
2380
  StoreFixedArrayElement(table, EphemeronHashTable::kCapacityIndex,
2381
                         SmiFromIntPtr(capacity), SKIP_WRITE_BARRIER);
2382 2383 2384

  TNode<IntPtrT> start = KeyIndexFromEntry(IntPtrConstant(0));
  FillFixedArrayWithValue(HOLEY_ELEMENTS, table, start, length,
2385
                          RootIndex::kUndefinedValue);
2386 2387 2388
  return table;
}

2389 2390
TNode<Smi> WeakCollectionsBuiltinsAssembler::CreateIdentityHash(
    TNode<Object> key) {
2391 2392
  TNode<ExternalReference> function_addr =
      ExternalConstant(ExternalReference::jsreceiver_create_identity_hash());
2393 2394
  TNode<ExternalReference> isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));
2395

2396 2397
  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();
2398

2399 2400 2401
  return CAST(CallCFunction(function_addr, type_tagged,
                            std::make_pair(type_ptr, isolate_ptr),
                            std::make_pair(type_tagged, key)));
2402 2403 2404 2405 2406 2407 2408 2409
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::EntryMask(
    TNode<IntPtrT> capacity) {
  return IntPtrSub(capacity, IntPtrConstant(1));
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndex(
2410
    TNode<HeapObject> table, TNode<IntPtrT> key_hash, TNode<IntPtrT> entry_mask,
2411
    const KeyComparator& key_compare) {
2412
  // See HashTable::FirstProbe().
2413 2414
  TVARIABLE(IntPtrT, var_entry, WordAnd(key_hash, entry_mask));
  TVARIABLE(IntPtrT, var_count, IntPtrConstant(0));
2415 2416

  Variable* loop_vars[] = {&var_count, &var_entry};
2417
  Label loop(this, arraysize(loop_vars), loop_vars), if_found(this);
2418 2419
  Goto(&loop);
  BIND(&loop);
2420
  TNode<IntPtrT> key_index;
2421
  {
2422
    key_index = KeyIndexFromEntry(var_entry.value());
2423 2424
    TNode<Object> entry_key =
        UnsafeLoadFixedArrayElement(CAST(table), key_index);
2425

2426
    key_compare(entry_key, &if_found);
2427 2428

    // See HashTable::NextProbe().
2429
    Increment(&var_count);
2430 2431
    var_entry =
        WordAnd(IntPtrAdd(var_entry.value(), var_count.value()), entry_mask);
2432 2433 2434
    Goto(&loop);
  }

2435 2436 2437 2438 2439
  BIND(&if_found);
  return key_index;
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForInsertion(
2440 2441
    TNode<HeapObject> table, TNode<IntPtrT> key_hash,
    TNode<IntPtrT> entry_mask) {
2442 2443 2444 2445 2446 2447 2448 2449 2450
  // See HashTable::FindInsertionEntry().
  auto is_not_live = [&](TNode<Object> entry_key, Label* if_found) {
    // This is the the negative form BaseShape::IsLive().
    GotoIf(Word32Or(IsTheHole(entry_key), IsUndefined(entry_key)), if_found);
  };
  return FindKeyIndex(table, key_hash, entry_mask, is_not_live);
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForKey(
2451
    TNode<HeapObject> table, TNode<Object> key, TNode<IntPtrT> hash,
2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466
    TNode<IntPtrT> entry_mask, Label* if_not_found) {
  // See HashTable::FindEntry().
  auto match_key_or_exit_on_empty = [&](TNode<Object> entry_key,
                                        Label* if_same) {
    GotoIf(IsUndefined(entry_key), if_not_found);
    GotoIf(WordEqual(entry_key, key), if_same);
  };
  return FindKeyIndex(table, hash, entry_mask, match_key_or_exit_on_empty);
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::KeyIndexFromEntry(
    TNode<IntPtrT> entry) {
  // See HashTable::KeyAt().
  // (entry * kEntrySize) + kElementsStartIndex + kEntryKeyIndex
  return IntPtrAdd(
2467 2468 2469
      IntPtrMul(entry, IntPtrConstant(EphemeronHashTable::kEntrySize)),
      IntPtrConstant(EphemeronHashTable::kElementsStartIndex +
                     EphemeronHashTable::kEntryKeyIndex));
2470 2471 2472
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfElements(
2473
    TNode<EphemeronHashTable> table, int offset) {
2474
  TNode<IntPtrT> number_of_elements = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
2475
      table, EphemeronHashTable::kNumberOfElementsIndex)));
2476 2477 2478 2479
  return IntPtrAdd(number_of_elements, IntPtrConstant(offset));
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfDeleted(
2480
    TNode<EphemeronHashTable> table, int offset) {
2481
  TNode<IntPtrT> number_of_deleted = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
2482
      table, EphemeronHashTable::kNumberOfDeletedElementsIndex)));
2483 2484 2485
  return IntPtrAdd(number_of_deleted, IntPtrConstant(offset));
}

2486 2487
TNode<EphemeronHashTable> WeakCollectionsBuiltinsAssembler::LoadTable(
    TNode<JSWeakCollection> collection) {
2488
  return CAST(LoadObjectField(collection, JSWeakCollection::kTableOffset));
2489 2490 2491
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadTableCapacity(
2492
    TNode<EphemeronHashTable> table) {
2493 2494
  return SmiUntag(CAST(
      UnsafeLoadFixedArrayElement(table, EphemeronHashTable::kCapacityIndex)));
2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514
}

TNode<Word32T> WeakCollectionsBuiltinsAssembler::InsufficientCapacityToAdd(
    TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements,
    TNode<IntPtrT> number_of_deleted) {
  // This is the negative form of HashTable::HasSufficientCapacityToAdd().
  // Return true if:
  //   - more than 50% of the available space are deleted elements
  //   - less than 50% will be available
  TNode<IntPtrT> available = IntPtrSub(capacity, number_of_elements);
  TNode<IntPtrT> half_available = WordShr(available, 1);
  TNode<IntPtrT> needed_available = WordShr(number_of_elements, 1);
  return Word32Or(
      // deleted > half
      IntPtrGreaterThan(number_of_deleted, half_available),
      // elements + needed available > capacity
      IntPtrGreaterThan(IntPtrAdd(number_of_elements, needed_available),
                        capacity));
}

2515
void WeakCollectionsBuiltinsAssembler::RemoveEntry(
2516
    TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index,
2517
    TNode<IntPtrT> number_of_elements) {
2518
  // See EphemeronHashTable::RemoveEntry().
2519 2520 2521 2522 2523 2524
  TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
  StoreFixedArrayElement(table, key_index, TheHoleConstant());
  StoreFixedArrayElement(table, value_index, TheHoleConstant());

  // See HashTableBase::ElementRemoved().
  TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table, 1);
2525
  StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2526
                         SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2527 2528
  StoreFixedArrayElement(table,
                         EphemeronHashTable::kNumberOfDeletedElementsIndex,
2529
                         SmiFromIntPtr(number_of_deleted), SKIP_WRITE_BARRIER);
2530 2531
}

2532 2533 2534 2535 2536 2537 2538
TNode<BoolT> WeakCollectionsBuiltinsAssembler::ShouldRehash(
    TNode<IntPtrT> number_of_elements, TNode<IntPtrT> number_of_deleted) {
  // Rehash if more than 33% of the entries are deleted.
  return IntPtrGreaterThanOrEqual(WordShl(number_of_deleted, 1),
                                  number_of_elements);
}

2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554
TNode<Word32T> WeakCollectionsBuiltinsAssembler::ShouldShrink(
    TNode<IntPtrT> capacity, TNode<IntPtrT> number_of_elements) {
  // See HashTable::Shrink().
  TNode<IntPtrT> quarter_capacity = WordShr(capacity, 2);
  return Word32And(
      // Shrink to fit the number of elements if only a quarter of the
      // capacity is filled with elements.
      IntPtrLessThanOrEqual(number_of_elements, quarter_capacity),

      // Allocate a new dictionary with room for at least the current
      // number of elements. The allocation method will make sure that
      // there is extra room in the dictionary for additions. Don't go
      // lower than room for 16 elements.
      IntPtrGreaterThanOrEqual(number_of_elements, IntPtrConstant(16)));
}

2555 2556 2557
TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::ValueIndexFromKeyIndex(
    TNode<IntPtrT> key_index) {
  return IntPtrAdd(key_index,
2558 2559
                   IntPtrConstant(EphemeronHashTableShape::kEntryValueIndex -
                                  EphemeronHashTable::kEntryKeyIndex));
2560 2561
}

2562
TF_BUILTIN(WeakMapConstructor, WeakCollectionsBuiltinsAssembler) {
2563
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2564
  TNode<IntPtrT> argc =
2565 2566
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2567 2568 2569

  GenerateConstructor(kWeakMap, isolate()->factory()->WeakMap_string(),
                      new_target, argc, context);
2570 2571 2572
}

TF_BUILTIN(WeakSetConstructor, WeakCollectionsBuiltinsAssembler) {
2573
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2574
  TNode<IntPtrT> argc =
2575 2576
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2577 2578 2579

  GenerateConstructor(kWeakSet, isolate()->factory()->WeakSet_string(),
                      new_target, argc, context);
2580 2581
}

2582
TF_BUILTIN(WeakMapLookupHashIndex, WeakCollectionsBuiltinsAssembler) {
2583
  TNode<EphemeronHashTable> table = CAST(Parameter(Descriptor::kTable));
2584 2585 2586 2587
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));

  Label if_not_found(this);

2588
  GotoIfNotJSReceiver(key, &if_not_found);
2589 2590 2591 2592 2593 2594 2595

  TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
  TNode<IntPtrT> capacity = LoadTableCapacity(table);
  TNode<IntPtrT> key_index =
      FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
  Return(SmiTag(ValueIndexFromKeyIndex(key_index)));

2596 2597 2598 2599
  BIND(&if_not_found);
  Return(SmiConstant(-1));
}

2600
TF_BUILTIN(WeakMapGet, WeakCollectionsBuiltinsAssembler) {
2601 2602 2603 2604 2605 2606 2607 2608 2609
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_undefined(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
                         "WeakMap.prototype.get");

2610 2611 2612
  TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
  TNode<Smi> const index =
      CAST(CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key));
2613 2614 2615 2616 2617 2618 2619 2620 2621

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_undefined);

  Return(LoadFixedArrayElement(table, SmiUntag(index)));

  BIND(&return_undefined);
  Return(UndefinedConstant());
}

2622
TF_BUILTIN(WeakMapPrototypeHas, WeakCollectionsBuiltinsAssembler) {
2623 2624 2625 2626 2627 2628 2629
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_false(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
2630
                         "WeakMap.prototype.has");
2631

2632
  TNode<EphemeronHashTable> const table = LoadTable(CAST(receiver));
2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643
  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

  Return(TrueConstant());

  BIND(&return_false);
  Return(FalseConstant());
}

2644
// Helper that removes the entry with a given key from the backing store
2645
// (EphemeronHashTable) of a WeakMap or WeakSet.
2646 2647
TF_BUILTIN(WeakCollectionDelete, WeakCollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2648
  TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
2649 2650 2651 2652
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));

  Label call_runtime(this), if_not_found(this);

2653
  GotoIfNotJSReceiver(key, &if_not_found);
2654 2655

  TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
2656
  TNode<EphemeronHashTable> table = LoadTable(collection);
2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673
  TNode<IntPtrT> capacity = LoadTableCapacity(table);
  TNode<IntPtrT> key_index =
      FindKeyIndexForKey(table, key, hash, EntryMask(capacity), &if_not_found);
  TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, -1);
  GotoIf(ShouldShrink(capacity, number_of_elements), &call_runtime);

  RemoveEntry(table, key_index, number_of_elements);
  Return(TrueConstant());

  BIND(&if_not_found);
  Return(FalseConstant());

  BIND(&call_runtime);
  Return(CallRuntime(Runtime::kWeakCollectionDelete, context, collection, key,
                     SmiTag(hash)));
}

2674 2675
// Helper that sets the key and value to the backing store (EphemeronHashTable)
// of a WeakMap or WeakSet.
2676 2677
TF_BUILTIN(WeakCollectionSet, WeakCollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2678
  TNode<JSWeakCollection> collection = CAST(Parameter(Descriptor::kCollection));
2679
  TNode<JSReceiver> key = CAST(Parameter(Descriptor::kKey));
2680 2681 2682 2683 2684 2685
  TNode<Object> value = CAST(Parameter(Descriptor::kValue));

  CSA_ASSERT(this, IsJSReceiver(key));

  Label call_runtime(this), if_no_hash(this), if_not_found(this);

2686
  TNode<EphemeronHashTable> table = LoadTable(collection);
2687 2688 2689 2690
  TNode<IntPtrT> capacity = LoadTableCapacity(table);
  TNode<IntPtrT> entry_mask = EntryMask(capacity);

  TVARIABLE(IntPtrT, var_hash, LoadJSReceiverIdentityHash(key, &if_no_hash));
2691 2692
  TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, var_hash.value(),
                                                entry_mask, &if_not_found);
2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713

  StoreFixedArrayElement(table, ValueIndexFromKeyIndex(key_index), value);
  Return(collection);

  BIND(&if_no_hash);
  {
    var_hash = SmiUntag(CreateIdentityHash(key));
    Goto(&if_not_found);
  }
  BIND(&if_not_found);
  {
    TNode<IntPtrT> number_of_deleted = LoadNumberOfDeleted(table);
    TNode<IntPtrT> number_of_elements = LoadNumberOfElements(table, 1);

    // TODO(pwong): Port HashTable's Rehash() and EnsureCapacity() to CSA.
    GotoIf(Word32Or(ShouldRehash(number_of_elements, number_of_deleted),
                    InsufficientCapacityToAdd(capacity, number_of_elements,
                                              number_of_deleted)),
           &call_runtime);

    TNode<IntPtrT> insertion_key_index =
2714
        FindKeyIndexForInsertion(table, var_hash.value(), entry_mask);
2715 2716 2717 2718 2719 2720
    AddEntry(table, insertion_key_index, key, value, number_of_elements);
    Return(collection);
  }
  BIND(&call_runtime);
  {
    CallRuntime(Runtime::kWeakCollectionSet, context, collection, key, value,
2721
                SmiTag(var_hash.value()));
2722 2723 2724 2725
    Return(collection);
  }
}

2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736
TF_BUILTIN(WeakMapPrototypeDelete, CodeStubAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
                         "WeakMap.prototype.delete");

  Return(CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, key));
}

2737
TF_BUILTIN(WeakMapPrototypeSet, WeakCollectionsBuiltinsAssembler) {
2738 2739 2740 2741 2742 2743 2744 2745 2746
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));
  TNode<Object> value = CAST(Parameter(Descriptor::kValue));

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_MAP_TYPE,
                         "WeakMap.prototype.set");

  Label throw_invalid_key(this);
2747
  GotoIfNotJSReceiver(key, &throw_invalid_key);
2748 2749 2750 2751 2752 2753 2754 2755

  Return(
      CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, key, value));

  BIND(&throw_invalid_key);
  ThrowTypeError(context, MessageTemplate::kInvalidWeakMapKey, key);
}

2756
TF_BUILTIN(WeakSetPrototypeAdd, WeakCollectionsBuiltinsAssembler) {
2757 2758 2759 2760 2761 2762 2763 2764
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
  TNode<Object> value = CAST(Parameter(Descriptor::kValue));

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
                         "WeakSet.prototype.add");

  Label throw_invalid_value(this);
2765
  GotoIfNotJSReceiver(value, &throw_invalid_value);
2766 2767 2768 2769 2770 2771 2772 2773

  Return(CallBuiltin(Builtins::kWeakCollectionSet, context, receiver, value,
                     TrueConstant()));

  BIND(&throw_invalid_value);
  ThrowTypeError(context, MessageTemplate::kInvalidWeakSetValue, value);
}

2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785
TF_BUILTIN(WeakSetPrototypeDelete, CodeStubAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));
  TNode<Object> value = CAST(Parameter(Descriptor::kValue));

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
                         "WeakSet.prototype.delete");

  Return(
      CallBuiltin(Builtins::kWeakCollectionDelete, context, receiver, value));
}

2786
TF_BUILTIN(WeakSetPrototypeHas, WeakCollectionsBuiltinsAssembler) {
2787 2788 2789 2790 2791 2792 2793
  Node* const receiver = Parameter(Descriptor::kReceiver);
  Node* const key = Parameter(Descriptor::kKey);
  Node* const context = Parameter(Descriptor::kContext);

  Label return_false(this);

  ThrowIfNotInstanceType(context, receiver, JS_WEAK_SET_TYPE,
2794
                         "WeakSet.prototype.has");
2795

2796
  Node* const table = LoadTable(CAST(receiver));
2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807
  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

  GotoIf(WordEqual(index, SmiConstant(-1)), &return_false);

  Return(TrueConstant());

  BIND(&return_false);
  Return(FalseConstant());
}

2808 2809
}  // namespace internal
}  // namespace v8