• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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