0ac2eccb6f8cb8c7c28313b3393c9b6857765d74
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGArrayMode.h
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
33 namespace JSC {
34
35 struct CodeOrigin;
36
37 namespace DFG {
38
39 class Graph;
40 struct AbstractValue;
41 struct 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.
46 namespace Array {
47 enum Action : uint8_t {
48     Read,
49     Write
50 };
51
52 enum 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
82 enum 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
91 enum 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 };
98 enum Conversion : uint8_t {
99     AsIs,
100     Convert
101 };
102 } // namespace Array
103
104 const char* arrayActionToString(Array::Action);
105 const char* arrayTypeToString(Array::Type);
106 const char* arrayClassToString(Array::Class);
107 const char* arraySpeculationToString(Array::Speculation);
108 const char* arrayConversionToString(Array::Conversion);
109
110 IndexingType toIndexingShape(Array::Type);
111
112 TypedArrayType toTypedArrayType(Array::Type);
113 Array::Type toArrayType(TypedArrayType);
114 Array::Type refineTypedArrayType(Array::Type, TypedArrayType);
115
116 bool permitsBoundsCheckLowering(Array::Type);
117
118 class ArrayMode {
119 public:
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(arrayModeFromStructure(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 = arrayModesWithIndexingShape(Int32Shape);
434             break;
435         case Array::Double:
436             result = arrayModesWithIndexingShape(DoubleShape);
437             break;
438         case Array::Contiguous:
439             result = arrayModesWithIndexingShape(ContiguousShape);
440             break;
441         case Array::ArrayStorage:
442             return arrayModesWithIndexingShape(ArrayStorageShape);
443         case Array::SlowPutArrayStorage:
444             return arrayModesWithIndexingShapes(SlowPutArrayStorageShape, ArrayStorageShape);
445         case Array::DirectArguments:
446         case Array::ScopedArguments:
447             return arrayModesWithIndexingShapes(ArrayStorageShape, NonArray);
448         default:
449             return asArrayModes(NonArray);
450         }
451
452         if (action() == Array::Write)
453             result &= ~ALL_COPY_ON_WRITE_ARRAY_MODES;
454         return result;
455     }
456     
457     bool getIndexedPropertyStorageMayTriggerGC() const
458     {
459         return type() == Array::String;
460     }
461     
462     IndexingType shapeMask() const
463     {
464         return toIndexingShape(type());
465     }
466     
467     TypedArrayType typedArrayType() const
468     {
469         return toTypedArrayType(type());
470     }
471
472     bool isSomeTypedArrayView() const
473     {
474         return type() == Array::AnyTypedArray || isTypedView(typedArrayType());
475     }
476     
477     bool operator==(const ArrayMode& other) const
478     {
479         return type() == other.type()
480             && arrayClass() == other.arrayClass()
481             && speculation() == other.speculation()
482             && conversion() == other.conversion();
483     }
484     
485     bool operator!=(const ArrayMode& other) const
486     {
487         return !(*this == other);
488     }
489 private:
490     explicit ArrayMode(unsigned word)
491     {
492         u.asWord = word;
493     }
494     
495     ArrayModes arrayModesWithIndexingShape(IndexingType shape) const
496     {
497         switch (arrayClass()) {
498         case Array::NonArray:
499         case Array::OriginalNonArray:
500             return asArrayModes(shape);
501         case Array::OriginalCopyOnWriteArray:
502             ASSERT(hasInt32(shape) || hasDouble(shape) || hasContiguous(shape));
503             return asArrayModes(shape | IsArray) | asArrayModes(shape | IsArray | CopyOnWrite);
504         case Array::Array:
505             if (hasInt32(shape) || hasDouble(shape) || hasContiguous(shape))
506                 return asArrayModes(shape | IsArray) | asArrayModes(shape | IsArray | CopyOnWrite);
507             FALLTHROUGH;
508         case Array::OriginalArray:
509             return asArrayModes(shape | IsArray);
510         case Array::PossiblyArray:
511             if (hasInt32(shape) || hasDouble(shape) || hasContiguous(shape))
512                 return asArrayModes(shape) | asArrayModes(shape | IsArray) | asArrayModes(shape | IsArray | CopyOnWrite);
513             return asArrayModes(shape) | asArrayModes(shape | IsArray);
514         default:
515             // This is only necessary for C++ compilers that don't understand enums.
516             return 0;
517         }
518     }
519     
520     ArrayModes arrayModesWithIndexingShapes(IndexingType shape1, IndexingType shape2) const
521     {
522         ArrayModes arrayMode1 = arrayModesWithIndexingShape(shape1);
523         ArrayModes arrayMode2 = arrayModesWithIndexingShape(shape2);
524         return arrayMode1 | arrayMode2;
525     }
526
527     bool alreadyChecked(Graph&, Node*, const AbstractValue&, IndexingType shape) const;
528     
529     union {
530         struct {
531             uint8_t type;
532             uint8_t arrayClass;
533             uint8_t speculation;
534             uint8_t conversion : 4;
535             uint8_t action : 4;
536         } asBytes;
537         unsigned asWord;
538     } u;
539     static_assert(sizeof(decltype(u.asBytes)) == sizeof(decltype(u.asWord)), "the word form of ArrayMode should have the same size as the individual slices");
540 };
541
542 static inline bool canCSEStorage(const ArrayMode& arrayMode)
543 {
544     return arrayMode.canCSEStorage();
545 }
546
547 static inline bool lengthNeedsStorage(const ArrayMode& arrayMode)
548 {
549     return arrayMode.lengthNeedsStorage();
550 }
551
552 static inline bool neverNeedsStorage(const ArrayMode&)
553 {
554     return false;
555 }
556
557 } } // namespace JSC::DFG
558
559 namespace WTF {
560
561 class PrintStream;
562 void printInternal(PrintStream&, JSC::DFG::Array::Action);
563 void printInternal(PrintStream&, JSC::DFG::Array::Type);
564 void printInternal(PrintStream&, JSC::DFG::Array::Class);
565 void printInternal(PrintStream&, JSC::DFG::Array::Speculation);
566 void printInternal(PrintStream&, JSC::DFG::Array::Conversion);
567
568 } // namespace WTF
569
570 #endif // ENABLE(DFG_JIT)