1 // Copyright 2012 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_OBJECTS_ELEMENTS_KIND_H_
6 #define V8_OBJECTS_ELEMENTS_KIND_H_
7
8 #include "src/base/bits.h"
9 #include "src/base/bounds.h"
10 #include "src/base/macros.h"
11 #include "src/common/checks.h"
12 #include "src/flags/flags.h"
13
14 namespace v8 {
15 namespace internal {
16
17 // V has parameters (Type, type, TYPE, C type)
18 #define TYPED_ARRAYS(V) \
19 V(Uint8, uint8, UINT8, uint8_t) \
20 V(Int8, int8, INT8, int8_t) \
21 V(Uint16, uint16, UINT16, uint16_t) \
22 V(Int16, int16, INT16, int16_t) \
23 V(Uint32, uint32, UINT32, uint32_t) \
24 V(Int32, int32, INT32, int32_t) \
25 V(Float32, float32, FLOAT32, float) \
26 V(Float64, float64, FLOAT64, double) \
27 V(Uint8Clamped, uint8_clamped, UINT8_CLAMPED, uint8_t) \
28 V(BigUint64, biguint64, BIGUINT64, uint64_t) \
29 V(BigInt64, bigint64, BIGINT64, int64_t)
30
31 enum ElementsKind : uint8_t {
32 // The "fast" kind for elements that only contain SMI values. Must be first
33 // to make it possible to efficiently check maps for this kind.
34 PACKED_SMI_ELEMENTS,
35 HOLEY_SMI_ELEMENTS,
36
37 // The "fast" kind for tagged values. Must be second to make it possible to
38 // efficiently check maps for this and the PACKED_SMI_ELEMENTS kind
39 // together at once.
40 PACKED_ELEMENTS,
41 HOLEY_ELEMENTS,
42
43 // The "fast" kind for unwrapped, non-tagged double values.
44 PACKED_DOUBLE_ELEMENTS,
45 HOLEY_DOUBLE_ELEMENTS,
46
47 // The nonextensible kind for elements.
48 PACKED_NONEXTENSIBLE_ELEMENTS,
49 HOLEY_NONEXTENSIBLE_ELEMENTS,
50
51 // The sealed kind for elements.
52 PACKED_SEALED_ELEMENTS,
53 HOLEY_SEALED_ELEMENTS,
54
55 // The frozen kind for elements.
56 PACKED_FROZEN_ELEMENTS,
57 HOLEY_FROZEN_ELEMENTS,
58
59 // The "slow" kind.
60 DICTIONARY_ELEMENTS,
61
62 // Elements kind of the "arguments" object (only in sloppy mode).
63 FAST_SLOPPY_ARGUMENTS_ELEMENTS,
64 SLOW_SLOPPY_ARGUMENTS_ELEMENTS,
65
66 // For string wrapper objects ("new String('...')"), the string's characters
67 // are overlaid onto a regular elements backing store.
68 FAST_STRING_WRAPPER_ELEMENTS,
69 SLOW_STRING_WRAPPER_ELEMENTS,
70
71 // Fixed typed arrays.
72 #define TYPED_ARRAY_ELEMENTS_KIND(Type, type, TYPE, ctype) TYPE##_ELEMENTS,
73 TYPED_ARRAYS(TYPED_ARRAY_ELEMENTS_KIND)
74 #undef TYPED_ARRAY_ELEMENTS_KIND
75
76 // Sentinel ElementsKind for objects with no elements.
77 NO_ELEMENTS,
78
79 // Derived constants from ElementsKind.
80 FIRST_ELEMENTS_KIND = PACKED_SMI_ELEMENTS,
81 LAST_ELEMENTS_KIND = BIGINT64_ELEMENTS,
82 FIRST_FAST_ELEMENTS_KIND = PACKED_SMI_ELEMENTS,
83 LAST_FAST_ELEMENTS_KIND = HOLEY_DOUBLE_ELEMENTS,
84 FIRST_FIXED_TYPED_ARRAY_ELEMENTS_KIND = UINT8_ELEMENTS,
85 LAST_FIXED_TYPED_ARRAY_ELEMENTS_KIND = BIGINT64_ELEMENTS,
86 TERMINAL_FAST_ELEMENTS_KIND = HOLEY_ELEMENTS,
87 FIRST_ANY_NONEXTENSIBLE_ELEMENTS_KIND = PACKED_NONEXTENSIBLE_ELEMENTS,
88 LAST_ANY_NONEXTENSIBLE_ELEMENTS_KIND = HOLEY_FROZEN_ELEMENTS,
89
90 // Alias for kSystemPointerSize-sized elements
91 #ifdef V8_COMPRESS_POINTERS
92 SYSTEM_POINTER_ELEMENTS = PACKED_DOUBLE_ELEMENTS,
93 #else
94 SYSTEM_POINTER_ELEMENTS = PACKED_ELEMENTS,
95 #endif
96 };
97
98 constexpr int kElementsKindCount = LAST_ELEMENTS_KIND - FIRST_ELEMENTS_KIND + 1;
99 constexpr int kFastElementsKindCount =
100 LAST_FAST_ELEMENTS_KIND - FIRST_FAST_ELEMENTS_KIND + 1;
101
102 // The number to add to a packed elements kind to reach a holey elements kind
103 constexpr int kFastElementsKindPackedToHoley =
104 HOLEY_SMI_ELEMENTS - PACKED_SMI_ELEMENTS;
105
106 constexpr int kElementsKindBits = 5;
107 STATIC_ASSERT((1 << kElementsKindBits) > LAST_ELEMENTS_KIND);
108 STATIC_ASSERT((1 << (kElementsKindBits - 1)) <= LAST_ELEMENTS_KIND);
109
110 constexpr int kFastElementsKindBits = 3;
111 STATIC_ASSERT((1 << kFastElementsKindBits) > LAST_FAST_ELEMENTS_KIND);
112 STATIC_ASSERT((1 << (kFastElementsKindBits - 1)) <= LAST_FAST_ELEMENTS_KIND);
113
114 V8_EXPORT_PRIVATE int ElementsKindToShiftSize(ElementsKind elements_kind);
115 V8_EXPORT_PRIVATE int ElementsKindToByteSize(ElementsKind elements_kind);
116 int GetDefaultHeaderSizeForElementsKind(ElementsKind elements_kind);
117 const char* ElementsKindToString(ElementsKind kind);
118
GetInitialFastElementsKind()119 inline ElementsKind GetInitialFastElementsKind() { return PACKED_SMI_ELEMENTS; }
120
121 ElementsKind GetFastElementsKindFromSequenceIndex(int sequence_number);
122 int GetSequenceIndexFromFastElementsKind(ElementsKind elements_kind);
123
124 ElementsKind GetNextTransitionElementsKind(ElementsKind elements_kind);
125
IsDictionaryElementsKind(ElementsKind kind)126 inline bool IsDictionaryElementsKind(ElementsKind kind) {
127 return kind == DICTIONARY_ELEMENTS;
128 }
129
IsFastArgumentsElementsKind(ElementsKind kind)130 inline bool IsFastArgumentsElementsKind(ElementsKind kind) {
131 return kind == FAST_SLOPPY_ARGUMENTS_ELEMENTS;
132 }
133
IsSlowArgumentsElementsKind(ElementsKind kind)134 inline bool IsSlowArgumentsElementsKind(ElementsKind kind) {
135 return kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS;
136 }
137
IsSloppyArgumentsElementsKind(ElementsKind kind)138 inline bool IsSloppyArgumentsElementsKind(ElementsKind kind) {
139 return base::IsInRange(kind, FAST_SLOPPY_ARGUMENTS_ELEMENTS,
140 SLOW_SLOPPY_ARGUMENTS_ELEMENTS);
141 }
142
IsStringWrapperElementsKind(ElementsKind kind)143 inline bool IsStringWrapperElementsKind(ElementsKind kind) {
144 return base::IsInRange(kind, FAST_STRING_WRAPPER_ELEMENTS,
145 SLOW_STRING_WRAPPER_ELEMENTS);
146 }
147
IsTypedArrayElementsKind(ElementsKind kind)148 inline bool IsTypedArrayElementsKind(ElementsKind kind) {
149 return base::IsInRange(kind, FIRST_FIXED_TYPED_ARRAY_ELEMENTS_KIND,
150 LAST_FIXED_TYPED_ARRAY_ELEMENTS_KIND);
151 }
152
IsTerminalElementsKind(ElementsKind kind)153 inline bool IsTerminalElementsKind(ElementsKind kind) {
154 return kind == TERMINAL_FAST_ELEMENTS_KIND || IsTypedArrayElementsKind(kind);
155 }
156
IsFastElementsKind(ElementsKind kind)157 inline bool IsFastElementsKind(ElementsKind kind) {
158 STATIC_ASSERT(FIRST_FAST_ELEMENTS_KIND == 0);
159 return kind <= LAST_FAST_ELEMENTS_KIND;
160 }
161
IsTransitionElementsKind(ElementsKind kind)162 inline bool IsTransitionElementsKind(ElementsKind kind) {
163 return IsFastElementsKind(kind) || IsTypedArrayElementsKind(kind) ||
164 kind == FAST_SLOPPY_ARGUMENTS_ELEMENTS ||
165 kind == FAST_STRING_WRAPPER_ELEMENTS;
166 }
167
IsDoubleElementsKind(ElementsKind kind)168 inline bool IsDoubleElementsKind(ElementsKind kind) {
169 return base::IsInRange(kind, PACKED_DOUBLE_ELEMENTS, HOLEY_DOUBLE_ELEMENTS);
170 }
171
IsFixedFloatElementsKind(ElementsKind kind)172 inline bool IsFixedFloatElementsKind(ElementsKind kind) {
173 return kind == FLOAT32_ELEMENTS || kind == FLOAT64_ELEMENTS;
174 }
175
IsDoubleOrFloatElementsKind(ElementsKind kind)176 inline bool IsDoubleOrFloatElementsKind(ElementsKind kind) {
177 return IsDoubleElementsKind(kind) || IsFixedFloatElementsKind(kind);
178 }
179
180 // This predicate is used for disabling respective functionality in builtins.
IsAnyNonextensibleElementsKindUnchecked(ElementsKind kind)181 inline bool IsAnyNonextensibleElementsKindUnchecked(ElementsKind kind) {
182 return base::IsInRange(kind, FIRST_ANY_NONEXTENSIBLE_ELEMENTS_KIND,
183 LAST_ANY_NONEXTENSIBLE_ELEMENTS_KIND);
184 }
185
IsAnyNonextensibleElementsKind(ElementsKind kind)186 inline bool IsAnyNonextensibleElementsKind(ElementsKind kind) {
187 DCHECK_IMPLIES(IsAnyNonextensibleElementsKindUnchecked(kind),
188 FLAG_enable_sealed_frozen_elements_kind);
189 return IsAnyNonextensibleElementsKindUnchecked(kind);
190 }
191
IsNonextensibleElementsKind(ElementsKind kind)192 inline bool IsNonextensibleElementsKind(ElementsKind kind) {
193 DCHECK_IMPLIES(base::IsInRange(kind, PACKED_NONEXTENSIBLE_ELEMENTS,
194 HOLEY_NONEXTENSIBLE_ELEMENTS),
195 FLAG_enable_sealed_frozen_elements_kind);
196 return base::IsInRange(kind, PACKED_NONEXTENSIBLE_ELEMENTS,
197 HOLEY_NONEXTENSIBLE_ELEMENTS);
198 }
199
IsSealedElementsKind(ElementsKind kind)200 inline bool IsSealedElementsKind(ElementsKind kind) {
201 DCHECK_IMPLIES(
202 base::IsInRange(kind, PACKED_SEALED_ELEMENTS, HOLEY_SEALED_ELEMENTS),
203 FLAG_enable_sealed_frozen_elements_kind);
204 return base::IsInRange(kind, PACKED_SEALED_ELEMENTS, HOLEY_SEALED_ELEMENTS);
205 }
206
IsFrozenElementsKind(ElementsKind kind)207 inline bool IsFrozenElementsKind(ElementsKind kind) {
208 DCHECK_IMPLIES(
209 base::IsInRange(kind, PACKED_FROZEN_ELEMENTS, HOLEY_FROZEN_ELEMENTS),
210 FLAG_enable_sealed_frozen_elements_kind);
211 return base::IsInRange(kind, PACKED_FROZEN_ELEMENTS, HOLEY_FROZEN_ELEMENTS);
212 }
213
IsSmiOrObjectElementsKind(ElementsKind kind)214 inline bool IsSmiOrObjectElementsKind(ElementsKind kind) {
215 return base::IsInRange(kind, PACKED_SMI_ELEMENTS, HOLEY_ELEMENTS);
216 }
217
IsSmiElementsKind(ElementsKind kind)218 inline bool IsSmiElementsKind(ElementsKind kind) {
219 return base::IsInRange(kind, PACKED_SMI_ELEMENTS, HOLEY_SMI_ELEMENTS);
220 }
221
IsFastNumberElementsKind(ElementsKind kind)222 inline bool IsFastNumberElementsKind(ElementsKind kind) {
223 return IsSmiElementsKind(kind) || IsDoubleElementsKind(kind);
224 }
225
IsObjectElementsKind(ElementsKind kind)226 inline bool IsObjectElementsKind(ElementsKind kind) {
227 return base::IsInRange(kind, PACKED_ELEMENTS, HOLEY_ELEMENTS);
228 }
229
IsAnyHoleyNonextensibleElementsKind(ElementsKind kind)230 inline bool IsAnyHoleyNonextensibleElementsKind(ElementsKind kind) {
231 DCHECK_IMPLIES(kind == HOLEY_NONEXTENSIBLE_ELEMENTS ||
232 kind == HOLEY_SEALED_ELEMENTS ||
233 kind == HOLEY_FROZEN_ELEMENTS,
234 FLAG_enable_sealed_frozen_elements_kind);
235 return kind == HOLEY_NONEXTENSIBLE_ELEMENTS ||
236 kind == HOLEY_SEALED_ELEMENTS || kind == HOLEY_FROZEN_ELEMENTS;
237 }
238
IsHoleyElementsKind(ElementsKind kind)239 inline bool IsHoleyElementsKind(ElementsKind kind) {
240 return kind % 2 == 1 && kind <= HOLEY_DOUBLE_ELEMENTS;
241 }
242
IsHoleyElementsKindForRead(ElementsKind kind)243 inline bool IsHoleyElementsKindForRead(ElementsKind kind) {
244 return kind % 2 == 1 && kind <= HOLEY_FROZEN_ELEMENTS;
245 }
246
IsHoleyOrDictionaryElementsKind(ElementsKind kind)247 inline bool IsHoleyOrDictionaryElementsKind(ElementsKind kind) {
248 return IsHoleyElementsKindForRead(kind) || kind == DICTIONARY_ELEMENTS;
249 }
250
IsFastPackedElementsKind(ElementsKind kind)251 inline bool IsFastPackedElementsKind(ElementsKind kind) {
252 return kind % 2 == 0 && kind <= PACKED_DOUBLE_ELEMENTS;
253 }
254
GetPackedElementsKind(ElementsKind holey_kind)255 inline ElementsKind GetPackedElementsKind(ElementsKind holey_kind) {
256 if (holey_kind == HOLEY_SMI_ELEMENTS) {
257 return PACKED_SMI_ELEMENTS;
258 }
259 if (holey_kind == HOLEY_DOUBLE_ELEMENTS) {
260 return PACKED_DOUBLE_ELEMENTS;
261 }
262 if (holey_kind == HOLEY_ELEMENTS) {
263 return PACKED_ELEMENTS;
264 }
265 return holey_kind;
266 }
267
GetHoleyElementsKind(ElementsKind packed_kind)268 inline ElementsKind GetHoleyElementsKind(ElementsKind packed_kind) {
269 if (packed_kind == PACKED_SMI_ELEMENTS) {
270 return HOLEY_SMI_ELEMENTS;
271 }
272 if (packed_kind == PACKED_DOUBLE_ELEMENTS) {
273 return HOLEY_DOUBLE_ELEMENTS;
274 }
275 if (packed_kind == PACKED_ELEMENTS) {
276 return HOLEY_ELEMENTS;
277 }
278 if (packed_kind == PACKED_NONEXTENSIBLE_ELEMENTS) {
279 return HOLEY_NONEXTENSIBLE_ELEMENTS;
280 }
281 return packed_kind;
282 }
283
UnionElementsKindUptoPackedness(ElementsKind * a_out,ElementsKind b)284 inline bool UnionElementsKindUptoPackedness(ElementsKind* a_out,
285 ElementsKind b) {
286 // Assert that the union of two ElementKinds can be computed via std::max.
287 static_assert(PACKED_SMI_ELEMENTS < HOLEY_SMI_ELEMENTS,
288 "ElementsKind union not computable via std::max.");
289 static_assert(PACKED_ELEMENTS < HOLEY_ELEMENTS,
290 "ElementsKind union not computable via std::max.");
291 static_assert(PACKED_DOUBLE_ELEMENTS < HOLEY_DOUBLE_ELEMENTS,
292 "ElementsKind union not computable via std::max.");
293 ElementsKind a = *a_out;
294 switch (a) {
295 case HOLEY_SMI_ELEMENTS:
296 case PACKED_SMI_ELEMENTS:
297 if (b == PACKED_SMI_ELEMENTS || b == HOLEY_SMI_ELEMENTS) {
298 *a_out = std::max(a, b);
299 return true;
300 }
301 break;
302 case PACKED_ELEMENTS:
303 case HOLEY_ELEMENTS:
304 if (b == PACKED_ELEMENTS || b == HOLEY_ELEMENTS) {
305 *a_out = std::max(a, b);
306 return true;
307 }
308 break;
309 case PACKED_DOUBLE_ELEMENTS:
310 case HOLEY_DOUBLE_ELEMENTS:
311 if (b == PACKED_DOUBLE_ELEMENTS || b == HOLEY_DOUBLE_ELEMENTS) {
312 *a_out = std::max(a, b);
313 return true;
314 }
315 break;
316 default:
317 break;
318 }
319 return false;
320 }
321
322 bool UnionElementsKindUptoSize(ElementsKind* a_out, ElementsKind b);
323
FastSmiToObjectElementsKind(ElementsKind from_kind)324 inline ElementsKind FastSmiToObjectElementsKind(ElementsKind from_kind) {
325 DCHECK(IsSmiElementsKind(from_kind));
326 return (from_kind == PACKED_SMI_ELEMENTS) ? PACKED_ELEMENTS : HOLEY_ELEMENTS;
327 }
328
IsSimpleMapChangeTransition(ElementsKind from_kind,ElementsKind to_kind)329 inline bool IsSimpleMapChangeTransition(ElementsKind from_kind,
330 ElementsKind to_kind) {
331 return (GetHoleyElementsKind(from_kind) == to_kind) ||
332 (IsSmiElementsKind(from_kind) && IsObjectElementsKind(to_kind));
333 }
334
335 bool IsMoreGeneralElementsKindTransition(ElementsKind from_kind,
336 ElementsKind to_kind);
337
GetMoreGeneralElementsKind(ElementsKind from_kind,ElementsKind to_kind)338 inline ElementsKind GetMoreGeneralElementsKind(ElementsKind from_kind,
339 ElementsKind to_kind) {
340 if (IsMoreGeneralElementsKindTransition(from_kind, to_kind)) {
341 return to_kind;
342 }
343 return from_kind;
344 }
345
IsTransitionableFastElementsKind(ElementsKind from_kind)346 inline bool IsTransitionableFastElementsKind(ElementsKind from_kind) {
347 return IsFastElementsKind(from_kind) &&
348 from_kind != TERMINAL_FAST_ELEMENTS_KIND;
349 }
350
ElementsKindEqual(ElementsKind a,ElementsKind b)351 inline bool ElementsKindEqual(ElementsKind a, ElementsKind b) { return a == b; }
352
353 enum class CompactElementsKind : uint8_t {
354 PACKED_SMI_ELEMENTS = PACKED_SMI_ELEMENTS,
355 HOLEY_SMI_ELEMENTS = HOLEY_SMI_ELEMENTS,
356
357 PACKED_ELEMENTS = PACKED_ELEMENTS,
358 HOLEY_ELEMENTS = HOLEY_ELEMENTS,
359
360 PACKED_DOUBLE_ELEMENTS = PACKED_DOUBLE_ELEMENTS,
361 HOLEY_DOUBLE_ELEMENTS = HOLEY_DOUBLE_ELEMENTS,
362
363 NON_COMPACT_ELEMENTS_KIND
364 };
365
ToCompactElementsKind(ElementsKind kind)366 inline CompactElementsKind ToCompactElementsKind(ElementsKind kind) {
367 if (base::IsInRange(kind, PACKED_SMI_ELEMENTS, HOLEY_DOUBLE_ELEMENTS)) {
368 return static_cast<CompactElementsKind>(kind);
369 }
370
371 return CompactElementsKind::NON_COMPACT_ELEMENTS_KIND;
372 }
373
374 const char* CompactElementsKindToString(CompactElementsKind kind);
375
376 } // namespace internal
377 } // namespace v8
378
379 #endif // V8_OBJECTS_ELEMENTS_KIND_H_
380