e3bfbc458ddcd8eb9f3e6843a8a9674e68d9a3a3
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGStructureAbstractValue.h
1 /*
2  * Copyright (C) 2011-2015 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 "DFGRegisteredStructureSet.h"
31 #include "DFGTransition.h"
32 #include "DumpContext.h"
33 #include "JSCast.h"
34 #include "SpeculatedType.h"
35 #include "StructureSet.h"
36
37 namespace JSC {
38
39 class TrackedReferences;
40
41 namespace DFG {
42
43 class StructureAbstractValue {
44 public:
45     StructureAbstractValue() { }
46     StructureAbstractValue(RegisteredStructure structure)
47         : m_set(structure)
48     {
49         setClobbered(false);
50     }
51     StructureAbstractValue(const RegisteredStructureSet& other)
52         : m_set(other)
53     {
54         setClobbered(false);
55     }
56     ALWAYS_INLINE StructureAbstractValue(const StructureAbstractValue& other)
57         : m_set(other.m_set)
58     {
59         setClobbered(other.isClobbered());
60     }
61     
62     ALWAYS_INLINE StructureAbstractValue& operator=(RegisteredStructure structure)
63     {
64         m_set = RegisteredStructureSet(structure);
65         setClobbered(false);
66         return *this;
67     }
68     ALWAYS_INLINE StructureAbstractValue& operator=(const RegisteredStructureSet& other)
69     {
70         m_set = other;
71         setClobbered(false);
72         return *this;
73     }
74     ALWAYS_INLINE StructureAbstractValue& operator=(const StructureAbstractValue& other)
75     {
76         m_set = other.m_set;
77         setClobbered(other.isClobbered());
78         return *this;
79     }
80     
81     void clear()
82     {
83         m_set.clear();
84         setClobbered(false);
85     }
86     
87     void makeTop()
88     {
89         m_set.deleteListIfNecessary();
90         m_set.m_pointer = topValue;
91     }
92     
93 #if ASSERT_DISABLED
94     void assertIsRegistered(Graph&) const { }
95 #else
96     void assertIsRegistered(Graph&) const;
97 #endif
98     
99     void clobber();
100     void observeInvalidationPoint() { setClobbered(false); }
101     
102     void observeTransition(RegisteredStructure from, RegisteredStructure to);
103     void observeTransitions(const TransitionVector&);
104     
105     static StructureAbstractValue top()
106     {
107         StructureAbstractValue result;
108         result.m_set.m_pointer = topValue;
109         return result;
110     }
111     
112     bool isClear() const { return m_set.isEmpty(); }
113     bool isTop() const { return m_set.m_pointer == topValue; }
114     bool isNeitherClearNorTop() const { return !isClear() && !isTop(); }
115     
116     // A clobbered abstract value means that the set currently contains the m_set set of
117     // structures plus TOP, except that the "plus TOP" will go away at the next invalidation
118     // point. Note that it's tempting to think of this as "the set of structures in m_set plus
119     // the set of structures transition-reachable from m_set" - but this isn't really correct,
120     // since if we add an unwatchable structure after clobbering, the two definitions are not
121     // equivalent. If we do this, the new unwatchable structure will be added to m_set.
122     // Invalidation points do not try to "clip" the set of transition-reachable structures from
123     // m_set by looking at reachability as this would mean that the new set is TOP. Instead they
124     // literally assume that the set is just m_set rather than m_set plus TOP.
125     bool isClobbered() const { return m_set.getReservedFlag(); }
126
127     // A finite structure abstract value is one where enumerating over it will yield all
128     // of the structures that the value may have right now. This is true so long as we're
129     // neither top nor clobbered.
130     bool isFinite() const { return !isTop() && !isClobbered(); }
131
132     // An infinite structure abstract value may currently have any structure.
133     bool isInfinite() const { return !isFinite(); }
134     
135     bool add(RegisteredStructure);
136     
137     bool merge(const RegisteredStructureSet& other);
138     
139     ALWAYS_INLINE bool merge(const StructureAbstractValue& other)
140     {
141         if (other.isClear())
142             return false;
143         
144         if (isTop())
145             return false;
146         
147         if (other.isTop()) {
148             makeTop();
149             return true;
150         }
151         
152         return mergeSlow(other);
153     }
154     
155     void filter(const RegisteredStructureSet& other);
156     void filter(const StructureAbstractValue& other);
157     
158     ALWAYS_INLINE void filter(SpeculatedType type)
159     {
160         if (!(type & SpecCell)) {
161             clear();
162             return;
163         }
164         if (isNeitherClearNorTop())
165             filterSlow(type);
166     }
167
168     ALWAYS_INLINE void filterClassInfo(const ClassInfo* classInfo)
169     {
170         if (isNeitherClearNorTop())
171             filterClassInfoSlow(classInfo);
172     }
173     
174     ALWAYS_INLINE bool operator==(const StructureAbstractValue& other) const
175     {
176         if ((m_set.isThin() && other.m_set.isThin()) || isTop() || other.isTop())
177             return m_set.m_pointer == other.m_set.m_pointer;
178         
179         return equalsSlow(other);
180     }
181     
182     const RegisteredStructureSet& set() const
183     {
184         ASSERT(!isTop());
185         return m_set;
186     }
187
188     StructureSet toStructureSet() const
189     {
190         RELEASE_ASSERT(isFinite());
191         return m_set.toStructureSet();
192     }
193     
194     size_t size() const
195     {
196         ASSERT(!isTop());
197         return m_set.size();
198     }
199     
200     RegisteredStructure at(size_t i) const
201     {
202         ASSERT(!isTop());
203         return m_set.at(i);
204     }
205     
206     RegisteredStructure operator[](size_t i) const { return at(i); }
207
208     // In most cases, what you really want to do is verify whether the set is top or clobbered, and
209     // if not, enumerate the set of structures. Use this only in cases where the singleton case is
210     // meaningfully special, like for transitions.
211     RegisteredStructure onlyStructure() const
212     {
213         if (isInfinite())
214             return RegisteredStructure();
215         return m_set.onlyStructure();
216     }
217
218     template<typename Functor>
219     void forEach(const Functor& functor) const
220     {
221         ASSERT(!isTop());
222         m_set.forEach(functor);
223     }
224     
225     void dumpInContext(PrintStream&, DumpContext*) const;
226     void dump(PrintStream&) const;
227     
228     // The methods below are all conservative and err on the side of making 'this' appear bigger
229     // than it is. For example, contains() may return true if the set is clobbered or TOP.
230     // isSubsetOf() may return false in case of ambiguities. Therefore you should only perform
231     // optimizations as a consequence of the "this is smaller" return value - so false for
232     // contains(), true for isSubsetOf(), false for isSupersetOf(), and false for overlaps().
233
234     bool contains(RegisteredStructure) const;
235     bool contains(Structure* structure) const;
236     
237     bool isSubsetOf(const RegisteredStructureSet& other) const;
238     bool isSubsetOf(const StructureAbstractValue& other) const;
239     
240     bool isSupersetOf(const RegisteredStructureSet& other) const;
241     bool isSupersetOf(const StructureAbstractValue& other) const
242     {
243         return other.isSubsetOf(*this);
244     }
245     
246     bool overlaps(const RegisteredStructureSet& other) const;
247     bool overlaps(const StructureAbstractValue& other) const;
248
249     bool isSubClassOf(const ClassInfo*) const;
250     
251     void validateReferences(const TrackedReferences&) const;
252     
253 private:
254     static const uintptr_t clobberedFlag = RegisteredStructureSet::reservedFlag;
255     static const uintptr_t topValue = RegisteredStructureSet::reservedValue;
256     static const unsigned polymorphismLimit = 10;
257     static const unsigned clobberedSupremacyThreshold = 2;
258     
259     void filterSlow(SpeculatedType type);
260     void filterClassInfoSlow(const ClassInfo*);
261     bool mergeSlow(const StructureAbstractValue& other);
262     
263     bool equalsSlow(const StructureAbstractValue& other) const;
264     
265     void makeTopWhenThin()
266     {
267         ASSERT(m_set.isThin());
268         m_set.m_pointer = topValue;
269     }
270     
271     bool mergeNotTop(const RegisteredStructureSet& other);
272     
273     void setClobbered(bool clobbered)
274     {
275         ASSERT(!isTop() || !clobbered);
276         m_set.setReservedFlag(clobbered);
277     }
278     
279     RegisteredStructureSet m_set;
280 };
281
282 } } // namespace JSC::DFG
283
284 #endif // ENABLE(DFG_JIT)