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