compiler/graph/Graph.java

/*
 * Copyright (c) 2011, 2013, 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 java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.function.Consumer;

import org.graalvm.compiler.core.common.CollectionsFactory;
import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.debug.DebugCloseable;
import org.graalvm.compiler.debug.DebugCounter;
import org.graalvm.compiler.debug.DebugTimer;
import org.graalvm.compiler.debug.Fingerprint;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.graph.Node.ValueNumberable;
import org.graalvm.compiler.graph.iterators.NodeIterable;
import org.graalvm.compiler.options.Option;
import org.graalvm.compiler.options.OptionType;
import org.graalvm.compiler.options.OptionValue;

/**
 * This class is a graph container, it contains the set of nodes that belong to this graph.
 */
public class Graph {

    public static class Options {
        @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)//
        public static final OptionValue<Boolean> VerifyGraalGraphs = new OptionValue<>(true);
        @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)//
        public static final OptionValue<Boolean> VerifyGraalGraphEdges = new OptionValue<>(false);
        @Option(help = "Graal graph compression is performed when percent of live nodes falls below this value", type = OptionType.Debug)//
        public static final OptionValue<Integer> GraphCompressionThreshold = new OptionValue<>(70);
        @Option(help = "Use Unsafe to clone graph nodes thus avoiding copying fields that will be re-initialized anyway", type = OptionType.Debug)//
        public static final OptionValue<Boolean> CloneNodesWithUnsafe = new OptionValue<>(true);
    }

    public final String name;

    /**
     * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.
     */
    Node[] nodes;

    /**
     * Source information to associate with newly created nodes.
     */
    NodeSourcePosition currentNodeSourcePosition;

    /**
     * Records if updating of node source information is required when performing inlining.
     */
    boolean seenNodeSourcePosition;

    /**
     * The number of valid entries in {@link #nodes}.
     */
    int nodesSize;

    /**
     * Records the modification count for nodes. This is only used in assertions.
     */
    private int[] nodeModCounts;

    /**
     * Records the modification count for nodes' usage lists. This is only used in assertions.
     */
    private int[] nodeUsageModCounts;

    // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.
    // they contain the first and last pointer to a linked list of all nodes with this type.
    private final ArrayList<Node> iterableNodesFirst;
    private final ArrayList<Node> iterableNodesLast;

    private int nodesDeletedSinceLastCompression;
    private int nodesDeletedBeforeLastCompression;

    /**
     * The number of times this graph has been compressed.
     */
    int compressions;

    NodeEventListener nodeEventListener;

    /**
     * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf}
     * nodes.
     */
    private final HashMap<CacheEntry, Node> cachedLeafNodes = CollectionsFactory.newMap();

    /*
     * Indicates that the graph should no longer be modified. Frozen graphs can be used my multiple
     * threads so it's only safe to read them.
     */
    private boolean isFrozen = false;

    /**
     * Entry in {@link Graph#cachedLeafNodes}.
     */
    private static final class CacheEntry {

        private final Node node;

        CacheEntry(Node node) {
            assert node.getNodeClass().valueNumberable();
            assert node.getNodeClass().isLeafNode();
            this.node = node;
        }

        @Override
        public int hashCode() {
            return node.getNodeClass().valueNumber(node);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (obj instanceof CacheEntry) {
                CacheEntry other = (CacheEntry) obj;
                if (other.node.getClass() == node.getClass()) {
                    return node.valueEquals(other.node);
                }
            }
            return false;
        }

        @Override
        public String toString() {
            return node.toString();
        }
    }

    private class NodeSourcePositionScope implements DebugCloseable {
        private final NodeSourcePosition previous;

        NodeSourcePositionScope(NodeSourcePosition sourcePosition) {
            previous = currentNodeSourcePosition;
            currentNodeSourcePosition = sourcePosition;
        }

        @Override
        public void close() {
            currentNodeSourcePosition = previous;
        }
    }

    public NodeSourcePosition currentNodeSourcePosition() {
        return currentNodeSourcePosition;
    }

    /**
     * Opens a scope in which the source information from {@code node} is copied into nodes created
     * within the scope. If {@code node} has no source information information, no scope is opened
     * and {@code null} is returned.
     *
     * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
     *         was opened
     */
    public DebugCloseable withNodeSourcePosition(Node node) {
        return withNodeSourcePosition(node.sourcePosition);
    }

    /**
     * Opens a scope in which {@code sourcePosition} is copied into nodes created within the scope.
     * If {@code sourcePosition == null}, no scope is opened and {@code null} is returned.
     *
     * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
     *         was opened
     */
    public DebugCloseable withNodeSourcePosition(NodeSourcePosition sourcePosition) {
        return sourcePosition != null ? new NodeSourcePositionScope(sourcePosition) : null;
    }

    /**
     * Opens a scope in which newly created nodes do not get any source information added.
     *
     * @return a {@link DebugCloseable} for managing the opened scope
     */
    public DebugCloseable withoutNodeSourcePosition() {
        return new NodeSourcePositionScope(null);
    }

    /**
     * Determines if this graph might contain nodes with source information. This is mainly useful
     * to short circuit logic for updating those positions after inlining since that requires
     * visiting every node in the graph.
     */
    public boolean mayHaveNodeSourcePosition() {
        assert seenNodeSourcePosition || verifyHasNoSourcePosition();
        return seenNodeSourcePosition;
    }

    private boolean verifyHasNoSourcePosition() {
        for (Node node : getNodes()) {
            assert node.getNodeSourcePosition() == null;
        }
        return true;
    }

    /**
     * Creates an empty Graph with no name.
     */
    public Graph() {
        this(null);
    }

    /**
     * We only want the expensive modification count tracking when assertions are enabled for the
     * {@link Graph} class.
     */
    @SuppressWarnings("all")
    public static boolean isModificationCountsEnabled() {
        boolean enabled = false;
        assert enabled = true;
        return enabled;
    }

    private static final int INITIAL_NODES_SIZE = 32;

    /**
     * Creates an empty Graph with a given name.
     *
     * @param name the name of the graph, used for debugging purposes
     */
    public Graph(String name) {
        nodes = new Node[INITIAL_NODES_SIZE];
        iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
        iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
        this.name = name;
        if (isModificationCountsEnabled()) {
            nodeModCounts = new int[INITIAL_NODES_SIZE];
            nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
        }
    }

    int extractOriginalNodeId(Node node) {
        int id = node.id;
        if (id <= Node.DELETED_ID_START) {
            id = Node.DELETED_ID_START - id;
        }
        return id;
    }

    int modCount(Node node) {
        int id = extractOriginalNodeId(node);
        if (id >= 0 && id < nodeModCounts.length) {
            return nodeModCounts[id];
        }
        return 0;
    }

    void incModCount(Node node) {
        int id = extractOriginalNodeId(node);
        if (id >= 0) {
            if (id >= nodeModCounts.length) {
                nodeModCounts = Arrays.copyOf(nodeModCounts, id * 2 + 30);
            }
            nodeModCounts[id]++;
        } else {
            assert false;
        }
    }

    int usageModCount(Node node) {
        int id = extractOriginalNodeId(node);
        if (id >= 0 && id < nodeUsageModCounts.length) {
            return nodeUsageModCounts[id];
        }
        return 0;
    }

    void incUsageModCount(Node node) {
        int id = extractOriginalNodeId(node);
        if (id >= 0) {
            if (id >= nodeUsageModCounts.length) {
                nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id * 2 + 30);
            }
            nodeUsageModCounts[id]++;
        } else {
            assert false;
        }
    }

    /**
     * Creates a copy of this graph.
     */
    public final Graph copy() {
        return copy(name, null);
    }

    /**
     * Creates a copy of this graph.
     *
     * @param duplicationMapCallback consumer of the duplication map created during the copying
     */
    public final Graph copy(Consumer<Map<Node, Node>> duplicationMapCallback) {
        return copy(name, duplicationMapCallback);
    }

    /**
     * Creates a copy of this graph.
     *
     * @param newName the name of the copy, used for debugging purposes (can be null)
     */
    public final Graph copy(String newName) {
        return copy(newName, null);
    }

    /**
     * Creates a copy of this graph.
     *
     * @param newName the name of the copy, used for debugging purposes (can be null)
     * @param duplicationMapCallback consumer of the duplication map created during the copying
     */
    protected Graph copy(String newName, Consumer<Map<Node, Node>> duplicationMapCallback) {
        Graph copy = new Graph(newName);
        Map<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (Map<Node, Node>) null);
        if (duplicationMapCallback != null) {
            duplicationMapCallback.accept(duplicates);
        }
        return copy;
    }

    @Override
    public String toString() {
        return name == null ? super.toString() : "Graph " + name;
    }

    /**
     * Gets the number of live nodes in this graph. That is the number of nodes which have been
     * added to the graph minus the number of deleted nodes.
     *
     * @return the number of live nodes in this graph
     */
    public int getNodeCount() {
        return nodesSize - getNodesDeletedSinceLastCompression();
    }

    /**
     * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node
     * identifiers are only stable between compressions. To ensure this constraint is observed, any
     * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.
     */
    public int getCompressions() {
        return compressions;
    }

    /**
     * Gets the number of nodes which have been deleted from this graph since it was last
     * {@linkplain #maybeCompress() compressed}.
     */
    public int getNodesDeletedSinceLastCompression() {
        return nodesDeletedSinceLastCompression;
    }

    /**
     * Gets the total number of nodes which have been deleted from this graph.
     */
    public int getTotalNodesDeleted() {
        return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;
    }

    /**
     * Adds a new node to the graph.
     *
     * @param node the node to be added
     * @return the node which was added to the graph
     */
    public <T extends Node> T add(T node) {
        if (node.getNodeClass().valueNumberable()) {
            throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique.");
        }
        return addHelper(node);
    }

    public <T extends Node> T addWithoutUnique(T node) {
        return addHelper(node);
    }

    public <T extends Node> T addOrUnique(T node) {
        if (node.getNodeClass().valueNumberable()) {
            return uniqueHelper(node, true);
        }
        return add(node);
    }

    public <T extends Node> T addWithoutUniqueWithInputs(T node) {
        addInputs(node);
        return addHelper(node);
    }

    public <T extends Node> T addOrUniqueWithInputs(T node) {
        addInputs(node);
        if (node.getNodeClass().valueNumberable()) {
            return uniqueHelper(node, true);
        }
        return add(node);
    }

    private final class AddInputsFilter extends Node.EdgeVisitor {

        @Override
        public Node apply(Node self, Node input) {
            if (!input.isAlive()) {
                assert !input.isDeleted();
                return addOrUniqueWithInputs(input);
            } else {
                return input;
            }
        }

    }

    private AddInputsFilter addInputsFilter = new AddInputsFilter();

    private <T extends Node> void addInputs(T node) {
        node.applyInputs(addInputsFilter);
    }

    private <T extends Node> T addHelper(T node) {
        node.initialize(this);
        return node;
    }

    /**
     * The type of events sent to a {@link NodeEventListener}.
     */
    public enum NodeEvent {
        /**
         * A node's input is changed.
         */
        INPUT_CHANGED,

        /**
         * A node's {@linkplain Node#usages() usages} count dropped to zero.
         */
        ZERO_USAGES,

        /**
         * A node was added to a graph.
         */
        NODE_ADDED;
    }

    /**
     * Client interested in one or more node related events.
     */
    public interface NodeEventListener {

        /**
         * Default handler for events.
         *
         * @param e an event
         * @param node the node related to {@code e}
         */
        default void event(NodeEvent e, Node node) {
        }

        /**
         * Notifies this listener of a change in a node's inputs.
         *
         * @param node a node who has had one of its inputs changed
         */
        default void inputChanged(Node node) {
            event(NodeEvent.INPUT_CHANGED, node);
        }

        /**
         * Notifies this listener of a node becoming unused.
         *
         * @param node a node whose {@link Node#usages()} just became empty
         */
        default void usagesDroppedToZero(Node node) {
            event(NodeEvent.ZERO_USAGES, node);
        }

        /**
         * Notifies this listener of an added node.
         *
         * @param node a node that was just added to the graph
         */
        default void nodeAdded(Node node) {
            event(NodeEvent.NODE_ADDED, node);
        }
    }

    /**
     * Registers a given {@link NodeEventListener} with the enclosing graph until this object is
     * {@linkplain #close() closed}.
     */
    public final class NodeEventScope implements AutoCloseable {
        NodeEventScope(NodeEventListener listener) {
            if (nodeEventListener == null) {
                nodeEventListener = listener;
            } else {
                nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener);
            }
        }

        @Override
        public void close() {
            assert nodeEventListener != null;
            if (nodeEventListener instanceof ChainedNodeEventListener) {
                nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next;
            } else {
                nodeEventListener = null;
            }
        }
    }

    private static class ChainedNodeEventListener implements NodeEventListener {

        NodeEventListener head;
        NodeEventListener next;

        ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) {
            this.head = head;
            this.next = next;
        }

        @Override
        public void nodeAdded(Node node) {
            head.nodeAdded(node);
            next.nodeAdded(node);
        }

        @Override
        public void inputChanged(Node node) {
            head.inputChanged(node);
            next.inputChanged(node);
        }

        @Override
        public void usagesDroppedToZero(Node node) {
            head.usagesDroppedToZero(node);
            next.usagesDroppedToZero(node);
        }
    }

    /**
     * Registers a given {@link NodeEventListener} with this graph. This should be used in
     * conjunction with try-with-resources statement as follows:
     *
     * <pre>
     * try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
     *     // make changes to the graph
     * }
     * </pre>
     */
    public NodeEventScope trackNodeEvents(NodeEventListener listener) {
        return new NodeEventScope(listener);
    }

    /**
     * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise
     * {@code node} is added to this graph and returned.
     *
     * @return a node similar to {@code node} if one exists, otherwise {@code node}
     */
    public <T extends Node & ValueNumberable> T unique(T node) {
        return uniqueHelper(node, true);
    }

    <T extends Node> T uniqueHelper(T node, boolean addIfMissing) {
        assert node.getNodeClass().valueNumberable();
        T other = this.findDuplicate(node);
        if (other != null) {
            return other;
        } else {
            T result = addIfMissing ? addHelper(node) : node;
            if (node.getNodeClass().isLeafNode()) {
                putNodeIntoCache(result);
            }
            return result;
        }
    }

    void putNodeIntoCache(Node node) {
        assert node.graph() == this || node.graph() == null;
        assert node.getNodeClass().valueNumberable();
        assert node.getNodeClass().isLeafNode() : node.getClass();
        CacheEntry entry = new CacheEntry(node);
        cachedLeafNodes.put(entry, node);
    }

    Node findNodeInCache(Node node) {
        CacheEntry key = new CacheEntry(node);
        Node result = cachedLeafNodes.get(key);
        if (result != null && result.isDeleted()) {
            cachedLeafNodes.remove(key);
            return null;
        }
        return result;
    }

    /**
     * Returns a possible duplicate for the given node in the graph or {@code null} if no such
     * duplicate exists.
     */
    @SuppressWarnings("unchecked")
    public <T extends Node> T findDuplicate(T node) {
        NodeClass<?> nodeClass = node.getNodeClass();
        assert nodeClass.valueNumberable();
        if (nodeClass.isLeafNode()) {
            // Leaf node: look up in cache
            Node cachedNode = findNodeInCache(node);
            if (cachedNode != null && cachedNode != node) {
                return (T) cachedNode;
            } else {
                return null;
            }
        } else {
            /*
             * Non-leaf node: look for another usage of the node's inputs that has the same data,
             * inputs and successors as the node. To reduce the cost of this computation, only the
             * input with lowest usage count is considered. If this node is the only user of any
             * input then the search can terminate early. The usage count is only incremented once
             * the Node is in the Graph, so account for that in the test.
             */
            final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
            int minCount = Integer.MAX_VALUE;
            Node minCountNode = null;
            for (Node input : node.inputs()) {
                int usageCount = input.getUsageCount();
                if (usageCount == earlyExitUsageCount) {
                    return null;
                } else if (usageCount < minCount) {
                    minCount = usageCount;
                    minCountNode = input;
                }
            }
            if (minCountNode != null) {
                for (Node usage : minCountNode.usages()) {
                    if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.equalInputs(node, usage) &&
                                    nodeClass.equalSuccessors(node, usage)) {
                        return (T) usage;
                    }
                }
                return null;
            }
            return null;
        }
    }

    public boolean isNew(Mark mark, Node node) {
        return node.id >= mark.getValue();
    }

    /**
     * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
     */
    public static class Mark extends NodeIdAccessor {
        private final int value;

        Mark(Graph graph) {
            super(graph);
            this.value = graph.nodeIdCount();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Mark) {
                Mark other = (Mark) obj;
                return other.getValue() == getValue() && other.getGraph() == getGraph();
            }
            return false;
        }

        @Override
        public int hashCode() {
            return value ^ (epoch + 11);
        }

        /**
         * Determines if this mark is positioned at the first live node in the graph.
         */
        public boolean isStart() {
            return value == 0;
        }

        /**
         * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when
         * this object was created.
         */
        int getValue() {
            return value;
        }

        /**
         * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node
         * count} of the graph.
         */
        public boolean isCurrent() {
            return value == graph.nodeIdCount();
        }
    }

    /**
     * Gets a mark that can be used with {@link #getNewNodes}.
     */
    public Mark getMark() {
        return new Mark(this);
    }

    /**
     * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark()
     * mark}.
     */
    public NodeIterable<Node> getNewNodes(Mark mark) {
        final int index = mark == null ? 0 : mark.getValue();
        return new NodeIterable<Node>() {

            @Override
            public Iterator<Node> iterator() {
                return new GraphNodeIterator(Graph.this, index);
            }
        };
    }

    /**
     * Returns an {@link Iterable} providing all the live nodes.
     *
     * @return an {@link Iterable} providing all the live nodes.
     */
    public NodeIterable<Node> getNodes() {
        return new NodeIterable<Node>() {

            @Override
            public Iterator<Node> iterator() {
                return new GraphNodeIterator(Graph.this);
            }

            @Override
            public int count() {
                return getNodeCount();
            }
        };
    }

    // Fully qualified annotation name is required to satisfy javac
    @org.graalvm.compiler.nodeinfo.NodeInfo
    static final class PlaceHolderNode extends Node {

        public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class);

        protected PlaceHolderNode() {
            super(TYPE);
        }

    }

    static final Node PLACE_HOLDER = new PlaceHolderNode();

    public static final int COMPRESSION_THRESHOLD = Options.GraphCompressionThreshold.getValue();

    private static final DebugCounter GraphCompressions = Debug.counter("GraphCompressions");

    /**
     * If the {@linkplain #COMPRESSION_THRESHOLD compression threshold} is met, the list of nodes is
     * compressed such that all non-null entries precede all null entries while preserving the
     * ordering between the nodes within the list.
     */
    public boolean maybeCompress() {
        if (Debug.isDumpEnabledForMethod() || Debug.isLogEnabledForMethod()) {
            return false;
        }
        int liveNodeCount = getNodeCount();
        int liveNodePercent = liveNodeCount * 100 / nodesSize;
        if (COMPRESSION_THRESHOLD == 0 || liveNodePercent >= COMPRESSION_THRESHOLD) {
            return false;
        }
        GraphCompressions.increment();
        int nextId = 0;
        for (int i = 0; nextId < liveNodeCount; i++) {
            Node n = nodes[i];
            if (n != null) {
                assert n.id == i;
                if (i != nextId) {
                    assert n.id > nextId;
                    n.id = nextId;
                    nodes[nextId] = n;
                    nodes[i] = null;
                }
                nextId++;
            }
        }
        if (isModificationCountsEnabled()) {
            // This will cause any current iteration to fail with an assertion
            Arrays.fill(nodeModCounts, 0);
            Arrays.fill(nodeUsageModCounts, 0);
        }
        nodesSize = nextId;
        compressions++;
        nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
        nodesDeletedSinceLastCompression = 0;
        return true;
    }

    /**
     * Returns an {@link Iterable} providing all the live nodes whose type is compatible with
     * {@code type}.
     *
     * @param nodeClass the type of node to return
     * @return an {@link Iterable} providing all the matching nodes
     */
    public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) {
        return new NodeIterable<T>() {

            @Override
            public Iterator<T> iterator() {
                return new TypedGraphNodeIterator<>(nodeClass, Graph.this);
            }
        };
    }

    /**
     * Returns whether the graph contains at least one node of the given type.
     *
     * @param type the type of node that is checked for occurrence
     * @return whether there is at least one such node
     */
    public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) {
        return getNodes(type).iterator().hasNext();
    }

    /**
     * @param iterableId
     * @return the first live Node with a matching iterableId
     */
    Node getIterableNodeStart(int iterableId) {
        if (iterableNodesFirst.size() <= iterableId) {
            return null;
        }
        Node start = iterableNodesFirst.get(iterableId);
        if (start == null || !start.isDeleted()) {
            return start;
        }
        return findFirstLiveIterable(iterableId, start);
    }

    private Node findFirstLiveIterable(int iterableId, Node node) {
        Node start = node;
        while (start != null && start.isDeleted()) {
            start = start.typeCacheNext;
        }
        /*
         * Multiple threads iterating nodes can update this cache simultaneously. This is a benign
         * race, since all threads update it to the same value.
         */
        iterableNodesFirst.set(iterableId, start);
        if (start == null) {
            iterableNodesLast.set(iterableId, start);
        }
        return start;
    }

    /**
     * @param node
     * @return return the first live Node with a matching iterableId starting from {@code node}
     */
    Node getIterableNodeNext(Node node) {
        if (node == null) {
            return null;
        }
        Node n = node;
        if (n == null || !n.isDeleted()) {
            return n;
        }

        return findNextLiveiterable(node);
    }

    private Node findNextLiveiterable(Node start) {
        Node n = start;
        while (n != null && n.isDeleted()) {
            n = n.typeCacheNext;
        }
        if (n == null) {
            // Only dead nodes after this one
            start.typeCacheNext = null;
            int nodeClassId = start.getNodeClass().iterableId();
            assert nodeClassId != Node.NOT_ITERABLE;
            iterableNodesLast.set(nodeClassId, start);
        } else {
            // Everything in between is dead
            start.typeCacheNext = n;
        }
        return n;
    }

    public NodeBitMap createNodeBitMap() {
        return new NodeBitMap(this);
    }

    public <T> NodeMap<T> createNodeMap() {
        return new NodeMap<>(this);
    }

    public NodeFlood createNodeFlood() {
        return new NodeFlood(this);
    }

    public NodeWorkList createNodeWorkList() {
        return new NodeWorkList.SingletonNodeWorkList(this);
    }

    public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
        return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
    }

    void register(Node node) {
        assert !isFrozen();
        assert node.id() == Node.INITIAL_ID;
        if (nodes.length == nodesSize) {
            Node[] newNodes = new Node[(nodesSize * 2) + 1];
            System.arraycopy(nodes, 0, newNodes, 0, nodesSize);
            nodes = newNodes;
        }
        int id = nodesSize;
        nodes[id] = node;
        if (currentNodeSourcePosition != null) {
            node.setNodeSourcePosition(currentNodeSourcePosition);
        } else if (!seenNodeSourcePosition && node.getNodeSourcePosition() != null) {
            seenNodeSourcePosition = true;
        }
        nodesSize++;

        updateNodeCaches(node);

        node.id = id;
        if (nodeEventListener != null) {
            nodeEventListener.nodeAdded(node);
        }
        if (!seenNodeSourcePosition && node.sourcePosition != null) {
            seenNodeSourcePosition = true;
        }
        if (Fingerprint.ENABLED) {
            Fingerprint.submit("%s: %s", NodeEvent.NODE_ADDED, node);
        }
    }

    @SuppressWarnings("unused")
    private void postDeserialization() {
        recomputeIterableNodeLists();
    }

    /**
     * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for
     * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have
     * changed.
     */
    private void recomputeIterableNodeLists() {
        iterableNodesFirst.clear();
        iterableNodesLast.clear();
        for (Node node : nodes) {
            if (node != null && node.isAlive()) {
                updateNodeCaches(node);
            }
        }
    }

    private void updateNodeCaches(Node node) {
        int nodeClassId = node.getNodeClass().iterableId();
        if (nodeClassId != Node.NOT_ITERABLE) {
            while (iterableNodesFirst.size() <= nodeClassId) {
                iterableNodesFirst.add(null);
                iterableNodesLast.add(null);
            }
            Node prev = iterableNodesLast.get(nodeClassId);
            if (prev != null) {
                prev.typeCacheNext = node;
            } else {
                iterableNodesFirst.set(nodeClassId, node);
            }
            iterableNodesLast.set(nodeClassId, node);
        }
    }

    void unregister(Node node) {
        assert !isFrozen();
        assert !node.isDeleted() : "cannot delete a node twice! node=" + node;
        nodes[node.id] = null;
        nodesDeletedSinceLastCompression++;

        // nodes aren't removed from the type cache here - they will be removed during iteration
    }

    public boolean verify() {
        if (Options.VerifyGraalGraphs.getValue()) {
            for (Node node : getNodes()) {
                try {
                    try {
                        assert node.verify();
                    } catch (AssertionError t) {
                        throw new GraalError(t);
                    } catch (RuntimeException t) {
                        throw new GraalError(t);
                    }
                } catch (GraalError e) {
                    throw GraalGraphError.transformAndAddContext(e, node).addContext(this);
                }
            }
        }
        return true;
    }

    public Node getNode(int id) {
        return nodes[id];
    }

    /**
     * Returns the number of node ids generated so far.
     *
     * @return the number of node ids generated so far
     */
    int nodeIdCount() {
        return nodesSize;
    }

    /**
     * Adds duplicates of the nodes in {@code nodes} to this graph. This will recreate any edges
     * between the duplicate nodes. The {@code replacement} map can be used to replace a node from
     * the source graph by a given node (which must already be in this graph). Edges between
     * duplicate and replacement nodes will also be recreated so care should be taken regarding the
     * matching of node types in the replacement map.
     *
     * @param newNodes the nodes to be duplicated
     * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
     * @return a map which associates the original nodes from {@code nodes} to their duplicates
     */
    public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, Map<Node, Node> replacementsMap) {
        DuplicationReplacement replacements;
        if (replacementsMap == null) {
            replacements = null;
        } else {
            replacements = new MapReplacement(replacementsMap);
        }
        return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
    }

    public interface DuplicationReplacement {

        Node replacement(Node original);
    }

    private static final class MapReplacement implements DuplicationReplacement {

        private final Map<Node, Node> map;

        MapReplacement(Map<Node, Node> map) {
            this.map = map;
        }

        @Override
        public Node replacement(Node original) {
            Node replacement = map.get(original);
            return replacement != null ? replacement : original;
        }

    }

    private static final DebugTimer DuplicateGraph = Debug.timer("DuplicateGraph");

    @SuppressWarnings({"all", "try"})
    public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
        try (DebugCloseable s = DuplicateGraph.start()) {
            return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
        }
    }

    /**
     * Reverses the usage orders of all nodes. This is used for debugging to make sure an unorthodox
     * usage order does not trigger bugs in the compiler.
     */
    public void reverseUsageOrder() {
        for (Node n : getNodes()) {
            n.reverseUsageOrder();
        }
    }

    public boolean isFrozen() {
        return isFrozen;
    }

    public void freeze() {
        this.isFrozen = true;
    }
}