diff options
Diffstat (limited to 'deps/v8/src/builtins/builtins-collections-gen.cc')
| -rw-r--r-- | deps/v8/src/builtins/builtins-collections-gen.cc | 1357 |
1 files changed, 1357 insertions, 0 deletions
diff --git a/deps/v8/src/builtins/builtins-collections-gen.cc b/deps/v8/src/builtins/builtins-collections-gen.cc new file mode 100644 index 0000000000..9f65065db5 --- /dev/null +++ b/deps/v8/src/builtins/builtins-collections-gen.cc @@ -0,0 +1,1357 @@ +// 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" +#include "src/objects/hash-table.h" + +namespace v8 { +namespace internal { + +using compiler::Node; + +class CollectionsBuiltinsAssembler : public CodeStubAssembler { + public: + explicit CollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state) + : CodeStubAssembler(state) {} + + protected: + Node* AllocateJSMap(Node* js_map_function); + + template <typename CollectionType> + Node* AllocateOrderedHashTable(); + Node* AllocateJSCollection(Node* js_map_function); + template <typename IteratorType> + Node* AllocateJSCollectionIterator(Node* context, int map_index, + Node* collection); + + Node* CallGetHashRaw(Node* const key); + template <typename CollectionType, int entrysize> + Node* CallHasRaw(Node* const table, Node* const key); + + // 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); + template <typename IteratorType, typename TableType> + std::tuple<Node*, Node*> TransitionAndUpdate(Node* const iterator); + template <typename TableType> + std::tuple<Node*, Node*, Node*> NextSkipHoles(Node* table, Node* index, + Label* if_end); + + // Builds code that finds OrderedHashTable entry for a key with hash code + // {hash} with using the comparison code generated by {key_compare}. The code + // jumps to {entry_found} if the key is found, or to {not_found} if the key + // was not found. In the {entry_found} branch, the variable + // entry_start_position will be bound to the index of the entry (relative to + // OrderedHashTable::kHashTableStartIndex). + // + // The {CollectionType} template parameter stands for the particular instance + // of OrderedHashTable, it should be OrderedHashMap or OrderedHashSet. + template <typename CollectionType> + void FindOrderedHashTableEntry( + Node* table, Node* hash, + std::function<void(Node* other, Label* if_same, Label* if_not_same)> + key_compare, + Variable* entry_start_position, Label* entry_found, Label* not_found); + + // Specialization for Smi. + template <typename CollectionType> + void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged, + Variable* entry_start_position, + Label* entry_found, Label* not_found); + void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same, + Label* if_not_same); + + // Specialization for heap numbers. + void SameValueZeroHeapNumber(Node* key_string, Node* candidate_key, + Label* if_same, Label* if_not_same); + template <typename CollectionType> + void FindOrderedHashTableEntryForHeapNumberKey(Node* context, Node* table, + Node* key_heap_number, + Variable* entry_start_position, + Label* entry_found, + Label* not_found); + + // Specialization for string. + template <typename CollectionType> + void FindOrderedHashTableEntryForStringKey(Node* context, Node* table, + Node* key_tagged, + Variable* entry_start_position, + Label* entry_found, + Label* not_found); + Node* ComputeIntegerHashForString(Node* context, Node* string_key); + void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key, + Label* if_same, Label* if_not_same); + + // Specialization for non-strings, non-numbers. For those we only need + // reference equality to compare the keys. + template <typename CollectionType> + void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table, + Node* key, + Variable* entry_start_position, + Label* entry_found, + Label* not_found); +}; + +template <typename CollectionType> +Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() { + static const int kCapacity = CollectionType::kMinCapacity; + static const int kBucketCount = kCapacity / CollectionType::kLoadFactor; + static const int kDataTableLength = kCapacity * CollectionType::kEntrySize; + static const int kFixedArrayLength = + CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength; + static const int kDataTableStartIndex = + CollectionType::kHashTableStartIndex + kBucketCount; + + STATIC_ASSERT(base::bits::IsPowerOfTwo(kCapacity)); + STATIC_ASSERT(kCapacity <= CollectionType::kMaxCapacity); + + // Allocate the table and add the proper map. + const ElementsKind elements_kind = HOLEY_ELEMENTS; + Node* const length_intptr = IntPtrConstant(kFixedArrayLength); + Node* const table = AllocateFixedArray(elements_kind, length_intptr); + CSA_ASSERT(this, + IntPtrLessThanOrEqual( + length_intptr, IntPtrConstant(FixedArray::kMaxRegularLength))); + Heap::RootListIndex map_index = Heap::kOrderedHashTableMapRootIndex; + // TODO(gsathya): Directly store correct in AllocateFixedArray, + // instead of overwriting here. + StoreMapNoWriteBarrier(table, map_index); + + // Initialize the OrderedHashTable fields. + const WriteBarrierMode barrier_mode = SKIP_WRITE_BARRIER; + StoreFixedArrayElement(table, CollectionType::kNumberOfElementsIndex, + SmiConstant(0), barrier_mode); + StoreFixedArrayElement(table, CollectionType::kNumberOfDeletedElementsIndex, + SmiConstant(0), barrier_mode); + StoreFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex, + SmiConstant(kBucketCount), barrier_mode); + + // Fill the buckets with kNotFound. + Node* const not_found = SmiConstant(CollectionType::kNotFound); + STATIC_ASSERT(CollectionType::kHashTableStartIndex == + CollectionType::kNumberOfBucketsIndex + 1); + STATIC_ASSERT((CollectionType::kHashTableStartIndex + kBucketCount) == + kDataTableStartIndex); + for (int i = 0; i < kBucketCount; i++) { + StoreFixedArrayElement(table, CollectionType::kHashTableStartIndex + i, + not_found, barrier_mode); + } + + // Fill the data table with undefined. + STATIC_ASSERT(kDataTableStartIndex + kDataTableLength == kFixedArrayLength); + for (int i = 0; i < kDataTableLength; i++) { + StoreFixedArrayElement(table, kDataTableStartIndex + i, UndefinedConstant(), + barrier_mode); + } + + return table; +} + +Node* CollectionsBuiltinsAssembler::AllocateJSCollection( + Node* js_map_function) { + CSA_ASSERT(this, IsConstructorMap(LoadMap(js_map_function))); + Node* const initial_map = LoadObjectField( + js_map_function, JSFunction::kPrototypeOrInitialMapOffset); + Node* const instance = AllocateJSObjectFromMap(initial_map); + + StoreObjectFieldRoot(instance, JSMap::kTableOffset, + Heap::kUndefinedValueRootIndex); + + return instance; +} + +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); + StoreObjectFieldRoot(iterator, IteratorType::kPropertiesOrHashOffset, + Heap::kEmptyFixedArrayRootIndex); + StoreObjectFieldRoot(iterator, IteratorType::kElementsOffset, + Heap::kEmptyFixedArrayRootIndex); + StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kTableOffset, table); + StoreObjectFieldNoWriteBarrier(iterator, IteratorType::kIndexOffset, + SmiConstant(0)); + return iterator; +} + +TF_BUILTIN(MapConstructor, CollectionsBuiltinsAssembler) { + const int kIterableArg = 0; + + Node* argc = + ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount)); + CodeStubArguments args(this, argc); + + Node* const iterable = args.GetOptionalArgumentValue(kIterableArg); + Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget); + Node* const context = Parameter(BuiltinDescriptor::kContext); + + Label if_target_is_undefined(this, Label::kDeferred); + GotoIf(IsUndefined(new_target), &if_target_is_undefined); + + Node* const native_context = LoadNativeContext(context); + Node* const js_map_fun = + LoadContextElement(native_context, Context::JS_MAP_FUN_INDEX); + + VARIABLE(var_result, MachineRepresentation::kTagged); + + Label init(this), exit(this), if_targetisnotmodified(this), + if_targetismodified(this); + Branch(WordEqual(js_map_fun, new_target), &if_targetisnotmodified, + &if_targetismodified); + + BIND(&if_targetisnotmodified); + { + Node* const instance = AllocateJSCollection(js_map_fun); + var_result.Bind(instance); + Goto(&init); + } + + BIND(&if_targetismodified); + { + ConstructorBuiltinsAssembler constructor_assembler(this->state()); + Node* const instance = constructor_assembler.EmitFastNewObject( + context, js_map_fun, new_target); + var_result.Bind(instance); + Goto(&init); + } + + BIND(&init); + Node* table = AllocateOrderedHashTable<OrderedHashMap>(); + StoreObjectField(var_result.value(), JSMap::kTableOffset, table); + + GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit); + + Label if_notcallable(this); + // TODO(gsathya): Add fast path for unmodified maps. + Node* const adder = GetProperty(context, var_result.value(), + isolate()->factory()->set_string()); + GotoIf(TaggedIsSmi(adder), &if_notcallable); + GotoIfNot(IsCallable(adder), &if_notcallable); + + IteratorBuiltinsAssembler iterator_assembler(this->state()); + Node* const iterator = iterator_assembler.GetIterator(context, iterable); + GotoIf(IsUndefined(iterator), &exit); + + Node* const fast_iterator_result_map = + LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX); + + VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant()); + + Label loop(this), if_notobject(this), if_exception(this); + Goto(&loop); + + BIND(&loop); + { + Node* const next = iterator_assembler.IteratorStep( + context, iterator, &exit, fast_iterator_result_map); + + Node* const next_value = iterator_assembler.IteratorValue( + context, next, fast_iterator_result_map); + + GotoIf(TaggedIsSmi(next_value), &if_notobject); + GotoIfNot(IsJSReceiver(next_value), &if_notobject); + + Node* const k = + GetProperty(context, next_value, isolate()->factory()->zero_string()); + GotoIfException(k, &if_exception, &var_exception); + + Node* const v = + GetProperty(context, next_value, isolate()->factory()->one_string()); + GotoIfException(v, &if_exception, &var_exception); + + Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder, + var_result.value(), k, v); + GotoIfException(add_call, &if_exception, &var_exception); + Goto(&loop); + + BIND(&if_notobject); + { + Node* const exception = MakeTypeError( + MessageTemplate::kIteratorValueNotAnObject, context, next_value); + var_exception.Bind(exception); + Goto(&if_exception); + } + } + + BIND(&if_exception); + { + iterator_assembler.IteratorCloseOnException(context, iterator, + &var_exception); + } + + BIND(&if_notcallable); + { + Node* const receiver_str = HeapConstant(isolate()->factory()->add_string()); + ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder, + receiver_str, var_result.value()); + } + + BIND(&if_target_is_undefined); + ThrowTypeError(context, MessageTemplate::kConstructorNotFunction, + HeapConstant(isolate()->factory()->Map_string())); + + BIND(&exit); + args.PopAndReturn(var_result.value()); +} + +TF_BUILTIN(SetConstructor, CollectionsBuiltinsAssembler) { + const int kIterableArg = 0; + + Node* argc = + ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount)); + CodeStubArguments args(this, argc); + + Node* const iterable = args.GetOptionalArgumentValue(kIterableArg); + Node* const new_target = Parameter(BuiltinDescriptor::kNewTarget); + Node* const context = Parameter(BuiltinDescriptor::kContext); + + Label if_target_is_undefined(this, Label::kDeferred); + GotoIf(IsUndefined(new_target), &if_target_is_undefined); + + Node* const native_context = LoadNativeContext(context); + Node* const js_set_fun = + LoadContextElement(native_context, Context::JS_SET_FUN_INDEX); + + VARIABLE(var_result, MachineRepresentation::kTagged); + + Label init(this), exit(this), if_targetisnotmodified(this), + if_targetismodified(this); + Branch(WordEqual(js_set_fun, new_target), &if_targetisnotmodified, + &if_targetismodified); + + BIND(&if_targetisnotmodified); + { + Node* const instance = AllocateJSCollection(js_set_fun); + var_result.Bind(instance); + Goto(&init); + } + + BIND(&if_targetismodified); + { + ConstructorBuiltinsAssembler constructor_assembler(this->state()); + Node* const instance = constructor_assembler.EmitFastNewObject( + context, js_set_fun, new_target); + var_result.Bind(instance); + Goto(&init); + } + + BIND(&init); + Node* table = AllocateOrderedHashTable<OrderedHashSet>(); + StoreObjectField(var_result.value(), JSSet::kTableOffset, table); + + GotoIf(Word32Or(IsUndefined(iterable), IsNull(iterable)), &exit); + + Label if_notcallable(this); + // TODO(gsathya): Add fast path for unmodified maps. + Node* const adder = GetProperty(context, var_result.value(), + isolate()->factory()->add_string()); + GotoIf(TaggedIsSmi(adder), &if_notcallable); + GotoIfNot(IsCallable(adder), &if_notcallable); + + IteratorBuiltinsAssembler iterator_assembler(this->state()); + Node* const iterator = iterator_assembler.GetIterator(context, iterable); + GotoIf(IsUndefined(iterator), &exit); + + Node* const fast_iterator_result_map = + LoadContextElement(native_context, Context::ITERATOR_RESULT_MAP_INDEX); + + VARIABLE(var_exception, MachineRepresentation::kTagged, TheHoleConstant()); + + Label loop(this), if_notobject(this), if_exception(this); + Goto(&loop); + + BIND(&loop); + { + Node* const next = iterator_assembler.IteratorStep( + context, iterator, &exit, fast_iterator_result_map); + + Node* const next_value = iterator_assembler.IteratorValue( + context, next, fast_iterator_result_map); + + Node* add_call = CallJS(CodeFactory::Call(isolate()), context, adder, + var_result.value(), next_value); + + GotoIfException(add_call, &if_exception, &var_exception); + Goto(&loop); + } + + BIND(&if_exception); + { + iterator_assembler.IteratorCloseOnException(context, iterator, + &var_exception); + } + + BIND(&if_notcallable); + ThrowTypeError(context, MessageTemplate::kPropertyNotFunction, adder, + HeapConstant(isolate()->factory()->add_string()), + var_result.value()); + + BIND(&if_target_is_undefined); + ThrowTypeError(context, MessageTemplate::kConstructorNotFunction, + HeapConstant(isolate()->factory()->Set_string())); + + BIND(&exit); + args.PopAndReturn(var_result.value()); +} + +Node* CollectionsBuiltinsAssembler::CallGetHashRaw(Node* const key) { + Node* const function_addr = ExternalConstant( + ExternalReference::orderedhashmap_gethash_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; +} + +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); +} + +template <typename CollectionType> +void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey( + Node* table, Node* smi_key, Variable* entry_start_position, + Label* entry_found, Label* not_found) { + Node* const key_untagged = SmiUntag(smi_key); + Node* const hash = + ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0))); + FindOrderedHashTableEntry<CollectionType>( + table, hash, + [&](Node* other_key, Label* if_same, Label* if_not_same) { + SameValueZeroSmi(smi_key, other_key, if_same, if_not_same); + }, + entry_start_position, entry_found, not_found); +} + +template <typename CollectionType> +void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey( + Node* context, Node* table, Node* key_tagged, + Variable* entry_start_position, Label* entry_found, Label* not_found) { + Node* const hash = ComputeIntegerHashForString(context, key_tagged); + FindOrderedHashTableEntry<CollectionType>( + table, hash, + [&](Node* other_key, Label* if_same, Label* if_not_same) { + SameValueZeroString(context, key_tagged, other_key, if_same, + if_not_same); + }, + entry_start_position, entry_found, not_found); +} + +template <typename CollectionType> +void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey( + Node* context, Node* table, Node* key_heap_number, + Variable* entry_start_position, Label* entry_found, Label* not_found) { + Node* tagged_hash = CallGetHashRaw(key_heap_number); + CSA_ASSERT(this, TaggedIsSmi(tagged_hash)); + Node* const key_float = LoadHeapNumberValue(key_heap_number); + FindOrderedHashTableEntry<CollectionType>( + table, SmiUntag(tagged_hash), + [&](Node* other_key, Label* if_same, Label* if_not_same) { + SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same); + }, + entry_start_position, entry_found, not_found); +} + +template <typename CollectionType> +void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey( + Node* context, Node* table, Node* key, Variable* entry_start_position, + Label* entry_found, Label* not_found) { + Node* tagged_hash = CallGetHashRaw(key); + CSA_ASSERT(this, TaggedIsSmi(tagged_hash)); + FindOrderedHashTableEntry<CollectionType>( + table, SmiUntag(tagged_hash), + [&](Node* other_key, Label* if_same, Label* if_not_same) { + Branch(WordEqual(key, other_key), if_same, if_not_same); + }, + entry_start_position, entry_found, not_found); +} + +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); + Node* tagged_hash = CallGetHashRaw(string_key); + CSA_ASSERT(this, TaggedIsSmi(tagged_hash)); + var_result.Bind(SmiUntag(tagged_hash)); + Goto(&done); + + 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); +} + +void CollectionsBuiltinsAssembler::SameValueZeroHeapNumber(Node* key_float, + Node* candidate_key, + Label* if_same, + Label* if_not_same) { + Label if_smi(this), if_keyisnan(this); + + // If the candidate is not a string, the keys are not equal. + 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); + } +} + +template <typename CollectionType> +void CollectionsBuiltinsAssembler::FindOrderedHashTableEntry( + Node* table, Node* hash, + std::function<void(Node*, Label*, Label*)> key_compare, + Variable* entry_start_position, Label* entry_found, Label* not_found) { + // Get the index of the bucket. + Node* const number_of_buckets = SmiUntag( + LoadFixedArrayElement(table, CollectionType::kNumberOfBucketsIndex)); + Node* const bucket = + WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1))); + Node* const first_entry = SmiUntag(LoadFixedArrayElement( + table, bucket, CollectionType::kHashTableStartIndex * kPointerSize)); + + // Walk the bucket chain. + { + VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry); + Label loop(this, {&var_entry, entry_start_position}), + continue_next_entry(this); + Goto(&loop); + BIND(&loop); + + // If the entry index is the not-found sentinel, we are done. + GotoIf( + WordEqual(var_entry.value(), IntPtrConstant(CollectionType::kNotFound)), + not_found); + + // Make sure the entry index is within range. + CSA_ASSERT( + this, + UintPtrLessThan( + var_entry.value(), + SmiUntag(SmiAdd( + LoadFixedArrayElement(table, + CollectionType::kNumberOfElementsIndex), + LoadFixedArrayElement( + table, CollectionType::kNumberOfDeletedElementsIndex))))); + + // Compute the index of the entry relative to kHashTableStartIndex. + Node* entry_start = + IntPtrAdd(IntPtrMul(var_entry.value(), + IntPtrConstant(CollectionType::kEntrySize)), + number_of_buckets); + entry_start_position->Bind(entry_start); + + // Load the key from the entry. + Node* const candidate_key = LoadFixedArrayElement( + table, entry_start, + CollectionType::kHashTableStartIndex * kPointerSize); + + key_compare(candidate_key, entry_found, &continue_next_entry); + + BIND(&continue_next_entry); + // Load the index of the next entry in the bucket chain. + var_entry.Bind(SmiUntag(LoadFixedArrayElement( + table, entry_start, + (CollectionType::kHashTableStartIndex + CollectionType::kChainOffset) * + kPointerSize))); + + Goto(&loop); + } +} + +TF_BUILTIN(OrderedHashTableHealIndex, CollectionsBuiltinsAssembler) { + Node* table = Parameter(Descriptor::kTable); + Node* index = Parameter(Descriptor::kIndex); + CSA_ASSERT(this, TaggedIsNotSmi(table)); + CSA_ASSERT(this, TaggedIsSmi(index)); + Label return_index(this), return_zero(this); + + // Check if we need to update the {index}. + GotoIfNot(SmiLessThan(SmiConstant(Smi::kZero), index), &return_zero); + + // 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); + Node* removed_index = LoadFixedArrayElement( + table, i, OrderedHashTableBase::kRemovedHolesIndex * kPointerSize); + GotoIf(SmiGreaterThanOrEqual(removed_index, index), &return_index); + Decrement(var_index, 1, SMI_PARAMETERS); + Increment(var_i); + Goto(&loop); + } + + BIND(&return_index); + Return(var_index.value()); + + BIND(&return_zero); + Return(SmiConstant(Smi::kZero)); +} + +template <typename TableType> +std::tuple<Node*, Node*> CollectionsBuiltinsAssembler::Transition( + Node* const table, Node* const index, + UpdateInTransition const& update_in_transition) { + VARIABLE(var_index, MachineType::PointerRepresentation(), index); + VARIABLE(var_table, MachineRepresentation::kTagged, table); + 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); + var_index.Bind( + SmiUntag(CallBuiltin(Builtins::kOrderedHashTableHealIndex, + NoContextConstant(), table, SmiTag(index)))); + Goto(&loop); + } + BIND(&done_loop); + + // Update with the new {table} and {index}. + update_in_transition(var_table.value(), var_index.value()); + Goto(&if_done); + } + + BIND(&if_done); + return std::tuple<Node*, Node*>(var_table.value(), var_index.value()); +} + +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)); + }); +} + +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); + Increment(var_index); + Branch(IsTheHole(entry_key), &loop, &done_loop); + } + + BIND(&done_loop); + return std::tuple<Node*, Node*, Node*>(entry_key, entry_start_position, + var_index.value()); +} + +TF_BUILTIN(MapGet, CollectionsBuiltinsAssembler) { + Node* const receiver = Parameter(Descriptor::kReceiver); + Node* const key = Parameter(Descriptor::kKey); + Node* const context = Parameter(Descriptor::kContext); + + ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get"); + + Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); + Node* index = CallBuiltin(Builtins::kMapLookupHashIndex, context, table, key); + + Label if_found(this), if_not_found(this); + Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found, + &if_not_found); + + BIND(&if_found); + Return(LoadFixedArrayElement(table, SmiUntag(index))); + + BIND(&if_not_found); + Return(UndefinedConstant()); +} + +TF_BUILTIN(MapHas, CollectionsBuiltinsAssembler) { + Node* const receiver = Parameter(Descriptor::kReceiver); + Node* const key = Parameter(Descriptor::kKey); + Node* const context = Parameter(Descriptor::kContext); + + ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has"); + + Node* const table = LoadObjectField(receiver, JSMap::kTableOffset); + Node* index = CallBuiltin(Builtins::kMapLookupHashIndex, context, table, key); + + Label if_found(this), if_not_found(this); + Branch(SmiGreaterThanOrEqual(index, SmiConstant(0)), &if_found, + &if_not_found); + + BIND(&if_found); + Return(TrueConstant()); + + BIND(&if_not_found); + Return(FalseConstant()); +} + +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)); +} + +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)); +} + +TF_BUILTIN(MapPrototypeForEach, CollectionsBuiltinsAssembler) { + const char* const kMethodName = "Map.prototype.forEach"; + Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount); + Node* const context = Parameter(BuiltinDescriptor::kContext); + 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(); + } +} + +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); + ThrowIncompatibleMethodReceiver(context, kMethodName, receiver); + BIND(&if_receiver_valid); + + // Check if the {receiver} is exhausted. + VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant()); + VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant()); + Label return_value(this, {&var_done, &var_value}), return_entry(this), + return_end(this, Label::kDeferred); + + // Transition the {receiver} table if necessary. + Node* table; + Node* index; + std::tie(table, index) = + TransitionAndUpdate<JSMapIterator, OrderedHashMap>(receiver); + + // 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, + Heap::kEmptyOrderedHashTableRootIndex); + Goto(&return_value); + } +} + +TF_BUILTIN(SetHas, CollectionsBuiltinsAssembler) { + 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); + + 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), + entry_found(this), not_found(this), done(this); + + GotoIf(TaggedIsSmi(key), &if_key_smi); + GotoIf(IsString(key), &if_key_string); + GotoIf(IsHeapNumber(key), &if_key_heap_number); + + FindOrderedHashTableEntryForOtherKey<OrderedHashSet>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + + BIND(&if_key_smi); + { + FindOrderedHashTableEntryForSmiKey<OrderedHashSet>( + table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&if_key_string); + { + FindOrderedHashTableEntryForStringKey<OrderedHashSet>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&if_key_heap_number); + { + FindOrderedHashTableEntryForHeapNumberKey<OrderedHashSet>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&entry_found); + Return(TrueConstant()); + + BIND(¬_found); + Return(FalseConstant()); +} + +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)); +} + +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)); +} + +TF_BUILTIN(SetPrototypeForEach, CollectionsBuiltinsAssembler) { + const char* const kMethodName = "Set.prototype.forEach"; + Node* const argc = Parameter(BuiltinDescriptor::kArgumentsCount); + Node* const context = Parameter(BuiltinDescriptor::kContext); + 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(); + } +} + +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); + ThrowIncompatibleMethodReceiver(context, kMethodName, receiver); + BIND(&if_receiver_valid); + + // Check if the {receiver} is exhausted. + VARIABLE(var_done, MachineRepresentation::kTagged, TrueConstant()); + VARIABLE(var_value, MachineRepresentation::kTagged, UndefinedConstant()); + Label return_value(this, {&var_done, &var_value}), return_entry(this), + return_end(this, Label::kDeferred); + + // Transition the {receiver} table if necessary. + Node* table; + Node* index; + std::tie(table, index) = + TransitionAndUpdate<JSSetIterator, OrderedHashSet>(receiver); + + // 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, + Heap::kEmptyOrderedHashTableRootIndex); + Goto(&return_value); + } +} + +TF_BUILTIN(MapLookupHashIndex, CollectionsBuiltinsAssembler) { + 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)); + VARIABLE(result, MachineRepresentation::kTaggedSigned, IntPtrConstant(0)); + Label if_key_smi(this), if_key_string(this), if_key_heap_number(this), + entry_found(this), not_found(this), done(this); + + GotoIf(TaggedIsSmi(key), &if_key_smi); + GotoIf(IsString(key), &if_key_string); + GotoIf(IsHeapNumber(key), &if_key_heap_number); + + FindOrderedHashTableEntryForOtherKey<OrderedHashMap>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + + BIND(&if_key_smi); + { + FindOrderedHashTableEntryForSmiKey<OrderedHashMap>( + table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&if_key_string); + { + FindOrderedHashTableEntryForStringKey<OrderedHashMap>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&if_key_heap_number); + { + FindOrderedHashTableEntryForHeapNumberKey<OrderedHashMap>( + context, table, key, &entry_start_position, &entry_found, ¬_found); + } + + BIND(&entry_found); + Node* index = IntPtrAdd(entry_start_position.value(), + IntPtrConstant(OrderedHashMap::kHashTableStartIndex + + OrderedHashMap::kValueOffset)); + result.Bind(SmiTag(index)); + Goto(&done); + + BIND(¬_found); + result.Bind(SmiConstant(-1)); + Goto(&done); + + BIND(&done); + Return(result.value()); +} + +TF_BUILTIN(WeakMapLookupHashIndex, CollectionsBuiltinsAssembler) { + Node* const table = Parameter(Descriptor::kTable); + Node* const key = Parameter(Descriptor::kKey); + + Label if_found(this), if_not_found(this); + + Node* const capacity = + SmiUntag(LoadFixedArrayElement(table, WeakHashTable::kCapacityIndex)); + Node* const mask = IntPtrSub(capacity, IntPtrConstant(1)); + + Node* const hash = SmiUntag(CallGetHashRaw(key)); + + GotoIf(IntPtrLessThan(hash, IntPtrConstant(0)), &if_not_found); + + // See HashTable::FirstProbe(). + Node* entry = WordAnd(hash, mask); + + VARIABLE(var_count, MachineType::PointerRepresentation(), IntPtrConstant(0)); + VARIABLE(var_entry, MachineType::PointerRepresentation(), entry); + Variable* loop_vars[] = {&var_count, &var_entry}; + Label loop(this, arraysize(loop_vars), loop_vars); + Goto(&loop); + BIND(&loop); + Node* index; + { + Node* entry = var_entry.value(); + + index = IntPtrMul(entry, IntPtrConstant(WeakHashTable::kEntrySize)); + index = + IntPtrAdd(index, IntPtrConstant(WeakHashTable::kElementsStartIndex)); + + Node* current = LoadFixedArrayElement(table, index); + GotoIf(WordEqual(current, UndefinedConstant()), &if_not_found); + GotoIf(WordEqual(current, key), &if_found); + + // See HashTable::NextProbe(). + Increment(var_count); + entry = WordAnd(IntPtrAdd(entry, var_count.value()), mask); + + var_entry.Bind(entry); + Goto(&loop); + } + + BIND(&if_not_found); + Return(SmiConstant(-1)); + + BIND(&if_found); + Return(SmiTag(IntPtrAdd(index, IntPtrConstant(1)))); +} + +TF_BUILTIN(WeakMapGet, CollectionsBuiltinsAssembler) { + 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"); + + GotoIf(TaggedIsSmi(key), &return_undefined); + GotoIfNot(IsJSReceiver(key), &return_undefined); + + Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset); + + 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()); +} + +TF_BUILTIN(WeakMapHas, CollectionsBuiltinsAssembler) { + 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, + "WeakMap.prototype.get"); + + GotoIf(TaggedIsSmi(key), &return_false); + GotoIfNot(IsJSReceiver(key), &return_false); + + Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset); + + Node* const index = + CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key); + + GotoIf(WordEqual(index, SmiConstant(-1)), &return_false); + + Return(TrueConstant()); + + BIND(&return_false); + Return(FalseConstant()); +} + +TF_BUILTIN(WeakSetHas, CollectionsBuiltinsAssembler) { + 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, + "WeakSet.prototype.get"); + + GotoIf(TaggedIsSmi(key), &return_false); + GotoIfNot(IsJSReceiver(key), &return_false); + + Node* const table = LoadObjectField(receiver, JSWeakCollection::kTableOffset); + + Node* const index = + CallBuiltin(Builtins::kWeakMapLookupHashIndex, context, table, key); + + GotoIf(WordEqual(index, SmiConstant(-1)), &return_false); + + Return(TrueConstant()); + + BIND(&return_false); + Return(FalseConstant()); +} + +} // namespace internal +} // namespace v8 |