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