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