1/*
2 * Copyright (C) 2014, 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#include "config.h"
27#include "DFGStructureAbstractValue.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32
33namespace JSC { namespace DFG {
34
35#if !ASSERT_DISABLED
36void StructureAbstractValue::assertIsRegistered(Graph& graph) const
37{
38 if (isTop())
39 return;
40
41 for (unsigned i = size(); i--;)
42 graph.assertIsRegistered(at(i).get());
43}
44#endif // !ASSERT_DISABLED
45
46void StructureAbstractValue::clobber()
47{
48 // The premise of this approach to clobbering is that anytime we introduce
49 // a watchable structure into an abstract value, we watchpoint it. You can assert
50 // that this holds by calling assertIsWatched().
51
52 if (isTop())
53 return;
54
55 setClobbered(true);
56
57 if (m_set.isThin()) {
58 if (!m_set.singleEntry())
59 return;
60 if (!m_set.singleEntry()->dfgShouldWatch())
61 makeTopWhenThin();
62 return;
63 }
64
65 RegisteredStructureSet::OutOfLineList* list = m_set.list();
66 for (unsigned i = list->m_length; i--;) {
67 if (!list->list()[i]->dfgShouldWatch()) {
68 makeTop();
69 return;
70 }
71 }
72}
73
74void StructureAbstractValue::observeTransition(RegisteredStructure from, RegisteredStructure to)
75{
76 ASSERT(!from->dfgShouldWatch());
77
78 if (isTop())
79 return;
80
81 if (!m_set.contains(from))
82 return;
83
84 if (!m_set.add(to))
85 return;
86
87 if (m_set.size() > polymorphismLimit)
88 makeTop();
89}
90
91void StructureAbstractValue::observeTransitions(const TransitionVector& vector)
92{
93 if (isTop())
94 return;
95
96 RegisteredStructureSet newStructures;
97 for (unsigned i = vector.size(); i--;) {
98 ASSERT(!vector[i].previous->dfgShouldWatch());
99
100 if (!m_set.contains(vector[i].previous))
101 continue;
102
103 newStructures.add(vector[i].next);
104 }
105
106 if (!m_set.merge(newStructures))
107 return;
108
109 if (m_set.size() > polymorphismLimit)
110 makeTop();
111}
112
113bool StructureAbstractValue::add(RegisteredStructure structure)
114{
115 if (isTop())
116 return false;
117
118 if (!m_set.add(structure))
119 return false;
120
121 if (m_set.size() > polymorphismLimit)
122 makeTop();
123
124 return true;
125}
126
127bool StructureAbstractValue::merge(const RegisteredStructureSet& other)
128{
129 if (isTop())
130 return false;
131
132 return mergeNotTop(other);
133}
134
135bool StructureAbstractValue::mergeSlow(const StructureAbstractValue& other)
136{
137 // It isn't immediately obvious that the code below is doing the right thing, so let's go
138 // through it.
139 //
140 // This not clobbered, other not clobbered: Clearly, we don't want to make anything clobbered
141 // since we just have two sets and we are merging them. mergeNotTop() can handle this just
142 // fine.
143 //
144 // This clobbered, other clobbered: Clobbered means that we have a set of things, plus we
145 // temporarily have the set of all things but the latter will go away once we hit the next
146 // invalidation point. This allows us to merge two clobbered sets the natural way. For now
147 // the set will still be TOP (and so we keep the clobbered bit set), but we know that after
148 // invalidation, we will have the union of the this and other.
149 //
150 // This clobbered, other not clobbered: It's safe to merge in other for both before and after
151 // invalidation, so long as we leave the clobbered bit set. Before invalidation this has no
152 // effect since the set will still appear to have all things in it. The way to think about
153 // what invalidation would do is imagine if we had a set A that was clobbered and a set B
154 // that wasn't and we considered the following two cases. Note that we expect A to be the
155 // same at the end in both cases:
156 //
157 // A.merge(B) InvalidationPoint
158 // InvalidationPoint A.merge(B)
159 //
160 // The fact that we expect A to be the same in both cases means that we want to merge other
161 // into this but keep the clobbered bit.
162 //
163 // This not clobbered, other clobbered: This is just the converse of the previous case. We
164 // want to merge other into this and set the clobbered bit.
165
166 bool changed = false;
167
168 if (!isClobbered() && other.isClobbered()) {
169 setClobbered(true);
170 changed = true;
171 }
172
173 changed |= mergeNotTop(other.m_set);
174
175 return changed;
176}
177
178bool StructureAbstractValue::mergeNotTop(const RegisteredStructureSet& other)
179{
180 if (!m_set.merge(other))
181 return false;
182
183 if (m_set.size() > polymorphismLimit)
184 makeTop();
185
186 return true;
187}
188
189void StructureAbstractValue::filter(const RegisteredStructureSet& other)
190{
191 if (isTop()) {
192 m_set = other;
193 return;
194 }
195
196 if (isClobbered()) {
197 // We have two choices here:
198 //
199 // Do nothing: It's legal to keep our set intact, which would essentially mean that for
200 // now, our set would behave like TOP but after the next invalidation point it wold be
201 // a finite set again. This may be a good choice if 'other' is much bigger than our
202 // m_set.
203 //
204 // Replace m_set with other and clear the clobber bit: This is also legal, and means that
205 // we're no longer clobbered. This is usually better because it immediately gives us a
206 // smaller set.
207 //
208 // This scenario should come up rarely. We usually don't do anything to an abstract value
209 // after it is clobbered. But we apply some heuristics.
210
211 if (other.size() > m_set.size() + clobberedSupremacyThreshold)
212 return; // Keep the clobbered set.
213
214 m_set = other;
215 setClobbered(false);
216 return;
217 }
218
219 m_set.filter(other);
220}
221
222void StructureAbstractValue::filter(const StructureAbstractValue& other)
223{
224 if (other.isTop())
225 return;
226
227 if (other.isClobbered()) {
228 if (isTop())
229 return;
230
231 if (!isClobbered()) {
232 // See justification in filter(const RegisteredStructureSet&), above. An unclobbered set is
233 // almost always better.
234 if (m_set.size() > other.m_set.size() + clobberedSupremacyThreshold)
235 *this = other; // Keep the clobbered set.
236 return;
237 }
238
239 m_set.filter(other.m_set);
240 return;
241 }
242
243 filter(other.m_set);
244}
245
246void StructureAbstractValue::filterSlow(SpeculatedType type)
247{
248 if (!(type & SpecCell)) {
249 clear();
250 return;
251 }
252
253 ASSERT(!isTop());
254
255 m_set.genericFilter(
256 [&] (RegisteredStructure structure) {
257 return !!(speculationFromStructure(structure.get()) & type);
258 });
259}
260
261void StructureAbstractValue::filterClassInfoSlow(const ClassInfo* classInfo)
262{
263 ASSERT(!isTop());
264 m_set.genericFilter(
265 [&] (RegisteredStructure structure) {
266 return structure->classInfo()->isSubClassOf(classInfo);
267 });
268}
269
270bool StructureAbstractValue::contains(RegisteredStructure structure) const
271{
272 if (isInfinite())
273 return true;
274
275 return m_set.contains(structure);
276}
277
278bool StructureAbstractValue::contains(Structure* structure) const
279{
280 if (isInfinite())
281 return true;
282
283 return m_set.toStructureSet().contains(structure);
284}
285
286bool StructureAbstractValue::isSubsetOf(const RegisteredStructureSet& other) const
287{
288 if (isInfinite())
289 return false;
290
291 return m_set.isSubsetOf(other);
292}
293
294bool StructureAbstractValue::isSubsetOf(const StructureAbstractValue& other) const
295{
296 if (isTop())
297 return false;
298
299 if (other.isTop())
300 return true;
301
302 if (isClobbered() == other.isClobbered())
303 return m_set.isSubsetOf(other.m_set);
304
305 // Here it gets tricky. If in doubt, return false!
306
307 if (isClobbered())
308 return false; // A clobbered set is never a subset of an unclobbered set.
309
310 // An unclobbered set is currently a subset of a clobbered set, but it may not be so after
311 // invalidation.
312 return m_set.isSubsetOf(other.m_set);
313}
314
315bool StructureAbstractValue::isSupersetOf(const RegisteredStructureSet& other) const
316{
317 if (isInfinite())
318 return true;
319
320 return m_set.isSupersetOf(other);
321}
322
323bool StructureAbstractValue::overlaps(const RegisteredStructureSet& other) const
324{
325 if (isInfinite())
326 return true;
327
328 return m_set.overlaps(other);
329}
330
331bool StructureAbstractValue::overlaps(const StructureAbstractValue& other) const
332{
333 if (other.isInfinite())
334 return true;
335
336 return overlaps(other.m_set);
337}
338
339bool StructureAbstractValue::isSubClassOf(const ClassInfo* classInfo) const
340{
341 if (isInfinite())
342 return false;
343
344 // Note taht this function returns true if the structure set is empty.
345 for (const RegisteredStructure structure : m_set) {
346 if (!structure->classInfo()->isSubClassOf(classInfo))
347 return false;
348 }
349 return true;
350}
351
352bool StructureAbstractValue::equalsSlow(const StructureAbstractValue& other) const
353{
354 ASSERT(m_set.m_pointer != other.m_set.m_pointer);
355 ASSERT(!isTop());
356 ASSERT(!other.isTop());
357
358 return m_set == other.m_set
359 && isClobbered() == other.isClobbered();
360}
361
362void StructureAbstractValue::dumpInContext(PrintStream& out, DumpContext* context) const
363{
364 if (isClobbered())
365 out.print("Clobbered:");
366
367 if (isTop())
368 out.print("TOP");
369 else
370 out.print(inContext(m_set.toStructureSet(), context));
371}
372
373void StructureAbstractValue::dump(PrintStream& out) const
374{
375 dumpInContext(out, 0);
376}
377
378void StructureAbstractValue::validateReferences(const TrackedReferences& trackedReferences) const
379{
380 if (isTop())
381 return;
382 m_set.validateReferences(trackedReferences);
383}
384
385} } // namespace JSC::DFG
386
387#endif // ENABLE(DFG_JIT)
388
389