Mercurial > hg > graal-jvmci-8
view graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java @ 5489:5d0d72b37f88
Switch to new loop transformation framework, use it for peeling and full unrolling for snippets
Change behaviour or addDuplicates : it now connects things to the 'outer world' for inputs. Only replacement of nodes which are in the set of duplicated nodes get their edges updates
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Wed, 06 Jun 2012 19:09:05 +0200 |
parents | 9743ae819f73 |
children | cedae73d9c2a |
line wrap: on
line source
/* * Copyright (c) 2011, 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 com.oracle.graal.graph; import java.lang.reflect.Field; import java.lang.reflect.Modifier; import java.util.*; import java.util.Map.*; import java.util.concurrent.ConcurrentHashMap; import com.oracle.graal.graph.Graph.DuplicationReplacement; import sun.misc.Unsafe; public class NodeClass { public static final int NOT_ITERABLE = -1; /** * Interface used by {@link NodeClass#rescanAllFieldOffsets(CalcOffset)} to determine the offset (in bytes) of a field. */ public interface CalcOffset { long getOffset(Field field); } private static final Class< ? > NODE_CLASS = Node.class; private static final Class< ? > INPUT_LIST_CLASS = NodeInputList.class; private static final Class< ? > SUCCESSOR_LIST_CLASS = NodeSuccessorList.class; private static final Unsafe unsafe = getUnsafe(); private static Unsafe getUnsafe() { try { // this will only fail if graal is not part of the boot class path return Unsafe.getUnsafe(); } catch (SecurityException e) { // nothing to do } try { Field theUnsafeInstance = Unsafe.class.getDeclaredField("theUnsafe"); theUnsafeInstance.setAccessible(true); return (Unsafe) theUnsafeInstance.get(Unsafe.class); } catch (Exception e) { // currently we rely on being able to use Unsafe... throw new RuntimeException("exception while trying to get Unsafe.theUnsafe via reflection:", e); } } private static final Map<Class< ? >, NodeClass> nodeClasses = new ConcurrentHashMap<>(); private static int nextIterableId = 0; private final Class< ? > clazz; private final int directInputCount; private final long[] inputOffsets; private final Class<?>[] inputTypes; private final String[] inputNames; private final int directSuccessorCount; private final long[] successorOffsets; private final Class<?>[] successorTypes; private final String[] successorNames; private final long[] dataOffsets; private final Class<?>[] dataTypes; private final String[] dataNames; private final boolean canGVN; private final int startGVNNumber; private final String shortName; private final int iterableId; private final boolean hasOutgoingEdges; static class DefaultCalcOffset implements CalcOffset { @Override public long getOffset(Field field) { return unsafe.objectFieldOffset(field); } } public NodeClass(Class< ? > clazz) { assert NODE_CLASS.isAssignableFrom(clazz); this.clazz = clazz; FieldScanner scanner = new FieldScanner(new DefaultCalcOffset()); scanner.scan(clazz); directInputCount = scanner.inputOffsets.size(); inputOffsets = sortedLongCopy(scanner.inputOffsets, scanner.inputListOffsets); directSuccessorCount = scanner.successorOffsets.size(); successorOffsets = sortedLongCopy(scanner.successorOffsets, scanner.successorListOffsets); dataOffsets = new long[scanner.dataOffsets.size()]; for (int i = 0; i < scanner.dataOffsets.size(); ++i) { dataOffsets[i] = scanner.dataOffsets.get(i); } dataTypes = scanner.dataTypes.toArray(new Class[0]); dataNames = scanner.dataNames.toArray(new String[0]); inputTypes = arrayUsingSortedOffsets(scanner.inputTypesMap, inputOffsets, new Class<?>[inputOffsets.length]); inputNames = arrayUsingSortedOffsets(scanner.inputNamesMap, inputOffsets, new String[inputOffsets.length]); successorTypes = arrayUsingSortedOffsets(scanner.successorTypesMap, successorOffsets, new Class<?>[successorOffsets.length]); successorNames = arrayUsingSortedOffsets(scanner.successorNamesMap, successorOffsets, new String[successorOffsets.length]); canGVN = Node.ValueNumberable.class.isAssignableFrom(clazz); startGVNNumber = clazz.hashCode(); String newShortName = clazz.getSimpleName(); if (newShortName.endsWith("Node") && !newShortName.equals("StartNode") && !newShortName.equals("EndNode")) { newShortName = newShortName.substring(0, newShortName.length() - 4); } NodeInfo info = clazz.getAnnotation(NodeInfo.class); if (info != null) { if (!info.shortName().isEmpty()) { newShortName = info.shortName(); } } this.shortName = newShortName; if (Node.IterableNodeType.class.isAssignableFrom(clazz)) { this.iterableId = nextIterableId++; // TODO (lstadler) add type hierarchy - based node iteration // for (NodeClass nodeClass : nodeClasses.values()) { // if (clazz.isAssignableFrom(nodeClass.clazz)) { // throw new UnsupportedOperationException("iterable non-final Node classes not supported: " + clazz); // } // } } else { this.iterableId = NOT_ITERABLE; } this.hasOutgoingEdges = this.inputOffsets.length > 0 || this.successorOffsets.length > 0; } public static void rescanAllFieldOffsets(CalcOffset calc) { for (NodeClass nodeClass : nodeClasses.values()) { nodeClass.rescanFieldOffsets(calc); } } private void rescanFieldOffsets(CalcOffset calc) { FieldScanner scanner = new FieldScanner(calc); scanner.scan(clazz); assert directInputCount == scanner.inputOffsets.size(); copyInto(inputOffsets, sortedLongCopy(scanner.inputOffsets, scanner.inputListOffsets)); assert directSuccessorCount == scanner.successorOffsets.size(); copyInto(successorOffsets, sortedLongCopy(scanner.successorOffsets, scanner.successorListOffsets)); assert dataOffsets.length == scanner.dataOffsets.size(); for (int i = 0; i < scanner.dataOffsets.size(); ++i) { dataOffsets[i] = scanner.dataOffsets.get(i); } copyInto(dataTypes, scanner.dataTypes); copyInto(dataNames, scanner.dataNames); copyInto(inputTypes, arrayUsingSortedOffsets(scanner.inputTypesMap, this.inputOffsets, new Class<?>[this.inputOffsets.length])); copyInto(inputNames, arrayUsingSortedOffsets(scanner.inputNamesMap, this.inputOffsets, new String[this.inputOffsets.length])); copyInto(successorTypes, arrayUsingSortedOffsets(scanner.successorTypesMap, this.successorOffsets, new Class<?>[this.successorOffsets.length])); copyInto(successorNames, arrayUsingSortedOffsets(scanner.successorNamesMap, this.successorOffsets, new String[this.successorNames.length])); } private static void copyInto(long[] dest, long[] src) { assert dest.length == src.length; for (int i = 0; i < dest.length; i++) { dest[i] = src[i]; } } private static <T> void copyInto(T[] dest, T[] src) { assert dest.length == src.length; for (int i = 0; i < dest.length; i++) { dest[i] = src[i]; } } private static <T> void copyInto(T[] dest, List<T> src) { assert dest.length == src.size(); for (int i = 0; i < dest.length; i++) { dest[i] = src.get(i); } } public boolean hasOutgoingEdges() { return hasOutgoingEdges; } public String shortName() { return shortName; } public int iterableId() { return iterableId; } public boolean valueNumberable() { return canGVN; } private static synchronized NodeClass getSynchronized(Class< ? > c) { NodeClass clazz = nodeClasses.get(c); if (clazz == null) { clazz = new NodeClass(c); nodeClasses.put(c, clazz); } return clazz; } public static final NodeClass get(Class< ? > c) { NodeClass clazz = nodeClasses.get(c); return clazz == null ? getSynchronized(c) : clazz; } public static int cacheSize() { return nextIterableId; } private static class FieldScanner { public final ArrayList<Long> inputOffsets = new ArrayList<>(); public final ArrayList<Long> inputListOffsets = new ArrayList<>(); public final Map<Long, Class< ? >> inputTypesMap = new HashMap<>(); public final Map<Long, String> inputNamesMap = new HashMap<>(); public final ArrayList<Long> successorOffsets = new ArrayList<>(); public final ArrayList<Long> successorListOffsets = new ArrayList<>(); public final Map<Long, Class< ? >> successorTypesMap = new HashMap<>(); public final Map<Long, String> successorNamesMap = new HashMap<>(); public final ArrayList<Long> dataOffsets = new ArrayList<>(); public final ArrayList<Class< ? >> dataTypes = new ArrayList<>(); public final ArrayList<String> dataNames = new ArrayList<>(); public final CalcOffset calc; public FieldScanner(CalcOffset calc) { this.calc = calc; } public void scan(Class< ? > clazz) { Class< ? > currentClazz = clazz; do { for (Field field : currentClazz.getDeclaredFields()) { if (!Modifier.isStatic(field.getModifiers())) { Class< ? > type = field.getType(); long offset = calc.getOffset(field); String name = field.getName(); if (field.isAnnotationPresent(Node.Input.class)) { assert !field.isAnnotationPresent(Node.Successor.class) : "field cannot be both input and successor"; if (INPUT_LIST_CLASS.isAssignableFrom(type)) { inputListOffsets.add(offset); } else { assert NODE_CLASS.isAssignableFrom(type) : "invalid input type: " + type; inputOffsets.add(offset); inputTypesMap.put(offset, type); } if (field.getAnnotation(Node.Input.class).notDataflow()) { inputNamesMap.put(offset, name + "#NDF"); } else { inputNamesMap.put(offset, name); } } else if (field.isAnnotationPresent(Node.Successor.class)) { if (SUCCESSOR_LIST_CLASS.isAssignableFrom(type)) { successorListOffsets.add(offset); } else { assert NODE_CLASS.isAssignableFrom(type) : "invalid successor type: " + type; successorOffsets.add(offset); successorTypesMap.put(offset, type); } successorNamesMap.put(offset, name); } else { assert !NODE_CLASS.isAssignableFrom(type) || name.equals("Null") : "suspicious node field: " + field; assert !INPUT_LIST_CLASS.isAssignableFrom(type) : "suspicious node input list field: " + field; assert !SUCCESSOR_LIST_CLASS.isAssignableFrom(type) : "suspicious node successor list field: " + field; dataOffsets.add(offset); dataTypes.add(type); dataNames.add(name); } } } currentClazz = currentClazz.getSuperclass(); } while (currentClazz != Node.class); } } private static <T> T[] arrayUsingSortedOffsets(Map<Long, T> map, long[] sortedOffsets, T[] result) { for (int i = 0; i < sortedOffsets.length; i++) { result[i] = map.get(sortedOffsets[i]); } return result; } private static long[] sortedLongCopy(ArrayList<Long> list1, ArrayList<Long> list2) { Collections.sort(list1); Collections.sort(list2); long[] result = new long[list1.size() + list2.size()]; for (int i = 0; i < list1.size(); i++) { result[i] = list1.get(i); } for (int i = 0; i < list2.size(); i++) { result[list1.size() + i] = list2.get(i); } return result; } @Override public String toString() { StringBuilder str = new StringBuilder(); str.append("NodeClass ").append(clazz.getSimpleName()).append(" ["); for (int i = 0; i < inputOffsets.length; i++) { str.append(i == 0 ? "" : ", ").append(inputOffsets[i]); } str.append("] ["); for (int i = 0; i < successorOffsets.length; i++) { str.append(i == 0 ? "" : ", ").append(successorOffsets[i]); } str.append("] ["); for (int i = 0; i < dataOffsets.length; i++) { str.append(i == 0 ? "" : ", ").append(dataOffsets[i]); } str.append("]"); return str.toString(); } public static final class Position { public final boolean input; public final int index; public final int subIndex; public Position(boolean input, int index, int subIndex) { this.input = input; this.index = index; this.subIndex = subIndex; } @Override public String toString() { return (input ? "input " : "successor ") + index + "/" + subIndex; } public Node get(Node node) { return node.getNodeClass().get(node, this); } public void set(Node node, Node value) { node.getNodeClass().set(node, this, value); } public boolean isValidFor(Node node, Node from) { return node.getNodeClass().isValid(this, from.getNodeClass()); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + index; result = prime * result + (input ? 1231 : 1237); result = prime * result + subIndex; return result; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } Position other = (Position) obj; if (index != other.index) { return false; } if (input != other.input) { return false; } if (subIndex != other.subIndex) { return false; } return true; } } private static Node getNode(Node node, long offset) { return (Node) unsafe.getObject(node, offset); } @SuppressWarnings("unchecked") private static NodeList<Node> getNodeList(Node node, long offset) { return (NodeList<Node>) unsafe.getObject(node, offset); } private static void putNode(Node node, long offset, Node value) { unsafe.putObject(node, offset, value); } private static void putNodeList(Node node, long offset, NodeList value) { unsafe.putObject(node, offset, value); } /** * An iterator that will iterate over the fields given in {@link offsets}. * The first {@ directCount} offsets are treated as fields of type {@link Node}, while the rest of the fields are treated as {@link NodeList}s. * All elements of these NodeLists will be visited by the iterator as well. * This iterator can be used to iterate over the inputs or successors of a node. * * An iterator of this type will not return null values, unless the field values are modified concurrently. * Concurrent modifications are detected by an assertion on a best-effort basis. */ public static final class NodeClassIterator implements Iterator<Node> { private final Node node; private final int modCount; private final int directCount; private final long[] offsets; private int index; private int subIndex; /** * Creates an iterator that will iterate over fields in the given node. * @param node the node which contains the fields. * @param offsets the offsets of the fields. * @param directCount the number of fields that should be treated as fields of type {@link Node}, the rest are treated as {@link NodeList}s. */ private NodeClassIterator(Node node, long[] offsets, int directCount) { this.node = node; this.modCount = node.modCount(); this.offsets = offsets; this.directCount = directCount; index = NOT_ITERABLE; subIndex = 0; forward(); } private void forward() { if (index < directCount) { index++; while (index < directCount) { Node element = getNode(node, offsets[index]); if (element != null) { return; } index++; } } else { subIndex++; } while (index < offsets.length) { NodeList<Node> list = getNodeList(node, offsets[index]); while (subIndex < list.size()) { if (list.get(subIndex) != null) { return; } subIndex++; } subIndex = 0; index++; } } private Node nextElement() { if (index < directCount) { return getNode(node, offsets[index]); } else if (index < offsets.length) { NodeList<Node> list = getNodeList(node, offsets[index]); return list.get(subIndex); } return null; } @Override public boolean hasNext() { try { return index < offsets.length; } finally { assert modCount == node.modCount() : "must not be modified"; } } @Override public Node next() { try { return nextElement(); } finally { forward(); assert modCount == node.modCount(); } } public Position nextPosition() { try { if (index < directCount) { return new Position(offsets == node.getNodeClass().inputOffsets, index, NOT_ITERABLE); } else { return new Position(offsets == node.getNodeClass().inputOffsets, index, subIndex); } } finally { forward(); assert modCount == node.modCount(); } } @Override public void remove() { throw new UnsupportedOperationException(); } } public int valueNumber(Node n) { int number = 0; if (canGVN) { number = startGVNNumber; for (int i = 0; i < dataOffsets.length; ++i) { Class<?> type = dataTypes[i]; if (type.isPrimitive()) { if (type == Integer.TYPE) { int intValue = unsafe.getInt(n, dataOffsets[i]); number += intValue; } else if (type == Boolean.TYPE) { boolean booleanValue = unsafe.getBoolean(n, dataOffsets[i]); if (booleanValue) { number += 7; } } else { assert false; } } else { Object o = unsafe.getObject(n, dataOffsets[i]); if (o != null) { number += o.hashCode(); } } number *= 13; } } return number; } /** * Populates a given map with the names and values of all fields marked with @{@link Data}. * @param node the node from which to take the values. * @param properties a map that will be populated. */ public void getDebugProperties(Node node, Map<Object, Object> properties) { for (int i = 0; i < dataOffsets.length; ++i) { Class<?> type = dataTypes[i]; Object value = null; if (type.isPrimitive()) { if (type == Integer.TYPE) { value = unsafe.getInt(node, dataOffsets[i]); } else if (type == Long.TYPE) { value = unsafe.getLong(node, dataOffsets[i]); } else if (type == Boolean.TYPE) { value = unsafe.getBoolean(node, dataOffsets[i]); } else if (type == Long.TYPE) { value = unsafe.getLong(node, dataOffsets[i]); } else if (type == Double.TYPE) { value = unsafe.getDouble(node, dataOffsets[i]); } else { assert false : "unhandled property type: " + type; } } else { value = unsafe.getObject(node, dataOffsets[i]); if (type.isArray()) { if (!type.getComponentType().isPrimitive()) { value = Arrays.toString((Object[]) value); } else if (type.getComponentType() == Integer.TYPE) { value = Arrays.toString((int[]) value); } else if (type.getComponentType() == Double.TYPE) { value = Arrays.toString((double[]) value); } } } properties.put("data." + dataNames[i], value); } } public boolean valueEqual(Node a, Node b) { if (!canGVN || a.getNodeClass() != b.getNodeClass()) { return a == b; } for (int i = 0; i < dataOffsets.length; ++i) { Class<?> type = dataTypes[i]; if (type.isPrimitive()) { if (type == Integer.TYPE) { int aInt = unsafe.getInt(a, dataOffsets[i]); int bInt = unsafe.getInt(b, dataOffsets[i]); if (aInt != bInt) { return false; } } else if (type == Boolean.TYPE) { boolean aBoolean = unsafe.getBoolean(a, dataOffsets[i]); boolean bBoolean = unsafe.getBoolean(b, dataOffsets[i]); if (aBoolean != bBoolean) { return false; } } else if (type == Long.TYPE) { long aLong = unsafe.getLong(a, dataOffsets[i]); long bLong = unsafe.getLong(b, dataOffsets[i]); if (aLong != bLong) { return false; } } else { assert false : "unhandled type: " + type; } } else { Object objectA = unsafe.getObject(a, dataOffsets[i]); Object objectB = unsafe.getObject(b, dataOffsets[i]); if (objectA != objectB) { if (objectA != null && objectB != null) { if (!(objectA.equals(objectB))) { return false; } } else { return false; } } } } return true; } public boolean isValid(Position pos, NodeClass from) { if (this == from) { return true; } long[] offsets = pos.input ? inputOffsets : successorOffsets; if (pos.index >= offsets.length) { return false; } long[] fromOffsets = pos.input ? from.inputOffsets : from.successorOffsets; if (pos.index >= fromOffsets.length) { return false; } return offsets[pos.index] == fromOffsets[pos.index]; } public Node get(Node node, Position pos) { long offset = pos.input ? inputOffsets[pos.index] : successorOffsets[pos.index]; if (pos.subIndex == NOT_ITERABLE) { return getNode(node, offset); } else { return getNodeList(node, offset).get(pos.subIndex); } } public String getName(Position pos) { return pos.input ? inputNames[pos.index] : successorNames[pos.index]; } private void set(Node node, Position pos, Node x) { long offset = pos.input ? inputOffsets[pos.index] : successorOffsets[pos.index]; if (pos.subIndex == NOT_ITERABLE) { Node old = getNode(node, offset); assert x == null || (pos.input ? inputTypes : successorTypes)[pos.index].isAssignableFrom(x.getClass()) : this + ".set(node, pos, " + x + ") while type is " + (pos.input ? inputTypes : successorTypes)[pos.index]; putNode(node, offset, x); if (pos.input) { node.updateUsages(old, x); } else { node.updatePredecessor(old, x); } } else { NodeList<Node> list = getNodeList(node, offset); if (pos.subIndex < list.size()) { list.set(pos.subIndex, x); } else { while (pos.subIndex < list.size() - 1) { list.add(null); } list.add(x); } } } public NodeInputsIterable getInputIterable(final Node node) { assert clazz.isInstance(node); return new NodeInputsIterable() { @Override public NodeClassIterator iterator() { return new NodeClassIterator(node, inputOffsets, directInputCount); } @Override public boolean contains(Node other) { return inputContains(node, other); } }; } public NodeSuccessorsIterable getSuccessorIterable(final Node node) { assert clazz.isInstance(node); return new NodeSuccessorsIterable() { @Override public NodeClassIterator iterator() { return new NodeClassIterator(node, successorOffsets, directSuccessorCount); } @Override public boolean contains(Node other) { return successorContains(node, other); } }; } public boolean replaceFirstInput(Node node, Node old, Node other) { int index = 0; while (index < directInputCount) { Node input = getNode(node, inputOffsets[index]); if (input == old) { assert other == null || inputTypes[index].isAssignableFrom(other.getClass()); // : "Can not assign " + other.getClass() + " to " + inputTypes[index] + " in " + node; putNode(node, inputOffsets[index], other); return true; } index++; } while (index < inputOffsets.length) { NodeList<Node> list = getNodeList(node, inputOffsets[index]); assert list != null : clazz; if (list.replaceFirst(old, other)) { return true; } index++; } return false; } public boolean replaceFirstSuccessor(Node node, Node old, Node other) { int index = 0; while (index < directSuccessorCount) { Node successor = getNode(node, successorOffsets[index]); if (successor == old) { assert other == null || successorTypes[index].isAssignableFrom(other.getClass()); // : successorTypes[index] + " is not compatible with " + other.getClass(); putNode(node, successorOffsets[index], other); return true; } index++; } while (index < successorOffsets.length) { NodeList<Node> list = getNodeList(node, successorOffsets[index]); assert list != null : clazz + " " + successorOffsets[index] + " " + node; if (list.replaceFirst(old, other)) { return true; } index++; } return false; } /** * Clear all inputs in the given node. This is accomplished by setting input fields to null and replacing input lists with new lists. * (which is important so that this method can be used to clear the inputs of cloned nodes.) * @param node the node to be cleared */ public void clearInputs(Node node) { int index = 0; while (index < directInputCount) { putNode(node, inputOffsets[index++], null); } while (index < inputOffsets.length) { long curOffset = inputOffsets[index++]; int size = (getNodeList(node, curOffset)).initialSize; // replacing with a new list object is the expected behavior! putNodeList(node, curOffset, new NodeInputList<>(node, size)); } } /** * Clear all successors in the given node. This is accomplished by setting successor fields to null and replacing successor lists with new lists. * (which is important so that this method can be used to clear the successors of cloned nodes.) * @param node the node to be cleared */ public void clearSuccessors(Node node) { int index = 0; while (index < directSuccessorCount) { putNode(node, successorOffsets[index++], null); } while (index < successorOffsets.length) { long curOffset = successorOffsets[index++]; int size = getNodeList(node, curOffset).initialSize; // replacing with a new list object is the expected behavior! putNodeList(node, curOffset, new NodeSuccessorList<>(node, size)); } } /** * Copies the inputs from node to newNode. The nodes are expected to be of the exact same NodeClass type. * @param node the node from which the inputs should be copied. * @param newNode the node to which the inputs should be copied. */ public void copyInputs(Node node, Node newNode) { assert node.getClass() == clazz && newNode.getClass() == clazz; int index = 0; while (index < directInputCount) { putNode(newNode, inputOffsets[index], getNode(node, inputOffsets[index])); index++; } while (index < inputOffsets.length) { NodeList<Node> list = getNodeList(newNode, inputOffsets[index]); list.copy(getNodeList(node, inputOffsets[index])); index++; } } /** * Copies the successors from node to newNode. The nodes are expected to be of the exact same NodeClass type. * @param node the node from which the successors should be copied. * @param newNode the node to which the successors should be copied. */ public void copySuccessors(Node node, Node newNode) { assert node.getClass() == clazz && newNode.getClass() == clazz; int index = 0; while (index < directSuccessorCount) { putNode(newNode, successorOffsets[index], getNode(node, successorOffsets[index])); index++; } while (index < successorOffsets.length) { NodeList<Node> list = getNodeList(newNode, successorOffsets[index]); list.copy(getNodeList(node, successorOffsets[index])); index++; } } public boolean edgesEqual(Node node, Node other) { assert node.getClass() == clazz && other.getClass() == clazz; int index = 0; while (index < directInputCount) { if (getNode(other, inputOffsets[index]) != getNode(node, inputOffsets[index])) { return false; } index++; } while (index < inputOffsets.length) { NodeList<Node> list = getNodeList(other, inputOffsets[index]); if (!list.equals(getNodeList(node, inputOffsets[index]))) { return false; } index++; } index = 0; while (index < directSuccessorCount) { if (getNode(other, successorOffsets[index]) != getNode(node, successorOffsets[index])) { return false; } index++; } while (index < successorOffsets.length) { NodeList<Node> list = getNodeList(other, successorOffsets[index]); if (!list.equals(getNodeList(node, successorOffsets[index]))) { return false; } index++; } return true; } public boolean inputContains(Node node, Node other) { assert node.getClass() == clazz; int index = 0; while (index < directInputCount) { if (getNode(node, inputOffsets[index]) == other) { return true; } index++; } while (index < inputOffsets.length) { NodeList<Node> list = getNodeList(node, inputOffsets[index]); if (list.contains(other)) { return true; } index++; } return false; } public boolean successorContains(Node node, Node other) { assert node.getClass() == clazz; int index = 0; while (index < directSuccessorCount) { if (getNode(node, successorOffsets[index]) == other) { return true; } index++; } while (index < successorOffsets.length) { NodeList<Node> list = getNodeList(node, successorOffsets[index]); if (list.contains(other)) { return true; } index++; } return false; } public int directInputCount() { return directInputCount; } public int directSuccessorCount() { return directSuccessorCount; } static Map<Node, Node> addGraphDuplicate(Graph graph, Iterable<Node> nodes, DuplicationReplacement replacements) { Map<Node, Node> newNodes = new IdentityHashMap<>(); Map<Node, Node> replacementsMap = new IdentityHashMap<>(); // create node duplicates for (Node node : nodes) { if (node != null) { assert !node.isDeleted() : "trying to duplicate deleted node"; Node replacement = replacements.replacement(node); if (replacement != node) { newNodes.put(node, replacement); } else { Node newNode = node.clone(graph); assert newNode.getClass() == node.getClass(); newNodes.put(node, newNode); } } } // re-wire inputs for (Entry<Node, Node> entry : newNodes.entrySet()) { Node oldNode = entry.getKey(); Node node = entry.getValue(); for (NodeClassIterator iter = oldNode.inputs().iterator(); iter.hasNext();) { Position pos = iter.nextPosition(); if (!pos.isValidFor(node, oldNode)) { continue; } Node input = oldNode.getNodeClass().get(oldNode, pos); Node target = newNodes.get(input); if (target == null) { target = replacementsMap.get(input); if (target == null) { Node replacement = replacements.replacement(input); if (replacement != input) { replacementsMap.put(input, replacement); assert replacement == null || node.getNodeClass().inputTypes[pos.index] == null || node.getNodeClass().inputTypes[pos.index].isAssignableFrom(replacement.getClass()); target = replacement; } else { // patch to the outer world target = input; } } } node.getNodeClass().set(node, pos, target); } } // re-wire successors for (Entry<Node, Node> entry : newNodes.entrySet()) { Node oldNode = entry.getKey(); Node node = entry.getValue(); for (NodeClassIterator iter = oldNode.successors().iterator(); iter.hasNext();) { Position pos = iter.nextPosition(); if (!pos.isValidFor(node, oldNode)) { continue; } Node succ = oldNode.getNodeClass().get(oldNode, pos); Node target = newNodes.get(succ); if (target == null) { target = replacementsMap.get(succ); if (target == null) { Node replacement = replacements.replacement(succ); if (replacement != succ) { replacementsMap.put(succ, replacement); assert replacement == null || node.getNodeClass().successorTypes[pos.index] == null || node.getNodeClass().successorTypes[pos.index].isAssignableFrom(replacement.getClass()); target = replacement; } } } node.getNodeClass().set(node, pos, target); } } return newNodes; } }