builtins-collections-gen.cc 98.1 KB
Newer Older
1 2 3 4 5 6 7 8
// 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.

#include "src/builtins/builtins-constructor-gen.h"
#include "src/builtins/builtins-iterator-gen.h"
#include "src/builtins/builtins-utils-gen.h"
#include "src/code-stub-assembler.h"
9
#include "src/heap/factory-inl.h"
10
#include "src/objects/hash-table-inl.h"
11
#include "src/objects/js-collection.h"
12 13 14 15 16

namespace v8 {
namespace internal {

using compiler::Node;
17 18
template <class T>
using TNode = compiler::TNode<T>;
19 20
template <class T>
using TVariable = compiler::TypedCodeAssemblerVariable<T>;
21

22
class BaseCollectionsAssembler : public CodeStubAssembler {
23
 public:
24
  explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state)
25 26
      : CodeStubAssembler(state) {}

27 28
  virtual ~BaseCollectionsAssembler() {}

29
 protected:
30
  enum Variant { kMap, kSet, kWeakMap, kWeakSet };
31 32 33

  // Adds an entry to a collection.  For Maps, properly handles extracting the
  // key and value from the entry (see LoadKeyValue()).
34
  void AddConstructorEntry(Variant variant, TNode<Context> context,
35
                           TNode<Object> collection, TNode<Object> add_function,
36 37 38 39
                           TNode<Object> key_value,
                           Label* if_may_have_side_effects = nullptr,
                           Label* if_exception = nullptr,
                           TVariable<Object>* var_exception = nullptr);
40 41 42 43 44 45

  // 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,
46
                             TNode<Object> initial_entries);
47 48 49 50 51

  // Fast path for adding constructor entries.  Assumes the entries are a fast
  // JS array (see CodeStubAssembler::BranchIfFastJSArray()).
  void AddConstructorEntriesFromFastJSArray(Variant variant,
                                            TNode<Context> context,
52
                                            TNode<Context> native_context,
53
                                            TNode<Object> collection,
54 55
                                            TNode<JSArray> fast_jsarray,
                                            Label* if_may_have_side_effects);
56 57 58 59 60 61 62 63 64 65

  // 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,
66
                                     TNode<JSFunction> constructor,
67 68 69 70 71 72 73 74 75
                                     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,
76
                                         TNode<JSFunction> constructor,
77 78 79 80 81 82 83 84
                                         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,
85 86 87
                           Handle<String> constructor_function_name,
                           TNode<Object> new_target, TNode<IntPtrT> argc,
                           TNode<Context> context);
88 89 90

  // Retrieves the collection function that adds an entry. `set` for Maps and
  // `add` for Sets.
91 92
  TNode<Object> GetAddFunction(Variant variant, TNode<Context> context,
                               TNode<Object> collection);
93 94 95 96 97 98 99 100 101 102 103 104 105

  // 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);

  // Retrieves the offset to access the backing table from the collection.
  int GetTableOffset(Variant variant);
106 107 108 109 110 111 112 113 114

  // 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);

115 116 117 118 119
  // Determines whether the collection's prototype has been modified.
  TNode<BoolT> HasInitialCollectionPrototype(Variant variant,
                                             TNode<Context> native_context,
                                             TNode<Object> collection);

120 121
  // Loads an element from a fixed array.  If the element is the hole, returns
  // `undefined`.
122
  TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<HeapObject> elements,
123 124 125 126
                                                  TNode<IntPtrT> index);

  // Loads an element from a fixed double array.  If the element is the hole,
  // returns `undefined`.
127 128
  TNode<Object> LoadAndNormalizeFixedDoubleArrayElement(
      TNode<HeapObject> elements, TNode<IntPtrT> index);
129

130 131 132 133
  // Loads key and value variables with the first and second elements of an
  // array.  If the array lacks 2 elements, undefined is used.
  void LoadKeyValue(TNode<Context> context, TNode<Object> maybe_array,
                    TVariable<Object>* key, TVariable<Object>* value,
134
                    Label* if_may_have_side_effects = nullptr,
135 136 137 138
                    Label* if_exception = nullptr,
                    TVariable<Object>* var_exception = nullptr);
};

139
void BaseCollectionsAssembler::AddConstructorEntry(
140
    Variant variant, TNode<Context> context, TNode<Object> collection,
141
    TNode<Object> add_function, TNode<Object> key_value,
142 143
    Label* if_may_have_side_effects, Label* if_exception,
    TVariable<Object>* var_exception) {
144
  CSA_ASSERT(this, Word32BinaryNot(IsTheHole(key_value)));
145
  if (variant == kMap || variant == kWeakMap) {
146 147
    TVARIABLE(Object, key);
    TVARIABLE(Object, value);
148 149
    LoadKeyValue(context, key_value, &key, &value, if_may_have_side_effects,
                 if_exception, var_exception);
150 151
    Node* key_n = key.value();
    Node* value_n = value.value();
152 153 154
    Node* ret = CallJS(CodeFactory::Call(isolate()), context, add_function,
                       collection, key_n, value_n);
    GotoIfException(ret, if_exception, var_exception);
155 156
  } else {
    DCHECK(variant == kSet || variant == kWeakSet);
157 158 159
    Node* ret = CallJS(CodeFactory::Call(isolate()), context, add_function,
                       collection, key_value);
    GotoIfException(ret, if_exception, var_exception);
160 161 162 163 164
  }
}

void BaseCollectionsAssembler::AddConstructorEntries(
    Variant variant, TNode<Context> context, TNode<Context> native_context,
165 166 167 168
    TNode<Object> collection, TNode<Object> initial_entries) {
  TVARIABLE(BoolT, use_fast_loop,
            IsFastJSArrayWithNoCustomIteration(initial_entries, context,
                                               native_context));
169
  TNode<IntPtrT> at_least_space_for =
170
      EstimatedInitialSize(initial_entries, use_fast_loop.value());
171 172 173 174 175 176 177 178
  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);
179 180 181
    GotoIfNot(
        HasInitialCollectionPrototype(variant, native_context, collection),
        &slow_loop);
182
    Branch(use_fast_loop.value(), &fast_loop, &slow_loop);
183 184 185
  }
  BIND(&fast_loop);
  {
186 187
    TNode<JSArray> initial_entries_jsarray =
        UncheckedCast<JSArray>(initial_entries);
188
#if DEBUG
189 190 191
    CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(
                         initial_entries_jsarray, context, native_context));
    TNode<Map> original_initial_entries_map = LoadMap(initial_entries_jsarray);
192 193 194
#endif

    Label if_may_have_side_effects(this, Label::kDeferred);
195 196 197
    AddConstructorEntriesFromFastJSArray(variant, context, native_context,
                                         collection, initial_entries_jsarray,
                                         &if_may_have_side_effects);
198
    Goto(&exit);
199

200 201 202 203 204 205
    if (variant == kMap || variant == kWeakMap) {
      BIND(&if_may_have_side_effects);
#if DEBUG
      CSA_ASSERT(this, HasInitialCollectionPrototype(variant, native_context,
                                                     collection));
      CSA_ASSERT(this, WordEqual(original_initial_entries_map,
206
                                 LoadMap(initial_entries_jsarray)));
207
#endif
208
      use_fast_loop = Int32FalseConstant();
209
      Goto(&allocate_table);
210
    }
211
  }
212 213 214 215 216 217
  BIND(&slow_loop);
  {
    AddConstructorEntriesFromIterable(variant, context, native_context,
                                      collection, initial_entries);
    Goto(&exit);
  }
218 219 220 221
  BIND(&exit);
}

void BaseCollectionsAssembler::AddConstructorEntriesFromFastJSArray(
222
    Variant variant, TNode<Context> context, TNode<Context> native_context,
223 224
    TNode<Object> collection, TNode<JSArray> fast_jsarray,
    Label* if_may_have_side_effects) {
225
  TNode<FixedArrayBase> elements = LoadElements(fast_jsarray);
226
  TNode<Int32T> elements_kind = LoadElementsKind(fast_jsarray);
227
  TNode<JSFunction> add_func = GetInitialAddFunction(variant, native_context);
228 229 230
  CSA_ASSERT(
      this,
      WordEqual(GetAddFunction(variant, native_context, collection), add_func));
231 232
  CSA_ASSERT(this, IsFastJSArrayWithNoCustomIteration(fast_jsarray, context,
                                                      native_context));
233
  TNode<IntPtrT> length = SmiUntag(LoadFastJSArrayLength(fast_jsarray));
234
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(length, IntPtrConstant(0)));
235 236
  CSA_ASSERT(
      this, HasInitialCollectionPrototype(variant, native_context, collection));
237

238 239 240 241
#if DEBUG
  TNode<Map> original_collection_map = LoadMap(CAST(collection));
  TNode<Map> original_fast_js_array_map = LoadMap(fast_jsarray);
#endif
242
  Label exit(this), if_doubles(this), if_smiorobjects(this);
243
  GotoIf(IntPtrEqual(length, IntPtrConstant(0)), &exit);
244 245 246 247 248
  Branch(IsFastSmiOrTaggedElementsKind(elements_kind), &if_smiorobjects,
         &if_doubles);
  BIND(&if_smiorobjects);
  {
    auto set_entry = [&](Node* index) {
249 250
      TNode<Object> element = LoadAndNormalizeFixedArrayElement(
          elements, UncheckedCast<IntPtrT>(index));
251 252
      AddConstructorEntry(variant, context, collection, add_func, element,
                          if_may_have_side_effects);
253
    };
254 255 256 257 258

    // 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.
259 260 261 262 263 264 265 266
    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.
267
    if (variant == kMap || variant == kWeakMap) {
268 269 270
      CSA_ASSERT(this, IntPtrGreaterThan(length, IntPtrConstant(0)));
      TNode<Object> element =
          LoadAndNormalizeFixedDoubleArrayElement(elements, IntPtrConstant(0));
271
      ThrowTypeError(context, MessageTemplate::kIteratorValueNotAnObject,
272
                     element);
273
    } else {
274
      DCHECK(variant == kSet || variant == kWeakSet);
275
      auto set_entry = [&](Node* index) {
276 277
        TNode<Object> entry = LoadAndNormalizeFixedDoubleArrayElement(
            elements, UncheckedCast<IntPtrT>(index));
278
        AddConstructorEntry(variant, context, collection, add_func, entry);
279 280 281 282 283 284 285
      };
      BuildFastLoop(IntPtrConstant(0), length, set_entry, 1,
                    ParameterMode::INTPTR_PARAMETERS, IndexAdvanceMode::kPost);
      Goto(&exit);
    }
  }
  BIND(&exit);
286 287 288 289 290 291
#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
292 293 294 295 296 297 298 299
}

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)));

300
  TNode<Object> add_func = GetAddFunction(variant, context, collection);
301
  IteratorBuiltinsAssembler iterator_assembler(this->state());
302
  IteratorRecord iterator = iterator_assembler.GetIterator(context, iterable);
303

304
  CSA_ASSERT(this, Word32BinaryNot(IsUndefined(iterator.object)));
305 306 307 308 309 310 311 312 313 314 315 316

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

  Goto(&loop);
  BIND(&loop);
  {
    TNode<Object> next = CAST(iterator_assembler.IteratorStep(
        context, iterator, &exit, fast_iterator_result_map));
    TNode<Object> next_value = CAST(iterator_assembler.IteratorValue(
        context, next, fast_iterator_result_map));
317 318
    AddConstructorEntry(variant, context, collection, add_func, next_value,
                        nullptr, &if_exception, &var_exception);
319 320 321 322 323 324 325 326 327 328 329
    Goto(&loop);
  }
  BIND(&if_exception);
  {
    iterator_assembler.IteratorCloseOnException(context, iterator,
                                                &var_exception);
  }
  BIND(&exit);
}

TNode<Object> BaseCollectionsAssembler::AllocateJSCollection(
330 331
    TNode<Context> context, TNode<JSFunction> constructor,
    TNode<Object> new_target) {
332 333 334 335 336 337 338
  TNode<BoolT> is_target_unmodified = WordEqual(constructor, new_target);

  return Select<Object>(is_target_unmodified,
                        [=] { return AllocateJSCollectionFast(constructor); },
                        [=] {
                          return AllocateJSCollectionSlow(context, constructor,
                                                          new_target);
339
                        });
340
}
341

342 343 344 345 346 347 348 349 350
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(
351
    TNode<Context> context, TNode<JSFunction> constructor,
352 353 354 355 356 357 358
    TNode<Object> new_target) {
  ConstructorBuiltinsAssembler constructor_assembler(this->state());
  return CAST(constructor_assembler.EmitFastNewObject(context, constructor,
                                                      new_target));
}

void BaseCollectionsAssembler::GenerateConstructor(
359 360
    Variant variant, Handle<String> constructor_function_name,
    TNode<Object> new_target, TNode<IntPtrT> argc, TNode<Context> context) {
361
  const int kIterableArg = 0;
362
  CodeStubArguments args(this, argc);
363 364 365 366 367
  TNode<Object> iterable = args.GetOptionalArgumentValue(kIterableArg);

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

368
  TNode<Context> native_context = LoadNativeContext(context);
369
  TNode<Object> collection = AllocateJSCollection(
370
      context, GetConstructor(variant, native_context), new_target);
371

372
  AddConstructorEntries(variant, context, native_context, collection, iterable);
373 374 375 376 377 378 379
  Return(collection);

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

380
TNode<Object> BaseCollectionsAssembler::GetAddFunction(
381
    Variant variant, TNode<Context> context, TNode<Object> collection) {
382
  Handle<String> add_func_name = (variant == kMap || variant == kWeakMap)
383 384
                                     ? isolate()->factory()->set_string()
                                     : isolate()->factory()->add_string();
385
  TNode<Object> add_func = GetProperty(context, collection, add_func_name);
386 387 388

  Label exit(this), if_notcallable(this, Label::kDeferred);
  GotoIf(TaggedIsSmi(add_func), &if_notcallable);
389
  GotoIfNot(IsCallable(CAST(add_func)), &if_notcallable);
390 391 392 393 394 395 396
  Goto(&exit);

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

  BIND(&exit);
397
  return add_func;
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
}

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();
452 453 454 455 456 457 458
}

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))); },
459
      [=] { return IntPtrConstant(0); });
460 461 462 463 464 465 466 467
}

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

468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487
TNode<BoolT> BaseCollectionsAssembler::HasInitialCollectionPrototype(
    Variant variant, TNode<Context> native_context, TNode<Object> collection) {
  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;
  }
  TNode<Map> initial_prototype_map =
      CAST(LoadContextElement(native_context, initial_prototype_index));
  TNode<Map> collection_proto_map =
488
      LoadMap(LoadMapPrototype(LoadMap(CAST(collection))));
489 490 491 492

  return WordEqual(collection_proto_map, initial_prototype_map);
}

493
TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedArrayElement(
494
    TNode<HeapObject> elements, TNode<IntPtrT> index) {
495
  TNode<Object> element = LoadFixedArrayElement(elements, index);
496
  return Select<Object>(IsTheHole(element), [=] { return UndefinedConstant(); },
497
                        [=] { return element; });
498 499 500
}

TNode<Object> BaseCollectionsAssembler::LoadAndNormalizeFixedDoubleArrayElement(
501
    TNode<HeapObject> elements, TNode<IntPtrT> index) {
502 503
  TVARIABLE(Object, entry);
  Label if_hole(this, Label::kDeferred), next(this);
504 505 506
  TNode<Float64T> element =
      LoadFixedDoubleArrayElement(CAST(elements), index, MachineType::Float64(),
                                  0, INTPTR_PARAMETERS, &if_hole);
507 508 509 510 511 512 513 514 515 516
  {  // not hole
    entry = AllocateHeapNumberWithValue(element);
    Goto(&next);
  }
  BIND(&if_hole);
  {
    entry = UndefinedConstant();
    Goto(&next);
  }
  BIND(&next);
517
  return entry.value();
518 519
}

520 521 522 523
void BaseCollectionsAssembler::LoadKeyValue(
    TNode<Context> context, TNode<Object> maybe_array, TVariable<Object>* key,
    TVariable<Object>* value, Label* if_may_have_side_effects,
    Label* if_exception, TVariable<Object>* var_exception) {
524 525
  CSA_ASSERT(this, Word32BinaryNot(IsTheHole(maybe_array)));

526 527 528 529 530 531 532
  Label exit(this), if_fast(this), if_slow(this, Label::kDeferred);
  BranchIfFastJSArray(maybe_array, context, &if_fast, &if_slow);
  BIND(&if_fast);
  {
    TNode<JSArray> array = CAST(maybe_array);
    TNode<Smi> length = LoadFastJSArrayLength(array);
    TNode<FixedArrayBase> elements = LoadElements(array);
533
    TNode<Int32T> elements_kind = LoadElementsKind(array);
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549

    Label if_smiorobjects(this), if_doubles(this);
    Branch(IsFastSmiOrTaggedElementsKind(elements_kind), &if_smiorobjects,
           &if_doubles);
    BIND(&if_smiorobjects);
    {
      Label if_one(this), if_two(this);
      GotoIf(SmiGreaterThan(length, SmiConstant(1)), &if_two);
      GotoIf(SmiEqual(length, SmiConstant(1)), &if_one);
      {  // empty array
        *key = UndefinedConstant();
        *value = UndefinedConstant();
        Goto(&exit);
      }
      BIND(&if_one);
      {
550
        *key = LoadAndNormalizeFixedArrayElement(elements, IntPtrConstant(0));
551 552 553 554 555
        *value = UndefinedConstant();
        Goto(&exit);
      }
      BIND(&if_two);
      {
556 557
        *key = LoadAndNormalizeFixedArrayElement(elements, IntPtrConstant(0));
        *value = LoadAndNormalizeFixedArrayElement(elements, IntPtrConstant(1));
558 559 560 561 562 563 564 565 566 567 568 569 570 571 572
        Goto(&exit);
      }
    }
    BIND(&if_doubles);
    {
      Label if_one(this), if_two(this);
      GotoIf(SmiGreaterThan(length, SmiConstant(1)), &if_two);
      GotoIf(SmiEqual(length, SmiConstant(1)), &if_one);
      {  // empty array
        *key = UndefinedConstant();
        *value = UndefinedConstant();
        Goto(&exit);
      }
      BIND(&if_one);
      {
573 574
        *key = LoadAndNormalizeFixedDoubleArrayElement(elements,
                                                       IntPtrConstant(0));
575 576 577 578 579
        *value = UndefinedConstant();
        Goto(&exit);
      }
      BIND(&if_two);
      {
580 581 582 583
        *key = LoadAndNormalizeFixedDoubleArrayElement(elements,
                                                       IntPtrConstant(0));
        *value = LoadAndNormalizeFixedDoubleArrayElement(elements,
                                                         IntPtrConstant(1));
584 585 586 587 588 589
        Goto(&exit);
      }
    }
  }
  BIND(&if_slow);
  {
590 591 592 593 594 595 596 597 598 599
    Label if_notobject(this, Label::kDeferred);
    GotoIfNotJSReceiver(maybe_array, &if_notobject);
    if (if_may_have_side_effects != nullptr) {
      // If the element is not a fast array, we cannot guarantee accessing the
      // key and value won't execute user code that will break fast path
      // assumptions.
      Goto(if_may_have_side_effects);
    } else {
      *key = UncheckedCast<Object>(GetProperty(
          context, maybe_array, isolate()->factory()->zero_string()));
600
      GotoIfException(key->value(), if_exception, var_exception);
601

602 603
      *value = UncheckedCast<Object>(GetProperty(
          context, maybe_array, isolate()->factory()->one_string()));
604
      GotoIfException(value->value(), if_exception, var_exception);
605 606 607 608 609 610 611 612 613
      Goto(&exit);
    }
    BIND(&if_notobject);
    {
      Node* ret = CallRuntime(
          Runtime::kThrowTypeError, context,
          SmiConstant(MessageTemplate::kIteratorValueNotAnObject), maybe_array);
      GotoIfException(ret, if_exception, var_exception);
      Unreachable();
614 615 616 617 618 619 620 621 622 623 624
    }
  }
  BIND(&exit);
}

class CollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
 public:
  explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
      : BaseCollectionsAssembler(state) {}

 protected:
625 626 627
  template <typename IteratorType>
  Node* AllocateJSCollectionIterator(Node* context, int map_index,
                                     Node* collection);
628 629
  TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
                              TNode<IntPtrT> at_least_space_for);
630
  Node* GetHash(Node* const key);
631
  Node* CallGetHashRaw(Node* const key);
632
  Node* CallGetOrCreateHashRaw(Node* const key);
633

634 635 636 637 638 639 640 641
  // 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>
  std::tuple<Node*, Node*> Transition(
      Node* const table, Node* const index,
      UpdateInTransition const& update_in_transition);
642
  template <typename IteratorType, typename TableType>
643
  std::tuple<Node*, Node*> TransitionAndUpdate(Node* const iterator);
644 645 646 647
  template <typename TableType>
  std::tuple<Node*, Node*, Node*> NextSkipHoles(Node* table, Node* index,
                                                Label* if_end);

648
  // Specialization for Smi.
649 650
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
651 652
  template <typename CollectionType>
  void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged,
653 654
                                          Variable* result, Label* entry_found,
                                          Label* not_found);
655 656 657
  void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
                        Label* if_not_same);

658
  // Specialization for heap numbers.
659 660
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
661 662
  void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key,
                               Label* if_same, Label* if_not_same);
663 664 665
  template <typename CollectionType>
  void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table,
                                                 Node* key_heap_number,
666
                                                 Variable* result,
667 668
                                                 Label* entry_found,
                                                 Label* not_found);
669

670 671 672 673 674 675 676 677 678 679 680
  // 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);

681
  // Specialization for string.
682 683
  // The {result} variable will contain the entry index if the key was found,
  // or the hash code otherwise.
684 685
  template <typename CollectionType>
  void FindOrderedHashTableEntryForStringKey(Node* context, Node* table,
686
                                             Node* key_tagged, Variable* result,
687 688
                                             Label* entry_found,
                                             Label* not_found);
689 690 691
  Node* ComputeIntegerHashForString(Node* context, Node* string_key);
  void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
                           Label* if_same, Label* if_not_same);
692 693 694

  // Specialization for non-strings, non-numbers. For those we only need
  // reference equality to compare the keys.
695 696 697
  // 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.
698 699
  template <typename CollectionType>
  void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table,
700
                                            Node* key, Variable* result,
701 702
                                            Label* entry_found,
                                            Label* not_found);
703 704 705 706 707 708

  template <typename CollectionType>
  void TryLookupOrderedHashTableIndex(Node* const table, Node* const key,
                                      Node* const context, Variable* result,
                                      Label* if_entry_found,
                                      Label* if_not_found);
709 710 711 712 713 714

  Node* NormalizeNumberKey(Node* key);
  void StoreOrderedHashMapNewEntry(Node* const table, Node* const key,
                                   Node* const value, Node* const hash,
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
715 716 717 718
  void StoreOrderedHashSetNewEntry(Node* const table, Node* const key,
                                   Node* const hash,
                                   Node* const number_of_buckets,
                                   Node* const occupancy);
719 720
};

721 722 723 724 725 726 727 728
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);
729
  StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset,
730 731 732 733 734 735 736 737 738
                       Heap::kEmptyFixedArrayRootIndex);
  StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset,
                       Heap::kEmptyFixedArrayRootIndex);
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table);
  StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset,
                                 SmiConstant(0));
  return iterator;
}

739 740 741
TNode<Object> CollectionsBuiltinsAssembler::AllocateTable(
    Variant variant, TNode<Context> context,
    TNode<IntPtrT> at_least_space_for) {
742 743 744
  return CAST((variant == kMap || variant == kWeakMap)
                  ? AllocateOrderedHashTable<OrderedHashMap>()
                  : AllocateOrderedHashTable<OrderedHashSet>());
745
}
746

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

  GenerateConstructor(kMap, isolate()->factory()->Map_string(), new_target,
                      argc, context);
755 756 757
}

TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) {
758
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
759
  TNode<IntPtrT> argc =
760 761
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
762 763 764

  GenerateConstructor(kSet, isolate()->factory()->Set_string(), new_target,
                      argc, context);
765 766
}

767 768 769 770 771 772 773 774 775 776 777 778 779 780 781
Node* CollectionsBuiltinsAssembler::CallGetOrCreateHashRaw(Node* const key) {
  Node* const function_addr =
      ExternalConstant(ExternalReference::get_or_create_hash_raw(isolate()));
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

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

  Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
                                      function_addr, isolate_ptr, key);

  return result;
}

782
Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) {
783 784
  Node* const function_addr =
      ExternalConstant(ExternalReference::orderedhashmap_gethash_raw());
785 786 787 788 789 790
  Node* const isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));

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

791 792
  Node* const result = CallCFunction2(type_tagged, type_ptr, type_tagged,
                                      function_addr, isolate_ptr, key);
793 794 795 796
  return SmiUntag(result);
}

Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) {
797 798 799
  VARIABLE(var_hash, MachineType::PointerRepresentation());
  Label if_receiver(this), if_other(this), done(this);
  Branch(IsJSReceiver(key), &if_receiver, &if_other);
800

801
  BIND(&if_receiver);
802
  {
803
    var_hash.Bind(LoadJSReceiverIdentityHash(key));
804 805
    Goto(&done);
  }
806

807
  BIND(&if_other);
808
  {
809
    var_hash.Bind(CallGetHashRaw(key));
810 811 812 813
    Goto(&done);
  }

  BIND(&done);
814
  return var_hash.value();
815 816
}

817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839
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);
}

840 841
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey(
842 843
    Node* table, Node* smi_key, Variable* result, Label* entry_found,
    Label* not_found) {
844
  Node* const key_untagged = SmiUntag(smi_key);
845
  Node* const hash =
846
      ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0)));
847 848
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
849
  FindOrderedHashTableEntry<CollectionType>(
850
      table, hash,
851 852 853
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
      },
854
      result, entry_found, not_found);
855 856
}

857 858
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey(
859 860
    Node* context, Node* table, Node* key_tagged, Variable* result,
    Label* entry_found, Label* not_found) {
861
  Node* const hash = ComputeIntegerHashForString(context, key_tagged);
862 863
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
864
  FindOrderedHashTableEntry<CollectionType>(
865
      table, hash,
866 867 868 869
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroString(context, key_tagged, other_key, if_same,
                            if_not_same);
      },
870
      result, entry_found, not_found);
871 872
}

873 874
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey(
875 876
    Node* context, Node* table, Node* key_heap_number, Variable* result,
    Label* entry_found, Label* not_found) {
877
  Node* hash = CallGetHashRaw(key_heap_number);
878 879
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  result->Bind(hash);
880
  Node* const key_float = LoadHeapNumberValue(key_heap_number);
881
  FindOrderedHashTableEntry<CollectionType>(
882
      table, hash,
883 884 885
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same);
      },
886
      result, entry_found, not_found);
887 888
}

889 890 891 892 893 894 895 896 897 898 899 900 901 902 903
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);
}

904 905
template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
906 907
    Node* context, Node* table, Node* key, Variable* result, Label* entry_found,
    Label* not_found) {
908
  Node* hash = GetHash(key);
909
  CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
910
  result->Bind(hash);
911
  FindOrderedHashTableEntry<CollectionType>(
912
      table, hash,
913 914 915
      [&](Node* other_key, Label* if_same, Label* if_not_same) {
        Branch(WordEqual(key, other_key), if_same, if_not_same);
      },
916
      result, entry_found, not_found);
917 918
}

919 920 921 922 923 924 925 926 927 928 929
Node* CollectionsBuiltinsAssembler::ComputeIntegerHashForString(
    Node* context, Node* string_key) {
  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);
930
  var_result.Bind(CallGetHashRaw(string_key));
931
  Goto(&done);
932

933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951
  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);
}

952 953 954 955 956 957 958 959
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);

960 961
  Branch(WordEqual(CallRuntime(Runtime::kBigIntEqualToBigInt,
                               NoContextConstant(), key, candidate_key),
962 963 964 965
                   TrueConstant()),
         if_same, if_not_same);
}

966 967 968 969 970 971 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
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);
  }
}

999
TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) {
1000 1001
  TNode<HeapObject> table = CAST(Parameter(Descriptor::kTable));
  TNode<Smi> index = CAST(Parameter(Descriptor::kIndex));
1002 1003 1004
  Label return_index(this), return_zero(this);

  // Check if we need to update the {index}.
1005
  GotoIfNot(SmiLessThan(SmiConstant(0), index), &return_zero);
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021

  // Check if the {table} was cleared.
  Node* number_of_deleted_elements = LoadAndUntagObjectField(
      table, OrderedHashTableBase::kNumberOfDeletedElementsOffset);
  GotoIf(WordEqual(number_of_deleted_elements,
                   IntPtrConstant(OrderedHashTableBase::kClearedTableSentinel)),
         &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);
1022 1023
    TNode<Smi> removed_index = CAST(LoadFixedArrayElement(
        table, i, OrderedHashTableBase::kRemovedHolesIndex * kPointerSize));
1024
    GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index);
1025 1026
    Decrement(&var_index, 1, SMI_PARAMETERS);
    Increment(&var_i);
1027 1028 1029 1030 1031 1032 1033
    Goto(&loop);
  }

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

  BIND(&return_zero);
1034
  Return(SmiConstant(0));
1035 1036
}

1037
template <typename TableType>
1038
std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::Transition(
1039 1040 1041 1042
    Node* const table, Node* const index,
    UpdateInTransition const& update_in_transition) {
  VARIABLE(var_index, MachineType::PointerRepresentation(), index);
  VARIABLE(var_table, MachineRepresentation::kTagged, table);
1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060
  Label if_done(this), if_transition(this, Label::kDeferred);
  Branch(TaggedIsSmi(
             LoadObjectField(var_table.value(), TableType::kNextTableOffset)),
         &if_done, &if_transition);

  BIND(&if_transition);
  {
    Label loop(this, {&var_table, &var_index}), done_loop(this);
    Goto(&loop);
    BIND(&loop);
    {
      Node* table = var_table.value();
      Node* index = var_index.value();

      Node* next_table = LoadObjectField(table, TableType::kNextTableOffset);
      GotoIf(TaggedIsSmi(next_table), &done_loop);

      var_table.Bind(next_table);
1061 1062 1063
      var_index.Bind(SmiUntag(
          CAST(CallBuiltin(Builtins::kOrderedHashTableHealIndex,
                           NoContextConstant(), table, SmiTag(index)))));
1064
      Goto(&loop);
1065 1066 1067
    }
    BIND(&done_loop);

1068 1069
    // Update with the new {table} and {index}.
    update_in_transition(var_table.value(), var_index.value());
1070 1071 1072 1073 1074 1075 1076
    Goto(&if_done);
  }

  BIND(&if_done);
  return std::tuple<Node*, Node*>(var_table.value(), var_index.value());
}

1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090
template <typename IteratorType, typename TableType>
std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::TransitionAndUpdate(
    Node* const iterator) {
  return Transition<TableType>(
      LoadObjectField(iterator, IteratorType::kTableOffset),
      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));
      });
}

1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
template <typename TableType>
std::tuple<Node*, Node*, Node*> CollectionsBuiltinsAssembler::NextSkipHoles(
    Node* table, Node* index, Label* if_end) {
  // Compute the used capacity for the {table}.
  Node* number_of_buckets =
      LoadAndUntagObjectField(table, TableType::kNumberOfBucketsOffset);
  Node* number_of_elements =
      LoadAndUntagObjectField(table, TableType::kNumberOfElementsOffset);
  Node* number_of_deleted_elements =
      LoadAndUntagObjectField(table, TableType::kNumberOfDeletedElementsOffset);
  Node* used_capacity =
      IntPtrAdd(number_of_elements, number_of_deleted_elements);

  Node* entry_key;
  Node* entry_start_position;
  VARIABLE(var_index, MachineType::PointerRepresentation(), index);
  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);
    entry_key =
        LoadFixedArrayElement(table, entry_start_position,
                              TableType::kHashTableStartIndex * kPointerSize);
1118
    Increment(&var_index);
1119 1120 1121 1122 1123 1124 1125 1126
    Branch(IsTheHole(entry_key), &loop, &done_loop);
  }

  BIND(&done_loop);
  return std::tuple<Node*, Node*, Node*>(entry_key, entry_start_position,
                                         var_index.value());
}

1127
TF_BUILTIN(MapPrototypeGet, CollectionsBuiltinsAssembler) {
1128
  Node* const receiver = Parameter(Descriptor::kReceiver);
1129
  Node* const key = Parameter(Descriptor::kKey);
1130 1131 1132 1133 1134
  Node* const context = Parameter(Descriptor::kContext);

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

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

1138 1139 1140
  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);
1141

1142
  BIND(&if_found);
1143 1144 1145 1146
  Return(LoadFixedArrayElement(
      table, SmiUntag(index),
      (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
          kPointerSize));
1147

1148
  BIND(&if_not_found);
1149
  Return(UndefinedConstant());
1150
}
1151

1152
TF_BUILTIN(MapPrototypeHas, CollectionsBuiltinsAssembler) {
1153
  Node* const receiver = Parameter(Descriptor::kReceiver);
1154
  Node* const key = Parameter(Descriptor::kKey);
1155 1156 1157 1158 1159
  Node* const context = Parameter(Descriptor::kContext);

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

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

1163 1164 1165
  Label if_found(this), if_not_found(this);
  Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found,
         &if_not_found);
1166

1167
  BIND(&if_found);
1168 1169
  Return(TrueConstant());

1170
  BIND(&if_not_found);
1171
  Return(FalseConstant());
1172 1173
}

1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190
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();
}

1191
TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) {
1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206
  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);

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

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

1207 1208 1209
  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);
1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222

  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,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));
  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.
1223 1224
    GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                             IntPtrConstant(0)),
1225 1226 1227
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
1228
    entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1229 1230 1231 1232 1233 1234 1235 1236 1237
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
  VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
  {
    // Check we have enough space for the entry.
1238 1239
    number_of_buckets.Bind(SmiUntag(CAST(
        LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex))));
1240 1241 1242 1243

    STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
1244 1245 1246
        CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)));
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table, OrderedHashMap::kNumberOfDeletedElementsOffset)));
1247 1248 1249 1250 1251 1252 1253
    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);
    table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
1254 1255
    number_of_buckets.Bind(SmiUntag(CAST(LoadFixedArrayElement(
        table_var.value(), OrderedHashMap::kNumberOfBucketsIndex))));
1256 1257 1258 1259
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashMap::kNumberOfElementsOffset)));
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashMap::kNumberOfDeletedElementsOffset)));
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 1292 1293 1294 1295 1296
    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(
    Node* const table, Node* const key, Node* const value, Node* const hash,
    Node* const number_of_buckets, Node* const occupancy) {
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
  Node* const bucket_entry = LoadFixedArrayElement(
      table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize);

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)),
      number_of_buckets);
  StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashMap::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start, value, UPDATE_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));
  StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kChainOffset));

  // Update the bucket head.
  StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
                         OrderedHashMap::kHashTableStartIndex * kPointerSize);

  // Bump the elements count.
1297 1298
  TNode<Smi> const number_of_elements =
      CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset));
1299 1300 1301 1302
  StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

1303
TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316
  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");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

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

1317 1318 1319
  TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context,
                                                 &entry_start_position_or_hash,
                                                 &entry_found, &not_found);
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334

  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,
                         kPointerSize * OrderedHashMap::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kPointerSize * (OrderedHashMap::kHashTableStartIndex +
                                         OrderedHashMap::kValueOffset));

  // Decrement the number of elements, increment the number of deleted elements.
1335
  TNode<Smi> const number_of_elements = SmiSub(
1336 1337
      CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)),
      SmiConstant(1));
1338 1339
  StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset,
                                 number_of_elements);
1340
  TNode<Smi> const number_of_deleted =
1341 1342 1343
      SmiAdd(CAST(LoadObjectField(
                 table, OrderedHashMap::kNumberOfDeletedElementsOffset)),
             SmiConstant(1));
1344 1345 1346
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashMap::kNumberOfDeletedElementsOffset, number_of_deleted);

1347 1348
  TNode<Smi> const number_of_buckets =
      CAST(LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex));
1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361

  // 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());
}

1362
TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler) {
1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388
  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);

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  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.
1389 1390
    GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(),
                             IntPtrConstant(0)),
1391 1392 1393
           &add_entry);

    // Otherwise, go to runtime to compute the hash code.
1394
    entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key)));
1395 1396 1397 1398 1399 1400 1401 1402 1403
    Goto(&add_entry);
  }

  BIND(&add_entry);
  VARIABLE(number_of_buckets, MachineType::PointerRepresentation());
  VARIABLE(occupancy, MachineType::PointerRepresentation());
  VARIABLE(table_var, MachineRepresentation::kTaggedPointer, table);
  {
    // Check we have enough space for the entry.
1404 1405
    number_of_buckets.Bind(SmiUntag(CAST(
        LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex))));
1406 1407 1408 1409

    STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2);
    Node* const capacity = WordShl(number_of_buckets.value(), 1);
    Node* const number_of_elements = SmiUntag(
1410 1411 1412
        CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)));
    Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table, OrderedHashSet::kNumberOfDeletedElementsOffset)));
1413 1414 1415 1416 1417 1418 1419
    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);
    table_var.Bind(LoadObjectField(receiver, JSMap::kTableOffset));
1420 1421
    number_of_buckets.Bind(SmiUntag(CAST(LoadFixedArrayElement(
        table_var.value(), OrderedHashSet::kNumberOfBucketsIndex))));
1422 1423 1424 1425
    Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashSet::kNumberOfElementsOffset)));
    Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table_var.value(), OrderedHashSet::kNumberOfDeletedElementsOffset)));
1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459
    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(
    Node* const table, Node* const key, Node* const hash,
    Node* const number_of_buckets, Node* const occupancy) {
  Node* const bucket =
      WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
  Node* const bucket_entry = LoadFixedArrayElement(
      table, bucket, OrderedHashSet::kHashTableStartIndex * kPointerSize);

  // Store the entry elements.
  Node* const entry_start = IntPtrAdd(
      IntPtrMul(occupancy, IntPtrConstant(OrderedHashSet::kEntrySize)),
      number_of_buckets);
  StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER,
                         kPointerSize * OrderedHashSet::kHashTableStartIndex);
  StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER,
                         kPointerSize * (OrderedHashSet::kHashTableStartIndex +
                                         OrderedHashSet::kChainOffset));

  // Update the bucket head.
  StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER,
                         OrderedHashSet::kHashTableStartIndex * kPointerSize);

  // Bump the elements count.
1460 1461
  TNode<Smi> const number_of_elements =
      CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset));
1462 1463 1464 1465
  StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
                                 SmiAdd(number_of_elements, SmiConstant(1)));
}

1466
TF_BUILTIN(SetPrototypeDelete, CollectionsBuiltinsAssembler) {
1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493
  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");

  Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);

  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,
                         kPointerSize * OrderedHashSet::kHashTableStartIndex);

  // Decrement the number of elements, increment the number of deleted elements.
1494
  TNode<Smi> const number_of_elements = SmiSub(
1495 1496
      CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)),
      SmiConstant(1));
1497 1498
  StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset,
                                 number_of_elements);
1499
  TNode<Smi> const number_of_deleted =
1500 1501 1502
      SmiAdd(CAST(LoadObjectField(
                 table, OrderedHashSet::kNumberOfDeletedElementsOffset)),
             SmiConstant(1));
1503 1504 1505
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashSet::kNumberOfDeletedElementsOffset, number_of_deleted);

1506 1507
  TNode<Smi> const number_of_buckets =
      CAST(LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex));
1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520

  // 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());
}

1521 1522 1523 1524 1525 1526 1527 1528 1529
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));
}

1530 1531 1532 1533 1534 1535 1536 1537 1538
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);
  Return(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset));
}

1539 1540
TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Map.prototype.forEach";
1541 1542
  Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
  Node* const context = Parameter(Descriptor::kContext);
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601
  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);

  VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_table, MachineRepresentation::kTagged,
           LoadObjectField(receiver, JSMap::kTableOffset));
  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.
    Node* index = var_index.value();
    Node* table = var_table.value();
    std::tie(table, index) =
        Transition<OrderedHashMap>(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<OrderedHashMap>(table, index, &done_loop);

    // Load the entry value as well.
    Node* entry_value = LoadFixedArrayElement(
        table, entry_start_position,
        (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
            kPointerSize);

    // 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.
    var_index.Bind(index);
    var_table.Bind(table);
    Goto(&loop);
  }

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

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

1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
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);
1636 1637
  ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
                 StringConstant(kMethodName), receiver);
1638 1639 1640 1641
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1642 1643 1644
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);
1645 1646 1647 1648

  // Transition the {receiver} table if necessary.
  Node* table;
  Node* index;
1649 1650
  std::tie(table, index) =
      TransitionAndUpdate<JSMapIterator, OrderedHashMap>(receiver);
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688

  // 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<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,
      (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
          kPointerSize));
  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,
1689
                         Heap::kEmptyOrderedHashMapRootIndex);
1690 1691 1692 1693
    Goto(&return_value);
  }
}

1694
TF_BUILTIN(SetPrototypeHas, CollectionsBuiltinsAssembler) {
1695 1696 1697 1698 1699 1700 1701
  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);
1702 1703 1704 1705 1706

  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),
1707
      if_key_bigint(this), entry_found(this), not_found(this), done(this);
1708 1709

  GotoIf(TaggedIsSmi(key), &if_key_smi);
1710 1711 1712 1713 1714 1715 1716

  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);
1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738

  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);
  }

1739 1740 1741 1742 1743 1744
  BIND(&if_key_bigint);
  {
    FindOrderedHashTableEntryForBigIntKey<OrderedHashSet>(
        context, table, key, &entry_start_position, &entry_found, &not_found);
  }

1745 1746 1747 1748 1749
  BIND(&entry_found);
  Return(TrueConstant());

  BIND(&not_found);
  Return(FalseConstant());
1750 1751
}

1752 1753 1754 1755 1756 1757 1758 1759 1760
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));
}

1761 1762 1763 1764 1765 1766 1767 1768 1769
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);
  Return(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset));
}

1770 1771
TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) {
  const char* const kMethodName = "Set.prototype.forEach";
1772 1773
  Node* const argc = Parameter(Descriptor::kJSActualArgumentsCount);
  Node* const context = Parameter(Descriptor::kContext);
1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825
  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);

  VARIABLE(var_index, MachineType::PointerRepresentation(), IntPtrConstant(0));
  VARIABLE(var_table, MachineRepresentation::kTagged,
           LoadObjectField(receiver, JSSet::kTableOffset));
  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.
    Node* index = var_index.value();
    Node* table = var_table.value();
    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.
    var_index.Bind(index);
    var_table.Bind(table);
    Goto(&loop);
  }

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

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

1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849
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);
1850 1851
  ThrowTypeError(context, MessageTemplate::kIncompatibleMethodReceiver,
                 StringConstant(kMethodName), receiver);
1852 1853 1854 1855
  BIND(&if_receiver_valid);

  // Check if the {receiver} is exhausted.
  VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant());
1856 1857 1858
  VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant());
  Label return_value(this, {&var_done, &var_value}), return_entry(this),
      return_end(this, Label::kDeferred);
1859 1860 1861 1862

  // Transition the {receiver} table if necessary.
  Node* table;
  Node* index;
1863 1864
  std::tie(table, index) =
      TransitionAndUpdate<JSSetIterator, OrderedHashSet>(receiver);
1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896

  // 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,
1897
                         Heap::kEmptyOrderedHashSetRootIndex);
1898 1899 1900 1901
    Goto(&return_value);
  }
}

1902 1903
template <typename CollectionType>
void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
1904 1905
    Node* const table, Node* const key, Node* const context, Variable* result,
    Label* if_entry_found, Label* if_not_found) {
1906 1907
  Label if_key_smi(this), if_key_string(this), if_key_heap_number(this),
      if_key_bigint(this);
1908 1909

  GotoIf(TaggedIsSmi(key), &if_key_smi);
1910 1911 1912 1913 1914 1915 1916

  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);
1917

1918
  FindOrderedHashTableEntryForOtherKey<CollectionType>(
1919
      context, table, key, result, if_entry_found, if_not_found);
1920 1921 1922

  BIND(&if_key_smi);
  {
1923
    FindOrderedHashTableEntryForSmiKey<CollectionType>(
1924
        table, key, result, if_entry_found, if_not_found);
1925 1926 1927 1928
  }

  BIND(&if_key_string);
  {
1929
    FindOrderedHashTableEntryForStringKey<CollectionType>(
1930
        context, table, key, result, if_entry_found, if_not_found);
1931 1932 1933 1934
  }

  BIND(&if_key_heap_number);
  {
1935
    FindOrderedHashTableEntryForHeapNumberKey<CollectionType>(
1936
        context, table, key, result, if_entry_found, if_not_found);
1937
  }
1938 1939 1940 1941 1942 1943

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

1946
TF_BUILTIN(FindOrderedHashMapEntry, CollectionsBuiltinsAssembler) {
1947 1948 1949 1950 1951 1952 1953 1954
  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);

1955 1956
  TryLookupOrderedHashTableIndex<OrderedHashMap>(
      table, key, context, &entry_start_position, &entry_found, &not_found);
1957 1958

  BIND(&entry_found);
1959
  Return(SmiTag(entry_start_position.value()));
1960 1961

  BIND(&not_found);
1962
  Return(SmiConstant(-1));
1963 1964
}

1965
class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler {
1966 1967
 public:
  explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state)
1968
      : BaseCollectionsAssembler(state) {}
1969

1970
 protected:
1971
  void AddEntry(TNode<HeapObject> table, TNode<IntPtrT> key_index,
1972 1973 1974
                TNode<Object> key, TNode<Object> value,
                TNode<IntPtrT> number_of_elements);

1975 1976 1977
  TNode<Object> AllocateTable(Variant variant, TNode<Context> context,
                              TNode<IntPtrT> at_least_space_for);

1978 1979 1980 1981
  // Generates and sets the identity for a JSRececiver.
  TNode<Smi> CreateIdentityHash(TNode<Object> receiver);
  TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity);

1982
  // Builds code that finds the EphemeronHashTable entry for a {key} using the
1983 1984 1985 1986
  // 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;
1987
  TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash,
1988 1989 1990
                              TNode<IntPtrT> entry_mask,
                              const KeyComparator& key_compare);

1991 1992
  // Builds code that finds an EphemeronHashTable entry available for a new
  // entry.
1993
  TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table,
1994 1995 1996
                                          TNode<IntPtrT> key_hash,
                                          TNode<IntPtrT> entry_mask);

1997
  // Builds code that finds the EphemeronHashTable entry with key that matches
1998 1999
  // {key} and returns the entry's key index. If {key} cannot be found, jumps to
  // {if_not_found}.
2000
  TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key,
2001 2002 2003 2004 2005 2006 2007 2008 2009
                                    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);

2010 2011 2012 2013
  TNode<IntPtrT> LoadNumberOfElements(TNode<HeapObject> table, int offset);
  TNode<IntPtrT> LoadNumberOfDeleted(TNode<HeapObject> table, int offset = 0);
  TNode<HeapObject> LoadTable(SloppyTNode<HeapObject> collection);
  TNode<IntPtrT> LoadTableCapacity(TNode<HeapObject> table);
2014

2015
  void RemoveEntry(TNode<HeapObject> table, TNode<IntPtrT> key_index,
2016 2017 2018 2019 2020 2021 2022
                   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);
};
2023

2024
void WeakCollectionsBuiltinsAssembler::AddEntry(
2025
    TNode<HeapObject> table, TNode<IntPtrT> key_index, TNode<Object> key,
2026
    TNode<Object> value, TNode<IntPtrT> number_of_elements) {
2027
  // See EphemeronHashTable::AddEntry().
2028 2029 2030 2031 2032
  TNode<IntPtrT> value_index = ValueIndexFromKeyIndex(key_index);
  StoreFixedArrayElement(table, key_index, key);
  StoreFixedArrayElement(table, value_index, value);

  // See HashTableBase::ElementAdded().
2033
  StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2034
                         SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2035
}
2036

2037 2038 2039 2040 2041 2042 2043 2044 2045 2046
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);
2047 2048
  TNode<FixedArray> table =
      AllocateFixedArray(HOLEY_ELEMENTS, length, kAllowLargeObjectAllocation);
2049

2050 2051
  Heap::RootListIndex map_root_index = static_cast<Heap::RootListIndex>(
      EphemeronHashTableShape::GetMapRootIndex());
2052
  StoreMapNoWriteBarrier(table, map_root_index);
2053
  StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2054
                         SmiConstant(0), SKIP_WRITE_BARRIER);
2055 2056
  StoreFixedArrayElement(table,
                         EphemeronHashTable::kNumberOfDeletedElementsIndex,
2057
                         SmiConstant(0), SKIP_WRITE_BARRIER);
2058
  StoreFixedArrayElement(table, EphemeronHashTable::kCapacityIndex,
2059
                         SmiFromIntPtr(capacity), SKIP_WRITE_BARRIER);
2060 2061 2062 2063 2064 2065 2066

  TNode<IntPtrT> start = KeyIndexFromEntry(IntPtrConstant(0));
  FillFixedArrayWithValue(HOLEY_ELEMENTS, table, start, length,
                          Heap::kUndefinedValueRootIndex);
  return table;
}

2067 2068 2069 2070 2071 2072
TNode<Smi> WeakCollectionsBuiltinsAssembler::CreateIdentityHash(
    TNode<Object> key) {
  TNode<ExternalReference> function_addr = ExternalConstant(
      ExternalReference::jsreceiver_create_identity_hash(isolate()));
  TNode<ExternalReference> isolate_ptr =
      ExternalConstant(ExternalReference::isolate_address(isolate()));
2073

2074 2075
  MachineType type_ptr = MachineType::Pointer();
  MachineType type_tagged = MachineType::AnyTagged();
2076

2077 2078 2079 2080 2081 2082 2083 2084 2085 2086
  return CAST(CallCFunction2(type_tagged, type_ptr, type_tagged, function_addr,
                             isolate_ptr, key));
}

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

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndex(
2087
    TNode<HeapObject> table, TNode<IntPtrT> key_hash, TNode<IntPtrT> entry_mask,
2088
    const KeyComparator& key_compare) {
2089
  // See HashTable::FirstProbe().
2090 2091
  TVARIABLE(IntPtrT, var_entry, WordAnd(key_hash, entry_mask));
  TVARIABLE(IntPtrT, var_count, IntPtrConstant(0));
2092 2093

  Variable* loop_vars[] = {&var_count, &var_entry};
2094
  Label loop(this, arraysize(loop_vars), loop_vars), if_found(this);
2095 2096
  Goto(&loop);
  BIND(&loop);
2097
  TNode<IntPtrT> key_index;
2098
  {
2099
    key_index = KeyIndexFromEntry(var_entry.value());
2100
    TNode<Object> entry_key = LoadFixedArrayElement(table, key_index);
2101

2102
    key_compare(entry_key, &if_found);
2103 2104

    // See HashTable::NextProbe().
2105
    Increment(&var_count);
2106 2107
    var_entry =
        WordAnd(IntPtrAdd(var_entry.value(), var_count.value()), entry_mask);
2108 2109 2110
    Goto(&loop);
  }

2111 2112 2113 2114 2115
  BIND(&if_found);
  return key_index;
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::FindKeyIndexForInsertion(
2116 2117
    TNode<HeapObject> table, TNode<IntPtrT> key_hash,
    TNode<IntPtrT> entry_mask) {
2118 2119 2120 2121 2122 2123 2124 2125 2126
  // 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(
2127
    TNode<HeapObject> table, TNode<Object> key, TNode<IntPtrT> hash,
2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142
    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(
2143 2144 2145
      IntPtrMul(entry, IntPtrConstant(EphemeronHashTable::kEntrySize)),
      IntPtrConstant(EphemeronHashTable::kElementsStartIndex +
                     EphemeronHashTable::kEntryKeyIndex));
2146 2147 2148
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfElements(
2149
    TNode<HeapObject> table, int offset) {
2150 2151
  TNode<IntPtrT> number_of_elements = SmiUntag(CAST(LoadFixedArrayElement(
      table, EphemeronHashTable::kNumberOfElementsIndex)));
2152 2153 2154 2155
  return IntPtrAdd(number_of_elements, IntPtrConstant(offset));
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadNumberOfDeleted(
2156
    TNode<HeapObject> table, int offset) {
2157
  TNode<IntPtrT> number_of_deleted = SmiUntag(CAST(LoadFixedArrayElement(
2158
      table, EphemeronHashTable::kNumberOfDeletedElementsIndex)));
2159 2160 2161
  return IntPtrAdd(number_of_deleted, IntPtrConstant(offset));
}

2162 2163 2164
TNode<HeapObject> WeakCollectionsBuiltinsAssembler::LoadTable(
    SloppyTNode<HeapObject> collection) {
  return CAST(LoadObjectField(collection, JSWeakCollection::kTableOffset));
2165 2166 2167
}

TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::LoadTableCapacity(
2168
    TNode<HeapObject> table) {
2169
  return SmiUntag(
2170
      CAST(LoadFixedArrayElement(table, EphemeronHashTable::kCapacityIndex)));
2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190
}

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));
}

2191
void WeakCollectionsBuiltinsAssembler::RemoveEntry(
2192
    TNode<HeapObject> table, TNode<IntPtrT> key_index,
2193
    TNode<IntPtrT> number_of_elements) {
2194
  // See EphemeronHashTable::RemoveEntry().
2195 2196 2197 2198 2199 2200
  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);
2201
  StoreFixedArrayElement(table, EphemeronHashTable::kNumberOfElementsIndex,
2202
                         SmiFromIntPtr(number_of_elements), SKIP_WRITE_BARRIER);
2203 2204
  StoreFixedArrayElement(table,
                         EphemeronHashTable::kNumberOfDeletedElementsIndex,
2205
                         SmiFromIntPtr(number_of_deleted), SKIP_WRITE_BARRIER);
2206 2207
}

2208 2209 2210 2211 2212 2213 2214
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);
}

2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230
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)));
}

2231 2232 2233
TNode<IntPtrT> WeakCollectionsBuiltinsAssembler::ValueIndexFromKeyIndex(
    TNode<IntPtrT> key_index) {
  return IntPtrAdd(key_index,
2234 2235
                   IntPtrConstant(EphemeronHashTableShape::kEntryValueIndex -
                                  EphemeronHashTable::kEntryKeyIndex));
2236 2237
}

2238
TF_BUILTIN(WeakMapConstructor, WeakCollectionsBuiltinsAssembler) {
2239
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2240
  TNode<IntPtrT> argc =
2241 2242
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2243 2244 2245

  GenerateConstructor(kWeakMap, isolate()->factory()->WeakMap_string(),
                      new_target, argc, context);
2246 2247 2248
}

TF_BUILTIN(WeakSetConstructor, WeakCollectionsBuiltinsAssembler) {
2249
  TNode<Object> new_target = CAST(Parameter(Descriptor::kJSNewTarget));
2250
  TNode<IntPtrT> argc =
2251 2252
      ChangeInt32ToIntPtr(Parameter(Descriptor::kJSActualArgumentsCount));
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2253 2254 2255

  GenerateConstructor(kWeakSet, isolate()->factory()->WeakSet_string(),
                      new_target, argc, context);
2256 2257
}

2258
TF_BUILTIN(WeakMapLookupHashIndex, WeakCollectionsBuiltinsAssembler) {
2259
  TNode<HeapObject> table = CAST(Parameter(Descriptor::kTable));
2260 2261 2262 2263
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));

  Label if_not_found(this);

2264
  GotoIfNotJSReceiver(key, &if_not_found);
2265 2266 2267 2268 2269 2270 2271

  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)));

2272 2273 2274 2275
  BIND(&if_not_found);
  Return(SmiConstant(-1));
}

2276
TF_BUILTIN(WeakMapGet, WeakCollectionsBuiltinsAssembler) {
2277 2278 2279 2280 2281 2282 2283 2284 2285
  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");

2286
  Node* const table = LoadTable(receiver);
2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297
  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

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

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

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

2298
TF_BUILTIN(WeakMapHas, WeakCollectionsBuiltinsAssembler) {
2299 2300 2301 2302 2303 2304 2305
  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,
2306
                         "WeakMap.prototype.has");
2307

2308
  Node* const table = LoadTable(receiver);
2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319
  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

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

  Return(TrueConstant());

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

2320
// Helper that removes the entry with a given key from the backing store
2321
// (EphemeronHashTable) of a WeakMap or WeakSet.
2322 2323
TF_BUILTIN(WeakCollectionDelete, WeakCollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2324
  TNode<HeapObject> collection = CAST(Parameter(Descriptor::kCollection));
2325 2326 2327 2328
  TNode<Object> key = CAST(Parameter(Descriptor::kKey));

  Label call_runtime(this), if_not_found(this);

2329
  GotoIfNotJSReceiver(key, &if_not_found);
2330 2331

  TNode<IntPtrT> hash = LoadJSReceiverIdentityHash(key, &if_not_found);
2332
  TNode<HeapObject> table = LoadTable(collection);
2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349
  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)));
}

2350 2351
// Helper that sets the key and value to the backing store (EphemeronHashTable)
// of a WeakMap or WeakSet.
2352 2353
TF_BUILTIN(WeakCollectionSet, WeakCollectionsBuiltinsAssembler) {
  TNode<Context> context = CAST(Parameter(Descriptor::kContext));
2354 2355
  TNode<HeapObject> collection = CAST(Parameter(Descriptor::kCollection));
  TNode<JSReceiver> key = CAST(Parameter(Descriptor::kKey));
2356 2357 2358 2359 2360 2361
  TNode<Object> value = CAST(Parameter(Descriptor::kValue));

  CSA_ASSERT(this, IsJSReceiver(key));

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

2362
  TNode<HeapObject> table = LoadTable(collection);
2363 2364 2365 2366
  TNode<IntPtrT> capacity = LoadTableCapacity(table);
  TNode<IntPtrT> entry_mask = EntryMask(capacity);

  TVARIABLE(IntPtrT, var_hash, LoadJSReceiverIdentityHash(key, &if_no_hash));
2367 2368
  TNode<IntPtrT> key_index = FindKeyIndexForKey(table, key, var_hash.value(),
                                                entry_mask, &if_not_found);
2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389

  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 =
2390
        FindKeyIndexForInsertion(table, var_hash.value(), entry_mask);
2391 2392 2393 2394 2395 2396
    AddEntry(table, insertion_key_index, key, value, number_of_elements);
    Return(collection);
  }
  BIND(&call_runtime);
  {
    CallRuntime(Runtime::kWeakCollectionSet, context, collection, key, value,
2397
                SmiTag(var_hash.value()));
2398 2399 2400 2401
    Return(collection);
  }
}

2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412
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));
}

2413
TF_BUILTIN(WeakMapPrototypeSet, WeakCollectionsBuiltinsAssembler) {
2414 2415 2416 2417 2418 2419 2420 2421 2422
  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);
2423
  GotoIfNotJSReceiver(key, &throw_invalid_key);
2424 2425 2426 2427 2428 2429 2430 2431

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

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

2432
TF_BUILTIN(WeakSetPrototypeAdd, WeakCollectionsBuiltinsAssembler) {
2433 2434 2435 2436 2437 2438 2439 2440
  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);
2441
  GotoIfNotJSReceiver(value, &throw_invalid_value);
2442 2443 2444 2445 2446 2447 2448 2449

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

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

2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461
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));
}

2462
TF_BUILTIN(WeakSetHas, WeakCollectionsBuiltinsAssembler) {
2463 2464 2465 2466 2467 2468 2469
  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,
2470
                         "WeakSet.prototype.has");
2471

2472
  Node* const table = LoadTable(receiver);
2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483
  Node* const index =
      CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key);

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

  Return(TrueConstant());

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

2484 2485
}  // namespace internal
}  // namespace v8