001/*
002 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph;
024
025import static com.oracle.graal.graph.Edges.Type.*;
026
027import java.util.*;
028import java.util.function.*;
029
030import jdk.internal.jvmci.common.*;
031import com.oracle.graal.debug.*;
032import jdk.internal.jvmci.options.*;
033
034import com.oracle.graal.compiler.common.*;
035import com.oracle.graal.graph.Node.ValueNumberable;
036import com.oracle.graal.graph.iterators.*;
037
038/**
039 * This class is a graph container, it contains the set of nodes that belong to this graph.
040 */
041public class Graph {
042
043    public static class Options {
044        @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)//
045        public static final OptionValue<Boolean> VerifyGraalGraphs = new OptionValue<>(true);
046        @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)//
047        public static final OptionValue<Boolean> VerifyGraalGraphEdges = new OptionValue<>(false);
048    }
049
050    public final String name;
051
052    /**
053     * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.
054     */
055    Node[] nodes;
056
057    /**
058     * The number of valid entries in {@link #nodes}.
059     */
060    int nodesSize;
061
062    /**
063     * Records the modification count for nodes. This is only used in assertions.
064     */
065    private int[] nodeModCounts;
066
067    /**
068     * Records the modification count for nodes' usage lists. This is only used in assertions.
069     */
070    private int[] nodeUsageModCounts;
071
072    // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.
073    // they contain the first and last pointer to a linked list of all nodes with this type.
074    private final ArrayList<Node> iterableNodesFirst;
075    private final ArrayList<Node> iterableNodesLast;
076
077    private int nodesDeletedSinceLastCompression;
078    private int nodesDeletedBeforeLastCompression;
079
080    /**
081     * The number of times this graph has been compressed.
082     */
083    int compressions;
084
085    NodeEventListener nodeEventListener;
086
087    /**
088     * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf}
089     * nodes.
090     */
091    private final HashMap<CacheEntry, Node> cachedLeafNodes = CollectionsFactory.newMap();
092
093    /*
094     * Indicates that the graph should no longer be modified. Frozen graphs can be used my multiple
095     * threads so it's only safe to read them.
096     */
097    private boolean isFrozen = false;
098
099    /**
100     * Entry in {@link Graph#cachedLeafNodes}.
101     */
102    private static final class CacheEntry {
103
104        private final Node node;
105
106        public CacheEntry(Node node) {
107            assert node.getNodeClass().valueNumberable();
108            assert node.getNodeClass().isLeafNode();
109            this.node = node;
110        }
111
112        @Override
113        public int hashCode() {
114            return node.getNodeClass().valueNumber(node);
115        }
116
117        @Override
118        public boolean equals(Object obj) {
119            if (obj == this) {
120                return true;
121            }
122            if (obj instanceof CacheEntry) {
123                CacheEntry other = (CacheEntry) obj;
124                if (other.node.getClass() == node.getClass()) {
125                    return node.valueEquals(other.node);
126                }
127            }
128            return false;
129        }
130
131        @Override
132        public String toString() {
133            return node.toString();
134        }
135    }
136
137    /**
138     * Creates an empty Graph with no name.
139     */
140    public Graph() {
141        this(null);
142    }
143
144    public static final boolean MODIFICATION_COUNTS_ENABLED = assertionsEnabled();
145
146    /**
147     * Determines if assertions are enabled for the {@link Graph} class.
148     */
149    @SuppressWarnings("all")
150    private static boolean assertionsEnabled() {
151        boolean enabled = false;
152        assert enabled = true;
153        return enabled;
154    }
155
156    private static final int INITIAL_NODES_SIZE = 32;
157
158    /**
159     * Creates an empty Graph with a given name.
160     *
161     * @param name the name of the graph, used for debugging purposes
162     */
163    public Graph(String name) {
164        nodes = new Node[INITIAL_NODES_SIZE];
165        iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
166        iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
167        this.name = name;
168        if (MODIFICATION_COUNTS_ENABLED) {
169            nodeModCounts = new int[INITIAL_NODES_SIZE];
170            nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
171        }
172    }
173
174    int extractOriginalNodeId(Node node) {
175        int id = node.id;
176        if (id <= Node.DELETED_ID_START) {
177            id = Node.DELETED_ID_START - id;
178        }
179        return id;
180    }
181
182    int modCount(Node node) {
183        int id = extractOriginalNodeId(node);
184        if (id >= 0 && id < nodeModCounts.length) {
185            return nodeModCounts[id];
186        }
187        return 0;
188    }
189
190    void incModCount(Node node) {
191        int id = extractOriginalNodeId(node);
192        if (id >= 0) {
193            if (id >= nodeModCounts.length) {
194                nodeModCounts = Arrays.copyOf(nodeModCounts, id + 30);
195            }
196            nodeModCounts[id]++;
197        } else {
198            assert false;
199        }
200    }
201
202    int usageModCount(Node node) {
203        int id = extractOriginalNodeId(node);
204        if (id >= 0 && id < nodeUsageModCounts.length) {
205            return nodeUsageModCounts[id];
206        }
207        return 0;
208    }
209
210    void incUsageModCount(Node node) {
211        int id = extractOriginalNodeId(node);
212        if (id >= 0) {
213            if (id >= nodeUsageModCounts.length) {
214                nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id + 30);
215            }
216            nodeUsageModCounts[id]++;
217        } else {
218            assert false;
219        }
220    }
221
222    /**
223     * Creates a copy of this graph.
224     */
225    public final Graph copy() {
226        return copy(name, null);
227    }
228
229    /**
230     * Creates a copy of this graph.
231     *
232     * @param duplicationMapCallback consumer of the duplication map created during the copying
233     */
234    public final Graph copy(Consumer<Map<Node, Node>> duplicationMapCallback) {
235        return copy(name, duplicationMapCallback);
236    }
237
238    /**
239     * Creates a copy of this graph.
240     *
241     * @param newName the name of the copy, used for debugging purposes (can be null)
242     */
243    public final Graph copy(String newName) {
244        return copy(newName, null);
245    }
246
247    /**
248     * Creates a copy of this graph.
249     *
250     * @param newName the name of the copy, used for debugging purposes (can be null)
251     * @param duplicationMapCallback consumer of the duplication map created during the copying
252     */
253    protected Graph copy(String newName, Consumer<Map<Node, Node>> duplicationMapCallback) {
254        Graph copy = new Graph(newName);
255        Map<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (Map<Node, Node>) null);
256        if (duplicationMapCallback != null) {
257            duplicationMapCallback.accept(duplicates);
258        }
259        return copy;
260    }
261
262    @Override
263    public String toString() {
264        return name == null ? super.toString() : "Graph " + name;
265    }
266
267    /**
268     * Gets the number of live nodes in this graph. That is the number of nodes which have been
269     * added to the graph minus the number of deleted nodes.
270     *
271     * @return the number of live nodes in this graph
272     */
273    public int getNodeCount() {
274        return nodesSize - getNodesDeletedSinceLastCompression();
275    }
276
277    /**
278     * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node
279     * identifiers are only stable between compressions. To ensure this constraint is observed, any
280     * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.
281     */
282    public int getCompressions() {
283        return compressions;
284    }
285
286    /**
287     * Gets the number of nodes which have been deleted from this graph since it was last
288     * {@linkplain #maybeCompress() compressed}.
289     */
290    public int getNodesDeletedSinceLastCompression() {
291        return nodesDeletedSinceLastCompression;
292    }
293
294    /**
295     * Gets the total number of nodes which have been deleted from this graph.
296     */
297    public int getTotalNodesDeleted() {
298        return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;
299    }
300
301    /**
302     * Adds a new node to the graph.
303     *
304     * @param node the node to be added
305     * @return the node which was added to the graph
306     */
307    public <T extends Node> T add(T node) {
308        if (node.getNodeClass().valueNumberable()) {
309            throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique.");
310        }
311        return addHelper(node);
312    }
313
314    public <T extends Node> T addWithoutUnique(T node) {
315        return addHelper(node);
316    }
317
318    public <T extends Node> T addOrUnique(T node) {
319        if (node.getNodeClass().valueNumberable()) {
320            return uniqueHelper(node, true);
321        }
322        return add(node);
323    }
324
325    public <T extends Node> void addWithoutUniqueWithInputs(T node) {
326        addInputs(node);
327        addHelper(node);
328    }
329
330    public <T extends Node> T addOrUniqueWithInputs(T node) {
331        addInputs(node);
332        if (node.getNodeClass().valueNumberable()) {
333            return uniqueHelper(node, true);
334        }
335        return add(node);
336    }
337
338    private <T extends Node> void addInputs(T node) {
339        NodePosIterator iterator = node.inputs().iterator();
340        while (iterator.hasNext()) {
341            Position pos = iterator.nextPosition();
342            Node input = pos.get(node);
343            if (input != null && !input.isAlive()) {
344                assert !input.isDeleted();
345                pos.initialize(node, addOrUniqueWithInputs(input));
346            }
347        }
348    }
349
350    private <T extends Node> T addHelper(T node) {
351        node.initialize(this);
352        return node;
353    }
354
355    /**
356     * The type of events sent to a {@link NodeEventListener}.
357     */
358    public enum NodeEvent {
359        /**
360         * A node's input is changed.
361         */
362        INPUT_CHANGED,
363
364        /**
365         * A node's {@linkplain Node#usages() usages} count dropped to zero.
366         */
367        ZERO_USAGES,
368
369        /**
370         * A node was added to a graph.
371         */
372        NODE_ADDED;
373    }
374
375    /**
376     * Client interested in one or more node related events.
377     */
378    public interface NodeEventListener {
379
380        /**
381         * Default handler for events.
382         *
383         * @param e an event
384         * @param node the node related to {@code e}
385         */
386        default void event(NodeEvent e, Node node) {
387        }
388
389        /**
390         * Notifies this listener of a change in a node's inputs.
391         *
392         * @param node a node who has had one of its inputs changed
393         */
394        default void inputChanged(Node node) {
395            event(NodeEvent.INPUT_CHANGED, node);
396        }
397
398        /**
399         * Notifies this listener of a node becoming unused.
400         *
401         * @param node a node whose {@link Node#usages()} just became empty
402         */
403        default void usagesDroppedToZero(Node node) {
404            event(NodeEvent.ZERO_USAGES, node);
405        }
406
407        /**
408         * Notifies this listener of an added node.
409         *
410         * @param node a node that was just added to the graph
411         */
412        default void nodeAdded(Node node) {
413            event(NodeEvent.NODE_ADDED, node);
414        }
415    }
416
417    /**
418     * Registers a given {@link NodeEventListener} with the enclosing graph until this object is
419     * {@linkplain #close() closed}.
420     */
421    public final class NodeEventScope implements AutoCloseable {
422        NodeEventScope(NodeEventListener listener) {
423            if (nodeEventListener == null) {
424                nodeEventListener = listener;
425            } else {
426                nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener);
427            }
428        }
429
430        public void close() {
431            assert nodeEventListener != null;
432            if (nodeEventListener instanceof ChainedNodeEventListener) {
433                nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next;
434            } else {
435                nodeEventListener = null;
436            }
437        }
438    }
439
440    private static class ChainedNodeEventListener implements NodeEventListener {
441
442        NodeEventListener head;
443        NodeEventListener next;
444
445        ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) {
446            this.head = head;
447            this.next = next;
448        }
449
450        public void nodeAdded(Node node) {
451            head.nodeAdded(node);
452            next.nodeAdded(node);
453        }
454
455        public void inputChanged(Node node) {
456            head.inputChanged(node);
457            next.inputChanged(node);
458        }
459
460        public void usagesDroppedToZero(Node node) {
461            head.usagesDroppedToZero(node);
462            next.usagesDroppedToZero(node);
463        }
464    }
465
466    /**
467     * Registers a given {@link NodeEventListener} with this graph. This should be used in
468     * conjunction with try-with-resources statement as follows:
469     *
470     * <pre>
471     * try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
472     *     // make changes to the graph
473     * }
474     * </pre>
475     */
476    public NodeEventScope trackNodeEvents(NodeEventListener listener) {
477        return new NodeEventScope(listener);
478    }
479
480    /**
481     * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise
482     * {@code node} is added to this graph and returned.
483     *
484     * @return a node similar to {@code node} if one exists, otherwise {@code node}
485     */
486    public <T extends Node & ValueNumberable> T unique(T node) {
487        return uniqueHelper(node, true);
488    }
489
490    <T extends Node> T uniqueHelper(T node, boolean addIfMissing) {
491        assert node.getNodeClass().valueNumberable();
492        T other = this.findDuplicate(node);
493        if (other != null) {
494            return other;
495        } else {
496            T result = addIfMissing ? addHelper(node) : node;
497            if (node.getNodeClass().isLeafNode()) {
498                putNodeIntoCache(result);
499            }
500            return result;
501        }
502    }
503
504    void putNodeIntoCache(Node node) {
505        assert node.graph() == this || node.graph() == null;
506        assert node.getNodeClass().valueNumberable();
507        assert node.getNodeClass().isLeafNode() : node.getClass();
508        cachedLeafNodes.put(new CacheEntry(node), node);
509    }
510
511    Node findNodeInCache(Node node) {
512        CacheEntry key = new CacheEntry(node);
513        Node result = cachedLeafNodes.get(key);
514        if (result != null && result.isDeleted()) {
515            cachedLeafNodes.remove(key);
516            return null;
517        }
518        return result;
519    }
520
521    @SuppressWarnings("unchecked")
522    public <T extends Node> T findDuplicate(T node) {
523        NodeClass<?> nodeClass = node.getNodeClass();
524        assert nodeClass.valueNumberable();
525        if (nodeClass.isLeafNode()) {
526            // Leaf node: look up in cache
527            Node cachedNode = findNodeInCache(node);
528            if (cachedNode != null) {
529                return (T) cachedNode;
530            } else {
531                return null;
532            }
533        } else {
534            /*
535             * Non-leaf node: look for another usage of the node's inputs that has the same data,
536             * inputs and successors as the node. To reduce the cost of this computation, only the
537             * input with lowest usage count is considered. If this node is the only user of any
538             * input then the search can terminate early. The usage count is only incremented once
539             * the Node is in the Graph, so account for that in the test.
540             */
541            final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
542            int minCount = Integer.MAX_VALUE;
543            Node minCountNode = null;
544            for (Node input : node.inputs()) {
545                if (input != null) {
546                    int usageCount = input.getUsageCount();
547                    if (usageCount == earlyExitUsageCount) {
548                        return null;
549                    } else if (usageCount < minCount) {
550                        minCount = usageCount;
551                        minCountNode = input;
552                    }
553                }
554            }
555            if (minCountNode != null) {
556                for (Node usage : minCountNode.usages()) {
557                    if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.getInputEdges().areEqualIn(node, usage) &&
558                                    nodeClass.getEdges(Successors).areEqualIn(node, usage)) {
559                        return (T) usage;
560                    }
561                }
562                return null;
563            }
564            return null;
565        }
566    }
567
568    public boolean isNew(Mark mark, Node node) {
569        return node.id >= mark.getValue();
570    }
571
572    /**
573     * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
574     */
575    public static class Mark extends NodeIdAccessor {
576        private final int value;
577
578        Mark(Graph graph) {
579            super(graph);
580            this.value = graph.nodeIdCount();
581        }
582
583        @Override
584        public boolean equals(Object obj) {
585            if (obj instanceof Mark) {
586                Mark other = (Mark) obj;
587                return other.getValue() == getValue() && other.getGraph() == getGraph();
588            }
589            return false;
590        }
591
592        @Override
593        public int hashCode() {
594            return value ^ (epoch + 11);
595        }
596
597        /**
598         * Determines if this mark is positioned at the first live node in the graph.
599         */
600        public boolean isStart() {
601            return value == 0;
602        }
603
604        /**
605         * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when
606         * this object was created.
607         */
608        int getValue() {
609            return value;
610        }
611
612        /**
613         * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node
614         * count} of the graph.
615         */
616        public boolean isCurrent() {
617            return value == graph.nodeIdCount();
618        }
619    }
620
621    /**
622     * Gets a mark that can be used with {@link #getNewNodes}.
623     */
624    public Mark getMark() {
625        return new Mark(this);
626    }
627
628    /**
629     * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark()
630     * mark}.
631     */
632    public NodeIterable<Node> getNewNodes(Mark mark) {
633        final int index = mark == null ? 0 : mark.getValue();
634        return new NodeIterable<Node>() {
635
636            @Override
637            public Iterator<Node> iterator() {
638                return new GraphNodeIterator(Graph.this, index);
639            }
640        };
641    }
642
643    /**
644     * Returns an {@link Iterable} providing all the live nodes.
645     *
646     * @return an {@link Iterable} providing all the live nodes.
647     */
648    public NodeIterable<Node> getNodes() {
649        return new NodeIterable<Node>() {
650
651            @Override
652            public Iterator<Node> iterator() {
653                return new GraphNodeIterator(Graph.this);
654            }
655
656            @Override
657            public int count() {
658                return getNodeCount();
659            }
660        };
661    }
662
663    // Fully qualified annotation name is required to satisfy javac
664    @com.oracle.graal.nodeinfo.NodeInfo
665    static final class PlaceHolderNode extends Node {
666
667        public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class);
668
669        public PlaceHolderNode() {
670            super(TYPE);
671        }
672
673    }
674
675    static final Node PLACE_HOLDER = new PlaceHolderNode();
676
677    /**
678     * When the percent of live nodes in {@link #nodes} fall below this number, a call to
679     * {@link #maybeCompress()} will actually do compression.
680     */
681    public static final int COMPRESSION_THRESHOLD = Integer.getInteger("graal.graphCompressionThreshold", 70);
682
683    private static final DebugMetric GraphCompressions = Debug.metric("GraphCompressions");
684
685    /**
686     * If the {@linkplain #COMPRESSION_THRESHOLD compression threshold} is met, the list of nodes is
687     * compressed such that all non-null entries precede all null entries while preserving the
688     * ordering between the nodes within the list.
689     */
690    public boolean maybeCompress() {
691        if (Debug.isDumpEnabledForMethod() || Debug.isLogEnabledForMethod()) {
692            return false;
693        }
694        int liveNodeCount = getNodeCount();
695        int liveNodePercent = liveNodeCount * 100 / nodesSize;
696        if (COMPRESSION_THRESHOLD == 0 || liveNodePercent >= COMPRESSION_THRESHOLD) {
697            return false;
698        }
699        GraphCompressions.increment();
700        int nextId = 0;
701        for (int i = 0; nextId < liveNodeCount; i++) {
702            Node n = nodes[i];
703            if (n != null) {
704                assert n.id == i;
705                if (i != nextId) {
706                    assert n.id > nextId;
707                    n.id = nextId;
708                    nodes[nextId] = n;
709                    nodes[i] = null;
710                }
711                nextId++;
712            }
713        }
714        if (MODIFICATION_COUNTS_ENABLED) {
715            // This will cause any current iteration to fail with an assertion
716            Arrays.fill(nodeModCounts, 0);
717            Arrays.fill(nodeUsageModCounts, 0);
718        }
719        nodesSize = nextId;
720        compressions++;
721        nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
722        nodesDeletedSinceLastCompression = 0;
723        return true;
724    }
725
726    /**
727     * Returns an {@link Iterable} providing all the live nodes whose type is compatible with
728     * {@code type}.
729     *
730     * @param nodeClass the type of node to return
731     * @return an {@link Iterable} providing all the matching nodes
732     */
733    public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) {
734        return new NodeIterable<T>() {
735
736            @Override
737            public Iterator<T> iterator() {
738                return new TypedGraphNodeIterator<>(nodeClass, Graph.this);
739            }
740        };
741    }
742
743    /**
744     * Returns whether the graph contains at least one node of the given type.
745     *
746     * @param type the type of node that is checked for occurrence
747     * @return whether there is at least one such node
748     */
749    public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) {
750        return getNodes(type).iterator().hasNext();
751    }
752
753    /**
754     * @param iterableId
755     * @return the first live Node with a matching iterableId
756     */
757    Node getIterableNodeStart(int iterableId) {
758        if (iterableNodesFirst.size() <= iterableId) {
759            return null;
760        }
761        Node start = iterableNodesFirst.get(iterableId);
762        if (start == null || !start.isDeleted()) {
763            return start;
764        }
765        return findFirstLiveIterable(iterableId, start);
766    }
767
768    private Node findFirstLiveIterable(int iterableId, Node node) {
769        assert iterableNodesFirst.get(iterableId) == node;
770        Node start = node;
771        while (start != null && start.isDeleted()) {
772            start = start.typeCacheNext;
773        }
774        iterableNodesFirst.set(iterableId, start);
775        if (start == null) {
776            iterableNodesLast.set(iterableId, start);
777        }
778        return start;
779    }
780
781    /**
782     * @param node
783     * @return return the first live Node with a matching iterableId starting from {@code node}
784     */
785    Node getIterableNodeNext(Node node) {
786        if (node == null) {
787            return null;
788        }
789        Node n = node;
790        if (n == null || !n.isDeleted()) {
791            return n;
792        }
793
794        return findNextLiveiterable(node);
795    }
796
797    private Node findNextLiveiterable(Node start) {
798        Node n = start;
799        while (n != null && n.isDeleted()) {
800            n = n.typeCacheNext;
801        }
802        if (n == null) {
803            // Only dead nodes after this one
804            start.typeCacheNext = null;
805            int nodeClassId = start.getNodeClass().iterableId();
806            assert nodeClassId != Node.NOT_ITERABLE;
807            iterableNodesLast.set(nodeClassId, start);
808        } else {
809            // Everything in between is dead
810            start.typeCacheNext = n;
811        }
812        return n;
813    }
814
815    public NodeBitMap createNodeBitMap() {
816        return new NodeBitMap(this);
817    }
818
819    public <T> NodeMap<T> createNodeMap() {
820        return new NodeMap<>(this);
821    }
822
823    public NodeFlood createNodeFlood() {
824        return new NodeFlood(this);
825    }
826
827    public NodeWorkList createNodeWorkList() {
828        return new NodeWorkList.SingletonNodeWorkList(this);
829    }
830
831    public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
832        return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
833    }
834
835    void register(Node node) {
836        assert !isFrozen();
837        assert node.id() == Node.INITIAL_ID;
838        if (nodes.length == nodesSize) {
839            Node[] newNodes = new Node[(nodesSize * 2) + 1];
840            System.arraycopy(nodes, 0, newNodes, 0, nodesSize);
841            nodes = newNodes;
842        }
843        int id = nodesSize;
844        nodes[id] = node;
845        nodesSize++;
846
847        updateNodeCaches(node);
848
849        node.id = id;
850        if (nodeEventListener != null) {
851            nodeEventListener.nodeAdded(node);
852        }
853        if (Fingerprint.ENABLED) {
854            Fingerprint.submit("%s: %s", NodeEvent.NODE_ADDED, node);
855        }
856    }
857
858    @SuppressWarnings("unused")
859    private void postDeserialization() {
860        recomputeIterableNodeLists();
861    }
862
863    /**
864     * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for
865     * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have
866     * changed.
867     */
868    private void recomputeIterableNodeLists() {
869        iterableNodesFirst.clear();
870        iterableNodesLast.clear();
871        for (Node node : nodes) {
872            if (node != null && node.isAlive()) {
873                updateNodeCaches(node);
874            }
875        }
876    }
877
878    private void updateNodeCaches(Node node) {
879        int nodeClassId = node.getNodeClass().iterableId();
880        if (nodeClassId != Node.NOT_ITERABLE) {
881            while (iterableNodesFirst.size() <= nodeClassId) {
882                iterableNodesFirst.add(null);
883                iterableNodesLast.add(null);
884            }
885            Node prev = iterableNodesLast.get(nodeClassId);
886            if (prev != null) {
887                prev.typeCacheNext = node;
888            } else {
889                iterableNodesFirst.set(nodeClassId, node);
890            }
891            iterableNodesLast.set(nodeClassId, node);
892        }
893    }
894
895    void unregister(Node node) {
896        assert !isFrozen();
897        assert !node.isDeleted() : "cannot delete a node twice! node=" + node;
898        nodes[node.id] = null;
899        nodesDeletedSinceLastCompression++;
900
901        // nodes aren't removed from the type cache here - they will be removed during iteration
902    }
903
904    public boolean verify() {
905        if (Options.VerifyGraalGraphs.getValue()) {
906            for (Node node : getNodes()) {
907                try {
908                    try {
909                        assert node.verify();
910                    } catch (AssertionError t) {
911                        throw new JVMCIError(t);
912                    } catch (RuntimeException t) {
913                        throw new JVMCIError(t);
914                    }
915                } catch (JVMCIError e) {
916                    throw GraalGraphJVMCIError.transformAndAddContext(e, node).addContext(this);
917                }
918            }
919        }
920        return true;
921    }
922
923    public Node getNode(int id) {
924        return nodes[id];
925    }
926
927    /**
928     * Returns the number of node ids generated so far.
929     *
930     * @return the number of node ids generated so far
931     */
932    int nodeIdCount() {
933        return nodesSize;
934    }
935
936    /**
937     * Adds duplicates of the nodes in {@code nodes} to this graph. This will recreate any edges
938     * between the duplicate nodes. The {@code replacement} map can be used to replace a node from
939     * the source graph by a given node (which must already be in this graph). Edges between
940     * duplicate and replacement nodes will also be recreated so care should be taken regarding the
941     * matching of node types in the replacement map.
942     *
943     * @param newNodes the nodes to be duplicated
944     * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
945     * @return a map which associates the original nodes from {@code nodes} to their duplicates
946     */
947    public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, Map<Node, Node> replacementsMap) {
948        DuplicationReplacement replacements;
949        if (replacementsMap == null) {
950            replacements = null;
951        } else {
952            replacements = new MapReplacement(replacementsMap);
953        }
954        return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
955    }
956
957    public interface DuplicationReplacement {
958
959        Node replacement(Node original);
960    }
961
962    private static final class MapReplacement implements DuplicationReplacement {
963
964        private final Map<Node, Node> map;
965
966        public MapReplacement(Map<Node, Node> map) {
967            this.map = map;
968        }
969
970        @Override
971        public Node replacement(Node original) {
972            Node replacement = map.get(original);
973            return replacement != null ? replacement : original;
974        }
975
976    }
977
978    private static final DebugTimer DuplicateGraph = Debug.timer("DuplicateGraph");
979
980    @SuppressWarnings("all")
981    public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
982        try (DebugCloseable s = DuplicateGraph.start()) {
983            return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
984        }
985    }
986
987    /**
988     * Reverses the usage orders of all nodes. This is used for debugging to make sure an unorthodox
989     * usage order does not trigger bugs in the compiler.
990     */
991    public void reverseUsageOrder() {
992        for (Node n : getNodes()) {
993            n.reverseUsageOrder();
994        }
995    }
996
997    public boolean isFrozen() {
998        return isFrozen;
999    }
1000
1001    public void freeze() {
1002        this.isFrozen = true;
1003    }
1004}