1/*
2 * Copyright (C) 2011, 2013, 2015 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 "DFGEdge.h"
31
32namespace JSC { namespace DFG {
33
34class AdjacencyList {
35public:
36 enum Kind {
37 Fixed,
38 Variable
39 };
40
41 enum { Size = 3 };
42
43 AdjacencyList() { }
44
45 AdjacencyList(Kind kind)
46 {
47 if (kind == Variable) {
48 m_words[0].m_encodedWord = UINT_MAX;
49 m_words[1].m_encodedWord = UINT_MAX;
50 }
51 }
52
53 AdjacencyList(Kind kind, Edge child1, Edge child2 = Edge(), Edge child3 = Edge())
54 {
55 ASSERT_UNUSED(kind, kind == Fixed);
56 initialize(child1, child2, child3);
57 }
58
59 AdjacencyList(Kind kind, unsigned firstChild, unsigned numChildren)
60 {
61 ASSERT_UNUSED(kind, kind == Variable);
62 setFirstChild(firstChild);
63 setNumChildren(numChildren);
64 // We need to make sure this is the empty value so equivalent adjacency
65 // lists produce identical hashes.
66 m_words[2] = Edge();
67 }
68
69 bool isEmpty() const { return !child1(); }
70
71 const Edge& child(unsigned i) const
72 {
73 ASSERT(i < Size);
74 return m_words[i];
75 }
76
77 Edge& child(unsigned i)
78 {
79 ASSERT(i < Size);
80 return m_words[i];
81 }
82
83 void setChild(unsigned i, Edge nodeUse)
84 {
85 ASSERT(i < Size);
86 m_words[i] = nodeUse;
87 }
88
89 Edge child1() const { return child(0); }
90 Edge child2() const { return child(1); }
91 Edge child3() const { return child(2); }
92
93 Edge& child1() { return child(0); }
94 Edge& child2() { return child(1); }
95 Edge& child3() { return child(2); }
96
97 void setChild1(Edge nodeUse) { setChild(0, nodeUse); }
98 void setChild2(Edge nodeUse) { setChild(1, nodeUse); }
99 void setChild3(Edge nodeUse) { setChild(2, nodeUse); }
100
101 Edge child1Unchecked() const { return m_words[0]; }
102
103 void initialize(Edge child1, Edge child2, Edge child3)
104 {
105 child(0) = child1;
106 child(1) = child2;
107 child(2) = child3;
108 }
109
110 void initialize(Node* child1 = 0, Node* child2 = 0, Node* child3 = 0)
111 {
112 initialize(Edge(child1), Edge(child2), Edge(child3));
113 }
114
115 void reset()
116 {
117 initialize();
118 }
119
120 // Call this if you wish to remove an edge and the node treats the list of children.
121 void removeEdge(unsigned edgeIndex)
122 {
123 for (unsigned i = edgeIndex; i < Size - 1; ++i)
124 setChild(i, child(i + 1));
125 setChild(Size - 1, Edge());
126 }
127
128 unsigned firstChild() const
129 {
130 return m_words[0].m_encodedWord;
131 }
132 void setFirstChild(unsigned firstChild)
133 {
134 m_words[0].m_encodedWord = firstChild;
135 }
136
137 unsigned numChildren() const
138 {
139 return m_words[1].m_encodedWord;
140 }
141 void setNumChildren(unsigned numChildren)
142 {
143 m_words[1].m_encodedWord = numChildren;
144 }
145
146 AdjacencyList sanitized() const
147 {
148 return AdjacencyList(Fixed, child1().sanitized(), child2().sanitized(), child3().sanitized());
149 }
150
151 AdjacencyList justChecks() const
152 {
153 AdjacencyList result(Fixed);
154 unsigned sourceIndex = 0;
155 unsigned targetIndex = 0;
156 while (sourceIndex < AdjacencyList::Size) {
157 Edge edge = child(sourceIndex++);
158 if (!edge)
159 break;
160 if (edge.willHaveCheck())
161 result.child(targetIndex++) = edge;
162 }
163 return result;
164 }
165
166 unsigned hash() const
167 {
168 unsigned result = 0;
169 if (!child1())
170 return result;
171
172 result += child1().hash();
173
174 if (!child2())
175 return result;
176
177 result *= 3;
178 result += child2().hash();
179
180 if (!child3())
181 return result;
182
183 result *= 3;
184 result += child3().hash();
185
186 return result;
187 }
188
189 bool operator==(const AdjacencyList& other) const
190 {
191 return child1() == other.child1()
192 && child2() == other.child2()
193 && child3() == other.child3();
194 }
195
196private:
197 Edge m_words[Size];
198};
199
200} } // namespace JSC::DFG
201
202#endif // ENABLE(DFG_JIT)
203