1/*
2 * Copyright (C) 2011, 2013, 2014 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 "DFGCommon.h"
31#include "DFGUseKind.h"
32
33namespace JSC { namespace DFG {
34
35class AdjacencyList;
36
37class Edge {
38public:
39 explicit Edge(Node* node = 0, UseKind useKind = UntypedUse, ProofStatus proofStatus = NeedsCheck, KillStatus killStatus = DoesNotKill)
40#if USE(JSVALUE64)
41 : m_encodedWord(makeWord(node, useKind, proofStatus, killStatus))
42#else
43 : m_node(node)
44 , m_encodedWord(makeWord(useKind, proofStatus, killStatus))
45#endif
46 {
47 }
48
49#if USE(JSVALUE64)
50 Node* node() const { return bitwise_cast<Node*>(m_encodedWord >> shift()); }
51#else
52 Node* node() const { return m_node; }
53#endif
54
55 Node& operator*() const { return *node(); }
56 Node* operator->() const { return node(); }
57
58 void setNode(Node* node)
59 {
60#if USE(JSVALUE64)
61 m_encodedWord = makeWord(node, useKind(), proofStatus(), killStatus());
62#else
63 m_node = node;
64#endif
65 }
66
67 UseKind useKindUnchecked() const
68 {
69#if USE(JSVALUE64)
70 unsigned masked = m_encodedWord & (((1 << shift()) - 1));
71 unsigned shifted = masked >> 2;
72#else
73 unsigned shifted = static_cast<UseKind>(m_encodedWord) >> 2;
74#endif
75 ASSERT(shifted < static_cast<unsigned>(LastUseKind));
76 UseKind result = static_cast<UseKind>(shifted);
77 ASSERT(node() || result == UntypedUse);
78 return result;
79 }
80 UseKind useKind() const
81 {
82 ASSERT(node());
83 return useKindUnchecked();
84 }
85 void setUseKind(UseKind useKind)
86 {
87 ASSERT(node());
88#if USE(JSVALUE64)
89 m_encodedWord = makeWord(node(), useKind, proofStatus(), killStatus());
90#else
91 m_encodedWord = makeWord(useKind, proofStatus(), killStatus());
92#endif
93 }
94
95 ProofStatus proofStatusUnchecked() const
96 {
97 return proofStatusForIsProved(m_encodedWord & 1);
98 }
99 ProofStatus proofStatus() const
100 {
101 ASSERT(node());
102 return proofStatusUnchecked();
103 }
104 void setProofStatus(ProofStatus proofStatus)
105 {
106 ASSERT(node());
107#if USE(JSVALUE64)
108 m_encodedWord = makeWord(node(), useKind(), proofStatus, killStatus());
109#else
110 m_encodedWord = makeWord(useKind(), proofStatus, killStatus());
111#endif
112 }
113 bool isProved() const
114 {
115 return proofStatus() == IsProved;
116 }
117
118 bool willNotHaveCheck() const
119 {
120 return isProved() || shouldNotHaveTypeCheck(useKind());
121 }
122 bool willHaveCheck() const
123 {
124 return !willNotHaveCheck();
125 }
126
127 KillStatus killStatusUnchecked() const
128 {
129 return killStatusForDoesKill(m_encodedWord & 2);
130 }
131 KillStatus killStatus() const
132 {
133 ASSERT(node());
134 return killStatusUnchecked();
135 }
136 void setKillStatus(KillStatus killStatus)
137 {
138 ASSERT(node());
139#if USE(JSVALUE64)
140 m_encodedWord = makeWord(node(), useKind(), proofStatus(), killStatus);
141#else
142 m_encodedWord = makeWord(useKind(), proofStatus(), killStatus);
143#endif
144 }
145 bool doesKill() const { return DFG::doesKill(killStatus()); }
146
147 bool isSet() const { return !!node(); }
148
149 Edge sanitized() const
150 {
151 Edge result = *this;
152#if USE(JSVALUE64)
153 result.m_encodedWord = makeWord(node(), useKindUnchecked(), NeedsCheck, DoesNotKill);
154#else
155 result.m_encodedWord = makeWord(useKindUnchecked(), NeedsCheck, DoesNotKill);
156#endif
157 return result;
158 }
159
160 bool operator!() const { return !isSet(); }
161 explicit operator bool() const { return isSet(); }
162
163 bool operator==(Edge other) const
164 {
165#if USE(JSVALUE64)
166 return m_encodedWord == other.m_encodedWord;
167#else
168 return m_node == other.m_node && m_encodedWord == other.m_encodedWord;
169#endif
170 }
171 bool operator!=(Edge other) const
172 {
173 return !(*this == other);
174 }
175
176 void dump(PrintStream&) const;
177
178 unsigned hash() const
179 {
180#if USE(JSVALUE64)
181 return IntHash<uintptr_t>::hash(m_encodedWord);
182#else
183 return PtrHash<Node*>::hash(m_node) + m_encodedWord;
184#endif
185 }
186
187private:
188 friend class AdjacencyList;
189
190#if USE(JSVALUE64)
191 static constexpr uint32_t shift() { return 8; }
192
193 static uintptr_t makeWord(Node* node, UseKind useKind, ProofStatus proofStatus, KillStatus killStatus)
194 {
195 ASSERT(sizeof(node) == 8);
196 uintptr_t shiftedValue = bitwise_cast<uintptr_t>(node) << shift();
197 ASSERT((shiftedValue >> shift()) == bitwise_cast<uintptr_t>(node));
198 ASSERT(useKind >= 0 && useKind < LastUseKind);
199 static_assert((static_cast<uintptr_t>(LastUseKind) << 2) < (static_cast<uintptr_t>(1) << shift()), "We rely on this being true to not clobber the node pointer.");
200 uintptr_t result = shiftedValue | (static_cast<uintptr_t>(useKind) << 2) | (DFG::doesKill(killStatus) << 1) | static_cast<uintptr_t>(DFG::isProved(proofStatus));
201 if (!ASSERT_DISABLED) {
202 union U {
203 U() { word = 0; }
204 uintptr_t word;
205 Edge edge;
206 } u;
207 u.word = result;
208 ASSERT(u.edge.useKindUnchecked() == useKind);
209 ASSERT(u.edge.node() == node);
210 ASSERT(u.edge.proofStatusUnchecked() == proofStatus);
211 ASSERT(u.edge.killStatusUnchecked() == killStatus);
212 }
213 return result;
214 }
215
216#else
217 static uintptr_t makeWord(UseKind useKind, ProofStatus proofStatus, KillStatus killStatus)
218 {
219 return (static_cast<uintptr_t>(useKind) << 2) | (DFG::doesKill(killStatus) << 1) | static_cast<uintptr_t>(DFG::isProved(proofStatus));
220 }
221
222 Node* m_node;
223#endif
224 // On 64-bit this holds both the pointer and the use kind, while on 32-bit
225 // this just holds the use kind. In both cases this may be hijacked by
226 // AdjacencyList for storing firstChild and numChildren.
227 uintptr_t m_encodedWord;
228};
229
230inline bool operator==(Edge edge, Node* node)
231{
232 return edge.node() == node;
233}
234inline bool operator==(Node* node, Edge edge)
235{
236 return edge.node() == node;
237}
238inline bool operator!=(Edge edge, Node* node)
239{
240 return edge.node() != node;
241}
242inline bool operator!=(Node* node, Edge edge)
243{
244 return edge.node() != node;
245}
246
247} } // namespace JSC::DFG
248
249#endif // ENABLE(DFG_JIT)
250