1/*
2 * Copyright (C) 2011-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#if ENABLE(DFG_JIT)
29
30#include "ArrayProfile.h"
31#include "DFGAbstractValueClobberEpoch.h"
32#include "DFGFiltrationResult.h"
33#include "DFGFlushFormat.h"
34#include "DFGFrozenValue.h"
35#include "DFGNodeFlags.h"
36#include "DFGStructureAbstractValue.h"
37#include "DFGStructureClobberState.h"
38#include "JSCast.h"
39#include "ResultType.h"
40#include "SpeculatedType.h"
41#include "DumpContext.h"
42
43namespace JSC {
44
45class TrackedReferences;
46
47namespace DFG {
48
49class Graph;
50struct Node;
51class VariableAccessData;
52
53struct AbstractValue {
54 AbstractValue()
55 : m_type(SpecNone)
56 , m_arrayModes(0)
57 {
58#if USE(JSVALUE64) && !defined(NDEBUG)
59 // The WTF Traits for AbstractValue allow the initialization of values with bzero().
60 // We verify the correctness of this assumption here.
61 static bool needsDefaultConstructorCheck = true;
62 if (needsDefaultConstructorCheck) {
63 needsDefaultConstructorCheck = false;
64 ensureCanInitializeWithZeros();
65 }
66#endif
67 }
68
69 void clear()
70 {
71 m_type = SpecNone;
72 m_arrayModes = 0;
73 m_structure.clear();
74 m_value = JSValue();
75 checkConsistency();
76 }
77
78 bool isClear() const { return m_type == SpecNone; }
79 bool operator!() const { return isClear(); }
80
81 void makeHeapTop()
82 {
83 makeTop(SpecHeapTop);
84 }
85
86 void makeBytecodeTop()
87 {
88 makeTop(SpecBytecodeTop);
89 }
90
91 void makeFullTop()
92 {
93 makeTop(SpecFullTop);
94 }
95
96 void clobberStructures()
97 {
98 if (m_type & SpecCell) {
99 m_structure.clobber();
100 clobberArrayModes();
101 } else {
102 ASSERT(m_structure.isClear());
103 ASSERT(!m_arrayModes);
104 }
105 checkConsistency();
106 }
107
108 ALWAYS_INLINE void fastForwardFromTo(AbstractValueClobberEpoch oldEpoch, AbstractValueClobberEpoch newEpoch)
109 {
110 if (newEpoch == oldEpoch)
111 return;
112
113 if (!(m_type & SpecCell))
114 return;
115
116 if (newEpoch.clobberEpoch() != oldEpoch.clobberEpoch())
117 clobberStructures();
118 if (newEpoch.structureClobberState() == StructuresAreWatched)
119 m_structure.observeInvalidationPoint();
120
121 checkConsistency();
122 }
123
124 ALWAYS_INLINE void fastForwardTo(AbstractValueClobberEpoch newEpoch)
125 {
126 if (newEpoch == m_effectEpoch)
127 return;
128
129 if (!(m_type & SpecCell)) {
130 m_effectEpoch = newEpoch;
131 return;
132 }
133
134 fastForwardToSlow(newEpoch);
135 }
136
137 void observeTransition(RegisteredStructure from, RegisteredStructure to)
138 {
139 if (m_type & SpecCell) {
140 m_structure.observeTransition(from, to);
141 observeIndexingTypeTransition(arrayModesFromStructure(from.get()), arrayModesFromStructure(to.get()));
142 }
143 checkConsistency();
144 }
145
146 void observeTransitions(const TransitionVector& vector);
147
148 class TransitionObserver {
149 public:
150 TransitionObserver(RegisteredStructure from, RegisteredStructure to)
151 : m_from(from)
152 , m_to(to)
153 {
154 }
155
156 void operator()(AbstractValue& value)
157 {
158 value.observeTransition(m_from, m_to);
159 }
160 private:
161 RegisteredStructure m_from;
162 RegisteredStructure m_to;
163 };
164
165 class TransitionsObserver {
166 public:
167 TransitionsObserver(const TransitionVector& vector)
168 : m_vector(vector)
169 {
170 }
171
172 void operator()(AbstractValue& value)
173 {
174 value.observeTransitions(m_vector);
175 }
176 private:
177 const TransitionVector& m_vector;
178 };
179
180 void clobberValue()
181 {
182 m_value = JSValue();
183 }
184
185 bool isHeapTop() const
186 {
187 return (m_type | SpecHeapTop) == m_type
188 && m_structure.isTop()
189 && m_arrayModes == ALL_ARRAY_MODES
190 && !m_value;
191 }
192
193 bool isBytecodeTop() const
194 {
195 return (m_type | SpecBytecodeTop) == m_type
196 && m_structure.isTop()
197 && m_arrayModes == ALL_ARRAY_MODES
198 && !m_value;
199 }
200
201 bool valueIsTop() const
202 {
203 return !m_value && m_type;
204 }
205
206 bool isInt52Any() const
207 {
208 return !(m_type & ~SpecInt52Any);
209 }
210
211 JSValue value() const
212 {
213 return m_value;
214 }
215
216 static AbstractValue heapTop()
217 {
218 AbstractValue result;
219 result.makeHeapTop();
220 return result;
221 }
222
223 static AbstractValue bytecodeTop()
224 {
225 AbstractValue result;
226 result.makeBytecodeTop();
227 return result;
228 }
229
230 static AbstractValue fullTop()
231 {
232 AbstractValue result;
233 result.makeFullTop();
234 return result;
235 }
236
237 void set(Graph&, const AbstractValue& other)
238 {
239 *this = other;
240 }
241
242 void set(Graph&, AbstractValue&& other)
243 {
244 *this = WTFMove(other);
245 }
246
247 void set(Graph&, const FrozenValue&, StructureClobberState);
248 void set(Graph&, Structure*);
249 void set(Graph&, RegisteredStructure);
250 void set(Graph&, const RegisteredStructureSet&);
251
252 // Set this value to represent the given set of types as precisely as possible.
253 void setType(Graph&, SpeculatedType);
254
255 // As above, but only valid for non-cell types.
256 ALWAYS_INLINE void setNonCellType(SpeculatedType type)
257 {
258 RELEASE_ASSERT(!(type & SpecCell));
259 m_structure.clear();
260 m_arrayModes = 0;
261 m_type = type;
262 m_value = JSValue();
263 checkConsistency();
264 }
265
266 void fixTypeForRepresentation(Graph&, NodeFlags representation, Node* = nullptr);
267 void fixTypeForRepresentation(Graph&, Node*);
268
269 bool operator==(const AbstractValue& other) const
270 {
271 return m_type == other.m_type
272 && m_arrayModes == other.m_arrayModes
273 && m_structure == other.m_structure
274 && m_value == other.m_value;
275 }
276 bool operator!=(const AbstractValue& other) const
277 {
278 return !(*this == other);
279 }
280
281 ALWAYS_INLINE bool merge(const AbstractValue& other)
282 {
283 if (other.isClear())
284 return false;
285
286#if !ASSERT_DISABLED
287 AbstractValue oldMe = *this;
288#endif
289 bool result = false;
290 if (isClear()) {
291 *this = other;
292 result = !other.isClear();
293 } else {
294 result |= mergeSpeculation(m_type, other.m_type);
295 result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
296 result |= m_structure.merge(other.m_structure);
297 if (m_value != other.m_value) {
298 result |= !!m_value;
299 m_value = JSValue();
300 }
301 }
302 checkConsistency();
303 ASSERT(result == (*this != oldMe));
304 return result;
305 }
306
307 bool mergeOSREntryValue(Graph&, JSValue, VariableAccessData*, Node*);
308
309 void merge(SpeculatedType type)
310 {
311 mergeSpeculation(m_type, type);
312
313 if (type & SpecCell) {
314 m_structure.makeTop();
315 m_arrayModes = ALL_ARRAY_MODES;
316 }
317 m_value = JSValue();
318
319 checkConsistency();
320 }
321
322 bool couldBeType(SpeculatedType desiredType) const
323 {
324 return !!(m_type & desiredType);
325 }
326
327 bool isType(SpeculatedType desiredType) const
328 {
329 return !(m_type & ~desiredType);
330 }
331
332 // Filters the value using the given structure set. If the admittedTypes argument is not passed, this
333 // implicitly filters by the types implied by the structure set, which are usually a subset of
334 // SpecCell. Hence, after this call, the value will no longer have any non-cell members. But, you can
335 // use admittedTypes to preserve some non-cell types. Note that it's wrong for admittedTypes to overlap
336 // with SpecCell.
337 FiltrationResult filter(Graph&, const RegisteredStructureSet&, SpeculatedType admittedTypes = SpecNone);
338
339 FiltrationResult filterArrayModes(ArrayModes);
340
341 ALWAYS_INLINE FiltrationResult filter(SpeculatedType type)
342 {
343 if ((m_type & type) == m_type)
344 return FiltrationOK;
345
346 // Fast path for the case that we don't even have a cell.
347 if (!(m_type & SpecCell)) {
348 m_type &= type;
349 FiltrationResult result;
350 if (m_type == SpecNone) {
351 clear();
352 result = Contradiction;
353 } else
354 result = FiltrationOK;
355 checkConsistency();
356 return result;
357 }
358
359 return filterSlow(type);
360 }
361
362 FiltrationResult filterByValue(const FrozenValue& value);
363 FiltrationResult filter(const AbstractValue&);
364 FiltrationResult filterClassInfo(Graph&, const ClassInfo*);
365
366 ALWAYS_INLINE FiltrationResult fastForwardToAndFilterUnproven(AbstractValueClobberEpoch newEpoch, SpeculatedType type)
367 {
368 if (m_type & SpecCell)
369 return fastForwardToAndFilterSlow(newEpoch, type);
370
371 m_effectEpoch = newEpoch;
372 m_type &= type;
373 FiltrationResult result;
374 if (m_type == SpecNone) {
375 clear();
376 result = Contradiction;
377 } else
378 result = FiltrationOK;
379 checkConsistency();
380 return result;
381 }
382
383 FiltrationResult changeStructure(Graph&, const RegisteredStructureSet&);
384
385 bool contains(RegisteredStructure) const;
386
387 bool validateOSREntryValue(JSValue value, FlushFormat format) const
388 {
389 if (isBytecodeTop())
390 return true;
391
392 if (format == FlushedInt52) {
393 if (!isInt52Any())
394 return false;
395
396 if (!validateTypeAcceptingBoxedInt52(value))
397 return false;
398
399 if (!!m_value) {
400 ASSERT(m_value.isAnyInt());
401 ASSERT(value.isAnyInt());
402 if (jsDoubleNumber(m_value.asAnyInt()) != jsDoubleNumber(value.asAnyInt()))
403 return false;
404 }
405 } else {
406 if (!!m_value && m_value != value)
407 return false;
408
409 if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
410 return false;
411
412 if (value.isEmpty()) {
413 ASSERT(m_type & SpecEmpty);
414 return true;
415 }
416 }
417
418 if (!!value && value.isCell()) {
419 ASSERT(m_type & SpecCell);
420 Structure* structure = value.asCell()->structure();
421 return m_structure.contains(structure)
422 && (m_arrayModes & arrayModesFromStructure(structure));
423 }
424
425 return true;
426 }
427
428 bool hasClobberableState() const
429 {
430 return m_structure.isNeitherClearNorTop()
431 || !arrayModesAreClearOrTop(m_arrayModes);
432 }
433
434#if ASSERT_DISABLED
435 void checkConsistency() const { }
436 void assertIsRegistered(Graph&) const { }
437#else
438 JS_EXPORT_PRIVATE void checkConsistency() const;
439 void assertIsRegistered(Graph&) const;
440#endif
441
442 ResultType resultType() const;
443
444 void dumpInContext(PrintStream&, DumpContext*) const;
445 void dump(PrintStream&) const;
446
447 void validateReferences(const TrackedReferences&);
448
449 // This is a proven constraint on the structures that this value can have right
450 // now. The structure of the current value must belong to this set. The set may
451 // be TOP, indicating that it is the set of all possible structures, in which
452 // case the current value can have any structure. The set may be BOTTOM (empty)
453 // in which case this value cannot be a cell. This is all subject to change
454 // anytime a new value is assigned to this one, anytime there is a control flow
455 // merge, or most crucially, anytime a side-effect or structure check happens.
456 // In case of a side-effect, we must assume that any value with a structure that
457 // isn't being watched may have had its structure changed, hence contravening
458 // our proof. In such a case we make the proof valid again by switching this to
459 // TOP (i.e. claiming that we have proved that this value may have any
460 // structure).
461 StructureAbstractValue m_structure;
462
463 // This is a proven constraint on the possible types that this value can have
464 // now or any time in the future, unless it is reassigned. This field is
465 // impervious to side-effects. The relationship between this field, and the
466 // structure fields above, is as follows. The fields above constraint the
467 // structures that a cell may have, but they say nothing about whether or not
468 // the value is known to be a cell. More formally, the m_structure is itself an
469 // abstract value that consists of the union of the set of all non-cell values
470 // and the set of cell values that have the given structure. This abstract
471 // value is then the intersection of the m_structure and the set of values
472 // whose type is m_type. So, for example if m_type is SpecFinal|SpecInt32Only and
473 // m_structure is [0x12345] then this abstract value corresponds to the set of
474 // all integers unified with the set of all objects with structure 0x12345.
475 SpeculatedType m_type;
476
477 // This is a proven constraint on the possible indexing types that this value
478 // can have right now. It also implicitly constraints the set of structures
479 // that the value may have right now, since a structure has an immutable
480 // indexing type. This is subject to change upon reassignment, or any side
481 // effect that makes non-obvious changes to the heap.
482 ArrayModes m_arrayModes;
483
484 // The effect epoch is usually ignored. This field is used by InPlaceAbstractState.
485 //
486 // InPlaceAbstractState needs to be able to clobberStructures() for all values it tracks. That
487 // could be a lot of values. So, it makes this operation O(1) by bumping its effect epoch and
488 // calling AbstractValue::fastForwardTo() anytime it vends someone an AbstractValue, which lazily
489 // does clobberStructures(). The epoch type used here (AbstractValueClobberEpoch) is a bit more
490 // complex than the normal Epoch, because it knows how to track clobberStructures() and
491 // observeInvalidationPoint() precisely using integer math.
492 //
493 // One reason why it's here is to steal the 32-bit hole between m_arrayModes and m_value on
494 // 64-bit systems.
495 AbstractValueClobberEpoch m_effectEpoch;
496
497 // This is a proven constraint on the possible values that this value can
498 // have now or any time in the future, unless it is reassigned. Note that this
499 // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
500 // means either BOTTOM or TOP depending on the state of m_type: if m_type is
501 // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
502 // means TOP. Also note that this value isn't necessarily known to the GC
503 // (strongly or even weakly - it may be an "fragile" value, see
504 // DFGValueStrength.h). If you perform any optimization based on a cell m_value
505 // that requires that the value be kept alive, you must call freeze() on that
506 // value, which will turn it into a weak value.
507 JSValue m_value;
508
509private:
510 void clobberArrayModes()
511 {
512 // FIXME: We could make this try to predict the set of array modes that this object
513 // could have in the future. For now, just do the simple thing.
514 m_arrayModes = ALL_ARRAY_MODES;
515 }
516
517 void observeIndexingTypeTransition(ArrayModes from, ArrayModes to)
518 {
519 if (m_arrayModes & from)
520 m_arrayModes |= to;
521 }
522
523 bool validateTypeAcceptingBoxedInt52(JSValue value) const
524 {
525 if (isBytecodeTop())
526 return true;
527
528 if (m_type & SpecInt52Any) {
529 if (mergeSpeculations(m_type, int52AwareSpeculationFromValue(value)) == m_type)
530 return true;
531 }
532
533 if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
534 return false;
535
536 return true;
537 }
538
539 void makeTop(SpeculatedType top)
540 {
541 m_type = top;
542 m_arrayModes = ALL_ARRAY_MODES;
543 m_structure.makeTop();
544 m_value = JSValue();
545 checkConsistency();
546 }
547
548 void fastForwardToSlow(AbstractValueClobberEpoch);
549 FiltrationResult filterSlow(SpeculatedType);
550 FiltrationResult fastForwardToAndFilterSlow(AbstractValueClobberEpoch, SpeculatedType);
551
552 void filterValueByType();
553 void filterArrayModesByType();
554
555#if USE(JSVALUE64) && !defined(NDEBUG)
556 JS_EXPORT_PRIVATE void ensureCanInitializeWithZeros();
557#endif
558
559 bool shouldBeClear() const;
560 FiltrationResult normalizeClarity();
561 FiltrationResult normalizeClarity(Graph&);
562};
563
564} } // namespace JSC::DFG
565
566#if USE(JSVALUE64)
567namespace WTF {
568template <>
569struct VectorTraits<JSC::DFG::AbstractValue> : VectorTraitsBase<false, JSC::DFG::AbstractValue> {
570 static const bool canInitializeWithMemset = true;
571};
572
573template <>
574struct HashTraits<JSC::DFG::AbstractValue> : GenericHashTraits<JSC::DFG::AbstractValue> {
575 static const bool emptyValueIsZero = true;
576};
577};
578#endif // USE(JSVALUE64)
579
580#endif // ENABLE(DFG_JIT)
581