881d99f135ab9ea9e6db20507863c223d27d5e75
[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(JSPromiseFields) \
80     macro(InternalState) \
81     macro(CatchLocals) \
82     macro(Absolute) \
83     /* DOMJIT tells the heap range with the pair of integers. */\
84     macro(DOMState) \
85     /* 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. */\
86     macro(Watchpoint_fire) \
87     /* Use these for reads only, just to indicate that if the world got clobbered, then this operation will not work. */\
88     macro(MiscFields) \
89     /* 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. */\
90     macro(SideState)
91
92 enum AbstractHeapKind {
93 #define ABSTRACT_HEAP_DECLARATION(name) name,
94     FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
95 #undef ABSTRACT_HEAP_DECLARATION
96 };
97
98 class AbstractHeap {
99 public:
100     class Payload {
101     public:
102         Payload()
103             : m_isTop(false)
104             , m_value(0)
105         {
106         }
107         
108         Payload(bool isTop, int64_t value)
109             : m_isTop(isTop)
110             , m_value(value)
111         {
112             ASSERT(!(isTop && value));
113         }
114         
115         Payload(int64_t value)
116             : m_isTop(false)
117             , m_value(value)
118         {
119         }
120         
121         Payload(const void* pointer)
122             : m_isTop(false)
123             , m_value(bitwise_cast<intptr_t>(pointer))
124         {
125         }
126         
127         Payload(VirtualRegister operand)
128             : m_isTop(false)
129             , m_value(operand.offset())
130         {
131         }
132         
133         static Payload top() { return Payload(true, 0); }
134         
135         bool isTop() const { return m_isTop; }
136         int64_t value() const
137         {
138             ASSERT(!isTop());
139             return valueImpl();
140         }
141         int64_t valueImpl() const
142         {
143             return m_value;
144         }
145         
146         int32_t value32() const
147         {
148             return static_cast<int32_t>(value());
149         }
150         
151         bool operator==(const Payload& other) const
152         {
153             return m_isTop == other.m_isTop
154                 && m_value == other.m_value;
155         }
156         
157         bool operator!=(const Payload& other) const
158         {
159             return !(*this == other);
160         }
161         
162         bool operator<(const Payload& other) const
163         {
164             if (isTop())
165                 return !other.isTop();
166             if (other.isTop())
167                 return false;
168             return value() < other.value();
169         }
170         
171         bool isDisjoint(const Payload& other) const
172         {
173             if (isTop())
174                 return false;
175             if (other.isTop())
176                 return false;
177             return m_value != other.m_value;
178         }
179         
180         bool overlaps(const Payload& other) const
181         {
182             return !isDisjoint(other);
183         }
184         
185         void dump(PrintStream&) const;
186         
187     private:
188         bool m_isTop;
189         int64_t m_value;
190     };
191     
192     AbstractHeap()
193     {
194         m_value = encode(InvalidAbstractHeap, Payload());
195     }
196     
197     AbstractHeap(AbstractHeapKind kind)
198     {
199         ASSERT(kind != InvalidAbstractHeap);
200         m_value = encode(kind, Payload::top());
201     }
202     
203     AbstractHeap(AbstractHeapKind kind, Payload payload)
204     {
205         ASSERT(kind != InvalidAbstractHeap && kind != World && kind != Heap && kind != SideState);
206         m_value = encode(kind, payload);
207     }
208     
209     AbstractHeap(WTF::HashTableDeletedValueType)
210     {
211         m_value = encode(InvalidAbstractHeap, Payload::top());
212     }
213     
214     bool operator!() const { return kind() == InvalidAbstractHeap && !payloadImpl().isTop(); }
215     
216     AbstractHeapKind kind() const { return static_cast<AbstractHeapKind>(m_value & ((1 << topShift) - 1)); }
217     Payload payload() const
218     {
219         ASSERT(kind() != World && kind() != InvalidAbstractHeap);
220         return payloadImpl();
221     }
222     
223     AbstractHeap supertype() const
224     {
225         ASSERT(kind() != InvalidAbstractHeap);
226         switch (kind()) {
227         case World:
228             return AbstractHeap();
229         case Heap:
230         case SideState:
231             return World;
232         default:
233             if (payload().isTop()) {
234                 if (kind() == Stack)
235                     return World;
236                 return Heap;
237             }
238             return AbstractHeap(kind());
239         }
240     }
241     
242     bool isStrictSubtypeOf(const AbstractHeap& other) const
243     {
244         AbstractHeap current = *this;
245         if (current.kind() == DOMState && other.kind() == DOMState) {
246             Payload currentPayload = current.payload();
247             Payload otherPayload = other.payload();
248             if (currentPayload.isTop())
249                 return false;
250             if (otherPayload.isTop())
251                 return true;
252             return DOMJIT::HeapRange::fromRaw(currentPayload.value32()).isStrictSubtypeOf(DOMJIT::HeapRange::fromRaw(otherPayload.value32()));
253         }
254         while (current.kind() != World) {
255             current = current.supertype();
256             if (current == other)
257                 return true;
258         }
259         return false;
260     }
261     
262     bool isSubtypeOf(const AbstractHeap& other) const
263     {
264         return *this == other || isStrictSubtypeOf(other);
265     }
266     
267     bool overlaps(const AbstractHeap& other) const
268     {
269         return *this == other || isStrictSubtypeOf(other) || other.isStrictSubtypeOf(*this);
270     }
271     
272     bool isDisjoint(const AbstractHeap& other) const
273     {
274         return !overlaps(other);
275     }
276     
277     unsigned hash() const
278     {
279         return WTF::IntHash<int64_t>::hash(m_value);
280     }
281     
282     bool operator==(const AbstractHeap& other) const
283     {
284         return m_value == other.m_value;
285     }
286     
287     bool operator!=(const AbstractHeap& other) const
288     {
289         return !(*this == other);
290     }
291     
292     bool operator<(const AbstractHeap& other) const
293     {
294         if (kind() != other.kind())
295             return kind() < other.kind();
296         return payload() < other.payload();
297     }
298     
299     bool isHashTableDeletedValue() const
300     {
301         return kind() == InvalidAbstractHeap && payloadImpl().isTop();
302     }
303     
304     void dump(PrintStream& out) const;
305     
306 private:
307     static const unsigned valueShift = 15;
308     static const unsigned topShift = 14;
309     
310     Payload payloadImpl() const
311     {
312         return Payload((m_value >> topShift) & 1, m_value >> valueShift);
313     }
314     
315     static int64_t encode(AbstractHeapKind kind, Payload payload)
316     {
317         int64_t kindAsInt = static_cast<int64_t>(kind);
318         ASSERT(kindAsInt < (1 << topShift));
319         return kindAsInt | (static_cast<uint64_t>(payload.isTop()) << topShift) | (bitwise_cast<uint64_t>(payload.valueImpl()) << valueShift);
320     }
321     
322     // The layout of the value is:
323     // Low 14 bits: the Kind
324     // 15th bit: whether or not the payload is TOP.
325     // The upper bits: the payload.value().
326     int64_t m_value;
327 };
328
329 struct AbstractHeapHash {
330     static unsigned hash(const AbstractHeap& key) { return key.hash(); }
331     static bool equal(const AbstractHeap& a, const AbstractHeap& b) { return a == b; }
332     static const bool safeToCompareToEmptyOrDeleted = true;
333 };
334
335 } } // namespace JSC::DFG
336
337 namespace WTF {
338
339 void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
340
341 template<typename T> struct DefaultHash;
342 template<> struct DefaultHash<JSC::DFG::AbstractHeap> {
343     typedef JSC::DFG::AbstractHeapHash Hash;
344 };
345
346 template<typename T> struct HashTraits;
347 template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
348
349 } // namespace WTF
350
351 #endif // ENABLE(DFG_JIT)