45e1d5a1218c5641837e06730934ec4c51808c77
[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 "DFGNodeFlags.h"
32 #include "SpeculatedType.h"
33
34 namespace JSC {
35
36 struct CodeOrigin;
37
38 namespace DFG {
39
40 class Graph;
41 struct AbstractValue;
42 struct Node;
43
44 // Use a namespace + enum instead of enum alone to avoid the namespace collision
45 // that would otherwise occur, since we say things like "Int8Array" and "JSArray"
46 // in lots of other places, to mean subtly different things.
47 namespace Array {
48 enum Action {
49     Read,
50     Write
51 };
52
53 enum Type {
54     SelectUsingPredictions, // Implies that we need predictions to decide. We will never get to the backend in this mode.
55     SelectUsingArguments, // Implies that we use the Node's arguments to decide. We will never get to the backend in this mode.
56     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.
57     ForceExit, // Implies that we have no idea how to execute this operation, so we should just give up.
58     Generic,
59     String,
60
61     Undecided,
62     Int32,
63     Double,
64     Contiguous,
65     ArrayStorage,
66     SlowPutArrayStorage,
67     
68     DirectArguments,
69     ScopedArguments,
70     
71     Int8Array,
72     Int16Array,
73     Int32Array,
74     Uint8Array,
75     Uint8ClampedArray,
76     Uint16Array,
77     Uint32Array,
78     Float32Array,
79     Float64Array,
80     AnyTypedArray
81 };
82
83 enum Class {
84     NonArray, // Definitely some object that is not a JSArray.
85     OriginalNonArray, // Definitely some object that is not a JSArray, but that object has the original structure.
86     Array, // Definitely a JSArray, and may or may not have custom properties or have undergone some other bizarre transitions.
87     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.
88     PossiblyArray // Some object that may or may not be a JSArray.
89 };
90
91 enum Speculation {
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 {
99     AsIs,
100     Convert
101 };
102 } // namespace Array
103
104 const char* arrayTypeToString(Array::Type);
105 const char* arrayClassToString(Array::Class);
106 const char* arraySpeculationToString(Array::Speculation);
107 const char* arrayConversionToString(Array::Conversion);
108
109 IndexingType toIndexingShape(Array::Type);
110
111 TypedArrayType toTypedArrayType(Array::Type);
112 Array::Type toArrayType(TypedArrayType);
113 Array::Type refineTypedArrayType(Array::Type, TypedArrayType);
114
115 bool permitsBoundsCheckLowering(Array::Type);
116
117 class ArrayMode {
118 public:
119     ArrayMode()
120     {
121         u.asBytes.type = Array::SelectUsingPredictions;
122         u.asBytes.arrayClass = Array::NonArray;
123         u.asBytes.speculation = Array::InBounds;
124         u.asBytes.conversion = Array::AsIs;
125     }
126     
127     explicit ArrayMode(Array::Type type)
128     {
129         u.asBytes.type = type;
130         u.asBytes.arrayClass = Array::NonArray;
131         u.asBytes.speculation = Array::InBounds;
132         u.asBytes.conversion = Array::AsIs;
133     }
134     
135     ArrayMode(Array::Type type, Array::Class arrayClass)
136     {
137         u.asBytes.type = type;
138         u.asBytes.arrayClass = arrayClass;
139         u.asBytes.speculation = Array::InBounds;
140         u.asBytes.conversion = Array::AsIs;
141     }
142     
143     ArrayMode(Array::Type type, Array::Class arrayClass, Array::Speculation speculation, Array::Conversion conversion)
144     {
145         u.asBytes.type = type;
146         u.asBytes.arrayClass = arrayClass;
147         u.asBytes.speculation = speculation;
148         u.asBytes.conversion = conversion;
149     }
150     
151     ArrayMode(Array::Type type, Array::Class arrayClass, Array::Conversion conversion)
152     {
153         u.asBytes.type = type;
154         u.asBytes.arrayClass = arrayClass;
155         u.asBytes.speculation = Array::InBounds;
156         u.asBytes.conversion = conversion;
157     }
158     
159     Array::Type type() const { return static_cast<Array::Type>(u.asBytes.type); }
160     Array::Class arrayClass() const { return static_cast<Array::Class>(u.asBytes.arrayClass); }
161     Array::Speculation speculation() const { return static_cast<Array::Speculation>(u.asBytes.speculation); }
162     Array::Conversion conversion() const { return static_cast<Array::Conversion>(u.asBytes.conversion); }
163     
164     unsigned asWord() const { return u.asWord; }
165     
166     static ArrayMode fromWord(unsigned word)
167     {
168         return ArrayMode(word);
169     }
170     
171     static ArrayMode fromObserved(const ConcurrentJSLocker&, ArrayProfile*, Array::Action, bool makeSafe);
172     
173     ArrayMode withSpeculation(Array::Speculation speculation) const
174     {
175         return ArrayMode(type(), arrayClass(), speculation, conversion());
176     }
177     
178     ArrayMode withArrayClass(Array::Class arrayClass) const
179     {
180         return ArrayMode(type(), arrayClass, speculation(), conversion());
181     }
182     
183     ArrayMode withSpeculationFromProfile(const ConcurrentJSLocker& locker, ArrayProfile* profile, bool makeSafe) const
184     {
185         Array::Speculation mySpeculation;
186
187         if (makeSafe)
188             mySpeculation = Array::OutOfBounds;
189         else if (profile->mayStoreToHole(locker))
190             mySpeculation = Array::ToHole;
191         else
192             mySpeculation = Array::InBounds;
193         
194         return withSpeculation(mySpeculation);
195     }
196     
197     ArrayMode withProfile(const ConcurrentJSLocker& locker, ArrayProfile* profile, bool makeSafe) const
198     {
199         Array::Class myArrayClass;
200
201         if (isJSArray()) {
202             if (profile->usesOriginalArrayStructures(locker) && benefitsFromOriginalArray())
203                 myArrayClass = Array::OriginalArray;
204             else
205                 myArrayClass = Array::Array;
206         } else
207             myArrayClass = arrayClass();
208         
209         return withArrayClass(myArrayClass).withSpeculationFromProfile(locker, profile, makeSafe);
210     }
211     
212     ArrayMode withType(Array::Type type) const
213     {
214         return ArrayMode(type, arrayClass(), speculation(), conversion());
215     }
216     
217     ArrayMode withConversion(Array::Conversion conversion) const
218     {
219         return ArrayMode(type(), arrayClass(), speculation(), conversion);
220     }
221     
222     ArrayMode withTypeAndConversion(Array::Type type, Array::Conversion conversion) const
223     {
224         return ArrayMode(type, arrayClass(), speculation(), conversion);
225     }
226     
227     ArrayMode refine(Graph&, Node*, SpeculatedType base, SpeculatedType index, SpeculatedType value = SpecNone) const;
228     
229     bool alreadyChecked(Graph&, Node*, const AbstractValue&) const;
230     
231     void dump(PrintStream&) const;
232     
233     bool usesButterfly() const
234     {
235         switch (type()) {
236         case Array::Undecided:
237         case Array::Int32:
238         case Array::Double:
239         case Array::Contiguous:
240         case Array::ArrayStorage:
241         case Array::SlowPutArrayStorage:
242             return true;
243         default:
244             return false;
245         }
246     }
247     
248     bool isJSArray() const
249     {
250         switch (arrayClass()) {
251         case Array::Array:
252         case Array::OriginalArray:
253             return true;
254         default:
255             return false;
256         }
257     }
258     
259     bool isJSArrayWithOriginalStructure() const
260     {
261         return arrayClass() == Array::OriginalArray;
262     }
263     
264     bool isSaneChain() const
265     {
266         return speculation() == Array::SaneChain;
267     }
268     
269     bool isInBounds() const
270     {
271         switch (speculation()) {
272         case Array::SaneChain:
273         case Array::InBounds:
274             return true;
275         default:
276             return false;
277         }
278     }
279     
280     bool mayStoreToHole() const
281     {
282         return !isInBounds();
283     }
284     
285     bool isOutOfBounds() const
286     {
287         return speculation() == Array::OutOfBounds;
288     }
289     
290     bool isSlowPut() const
291     {
292         return type() == Array::SlowPutArrayStorage;
293     }
294     
295     bool canCSEStorage() const
296     {
297         switch (type()) {
298         case Array::SelectUsingPredictions:
299         case Array::SelectUsingArguments:
300         case Array::Unprofiled:
301         case Array::Undecided:
302         case Array::ForceExit:
303         case Array::Generic:
304         case Array::DirectArguments:
305         case Array::ScopedArguments:
306             return false;
307         default:
308             return true;
309         }
310     }
311     
312     bool lengthNeedsStorage() const
313     {
314         switch (type()) {
315         case Array::Undecided:
316         case Array::Int32:
317         case Array::Double:
318         case Array::Contiguous:
319         case Array::ArrayStorage:
320         case Array::SlowPutArrayStorage:
321             return true;
322         default:
323             return false;
324         }
325     }
326     
327     ArrayMode modeForPut() const
328     {
329         switch (type()) {
330         case Array::String:
331         case Array::DirectArguments:
332         case Array::ScopedArguments:
333             return ArrayMode(Array::Generic);
334         default:
335             return *this;
336         }
337     }
338     
339     bool isSpecific() const
340     {
341         switch (type()) {
342         case Array::SelectUsingPredictions:
343         case Array::SelectUsingArguments:
344         case Array::Unprofiled:
345         case Array::ForceExit:
346         case Array::Generic:
347             return false;
348         default:
349             return true;
350         }
351     }
352     
353     bool supportsSelfLength() const
354     {
355         switch (type()) {
356         case Array::SelectUsingPredictions:
357         case Array::Unprofiled:
358         case Array::ForceExit:
359         case Array::Generic:
360         // TypedArrays do not have a self length property as of ES6.
361         case Array::Int8Array:
362         case Array::Int16Array:
363         case Array::Int32Array:
364         case Array::Uint8Array:
365         case Array::Uint8ClampedArray:
366         case Array::Uint16Array:
367         case Array::Uint32Array:
368         case Array::Float32Array:
369         case Array::Float64Array:
370             return false;
371         case Array::Int32:
372         case Array::Double:
373         case Array::Contiguous:
374         case Array::ArrayStorage:
375         case Array::SlowPutArrayStorage:
376             return isJSArray();
377         default:
378             return true;
379         }
380     }
381     
382     bool permitsBoundsCheckLowering() const;
383     
384     bool benefitsFromOriginalArray() const
385     {
386         switch (type()) {
387         case Array::Int32:
388         case Array::Double:
389         case Array::Contiguous:
390         case Array::Undecided:
391         case Array::ArrayStorage:
392             return true;
393         default:
394             return false;
395         }
396     }
397     
398     // Returns 0 if this is not OriginalArray.
399     Structure* originalArrayStructure(Graph&, const CodeOrigin&) const;
400     Structure* originalArrayStructure(Graph&, Node*) const;
401     
402     bool doesConversion() const
403     {
404         return conversion() != Array::AsIs;
405     }
406
407     bool structureWouldPassArrayModeFiltering(Structure* structure)
408     {
409         return arrayModesAlreadyChecked(arrayModeFromStructure(structure), arrayModesThatPassFiltering());
410     }
411     
412     ArrayModes arrayModesThatPassFiltering() const
413     {
414         switch (type()) {
415         case Array::Generic:
416             return ALL_ARRAY_MODES;
417         case Array::Int32:
418             return arrayModesWithIndexingShape(Int32Shape);
419         case Array::Double:
420             return arrayModesWithIndexingShape(DoubleShape);
421         case Array::Contiguous:
422             return arrayModesWithIndexingShape(ContiguousShape);
423         case Array::ArrayStorage:
424             return arrayModesWithIndexingShape(ArrayStorageShape);
425         case Array::SlowPutArrayStorage:
426             return arrayModesWithIndexingShapes(SlowPutArrayStorageShape, ArrayStorageShape);
427         default:
428             return asArrayModes(NonArray);
429         }
430     }
431     
432     bool getIndexedPropertyStorageMayTriggerGC() const
433     {
434         return type() == Array::String;
435     }
436     
437     IndexingType shapeMask() const
438     {
439         return toIndexingShape(type());
440     }
441     
442     TypedArrayType typedArrayType() const
443     {
444         return toTypedArrayType(type());
445     }
446
447     bool isSomeTypedArrayView() const
448     {
449         return type() == Array::AnyTypedArray || isTypedView(typedArrayType());
450     }
451     
452     bool operator==(const ArrayMode& other) const
453     {
454         return type() == other.type()
455             && arrayClass() == other.arrayClass()
456             && speculation() == other.speculation()
457             && conversion() == other.conversion();
458     }
459     
460     bool operator!=(const ArrayMode& other) const
461     {
462         return !(*this == other);
463     }
464 private:
465     explicit ArrayMode(unsigned word)
466     {
467         u.asWord = word;
468     }
469     
470     ArrayModes arrayModesWithIndexingShape(IndexingType shape) const
471     {
472         switch (arrayClass()) {
473         case Array::NonArray:
474         case Array::OriginalNonArray:
475             return asArrayModes(shape);
476         case Array::Array:
477         case Array::OriginalArray:
478             return asArrayModes(shape | IsArray);
479         case Array::PossiblyArray:
480             return asArrayModes(shape) | asArrayModes(shape | IsArray);
481         default:
482             // This is only necessary for C++ compilers that don't understand enums.
483             return 0;
484         }
485     }
486     
487     ArrayModes arrayModesWithIndexingShapes(IndexingType shape1, IndexingType shape2) const
488     {
489         ArrayModes arrayMode1 = arrayModesWithIndexingShape(shape1);
490         ArrayModes arrayMode2 = arrayModesWithIndexingShape(shape2);
491         return arrayMode1 | arrayMode2;
492     }
493
494     bool alreadyChecked(Graph&, Node*, const AbstractValue&, IndexingType shape) const;
495     
496     union {
497         struct {
498             uint8_t type;
499             uint8_t arrayClass;
500             uint8_t speculation;
501             uint8_t conversion;
502         } asBytes;
503         unsigned asWord;
504     } u;
505 };
506
507 static inline bool canCSEStorage(const ArrayMode& arrayMode)
508 {
509     return arrayMode.canCSEStorage();
510 }
511
512 static inline bool lengthNeedsStorage(const ArrayMode& arrayMode)
513 {
514     return arrayMode.lengthNeedsStorage();
515 }
516
517 static inline bool neverNeedsStorage(const ArrayMode&)
518 {
519     return false;
520 }
521
522 } } // namespace JSC::DFG
523
524 namespace WTF {
525
526 class PrintStream;
527 void printInternal(PrintStream&, JSC::DFG::Array::Type);
528 void printInternal(PrintStream&, JSC::DFG::Array::Class);
529 void printInternal(PrintStream&, JSC::DFG::Array::Speculation);
530 void printInternal(PrintStream&, JSC::DFG::Array::Conversion);
531
532 } // namespace WTF
533
534 #endif // ENABLE(DFG_JIT)