1/*
2 * Copyright (C) 2012-2018 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#include "ConcurrentJSLock.h"
29#include "Structure.h"
30
31namespace JSC {
32
33class CodeBlock;
34class LLIntOffsetsExtractor;
35
36// This is a bitfield where each bit represents an type of array access that we have seen.
37// There are 19 indexing types that use the lower bits.
38// There are 9 typed array types taking the bits 16 to 25.
39typedef unsigned ArrayModes;
40
41// The possible IndexingTypes are limited within (0 - 16, 21, 23, 25).
42// This is because CoW types only appear for JSArrays.
43static_assert(CopyOnWriteArrayWithInt32 == 21, "");
44static_assert(CopyOnWriteArrayWithDouble == 23, "");
45static_assert(CopyOnWriteArrayWithContiguous == 25, "");
46const ArrayModes CopyOnWriteArrayWithInt32ArrayMode = 1 << CopyOnWriteArrayWithInt32;
47const ArrayModes CopyOnWriteArrayWithDoubleArrayMode = 1 << CopyOnWriteArrayWithDouble;
48const ArrayModes CopyOnWriteArrayWithContiguousArrayMode = 1 << CopyOnWriteArrayWithContiguous;
49
50const ArrayModes Int8ArrayMode = 1 << 16;
51const ArrayModes Int16ArrayMode = 1 << 17;
52const ArrayModes Int32ArrayMode = 1 << 18;
53const ArrayModes Uint8ArrayMode = 1 << 19;
54const ArrayModes Uint8ClampedArrayMode = 1 << 20; // 21 - 25 are used for CoW arrays.
55const ArrayModes Uint16ArrayMode = 1 << 26;
56const ArrayModes Uint32ArrayMode = 1 << 27;
57const ArrayModes Float32ArrayMode = 1 << 28;
58const ArrayModes Float64ArrayMode = 1 << 29;
59
60JS_EXPORT_PRIVATE extern const ArrayModes typedArrayModes[NumberOfTypedArrayTypesExcludingDataView];
61
62constexpr ArrayModes asArrayModesIgnoringTypedArrays(IndexingType indexingMode)
63{
64 return static_cast<unsigned>(1) << static_cast<unsigned>(indexingMode);
65}
66
67#define ALL_TYPED_ARRAY_MODES \
68 (Int8ArrayMode \
69 | Int16ArrayMode \
70 | Int32ArrayMode \
71 | Uint8ArrayMode \
72 | Uint8ClampedArrayMode \
73 | Uint16ArrayMode \
74 | Uint32ArrayMode \
75 | Float32ArrayMode \
76 | Float64ArrayMode \
77 )
78
79#define ALL_NON_ARRAY_ARRAY_MODES \
80 (asArrayModesIgnoringTypedArrays(NonArray) \
81 | asArrayModesIgnoringTypedArrays(NonArrayWithInt32) \
82 | asArrayModesIgnoringTypedArrays(NonArrayWithDouble) \
83 | asArrayModesIgnoringTypedArrays(NonArrayWithContiguous) \
84 | asArrayModesIgnoringTypedArrays(NonArrayWithArrayStorage) \
85 | asArrayModesIgnoringTypedArrays(NonArrayWithSlowPutArrayStorage) \
86 | ALL_TYPED_ARRAY_MODES)
87
88#define ALL_COPY_ON_WRITE_ARRAY_MODES \
89 (CopyOnWriteArrayWithInt32ArrayMode \
90 | CopyOnWriteArrayWithDoubleArrayMode \
91 | CopyOnWriteArrayWithContiguousArrayMode)
92
93#define ALL_WRITABLE_ARRAY_ARRAY_MODES \
94 (asArrayModesIgnoringTypedArrays(ArrayClass) \
95 | asArrayModesIgnoringTypedArrays(ArrayWithUndecided) \
96 | asArrayModesIgnoringTypedArrays(ArrayWithInt32) \
97 | asArrayModesIgnoringTypedArrays(ArrayWithDouble) \
98 | asArrayModesIgnoringTypedArrays(ArrayWithContiguous) \
99 | asArrayModesIgnoringTypedArrays(ArrayWithArrayStorage) \
100 | asArrayModesIgnoringTypedArrays(ArrayWithSlowPutArrayStorage))
101
102#define ALL_ARRAY_ARRAY_MODES \
103 (ALL_WRITABLE_ARRAY_ARRAY_MODES \
104 | ALL_COPY_ON_WRITE_ARRAY_MODES)
105
106#define ALL_ARRAY_MODES (ALL_NON_ARRAY_ARRAY_MODES | ALL_ARRAY_ARRAY_MODES)
107
108inline ArrayModes arrayModesFromStructure(Structure* structure)
109{
110 JSType type = structure->typeInfo().type();
111 if (isTypedArrayType(type))
112 return typedArrayModes[type - FirstTypedArrayType];
113 return asArrayModesIgnoringTypedArrays(structure->indexingMode());
114}
115
116void dumpArrayModes(PrintStream&, ArrayModes);
117MAKE_PRINT_ADAPTOR(ArrayModesDump, ArrayModes, dumpArrayModes);
118
119inline bool mergeArrayModes(ArrayModes& left, ArrayModes right)
120{
121 ArrayModes newModes = left | right;
122 if (newModes == left)
123 return false;
124 left = newModes;
125 return true;
126}
127
128inline bool arrayModesAreClearOrTop(ArrayModes modes)
129{
130 return !modes || modes == ALL_ARRAY_MODES;
131}
132
133// Checks if proven is a subset of expected.
134inline bool arrayModesAlreadyChecked(ArrayModes proven, ArrayModes expected)
135{
136 return (expected | proven) == expected;
137}
138
139inline bool arrayModesIncludeIgnoringTypedArrays(ArrayModes arrayModes, IndexingType shape)
140{
141 ArrayModes modes = asArrayModesIgnoringTypedArrays(NonArray | shape) | asArrayModesIgnoringTypedArrays(ArrayClass | shape);
142 if (hasInt32(shape) || hasDouble(shape) || hasContiguous(shape))
143 modes |= asArrayModesIgnoringTypedArrays(ArrayClass | shape | CopyOnWrite);
144 return !!(arrayModes & modes);
145}
146
147inline bool shouldUseSlowPutArrayStorage(ArrayModes arrayModes)
148{
149 return arrayModesIncludeIgnoringTypedArrays(arrayModes, SlowPutArrayStorageShape);
150}
151
152inline bool shouldUseFastArrayStorage(ArrayModes arrayModes)
153{
154 return arrayModesIncludeIgnoringTypedArrays(arrayModes, ArrayStorageShape);
155}
156
157inline bool shouldUseContiguous(ArrayModes arrayModes)
158{
159 return arrayModesIncludeIgnoringTypedArrays(arrayModes, ContiguousShape);
160}
161
162inline bool shouldUseDouble(ArrayModes arrayModes)
163{
164 return arrayModesIncludeIgnoringTypedArrays(arrayModes, DoubleShape);
165}
166
167inline bool shouldUseInt32(ArrayModes arrayModes)
168{
169 return arrayModesIncludeIgnoringTypedArrays(arrayModes, Int32Shape);
170}
171
172inline bool hasSeenArray(ArrayModes arrayModes)
173{
174 return arrayModes & ALL_ARRAY_ARRAY_MODES;
175}
176
177inline bool hasSeenNonArray(ArrayModes arrayModes)
178{
179 return arrayModes & ALL_NON_ARRAY_ARRAY_MODES;
180}
181
182inline bool hasSeenWritableArray(ArrayModes arrayModes)
183{
184 return arrayModes & ALL_WRITABLE_ARRAY_ARRAY_MODES;
185}
186
187inline bool hasSeenCopyOnWriteArray(ArrayModes arrayModes)
188{
189 return arrayModes & ALL_COPY_ON_WRITE_ARRAY_MODES;
190}
191
192class ArrayProfile {
193 friend class CodeBlock;
194
195public:
196 explicit ArrayProfile()
197 : m_mayInterceptIndexedAccesses(false)
198 , m_usesOriginalArrayStructures(true)
199 , m_didPerformFirstRunPruning(false)
200 {
201 }
202
203 StructureID* addressOfLastSeenStructureID() { return &m_lastSeenStructureID; }
204 ArrayModes* addressOfArrayModes() { return &m_observedArrayModes; }
205 bool* addressOfMayStoreToHole() { return &m_mayStoreToHole; }
206
207 void setOutOfBounds() { m_outOfBounds = true; }
208 bool* addressOfOutOfBounds() { return &m_outOfBounds; }
209
210 void observeStructure(Structure* structure)
211 {
212 m_lastSeenStructureID = structure->id();
213 }
214
215 void computeUpdatedPrediction(const ConcurrentJSLocker&, CodeBlock*);
216 void computeUpdatedPrediction(const ConcurrentJSLocker&, CodeBlock*, Structure* lastSeenStructure);
217
218 void observeArrayMode(ArrayModes mode) { m_observedArrayModes |= mode; }
219 void observeIndexedRead(VM&, JSCell*, unsigned index);
220
221 ArrayModes observedArrayModes(const ConcurrentJSLocker&) const { return m_observedArrayModes; }
222 bool mayInterceptIndexedAccesses(const ConcurrentJSLocker&) const { return m_mayInterceptIndexedAccesses; }
223
224 bool mayStoreToHole(const ConcurrentJSLocker&) const { return m_mayStoreToHole; }
225 bool outOfBounds(const ConcurrentJSLocker&) const { return m_outOfBounds; }
226
227 bool usesOriginalArrayStructures(const ConcurrentJSLocker&) const { return m_usesOriginalArrayStructures; }
228
229 CString briefDescription(const ConcurrentJSLocker&, CodeBlock*);
230 CString briefDescriptionWithoutUpdating(const ConcurrentJSLocker&);
231
232private:
233 friend class LLIntOffsetsExtractor;
234
235 static Structure* polymorphicStructure() { return static_cast<Structure*>(reinterpret_cast<void*>(1)); }
236
237 StructureID m_lastSeenStructureID { 0 };
238 bool m_mayStoreToHole { false }; // This flag may become overloaded to indicate other special cases that were encountered during array access, as it depends on indexing type. Since we currently have basically just one indexing type (two variants of ArrayStorage), this flag for now just means exactly what its name implies.
239 bool m_outOfBounds { false };
240 bool m_mayInterceptIndexedAccesses : 1;
241 bool m_usesOriginalArrayStructures : 1;
242 bool m_didPerformFirstRunPruning : 1;
243 ArrayModes m_observedArrayModes { 0 };
244};
245static_assert(sizeof(ArrayProfile) == 12);
246
247} // namespace JSC
248