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 }