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