| // 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/factory-inl.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* GetHash(Node* const key); |
| Node* CallGetHashRaw(Node* const key); |
| Node* CallGetOrCreateHashRaw(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. |
| // The {result} variable will contain the entry index if the key was found, |
| // or the hash code otherwise. |
| template <typename CollectionType> |
| void FindOrderedHashTableEntryForSmiKey(Node* table, Node* key_tagged, |
| Variable* result, 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. |
| // The {result} variable will contain the entry index if the key was found, |
| // or the hash code otherwise. |
| 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* result, |
| Label* entry_found, |
| Label* not_found); |
| |
| // 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); |
| |
| // Specialization for string. |
| // The {result} variable will contain the entry index if the key was found, |
| // or the hash code otherwise. |
| template <typename CollectionType> |
| void FindOrderedHashTableEntryForStringKey(Node* context, Node* table, |
| Node* key_tagged, Variable* result, |
| 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. |
| // 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. |
| template <typename CollectionType> |
| void FindOrderedHashTableEntryForOtherKey(Node* context, Node* table, |
| Node* key, Variable* result, |
| Label* entry_found, |
| Label* not_found); |
| |
| template <typename CollectionType> |
| void TryLookupOrderedHashTableIndex(Node* const table, Node* const key, |
| Node* const context, Variable* result, |
| Label* if_entry_found, |
| Label* if_not_found); |
| |
| 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); |
| void StoreOrderedHashSetNewEntry(Node* const table, Node* const key, |
| Node* const hash, |
| Node* const number_of_buckets, |
| Node* const occupancy); |
| }; |
| |
| 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::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; |
| } |
| |
| 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 SmiUntag(result); |
| } |
| |
| Node* CollectionsBuiltinsAssembler::GetHash(Node* const key) { |
| VARIABLE(var_result, MachineType::PointerRepresentation()); |
| Label if_jsobject(this), other(this), done(this); |
| Node* instance_type = LoadMapInstanceType(LoadMap(key)); |
| Branch(IsJSObjectInstanceType(instance_type), &if_jsobject, &other); |
| |
| BIND(&if_jsobject); |
| { |
| Node* hash = LoadHashForJSObject(key, instance_type); |
| // TODO(gsathya): Change all uses of -1 to PropertyArray::kNoHashSentinel. |
| var_result.Bind(SelectConstant( |
| Word32Equal(hash, Int32Constant(PropertyArray::kNoHashSentinel)), |
| IntPtrConstant(-1), ChangeInt32ToIntPtr(hash), |
| MachineType::PointerRepresentation())); |
| Goto(&done); |
| } |
| |
| BIND(&other); |
| { |
| var_result.Bind(CallGetHashRaw(key)); |
| Goto(&done); |
| } |
| |
| BIND(&done); |
| return var_result.value(); |
| } |
| |
| 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* result, Label* entry_found, |
| Label* not_found) { |
| Node* const key_untagged = SmiUntag(smi_key); |
| Node* const hash = |
| ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0))); |
| CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0))); |
| result->Bind(hash); |
| FindOrderedHashTableEntry<CollectionType>( |
| table, hash, |
| [&](Node* other_key, Label* if_same, Label* if_not_same) { |
| SameValueZeroSmi(smi_key, other_key, if_same, if_not_same); |
| }, |
| result, entry_found, not_found); |
| } |
| |
| template <typename CollectionType> |
| void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForStringKey( |
| Node* context, Node* table, Node* key_tagged, Variable* result, |
| Label* entry_found, Label* not_found) { |
| Node* const hash = ComputeIntegerHashForString(context, key_tagged); |
| CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0))); |
| result->Bind(hash); |
| 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); |
| }, |
| result, entry_found, not_found); |
| } |
| |
| template <typename CollectionType> |
| void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForHeapNumberKey( |
| Node* context, Node* table, Node* key_heap_number, Variable* result, |
| Label* entry_found, Label* not_found) { |
| Node* hash = CallGetHashRaw(key_heap_number); |
| CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0))); |
| result->Bind(hash); |
| Node* const key_float = LoadHeapNumberValue(key_heap_number); |
| FindOrderedHashTableEntry<CollectionType>( |
| table, hash, |
| [&](Node* other_key, Label* if_same, Label* if_not_same) { |
| SameValueZeroHeapNumber(key_float, other_key, if_same, if_not_same); |
| }, |
| result, entry_found, not_found); |
| } |
| |
| 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); |
| } |
| |
| template <typename CollectionType> |
| void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey( |
| Node* context, Node* table, Node* key, Variable* result, Label* entry_found, |
| Label* not_found) { |
| Node* hash = GetHash(key); |
| result->Bind(hash); |
| FindOrderedHashTableEntry<CollectionType>( |
| table, hash, |
| [&](Node* other_key, Label* if_same, Label* if_not_same) { |
| Branch(WordEqual(key, other_key), if_same, if_not_same); |
| }, |
| result, 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); |
| var_result.Bind(CallGetHashRaw(string_key)); |
| 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::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); |
| |
| Branch(WordEqual(CallRuntime(Runtime::kBigIntEqual, NoContextConstant(), key, |
| 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); |
| |
| 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. |
| Node* entry_start; |
| Label if_key_found(this); |
| { |
| 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. |
| entry_start = |
| IntPtrAdd(IntPtrMul(var_entry.value(), |
| IntPtrConstant(CollectionType::kEntrySize)), |
| number_of_buckets); |
| |
| // Load the key from the entry. |
| Node* const candidate_key = LoadFixedArrayElement( |
| table, entry_start, |
| CollectionType::kHashTableStartIndex * kPointerSize); |
| |
| key_compare(candidate_key, &if_key_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); |
| } |
| |
| BIND(&if_key_found); |
| entry_start_position->Bind(entry_start); |
| Goto(entry_found); |
| } |
| |
| 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()); |
| } |
| |
| 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(); |
| } |
| |
| TF_BUILTIN(MapSet, CollectionsBuiltinsAssembler) { |
| 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); |
| |
| TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context, |
| &entry_start_position_or_hash, |
| &entry_found, ¬_found); |
| |
| 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(¬_found); |
| { |
| // If we have a hash code, we can start adding the new entry. |
| GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(), |
| IntPtrConstant(0)), |
| &add_entry); |
| |
| // Otherwise, go to runtime to compute the hash code. |
| entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key))); |
| 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. |
| number_of_buckets.Bind(SmiUntag( |
| LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex))); |
| |
| STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2); |
| Node* const capacity = WordShl(number_of_buckets.value(), 1); |
| Node* const number_of_elements = SmiUntag( |
| CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset))); |
| Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField( |
| table, OrderedHashMap::kNumberOfDeletedElementsOffset))); |
| 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)); |
| number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement( |
| table_var.value(), OrderedHashMap::kNumberOfBucketsIndex))); |
| 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))); |
| 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. |
| Node* const number_of_elements = |
| LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset); |
| StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset, |
| SmiAdd(number_of_elements, SmiConstant(1))); |
| } |
| |
| TF_BUILTIN(MapDelete, CollectionsBuiltinsAssembler) { |
| 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); |
| |
| TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context, |
| &entry_start_position_or_hash, |
| &entry_found, ¬_found); |
| |
| BIND(¬_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. |
| Node* const number_of_elements = SmiSub( |
| CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)), |
| SmiConstant(1)); |
| StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset, |
| number_of_elements); |
| Node* const number_of_deleted = |
| SmiAdd(CAST(LoadObjectField( |
| table, OrderedHashMap::kNumberOfDeletedElementsOffset)), |
| SmiConstant(1)); |
| StoreObjectFieldNoWriteBarrier( |
| table, OrderedHashMap::kNumberOfDeletedElementsOffset, number_of_deleted); |
| |
| Node* const number_of_buckets = |
| LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex); |
| |
| // 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()); |
| } |
| |
| TF_BUILTIN(SetAdd, CollectionsBuiltinsAssembler) { |
| 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, ¬_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(¬_found); |
| { |
| // If we have a hash code, we can start adding the new entry. |
| GotoIf(IntPtrGreaterThanOrEqual(entry_start_position_or_hash.value(), |
| IntPtrConstant(0)), |
| &add_entry); |
| |
| // Otherwise, go to runtime to compute the hash code. |
| entry_start_position_or_hash.Bind(SmiUntag((CallGetOrCreateHashRaw(key)))); |
| 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. |
| number_of_buckets.Bind(SmiUntag( |
| LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex))); |
| |
| STATIC_ASSERT(OrderedHashSet::kLoadFactor == 2); |
| Node* const capacity = WordShl(number_of_buckets.value(), 1); |
| Node* const number_of_elements = SmiUntag( |
| CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset))); |
| Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField( |
| table, OrderedHashSet::kNumberOfDeletedElementsOffset))); |
| 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)); |
| number_of_buckets.Bind(SmiUntag(LoadFixedArrayElement( |
| table_var.value(), OrderedHashSet::kNumberOfBucketsIndex))); |
| 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))); |
| 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. |
| Node* const number_of_elements = |
| LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset); |
| StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset, |
| SmiAdd(number_of_elements, SmiConstant(1))); |
| } |
| |
| TF_BUILTIN(SetDelete, CollectionsBuiltinsAssembler) { |
| 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, ¬_found); |
| |
| BIND(¬_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. |
| Node* const number_of_elements = SmiSub( |
| CAST(LoadObjectField(table, OrderedHashSet::kNumberOfElementsOffset)), |
| SmiConstant(1)); |
| StoreObjectFieldNoWriteBarrier(table, OrderedHashSet::kNumberOfElementsOffset, |
| number_of_elements); |
| Node* const number_of_deleted = |
| SmiAdd(CAST(LoadObjectField( |
| table, OrderedHashSet::kNumberOfDeletedElementsOffset)), |
| SmiConstant(1)); |
| StoreObjectFieldNoWriteBarrier( |
| table, OrderedHashSet::kNumberOfDeletedElementsOffset, number_of_deleted); |
| |
| Node* const number_of_buckets = |
| LoadFixedArrayElement(table, OrderedHashSet::kNumberOfBucketsIndex); |
| |
| // 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()); |
| } |
| |
| 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), |
| if_key_bigint(this), entry_found(this), not_found(this), done(this); |
| |
| GotoIf(TaggedIsSmi(key), &if_key_smi); |
| |
| 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); |
| |
| 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(&if_key_bigint); |
| { |
| FindOrderedHashTableEntryForBigIntKey<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); |
| } |
| } |
| |
| template <typename CollectionType> |
| void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex( |
| Node* const table, Node* const key, Node* const context, Variable* result, |
| Label* if_entry_found, Label* if_not_found) { |
| Label if_key_smi(this), if_key_string(this), if_key_heap_number(this), |
| if_key_bigint(this); |
| |
| GotoIf(TaggedIsSmi(key), &if_key_smi); |
| |
| 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); |
| |
| FindOrderedHashTableEntryForOtherKey<CollectionType>( |
| context, table, key, result, if_entry_found, if_not_found); |
| |
| BIND(&if_key_smi); |
| { |
| FindOrderedHashTableEntryForSmiKey<CollectionType>( |
| table, key, result, if_entry_found, if_not_found); |
| } |
| |
| BIND(&if_key_string); |
| { |
| FindOrderedHashTableEntryForStringKey<CollectionType>( |
| context, table, key, result, if_entry_found, if_not_found); |
| } |
| |
| BIND(&if_key_heap_number); |
| { |
| FindOrderedHashTableEntryForHeapNumberKey<CollectionType>( |
| context, table, key, result, if_entry_found, if_not_found); |
| } |
| |
| BIND(&if_key_bigint); |
| { |
| FindOrderedHashTableEntryForBigIntKey<CollectionType>( |
| context, table, key, result, if_entry_found, if_not_found); |
| } |
| } |
| |
| 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)); |
| Label entry_found(this), not_found(this); |
| |
| TryLookupOrderedHashTableIndex<OrderedHashMap>( |
| table, key, context, &entry_start_position, &entry_found, ¬_found); |
| |
| BIND(&entry_found); |
| Node* index = IntPtrAdd(entry_start_position.value(), |
| IntPtrConstant(OrderedHashMap::kHashTableStartIndex + |
| OrderedHashMap::kValueOffset)); |
| Return(SmiTag(index)); |
| |
| BIND(¬_found); |
| Return(SmiConstant(-1)); |
| } |
| |
| 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 = GetHash(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(Signed(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 |