DFG should have some facility for recognizing redundant CheckArrays and Arrayifies
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractValue.h
1 /*
2  * Copyright (C) 2011, 2012 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 #include <wtf/Platform.h>
30
31 #if ENABLE(DFG_JIT)
32
33 #include "ArrayProfile.h"
34 #include "DFGStructureAbstractValue.h"
35 #include "JSCell.h"
36 #include "SpeculatedType.h"
37 #include "StructureSet.h"
38
39 namespace JSC { namespace DFG {
40
41 struct AbstractValue {
42     AbstractValue()
43         : m_type(SpecNone)
44         , m_arrayModes(0)
45     {
46     }
47     
48     void clear()
49     {
50         m_type = SpecNone;
51         m_arrayModes = 0;
52         m_currentKnownStructure.clear();
53         m_futurePossibleStructure.clear();
54         m_value = JSValue();
55         checkConsistency();
56     }
57     
58     bool isClear() const
59     {
60         bool result = m_type == SpecNone && !m_arrayModes && m_currentKnownStructure.isClear() && m_futurePossibleStructure.isClear();
61         if (result)
62             ASSERT(!m_value);
63         return result;
64     }
65     
66     void makeTop()
67     {
68         m_type = SpecTop;
69         m_arrayModes = ALL_ARRAY_MODES;
70         m_currentKnownStructure.makeTop();
71         m_futurePossibleStructure.makeTop();
72         m_value = JSValue();
73         checkConsistency();
74     }
75     
76     void clobberStructures()
77     {
78         if (m_type & SpecCell) {
79             m_currentKnownStructure.makeTop();
80             clobberArrayModes();
81         } else {
82             ASSERT(m_currentKnownStructure.isClear());
83             ASSERT(!m_arrayModes);
84         }
85         checkConsistency();
86     }
87         
88     void clobberValue()
89     {
90         m_value = JSValue();
91     }
92     
93     bool isTop() const
94     {
95         return m_type == SpecTop && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop();
96     }
97     
98     bool valueIsTop() const
99     {
100         return !m_value && m_type;
101     }
102     
103     JSValue value() const
104     {
105         return m_value;
106     }
107     
108     static AbstractValue top()
109     {
110         AbstractValue result;
111         result.makeTop();
112         return result;
113     }
114     
115     void setMostSpecific(JSValue value)
116     {
117         if (!!value && value.isCell()) {
118             Structure* structure = value.asCell()->structure();
119             m_currentKnownStructure = structure;
120             setFuturePossibleStructure(structure);
121             m_arrayModes = asArrayModes(structure->indexingType());
122         } else {
123             m_currentKnownStructure.clear();
124             m_futurePossibleStructure.clear();
125             m_arrayModes = 0;
126         }
127         
128         m_type = speculationFromValue(value);
129         m_value = value;
130         
131         checkConsistency();
132     }
133     
134     void set(JSValue value)
135     {
136         if (!!value && value.isCell()) {
137             m_currentKnownStructure.makeTop();
138             Structure* structure = value.asCell()->structure();
139             setFuturePossibleStructure(structure);
140             m_arrayModes = asArrayModes(structure->indexingType());
141             clobberArrayModes();
142         } else {
143             m_currentKnownStructure.clear();
144             m_futurePossibleStructure.clear();
145             m_arrayModes = 0;
146         }
147         
148         m_type = speculationFromValue(value);
149         m_value = value;
150         
151         checkConsistency();
152     }
153     
154     void set(Structure* structure)
155     {
156         m_currentKnownStructure = structure;
157         setFuturePossibleStructure(structure);
158         m_arrayModes = asArrayModes(structure->indexingType());
159         m_type = speculationFromStructure(structure);
160         m_value = JSValue();
161         
162         checkConsistency();
163     }
164     
165     void set(SpeculatedType type)
166     {
167         if (type & SpecCell) {
168             m_currentKnownStructure.makeTop();
169             m_futurePossibleStructure.makeTop();
170             m_arrayModes = ALL_ARRAY_MODES;
171         } else {
172             m_currentKnownStructure.clear();
173             m_futurePossibleStructure.clear();
174             m_arrayModes = 0;
175         }
176         m_type = type;
177         m_value = JSValue();
178         checkConsistency();
179     }
180     
181     bool operator==(const AbstractValue& other) const
182     {
183         return m_type == other.m_type
184             && m_arrayModes == other.m_arrayModes
185             && m_currentKnownStructure == other.m_currentKnownStructure
186             && m_futurePossibleStructure == other.m_futurePossibleStructure
187             && m_value == other.m_value;
188     }
189     bool operator!=(const AbstractValue& other) const
190     {
191         return !(*this == other);
192     }
193     
194     bool merge(const AbstractValue& other)
195     {
196 #if !ASSERT_DISABLED
197         AbstractValue oldMe = *this;
198 #endif
199         bool result = false;
200         if (isClear()) {
201             *this = other;
202             result = !other.isClear();
203         } else {
204             result |= mergeSpeculation(m_type, other.m_type);
205             result |= mergeArrayModes(m_arrayModes, other.m_arrayModes);
206             result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure);
207             result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure);
208             if (m_value != other.m_value) {
209                 result |= !!m_value;
210                 m_value = JSValue();
211             }
212         }
213         checkConsistency();
214         ASSERT(result == (*this != oldMe));
215         return result;
216     }
217     
218     void merge(SpeculatedType type)
219     {
220         mergeSpeculation(m_type, type);
221         
222         if (type & SpecCell) {
223             m_currentKnownStructure.makeTop();
224             m_futurePossibleStructure.makeTop();
225             m_arrayModes = ALL_ARRAY_MODES;
226         }
227         m_value = JSValue();
228
229         checkConsistency();
230     }
231     
232     void filter(const StructureSet& other)
233     {
234         m_type &= other.speculationFromStructures();
235         m_arrayModes &= other.arrayModesFromStructures();
236         m_currentKnownStructure.filter(other);
237         if (m_currentKnownStructure.isClear())
238             m_futurePossibleStructure.clear();
239         else if (m_currentKnownStructure.hasSingleton())
240             filterFuturePossibleStructure(m_currentKnownStructure.singleton());
241         
242         // It's possible that prior to the above two statements we had (Foo, TOP), where
243         // Foo is a SpeculatedType that is disjoint with the passed StructureSet. In that
244         // case, we will now have (None, [someStructure]). In general, we need to make
245         // sure that new information gleaned from the SpeculatedType needs to be fed back
246         // into the information gleaned from the StructureSet.
247         m_currentKnownStructure.filter(m_type);
248         m_futurePossibleStructure.filter(m_type);
249         
250         filterArrayModesByType();
251         filterValueByType();
252         
253         checkConsistency();
254     }
255     
256     void filterArrayModes(ArrayModes arrayModes)
257     {
258         ASSERT(arrayModes);
259         
260         m_type &= SpecCell;
261         m_arrayModes &= arrayModes;
262         
263         // I could do more fancy filtering here. But it probably won't make any difference.
264         
265         checkConsistency();
266     }
267     
268     void filter(SpeculatedType type)
269     {
270         if (type == SpecTop)
271             return;
272         m_type &= type;
273         
274         // It's possible that prior to this filter() call we had, say, (Final, TOP), and
275         // the passed type is Array. At this point we'll have (None, TOP). The best way
276         // to ensure that the structure filtering does the right thing is to filter on
277         // the new type (None) rather than the one passed (Array).
278         m_currentKnownStructure.filter(m_type);
279         m_futurePossibleStructure.filter(m_type);
280         
281         filterArrayModesByType();
282         filterValueByType();
283         
284         checkConsistency();
285     }
286     
287     bool validateType(JSValue value) const
288     {
289         if (isTop())
290             return true;
291         
292         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
293             return false;
294         
295         if (value.isEmpty()) {
296             ASSERT(m_type & SpecEmpty);
297             return true;
298         }
299         
300         return true;
301     }
302     
303     bool validate(JSValue value) const
304     {
305         if (isTop())
306             return true;
307         
308         if (!!m_value && m_value != value)
309             return false;
310         
311         if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
312             return false;
313         
314         if (value.isEmpty()) {
315             ASSERT(m_type & SpecEmpty);
316             return true;
317         }
318         
319         if (!!value && value.isCell()) {
320             ASSERT(m_type & SpecCell);
321             Structure* structure = value.asCell()->structure();
322             return m_currentKnownStructure.contains(structure)
323                 && m_futurePossibleStructure.contains(structure)
324                 && (m_arrayModes & asArrayModes(structure->indexingType()));
325         }
326         
327         return true;
328     }
329     
330     void checkConsistency() const
331     {
332         if (!(m_type & SpecCell)) {
333             ASSERT(m_currentKnownStructure.isClear());
334             ASSERT(m_futurePossibleStructure.isClear());
335             ASSERT(!m_arrayModes);
336         }
337         
338         if (isClear())
339             ASSERT(!m_value);
340         
341         if (!!m_value)
342             ASSERT(mergeSpeculations(m_type, speculationFromValue(m_value)) == m_type);
343         
344         // Note that it's possible for a prediction like (Final, []). This really means that
345         // the value is bottom and that any code that uses the value is unreachable. But
346         // we don't want to get pedantic about this as it would only increase the computational
347         // complexity of the code.
348     }
349     
350     void dump(FILE* out) const
351     {
352         fprintf(out, "(%s, %s, ", speculationToString(m_type), arrayModesToString(m_arrayModes));
353         m_currentKnownStructure.dump(out);
354         dataLog(", ");
355         m_futurePossibleStructure.dump(out);
356         if (!!m_value)
357             fprintf(out, ", %s", m_value.description());
358         fprintf(out, ")");
359     }
360     
361     // A great way to think about the difference between m_currentKnownStructure and
362     // m_futurePossibleStructure is to consider these four examples:
363     //
364     // 1) x = foo();
365     //
366     //    In this case x's m_currentKnownStructure and m_futurePossibleStructure will
367     //    both be TOP, since we don't know anything about x for sure, yet.
368     //
369     // 2) x = foo();
370     //    y = x.f;
371     //
372     //    Where x will later have a new property added to it, 'g'. Because of the
373     //    known but not-yet-executed property addition, x's currently structure will
374     //    not be watchpointable; hence we have no way of statically bounding the set
375     //    of possible structures that x may have if a clobbering event happens. So,
376     //    x's m_currentKnownStructure will be whatever structure we check to get
377     //    property 'f', and m_futurePossibleStructure will be TOP.
378     //
379     // 3) x = foo();
380     //    y = x.f;
381     //
382     //    Where x has a terminal structure that is still watchpointable. In this case,
383     //    x's m_currentKnownStructure and m_futurePossibleStructure will both be
384     //    whatever structure we checked for when getting 'f'.
385     //
386     // 4) x = foo();
387     //    y = x.f;
388     //    bar();
389     //
390     //    Where x has a terminal structure that is still watchpointable. In this
391     //    case, m_currentKnownStructure will be TOP because bar() may potentially
392     //    change x's structure and we have no way of proving otherwise, but
393     //    x's m_futurePossibleStructure will be whatever structure we had checked
394     //    when getting property 'f'.
395
396     // This is a proven constraint on the structures that this value can have right
397     // now. The structure of the current value must belong to this set. The set may
398     // be TOP, indicating that it is the set of all possible structures, in which
399     // case the current value can have any structure. The set may be BOTTOM (empty)
400     // in which case this value cannot be a cell. This is all subject to change
401     // anytime a new value is assigned to this one, anytime there is a control flow
402     // merge, or most crucially, anytime a side-effect or structure check happens.
403     // In case of a side-effect, we typically must assume that any value may have
404     // had its structure changed, hence contravening our proof. We make the proof
405     // valid again by switching this to TOP (i.e. claiming that we have proved that
406     // this value may have any structure). Of note is that the proof represented by
407     // this field is not subject to structure transition watchpoints - even if one
408     // fires, we can be sure that this proof is still valid.
409     StructureAbstractValue m_currentKnownStructure;
410     
411     // This is a proven constraint on the structures that this value can have now
412     // or any time in the future subject to the structure transition watchpoints of
413     // all members of this set not having fired. This set is impervious to side-
414     // effects; even if one happens the side-effect can only cause the value to
415     // change to at worst another structure that is also a member of this set. But,
416     // the theorem being proved by this field is predicated upon there not being
417     // any new structure transitions introduced into any members of this set. In
418     // cases where there is no way for us to guard this happening, the set must be
419     // TOP. But in cases where we can guard new structure transitions (all members
420     // of the set have still-valid structure transition watchpoints) then this set
421     // will be finite. Anytime that we make use of the finite nature of this set,
422     // we must first issue a structure transition watchpoint, which will effectively
423     // result in m_currentKnownStructure being filtered according to
424     // m_futurePossibleStructure.
425     StructureAbstractValue m_futurePossibleStructure;
426     
427     // This is a proven constraint on the possible types that this value can have
428     // now or any time in the future, unless it is reassigned. This field is
429     // impervious to side-effects unless the side-effect can reassign the value
430     // (for example if we're talking about a captured variable). The relationship
431     // between this field, and the structure fields above, is as follows. The
432     // fields above constraint the structures that a cell may have, but they say
433     // nothing about whether or not the value is known to be a cell. More formally,
434     // the m_currentKnownStructure is itself an abstract value that consists of the
435     // union of the set of all non-cell values and the set of cell values that have
436     // the given structure. This abstract value is then the intersection of the
437     // m_currentKnownStructure and the set of values whose type is m_type. So, for
438     // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is
439     // [0x12345] then this abstract value corresponds to the set of all integers
440     // unified with the set of all objects with structure 0x12345.
441     SpeculatedType m_type;
442     
443     // This is a proven constraint on the possible indexing types that this value
444     // can have right now. It also implicitly constraints the set of structures
445     // that the value may have right now, since a structure has an immutable
446     // indexing type. This is subject to change upon reassignment, or any side
447     // effect that makes non-obvious changes to the heap.
448     ArrayModes m_arrayModes;
449     
450     // This is a proven constraint on the possible values that this value can
451     // have now or any time in the future, unless it is reassigned. Note that this
452     // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value)
453     // means either BOTTOM or TOP depending on the state of m_type: if m_type is
454     // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue()
455     // means TOP.
456     JSValue m_value;
457
458 private:
459     void clobberArrayModes()
460     {
461         if (m_arrayModes == ALL_ARRAY_MODES)
462             return;
463         
464         if (LIKELY(m_arrayModes & asArrayModes(NonArray)))
465             m_arrayModes = ALL_ARRAY_MODES;
466         else
467             clobberArrayModesSlow();
468     }
469     
470     void clobberArrayModesSlow()
471     {
472         if (m_arrayModes & asArrayModes(ArrayClass))
473             m_arrayModes = ALL_ARRAY_MODES;
474         else if (m_arrayModes & asArrayModes(NonArrayWithContiguous))
475             m_arrayModes |= asArrayModes(NonArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage);
476         else if (m_arrayModes & asArrayModes(ArrayWithContiguous))
477             m_arrayModes |= asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage);
478         else if (m_arrayModes & asArrayModes(NonArrayWithArrayStorage))
479             m_arrayModes |= asArrayModes(NonArrayWithSlowPutArrayStorage);
480         else if (m_arrayModes & asArrayModes(ArrayWithArrayStorage))
481             m_arrayModes |= asArrayModes(ArrayWithArrayStorage);
482     }
483
484     void setFuturePossibleStructure(Structure* structure)
485     {
486         if (structure->transitionWatchpointSetIsStillValid())
487             m_futurePossibleStructure = structure;
488         else
489             m_futurePossibleStructure.makeTop();
490     }
491     
492     void filterFuturePossibleStructure(Structure* structure)
493     {
494         if (structure->transitionWatchpointSetIsStillValid())
495             m_futurePossibleStructure.filter(StructureAbstractValue(structure));
496     }
497
498     // We could go further, and ensure that if the futurePossibleStructure contravenes
499     // the value, then we could clear both of those things. But that's unlikely to help
500     // in any realistic scenario, so we don't do it. Simpler is better.
501     void filterValueByType()
502     {
503         if (!!m_type) {
504             // The type is still non-empty. This implies that regardless of what filtering
505             // was done, we either didn't have a value to begin with, or that value is still
506             // valid.
507             ASSERT(!m_value || validateType(m_value));
508             return;
509         }
510         
511         // The type has been rendered empty. That means that the value must now be invalid,
512         // as well.
513         ASSERT(!m_value || !validateType(m_value));
514         m_value = JSValue();
515     }
516     
517     void filterArrayModesByType()
518     {
519         if (!(m_type & SpecCell))
520             m_arrayModes = 0;
521         else if (!(m_type & ~SpecArray))
522             m_arrayModes &= ALL_ARRAY_ARRAY_MODES;
523         else if (!(m_type & SpecArray))
524             m_arrayModes &= ALL_NON_ARRAY_ARRAY_MODES;
525     }
526 };
527
528 } } // namespace JSC::DFG
529
530 #endif // ENABLE(DFG_JIT)
531
532 #endif // DFGAbstractValue_h
533
534