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