1 /*
2 * Copyright (c) 2014, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.graph;
26
27 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
28 import static org.graalvm.compiler.graph.Node.NOT_ITERABLE;
29
30 import java.util.ArrayList;
31 import java.util.Iterator;
32
33 import org.graalvm.compiler.core.common.Fields;
34 import org.graalvm.compiler.core.common.FieldsScanner;
35 import org.graalvm.compiler.graph.NodeClass.EdgeInfo;
36 import org.graalvm.compiler.serviceprovider.GraalUnsafeAccess;
37
38 import sun.misc.Unsafe;
39
40 /**
41 * Describes {@link Node} fields representing the set of inputs for the node or the set of the
42 * node's successors.
43 */
44 public abstract class Edges extends Fields {
45
46 private static final Unsafe UNSAFE = GraalUnsafeAccess.getUnsafe();
47
48 /**
49 * Constants denoting whether a set of edges are inputs or successors.
50 */
51 public enum Type {
52 Inputs,
53 Successors;
54 }
55
56 private final int directCount;
57 private final Type type;
58
59 public Edges(Type type, int directCount, ArrayList<? extends FieldsScanner.FieldInfo> edges) {
60 super(edges);
61 this.type = type;
62 this.directCount = directCount;
63 }
64
65 public static void translateInto(Edges edges, ArrayList<EdgeInfo> infos) {
66 for (int index = 0; index < edges.getCount(); index++) {
67 infos.add(new EdgeInfo(edges.offsets[index], edges.getName(index), edges.getType(index), edges.getDeclaringClass(index)));
68 }
69 }
70
71 public static Node getNodeUnsafe(Node node, long offset) {
72 return (Node) UNSAFE.getObject(node, offset);
73 }
74
75 @SuppressWarnings("unchecked")
76 public static NodeList<Node> getNodeListUnsafe(Node node, long offset) {
77 return (NodeList<Node>) UNSAFE.getObject(node, offset);
78 }
79
80 public static void putNodeUnsafe(Node node, long offset, Node value) {
81 UNSAFE.putObject(node, offset, value);
82 }
83
84 public static void putNodeListUnsafe(Node node, long offset, NodeList<?> value) {
85 UNSAFE.putObject(node, offset, value);
86 }
87
88 /**
89 * Get the number of direct edges represented by this object. A direct edge goes directly to
90 * another {@link Node}. An indirect edge goes via a {@link NodeList}.
91 */
92 public int getDirectCount() {
93 return directCount;
94 }
95
96 /**
97 * Gets the {@link Node} at the end point of a {@linkplain #getDirectCount() direct} edge.
98 *
99 * @param node one end point of the edge
100 * @param index the index of a non-list the edge (must be less than {@link #getDirectCount()})
101 * @return the Node at the other edge of the requested edge
102 */
103 public static Node getNode(Node node, long[] offsets, int index) {
104 return getNodeUnsafe(node, offsets[index]);
105 }
106
107 /**
108 * Gets the {@link NodeList} at the end point of a {@linkplain #getDirectCount() direct} edge.
109 *
110 * @param node one end point of the edge
111 * @param index the index of a non-list the edge (must be equal to or greater than
112 * {@link #getDirectCount()})
113 * @return the {@link NodeList} at the other edge of the requested edge
114 */
115 public static NodeList<Node> getNodeList(Node node, long[] offsets, int index) {
116 return getNodeListUnsafe(node, offsets[index]);
117 }
118
119 /**
120 * Clear edges in a given node. This is accomplished by setting {@linkplain #getDirectCount()
121 * direct} edges to null and replacing the lists containing indirect edges with new lists. The
122 * latter is important so that this method can be used to clear the edges of cloned nodes.
123 *
124 * @param node the node whose edges are to be cleared
125 */
126 public void clear(Node node) {
127 final long[] curOffsets = this.offsets;
128 final Type curType = this.type;
129 int index = 0;
130 int curDirectCount = getDirectCount();
131 while (index < curDirectCount) {
132 initializeNode(node, index++, null);
133 }
134 int curCount = getCount();
135 while (index < curCount) {
136 NodeList<Node> list = getNodeList(node, curOffsets, index);
137 if (list != null) {
138 int size = list.initialSize;
139 NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
140
141 // replacing with a new list object is the expected behavior!
142 initializeList(node, index, newList);
143 }
144 index++;
145 }
146 }
147
148 /**
149 * Initializes the list edges in a given node based on the size of the list edges in a prototype
150 * node.
151 *
152 * @param node the node whose list edges are to be initialized
153 * @param prototype the node whose list edge sizes are used when creating new edge lists
154 */
155 public void initializeLists(Node node, Node prototype) {
156 int index = getDirectCount();
157 final long[] curOffsets = this.offsets;
158 final Edges.Type curType = this.type;
159 while (index < getCount()) {
160 NodeList<Node> list = getNodeList(prototype, curOffsets, index);
161 if (list != null) {
162 int size = list.initialSize;
163 NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
164 initializeList(node, index, newList);
165 }
166 index++;
167 }
168 }
169
170 /**
171 * Copies edges from {@code fromNode} to {@code toNode}. The nodes are expected to be of the
172 * exact same type.
173 *
174 * @param fromNode the node from which the edges should be copied.
175 * @param toNode the node to which the edges should be copied.
176 */
177 public void copy(Node fromNode, Node toNode) {
178 assert fromNode != toNode;
179 assert fromNode.getNodeClass().getClazz() == toNode.getNodeClass().getClazz();
180 int index = 0;
181 final long[] curOffsets = this.offsets;
182 final Type curType = this.type;
183 int curDirectCount = getDirectCount();
184 while (index < curDirectCount) {
185 initializeNode(toNode, index, getNode(fromNode, curOffsets, index));
186 index++;
187 }
188 int curCount = getCount();
189 while (index < curCount) {
190 NodeList<Node> list = getNodeList(toNode, curOffsets, index);
191 NodeList<Node> fromList = getNodeList(fromNode, curOffsets, index);
192 if (list == null || list == fromList) {
193 list = curType == Edges.Type.Inputs ? new NodeInputList<>(toNode, fromList) : new NodeSuccessorList<>(toNode, fromList);
194 initializeList(toNode, index, list);
195 } else {
196 list.copy(fromList);
197 }
198 index++;
199 }
200 }
201
202 @Override
203 public void set(Object node, int index, Object value) {
204 throw new IllegalArgumentException("Cannot call set on " + this);
205 }
206
207 /**
208 * Sets the value of a given edge without notifying the new and old nodes on the other end of
209 * the edge of the change.
210 *
211 * @param node the node whose edge is to be updated
212 * @param index the index of the edge (between 0 and {@link #getCount()})
213 * @param value the node to be written to the edge
214 */
215 public void initializeNode(Node node, int index, Node value) {
216 verifyUpdateValid(node, index, value);
217 putNodeUnsafe(node, offsets[index], value);
218 }
219
220 public void initializeList(Node node, int index, NodeList<Node> value) {
221 verifyUpdateValid(node, index, value);
222 putNodeListUnsafe(node, offsets[index], value);
223 }
224
225 private void verifyUpdateValid(Node node, int index, Object newValue) {
226 if (newValue != null && !getType(index).isAssignableFrom(newValue.getClass())) {
227 throw new IllegalArgumentException("Can not assign " + newValue.getClass() + " to " + getType(index) + " in " + node);
228 }
229 }
230
231 /**
232 * Sets the value of a given edge and notifies the new and old nodes on the other end of the
233 * edge of the change.
234 *
235 * @param node the node whose edge is to be updated
236 * @param index the index of the edge (between 0 and {@link #getCount()})
237 * @param value the node to be written to the edge
238 */
239 public void setNode(Node node, int index, Node value) {
240 assert index < directCount;
241 Node old = getNodeUnsafe(node, offsets[index]);
242 initializeNode(node, index, value);
243 update(node, old, value);
244 }
245
246 public abstract void update(Node node, Node oldValue, Node newValue);
247
248 public boolean contains(Node node, Node value) {
249 final long[] curOffsets = this.offsets;
250 for (int i = 0; i < directCount; i++) {
251 if (getNode(node, curOffsets, i) == value) {
252 return true;
253 }
254 }
255 for (int i = directCount; i < getCount(); i++) {
256 NodeList<?> curList = getNodeList(node, curOffsets, i);
257 if (curList != null && curList.contains(value)) {
258 return true;
259 }
260 }
261 return false;
262 }
263
264 /**
265 * An iterator that will iterate over edges.
266 *
267 * An iterator of this type will not return null values, unless edges are modified concurrently.
268 * Concurrent modifications are detected by an assertion on a best-effort basis.
269 */
270 private static class EdgesIterator implements Iterator<Position> {
271 protected final Node node;
272 protected final Edges edges;
273 protected int index;
274 protected int subIndex;
275 protected boolean needsForward;
276 protected final int directCount;
277 protected final long[] offsets;
278
279 /**
280 * Creates an iterator that will iterate over some given edges in a given node.
281 */
282 EdgesIterator(Node node, Edges edges) {
283 this.node = node;
284 this.edges = edges;
285 index = NOT_ITERABLE;
286 subIndex = 0;
287 needsForward = true;
288 this.directCount = edges.getDirectCount();
289 this.offsets = edges.getOffsets();
290 }
291
292 void forward() {
293 needsForward = false;
294 if (index < directCount) {
295 index++;
296 if (index < directCount) {
297 return;
298 }
299 } else {
300 subIndex++;
301 }
302 if (index < edges.getCount()) {
303 forwardNodeList();
304 }
305 }
306
307 private void forwardNodeList() {
308 do {
309 NodeList<?> list = Edges.getNodeList(node, offsets, index);
310 if (list != null) {
311 if (subIndex < list.size()) {
312 return;
313 }
314 }
315 subIndex = 0;
316 index++;
317 } while (index < edges.getCount());
318 }
319
320 @Override
321 public boolean hasNext() {
322 if (needsForward) {
323 forward();
324 }
325 return index < edges.getCount();
326 }
327
328 @Override
329 public Position next() {
330 if (needsForward) {
331 forward();
332 }
333 needsForward = true;
334 if (index < directCount) {
335 return new Position(edges, index, NOT_ITERABLE);
336 } else {
337 return new Position(edges, index, subIndex);
338 }
339 }
340
341 @Override
342 public void remove() {
343 throw new UnsupportedOperationException();
344 }
345 }
346
347 private static final class EdgesWithModCountIterator extends EdgesIterator {
348 private final int modCount;
349
350 private EdgesWithModCountIterator(Node node, Edges edges) {
351 super(node, edges);
352 assert isModificationCountsEnabled();
353 this.modCount = node.modCount();
354 }
355
356 @Override
357 public boolean hasNext() {
358 try {
359 return super.hasNext();
360 } finally {
361 assert modCount == node.modCount() : "must not be modified";
362 }
363 }
364
365 @Override
366 public Position next() {
367 try {
368 return super.next();
369 } finally {
370 assert modCount == node.modCount() : "must not be modified";
371 }
372 }
373 }
374
375 public Iterable<Position> getPositionsIterable(final Node node) {
376 return new Iterable<Position>() {
377
378 @Override
379 public Iterator<Position> iterator() {
380 if (isModificationCountsEnabled()) {
381 return new EdgesWithModCountIterator(node, Edges.this);
382 } else {
383 return new EdgesIterator(node, Edges.this);
384 }
385 }
386 };
387 }
388
389 public Type type() {
390 return type;
391 }
392 }