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