a4902534263dfb88c3d2750f768e3f0cd093c523
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractValue.h
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
43 namespace JSC {
44
45 class TrackedReferences;
46
47 namespace DFG {
48
49 class Graph;
50 struct Node;
51
52 struct 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 valueIsTop() const
193     {
194         return !m_value && m_type;
195     }
196     
197     JSValue value() const
198     {
199         return m_value;
200     }
201     
202     static AbstractValue heapTop()
203     {
204         AbstractValue result;
205         result.makeHeapTop();
206         return result;
207     }
208     
209     static AbstractValue bytecodeTop()
210     {
211         AbstractValue result;
212         result.makeBytecodeTop();
213         return result;
214     }
215     
216     static AbstractValue fullTop()
217     {
218         AbstractValue result;
219         result.makeFullTop();
220         return result;
221     }
222     
223     void set(Graph&, const AbstractValue& other)
224     {
225         *this = other;
226     }
227     
228     void set(Graph&, AbstractValue&& other)
229     {
230         *this = WTFMove(other);
231     }
232     
233     void set(Graph&, const FrozenValue&, StructureClobberState);
234     void set(Graph&, Structure*);
235     void set(Graph&, RegisteredStructure);
236     void set(Graph&, const RegisteredStructureSet&);
237     
238     // Set this value to represent the given set of types as precisely as possible.
239     void setType(Graph&, SpeculatedType);
240     
241     // As above, but only valid for non-cell types.
242     ALWAYS_INLINE void setNonCellType(SpeculatedType type)
243     {
244         RELEASE_ASSERT(!(type & SpecCell));
245         m_structure.clear();
246         m_arrayModes = 0;
247         m_type = type;
248         m_value = JSValue();
249         checkConsistency();
250     }
251
252     void fixTypeForRepresentation(Graph&, NodeFlags representation, Node* = nullptr);
253     void fixTypeForRepresentation(Graph&, Node*);
254     
255     bool operator==(const AbstractValue& other) const
256     {
257         return m_type == other.m_type
258             && m_arrayModes == other.m_arrayModes
259             && m_structure == other.m_structure
260             && m_value == other.m_value;
261     }
262     bool operator!=(const AbstractValue& other) const
263     {
264         return !(*this == other);
265     }
266     
267     ALWAYS_INLINE bool merge(const AbstractValue& other)
268     {
269         if (other.isClear())
270             return false;
271         
272 #if !ASSERT_DISABLED
273         AbstractValue oldMe = *this;
274 #endif
275         bool result = false;
276         if (isClear()) {
277             *this = other;
278             result = !other.isClear();
279         } else {
280             result |= mergeSpeculation(m_type, other.m_type);
281             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
282             result |= m_structure.merge(other.m_structure);
283             if (m_value != other.m_value) {
284                 result |= !!m_value;
285                 m_value = JSValue();
286             }
287         }
288         checkConsistency();
289         ASSERT(result == (*this != oldMe));
290         return result;
291     }
292     
293     bool mergeOSREntryValue(Graph&, JSValue);
294     
295     void merge(SpeculatedType type)
296     {
297         mergeSpeculation(m_type, type);
298         
299         if (type & SpecCell) {
300             m_structure.makeTop();
301             m_arrayModes = ALL_ARRAY_MODES;
302         }
303         m_value = JSValue();
304
305         checkConsistency();
306     }
307     
308     bool couldBeType(SpeculatedType desiredType) const
309     {
310         return !!(m_type & desiredType);
311     }
312     
313     bool isType(SpeculatedType desiredType) const
314     {
315         return !(m_type & ~desiredType);
316     }
317
318     // Filters the value using the given structure set. If the admittedTypes argument is not passed, this
319     // implicitly filters by the types implied by the structure set, which are usually a subset of
320     // SpecCell. Hence, after this call, the value will no longer have any non-cell members. But, you can
321     // use admittedTypes to preserve some non-cell types. Note that it's wrong for admittedTypes to overlap
322     // with SpecCell.
323     FiltrationResult filter(Graph&, const RegisteredStructureSet&, SpeculatedType admittedTypes = SpecNone);
324     
325     FiltrationResult filterArrayModes(ArrayModes);
326
327     ALWAYS_INLINE FiltrationResult filter(SpeculatedType type)
328     {
329         if ((m_type & type) == m_type)
330             return FiltrationOK;
331     
332         // Fast path for the case that we don't even have a cell.
333         if (!(m_type & SpecCell)) {
334             m_type &= type;
335             FiltrationResult result;
336             if (m_type == SpecNone) {
337                 clear();
338                 result = Contradiction;
339             } else
340                 result = FiltrationOK;
341             checkConsistency();
342             return result;
343         }
344         
345         return filterSlow(type);
346     }
347     
348     FiltrationResult filterByValue(const FrozenValue& value);
349     FiltrationResult filter(const AbstractValue&);
350     FiltrationResult filterClassInfo(Graph&, const ClassInfo*);
351
352     ALWAYS_INLINE FiltrationResult fastForwardToAndFilterUnproven(AbstractValueClobberEpoch newEpoch, SpeculatedType type)
353     {
354         if (m_type & SpecCell)
355             return fastForwardToAndFilterSlow(newEpoch, type);
356         
357         m_effectEpoch = newEpoch;
358         m_type &= type;
359         FiltrationResult result;
360         if (m_type == SpecNone) {
361             clear();
362             result = Contradiction;
363         } else
364             result = FiltrationOK;
365         checkConsistency();
366         return result;
367     }
368
369     FiltrationResult changeStructure(Graph&, const RegisteredStructureSet&);
370     
371     bool contains(RegisteredStructure) const;
372
373     bool validateOSREntryValue(JSValue value, FlushFormat format) const
374     {
375         if (isHeapTop())
376             return true;
377         
378         if (!!m_value && m_value != value)
379             return false;
380         
381         if (format == FlushedInt52) {
382             if (!validateTypeAcceptingBoxedInt52(value))
383                 return false;
384         } else {
385             if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
386                 return false;
387             
388             if (value.isEmpty()) {
389                 ASSERT(m_type & SpecEmpty);
390                 return true;
391             }
392         }
393         
394         if (!!value && value.isCell()) {
395             ASSERT(m_type & SpecCell);
396             Structure* structure = value.asCell()->structure();
397             return m_structure.contains(structure)
398                 && (m_arrayModes & arrayModesFromStructure(structure));
399         }
400         
401         return true;
402     }
403     
404     bool hasClobberableState() const
405     {
406         return m_structure.isNeitherClearNorTop()
407             || !arrayModesAreClearOrTop(m_arrayModes);
408     }
409     
410 #if ASSERT_DISABLED
411     void checkConsistency() const { }
412     void assertIsRegistered(Graph&) const { }
413 #else
414     void checkConsistency() const;
415     void assertIsRegistered(Graph&) const;
416 #endif
417
418     ResultType resultType() const;
419
420     void dumpInContext(PrintStream&, DumpContext*) const;
421     void dump(PrintStream&) const;
422     
423     void validateReferences(const TrackedReferences&);
424     
425     // This is a proven constraint on the structures that this value can have right
426     // now. The structure of the current value must belong to this set. The set may
427     // be TOP, indicating that it is the set of all possible structures, in which
428     // case the current value can have any structure. The set may be BOTTOM (empty)
429     // in which case this value cannot be a cell. This is all subject to change
430     // anytime a new value is assigned to this one, anytime there is a control flow
431     // merge, or most crucially, anytime a side-effect or structure check happens.
432     // In case of a side-effect, we must assume that any value with a structure that
433     // isn't being watched may have had its structure changed, hence contravening
434     // our proof. In such a case we make the proof valid again by switching this to
435     // TOP (i.e. claiming that we have proved that this value may have any
436     // structure).
437     StructureAbstractValue m_structure;
438     
439     // This is a proven constraint on the possible types that this value can have
440     // now or any time in the future, unless it is reassigned. This field is
441     // impervious to side-effects. The relationship between this field, and the
442     // structure fields above, is as follows. The fields above constraint the
443     // structures that a cell may have, but they say nothing about whether or not
444     // the value is known to be a cell. More formally, the m_structure is itself an
445     // abstract value that consists of the union of the set of all non-cell values
446     // and the set of cell values that have the given structure. This abstract
447     // value is then the intersection of the m_structure and the set of values
448     // whose type is m_type. So, for example if m_type is SpecFinal|SpecInt32Only and
449     // m_structure is [0x12345] then this abstract value corresponds to the set of
450     // all integers unified with the set of all objects with structure 0x12345.
451     SpeculatedType m_type;
452     
453     // This is a proven constraint on the possible indexing types that this value
454     // can have right now. It also implicitly constraints the set of structures
455     // that the value may have right now, since a structure has an immutable
456     // indexing type. This is subject to change upon reassignment, or any side
457     // effect that makes non-obvious changes to the heap.
458     ArrayModes m_arrayModes;
459     
460     // The effect epoch is usually ignored. This field is used by InPlaceAbstractState.
461     //
462     // InPlaceAbstractState needs to be able to clobberStructures() for all values it tracks. That
463     // could be a lot of values. So, it makes this operation O(1) by bumping its effect epoch and
464     // calling AbstractValue::fastForwardTo() anytime it vends someone an AbstractValue, which lazily
465     // does clobberStructures(). The epoch type used here (AbstractValueClobberEpoch) is a bit more
466     // complex than the normal Epoch, because it knows how to track clobberStructures() and
467     // observeInvalidationPoint() precisely using integer math.
468     //
469     // One reason why it's here is to steal the 32-bit hole between m_arrayModes and m_value on
470     // 64-bit systems.
471     AbstractValueClobberEpoch m_effectEpoch;
472     
473     // This is a proven constraint on the possible values that this value can
474     // have now or any time in the future, unless it is reassigned. Note that this
475     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
476     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
477     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
478     // means TOP. Also note that this value isn't necessarily known to the GC
479     // (strongly or even weakly - it may be an "fragile" value, see
480     // DFGValueStrength.h). If you perform any optimization based on a cell m_value
481     // that requires that the value be kept alive, you must call freeze() on that
482     // value, which will turn it into a weak value.
483     JSValue m_value;
484
485 private:
486     void clobberArrayModes()
487     {
488         // FIXME: We could make this try to predict the set of array modes that this object
489         // could have in the future. For now, just do the simple thing.
490         m_arrayModes = ALL_ARRAY_MODES;
491     }
492     
493     void observeIndexingTypeTransition(ArrayModes from, ArrayModes to)
494     {
495         if (m_arrayModes & from)
496             m_arrayModes |= to;
497     }
498     
499     bool validateTypeAcceptingBoxedInt52(JSValue value) const
500     {
501         if (isHeapTop())
502             return true;
503         
504         // Constant folding always represents Int52's in a double (i.e. AnyIntAsDouble).
505         // So speculationFromValue(value) for an Int52 value will return AnyIntAsDouble,
506         // and that's fine - the type validates just fine.
507         SpeculatedType type = m_type;
508         if (type & SpecInt52Only)
509             type |= SpecAnyIntAsDouble;
510         
511         if (mergeSpeculations(type, speculationFromValue(value)) != type)
512             return false;
513         
514         if (value.isEmpty()) {
515             ASSERT(m_type & SpecEmpty);
516             return true;
517         }
518         
519         return true;
520     }
521     
522     void makeTop(SpeculatedType top)
523     {
524         m_type = top;
525         m_arrayModes = ALL_ARRAY_MODES;
526         m_structure.makeTop();
527         m_value = JSValue();
528         checkConsistency();
529     }
530     
531     void fastForwardToSlow(AbstractValueClobberEpoch);
532     FiltrationResult filterSlow(SpeculatedType);
533     FiltrationResult fastForwardToAndFilterSlow(AbstractValueClobberEpoch, SpeculatedType);
534     
535     void filterValueByType();
536     void filterArrayModesByType();
537
538 #if USE(JSVALUE64) && !defined(NDEBUG)
539     void ensureCanInitializeWithZeros();
540 #endif
541     
542     bool shouldBeClear() const;
543     FiltrationResult normalizeClarity();
544     FiltrationResult normalizeClarity(Graph&);
545 };
546
547 } } // namespace JSC::DFG
548
549 #if USE(JSVALUE64)
550 namespace WTF {
551 template <>
552 struct VectorTraits<JSC::DFG::AbstractValue> : VectorTraitsBase<false, JSC::DFG::AbstractValue> {
553     static const bool canInitializeWithMemset = true;
554 };
555
556 template <>
557 struct HashTraits<JSC::DFG::AbstractValue> : GenericHashTraits<JSC::DFG::AbstractValue> {
558     static const bool emptyValueIsZero = true;
559 };
560 };
561 #endif // USE(JSVALUE64)
562
563 #endif // ENABLE(DFG_JIT)