DFG should have some facility for recognizing redundant CheckArrays and Arrayifies
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGArrayMode.h
1 /*
2  * Copyright (C) 2012 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 #include <wtf/Platform.h>
30
31 #if ENABLE(DFG_JIT)
32
33 #include "ArrayProfile.h"
34 #include "SpeculatedType.h"
35
36 namespace JSC { namespace DFG {
37
38 struct AbstractValue;
39
40 // Use a namespace + enum instead of enum alone to avoid the namespace collision
41 // that would otherwise occur, since we say things like "Int8Array" and "JSArray"
42 // in lots of other places, to mean subtly different things.
43 namespace Array {
44 enum Action {
45     Read,
46     Write
47 };
48
49 enum Mode {
50     Undecided, // Implies that we need predictions to decide. We will never get to the backend in this mode.
51     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.
52     ForceExit, // Implies that we have no idea how to execute this operation, so we should just give up.
53     Generic,
54     String,
55     
56     // Modes of conventional indexed storage where the check is non side-effecting.
57     Contiguous,
58     ContiguousToTail,
59     ContiguousOutOfBounds,
60     ArrayWithContiguous,
61     ArrayWithContiguousToTail,
62     ArrayWithContiguousOutOfBounds,
63     PossiblyArrayWithContiguous,
64     PossiblyArrayWithContiguousToTail,
65     PossiblyArrayWithContiguousOutOfBounds,
66     ArrayStorage,
67     ArrayStorageToHole,
68     SlowPutArrayStorage,
69     ArrayStorageOutOfBounds,
70     ArrayWithArrayStorage,
71     ArrayWithArrayStorageToHole,
72     ArrayWithSlowPutArrayStorage,
73     ArrayWithArrayStorageOutOfBounds,
74     PossiblyArrayWithArrayStorage,
75     PossiblyArrayWithArrayStorageToHole,
76     PossiblyArrayWithSlowPutArrayStorage,
77     PossiblyArrayWithArrayStorageOutOfBounds,
78     
79     // Modes of conventional indexed storage where the check is side-effecting.
80     ToContiguous,
81     ToArrayStorage,
82     ArrayToArrayStorage,
83     PossiblyArrayToArrayStorage,
84     ToSlowPutArrayStorage,
85     
86     Arguments,
87     Int8Array,
88     Int16Array,
89     Int32Array,
90     Uint8Array,
91     Uint8ClampedArray,
92     Uint16Array,
93     Uint32Array,
94     Float32Array,
95     Float64Array
96 };
97 } // namespace Array
98
99 // Helpers for 'case' statements. For example, saying "case AllArrayStorageModes:"
100 // is the same as having multiple case statements listing off all of the modes that
101 // have the word "ArrayStorage" in them.
102
103 // First: helpers for non-side-effecting checks.
104 #define NON_ARRAY_CONTIGUOUS_MODES                         \
105     Array::Contiguous:                                     \
106     case Array::ContiguousToTail:                          \
107     case Array::ContiguousOutOfBounds:                     \
108     case Array::PossiblyArrayWithContiguous:               \
109     case Array::PossiblyArrayWithContiguousToTail:         \
110     case Array::PossiblyArrayWithContiguousOutOfBounds
111 #define ARRAY_WITH_CONTIGUOUS_MODES                        \
112     Array::ArrayWithContiguous:                            \
113     case Array::ArrayWithContiguousToTail:                 \
114     case Array::ArrayWithContiguousOutOfBounds
115 #define ALL_CONTIGUOUS_MODES                               \
116     NON_ARRAY_CONTIGUOUS_MODES:                            \
117     case ARRAY_WITH_CONTIGUOUS_MODES
118 #define IN_BOUNDS_CONTIGUOUS_MODES                         \
119     Array::Contiguous:                                     \
120     case Array::ArrayWithContiguous:                       \
121     case Array::PossiblyArrayWithContiguous
122 #define CONTIGUOUS_TO_TAIL_MODES                           \
123     Array::ContiguousToTail:                               \
124     case Array::ArrayWithContiguousToTail:                 \
125     case Array::PossiblyArrayWithContiguousToTail
126 #define OUT_OF_BOUNDS_CONTIGUOUS_MODES                     \
127     Array::ContiguousOutOfBounds:                          \
128     case Array::ArrayWithContiguousOutOfBounds:            \
129     case Array::PossiblyArrayWithContiguousOutOfBounds
130 #define NON_ARRAY_ARRAY_STORAGE_MODES                      \
131     Array::ArrayStorage:                                   \
132     case Array::ArrayStorageToHole:                        \
133     case Array::SlowPutArrayStorage:                       \
134     case Array::ArrayStorageOutOfBounds:                   \
135     case Array::PossiblyArrayWithArrayStorage:             \
136     case Array::PossiblyArrayWithArrayStorageToHole:       \
137     case Array::PossiblyArrayWithSlowPutArrayStorage:      \
138     case Array::PossiblyArrayWithArrayStorageOutOfBounds
139 #define ARRAY_WITH_ARRAY_STORAGE_MODES                     \
140     Array::ArrayWithArrayStorage:                          \
141     case Array::ArrayWithArrayStorageToHole:               \
142     case Array::ArrayWithSlowPutArrayStorage:              \
143     case Array::ArrayWithArrayStorageOutOfBounds
144 #define ALL_ARRAY_STORAGE_MODES                            \
145     NON_ARRAY_ARRAY_STORAGE_MODES:                         \
146     case ARRAY_WITH_ARRAY_STORAGE_MODES
147 #define IN_BOUNDS_ARRAY_STORAGE_MODES                      \
148     Array::ArrayStorage:                                   \
149     case Array::ArrayWithArrayStorage:                     \
150     case Array::PossiblyArrayWithArrayStorage
151 #define ARRAY_STORAGE_TO_HOLE_MODES                        \
152     Array::ArrayStorageToHole:                             \
153     case Array::ArrayWithArrayStorageToHole:               \
154     case Array::PossiblyArrayWithArrayStorageToHole
155 #define SLOW_PUT_ARRAY_STORAGE_MODES                       \
156     Array::SlowPutArrayStorage:                            \
157     case Array::ArrayWithSlowPutArrayStorage:              \
158     case Array::PossiblyArrayWithSlowPutArrayStorage
159 #define OUT_OF_BOUNDS_ARRAY_STORAGE_MODES                  \
160     Array::ArrayStorageOutOfBounds:                        \
161     case Array::ArrayWithArrayStorageOutOfBounds:          \
162     case Array::PossiblyArrayWithArrayStorageOutOfBounds
163
164 // Next: helpers for side-effecting checks.
165 #define NON_ARRAY_EFFECTFUL_MODES                          \
166     Array::ToContiguous:                                   \
167     case Array::ToArrayStorage:                            \
168     case Array::ToSlowPutArrayStorage:                     \
169     case Array::PossiblyArrayToArrayStorage
170 #define ARRAY_EFFECTFUL_MODES                              \
171     Array::ArrayToArrayStorage
172 #define ALL_EFFECTFUL_CONTIGUOUS_MODES                     \
173     Array::ToContiguous
174 #define ALL_EFFECTFUL_ARRAY_STORAGE_MODES                  \
175     Array::ToArrayStorage:                                 \
176     case Array::ToSlowPutArrayStorage:                     \
177     case Array::ArrayToArrayStorage:                       \
178     case Array::PossiblyArrayToArrayStorage
179 #define SLOW_PUT_EFFECTFUL_ARRAY_STORAGE_MODES             \
180     Array::ToSlowPutArrayStorage
181 #define ALL_EFFECTFUL_MODES                                \
182     ALL_EFFECTFUL_CONTIGUOUS_MODES:                        \
183     case ALL_EFFECTFUL_ARRAY_STORAGE_MODES
184
185 Array::Mode fromObserved(ArrayProfile*, Array::Action, bool makeSafe);
186
187 Array::Mode refineArrayMode(Array::Mode, SpeculatedType base, SpeculatedType index);
188
189 bool modeAlreadyChecked(AbstractValue&, Array::Mode);
190
191 const char* modeToString(Array::Mode);
192
193 inline bool modeUsesButterfly(Array::Mode arrayMode)
194 {
195     switch (arrayMode) {
196     case ALL_CONTIGUOUS_MODES:
197     case ALL_ARRAY_STORAGE_MODES:
198     case ALL_EFFECTFUL_MODES:
199         return true;
200     default:
201         return false;
202     }
203 }
204
205 inline bool modeIsJSArray(Array::Mode arrayMode)
206 {
207     switch (arrayMode) {
208     case ARRAY_WITH_CONTIGUOUS_MODES:
209     case ARRAY_WITH_ARRAY_STORAGE_MODES:
210     case ARRAY_EFFECTFUL_MODES:
211         return true;
212     default:
213         return false;
214     }
215 }
216
217 inline bool isInBoundsAccess(Array::Mode arrayMode)
218 {
219     switch (arrayMode) {
220     case IN_BOUNDS_CONTIGUOUS_MODES:
221     case CONTIGUOUS_TO_TAIL_MODES:
222     case ARRAY_STORAGE_TO_HOLE_MODES:
223     case IN_BOUNDS_ARRAY_STORAGE_MODES:
224         return true;
225     default:
226         return false;
227     }
228 }
229
230 inline bool isSlowPutAccess(Array::Mode arrayMode)
231 {
232     switch (arrayMode) {
233     case SLOW_PUT_ARRAY_STORAGE_MODES:
234     case SLOW_PUT_EFFECTFUL_ARRAY_STORAGE_MODES:
235         return true;
236     default:
237         return false;
238     }
239 }
240
241 inline bool mayStoreToTail(Array::Mode arrayMode)
242 {
243     switch (arrayMode) {
244     case CONTIGUOUS_TO_TAIL_MODES:
245     case OUT_OF_BOUNDS_CONTIGUOUS_MODES:
246     case ALL_EFFECTFUL_CONTIGUOUS_MODES:
247         return true;
248     default:
249         return false;
250     }
251 }
252
253 inline bool mayStoreToHole(Array::Mode arrayMode)
254 {
255     switch (arrayMode) {
256     case ARRAY_STORAGE_TO_HOLE_MODES:
257     case OUT_OF_BOUNDS_ARRAY_STORAGE_MODES:
258     case SLOW_PUT_ARRAY_STORAGE_MODES:
259     case ALL_EFFECTFUL_ARRAY_STORAGE_MODES:
260         return true;
261     default:
262         return false;
263     }
264 }
265
266 inline bool canCSEStorage(Array::Mode arrayMode)
267 {
268     switch (arrayMode) {
269     case Array::Undecided:
270     case Array::Unprofiled:
271     case Array::ForceExit:
272     case Array::Generic:
273     case Array::Arguments:
274         return false;
275     default:
276         return true;
277     }
278 }
279
280 inline bool lengthNeedsStorage(Array::Mode arrayMode)
281 {
282     return modeIsJSArray(arrayMode);
283 }
284
285 inline Array::Mode modeForPut(Array::Mode arrayMode)
286 {
287     switch (arrayMode) {
288     case Array::String:
289         return Array::Generic;
290 #if USE(JSVALUE32_64)
291     case Array::Arguments:
292         return Array::Generic;
293 #endif
294     default:
295         return arrayMode;
296     }
297 }
298
299 inline bool modeIsSpecific(Array::Mode mode)
300 {
301     switch (mode) {
302     case Array::Undecided:
303     case Array::Unprofiled:
304     case Array::ForceExit:
305     case Array::Generic:
306         return false;
307     default:
308         return true;
309     }
310 }
311
312 inline bool modeSupportsLength(Array::Mode mode)
313 {
314     switch (mode) {
315     case Array::Undecided:
316     case Array::Unprofiled:
317     case Array::ForceExit:
318     case Array::Generic:
319     case NON_ARRAY_CONTIGUOUS_MODES:
320     case NON_ARRAY_ARRAY_STORAGE_MODES:
321     case NON_ARRAY_EFFECTFUL_MODES:
322         return false;
323     default:
324         return true;
325     }
326 }
327
328 inline bool benefitsFromStructureCheck(Array::Mode mode)
329 {
330     switch (mode) {
331     case ALL_EFFECTFUL_MODES:
332     case Array::Undecided:
333     case Array::Unprofiled:
334     case Array::ForceExit:
335     case Array::Generic:
336         return false;
337     default:
338         return true;
339     }
340 }
341
342 inline bool isEffectful(Array::Mode mode)
343 {
344     switch (mode) {
345     case ALL_EFFECTFUL_MODES:
346         return true;
347     default:
348         return false;
349     }
350 }
351
352 // This returns the set of array modes that will pass filtering of a CheckArray or
353 // Arrayify with the given mode.
354 inline ArrayModes arrayModesFor(Array::Mode arrayMode)
355 {
356     switch (arrayMode) {
357     case Array::Generic:
358         return ALL_ARRAY_MODES;
359     case Array::Contiguous:
360     case Array::ContiguousToTail:
361     case Array::ContiguousOutOfBounds:
362     case Array::ToContiguous:
363         return asArrayModes(NonArrayWithContiguous);
364     case Array::PossiblyArrayWithContiguous:
365     case Array::PossiblyArrayWithContiguousToTail:
366     case Array::PossiblyArrayWithContiguousOutOfBounds:
367         return asArrayModes(NonArrayWithContiguous) | asArrayModes(ArrayWithContiguous);
368     case ARRAY_WITH_CONTIGUOUS_MODES:
369         return asArrayModes(ArrayWithContiguous);
370     case Array::ArrayStorage:
371     case Array::ArrayStorageToHole:
372     case Array::ArrayStorageOutOfBounds:
373     case Array::ToArrayStorage:
374         return asArrayModes(NonArrayWithArrayStorage);
375     case Array::ToSlowPutArrayStorage:
376     case Array::SlowPutArrayStorage:
377         return asArrayModes(NonArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage);
378     case Array::PossiblyArrayWithArrayStorage:
379     case Array::PossiblyArrayWithArrayStorageToHole:
380     case Array::PossiblyArrayWithArrayStorageOutOfBounds:
381     case Array::PossiblyArrayToArrayStorage:
382         return asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage);
383     case Array::PossiblyArrayWithSlowPutArrayStorage:
384         return asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage);
385     case Array::ArrayWithArrayStorage:
386     case Array::ArrayWithArrayStorageToHole:
387     case Array::ArrayWithArrayStorageOutOfBounds:
388     case Array::ArrayToArrayStorage:
389         return asArrayModes(ArrayWithArrayStorage);
390     case Array::ArrayWithSlowPutArrayStorage:
391         return asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage);
392     default:
393         return asArrayModes(NonArray);
394     }
395 }
396
397 } } // namespace JSC::DFG
398
399 #endif // ENABLE(DFG_JIT)
400
401 #endif // DFGArrayMode_h
402