1/*
2 * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#if ENABLE(DFG_JIT)
29
30#include "ArrayProfile.h"
31#include "SpeculatedType.h"
32
33namespace JSC {
34
35class CodeOrigin;
36
37namespace DFG {
38
39class Graph;
40struct AbstractValue;
41struct Node;
42
43// Use a namespace + enum instead of enum alone to avoid the namespace collision
44// that would otherwise occur, since we say things like "Int8Array" and "JSArray"
45// in lots of other places, to mean subtly different things.
46namespace Array {
47enum Action : uint8_t {
48 Read,
49 Write
50};
51
52enum Type : uint8_t {
53 SelectUsingPredictions, // Implies that we need predictions to decide. We will never get to the backend in this mode.
54 SelectUsingArguments, // Implies that we use the Node's arguments to decide. We will never get to the backend in this mode.
55 Unprofiled, // Implies that array profiling didn't see anything. But that could be because the operands didn't comply with basic type assumptions (base is cell, property is int). This either becomes Generic or ForceExit depending on value profiling.
56 ForceExit, // Implies that we have no idea how to execute this operation, so we should just give up.
57 Generic,
58 String,
59
60 Undecided,
61 Int32,
62 Double,
63 Contiguous,
64 ArrayStorage,
65 SlowPutArrayStorage,
66
67 DirectArguments,
68 ScopedArguments,
69
70 Int8Array,
71 Int16Array,
72 Int32Array,
73 Uint8Array,
74 Uint8ClampedArray,
75 Uint16Array,
76 Uint32Array,
77 Float32Array,
78 Float64Array,
79 AnyTypedArray
80};
81
82enum Class : uint8_t {
83 NonArray, // Definitely some object that is not a JSArray.
84 OriginalNonArray, // Definitely some object that is not a JSArray, but that object has the original structure.
85 Array, // Definitely a JSArray, and may or may not have custom properties or have undergone some other bizarre transitions.
86 OriginalArray, // Definitely a JSArray, and still has one of the primordial JSArray structures for the global object that this code block (possibly inlined code block) belongs to.
87 OriginalCopyOnWriteArray, // Definitely a copy on write JSArray, and still has one of the primordial JSArray copy on write structures for the global object that this code block (possibly inlined code block) belongs to.
88 PossiblyArray // Some object that may or may not be a JSArray.
89};
90
91enum Speculation : uint8_t {
92 SaneChain, // In bounds and the array prototype chain is still intact, i.e. loading a hole doesn't require special treatment.
93
94 InBounds, // In bounds and not loading a hole.
95 ToHole, // Potentially storing to a hole.
96 OutOfBounds // Out-of-bounds access and anything can happen.
97};
98enum Conversion : uint8_t {
99 AsIs,
100 Convert
101};
102} // namespace Array
103
104const char* arrayActionToString(Array::Action);
105const char* arrayTypeToString(Array::Type);
106const char* arrayClassToString(Array::Class);
107const char* arraySpeculationToString(Array::Speculation);
108const char* arrayConversionToString(Array::Conversion);
109
110IndexingType toIndexingShape(Array::Type);
111
112TypedArrayType toTypedArrayType(Array::Type);
113Array::Type toArrayType(TypedArrayType);
114Array::Type refineTypedArrayType(Array::Type, TypedArrayType);
115
116bool permitsBoundsCheckLowering(Array::Type);
117
118class ArrayMode {
119public:
120 ArrayMode()
121 {
122 u.asBytes.type = Array::SelectUsingPredictions;
123 u.asBytes.arrayClass = Array::NonArray;
124 u.asBytes.speculation = Array::InBounds;
125 u.asBytes.conversion = Array::AsIs;
126 u.asBytes.action = Array::Write;
127 }
128
129 explicit ArrayMode(Array::Type type, Array::Action action)
130 {
131 u.asBytes.type = type;
132 u.asBytes.arrayClass = Array::NonArray;
133 u.asBytes.speculation = Array::InBounds;
134 u.asBytes.conversion = Array::AsIs;
135 u.asBytes.action = action;
136 }
137
138 ArrayMode(Array::Type type, Array::Class arrayClass, Array::Action action)
139 {
140 u.asBytes.type = type;
141 u.asBytes.arrayClass = arrayClass;
142 u.asBytes.speculation = Array::InBounds;
143 u.asBytes.conversion = Array::AsIs;
144 u.asBytes.action = action;
145 }
146
147 ArrayMode(Array::Type type, Array::Class arrayClass, Array::Speculation speculation, Array::Conversion conversion, Array::Action action)
148 {
149 u.asBytes.type = type;
150 u.asBytes.arrayClass = arrayClass;
151 u.asBytes.speculation = speculation;
152 u.asBytes.conversion = conversion;
153 u.asBytes.action = action;
154 }
155
156 ArrayMode(Array::Type type, Array::Class arrayClass, Array::Conversion conversion, Array::Action action)
157 {
158 u.asBytes.type = type;
159 u.asBytes.arrayClass = arrayClass;
160 u.asBytes.speculation = Array::InBounds;
161 u.asBytes.conversion = conversion;
162 u.asBytes.action = action;
163 }
164
165 Array::Type type() const { return static_cast<Array::Type>(u.asBytes.type); }
166 Array::Class arrayClass() const { return static_cast<Array::Class>(u.asBytes.arrayClass); }
167 Array::Speculation speculation() const { return static_cast<Array::Speculation>(u.asBytes.speculation); }
168 Array::Conversion conversion() const { return static_cast<Array::Conversion>(u.asBytes.conversion); }
169 Array::Action action() const { return static_cast<Array::Action>(u.asBytes.action); }
170
171 unsigned asWord() const { return u.asWord; }
172
173 static ArrayMode fromWord(unsigned word)
174 {
175 return ArrayMode(word);
176 }
177
178 static ArrayMode fromObserved(const ConcurrentJSLocker&, ArrayProfile*, Array::Action, bool makeSafe);
179
180 ArrayMode withSpeculation(Array::Speculation speculation) const
181 {
182 return ArrayMode(type(), arrayClass(), speculation, conversion(), action());
183 }
184
185 ArrayMode withArrayClass(Array::Class arrayClass) const
186 {
187 return ArrayMode(type(), arrayClass, speculation(), conversion(), action());
188 }
189
190 ArrayMode withSpeculationFromProfile(const ConcurrentJSLocker& locker, ArrayProfile* profile, bool makeSafe) const
191 {
192 Array::Speculation mySpeculation;
193
194 if (makeSafe)
195 mySpeculation = Array::OutOfBounds;
196 else if (profile->mayStoreToHole(locker))
197 mySpeculation = Array::ToHole;
198 else
199 mySpeculation = Array::InBounds;
200
201 return withSpeculation(mySpeculation);
202 }
203
204 ArrayMode withProfile(const ConcurrentJSLocker& locker, ArrayProfile* profile, bool makeSafe) const
205 {
206 Array::Class myArrayClass;
207
208 if (isJSArray()) {
209 if (profile->usesOriginalArrayStructures(locker) && benefitsFromOriginalArray()) {
210 ArrayModes arrayModes = profile->observedArrayModes(locker);
211 if (hasSeenCopyOnWriteArray(arrayModes) && !hasSeenWritableArray(arrayModes))
212 myArrayClass = Array::OriginalCopyOnWriteArray;
213 else if (!hasSeenCopyOnWriteArray(arrayModes) && hasSeenWritableArray(arrayModes))
214 myArrayClass = Array::OriginalArray;
215 else
216 myArrayClass = Array::Array;
217 } else
218 myArrayClass = Array::Array;
219 } else
220 myArrayClass = arrayClass();
221
222 return withArrayClass(myArrayClass).withSpeculationFromProfile(locker, profile, makeSafe);
223 }
224
225 ArrayMode withType(Array::Type type) const
226 {
227 return ArrayMode(type, arrayClass(), speculation(), conversion(), action());
228 }
229
230 ArrayMode withConversion(Array::Conversion conversion) const
231 {
232 return ArrayMode(type(), arrayClass(), speculation(), conversion, action());
233 }
234
235 ArrayMode withTypeAndConversion(Array::Type type, Array::Conversion conversion) const
236 {
237 return ArrayMode(type, arrayClass(), speculation(), conversion, action());
238 }
239
240 ArrayMode refine(Graph&, Node*, SpeculatedType base, SpeculatedType index, SpeculatedType value = SpecNone) const;
241
242 bool alreadyChecked(Graph&, Node*, const AbstractValue&) const;
243
244 void dump(PrintStream&) const;
245
246 bool usesButterfly() const
247 {
248 switch (type()) {
249 case Array::Undecided:
250 case Array::Int32:
251 case Array::Double:
252 case Array::Contiguous:
253 case Array::ArrayStorage:
254 case Array::SlowPutArrayStorage:
255 return true;
256 default:
257 return false;
258 }
259 }
260
261 bool isJSArray() const
262 {
263 switch (arrayClass()) {
264 case Array::Array:
265 case Array::OriginalArray:
266 case Array::OriginalCopyOnWriteArray:
267 return true;
268 default:
269 return false;
270 }
271 }
272
273 bool isJSArrayWithOriginalStructure() const
274 {
275 return arrayClass() == Array::OriginalArray || arrayClass() == Array::OriginalCopyOnWriteArray;
276 }
277
278 bool isSaneChain() const
279 {
280 return speculation() == Array::SaneChain;
281 }
282
283 bool isInBounds() const
284 {
285 switch (speculation()) {
286 case Array::SaneChain:
287 case Array::InBounds:
288 return true;
289 default:
290 return false;
291 }
292 }
293
294 bool mayStoreToHole() const
295 {
296 return !isInBounds();
297 }
298
299 bool isOutOfBounds() const
300 {
301 return speculation() == Array::OutOfBounds;
302 }
303
304 bool isSlowPut() const
305 {
306 return type() == Array::SlowPutArrayStorage;
307 }
308
309 bool canCSEStorage() const
310 {
311 switch (type()) {
312 case Array::SelectUsingPredictions:
313 case Array::SelectUsingArguments:
314 case Array::Unprofiled:
315 case Array::Undecided:
316 case Array::ForceExit:
317 case Array::Generic:
318 case Array::DirectArguments:
319 case Array::ScopedArguments:
320 return false;
321 default:
322 return true;
323 }
324 }
325
326 bool lengthNeedsStorage() const
327 {
328 switch (type()) {
329 case Array::Undecided:
330 case Array::Int32:
331 case Array::Double:
332 case Array::Contiguous:
333 case Array::ArrayStorage:
334 case Array::SlowPutArrayStorage:
335 return true;
336 default:
337 return false;
338 }
339 }
340
341 ArrayMode modeForPut() const
342 {
343 switch (type()) {
344 case Array::String:
345 case Array::DirectArguments:
346 case Array::ScopedArguments:
347 return ArrayMode(Array::Generic);
348 default:
349 return *this;
350 }
351 }
352
353 bool isSpecific() const
354 {
355 switch (type()) {
356 case Array::SelectUsingPredictions:
357 case Array::SelectUsingArguments:
358 case Array::Unprofiled:
359 case Array::ForceExit:
360 case Array::Generic:
361 return false;
362 default:
363 return true;
364 }
365 }
366
367 bool supportsSelfLength() const
368 {
369 switch (type()) {
370 case Array::SelectUsingPredictions:
371 case Array::Unprofiled:
372 case Array::ForceExit:
373 case Array::Generic:
374 // TypedArrays do not have a self length property as of ES6.
375 case Array::Int8Array:
376 case Array::Int16Array:
377 case Array::Int32Array:
378 case Array::Uint8Array:
379 case Array::Uint8ClampedArray:
380 case Array::Uint16Array:
381 case Array::Uint32Array:
382 case Array::Float32Array:
383 case Array::Float64Array:
384 return false;
385 case Array::Int32:
386 case Array::Double:
387 case Array::Contiguous:
388 case Array::ArrayStorage:
389 case Array::SlowPutArrayStorage:
390 return isJSArray();
391 default:
392 return true;
393 }
394 }
395
396 bool permitsBoundsCheckLowering() const;
397
398 bool benefitsFromOriginalArray() const
399 {
400 switch (type()) {
401 case Array::Int32:
402 case Array::Double:
403 case Array::Contiguous:
404 case Array::Undecided:
405 case Array::ArrayStorage:
406 return true;
407 default:
408 return false;
409 }
410 }
411
412 // Returns 0 if this is not OriginalArray.
413 Structure* originalArrayStructure(Graph&, const CodeOrigin&) const;
414 Structure* originalArrayStructure(Graph&, Node*) const;
415
416 bool doesConversion() const
417 {
418 return conversion() != Array::AsIs;
419 }
420
421 bool structureWouldPassArrayModeFiltering(Structure* structure)
422 {
423 return arrayModesAlreadyChecked(arrayModesFromStructure(structure), arrayModesThatPassFiltering());
424 }
425
426 ArrayModes arrayModesThatPassFiltering() const
427 {
428 ArrayModes result;
429 switch (type()) {
430 case Array::Generic:
431 return ALL_ARRAY_MODES;
432 case Array::Int32:
433 result = arrayModesWithIndexingShapes(Int32Shape);
434 break;
435 case Array::Double:
436 result = arrayModesWithIndexingShapes(DoubleShape);
437 break;
438 case Array::Contiguous:
439 result = arrayModesWithIndexingShapes(ContiguousShape);
440 break;
441 case Array::ArrayStorage:
442 return arrayModesWithIndexingShapes(ArrayStorageShape);
443 case Array::SlowPutArrayStorage:
444 return arrayModesWithIndexingShapes(SlowPutArrayStorageShape, ArrayStorageShape);
445 case Array::DirectArguments:
446 case Array::ScopedArguments:
447 return arrayModesWithIndexingShapes(ArrayStorageShape, SlowPutArrayStorageShape, NonArray);
448 case Array::Int8Array:
449 return Int8ArrayMode;
450 case Array::Int16Array:
451 return Int16ArrayMode;
452 case Array::Int32Array:
453 return Int32ArrayMode;
454 case Array::Uint8Array:
455 return Uint8ArrayMode;
456 case Array::Uint8ClampedArray:
457 return Uint8ClampedArrayMode;
458 case Array::Uint16Array:
459 return Uint16ArrayMode;
460 case Array::Uint32Array:
461 return Uint32ArrayMode;
462 case Array::Float32Array:
463 return Float32ArrayMode;
464 case Array::Float64Array:
465 return Float64ArrayMode;
466 case Array::AnyTypedArray:
467 return ALL_TYPED_ARRAY_MODES;
468 default:
469 return asArrayModesIgnoringTypedArrays(NonArray);
470 }
471
472 if (action() == Array::Write)
473 result &= ~ALL_COPY_ON_WRITE_ARRAY_MODES;
474 return result;
475 }
476
477 bool getIndexedPropertyStorageMayTriggerGC() const
478 {
479 return type() == Array::String;
480 }
481
482 IndexingType shapeMask() const
483 {
484 return toIndexingShape(type());
485 }
486
487 TypedArrayType typedArrayType() const
488 {
489 return toTypedArrayType(type());
490 }
491
492 bool isSomeTypedArrayView() const
493 {
494 return type() == Array::AnyTypedArray || isTypedView(typedArrayType());
495 }
496
497 bool operator==(const ArrayMode& other) const
498 {
499 return type() == other.type()
500 && arrayClass() == other.arrayClass()
501 && speculation() == other.speculation()
502 && conversion() == other.conversion();
503 }
504
505 bool operator!=(const ArrayMode& other) const
506 {
507 return !(*this == other);
508 }
509private:
510 explicit ArrayMode(unsigned word)
511 {
512 u.asWord = word;
513 }
514
515 ArrayModes arrayModesWithIndexingShapes(IndexingType shape) const
516 {
517 switch (arrayClass()) {
518 case Array::NonArray:
519 case Array::OriginalNonArray:
520 return asArrayModesIgnoringTypedArrays(shape);
521 case Array::OriginalCopyOnWriteArray:
522 ASSERT(hasInt32(shape) || hasDouble(shape) || hasContiguous(shape));
523 return asArrayModesIgnoringTypedArrays(shape | IsArray) | asArrayModesIgnoringTypedArrays(shape | IsArray | CopyOnWrite);
524 case Array::Array:
525 if (hasInt32(shape) || hasDouble(shape) || hasContiguous(shape))
526 return asArrayModesIgnoringTypedArrays(shape | IsArray) | asArrayModesIgnoringTypedArrays(shape | IsArray | CopyOnWrite);
527 FALLTHROUGH;
528 case Array::OriginalArray:
529 return asArrayModesIgnoringTypedArrays(shape | IsArray);
530 case Array::PossiblyArray:
531 if (hasInt32(shape) || hasDouble(shape) || hasContiguous(shape))
532 return asArrayModesIgnoringTypedArrays(shape) | asArrayModesIgnoringTypedArrays(shape | IsArray) | asArrayModesIgnoringTypedArrays(shape | IsArray | CopyOnWrite);
533 return asArrayModesIgnoringTypedArrays(shape) | asArrayModesIgnoringTypedArrays(shape | IsArray);
534 default:
535 // This is only necessary for C++ compilers that don't understand enums.
536 return 0;
537 }
538 }
539
540 template <typename... Args>
541 ArrayModes arrayModesWithIndexingShapes(IndexingType shape1, Args... args) const
542 {
543 ArrayModes arrayMode1 = arrayModesWithIndexingShapes(shape1);
544 ArrayModes arrayMode2 = arrayModesWithIndexingShapes(args...);
545 return arrayMode1 | arrayMode2;
546 }
547
548 bool alreadyChecked(Graph&, Node*, const AbstractValue&, IndexingType shape) const;
549
550 union {
551 struct {
552 uint8_t type;
553 uint8_t arrayClass;
554 uint8_t speculation;
555 uint8_t conversion : 4;
556 uint8_t action : 4;
557 } asBytes;
558 unsigned asWord;
559 } u;
560 static_assert(sizeof(decltype(u.asBytes)) == sizeof(decltype(u.asWord)), "the word form of ArrayMode should have the same size as the individual slices");
561};
562
563static inline bool canCSEStorage(const ArrayMode& arrayMode)
564{
565 return arrayMode.canCSEStorage();
566}
567
568static inline bool lengthNeedsStorage(const ArrayMode& arrayMode)
569{
570 return arrayMode.lengthNeedsStorage();
571}
572
573static inline bool neverNeedsStorage(const ArrayMode&)
574{
575 return false;
576}
577
578} } // namespace JSC::DFG
579
580namespace WTF {
581
582class PrintStream;
583void printInternal(PrintStream&, JSC::DFG::Array::Action);
584void printInternal(PrintStream&, JSC::DFG::Array::Type);
585void printInternal(PrintStream&, JSC::DFG::Array::Class);
586void printInternal(PrintStream&, JSC::DFG::Array::Speculation);
587void printInternal(PrintStream&, JSC::DFG::Array::Conversion);
588
589} // namespace WTF
590
591#endif // ENABLE(DFG_JIT)
592