[JSC] Implement optimized WeakMap and WeakSet
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractHeap.h
1 /*
2  * Copyright (C) 2013-2016 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 "DOMJITHeapRange.h"
31 #include "VirtualRegister.h"
32 #include <wtf/HashMap.h>
33 #include <wtf/PrintStream.h>
34
35 namespace JSC { namespace DFG {
36
37 // Implements a four-level type hierarchy:
38 // - World is the supertype of all of the things.
39 // - Stack with a TOP payload is a direct subtype of World
40 // - Stack with a non-TOP payload is a direct subtype of Stack with a TOP payload.
41 // - Heap is a direct subtype of World.
42 // - SideState is a direct subtype of World.
43 // - Any other kind with TOP payload is the direct subtype of Heap.
44 // - Any other kind with non-TOP payload is the direct subtype of the same kind with a TOP payload.
45
46 #define FOR_EACH_ABSTRACT_HEAP_KIND(macro) \
47     macro(InvalidAbstractHeap) \
48     macro(World) \
49     macro(Stack) \
50     macro(Heap) \
51     macro(Butterfly_publicLength) \
52     macro(Butterfly_vectorLength) \
53     macro(GetterSetter_getter) \
54     macro(GetterSetter_setter) \
55     macro(JSCell_cellState) \
56     macro(JSCell_indexingType) \
57     macro(JSCell_structureID) \
58     macro(JSCell_typeInfoFlags) \
59     macro(JSCell_typeInfoType) \
60     macro(JSObject_butterfly) \
61     macro(JSPropertyNameEnumerator_cachedPropertyNames) \
62     macro(RegExpObject_lastIndex) \
63     macro(NamedProperties) \
64     macro(IndexedInt32Properties) \
65     macro(IndexedDoubleProperties) \
66     macro(IndexedContiguousProperties) \
67     macro(IndexedArrayStorageProperties) \
68     macro(ArrayStorageProperties) \
69     macro(DirectArgumentsProperties) \
70     macro(ScopeProperties) \
71     macro(TypedArrayProperties) \
72     macro(HeapObjectCount) /* Used to reflect the fact that some allocations reveal object identity */\
73     macro(RegExpState) \
74     macro(MathDotRandomState) \
75     macro(JSMapFields) \
76     macro(JSSetFields) \
77     macro(JSWeakMapFields) \
78     macro(JSWeakSetFields) \
79     macro(InternalState) \
80     macro(Absolute) \
81     /* DOMJIT tells the heap range with the pair of integers. */\
82     macro(DOMState) \
83     /* Use this for writes only, to indicate that this may fire watchpoints. Usually this is never directly written but instead we test to see if a node clobbers this; it just so happens that you have to write world to clobber it. */\
84     macro(Watchpoint_fire) \
85     /* Use these for reads only, just to indicate that if the world got clobbered, then this operation will not work. */\
86     macro(MiscFields) \
87     /* Use this for writes only, just to indicate that hoisting the node is invalid. This works because we don't hoist anything that has any side effects at all. */\
88     macro(SideState)
89
90 enum AbstractHeapKind {
91 #define ABSTRACT_HEAP_DECLARATION(name) name,
92     FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
93 #undef ABSTRACT_HEAP_DECLARATION
94 };
95
96 class AbstractHeap {
97 public:
98     class Payload {
99     public:
100         Payload()
101             : m_isTop(false)
102             , m_value(0)
103         {
104         }
105         
106         Payload(bool isTop, int64_t value)
107             : m_isTop(isTop)
108             , m_value(value)
109         {
110             ASSERT(!(isTop && value));
111         }
112         
113         Payload(int64_t value)
114             : m_isTop(false)
115             , m_value(value)
116         {
117         }
118         
119         Payload(const void* pointer)
120             : m_isTop(false)
121             , m_value(bitwise_cast<intptr_t>(pointer))
122         {
123         }
124         
125         Payload(VirtualRegister operand)
126             : m_isTop(false)
127             , m_value(operand.offset())
128         {
129         }
130         
131         static Payload top() { return Payload(true, 0); }
132         
133         bool isTop() const { return m_isTop; }
134         int64_t value() const
135         {
136             ASSERT(!isTop());
137             return valueImpl();
138         }
139         int64_t valueImpl() const
140         {
141             return m_value;
142         }
143         
144         int32_t value32() const
145         {
146             return static_cast<int32_t>(value());
147         }
148         
149         bool operator==(const Payload& other) const
150         {
151             return m_isTop == other.m_isTop
152                 && m_value == other.m_value;
153         }
154         
155         bool operator!=(const Payload& other) const
156         {
157             return !(*this == other);
158         }
159         
160         bool operator<(const Payload& other) const
161         {
162             if (isTop())
163                 return !other.isTop();
164             if (other.isTop())
165                 return false;
166             return value() < other.value();
167         }
168         
169         bool isDisjoint(const Payload& other) const
170         {
171             if (isTop())
172                 return false;
173             if (other.isTop())
174                 return false;
175             return m_value != other.m_value;
176         }
177         
178         bool overlaps(const Payload& other) const
179         {
180             return !isDisjoint(other);
181         }
182         
183         void dump(PrintStream&) const;
184         
185     private:
186         bool m_isTop;
187         int64_t m_value;
188     };
189     
190     AbstractHeap()
191     {
192         m_value = encode(InvalidAbstractHeap, Payload());
193     }
194     
195     AbstractHeap(AbstractHeapKind kind)
196     {
197         ASSERT(kind != InvalidAbstractHeap);
198         m_value = encode(kind, Payload::top());
199     }
200     
201     AbstractHeap(AbstractHeapKind kind, Payload payload)
202     {
203         ASSERT(kind != InvalidAbstractHeap && kind != World && kind != Heap && kind != SideState);
204         m_value = encode(kind, payload);
205     }
206     
207     AbstractHeap(WTF::HashTableDeletedValueType)
208     {
209         m_value = encode(InvalidAbstractHeap, Payload::top());
210     }
211     
212     bool operator!() const { return kind() == InvalidAbstractHeap && !payloadImpl().isTop(); }
213     
214     AbstractHeapKind kind() const { return static_cast<AbstractHeapKind>(m_value & ((1 << topShift) - 1)); }
215     Payload payload() const
216     {
217         ASSERT(kind() != World && kind() != InvalidAbstractHeap);
218         return payloadImpl();
219     }
220     
221     AbstractHeap supertype() const
222     {
223         ASSERT(kind() != InvalidAbstractHeap);
224         switch (kind()) {
225         case World:
226             return AbstractHeap();
227         case Heap:
228         case SideState:
229             return World;
230         default:
231             if (payload().isTop()) {
232                 if (kind() == Stack)
233                     return World;
234                 return Heap;
235             }
236             return AbstractHeap(kind());
237         }
238     }
239     
240     bool isStrictSubtypeOf(const AbstractHeap& other) const
241     {
242         AbstractHeap current = *this;
243         if (current.kind() == DOMState && other.kind() == DOMState) {
244             Payload currentPayload = current.payload();
245             Payload otherPayload = other.payload();
246             if (currentPayload.isTop())
247                 return false;
248             if (otherPayload.isTop())
249                 return true;
250             return DOMJIT::HeapRange::fromRaw(currentPayload.value32()).isStrictSubtypeOf(DOMJIT::HeapRange::fromRaw(otherPayload.value32()));
251         }
252         while (current.kind() != World) {
253             current = current.supertype();
254             if (current == other)
255                 return true;
256         }
257         return false;
258     }
259     
260     bool isSubtypeOf(const AbstractHeap& other) const
261     {
262         return *this == other || isStrictSubtypeOf(other);
263     }
264     
265     bool overlaps(const AbstractHeap& other) const
266     {
267         return *this == other || isStrictSubtypeOf(other) || other.isStrictSubtypeOf(*this);
268     }
269     
270     bool isDisjoint(const AbstractHeap& other) const
271     {
272         return !overlaps(other);
273     }
274     
275     unsigned hash() const
276     {
277         return WTF::IntHash<int64_t>::hash(m_value);
278     }
279     
280     bool operator==(const AbstractHeap& other) const
281     {
282         return m_value == other.m_value;
283     }
284     
285     bool operator!=(const AbstractHeap& other) const
286     {
287         return !(*this == other);
288     }
289     
290     bool operator<(const AbstractHeap& other) const
291     {
292         if (kind() != other.kind())
293             return kind() < other.kind();
294         return payload() < other.payload();
295     }
296     
297     bool isHashTableDeletedValue() const
298     {
299         return kind() == InvalidAbstractHeap && payloadImpl().isTop();
300     }
301     
302     void dump(PrintStream& out) const;
303     
304 private:
305     static const unsigned valueShift = 15;
306     static const unsigned topShift = 14;
307     
308     Payload payloadImpl() const
309     {
310         return Payload((m_value >> topShift) & 1, m_value >> valueShift);
311     }
312     
313     static int64_t encode(AbstractHeapKind kind, Payload payload)
314     {
315         int64_t kindAsInt = static_cast<int64_t>(kind);
316         ASSERT(kindAsInt < (1 << topShift));
317         return kindAsInt | (static_cast<uint64_t>(payload.isTop()) << topShift) | (bitwise_cast<uint64_t>(payload.valueImpl()) << valueShift);
318     }
319     
320     // The layout of the value is:
321     // Low 14 bits: the Kind
322     // 15th bit: whether or not the payload is TOP.
323     // The upper bits: the payload.value().
324     int64_t m_value;
325 };
326
327 struct AbstractHeapHash {
328     static unsigned hash(const AbstractHeap& key) { return key.hash(); }
329     static bool equal(const AbstractHeap& a, const AbstractHeap& b) { return a == b; }
330     static const bool safeToCompareToEmptyOrDeleted = true;
331 };
332
333 } } // namespace JSC::DFG
334
335 namespace WTF {
336
337 void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
338
339 template<typename T> struct DefaultHash;
340 template<> struct DefaultHash<JSC::DFG::AbstractHeap> {
341     typedef JSC::DFG::AbstractHeapHash Hash;
342 };
343
344 template<typename T> struct HashTraits;
345 template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
346
347 } // namespace WTF
348
349 #endif // ENABLE(DFG_JIT)