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#include "config.h"
27#include "DFGArrayMode.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGAbstractValue.h"
32#include "DFGGraph.h"
33#include "JSCInlines.h"
34
35namespace JSC { namespace DFG {
36
37ArrayMode ArrayMode::fromObserved(const ConcurrentJITLocker& locker, ArrayProfile* profile, Array::Action action, bool makeSafe)
38{
39    Array::Class nonArray;
40    if (profile->usesOriginalArrayStructures(locker))
41        nonArray = Array::OriginalNonArray;
42    else
43        nonArray = Array::NonArray;
44
45    ArrayModes observed = profile->observedArrayModes(locker);
46    switch (observed) {
47    case 0:
48        return ArrayMode(Array::Unprofiled);
49    case asArrayModes(NonArray):
50        if (action == Array::Write && !profile->mayInterceptIndexedAccesses(locker))
51            return ArrayMode(Array::Undecided, nonArray, Array::OutOfBounds, Array::Convert);
52        return ArrayMode(Array::SelectUsingPredictions, nonArray).withSpeculationFromProfile(locker, profile, makeSafe);
53
54    case asArrayModes(ArrayWithUndecided):
55        if (action == Array::Write)
56            return ArrayMode(Array::Undecided, Array::Array, Array::OutOfBounds, Array::Convert);
57        return ArrayMode(Array::Generic);
58
59    case asArrayModes(NonArray) | asArrayModes(ArrayWithUndecided):
60        if (action == Array::Write && !profile->mayInterceptIndexedAccesses(locker))
61            return ArrayMode(Array::Undecided, Array::PossiblyArray, Array::OutOfBounds, Array::Convert);
62        return ArrayMode(Array::SelectUsingPredictions).withSpeculationFromProfile(locker, profile, makeSafe);
63
64    case asArrayModes(NonArrayWithInt32):
65        return ArrayMode(Array::Int32, nonArray, Array::AsIs).withProfile(locker, profile, makeSafe);
66    case asArrayModes(ArrayWithInt32):
67        return ArrayMode(Array::Int32, Array::Array, Array::AsIs).withProfile(locker, profile, makeSafe);
68    case asArrayModes(NonArrayWithInt32) | asArrayModes(ArrayWithInt32):
69        return ArrayMode(Array::Int32, Array::PossiblyArray, Array::AsIs).withProfile(locker, profile, makeSafe);
70
71    case asArrayModes(NonArrayWithDouble):
72        return ArrayMode(Array::Double, nonArray, Array::AsIs).withProfile(locker, profile, makeSafe);
73    case asArrayModes(ArrayWithDouble):
74        return ArrayMode(Array::Double, Array::Array, Array::AsIs).withProfile(locker, profile, makeSafe);
75    case asArrayModes(NonArrayWithDouble) | asArrayModes(ArrayWithDouble):
76        return ArrayMode(Array::Double, Array::PossiblyArray, Array::AsIs).withProfile(locker, profile, makeSafe);
77
78    case asArrayModes(NonArrayWithContiguous):
79        return ArrayMode(Array::Contiguous, nonArray, Array::AsIs).withProfile(locker, profile, makeSafe);
80    case asArrayModes(ArrayWithContiguous):
81        return ArrayMode(Array::Contiguous, Array::Array, Array::AsIs).withProfile(locker, profile, makeSafe);
82    case asArrayModes(NonArrayWithContiguous) | asArrayModes(ArrayWithContiguous):
83        return ArrayMode(Array::Contiguous, Array::PossiblyArray, Array::AsIs).withProfile(locker, profile, makeSafe);
84
85    case asArrayModes(NonArrayWithArrayStorage):
86        return ArrayMode(Array::ArrayStorage, nonArray, Array::AsIs).withProfile(locker, profile, makeSafe);
87    case asArrayModes(NonArrayWithSlowPutArrayStorage):
88    case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage):
89        return ArrayMode(Array::SlowPutArrayStorage, nonArray, Array::AsIs).withProfile(locker, profile, makeSafe);
90    case asArrayModes(ArrayWithArrayStorage):
91        return ArrayMode(Array::ArrayStorage, Array::Array, Array::AsIs).withProfile(locker, profile, makeSafe);
92    case asArrayModes(ArrayWithSlowPutArrayStorage):
93    case asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
94        return ArrayMode(Array::SlowPutArrayStorage, Array::Array, Array::AsIs).withProfile(locker, profile, makeSafe);
95    case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage):
96        return ArrayMode(Array::ArrayStorage, Array::PossiblyArray, Array::AsIs).withProfile(locker, profile, makeSafe);
97    case asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
98    case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
99        return ArrayMode(Array::SlowPutArrayStorage, Array::PossiblyArray, Array::AsIs).withProfile(locker, profile, makeSafe);
100
101    default:
102        if ((observed & asArrayModes(NonArray)) && profile->mayInterceptIndexedAccesses(locker))
103            return ArrayMode(Array::SelectUsingPredictions).withSpeculationFromProfile(locker, profile, makeSafe);
104
105        Array::Type type;
106        Array::Class arrayClass;
107
108        if (shouldUseSlowPutArrayStorage(observed))
109            type = Array::SlowPutArrayStorage;
110        else if (shouldUseFastArrayStorage(observed))
111            type = Array::ArrayStorage;
112        else if (shouldUseContiguous(observed))
113            type = Array::Contiguous;
114        else if (shouldUseDouble(observed))
115            type = Array::Double;
116        else if (shouldUseInt32(observed))
117            type = Array::Int32;
118        else
119            type = Array::Undecided;
120
121        if (hasSeenArray(observed) && hasSeenNonArray(observed))
122            arrayClass = Array::PossiblyArray;
123        else if (hasSeenArray(observed))
124            arrayClass = Array::Array;
125        else if (hasSeenNonArray(observed))
126            arrayClass = nonArray;
127        else
128            arrayClass = Array::PossiblyArray;
129
130        return ArrayMode(type, arrayClass, Array::Convert).withProfile(locker, profile, makeSafe);
131    }
132}
133
134ArrayMode ArrayMode::refine(
135    Graph& graph, Node* node,
136    SpeculatedType base, SpeculatedType index, SpeculatedType value,
137    NodeFlags flags) const
138{
139    if (!base || !index) {
140        // It can be that we had a legitimate arrayMode but no incoming predictions. That'll
141        // happen if we inlined code based on, say, a global variable watchpoint, but later
142        // realized that the callsite could not have possibly executed. It may be worthwhile
143        // to fix that, but for now I'm leaving it as-is.
144        return ArrayMode(Array::ForceExit);
145    }
146
147    if (!isInt32Speculation(index))
148        return ArrayMode(Array::Generic);
149
150    // Note: our profiling currently doesn't give us good information in case we have
151    // an unlikely control flow path that sets the base to a non-cell value. Value
152    // profiling and prediction propagation will probably tell us that the value is
153    // either a cell or not, but that doesn't tell us which is more likely: that this
154    // is an array access on a cell (what we want and can optimize) or that the user is
155    // doing a crazy by-val access on a primitive (we can't easily optimize this and
156    // don't want to). So, for now, we assume that if the base is not a cell according
157    // to value profiling, but the array profile tells us something else, then we
158    // should just trust the array profile.
159
160    switch (type()) {
161    case Array::Unprofiled:
162        return ArrayMode(Array::ForceExit);
163
164    case Array::Undecided:
165        if (!value)
166            return withType(Array::ForceExit);
167        if (isInt32Speculation(value))
168            return withTypeAndConversion(Array::Int32, Array::Convert);
169        if (isFullNumberSpeculation(value))
170            return withTypeAndConversion(Array::Double, Array::Convert);
171        return withTypeAndConversion(Array::Contiguous, Array::Convert);
172
173    case Array::Int32:
174        if (!value || isInt32Speculation(value))
175            return *this;
176        if (isFullNumberSpeculation(value))
177            return withTypeAndConversion(Array::Double, Array::Convert);
178        return withTypeAndConversion(Array::Contiguous, Array::Convert);
179
180    case Array::Double:
181        if (flags & NodeBytecodeUsesAsInt)
182            return withTypeAndConversion(Array::Contiguous, Array::RageConvert);
183        if (!value || isFullNumberSpeculation(value))
184            return *this;
185        return withTypeAndConversion(Array::Contiguous, Array::Convert);
186
187    case Array::Contiguous:
188        if (doesConversion() && (flags & NodeBytecodeUsesAsInt))
189            return withConversion(Array::RageConvert);
190        return *this;
191
192    case Array::SelectUsingPredictions: {
193        base &= ~SpecOther;
194
195        if (isStringSpeculation(base))
196            return withType(Array::String);
197
198        if (isArgumentsSpeculation(base))
199            return withType(Array::Arguments);
200
201        ArrayMode result;
202        switch (node->op()) {
203        case PutByVal:
204            if (graph.hasExitSite(node->origin.semantic, OutOfBounds) || !isInBounds())
205                result = withSpeculation(Array::OutOfBounds);
206            else
207                result = withSpeculation(Array::InBounds);
208            break;
209
210        default:
211            result = withSpeculation(Array::InBounds);
212            break;
213        }
214
215        if (isInt8ArraySpeculation(base))
216            return result.withType(Array::Int8Array);
217
218        if (isInt16ArraySpeculation(base))
219            return result.withType(Array::Int16Array);
220
221        if (isInt32ArraySpeculation(base))
222            return result.withType(Array::Int32Array);
223
224        if (isUint8ArraySpeculation(base))
225            return result.withType(Array::Uint8Array);
226
227        if (isUint8ClampedArraySpeculation(base))
228            return result.withType(Array::Uint8ClampedArray);
229
230        if (isUint16ArraySpeculation(base))
231            return result.withType(Array::Uint16Array);
232
233        if (isUint32ArraySpeculation(base))
234            return result.withType(Array::Uint32Array);
235
236        if (isFloat32ArraySpeculation(base))
237            return result.withType(Array::Float32Array);
238
239        if (isFloat64ArraySpeculation(base))
240            return result.withType(Array::Float64Array);
241
242        return ArrayMode(Array::Generic);
243    }
244
245    default:
246        return *this;
247    }
248}
249
250Structure* ArrayMode::originalArrayStructure(Graph& graph, const CodeOrigin& codeOrigin) const
251{
252    JSGlobalObject* globalObject = graph.globalObjectFor(codeOrigin);
253
254    switch (arrayClass()) {
255    case Array::OriginalArray: {
256        switch (type()) {
257        case Array::Int32:
258            return globalObject->originalArrayStructureForIndexingType(ArrayWithInt32);
259        case Array::Double:
260            return globalObject->originalArrayStructureForIndexingType(ArrayWithDouble);
261        case Array::Contiguous:
262            return globalObject->originalArrayStructureForIndexingType(ArrayWithContiguous);
263        case Array::ArrayStorage:
264            return globalObject->originalArrayStructureForIndexingType(ArrayWithArrayStorage);
265        default:
266            CRASH();
267            return 0;
268        }
269    }
270
271    case Array::OriginalNonArray: {
272        TypedArrayType type = typedArrayType();
273        if (type == NotTypedArray)
274            return 0;
275
276        return globalObject->typedArrayStructure(type);
277    }
278
279    default:
280        return 0;
281    }
282}
283
284Structure* ArrayMode::originalArrayStructure(Graph& graph, Node* node) const
285{
286    return originalArrayStructure(graph, node->origin.semantic);
287}
288
289bool ArrayMode::alreadyChecked(Graph& graph, Node* node, AbstractValue& value, IndexingType shape) const
290{
291    switch (arrayClass()) {
292    case Array::OriginalArray:
293        return value.m_currentKnownStructure.hasSingleton()
294            && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape
295            && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray)
296            && graph.globalObjectFor(node->origin.semantic)->isOriginalArrayStructure(value.m_currentKnownStructure.singleton());
297
298    case Array::Array:
299        if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(shape | IsArray)))
300            return true;
301        return value.m_currentKnownStructure.hasSingleton()
302            && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape
303            && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
304
305    default:
306        if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(shape) | asArrayModes(shape | IsArray)))
307            return true;
308        return value.m_currentKnownStructure.hasSingleton()
309            && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape;
310    }
311}
312
313bool ArrayMode::alreadyChecked(Graph& graph, Node* node, AbstractValue& value) const
314{
315    switch (type()) {
316    case Array::Generic:
317        return true;
318
319    case Array::ForceExit:
320        return false;
321
322    case Array::String:
323        return speculationChecked(value.m_type, SpecString);
324
325    case Array::Int32:
326        return alreadyChecked(graph, node, value, Int32Shape);
327
328    case Array::Double:
329        return alreadyChecked(graph, node, value, DoubleShape);
330
331    case Array::Contiguous:
332        return alreadyChecked(graph, node, value, ContiguousShape);
333
334    case Array::ArrayStorage:
335        return alreadyChecked(graph, node, value, ArrayStorageShape);
336
337    case Array::SlowPutArrayStorage:
338        switch (arrayClass()) {
339        case Array::OriginalArray:
340            CRASH();
341            return false;
342
343        case Array::Array:
344            if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage)))
345                return true;
346            return value.m_currentKnownStructure.hasSingleton()
347                && hasAnyArrayStorage(value.m_currentKnownStructure.singleton()->indexingType())
348                && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
349
350        default:
351            if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage)))
352                return true;
353            return value.m_currentKnownStructure.hasSingleton()
354                && hasAnyArrayStorage(value.m_currentKnownStructure.singleton()->indexingType());
355        }
356
357    case Array::Arguments:
358        return speculationChecked(value.m_type, SpecArguments);
359
360    case Array::Int8Array:
361        return speculationChecked(value.m_type, SpecInt8Array);
362
363    case Array::Int16Array:
364        return speculationChecked(value.m_type, SpecInt16Array);
365
366    case Array::Int32Array:
367        return speculationChecked(value.m_type, SpecInt32Array);
368
369    case Array::Uint8Array:
370        return speculationChecked(value.m_type, SpecUint8Array);
371
372    case Array::Uint8ClampedArray:
373        return speculationChecked(value.m_type, SpecUint8ClampedArray);
374
375    case Array::Uint16Array:
376        return speculationChecked(value.m_type, SpecUint16Array);
377
378    case Array::Uint32Array:
379        return speculationChecked(value.m_type, SpecUint32Array);
380
381    case Array::Float32Array:
382        return speculationChecked(value.m_type, SpecFloat32Array);
383
384    case Array::Float64Array:
385        return speculationChecked(value.m_type, SpecFloat64Array);
386
387    case Array::SelectUsingPredictions:
388    case Array::Unprofiled:
389    case Array::Undecided:
390        break;
391    }
392
393    CRASH();
394    return false;
395}
396
397const char* arrayTypeToString(Array::Type type)
398{
399    switch (type) {
400    case Array::SelectUsingPredictions:
401        return "SelectUsingPredictions";
402    case Array::Unprofiled:
403        return "Unprofiled";
404    case Array::Generic:
405        return "Generic";
406    case Array::ForceExit:
407        return "ForceExit";
408    case Array::String:
409        return "String";
410    case Array::Undecided:
411        return "Undecided";
412    case Array::Int32:
413        return "Int32";
414    case Array::Double:
415        return "Double";
416    case Array::Contiguous:
417        return "Contiguous";
418    case Array::ArrayStorage:
419        return "ArrayStorage";
420    case Array::SlowPutArrayStorage:
421        return "SlowPutArrayStorage";
422    case Array::Arguments:
423        return "Arguments";
424    case Array::Int8Array:
425        return "Int8Array";
426    case Array::Int16Array:
427        return "Int16Array";
428    case Array::Int32Array:
429        return "Int32Array";
430    case Array::Uint8Array:
431        return "Uint8Array";
432    case Array::Uint8ClampedArray:
433        return "Uint8ClampedArray";
434    case Array::Uint16Array:
435        return "Uint16Array";
436    case Array::Uint32Array:
437        return "Uint32Array";
438    case Array::Float32Array:
439        return "Float32Array";
440    case Array::Float64Array:
441        return "Float64Array";
442    default:
443        // Better to return something then it is to crash. Remember, this method
444        // is being called from our main diagnostic tool, the IR dumper. It's like
445        // a stack trace. So if we get here then probably something has already
446        // gone wrong.
447        return "Unknown!";
448    }
449}
450
451const char* arrayClassToString(Array::Class arrayClass)
452{
453    switch (arrayClass) {
454    case Array::Array:
455        return "Array";
456    case Array::OriginalArray:
457        return "OriginalArray";
458    case Array::NonArray:
459        return "NonArray";
460    case Array::OriginalNonArray:
461        return "OriginalNonArray";
462    case Array::PossiblyArray:
463        return "PossiblyArray";
464    default:
465        return "Unknown!";
466    }
467}
468
469const char* arraySpeculationToString(Array::Speculation speculation)
470{
471    switch (speculation) {
472    case Array::SaneChain:
473        return "SaneChain";
474    case Array::InBounds:
475        return "InBounds";
476    case Array::ToHole:
477        return "ToHole";
478    case Array::OutOfBounds:
479        return "OutOfBounds";
480    default:
481        return "Unknown!";
482    }
483}
484
485const char* arrayConversionToString(Array::Conversion conversion)
486{
487    switch (conversion) {
488    case Array::AsIs:
489        return "AsIs";
490    case Array::Convert:
491        return "Convert";
492    case Array::RageConvert:
493        return "RageConvert";
494    default:
495        return "Unknown!";
496    }
497}
498
499IndexingType toIndexingShape(Array::Type type)
500{
501    switch (type) {
502    case Array::Int32:
503        return Int32Shape;
504    case Array::Double:
505        return DoubleShape;
506    case Array::Contiguous:
507        return ContiguousShape;
508    case Array::ArrayStorage:
509        return ArrayStorageShape;
510    case Array::SlowPutArrayStorage:
511        return SlowPutArrayStorageShape;
512    default:
513        return NoIndexingShape;
514    }
515}
516
517TypedArrayType toTypedArrayType(Array::Type type)
518{
519    switch (type) {
520    case Array::Int8Array:
521        return TypeInt8;
522    case Array::Int16Array:
523        return TypeInt16;
524    case Array::Int32Array:
525        return TypeInt32;
526    case Array::Uint8Array:
527        return TypeUint8;
528    case Array::Uint8ClampedArray:
529        return TypeUint8Clamped;
530    case Array::Uint16Array:
531        return TypeUint16;
532    case Array::Uint32Array:
533        return TypeUint32;
534    case Array::Float32Array:
535        return TypeFloat32;
536    case Array::Float64Array:
537        return TypeFloat64;
538    default:
539        return NotTypedArray;
540    }
541}
542
543Array::Type toArrayType(TypedArrayType type)
544{
545    switch (type) {
546    case TypeInt8:
547        return Array::Int8Array;
548    case TypeInt16:
549        return Array::Int16Array;
550    case TypeInt32:
551        return Array::Int32Array;
552    case TypeUint8:
553        return Array::Uint8Array;
554    case TypeUint8Clamped:
555        return Array::Uint8ClampedArray;
556    case TypeUint16:
557        return Array::Uint16Array;
558    case TypeUint32:
559        return Array::Uint32Array;
560    case TypeFloat32:
561        return Array::Float32Array;
562    case TypeFloat64:
563        return Array::Float64Array;
564    default:
565        return Array::Generic;
566    }
567}
568
569bool permitsBoundsCheckLowering(Array::Type type)
570{
571    switch (type) {
572    case Array::Int32:
573    case Array::Double:
574    case Array::Contiguous:
575    case Array::Int8Array:
576    case Array::Int16Array:
577    case Array::Int32Array:
578    case Array::Uint8Array:
579    case Array::Uint8ClampedArray:
580    case Array::Uint16Array:
581    case Array::Uint32Array:
582    case Array::Float32Array:
583    case Array::Float64Array:
584        return true;
585    default:
586        // These don't allow for bounds check lowering either because the bounds
587        // check involves something other than GetArrayLength (like ArrayStorage),
588        // or because the bounds check isn't a speculation (like String, sort of),
589        // or because the type implies an impure access.
590        return false;
591    }
592}
593
594bool ArrayMode::permitsBoundsCheckLowering() const
595{
596    return DFG::permitsBoundsCheckLowering(type()) && isInBounds();
597}
598
599void ArrayMode::dump(PrintStream& out) const
600{
601    out.print(type(), arrayClass(), speculation(), conversion());
602}
603
604} } // namespace JSC::DFG
605
606namespace WTF {
607
608void printInternal(PrintStream& out, JSC::DFG::Array::Type type)
609{
610    out.print(JSC::DFG::arrayTypeToString(type));
611}
612
613void printInternal(PrintStream& out, JSC::DFG::Array::Class arrayClass)
614{
615    out.print(JSC::DFG::arrayClassToString(arrayClass));
616}
617
618void printInternal(PrintStream& out, JSC::DFG::Array::Speculation speculation)
619{
620    out.print(JSC::DFG::arraySpeculationToString(speculation));
621}
622
623void printInternal(PrintStream& out, JSC::DFG::Array::Conversion conversion)
624{
625    out.print(JSC::DFG::arrayConversionToString(conversion));
626}
627
628} // namespace WTF
629
630#endif // ENABLE(DFG_JIT)
631
632