1/*
2 * Copyright (C) 2013-2019 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
35namespace 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(DirectArgumentsProperties) \
69 macro(ScopeProperties) \
70 macro(TypedArrayProperties) \
71 macro(HeapObjectCount) /* Used to reflect the fact that some allocations reveal object identity */\
72 macro(RegExpState) \
73 macro(MathDotRandomState) \
74 macro(JSDateFields) \
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
92enum AbstractHeapKind {
93#define ABSTRACT_HEAP_DECLARATION(name) name,
94 FOR_EACH_ABSTRACT_HEAP_KIND(ABSTRACT_HEAP_DECLARATION)
95#undef ABSTRACT_HEAP_DECLARATION
96};
97
98class AbstractHeap {
99public:
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
306private:
307 static constexpr unsigned valueShift = 15;
308 static constexpr 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
329struct 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 constexpr bool safeToCompareToEmptyOrDeleted = true;
333};
334
335} } // namespace JSC::DFG
336
337namespace WTF {
338
339void printInternal(PrintStream&, JSC::DFG::AbstractHeapKind);
340
341template<typename T> struct DefaultHash;
342template<> struct DefaultHash<JSC::DFG::AbstractHeap> {
343 typedef JSC::DFG::AbstractHeapHash Hash;
344};
345
346template<typename T> struct HashTraits;
347template<> struct HashTraits<JSC::DFG::AbstractHeap> : SimpleClassHashTraits<JSC::DFG::AbstractHeap> { };
348
349} // namespace WTF
350
351#endif // ENABLE(DFG_JIT)
352