1 /*
   2  * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.graph;
  24 
  25 import java.util.ArrayList;
  26 import java.util.Arrays;
  27 import java.util.HashMap;
  28 import java.util.Iterator;
  29 import java.util.Map;
  30 import java.util.function.Consumer;
  31 
  32 import org.graalvm.compiler.core.common.CollectionsFactory;
  33 import org.graalvm.compiler.debug.Debug;
  34 import org.graalvm.compiler.debug.DebugCloseable;
  35 import org.graalvm.compiler.debug.DebugCounter;
  36 import org.graalvm.compiler.debug.DebugTimer;
  37 import org.graalvm.compiler.debug.Fingerprint;
  38 import org.graalvm.compiler.debug.GraalError;
  39 import org.graalvm.compiler.graph.Node.ValueNumberable;
  40 import org.graalvm.compiler.graph.iterators.NodeIterable;
  41 import org.graalvm.compiler.options.Option;
  42 import org.graalvm.compiler.options.OptionType;
  43 import org.graalvm.compiler.options.OptionValue;
  44 
  45 /**
  46  * This class is a graph container, it contains the set of nodes that belong to this graph.
  47  */
  48 public class Graph {
  49 
  50     public static class Options {
  51         @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)//
  52         public static final OptionValue<Boolean> VerifyGraalGraphs = new OptionValue<>(true);
  53         @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)//
  54         public static final OptionValue<Boolean> VerifyGraalGraphEdges = new OptionValue<>(false);
  55         @Option(help = "Graal graph compression is performed when percent of live nodes falls below this value", type = OptionType.Debug)//
  56         public static final OptionValue<Integer> GraphCompressionThreshold = new OptionValue<>(70);
  57         @Option(help = "Use Unsafe to clone graph nodes thus avoiding copying fields that will be re-initialized anyway", type = OptionType.Debug)//
  58         public static final OptionValue<Boolean> CloneNodesWithUnsafe = new OptionValue<>(true);
  59     }
  60 
  61     public final String name;
  62 
  63     /**
  64      * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.
  65      */
  66     Node[] nodes;
  67 
  68     /**
  69      * Source information to associate with newly created nodes.
  70      */
  71     NodeSourcePosition currentNodeSourcePosition;
  72 
  73     /**
  74      * Records if updating of node source information is required when performing inlining.
  75      */
  76     boolean seenNodeSourcePosition;
  77 
  78     /**
  79      * The number of valid entries in {@link #nodes}.
  80      */
  81     int nodesSize;
  82 
  83     /**
  84      * Records the modification count for nodes. This is only used in assertions.
  85      */
  86     private int[] nodeModCounts;
  87 
  88     /**
  89      * Records the modification count for nodes' usage lists. This is only used in assertions.
  90      */
  91     private int[] nodeUsageModCounts;
  92 
  93     // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.
  94     // they contain the first and last pointer to a linked list of all nodes with this type.
  95     private final ArrayList<Node> iterableNodesFirst;
  96     private final ArrayList<Node> iterableNodesLast;
  97 
  98     private int nodesDeletedSinceLastCompression;
  99     private int nodesDeletedBeforeLastCompression;
 100 
 101     /**
 102      * The number of times this graph has been compressed.
 103      */
 104     int compressions;
 105 
 106     NodeEventListener nodeEventListener;
 107 
 108     /**
 109      * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf}
 110      * nodes.
 111      */
 112     private final HashMap<CacheEntry, Node> cachedLeafNodes = CollectionsFactory.newMap();
 113 
 114     /*
 115      * Indicates that the graph should no longer be modified. Frozen graphs can be used my multiple
 116      * threads so it's only safe to read them.
 117      */
 118     private boolean isFrozen = false;
 119 
 120     /**
 121      * Entry in {@link Graph#cachedLeafNodes}.
 122      */
 123     private static final class CacheEntry {
 124 
 125         private final Node node;
 126 
 127         CacheEntry(Node node) {
 128             assert node.getNodeClass().valueNumberable();
 129             assert node.getNodeClass().isLeafNode();
 130             this.node = node;
 131         }
 132 
 133         @Override
 134         public int hashCode() {
 135             return node.getNodeClass().valueNumber(node);
 136         }
 137 
 138         @Override
 139         public boolean equals(Object obj) {
 140             if (obj == this) {
 141                 return true;
 142             }
 143             if (obj instanceof CacheEntry) {
 144                 CacheEntry other = (CacheEntry) obj;
 145                 if (other.node.getClass() == node.getClass()) {
 146                     return node.valueEquals(other.node);
 147                 }
 148             }
 149             return false;
 150         }
 151 
 152         @Override
 153         public String toString() {
 154             return node.toString();
 155         }
 156     }
 157 
 158     private class NodeSourcePositionScope implements DebugCloseable {
 159         private final NodeSourcePosition previous;
 160 
 161         NodeSourcePositionScope(NodeSourcePosition sourcePosition) {
 162             previous = currentNodeSourcePosition;
 163             currentNodeSourcePosition = sourcePosition;
 164         }
 165 
 166         @Override
 167         public void close() {
 168             currentNodeSourcePosition = previous;
 169         }
 170     }
 171 
 172     public NodeSourcePosition currentNodeSourcePosition() {
 173         return currentNodeSourcePosition;
 174     }
 175 
 176     /**
 177      * Opens a scope in which the source information from {@code node} is copied into nodes created
 178      * within the scope. If {@code node} has no source information information, no scope is opened
 179      * and {@code null} is returned.
 180      *
 181      * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
 182      *         was opened
 183      */
 184     public DebugCloseable withNodeSourcePosition(Node node) {
 185         return withNodeSourcePosition(node.sourcePosition);
 186     }
 187 
 188     /**
 189      * Opens a scope in which {@code sourcePosition} is copied into nodes created within the scope.
 190      * If {@code sourcePosition == null}, no scope is opened and {@code null} is returned.
 191      *
 192      * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
 193      *         was opened
 194      */
 195     public DebugCloseable withNodeSourcePosition(NodeSourcePosition sourcePosition) {
 196         return sourcePosition != null ? new NodeSourcePositionScope(sourcePosition) : null;
 197     }
 198 
 199     /**
 200      * Opens a scope in which newly created nodes do not get any source information added.
 201      *
 202      * @return a {@link DebugCloseable} for managing the opened scope
 203      */
 204     public DebugCloseable withoutNodeSourcePosition() {
 205         return new NodeSourcePositionScope(null);
 206     }
 207 
 208     /**
 209      * Determines if this graph might contain nodes with source information. This is mainly useful
 210      * to short circuit logic for updating those positions after inlining since that requires
 211      * visiting every node in the graph.
 212      */
 213     public boolean mayHaveNodeSourcePosition() {
 214         assert seenNodeSourcePosition || verifyHasNoSourcePosition();
 215         return seenNodeSourcePosition;
 216     }
 217 
 218     private boolean verifyHasNoSourcePosition() {
 219         for (Node node : getNodes()) {
 220             assert node.getNodeSourcePosition() == null;
 221         }
 222         return true;
 223     }
 224 
 225     /**
 226      * Creates an empty Graph with no name.
 227      */
 228     public Graph() {
 229         this(null);
 230     }
 231 
 232     /**
 233      * We only want the expensive modification count tracking when assertions are enabled for the
 234      * {@link Graph} class.
 235      */
 236     @SuppressWarnings("all")
 237     public static boolean isModificationCountsEnabled() {
 238         boolean enabled = false;
 239         assert enabled = true;
 240         return enabled;
 241     }
 242 
 243     private static final int INITIAL_NODES_SIZE = 32;
 244 
 245     /**
 246      * Creates an empty Graph with a given name.
 247      *
 248      * @param name the name of the graph, used for debugging purposes
 249      */
 250     public Graph(String name) {
 251         nodes = new Node[INITIAL_NODES_SIZE];
 252         iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
 253         iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
 254         this.name = name;
 255         if (isModificationCountsEnabled()) {
 256             nodeModCounts = new int[INITIAL_NODES_SIZE];
 257             nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
 258         }
 259     }
 260 
 261     int extractOriginalNodeId(Node node) {
 262         int id = node.id;
 263         if (id <= Node.DELETED_ID_START) {
 264             id = Node.DELETED_ID_START - id;
 265         }
 266         return id;
 267     }
 268 
 269     int modCount(Node node) {
 270         int id = extractOriginalNodeId(node);
 271         if (id >= 0 && id < nodeModCounts.length) {
 272             return nodeModCounts[id];
 273         }
 274         return 0;
 275     }
 276 
 277     void incModCount(Node node) {
 278         int id = extractOriginalNodeId(node);
 279         if (id >= 0) {
 280             if (id >= nodeModCounts.length) {
 281                 nodeModCounts = Arrays.copyOf(nodeModCounts, id * 2 + 30);
 282             }
 283             nodeModCounts[id]++;
 284         } else {
 285             assert false;
 286         }
 287     }
 288 
 289     int usageModCount(Node node) {
 290         int id = extractOriginalNodeId(node);
 291         if (id >= 0 && id < nodeUsageModCounts.length) {
 292             return nodeUsageModCounts[id];
 293         }
 294         return 0;
 295     }
 296 
 297     void incUsageModCount(Node node) {
 298         int id = extractOriginalNodeId(node);
 299         if (id >= 0) {
 300             if (id >= nodeUsageModCounts.length) {
 301                 nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id * 2 + 30);
 302             }
 303             nodeUsageModCounts[id]++;
 304         } else {
 305             assert false;
 306         }
 307     }
 308 
 309     /**
 310      * Creates a copy of this graph.
 311      */
 312     public final Graph copy() {
 313         return copy(name, null);
 314     }
 315 
 316     /**
 317      * Creates a copy of this graph.
 318      *
 319      * @param duplicationMapCallback consumer of the duplication map created during the copying
 320      */
 321     public final Graph copy(Consumer<Map<Node, Node>> duplicationMapCallback) {
 322         return copy(name, duplicationMapCallback);
 323     }
 324 
 325     /**
 326      * Creates a copy of this graph.
 327      *
 328      * @param newName the name of the copy, used for debugging purposes (can be null)
 329      */
 330     public final Graph copy(String newName) {
 331         return copy(newName, null);
 332     }
 333 
 334     /**
 335      * Creates a copy of this graph.
 336      *
 337      * @param newName the name of the copy, used for debugging purposes (can be null)
 338      * @param duplicationMapCallback consumer of the duplication map created during the copying
 339      */
 340     protected Graph copy(String newName, Consumer<Map<Node, Node>> duplicationMapCallback) {
 341         Graph copy = new Graph(newName);
 342         Map<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (Map<Node, Node>) null);
 343         if (duplicationMapCallback != null) {
 344             duplicationMapCallback.accept(duplicates);
 345         }
 346         return copy;
 347     }
 348 
 349     @Override
 350     public String toString() {
 351         return name == null ? super.toString() : "Graph " + name;
 352     }
 353 
 354     /**
 355      * Gets the number of live nodes in this graph. That is the number of nodes which have been
 356      * added to the graph minus the number of deleted nodes.
 357      *
 358      * @return the number of live nodes in this graph
 359      */
 360     public int getNodeCount() {
 361         return nodesSize - getNodesDeletedSinceLastCompression();
 362     }
 363 
 364     /**
 365      * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node
 366      * identifiers are only stable between compressions. To ensure this constraint is observed, any
 367      * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.
 368      */
 369     public int getCompressions() {
 370         return compressions;
 371     }
 372 
 373     /**
 374      * Gets the number of nodes which have been deleted from this graph since it was last
 375      * {@linkplain #maybeCompress() compressed}.
 376      */
 377     public int getNodesDeletedSinceLastCompression() {
 378         return nodesDeletedSinceLastCompression;
 379     }
 380 
 381     /**
 382      * Gets the total number of nodes which have been deleted from this graph.
 383      */
 384     public int getTotalNodesDeleted() {
 385         return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;
 386     }
 387 
 388     /**
 389      * Adds a new node to the graph.
 390      *
 391      * @param node the node to be added
 392      * @return the node which was added to the graph
 393      */
 394     public <T extends Node> T add(T node) {
 395         if (node.getNodeClass().valueNumberable()) {
 396             throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique.");
 397         }
 398         return addHelper(node);
 399     }
 400 
 401     public <T extends Node> T addWithoutUnique(T node) {
 402         return addHelper(node);
 403     }
 404 
 405     public <T extends Node> T addOrUnique(T node) {
 406         if (node.getNodeClass().valueNumberable()) {
 407             return uniqueHelper(node, true);
 408         }
 409         return add(node);
 410     }
 411 
 412     public <T extends Node> T addWithoutUniqueWithInputs(T node) {
 413         addInputs(node);
 414         return addHelper(node);
 415     }
 416 
 417     public <T extends Node> T addOrUniqueWithInputs(T node) {
 418         addInputs(node);
 419         if (node.getNodeClass().valueNumberable()) {
 420             return uniqueHelper(node, true);
 421         }
 422         return add(node);
 423     }
 424 
 425     private final class AddInputsFilter extends Node.EdgeVisitor {
 426 
 427         @Override
 428         public Node apply(Node self, Node input) {
 429             if (!input.isAlive()) {
 430                 assert !input.isDeleted();
 431                 return addOrUniqueWithInputs(input);
 432             } else {
 433                 return input;
 434             }
 435         }
 436 
 437     }
 438 
 439     private AddInputsFilter addInputsFilter = new AddInputsFilter();
 440 
 441     private <T extends Node> void addInputs(T node) {
 442         node.applyInputs(addInputsFilter);
 443     }
 444 
 445     private <T extends Node> T addHelper(T node) {
 446         node.initialize(this);
 447         return node;
 448     }
 449 
 450     /**
 451      * The type of events sent to a {@link NodeEventListener}.
 452      */
 453     public enum NodeEvent {
 454         /**
 455          * A node's input is changed.
 456          */
 457         INPUT_CHANGED,
 458 
 459         /**
 460          * A node's {@linkplain Node#usages() usages} count dropped to zero.
 461          */
 462         ZERO_USAGES,
 463 
 464         /**
 465          * A node was added to a graph.
 466          */
 467         NODE_ADDED;
 468     }
 469 
 470     /**
 471      * Client interested in one or more node related events.
 472      */
 473     public interface NodeEventListener {
 474 
 475         /**
 476          * Default handler for events.
 477          *
 478          * @param e an event
 479          * @param node the node related to {@code e}
 480          */
 481         default void event(NodeEvent e, Node node) {
 482         }
 483 
 484         /**
 485          * Notifies this listener of a change in a node's inputs.
 486          *
 487          * @param node a node who has had one of its inputs changed
 488          */
 489         default void inputChanged(Node node) {
 490             event(NodeEvent.INPUT_CHANGED, node);
 491         }
 492 
 493         /**
 494          * Notifies this listener of a node becoming unused.
 495          *
 496          * @param node a node whose {@link Node#usages()} just became empty
 497          */
 498         default void usagesDroppedToZero(Node node) {
 499             event(NodeEvent.ZERO_USAGES, node);
 500         }
 501 
 502         /**
 503          * Notifies this listener of an added node.
 504          *
 505          * @param node a node that was just added to the graph
 506          */
 507         default void nodeAdded(Node node) {
 508             event(NodeEvent.NODE_ADDED, node);
 509         }
 510     }
 511 
 512     /**
 513      * Registers a given {@link NodeEventListener} with the enclosing graph until this object is
 514      * {@linkplain #close() closed}.
 515      */
 516     public final class NodeEventScope implements AutoCloseable {
 517         NodeEventScope(NodeEventListener listener) {
 518             if (nodeEventListener == null) {
 519                 nodeEventListener = listener;
 520             } else {
 521                 nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener);
 522             }
 523         }
 524 
 525         @Override
 526         public void close() {
 527             assert nodeEventListener != null;
 528             if (nodeEventListener instanceof ChainedNodeEventListener) {
 529                 nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next;
 530             } else {
 531                 nodeEventListener = null;
 532             }
 533         }
 534     }
 535 
 536     private static class ChainedNodeEventListener implements NodeEventListener {
 537 
 538         NodeEventListener head;
 539         NodeEventListener next;
 540 
 541         ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) {
 542             this.head = head;
 543             this.next = next;
 544         }
 545 
 546         @Override
 547         public void nodeAdded(Node node) {
 548             head.nodeAdded(node);
 549             next.nodeAdded(node);
 550         }
 551 
 552         @Override
 553         public void inputChanged(Node node) {
 554             head.inputChanged(node);
 555             next.inputChanged(node);
 556         }
 557 
 558         @Override
 559         public void usagesDroppedToZero(Node node) {
 560             head.usagesDroppedToZero(node);
 561             next.usagesDroppedToZero(node);
 562         }
 563     }
 564 
 565     /**
 566      * Registers a given {@link NodeEventListener} with this graph. This should be used in
 567      * conjunction with try-with-resources statement as follows:
 568      *
 569      * <pre>
 570      * try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
 571      *     // make changes to the graph
 572      * }
 573      * </pre>
 574      */
 575     public NodeEventScope trackNodeEvents(NodeEventListener listener) {
 576         return new NodeEventScope(listener);
 577     }
 578 
 579     /**
 580      * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise
 581      * {@code node} is added to this graph and returned.
 582      *
 583      * @return a node similar to {@code node} if one exists, otherwise {@code node}
 584      */
 585     public <T extends Node & ValueNumberable> T unique(T node) {
 586         return uniqueHelper(node, true);
 587     }
 588 
 589     <T extends Node> T uniqueHelper(T node, boolean addIfMissing) {
 590         assert node.getNodeClass().valueNumberable();
 591         T other = this.findDuplicate(node);
 592         if (other != null) {
 593             return other;
 594         } else {
 595             T result = addIfMissing ? addHelper(node) : node;
 596             if (node.getNodeClass().isLeafNode()) {
 597                 putNodeIntoCache(result);
 598             }
 599             return result;
 600         }
 601     }
 602 
 603     void putNodeIntoCache(Node node) {
 604         assert node.graph() == this || node.graph() == null;
 605         assert node.getNodeClass().valueNumberable();
 606         assert node.getNodeClass().isLeafNode() : node.getClass();
 607         CacheEntry entry = new CacheEntry(node);
 608         cachedLeafNodes.put(entry, node);
 609     }
 610 
 611     Node findNodeInCache(Node node) {
 612         CacheEntry key = new CacheEntry(node);
 613         Node result = cachedLeafNodes.get(key);
 614         if (result != null && result.isDeleted()) {
 615             cachedLeafNodes.remove(key);
 616             return null;
 617         }
 618         return result;
 619     }
 620 
 621     /**
 622      * Returns a possible duplicate for the given node in the graph or {@code null} if no such
 623      * duplicate exists.
 624      */
 625     @SuppressWarnings("unchecked")
 626     public <T extends Node> T findDuplicate(T node) {
 627         NodeClass<?> nodeClass = node.getNodeClass();
 628         assert nodeClass.valueNumberable();
 629         if (nodeClass.isLeafNode()) {
 630             // Leaf node: look up in cache
 631             Node cachedNode = findNodeInCache(node);
 632             if (cachedNode != null && cachedNode != node) {
 633                 return (T) cachedNode;
 634             } else {
 635                 return null;
 636             }
 637         } else {
 638             /*
 639              * Non-leaf node: look for another usage of the node's inputs that has the same data,
 640              * inputs and successors as the node. To reduce the cost of this computation, only the
 641              * input with lowest usage count is considered. If this node is the only user of any
 642              * input then the search can terminate early. The usage count is only incremented once
 643              * the Node is in the Graph, so account for that in the test.
 644              */
 645             final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
 646             int minCount = Integer.MAX_VALUE;
 647             Node minCountNode = null;
 648             for (Node input : node.inputs()) {
 649                 int usageCount = input.getUsageCount();
 650                 if (usageCount == earlyExitUsageCount) {
 651                     return null;
 652                 } else if (usageCount < minCount) {
 653                     minCount = usageCount;
 654                     minCountNode = input;
 655                 }
 656             }
 657             if (minCountNode != null) {
 658                 for (Node usage : minCountNode.usages()) {
 659                     if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.equalInputs(node, usage) &&
 660                                     nodeClass.equalSuccessors(node, usage)) {
 661                         return (T) usage;
 662                     }
 663                 }
 664                 return null;
 665             }
 666             return null;
 667         }
 668     }
 669 
 670     public boolean isNew(Mark mark, Node node) {
 671         return node.id >= mark.getValue();
 672     }
 673 
 674     /**
 675      * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
 676      */
 677     public static class Mark extends NodeIdAccessor {
 678         private final int value;
 679 
 680         Mark(Graph graph) {
 681             super(graph);
 682             this.value = graph.nodeIdCount();
 683         }
 684 
 685         @Override
 686         public boolean equals(Object obj) {
 687             if (obj instanceof Mark) {
 688                 Mark other = (Mark) obj;
 689                 return other.getValue() == getValue() && other.getGraph() == getGraph();
 690             }
 691             return false;
 692         }
 693 
 694         @Override
 695         public int hashCode() {
 696             return value ^ (epoch + 11);
 697         }
 698 
 699         /**
 700          * Determines if this mark is positioned at the first live node in the graph.
 701          */
 702         public boolean isStart() {
 703             return value == 0;
 704         }
 705 
 706         /**
 707          * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when
 708          * this object was created.
 709          */
 710         int getValue() {
 711             return value;
 712         }
 713 
 714         /**
 715          * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node
 716          * count} of the graph.
 717          */
 718         public boolean isCurrent() {
 719             return value == graph.nodeIdCount();
 720         }
 721     }
 722 
 723     /**
 724      * Gets a mark that can be used with {@link #getNewNodes}.
 725      */
 726     public Mark getMark() {
 727         return new Mark(this);
 728     }
 729 
 730     /**
 731      * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark()
 732      * mark}.
 733      */
 734     public NodeIterable<Node> getNewNodes(Mark mark) {
 735         final int index = mark == null ? 0 : mark.getValue();
 736         return new NodeIterable<Node>() {
 737 
 738             @Override
 739             public Iterator<Node> iterator() {
 740                 return new GraphNodeIterator(Graph.this, index);
 741             }
 742         };
 743     }
 744 
 745     /**
 746      * Returns an {@link Iterable} providing all the live nodes.
 747      *
 748      * @return an {@link Iterable} providing all the live nodes.
 749      */
 750     public NodeIterable<Node> getNodes() {
 751         return new NodeIterable<Node>() {
 752 
 753             @Override
 754             public Iterator<Node> iterator() {
 755                 return new GraphNodeIterator(Graph.this);
 756             }
 757 
 758             @Override
 759             public int count() {
 760                 return getNodeCount();
 761             }
 762         };
 763     }
 764 
 765     // Fully qualified annotation name is required to satisfy javac
 766     @org.graalvm.compiler.nodeinfo.NodeInfo
 767     static final class PlaceHolderNode extends Node {
 768 
 769         public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class);
 770 
 771         protected PlaceHolderNode() {
 772             super(TYPE);
 773         }
 774 
 775     }
 776 
 777     static final Node PLACE_HOLDER = new PlaceHolderNode();
 778 
 779     public static final int COMPRESSION_THRESHOLD = Options.GraphCompressionThreshold.getValue();
 780 
 781     private static final DebugCounter GraphCompressions = Debug.counter("GraphCompressions");
 782 
 783     /**
 784      * If the {@linkplain #COMPRESSION_THRESHOLD compression threshold} is met, the list of nodes is
 785      * compressed such that all non-null entries precede all null entries while preserving the
 786      * ordering between the nodes within the list.
 787      */
 788     public boolean maybeCompress() {
 789         if (Debug.isDumpEnabledForMethod() || Debug.isLogEnabledForMethod()) {
 790             return false;
 791         }
 792         int liveNodeCount = getNodeCount();
 793         int liveNodePercent = liveNodeCount * 100 / nodesSize;
 794         if (COMPRESSION_THRESHOLD == 0 || liveNodePercent >= COMPRESSION_THRESHOLD) {
 795             return false;
 796         }
 797         GraphCompressions.increment();
 798         int nextId = 0;
 799         for (int i = 0; nextId < liveNodeCount; i++) {
 800             Node n = nodes[i];
 801             if (n != null) {
 802                 assert n.id == i;
 803                 if (i != nextId) {
 804                     assert n.id > nextId;
 805                     n.id = nextId;
 806                     nodes[nextId] = n;
 807                     nodes[i] = null;
 808                 }
 809                 nextId++;
 810             }
 811         }
 812         if (isModificationCountsEnabled()) {
 813             // This will cause any current iteration to fail with an assertion
 814             Arrays.fill(nodeModCounts, 0);
 815             Arrays.fill(nodeUsageModCounts, 0);
 816         }
 817         nodesSize = nextId;
 818         compressions++;
 819         nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
 820         nodesDeletedSinceLastCompression = 0;
 821         return true;
 822     }
 823 
 824     /**
 825      * Returns an {@link Iterable} providing all the live nodes whose type is compatible with
 826      * {@code type}.
 827      *
 828      * @param nodeClass the type of node to return
 829      * @return an {@link Iterable} providing all the matching nodes
 830      */
 831     public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) {
 832         return new NodeIterable<T>() {
 833 
 834             @Override
 835             public Iterator<T> iterator() {
 836                 return new TypedGraphNodeIterator<>(nodeClass, Graph.this);
 837             }
 838         };
 839     }
 840 
 841     /**
 842      * Returns whether the graph contains at least one node of the given type.
 843      *
 844      * @param type the type of node that is checked for occurrence
 845      * @return whether there is at least one such node
 846      */
 847     public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) {
 848         return getNodes(type).iterator().hasNext();
 849     }
 850 
 851     /**
 852      * @param iterableId
 853      * @return the first live Node with a matching iterableId
 854      */
 855     Node getIterableNodeStart(int iterableId) {
 856         if (iterableNodesFirst.size() <= iterableId) {
 857             return null;
 858         }
 859         Node start = iterableNodesFirst.get(iterableId);
 860         if (start == null || !start.isDeleted()) {
 861             return start;
 862         }
 863         return findFirstLiveIterable(iterableId, start);
 864     }
 865 
 866     private Node findFirstLiveIterable(int iterableId, Node node) {
 867         Node start = node;
 868         while (start != null && start.isDeleted()) {
 869             start = start.typeCacheNext;
 870         }
 871         /*
 872          * Multiple threads iterating nodes can update this cache simultaneously. This is a benign
 873          * race, since all threads update it to the same value.
 874          */
 875         iterableNodesFirst.set(iterableId, start);
 876         if (start == null) {
 877             iterableNodesLast.set(iterableId, start);
 878         }
 879         return start;
 880     }
 881 
 882     /**
 883      * @param node
 884      * @return return the first live Node with a matching iterableId starting from {@code node}
 885      */
 886     Node getIterableNodeNext(Node node) {
 887         if (node == null) {
 888             return null;
 889         }
 890         Node n = node;
 891         if (n == null || !n.isDeleted()) {
 892             return n;
 893         }
 894 
 895         return findNextLiveiterable(node);
 896     }
 897 
 898     private Node findNextLiveiterable(Node start) {
 899         Node n = start;
 900         while (n != null && n.isDeleted()) {
 901             n = n.typeCacheNext;
 902         }
 903         if (n == null) {
 904             // Only dead nodes after this one
 905             start.typeCacheNext = null;
 906             int nodeClassId = start.getNodeClass().iterableId();
 907             assert nodeClassId != Node.NOT_ITERABLE;
 908             iterableNodesLast.set(nodeClassId, start);
 909         } else {
 910             // Everything in between is dead
 911             start.typeCacheNext = n;
 912         }
 913         return n;
 914     }
 915 
 916     public NodeBitMap createNodeBitMap() {
 917         return new NodeBitMap(this);
 918     }
 919 
 920     public <T> NodeMap<T> createNodeMap() {
 921         return new NodeMap<>(this);
 922     }
 923 
 924     public NodeFlood createNodeFlood() {
 925         return new NodeFlood(this);
 926     }
 927 
 928     public NodeWorkList createNodeWorkList() {
 929         return new NodeWorkList.SingletonNodeWorkList(this);
 930     }
 931 
 932     public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
 933         return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
 934     }
 935 
 936     void register(Node node) {
 937         assert !isFrozen();
 938         assert node.id() == Node.INITIAL_ID;
 939         if (nodes.length == nodesSize) {
 940             Node[] newNodes = new Node[(nodesSize * 2) + 1];
 941             System.arraycopy(nodes, 0, newNodes, 0, nodesSize);
 942             nodes = newNodes;
 943         }
 944         int id = nodesSize;
 945         nodes[id] = node;
 946         if (currentNodeSourcePosition != null) {
 947             node.setNodeSourcePosition(currentNodeSourcePosition);
 948         } else if (!seenNodeSourcePosition && node.getNodeSourcePosition() != null) {
 949             seenNodeSourcePosition = true;
 950         }
 951         nodesSize++;
 952 
 953         updateNodeCaches(node);
 954 
 955         node.id = id;
 956         if (nodeEventListener != null) {
 957             nodeEventListener.nodeAdded(node);
 958         }
 959         if (!seenNodeSourcePosition && node.sourcePosition != null) {
 960             seenNodeSourcePosition = true;
 961         }
 962         if (Fingerprint.ENABLED) {
 963             Fingerprint.submit("%s: %s", NodeEvent.NODE_ADDED, node);
 964         }
 965     }
 966 
 967     @SuppressWarnings("unused")
 968     private void postDeserialization() {
 969         recomputeIterableNodeLists();
 970     }
 971 
 972     /**
 973      * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for
 974      * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have
 975      * changed.
 976      */
 977     private void recomputeIterableNodeLists() {
 978         iterableNodesFirst.clear();
 979         iterableNodesLast.clear();
 980         for (Node node : nodes) {
 981             if (node != null && node.isAlive()) {
 982                 updateNodeCaches(node);
 983             }
 984         }
 985     }
 986 
 987     private void updateNodeCaches(Node node) {
 988         int nodeClassId = node.getNodeClass().iterableId();
 989         if (nodeClassId != Node.NOT_ITERABLE) {
 990             while (iterableNodesFirst.size() <= nodeClassId) {
 991                 iterableNodesFirst.add(null);
 992                 iterableNodesLast.add(null);
 993             }
 994             Node prev = iterableNodesLast.get(nodeClassId);
 995             if (prev != null) {
 996                 prev.typeCacheNext = node;
 997             } else {
 998                 iterableNodesFirst.set(nodeClassId, node);
 999             }
1000             iterableNodesLast.set(nodeClassId, node);
1001         }
1002     }
1003 
1004     void unregister(Node node) {
1005         assert !isFrozen();
1006         assert !node.isDeleted() : "cannot delete a node twice! node=" + node;
1007         nodes[node.id] = null;
1008         nodesDeletedSinceLastCompression++;
1009 
1010         // nodes aren't removed from the type cache here - they will be removed during iteration
1011     }
1012 
1013     public boolean verify() {
1014         if (Options.VerifyGraalGraphs.getValue()) {
1015             for (Node node : getNodes()) {
1016                 try {
1017                     try {
1018                         assert node.verify();
1019                     } catch (AssertionError t) {
1020                         throw new GraalError(t);
1021                     } catch (RuntimeException t) {
1022                         throw new GraalError(t);
1023                     }
1024                 } catch (GraalError e) {
1025                     throw GraalGraphError.transformAndAddContext(e, node).addContext(this);
1026                 }
1027             }
1028         }
1029         return true;
1030     }
1031 
1032     public Node getNode(int id) {
1033         return nodes[id];
1034     }
1035 
1036     /**
1037      * Returns the number of node ids generated so far.
1038      *
1039      * @return the number of node ids generated so far
1040      */
1041     int nodeIdCount() {
1042         return nodesSize;
1043     }
1044 
1045     /**
1046      * Adds duplicates of the nodes in {@code nodes} to this graph. This will recreate any edges
1047      * between the duplicate nodes. The {@code replacement} map can be used to replace a node from
1048      * the source graph by a given node (which must already be in this graph). Edges between
1049      * duplicate and replacement nodes will also be recreated so care should be taken regarding the
1050      * matching of node types in the replacement map.
1051      *
1052      * @param newNodes the nodes to be duplicated
1053      * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
1054      * @return a map which associates the original nodes from {@code nodes} to their duplicates
1055      */
1056     public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, Map<Node, Node> replacementsMap) {
1057         DuplicationReplacement replacements;
1058         if (replacementsMap == null) {
1059             replacements = null;
1060         } else {
1061             replacements = new MapReplacement(replacementsMap);
1062         }
1063         return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
1064     }
1065 
1066     public interface DuplicationReplacement {
1067 
1068         Node replacement(Node original);
1069     }
1070 
1071     private static final class MapReplacement implements DuplicationReplacement {
1072 
1073         private final Map<Node, Node> map;
1074 
1075         MapReplacement(Map<Node, Node> map) {
1076             this.map = map;
1077         }
1078 
1079         @Override
1080         public Node replacement(Node original) {
1081             Node replacement = map.get(original);
1082             return replacement != null ? replacement : original;
1083         }
1084 
1085     }
1086 
1087     private static final DebugTimer DuplicateGraph = Debug.timer("DuplicateGraph");
1088 
1089     @SuppressWarnings({"all", "try"})
1090     public Map<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
1091         try (DebugCloseable s = DuplicateGraph.start()) {
1092             return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
1093         }
1094     }
1095 
1096     /**
1097      * Reverses the usage orders of all nodes. This is used for debugging to make sure an unorthodox
1098      * usage order does not trigger bugs in the compiler.
1099      */
1100     public void reverseUsageOrder() {
1101         for (Node n : getNodes()) {
1102             n.reverseUsageOrder();
1103         }
1104     }
1105 
1106     public boolean isFrozen() {
1107         return isFrozen;
1108     }
1109 
1110     public void freeze() {
1111         this.isFrozen = true;
1112     }
1113 }