/*
 * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */


package org.graalvm.compiler.graph;

import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
import static org.graalvm.compiler.graph.Node.NOT_ITERABLE;
import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;

import java.util.ArrayList;
import java.util.Iterator;

import org.graalvm.compiler.core.common.Fields;
import org.graalvm.compiler.core.common.FieldsScanner;
import org.graalvm.compiler.graph.NodeClass.EdgeInfo;

Describes Node fields representing the set of inputs for the node or the set of the node's successors.
/** * Describes {@link Node} fields representing the set of inputs for the node or the set of the * node's successors. */
public abstract class Edges extends Fields {
Constants denoting whether a set of edges are inputs or successors.
/** * Constants denoting whether a set of edges are inputs or successors. */
public enum Type { Inputs, Successors; } private final int directCount; private final Type type; public Edges(Type type, int directCount, ArrayList<? extends FieldsScanner.FieldInfo> edges) { super(edges); this.type = type; this.directCount = directCount; } public static void translateInto(Edges edges, ArrayList<EdgeInfo> infos) { for (int index = 0; index < edges.getCount(); index++) { infos.add(new EdgeInfo(edges.offsets[index], edges.getName(index), edges.getType(index), edges.getDeclaringClass(index))); } } public static Node getNodeUnsafe(Node node, long offset) { return (Node) UNSAFE.getObject(node, offset); } @SuppressWarnings("unchecked") public static NodeList<Node> getNodeListUnsafe(Node node, long offset) { return (NodeList<Node>) UNSAFE.getObject(node, offset); } public static void putNodeUnsafe(Node node, long offset, Node value) { UNSAFE.putObject(node, offset, value); } public static void putNodeListUnsafe(Node node, long offset, NodeList<?> value) { UNSAFE.putObject(node, offset, value); }
Get the number of direct edges represented by this object. A direct edge goes directly to another Node. An indirect edge goes via a NodeList.
/** * Get the number of direct edges represented by this object. A direct edge goes directly to * another {@link Node}. An indirect edge goes via a {@link NodeList}. */
public int getDirectCount() { return directCount; }
Gets the Node at the end point of a direct edge.
Params:
  • node – one end point of the edge
  • index – the index of a non-list the edge (must be less than getDirectCount())
Returns:the Node at the other edge of the requested edge
/** * Gets the {@link Node} at the end point of a {@linkplain #getDirectCount() direct} edge. * * @param node one end point of the edge * @param index the index of a non-list the edge (must be less than {@link #getDirectCount()}) * @return the Node at the other edge of the requested edge */
public static Node getNode(Node node, long[] offsets, int index) { return getNodeUnsafe(node, offsets[index]); }
Gets the NodeList at the end point of a direct edge.
Params:
  • node – one end point of the edge
  • index – the index of a non-list the edge (must be equal to or greater than getDirectCount())
Returns:the NodeList at the other edge of the requested edge
/** * Gets the {@link NodeList} at the end point of a {@linkplain #getDirectCount() direct} edge. * * @param node one end point of the edge * @param index the index of a non-list the edge (must be equal to or greater than * {@link #getDirectCount()}) * @return the {@link NodeList} at the other edge of the requested edge */
public static NodeList<Node> getNodeList(Node node, long[] offsets, int index) { return getNodeListUnsafe(node, offsets[index]); }
Clear edges in a given node. This is accomplished by setting direct edges to null and replacing the lists containing indirect edges with new lists. The latter is important so that this method can be used to clear the edges of cloned nodes.
Params:
  • node – the node whose edges are to be cleared
/** * Clear edges in a given node. This is accomplished by setting {@linkplain #getDirectCount() * direct} edges to null and replacing the lists containing indirect edges with new lists. The * latter is important so that this method can be used to clear the edges of cloned nodes. * * @param node the node whose edges are to be cleared */
public void clear(Node node) { final long[] curOffsets = this.offsets; final Type curType = this.type; int index = 0; int curDirectCount = getDirectCount(); while (index < curDirectCount) { initializeNode(node, index++, null); } int curCount = getCount(); while (index < curCount) { NodeList<Node> list = getNodeList(node, curOffsets, index); if (list != null) { int size = list.initialSize; NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size); // replacing with a new list object is the expected behavior! initializeList(node, index, newList); } index++; } }
Initializes the list edges in a given node based on the size of the list edges in a prototype node.
Params:
  • node – the node whose list edges are to be initialized
  • prototype – the node whose list edge sizes are used when creating new edge lists
/** * Initializes the list edges in a given node based on the size of the list edges in a prototype * node. * * @param node the node whose list edges are to be initialized * @param prototype the node whose list edge sizes are used when creating new edge lists */
public void initializeLists(Node node, Node prototype) { int index = getDirectCount(); final long[] curOffsets = this.offsets; final Edges.Type curType = this.type; while (index < getCount()) { NodeList<Node> list = getNodeList(prototype, curOffsets, index); if (list != null) { int size = list.initialSize; NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size); initializeList(node, index, newList); } index++; } }
Copies edges from fromNode to toNode. The nodes are expected to be of the exact same type.
Params:
  • fromNode – the node from which the edges should be copied.
  • toNode – the node to which the edges should be copied.
/** * Copies edges from {@code fromNode} to {@code toNode}. The nodes are expected to be of the * exact same type. * * @param fromNode the node from which the edges should be copied. * @param toNode the node to which the edges should be copied. */
public void copy(Node fromNode, Node toNode) { assert fromNode != toNode; assert fromNode.getNodeClass().getClazz() == toNode.getNodeClass().getClazz(); int index = 0; final long[] curOffsets = this.offsets; final Type curType = this.type; int curDirectCount = getDirectCount(); while (index < curDirectCount) { initializeNode(toNode, index, getNode(fromNode, curOffsets, index)); index++; } int curCount = getCount(); while (index < curCount) { NodeList<Node> list = getNodeList(toNode, curOffsets, index); NodeList<Node> fromList = getNodeList(fromNode, curOffsets, index); if (list == null || list == fromList) { list = curType == Edges.Type.Inputs ? new NodeInputList<>(toNode, fromList) : new NodeSuccessorList<>(toNode, fromList); initializeList(toNode, index, list); } else { list.copy(fromList); } index++; } } @Override public void set(Object node, int index, Object value) { throw new IllegalArgumentException("Cannot call set on " + this); }
Sets the value of a given edge without notifying the new and old nodes on the other end of the edge of the change.
Params:
  • node – the node whose edge is to be updated
  • index – the index of the edge (between 0 and Fields.getCount())
  • value – the node to be written to the edge
/** * Sets the value of a given edge without notifying the new and old nodes on the other end of * the edge of the change. * * @param node the node whose edge is to be updated * @param index the index of the edge (between 0 and {@link #getCount()}) * @param value the node to be written to the edge */
public void initializeNode(Node node, int index, Node value) { verifyUpdateValid(node, index, value); putNodeUnsafe(node, offsets[index], value); } public void initializeList(Node node, int index, NodeList<Node> value) { verifyUpdateValid(node, index, value); putNodeListUnsafe(node, offsets[index], value); } private void verifyUpdateValid(Node node, int index, Object newValue) { if (newValue != null && !getType(index).isAssignableFrom(newValue.getClass())) { throw new IllegalArgumentException("Can not assign " + newValue.getClass() + " to " + getType(index) + " in " + node); } }
Sets the value of a given edge and notifies the new and old nodes on the other end of the edge of the change.
Params:
  • node – the node whose edge is to be updated
  • index – the index of the edge (between 0 and Fields.getCount())
  • value – the node to be written to the edge
/** * Sets the value of a given edge and notifies the new and old nodes on the other end of the * edge of the change. * * @param node the node whose edge is to be updated * @param index the index of the edge (between 0 and {@link #getCount()}) * @param value the node to be written to the edge */
public void setNode(Node node, int index, Node value) { assert index < directCount; Node old = getNodeUnsafe(node, offsets[index]); initializeNode(node, index, value); update(node, old, value); } public abstract void update(Node node, Node oldValue, Node newValue); public boolean contains(Node node, Node value) { final long[] curOffsets = this.offsets; for (int i = 0; i < directCount; i++) { if (getNode(node, curOffsets, i) == value) { return true; } } for (int i = directCount; i < getCount(); i++) { NodeList<?> curList = getNodeList(node, curOffsets, i); if (curList != null && curList.contains(value)) { return true; } } return false; }
An iterator that will iterate over edges. An iterator of this type will not return null values, unless edges are modified concurrently. Concurrent modifications are detected by an assertion on a best-effort basis.
/** * An iterator that will iterate over edges. * * An iterator of this type will not return null values, unless edges are modified concurrently. * Concurrent modifications are detected by an assertion on a best-effort basis. */
private static class EdgesIterator implements Iterator<Position> { protected final Node node; protected final Edges edges; protected int index; protected int subIndex; protected boolean needsForward; protected final int directCount; protected final long[] offsets;
Creates an iterator that will iterate over some given edges in a given node.
/** * Creates an iterator that will iterate over some given edges in a given node. */
EdgesIterator(Node node, Edges edges) { this.node = node; this.edges = edges; index = NOT_ITERABLE; subIndex = 0; needsForward = true; this.directCount = edges.getDirectCount(); this.offsets = edges.getOffsets(); } void forward() { needsForward = false; if (index < directCount) { index++; if (index < directCount) { return; } } else { subIndex++; } if (index < edges.getCount()) { forwardNodeList(); } } private void forwardNodeList() { do { NodeList<?> list = Edges.getNodeList(node, offsets, index); if (list != null) { if (subIndex < list.size()) { return; } } subIndex = 0; index++; } while (index < edges.getCount()); } @Override public boolean hasNext() { if (needsForward) { forward(); } return index < edges.getCount(); } @Override public Position next() { if (needsForward) { forward(); } needsForward = true; if (index < directCount) { return new Position(edges, index, NOT_ITERABLE); } else { return new Position(edges, index, subIndex); } } @Override public void remove() { throw new UnsupportedOperationException(); } } private static final class EdgesWithModCountIterator extends EdgesIterator { private final int modCount; private EdgesWithModCountIterator(Node node, Edges edges) { super(node, edges); assert isModificationCountsEnabled(); this.modCount = node.modCount(); } @Override public boolean hasNext() { try { return super.hasNext(); } finally { assert modCount == node.modCount() : "must not be modified"; } } @Override public Position next() { try { return super.next(); } finally { assert modCount == node.modCount() : "must not be modified"; } } } public Iterable<Position> getPositionsIterable(final Node node) { return new Iterable<Position>() { @Override public Iterator<Position> iterator() { if (isModificationCountsEnabled()) { return new EdgesWithModCountIterator(node, Edges.this); } else { return new EdgesIterator(node, Edges.this); } } }; } public Type type() { return type; } }