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
37namespace JSC {
38
39class TrackedReferences;
40
41namespace DFG {
42
43class StructureAbstractValue {
44public:
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 JS_EXPORT_PRIVATE 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
253private:
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)
285