Merge r169148, r169185, r169188, r169578, r169582, r169584, r169588, r169753 from...
[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 "DFGStructureClobberState.h"
36 #include "JSCell.h"
37 #include "SpeculatedType.h"
38 #include "DumpContext.h"
39 #include "StructureSet.h"
40
41 namespace JSC { namespace DFG {
42
43 class Graph;
44 struct Node;
45
46 struct AbstractValue {
47     AbstractValue()
48         : m_type(SpecNone)
49         , m_arrayModes(0)
50     {
51     }
52     
53     void clear()
54     {
55         m_type = SpecNone;
56         m_arrayModes = 0;
57         m_structure.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_structure.clobber();
79             clobberArrayModes();
80         } else {
81             ASSERT(m_structure.isClear());
82             ASSERT(!m_arrayModes);
83         }
84         checkConsistency();
85     }
86     
87     static void clobberStructuresFor(AbstractValue& value)
88     {
89         value.clobberStructures();
90     }
91     
92     void observeInvalidationPoint()
93     {
94         m_structure.observeInvalidationPoint();
95         checkConsistency();
96     }
97     
98     static void observeInvalidationPointFor(AbstractValue& value)
99     {
100         value.observeInvalidationPoint();
101     }
102     
103     void observeTransition(Structure* from, Structure* to)
104     {
105         if (m_type & SpecCell) {
106             m_structure.observeTransition(from, to);
107             observeIndexingTypeTransition(from->indexingType(), to->indexingType());
108         }
109         checkConsistency();
110     }
111     
112     void observeTransitions(const TransitionVector& vector);
113     
114     class TransitionObserver {
115     public:
116         TransitionObserver(Structure* from, Structure* to)
117             : m_from(from)
118             , m_to(to)
119         {
120         }
121         
122         void operator()(AbstractValue& value)
123         {
124             value.observeTransition(m_from, m_to);
125         }
126     private:
127         Structure* m_from;
128         Structure* m_to;
129     };
130     
131     class TransitionsObserver {
132     public:
133         TransitionsObserver(const TransitionVector& vector)
134             : m_vector(vector)
135         {
136         }
137         
138         void operator()(AbstractValue& value)
139         {
140             value.observeTransitions(m_vector);
141         }
142     private:
143         const TransitionVector& m_vector;
144     };
145     
146     void clobberValue()
147     {
148         m_value = JSValue();
149     }
150     
151     bool isHeapTop() const
152     {
153         return (m_type | SpecHeapTop) == m_type
154             && m_structure.isTop()
155             && m_arrayModes == ALL_ARRAY_MODES
156             && !m_value;
157     }
158     
159     bool valueIsTop() const
160     {
161         return !m_value && m_type;
162     }
163     
164     JSValue value() const
165     {
166         return m_value;
167     }
168     
169     static AbstractValue heapTop()
170     {
171         AbstractValue result;
172         result.makeHeapTop();
173         return result;
174     }
175     
176     void setMostSpecific(Graph&, JSValue);
177     void set(Graph&, JSValue, StructureClobberState);
178     void set(Graph&, Structure*);
179     void set(Graph&, const StructureSet&);
180     
181     void setType(SpeculatedType type)
182     {
183         if (type & SpecCell) {
184             m_structure.makeTop();
185             m_arrayModes = ALL_ARRAY_MODES;
186         } else {
187             m_structure.clear();
188             m_arrayModes = 0;
189         }
190         m_type = type;
191         m_value = JSValue();
192         checkConsistency();
193     }
194     
195     void fixTypeForRepresentation(NodeFlags representation);
196     void fixTypeForRepresentation(Node*);
197     
198     bool operator==(const AbstractValue& other) const
199     {
200         return m_type == other.m_type
201             && m_arrayModes == other.m_arrayModes
202             && m_structure == other.m_structure
203             && m_value == other.m_value;
204     }
205     bool operator!=(const AbstractValue& other) const
206     {
207         return !(*this == other);
208     }
209     
210     bool merge(const AbstractValue& other)
211     {
212         if (other.isClear())
213             return false;
214         
215 #if !ASSERT_DISABLED
216         AbstractValue oldMe = *this;
217 #endif
218         bool result = false;
219         if (isClear()) {
220             *this = other;
221             result = !other.isClear();
222         } else {
223             result |= mergeSpeculation(m_type, other.m_type);
224             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
225             result |= m_structure.merge(other.m_structure);
226             if (m_value != other.m_value) {
227                 result |= !!m_value;
228                 m_value = JSValue();
229             }
230         }
231         checkConsistency();
232         ASSERT(result == (*this != oldMe));
233         return result;
234     }
235     
236     void merge(SpeculatedType type)
237     {
238         mergeSpeculation(m_type, type);
239         
240         if (type & SpecCell) {
241             m_structure.makeTop();
242             m_arrayModes = ALL_ARRAY_MODES;
243         }
244         m_value = JSValue();
245
246         checkConsistency();
247     }
248     
249     bool couldBeType(SpeculatedType desiredType)
250     {
251         return !!(m_type & desiredType);
252     }
253     
254     bool isType(SpeculatedType desiredType)
255     {
256         return !(m_type & ~desiredType);
257     }
258     
259     FiltrationResult filter(Graph&, const StructureSet&);
260     
261     FiltrationResult filterArrayModes(ArrayModes);
262     
263     FiltrationResult filter(SpeculatedType);
264     
265     FiltrationResult filterByValue(JSValue);
266     
267     bool validate(JSValue value) const
268     {
269         if (isHeapTop())
270             return true;
271         
272         if (!!m_value && m_value != value)
273             return false;
274         
275         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
276             return false;
277         
278         if (value.isEmpty()) {
279             ASSERT(m_type & SpecEmpty);
280             return true;
281         }
282         
283         if (!!value && value.isCell()) {
284             ASSERT(m_type & SpecCell);
285             Structure* structure = value.asCell()->structure();
286             return m_structure.contains(structure)
287                 && (m_arrayModes & asArrayModes(structure->indexingType()));
288         }
289         
290         return true;
291     }
292     
293     bool hasClobberableState() const
294     {
295         return m_structure.isNeitherClearNorTop()
296             || !arrayModesAreClearOrTop(m_arrayModes);
297     }
298     
299 #if ASSERT_DISABLED
300     void checkConsistency() const { }
301     void assertIsWatched(Graph&) const { }
302 #else
303     void checkConsistency() const;
304     void assertIsWatched(Graph&) const;
305 #endif
306     
307     void dumpInContext(PrintStream&, DumpContext*) const;
308     void dump(PrintStream&) const;
309     
310     // This is a proven constraint on the structures that this value can have right
311     // now. The structure of the current value must belong to this set. The set may
312     // be TOP, indicating that it is the set of all possible structures, in which
313     // case the current value can have any structure. The set may be BOTTOM (empty)
314     // in which case this value cannot be a cell. This is all subject to change
315     // anytime a new value is assigned to this one, anytime there is a control flow
316     // merge, or most crucially, anytime a side-effect or structure check happens.
317     // In case of a side-effect, we must assume that any value with a structure that
318     // isn't being watched may have had its structure changed, hence contravening
319     // our proof. In such a case we make the proof valid again by switching this to
320     // TOP (i.e. claiming that we have proved that this value may have any
321     // structure).
322     StructureAbstractValue m_structure;
323     
324     // This is a proven constraint on the possible types that this value can have
325     // now or any time in the future, unless it is reassigned. This field is
326     // impervious to side-effects unless the side-effect can reassign the value
327     // (for example if we're talking about a captured variable). The relationship
328     // between this field, and the structure fields above, is as follows. The
329     // fields above constraint the structures that a cell may have, but they say
330     // nothing about whether or not the value is known to be a cell. More formally,
331     // the m_structure is itself an abstract value that consists of the
332     // union of the set of all non-cell values and the set of cell values that have
333     // the given structure. This abstract value is then the intersection of the
334     // m_structure and the set of values whose type is m_type. So, for
335     // example if m_type is SpecFinal|SpecInt32 and m_structure is
336     // [0x12345] then this abstract value corresponds to the set of all integers
337     // unified with the set of all objects with structure 0x12345.
338     SpeculatedType m_type;
339     
340     // This is a proven constraint on the possible indexing types that this value
341     // can have right now. It also implicitly constraints the set of structures
342     // that the value may have right now, since a structure has an immutable
343     // indexing type. This is subject to change upon reassignment, or any side
344     // effect that makes non-obvious changes to the heap.
345     ArrayModes m_arrayModes;
346     
347     // This is a proven constraint on the possible values that this value can
348     // have now or any time in the future, unless it is reassigned. Note that this
349     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
350     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
351     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
352     // means TOP.
353     JSValue m_value;
354
355 private:
356     void clobberArrayModes()
357     {
358         // FIXME: We could make this try to predict the set of array modes that this object
359         // could have in the future. For now, just do the simple thing.
360         m_arrayModes = ALL_ARRAY_MODES;
361     }
362     
363     void observeIndexingTypeTransition(IndexingType from, IndexingType to)
364     {
365         if (m_arrayModes & asArrayModes(from))
366             m_arrayModes |= asArrayModes(to);
367     }
368     
369     bool validateType(JSValue value) const
370     {
371         if (isHeapTop())
372             return true;
373         
374         // Constant folding always represents Int52's in a double (i.e. Int52AsDouble).
375         // So speculationFromValue(value) for an Int52 value will return Int52AsDouble,
376         // and that's fine - the type validates just fine.
377         SpeculatedType type = m_type;
378         if (type & SpecInt52)
379             type |= SpecInt52AsDouble;
380         
381         if (mergeSpeculations(type, speculationFromValue(value)) != type)
382             return false;
383         
384         if (value.isEmpty()) {
385             ASSERT(m_type & SpecEmpty);
386             return true;
387         }
388         
389         return true;
390     }
391     
392     void makeTop(SpeculatedType top)
393     {
394         m_type |= top;
395         m_arrayModes = ALL_ARRAY_MODES;
396         m_structure.makeTop();
397         m_value = JSValue();
398         checkConsistency();
399     }
400     
401     void filterValueByType();
402     void filterArrayModesByType();
403     
404     bool shouldBeClear() const;
405     FiltrationResult normalizeClarity();
406     FiltrationResult normalizeClarity(Graph&);
407 };
408
409 } } // namespace JSC::DFG
410
411 #endif // ENABLE(DFG_JIT)
412
413 #endif // DFGAbstractValue_h
414
415