1 // Copyright 2018 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_ 6 #define V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_ 7 8 #include "src/codegen/code-stub-assembler.h" 9 10 namespace v8 { 11 namespace internal { 12 13 void BranchIfIterableWithOriginalKeyOrValueMapIterator( 14 compiler::CodeAssemblerState* state, TNode<Object> iterable, 15 TNode<Context> context, compiler::CodeAssemblerLabel* if_true, 16 compiler::CodeAssemblerLabel* if_false); 17 18 void BranchIfIterableWithOriginalValueSetIterator( 19 compiler::CodeAssemblerState* state, TNode<Object> iterable, 20 TNode<Context> context, compiler::CodeAssemblerLabel* if_true, 21 compiler::CodeAssemblerLabel* if_false); 22 23 class BaseCollectionsAssembler : public CodeStubAssembler { 24 public: BaseCollectionsAssembler(compiler::CodeAssemblerState * state)25 explicit BaseCollectionsAssembler(compiler::CodeAssemblerState* state) 26 : CodeStubAssembler(state) {} 27 28 virtual ~BaseCollectionsAssembler() = default; 29 30 void GotoIfCannotBeHeldWeakly(const TNode<Object> obj, 31 Label* if_cannot_be_held_weakly); 32 33 protected: 34 enum Variant { kMap, kSet, kWeakMap, kWeakSet }; 35 36 // Adds an entry to a collection. For Maps, properly handles extracting the 37 // key and value from the entry (see LoadKeyValue()). 38 void AddConstructorEntry(Variant variant, TNode<Context> context, 39 TNode<Object> collection, TNode<Object> add_function, 40 TNode<Object> key_value, 41 Label* if_may_have_side_effects = nullptr, 42 Label* if_exception = nullptr, 43 TVariable<Object>* var_exception = nullptr); 44 45 // Adds constructor entries to a collection. Choosing a fast path when 46 // possible. 47 void AddConstructorEntries(Variant variant, TNode<Context> context, 48 TNode<Context> native_context, 49 TNode<HeapObject> collection, 50 TNode<Object> initial_entries); 51 52 // Fast path for adding constructor entries. Assumes the entries are a fast 53 // JS array (see CodeStubAssembler::BranchIfFastJSArray()). 54 void AddConstructorEntriesFromFastJSArray(Variant variant, 55 TNode<Context> context, 56 TNode<Context> native_context, 57 TNode<Object> collection, 58 TNode<JSArray> fast_jsarray, 59 Label* if_may_have_side_effects); 60 61 // Adds constructor entries to a collection using the iterator protocol. 62 void AddConstructorEntriesFromIterable(Variant variant, 63 TNode<Context> context, 64 TNode<Context> native_context, 65 TNode<Object> collection, 66 TNode<Object> iterable); 67 68 // Constructs a collection instance. Choosing a fast path when possible. 69 TNode<JSObject> AllocateJSCollection(TNode<Context> context, 70 TNode<JSFunction> constructor, 71 TNode<JSReceiver> new_target); 72 73 // Fast path for constructing a collection instance if the constructor 74 // function has not been modified. 75 TNode<JSObject> AllocateJSCollectionFast(TNode<JSFunction> constructor); 76 77 // Fallback for constructing a collection instance if the constructor function 78 // has been modified. 79 TNode<JSObject> AllocateJSCollectionSlow(TNode<Context> context, 80 TNode<JSFunction> constructor, 81 TNode<JSReceiver> new_target); 82 83 // Allocates the backing store for a collection. 84 virtual TNode<HeapObject> AllocateTable( 85 Variant variant, TNode<IntPtrT> at_least_space_for) = 0; 86 87 // Main entry point for a collection constructor builtin. 88 void GenerateConstructor(Variant variant, 89 Handle<String> constructor_function_name, 90 TNode<Object> new_target, TNode<IntPtrT> argc, 91 TNode<Context> context); 92 93 // Retrieves the collection function that adds an entry. `set` for Maps and 94 // `add` for Sets. 95 TNode<Object> GetAddFunction(Variant variant, TNode<Context> context, 96 TNode<Object> collection); 97 98 // Retrieves the collection constructor function. 99 TNode<JSFunction> GetConstructor(Variant variant, 100 TNode<Context> native_context); 101 102 // Retrieves the initial collection function that adds an entry. Should only 103 // be called when it is certain that a collection prototype's map hasn't been 104 // changed. 105 TNode<JSFunction> GetInitialAddFunction(Variant variant, 106 TNode<Context> native_context); 107 108 // Checks whether {collection}'s initial add/set function has been modified 109 // (depending on {variant}, loaded from {native_context}). 110 void GotoIfInitialAddFunctionModified(Variant variant, 111 TNode<NativeContext> native_context, 112 TNode<HeapObject> collection, 113 Label* if_modified); 114 115 // Gets root index for the name of the add/set function. 116 RootIndex GetAddFunctionNameIndex(Variant variant); 117 118 // Retrieves the offset to access the backing table from the collection. 119 int GetTableOffset(Variant variant); 120 121 // Estimates the number of entries the collection will have after adding the 122 // entries passed in the constructor. AllocateTable() can use this to avoid 123 // the time of growing/rehashing when adding the constructor entries. 124 TNode<IntPtrT> EstimatedInitialSize(TNode<Object> initial_entries, 125 TNode<BoolT> is_fast_jsarray); 126 127 // Determines whether the collection's prototype has been modified. 128 TNode<BoolT> HasInitialCollectionPrototype(Variant variant, 129 TNode<Context> native_context, 130 TNode<Object> collection); 131 132 // Gets the initial prototype map for given collection {variant}. 133 TNode<Map> GetInitialCollectionPrototype(Variant variant, 134 TNode<Context> native_context); 135 136 // Loads an element from a fixed array. If the element is the hole, returns 137 // `undefined`. 138 TNode<Object> LoadAndNormalizeFixedArrayElement(TNode<FixedArray> elements, 139 TNode<IntPtrT> index); 140 141 // Loads an element from a fixed double array. If the element is the hole, 142 // returns `undefined`. 143 TNode<Object> LoadAndNormalizeFixedDoubleArrayElement( 144 TNode<HeapObject> elements, TNode<IntPtrT> index); 145 }; 146 147 class WeakCollectionsBuiltinsAssembler : public BaseCollectionsAssembler { 148 public: WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState * state)149 explicit WeakCollectionsBuiltinsAssembler(compiler::CodeAssemblerState* state) 150 : BaseCollectionsAssembler(state) {} 151 152 protected: 153 void AddEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index, 154 TNode<Object> key, TNode<Object> value, 155 TNode<IntPtrT> number_of_elements); 156 157 TNode<HeapObject> AllocateTable(Variant variant, 158 TNode<IntPtrT> at_least_space_for) override; 159 160 TNode<IntPtrT> GetHash(const TNode<HeapObject> key, Label* if_no_hash); 161 // Generates and sets the identity for a JSRececiver. 162 TNode<Smi> CreateIdentityHash(TNode<Object> receiver); 163 TNode<IntPtrT> EntryMask(TNode<IntPtrT> capacity); 164 165 // Builds code that finds the EphemeronHashTable entry for a {key} using the 166 // comparison code generated by {key_compare}. The key index is returned if 167 // the {key} is found. 168 using KeyComparator = 169 std::function<void(TNode<Object> entry_key, Label* if_same)>; 170 TNode<IntPtrT> FindKeyIndex(TNode<HeapObject> table, TNode<IntPtrT> key_hash, 171 TNode<IntPtrT> entry_mask, 172 const KeyComparator& key_compare); 173 174 // Builds code that finds an EphemeronHashTable entry available for a new 175 // entry. 176 TNode<IntPtrT> FindKeyIndexForInsertion(TNode<HeapObject> table, 177 TNode<IntPtrT> key_hash, 178 TNode<IntPtrT> entry_mask); 179 180 // Builds code that finds the EphemeronHashTable entry with key that matches 181 // {key} and returns the entry's key index. If {key} cannot be found, jumps to 182 // {if_not_found}. 183 TNode<IntPtrT> FindKeyIndexForKey(TNode<HeapObject> table, TNode<Object> key, 184 TNode<IntPtrT> hash, 185 TNode<IntPtrT> entry_mask, 186 Label* if_not_found); 187 188 TNode<Word32T> InsufficientCapacityToAdd(TNode<IntPtrT> capacity, 189 TNode<IntPtrT> number_of_elements, 190 TNode<IntPtrT> number_of_deleted); 191 TNode<IntPtrT> KeyIndexFromEntry(TNode<IntPtrT> entry); 192 193 TNode<IntPtrT> LoadNumberOfElements(TNode<EphemeronHashTable> table, 194 int offset); 195 TNode<IntPtrT> LoadNumberOfDeleted(TNode<EphemeronHashTable> table, 196 int offset = 0); 197 TNode<EphemeronHashTable> LoadTable(TNode<JSWeakCollection> collection); 198 TNode<IntPtrT> LoadTableCapacity(TNode<EphemeronHashTable> table); 199 200 void RemoveEntry(TNode<EphemeronHashTable> table, TNode<IntPtrT> key_index, 201 TNode<IntPtrT> number_of_elements); 202 TNode<BoolT> ShouldRehash(TNode<IntPtrT> number_of_elements, 203 TNode<IntPtrT> number_of_deleted); 204 TNode<Word32T> ShouldShrink(TNode<IntPtrT> capacity, 205 TNode<IntPtrT> number_of_elements); 206 TNode<IntPtrT> ValueIndexFromKeyIndex(TNode<IntPtrT> key_index); 207 }; 208 209 } // namespace internal 210 } // namespace v8 211 212 #endif // V8_BUILTINS_BUILTINS_COLLECTIONS_GEN_H_ 213