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