blob: c8750cf6a32525123db9405bd8155248b9a83c5b [file] [log] [blame]
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +00001/*
fpizlo@apple.com163291d2015-04-28 19:27:23 +00002 * Copyright (C) 2011, 2013, 2015 Apple Inc. All rights reserved.
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +00003 *
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
ryanhaddad@apple.com22104f52016-09-28 17:08:17 +000026#pragma once
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000027
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000028#if ENABLE(DFG_JIT)
29
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000030#include "DFGEdge.h"
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000031
32namespace JSC { namespace DFG {
33
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000034class AdjacencyList {
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000035public:
36 enum Kind {
37 Fixed,
38 Variable
39 };
fpizlo@apple.com79c51ee2012-05-18 22:30:24 +000040
41 enum { Size = 3 };
42
fpizlo@apple.comd8dd0532012-09-13 04:18:52 +000043 AdjacencyList() { }
44
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000045 AdjacencyList(Kind kind)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000046 {
47 if (kind == Variable) {
48 m_words[0].m_encodedWord = UINT_MAX;
49 m_words[1].m_encodedWord = UINT_MAX;
50 }
51 }
52
fpizlo@apple.com2c4a7e92014-08-06 05:27:46 +000053 AdjacencyList(Kind kind, Edge child1, Edge child2 = Edge(), Edge child3 = Edge())
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000054 {
55 ASSERT_UNUSED(kind, kind == Fixed);
56 initialize(child1, child2, child3);
57 }
58
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000059 AdjacencyList(Kind kind, unsigned firstChild, unsigned numChildren)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000060 {
61 ASSERT_UNUSED(kind, kind == Variable);
62 setFirstChild(firstChild);
63 setNumChildren(numChildren);
sbarati@apple.come2cdd872018-02-13 01:12:28 +000064 // We need to make sure this is the empty value so equivalent adjacency
65 // lists produce identical hashes.
66 m_words[2] = Edge();
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000067 }
68
fpizlo@apple.comb41e6822014-07-25 20:55:17 +000069 bool isEmpty() const { return !child1(); }
70
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000071 const Edge& child(unsigned i) const
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000072 {
fpizlo@apple.com79c51ee2012-05-18 22:30:24 +000073 ASSERT(i < Size);
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000074 return m_words[i];
75 }
76
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000077 Edge& child(unsigned i)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000078 {
fpizlo@apple.com79c51ee2012-05-18 22:30:24 +000079 ASSERT(i < Size);
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000080 return m_words[i];
81 }
82
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000083 void setChild(unsigned i, Edge nodeUse)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000084 {
fpizlo@apple.com79c51ee2012-05-18 22:30:24 +000085 ASSERT(i < Size);
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000086 m_words[i] = nodeUse;
87 }
88
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000089 Edge child1() const { return child(0); }
90 Edge child2() const { return child(1); }
91 Edge child3() const { return child(2); }
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000092
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000093 Edge& child1() { return child(0); }
94 Edge& child2() { return child(1); }
95 Edge& child3() { return child(2); }
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +000096
fpizlo@apple.come5abbae2012-03-19 21:44:23 +000097 void setChild1(Edge nodeUse) { setChild(0, nodeUse); }
98 void setChild2(Edge nodeUse) { setChild(1, nodeUse); }
99 void setChild3(Edge nodeUse) { setChild(2, nodeUse); }
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000100
fpizlo@apple.come5abbae2012-03-19 21:44:23 +0000101 Edge child1Unchecked() const { return m_words[0]; }
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000102
oliver@apple.com827d2cf2013-07-25 04:04:45 +0000103 Edge justOneChild() const
104 {
105 if (!!child1() && !child2()) {
106 ASSERT(!child3());
107 return child1();
108 }
109 return Edge();
110 }
111
fpizlo@apple.come5abbae2012-03-19 21:44:23 +0000112 void initialize(Edge child1, Edge child2, Edge child3)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000113 {
114 child(0) = child1;
115 child(1) = child2;
116 child(2) = child3;
117 }
118
fpizlo@apple.com8ff092f2013-01-29 08:01:03 +0000119 void initialize(Node* child1 = 0, Node* child2 = 0, Node* child3 = 0)
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000120 {
fpizlo@apple.come5abbae2012-03-19 21:44:23 +0000121 initialize(Edge(child1), Edge(child2), Edge(child3));
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000122 }
fpizlo@apple.com3187c922012-05-18 21:47:53 +0000123
124 void reset()
125 {
fpizlo@apple.com3187c922012-05-18 21:47:53 +0000126 initialize();
127 }
fpizlo@apple.com9a548f12012-05-24 05:33:09 +0000128
fpizlo@apple.com4463e442013-03-20 20:29:37 +0000129 // Call this if you wish to remove an edge and the node treats the list of children.
130 void removeEdge(unsigned edgeIndex)
fpizlo@apple.com9a548f12012-05-24 05:33:09 +0000131 {
132 for (unsigned i = edgeIndex; i < Size - 1; ++i)
133 setChild(i, child(i + 1));
134 setChild(Size - 1, Edge());
135 }
fpizlo@apple.com2c4a7e92014-08-06 05:27:46 +0000136
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000137 unsigned firstChild() const
138 {
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000139 return m_words[0].m_encodedWord;
140 }
141 void setFirstChild(unsigned firstChild)
142 {
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000143 m_words[0].m_encodedWord = firstChild;
144 }
145
146 unsigned numChildren() const
147 {
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000148 return m_words[1].m_encodedWord;
149 }
150 void setNumChildren(unsigned numChildren)
151 {
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000152 m_words[1].m_encodedWord = numChildren;
153 }
154
fpizlo@apple.com2c4a7e92014-08-06 05:27:46 +0000155 AdjacencyList sanitized() const
156 {
157 return AdjacencyList(Fixed, child1().sanitized(), child2().sanitized(), child3().sanitized());
158 }
159
fpizlo@apple.com163291d2015-04-28 19:27:23 +0000160 AdjacencyList justChecks() const
161 {
162 AdjacencyList result(Fixed);
163 unsigned sourceIndex = 0;
164 unsigned targetIndex = 0;
165 while (sourceIndex < AdjacencyList::Size) {
166 Edge edge = child(sourceIndex++);
167 if (!edge)
168 break;
169 if (edge.willHaveCheck())
170 result.child(targetIndex++) = edge;
171 }
172 return result;
173 }
174
fpizlo@apple.com2c4a7e92014-08-06 05:27:46 +0000175 unsigned hash() const
176 {
177 unsigned result = 0;
178 if (!child1())
179 return result;
180
181 result += child1().hash();
182
183 if (!child2())
184 return result;
185
186 result *= 3;
187 result += child2().hash();
188
189 if (!child3())
190 return result;
191
192 result *= 3;
193 result += child3().hash();
194
195 return result;
196 }
197
198 bool operator==(const AdjacencyList& other) const
199 {
200 return child1() == other.child1()
201 && child2() == other.child2()
202 && child3() == other.child3();
203 }
204
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000205private:
fpizlo@apple.com79c51ee2012-05-18 22:30:24 +0000206 Edge m_words[Size];
fpizlo@apple.com1996b4b2012-02-06 06:44:24 +0000207};
208
209} } // namespace JSC::DFG
210
211#endif // ENABLE(DFG_JIT)