14363dfa3f763b599f3413e1c7ce34754bbb7751
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractValue.h
1 /*
2  * Copyright (C) 2011, 2012, 2013, 2014 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 #ifndef DFGAbstractValue_h
27 #define DFGAbstractValue_h
28
29 #if ENABLE(DFG_JIT)
30
31 #include "ArrayProfile.h"
32 #include "DFGFiltrationResult.h"
33 #include "DFGNodeFlags.h"
34 #include "DFGStructureAbstractValue.h"
35 #include "JSCell.h"
36 #include "SpeculatedType.h"
37 #include "DumpContext.h"
38 #include "StructureSet.h"
39
40 namespace JSC { namespace DFG {
41
42 class Graph;
43 struct Node;
44
45 struct AbstractValue {
46     AbstractValue()
47         : m_type(SpecNone)
48         , m_arrayModes(0)
49     {
50     }
51     
52     void clear()
53     {
54         m_type = SpecNone;
55         m_arrayModes = 0;
56         m_currentKnownStructure.clear();
57         m_futurePossibleStructure.clear();
58         m_value = JSValue();
59         checkConsistency();
60     }
61     
62     bool isClear() const { return m_type == SpecNone; }
63     bool operator!() const { return isClear(); }
64     
65     void makeHeapTop()
66     {
67         makeTop(SpecHeapTop);
68     }
69     
70     void makeBytecodeTop()
71     {
72         makeTop(SpecBytecodeTop);
73     }
74     
75     void clobberStructures()
76     {
77         if (m_type & SpecCell) {
78             m_currentKnownStructure.makeTop();
79             clobberArrayModes();
80         } else {
81             ASSERT(m_currentKnownStructure.isClear());
82             ASSERT(!m_arrayModes);
83         }
84         checkConsistency();
85     }
86         
87     void clobberValue()
88     {
89         m_value = JSValue();
90     }
91     
92     bool isHeapTop() const
93     {
94         return (m_type | SpecHeapTop) == m_type && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop();
95     }
96     
97     bool valueIsTop() const
98     {
99         return !m_value && m_type;
100     }
101     
102     JSValue value() const
103     {
104         return m_value;
105     }
106     
107     static AbstractValue heapTop()
108     {
109         AbstractValue result;
110         result.makeHeapTop();
111         return result;
112     }
113     
114     void setMostSpecific(Graph&, JSValue);
115     void set(Graph&, JSValue);
116     void set(Graph&, Structure*);
117     
118     void setType(SpeculatedType type)
119     {
120         if (type & SpecCell) {
121             m_currentKnownStructure.makeTop();
122             m_futurePossibleStructure.makeTop();
123             m_arrayModes = ALL_ARRAY_MODES;
124         } else {
125             m_currentKnownStructure.clear();
126             m_futurePossibleStructure.clear();
127             m_arrayModes = 0;
128         }
129         m_type = type;
130         m_value = JSValue();
131         checkConsistency();
132     }
133     
134     void fixTypeForRepresentation(NodeFlags representation);
135     void fixTypeForRepresentation(Node*);
136     
137     bool operator==(const AbstractValue& other) const
138     {
139         return m_type == other.m_type
140             && m_arrayModes == other.m_arrayModes
141             && m_currentKnownStructure == other.m_currentKnownStructure
142             && m_futurePossibleStructure == other.m_futurePossibleStructure
143             && m_value == other.m_value;
144     }
145     bool operator!=(const AbstractValue& other) const
146     {
147         return !(*this == other);
148     }
149     
150     bool merge(const AbstractValue& other)
151     {
152         if (other.isClear())
153             return false;
154         
155 #if !ASSERT_DISABLED
156         AbstractValue oldMe = *this;
157 #endif
158         bool result = false;
159         if (isClear()) {
160             *this = other;
161             result = !other.isClear();
162         } else {
163             result |= mergeSpeculation(m_type, other.m_type);
164             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
165             result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure);
166             result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure);
167             if (m_value != other.m_value) {
168                 result |= !!m_value;
169                 m_value = JSValue();
170             }
171         }
172         checkConsistency();
173         ASSERT(result == (*this != oldMe));
174         return result;
175     }
176     
177     void merge(SpeculatedType type)
178     {
179         mergeSpeculation(m_type, type);
180         
181         if (type & SpecCell) {
182             m_currentKnownStructure.makeTop();
183             m_futurePossibleStructure.makeTop();
184             m_arrayModes = ALL_ARRAY_MODES;
185         }
186         m_value = JSValue();
187
188         checkConsistency();
189     }
190     
191     bool couldBeType(SpeculatedType desiredType)
192     {
193         return !!(m_type & desiredType);
194     }
195     
196     bool isType(SpeculatedType desiredType)
197     {
198         return !(m_type & ~desiredType);
199     }
200     
201     FiltrationResult filter(Graph&, const StructureSet&);
202     
203     FiltrationResult filterArrayModes(ArrayModes);
204     
205     FiltrationResult filter(SpeculatedType);
206     
207     FiltrationResult filterByValue(JSValue);
208     
209     bool validate(JSValue value) const
210     {
211         if (isHeapTop())
212             return true;
213         
214         if (!!m_value && m_value != value)
215             return false;
216         
217         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
218             return false;
219         
220         if (value.isEmpty()) {
221             ASSERT(m_type & SpecEmpty);
222             return true;
223         }
224         
225         if (!!value && value.isCell()) {
226             ASSERT(m_type & SpecCell);
227             Structure* structure = value.asCell()->structure();
228             return m_currentKnownStructure.contains(structure)
229                 && m_futurePossibleStructure.contains(structure)
230                 && (m_arrayModes & asArrayModes(structure->indexingType()));
231         }
232         
233         return true;
234     }
235     
236     Structure* bestProvenStructure() const
237     {
238         if (m_currentKnownStructure.hasSingleton())
239             return m_currentKnownStructure.singleton();
240         if (m_futurePossibleStructure.hasSingleton())
241             return m_futurePossibleStructure.singleton();
242         return 0;
243     }
244     
245     bool hasClobberableState() const
246     {
247         return m_currentKnownStructure.isNeitherClearNorTop()
248             || !arrayModesAreClearOrTop(m_arrayModes);
249     }
250     
251 #if ASSERT_DISABLED
252     void checkConsistency() const { }
253 #else
254     void checkConsistency() const;
255 #endif
256     
257     void dumpInContext(PrintStream&, DumpContext*) const;
258     void dump(PrintStream&) const;
259     
260     // A great way to think about the difference between m_currentKnownStructure and
261     // m_futurePossibleStructure is to consider these four examples:
262     //
263     // 1) x = foo();
264     //
265     //    In this case x's m_currentKnownStructure and m_futurePossibleStructure will
266     //    both be TOP, since we don't know anything about x for sure, yet.
267     //
268     // 2) x = foo();
269     //    y = x.f;
270     //
271     //    Where x will later have a new property added to it, 'g'. Because of the
272     //    known but not-yet-executed property addition, x's current structure will
273     //    not be watchpointable; hence we have no way of statically bounding the set
274     //    of possible structures that x may have if a clobbering event happens. So,
275     //    x's m_currentKnownStructure will be whatever structure we check to get
276     //    property 'f', and m_futurePossibleStructure will be TOP.
277     //
278     // 3) x = foo();
279     //    y = x.f;
280     //
281     //    Where x has a terminal structure that is still watchpointable. In this case,
282     //    x's m_currentKnownStructure and m_futurePossibleStructure will both be
283     //    whatever structure we checked for when getting 'f'.
284     //
285     // 4) x = foo();
286     //    y = x.f;
287     //    bar();
288     //
289     //    Where x has a terminal structure that is still watchpointable. In this
290     //    case, m_currentKnownStructure will be TOP because bar() may potentially
291     //    change x's structure and we have no way of proving otherwise, but
292     //    x's m_futurePossibleStructure will be whatever structure we had checked
293     //    when getting property 'f'.
294     
295     // NB. All fields in this struct must have trivial destructors.
296
297     // This is a proven constraint on the structures that this value can have right
298     // now. The structure of the current value must belong to this set. The set may
299     // be TOP, indicating that it is the set of all possible structures, in which
300     // case the current value can have any structure. The set may be BOTTOM (empty)
301     // in which case this value cannot be a cell. This is all subject to change
302     // anytime a new value is assigned to this one, anytime there is a control flow
303     // merge, or most crucially, anytime a side-effect or structure check happens.
304     // In case of a side-effect, we typically must assume that any value may have
305     // had its structure changed, hence contravening our proof. We make the proof
306     // valid again by switching this to TOP (i.e. claiming that we have proved that
307     // this value may have any structure). Of note is that the proof represented by
308     // this field is not subject to structure transition watchpoints - even if one
309     // fires, we can be sure that this proof is still valid.
310     StructureAbstractValue m_currentKnownStructure;
311     
312     // This is a proven constraint on the structures that this value can have now
313     // or any time in the future subject to the structure transition watchpoints of
314     // all members of this set not having fired. This set is impervious to side-
315     // effects; even if one happens the side-effect can only cause the value to
316     // change to at worst another structure that is also a member of this set. But,
317     // the theorem being proved by this field is predicated upon there not being
318     // any new structure transitions introduced into any members of this set. In
319     // cases where there is no way for us to guard this happening, the set must be
320     // TOP. But in cases where we can guard new structure transitions (all members
321     // of the set have still-valid structure transition watchpoints) then this set
322     // will be finite. Anytime that we make use of the finite nature of this set,
323     // we must first issue a structure transition watchpoint, which will effectively
324     // result in m_currentKnownStructure being filtered according to
325     // m_futurePossibleStructure.
326     StructureAbstractValue m_futurePossibleStructure;
327     
328     // This is a proven constraint on the possible types that this value can have
329     // now or any time in the future, unless it is reassigned. This field is
330     // impervious to side-effects unless the side-effect can reassign the value
331     // (for example if we're talking about a captured variable). The relationship
332     // between this field, and the structure fields above, is as follows. The
333     // fields above constraint the structures that a cell may have, but they say
334     // nothing about whether or not the value is known to be a cell. More formally,
335     // the m_currentKnownStructure is itself an abstract value that consists of the
336     // union of the set of all non-cell values and the set of cell values that have
337     // the given structure. This abstract value is then the intersection of the
338     // m_currentKnownStructure and the set of values whose type is m_type. So, for
339     // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is
340     // [0x12345] then this abstract value corresponds to the set of all integers
341     // unified with the set of all objects with structure 0x12345.
342     SpeculatedType m_type;
343     
344     // This is a proven constraint on the possible indexing types that this value
345     // can have right now. It also implicitly constraints the set of structures
346     // that the value may have right now, since a structure has an immutable
347     // indexing type. This is subject to change upon reassignment, or any side
348     // effect that makes non-obvious changes to the heap.
349     ArrayModes m_arrayModes;
350     
351     // This is a proven constraint on the possible values that this value can
352     // have now or any time in the future, unless it is reassigned. Note that this
353     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
354     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
355     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
356     // means TOP.
357     JSValue m_value;
358
359 private:
360     void clobberArrayModes()
361     {
362         // FIXME: We could make this try to predict the set of array modes that this object
363         // could have in the future. For now, just do the simple thing.
364         m_arrayModes = ALL_ARRAY_MODES;
365     }
366     
367     bool validateType(JSValue value) const
368     {
369         if (isHeapTop())
370             return true;
371         
372         // Constant folding always represents Int52's in a double (i.e. Int52AsDouble).
373         // So speculationFromValue(value) for an Int52 value will return Int52AsDouble,
374         // and that's fine - the type validates just fine.
375         SpeculatedType type = m_type;
376         if (type & SpecInt52)
377             type |= SpecInt52AsDouble;
378         
379         if (mergeSpeculations(type, speculationFromValue(value)) != type)
380             return false;
381         
382         if (value.isEmpty()) {
383             ASSERT(m_type & SpecEmpty);
384             return true;
385         }
386         
387         return true;
388     }
389     
390     void makeTop(SpeculatedType top)
391     {
392         m_type |= top;
393         m_arrayModes = ALL_ARRAY_MODES;
394         m_currentKnownStructure.makeTop();
395         m_futurePossibleStructure.makeTop();
396         m_value = JSValue();
397         checkConsistency();
398     }
399     
400     void setFuturePossibleStructure(Graph&, Structure*);
401
402     void filterValueByType();
403     void filterArrayModesByType();
404     
405     bool shouldBeClear() const;
406     FiltrationResult normalizeClarity();
407 };
408
409 } } // namespace JSC::DFG
410
411 #endif // ENABLE(DFG_JIT)
412
413 #endif // DFGAbstractValue_h
414
415