1 /* 2 * Copyright (c) 2011, 2018, 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 24 25 package org.graalvm.compiler.graph; 26 27 import static org.graalvm.compiler.core.common.GraalOptions.TrackNodeInsertion; 28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED; 29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED; 30 31 import java.util.ArrayList; 32 import java.util.Arrays; 33 import java.util.Iterator; 34 import java.util.function.Consumer; 35 36 import jdk.internal.vm.compiler.collections.EconomicMap; 37 import jdk.internal.vm.compiler.collections.Equivalence; 38 import jdk.internal.vm.compiler.collections.UnmodifiableEconomicMap; 39 import org.graalvm.compiler.core.common.GraalOptions; 40 import org.graalvm.compiler.debug.CounterKey; 41 import org.graalvm.compiler.debug.DebugCloseable; 42 import org.graalvm.compiler.debug.DebugContext; 43 import org.graalvm.compiler.debug.GraalError; 44 import org.graalvm.compiler.debug.TimerKey; 45 import org.graalvm.compiler.graph.Node.NodeInsertionStackTrace; 46 import org.graalvm.compiler.graph.Node.ValueNumberable; 47 import org.graalvm.compiler.graph.iterators.NodeIterable; 48 import org.graalvm.compiler.options.Option; 49 import org.graalvm.compiler.options.OptionKey; 50 import org.graalvm.compiler.options.OptionType; 51 import org.graalvm.compiler.options.OptionValues; 52 53 import jdk.vm.ci.meta.ResolvedJavaMethod; 54 55 /** 56 * This class is a graph container, it contains the set of nodes that belong to this graph. 57 */ 58 public class Graph { 59 60 public static class Options { 61 @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)// 62 public static final OptionKey<Boolean> VerifyGraalGraphs = new OptionKey<>(true); 63 @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)// 64 public static final OptionKey<Boolean> VerifyGraalGraphEdges = new OptionKey<>(false); 65 @Option(help = "Graal graph compression is performed when percent of live nodes falls below this value", type = OptionType.Debug)// 66 public static final OptionKey<Integer> GraphCompressionThreshold = new OptionKey<>(70); 67 } 68 69 private enum FreezeState { 70 Unfrozen, 71 TemporaryFreeze, 72 DeepFreeze 73 } 74 75 public final String name; 76 77 /** 78 * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time. 79 */ 80 Node[] nodes; 81 82 /** 83 * Source information to associate with newly created nodes. 84 */ 85 NodeSourcePosition currentNodeSourcePosition; 86 87 /** 88 * Records if updating of node source information is required when performing inlining. 89 */ 90 protected boolean trackNodeSourcePosition; 91 92 /** 93 * The number of valid entries in {@link #nodes}. 94 */ 95 int nodesSize; 96 97 /** 98 * Records the modification count for nodes. This is only used in assertions. 99 */ 100 private int[] nodeModCounts; 101 102 /** 103 * Records the modification count for nodes' usage lists. This is only used in assertions. 104 */ 105 private int[] nodeUsageModCounts; 106 107 // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId. 108 // they contain the first and last pointer to a linked list of all nodes with this type. 109 private final ArrayList<Node> iterableNodesFirst; 110 private final ArrayList<Node> iterableNodesLast; 111 112 private int nodesDeletedSinceLastCompression; 113 private int nodesDeletedBeforeLastCompression; 114 115 /** 116 * The number of times this graph has been compressed. 117 */ 118 int compressions; 119 120 NodeEventListener nodeEventListener; 121 122 /** 123 * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf} 124 * nodes. 125 */ 126 private EconomicMap<Node, Node>[] cachedLeafNodes; 127 128 private static final Equivalence NODE_VALUE_COMPARE = new Equivalence() { 129 130 @Override 131 public boolean equals(Object a, Object b) { 132 if (a == b) { 133 return true; 134 } 135 136 assert a.getClass() == b.getClass(); 137 return ((Node) a).valueEquals((Node) b); 138 } 139 140 @Override 141 public int hashCode(Object k) { 142 return ((Node) k).getNodeClass().valueNumber((Node) k); 143 } 144 }; 145 146 /** 147 * Indicates that the graph should no longer be modified. Frozen graphs can be used by multiple 148 * threads so it's only safe to read them. 149 */ 150 private FreezeState freezeState = FreezeState.Unfrozen; 151 152 /** 153 * The option values used while compiling this graph. 154 */ 155 private final OptionValues options; 156 157 /** 158 * The {@link DebugContext} used while compiling this graph. 159 */ 160 private DebugContext debug; 161 162 private class NodeSourcePositionScope implements DebugCloseable { 163 private final NodeSourcePosition previous; 164 165 NodeSourcePositionScope(NodeSourcePosition sourcePosition) { 166 previous = currentNodeSourcePosition; 167 currentNodeSourcePosition = sourcePosition; 168 } 169 170 @Override 171 public DebugContext getDebug() { 172 return debug; 173 } 174 175 @Override 176 public void close() { 177 currentNodeSourcePosition = previous; 178 } 179 } 180 181 public NodeSourcePosition currentNodeSourcePosition() { 182 return currentNodeSourcePosition; 183 } 184 185 /** 186 * Opens a scope in which the source information from {@code node} is copied into nodes created 187 * within the scope. If {@code node} has no source information information, no scope is opened 188 * and {@code null} is returned. 189 * 190 * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope 191 * was opened 192 */ 193 public DebugCloseable withNodeSourcePosition(Node node) { 194 return withNodeSourcePosition(node.getNodeSourcePosition()); 195 } 196 197 /** 198 * Opens a scope in which {@code sourcePosition} is copied into nodes created within the scope. 199 * If {@code sourcePosition == null}, no scope is opened and {@code null} is returned. 200 * 201 * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope 202 * was opened 203 */ 204 public DebugCloseable withNodeSourcePosition(NodeSourcePosition sourcePosition) { 205 return trackNodeSourcePosition() && sourcePosition != null ? new NodeSourcePositionScope(sourcePosition) : null; 206 } 207 208 /** 209 * Opens a scope in which newly created nodes do not get any source information added. 210 * 211 * @return a {@link DebugCloseable} for managing the opened scope 212 */ 213 public DebugCloseable withoutNodeSourcePosition() { 214 return new NodeSourcePositionScope(null); 215 } 216 217 public boolean trackNodeSourcePosition() { 218 return trackNodeSourcePosition; 219 } 220 221 public void setTrackNodeSourcePosition() { 222 if (!trackNodeSourcePosition) { 223 assert getNodeCount() == 1 : "can't change the value after nodes have been added"; 224 trackNodeSourcePosition = true; 225 } 226 } 227 228 public static boolean trackNodeSourcePositionDefault(OptionValues options, DebugContext debug) { 229 return (GraalOptions.TrackNodeSourcePosition.getValue(options) || debug.isDumpEnabledForMethod()); 230 } 231 232 /** 233 * Creates an empty Graph with no name. 234 */ 235 public Graph(OptionValues options, DebugContext debug) { 236 this(null, options, debug, false); 237 } 238 239 /** 240 * We only want the expensive modification count tracking when assertions are enabled for the 241 * {@link Graph} class. 242 */ 243 @SuppressWarnings("all") 244 public static boolean isModificationCountsEnabled() { 245 boolean enabled = false; 246 assert enabled = true; 247 return enabled; 248 } 249 250 private static final int INITIAL_NODES_SIZE = 32; 251 252 /** 253 * Creates an empty Graph with a given name. 254 * 255 * @param name the name of the graph, used for debugging purposes 256 */ 257 public Graph(String name, OptionValues options, DebugContext debug, boolean trackNodeSourcePosition) { 258 nodes = new Node[INITIAL_NODES_SIZE]; 259 iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds()); 260 iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds()); 261 this.name = name; 262 this.options = options; 263 this.trackNodeSourcePosition = trackNodeSourcePosition || trackNodeSourcePositionDefault(options, debug); 264 assert debug != null; 265 this.debug = debug; 266 267 if (isModificationCountsEnabled()) { 268 nodeModCounts = new int[INITIAL_NODES_SIZE]; 269 nodeUsageModCounts = new int[INITIAL_NODES_SIZE]; 270 } 271 } 272 273 int extractOriginalNodeId(Node node) { 274 int id = node.id; 275 if (id <= Node.DELETED_ID_START) { 276 id = Node.DELETED_ID_START - id; 277 } 278 return id; 279 } 280 281 int modCount(Node node) { 282 int id = extractOriginalNodeId(node); 283 if (id >= 0 && id < nodeModCounts.length) { 284 return nodeModCounts[id]; 285 } 286 return 0; 287 } 288 289 void incModCount(Node node) { 290 int id = extractOriginalNodeId(node); 291 if (id >= 0) { 292 if (id >= nodeModCounts.length) { 293 nodeModCounts = Arrays.copyOf(nodeModCounts, id * 2 + 30); 294 } 295 nodeModCounts[id]++; 296 } else { 297 assert false; 298 } 299 } 300 301 int usageModCount(Node node) { 302 int id = extractOriginalNodeId(node); 303 if (id >= 0 && id < nodeUsageModCounts.length) { 304 return nodeUsageModCounts[id]; 305 } 306 return 0; 307 } 308 309 void incUsageModCount(Node node) { 310 int id = extractOriginalNodeId(node); 311 if (id >= 0) { 312 if (id >= nodeUsageModCounts.length) { 313 nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id * 2 + 30); 314 } 315 nodeUsageModCounts[id]++; 316 } else { 317 assert false; 318 } 319 } 320 321 /** 322 * Creates a copy of this graph. 323 * 324 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this 325 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache 326 * accessed by multiple threads). 327 */ 328 public final Graph copy(DebugContext debugForCopy) { 329 return copy(name, null, debugForCopy); 330 } 331 332 /** 333 * Creates a copy of this graph. 334 * 335 * @param duplicationMapCallback consumer of the duplication map created during the copying 336 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this 337 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache 338 * accessed by multiple threads). 339 */ 340 public final Graph copy(Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) { 341 return copy(name, duplicationMapCallback, debugForCopy); 342 } 343 344 /** 345 * Creates a copy of this graph. 346 * 347 * @param newName the name of the copy, used for debugging purposes (can be null) 348 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this 349 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache 350 * accessed by multiple threads). 351 */ 352 public final Graph copy(String newName, DebugContext debugForCopy) { 353 return copy(newName, null, debugForCopy); 354 } 355 356 /** 357 * Creates a copy of this graph. 358 * 359 * @param newName the name of the copy, used for debugging purposes (can be null) 360 * @param duplicationMapCallback consumer of the duplication map created during the copying 361 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this 362 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache 363 * accessed by multiple threads). 364 */ 365 protected Graph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) { 366 Graph copy = new Graph(newName, options, debugForCopy, trackNodeSourcePosition()); 367 UnmodifiableEconomicMap<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (EconomicMap<Node, Node>) null); 368 if (duplicationMapCallback != null) { 369 duplicationMapCallback.accept(duplicates); 370 } 371 return copy; 372 } 373 374 public final OptionValues getOptions() { 375 return options; 376 } 377 378 public DebugContext getDebug() { 379 return debug; 380 } 381 382 /** 383 * Resets the {@link DebugContext} for this graph to a new value. This is useful when a graph is 384 * "handed over" from its creating thread to another thread. 385 * 386 * This must only be done when the current thread is no longer using the graph. This is in 387 * general impossible to test due to races and since metrics can be updated at any time. As 388 * such, this method only performs a weak sanity check that at least the current debug context 389 * does not have a nested scope open (the top level scope will always be open if scopes are 390 * enabled). 391 */ 392 public void resetDebug(DebugContext newDebug) { 393 assert newDebug == debug || !debug.inNestedScope() : String.format("Cannot reset the debug context for %s while it has the nested scope \"%s\" open", this, debug.getCurrentScopeName()); 394 this.debug = newDebug; 395 } 396 397 @Override 398 public String toString() { 399 return name == null ? super.toString() : "Graph " + name; 400 } 401 402 /** 403 * Gets the number of live nodes in this graph. That is the number of nodes which have been 404 * added to the graph minus the number of deleted nodes. 405 * 406 * @return the number of live nodes in this graph 407 */ 408 public int getNodeCount() { 409 return nodesSize - getNodesDeletedSinceLastCompression(); 410 } 411 412 /** 413 * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node 414 * identifiers are only stable between compressions. To ensure this constraint is observed, any 415 * entity relying upon stable node identifiers should use {@link NodeIdAccessor}. 416 */ 417 public int getCompressions() { 418 return compressions; 419 } 420 421 /** 422 * Gets the number of nodes which have been deleted from this graph since it was last 423 * {@linkplain #maybeCompress() compressed}. 424 */ 425 public int getNodesDeletedSinceLastCompression() { 426 return nodesDeletedSinceLastCompression; 427 } 428 429 /** 430 * Gets the total number of nodes which have been deleted from this graph. 431 */ 432 public int getTotalNodesDeleted() { 433 return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression; 434 } 435 436 /** 437 * Adds a new node to the graph. 438 * 439 * @param node the node to be added 440 * @return the node which was added to the graph 441 */ 442 public <T extends Node> T add(T node) { 443 if (node.getNodeClass().valueNumberable()) { 444 throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique."); 445 } 446 return addHelper(node); 447 } 448 449 public <T extends Node> T addWithoutUnique(T node) { 450 return addHelper(node); 451 } 452 453 public <T extends Node> T addOrUnique(T node) { 454 if (node.getNodeClass().valueNumberable()) { 455 return uniqueHelper(node); 456 } 457 return add(node); 458 } 459 460 public <T extends Node> T maybeAddOrUnique(T node) { 461 if (node.isAlive()) { 462 return node; 463 } 464 return addOrUnique(node); 465 } 466 467 public <T extends Node> T addOrUniqueWithInputs(T node) { 468 if (node.isAlive()) { 469 assert node.graph() == this; 470 return node; 471 } else { 472 assert node.isUnregistered(); 473 addInputs(node); 474 if (node.getNodeClass().valueNumberable()) { 475 return uniqueHelper(node); 476 } 477 return add(node); 478 } 479 } 480 481 public <T extends Node> T addWithoutUniqueWithInputs(T node) { 482 addInputs(node); 483 return addHelper(node); 484 } 485 486 private final class AddInputsFilter extends Node.EdgeVisitor { 487 488 @Override 489 public Node apply(Node self, Node input) { 490 if (!input.isAlive()) { 491 assert !input.isDeleted(); 492 return addOrUniqueWithInputs(input); 493 } else { 494 return input; 495 } 496 } 497 498 } 499 500 private AddInputsFilter addInputsFilter = new AddInputsFilter(); 501 502 private <T extends Node> void addInputs(T node) { 503 node.applyInputs(addInputsFilter); 504 } 505 506 private <T extends Node> T addHelper(T node) { 507 node.initialize(this); 508 return node; 509 } 510 511 /** 512 * The type of events sent to a {@link NodeEventListener}. 513 */ 514 public enum NodeEvent { 515 /** 516 * A node's input is changed. 517 */ 518 INPUT_CHANGED, 519 520 /** 521 * A node's {@linkplain Node#usages() usages} count dropped to zero. 522 */ 523 ZERO_USAGES, 524 525 /** 526 * A node was added to a graph. 527 */ 528 NODE_ADDED, 529 530 /** 531 * A node was removed from the graph. 532 */ 533 NODE_REMOVED 534 } 535 536 /** 537 * Client interested in one or more node related events. 538 */ 539 public abstract static class NodeEventListener { 540 541 /** 542 * A method called when a change event occurs. 543 * 544 * This method dispatches the event to user-defined triggers. The methods that change the 545 * graph (typically in Graph and Node) must call this method to dispatch the event. 546 * 547 * @param e an event 548 * @param node the node related to {@code e} 549 */ 550 final void event(NodeEvent e, Node node) { 551 switch (e) { 552 case INPUT_CHANGED: 553 inputChanged(node); 554 break; 555 case ZERO_USAGES: 556 usagesDroppedToZero(node); 557 break; 558 case NODE_ADDED: 559 nodeAdded(node); 560 break; 561 case NODE_REMOVED: 562 nodeRemoved(node); 563 break; 564 } 565 changed(e, node); 566 } 567 568 /** 569 * Notifies this listener about any change event in the graph. 570 * 571 * @param e an event 572 * @param node the node related to {@code e} 573 */ 574 public void changed(NodeEvent e, Node node) { 575 } 576 577 /** 578 * Notifies this listener about a change in a node's inputs. 579 * 580 * @param node a node who has had one of its inputs changed 581 */ 582 public void inputChanged(Node node) { 583 } 584 585 /** 586 * Notifies this listener of a node becoming unused. 587 * 588 * @param node a node whose {@link Node#usages()} just became empty 589 */ 590 public void usagesDroppedToZero(Node node) { 591 } 592 593 /** 594 * Notifies this listener of an added node. 595 * 596 * @param node a node that was just added to the graph 597 */ 598 public void nodeAdded(Node node) { 599 } 600 601 /** 602 * Notifies this listener of a removed node. 603 * 604 * @param node 605 */ 606 public void nodeRemoved(Node node) { 607 } 608 } 609 610 /** 611 * Registers a given {@link NodeEventListener} with the enclosing graph until this object is 612 * {@linkplain #close() closed}. 613 */ 614 public final class NodeEventScope implements AutoCloseable { 615 NodeEventScope(NodeEventListener listener) { 616 if (nodeEventListener == null) { 617 nodeEventListener = listener; 618 } else { 619 nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener); 620 } 621 } 622 623 @Override 624 public void close() { 625 assert nodeEventListener != null; 626 if (nodeEventListener instanceof ChainedNodeEventListener) { 627 nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next; 628 } else { 629 nodeEventListener = null; 630 } 631 } 632 } 633 634 private static class ChainedNodeEventListener extends NodeEventListener { 635 636 NodeEventListener head; 637 NodeEventListener next; 638 639 ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) { 640 this.head = head; 641 this.next = next; 642 } 643 644 @Override 645 public void changed(NodeEvent e, Node node) { 646 head.event(e, node); 647 next.event(e, node); 648 } 649 } 650 651 /** 652 * Registers a given {@link NodeEventListener} with this graph. This should be used in 653 * conjunction with try-with-resources statement as follows: 654 * 655 * <pre> 656 * try (NodeEventScope nes = graph.trackNodeEvents(listener)) { 657 * // make changes to the graph 658 * } 659 * </pre> 660 */ 661 public NodeEventScope trackNodeEvents(NodeEventListener listener) { 662 return new NodeEventScope(listener); 663 } 664 665 /** 666 * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise 667 * {@code node} is added to this graph and returned. 668 * 669 * @return a node similar to {@code node} if one exists, otherwise {@code node} 670 */ 671 public <T extends Node & ValueNumberable> T unique(T node) { 672 return uniqueHelper(node); 673 } 674 675 <T extends Node> T uniqueHelper(T node) { 676 assert node.getNodeClass().valueNumberable(); 677 T other = this.findDuplicate(node); 678 if (other != null) { 679 if (other.getNodeSourcePosition() == null) { 680 other.setNodeSourcePosition(node.getNodeSourcePosition()); 681 } 682 return other; 683 } else { 684 T result = addHelper(node); 685 if (node.getNodeClass().isLeafNode()) { 686 putNodeIntoCache(result); 687 } 688 return result; 689 } 690 } 691 692 void removeNodeFromCache(Node node) { 693 assert node.graph() == this || node.graph() == null; 694 assert node.getNodeClass().valueNumberable(); 695 assert node.getNodeClass().isLeafNode() : node.getClass(); 696 697 int leafId = node.getNodeClass().getLeafId(); 698 if (cachedLeafNodes != null && cachedLeafNodes.length > leafId && cachedLeafNodes[leafId] != null) { 699 cachedLeafNodes[leafId].removeKey(node); 700 } 701 } 702 703 @SuppressWarnings({"unchecked", "rawtypes"}) 704 void putNodeIntoCache(Node node) { 705 assert node.graph() == this || node.graph() == null; 706 assert node.getNodeClass().valueNumberable(); 707 assert node.getNodeClass().isLeafNode() : node.getClass(); 708 709 int leafId = node.getNodeClass().getLeafId(); 710 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId) { 711 EconomicMap[] newLeafNodes = new EconomicMap[leafId + 1]; 712 if (cachedLeafNodes != null) { 713 System.arraycopy(cachedLeafNodes, 0, newLeafNodes, 0, cachedLeafNodes.length); 714 } 715 cachedLeafNodes = newLeafNodes; 716 } 717 718 if (cachedLeafNodes[leafId] == null) { 719 cachedLeafNodes[leafId] = EconomicMap.create(NODE_VALUE_COMPARE); 720 } 721 722 cachedLeafNodes[leafId].put(node, node); 723 } 724 725 Node findNodeInCache(Node node) { 726 int leafId = node.getNodeClass().getLeafId(); 727 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId || cachedLeafNodes[leafId] == null) { 728 return null; 729 } 730 731 Node result = cachedLeafNodes[leafId].get(node); 732 assert result == null || result.isAlive() : result; 733 return result; 734 } 735 736 /** 737 * Returns a possible duplicate for the given node in the graph or {@code null} if no such 738 * duplicate exists. 739 */ 740 @SuppressWarnings("unchecked") 741 public <T extends Node> T findDuplicate(T node) { 742 NodeClass<?> nodeClass = node.getNodeClass(); 743 assert nodeClass.valueNumberable(); 744 if (nodeClass.isLeafNode()) { 745 // Leaf node: look up in cache 746 Node cachedNode = findNodeInCache(node); 747 if (cachedNode != null && cachedNode != node) { 748 return (T) cachedNode; 749 } else { 750 return null; 751 } 752 } else { 753 /* 754 * Non-leaf node: look for another usage of the node's inputs that has the same data, 755 * inputs and successors as the node. To reduce the cost of this computation, only the 756 * input with lowest usage count is considered. If this node is the only user of any 757 * input then the search can terminate early. The usage count is only incremented once 758 * the Node is in the Graph, so account for that in the test. 759 */ 760 final int earlyExitUsageCount = node.graph() != null ? 1 : 0; 761 int minCount = Integer.MAX_VALUE; 762 Node minCountNode = null; 763 for (Node input : node.inputs()) { 764 int usageCount = input.getUsageCount(); 765 if (usageCount == earlyExitUsageCount) { 766 return null; 767 } else if (usageCount < minCount) { 768 minCount = usageCount; 769 minCountNode = input; 770 } 771 } 772 if (minCountNode != null) { 773 for (Node usage : minCountNode.usages()) { 774 if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.equalInputs(node, usage) && 775 nodeClass.equalSuccessors(node, usage)) { 776 return (T) usage; 777 } 778 } 779 return null; 780 } 781 return null; 782 } 783 } 784 785 public boolean isNew(Mark mark, Node node) { 786 return node.id >= mark.getValue(); 787 } 788 789 /** 790 * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph. 791 */ 792 public static class Mark extends NodeIdAccessor { 793 private final int value; 794 795 Mark(Graph graph) { 796 super(graph); 797 this.value = graph.nodeIdCount(); 798 } 799 800 @Override 801 public boolean equals(Object obj) { 802 if (obj instanceof Mark) { 803 Mark other = (Mark) obj; 804 return other.getValue() == getValue() && other.getGraph() == getGraph(); 805 } 806 return false; 807 } 808 809 @Override 810 public int hashCode() { 811 return value ^ (epoch + 11); 812 } 813 814 /** 815 * Determines if this mark is positioned at the first live node in the graph. 816 */ 817 public boolean isStart() { 818 return value == 0; 819 } 820 821 /** 822 * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when 823 * this object was created. 824 */ 825 int getValue() { 826 return value; 827 } 828 829 /** 830 * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node 831 * count} of the graph. 832 */ 833 public boolean isCurrent() { 834 return value == graph.nodeIdCount(); 835 } 836 } 837 838 /** 839 * Gets a mark that can be used with {@link #getNewNodes}. 840 */ 841 public Mark getMark() { 842 return new Mark(this); 843 } 844 845 /** 846 * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark() 847 * mark}. 848 */ 849 public NodeIterable<Node> getNewNodes(Mark mark) { 850 final int index = mark == null ? 0 : mark.getValue(); 851 return new NodeIterable<Node>() { 852 853 @Override 854 public Iterator<Node> iterator() { 855 return new GraphNodeIterator(Graph.this, index); 856 } 857 }; 858 } 859 860 /** 861 * Returns an {@link Iterable} providing all the live nodes. 862 * 863 * @return an {@link Iterable} providing all the live nodes. 864 */ 865 public NodeIterable<Node> getNodes() { 866 return new NodeIterable<Node>() { 867 868 @Override 869 public Iterator<Node> iterator() { 870 return new GraphNodeIterator(Graph.this); 871 } 872 873 @Override 874 public int count() { 875 return getNodeCount(); 876 } 877 }; 878 } 879 880 // Fully qualified annotation name is required to satisfy javac 881 @org.graalvm.compiler.nodeinfo.NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED) 882 static final class PlaceHolderNode extends Node { 883 884 public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class); 885 886 protected PlaceHolderNode() { 887 super(TYPE); 888 } 889 890 } 891 892 private static final CounterKey GraphCompressions = DebugContext.counter("GraphCompressions"); 893 894 /** 895 * If the {@linkplain Options#GraphCompressionThreshold compression threshold} is met, the list 896 * of nodes is compressed such that all non-null entries precede all null entries while 897 * preserving the ordering between the nodes within the list. 898 */ 899 public boolean maybeCompress() { 900 if (debug.isDumpEnabledForMethod() || debug.isLogEnabledForMethod()) { 901 return false; 902 } 903 int liveNodeCount = getNodeCount(); 904 int liveNodePercent = liveNodeCount * 100 / nodesSize; 905 int compressionThreshold = Options.GraphCompressionThreshold.getValue(options); 906 if (compressionThreshold == 0 || liveNodePercent >= compressionThreshold) { 907 return false; 908 } 909 GraphCompressions.increment(debug); 910 int nextId = 0; 911 for (int i = 0; nextId < liveNodeCount; i++) { 912 Node n = nodes[i]; 913 if (n != null) { 914 assert n.id == i; 915 if (i != nextId) { 916 assert n.id > nextId; 917 n.id = nextId; 918 nodes[nextId] = n; 919 nodes[i] = null; 920 } 921 nextId++; 922 } 923 } 924 if (isModificationCountsEnabled()) { 925 // This will cause any current iteration to fail with an assertion 926 Arrays.fill(nodeModCounts, 0); 927 Arrays.fill(nodeUsageModCounts, 0); 928 } 929 nodesSize = nextId; 930 compressions++; 931 nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression; 932 nodesDeletedSinceLastCompression = 0; 933 return true; 934 } 935 936 /** 937 * Returns an {@link Iterable} providing all the live nodes whose type is compatible with 938 * {@code type}. 939 * 940 * @param nodeClass the type of node to return 941 * @return an {@link Iterable} providing all the matching nodes 942 */ 943 public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) { 944 return new NodeIterable<T>() { 945 946 @Override 947 public Iterator<T> iterator() { 948 return new TypedGraphNodeIterator<>(nodeClass, Graph.this); 949 } 950 }; 951 } 952 953 /** 954 * Returns whether the graph contains at least one node of the given type. 955 * 956 * @param type the type of node that is checked for occurrence 957 * @return whether there is at least one such node 958 */ 959 public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) { 960 return getNodes(type).iterator().hasNext(); 961 } 962 963 /** 964 * @param iterableId 965 * @return the first live Node with a matching iterableId 966 */ 967 Node getIterableNodeStart(int iterableId) { 968 if (iterableNodesFirst.size() <= iterableId) { 969 return null; 970 } 971 Node start = iterableNodesFirst.get(iterableId); 972 if (start == null || !start.isDeleted()) { 973 return start; 974 } 975 return findFirstLiveIterable(iterableId, start); 976 } 977 978 private Node findFirstLiveIterable(int iterableId, Node node) { 979 Node start = node; 980 while (start != null && start.isDeleted()) { 981 start = start.typeCacheNext; 982 } 983 /* 984 * Multiple threads iterating nodes can update this cache simultaneously. This is a benign 985 * race, since all threads update it to the same value. 986 */ 987 iterableNodesFirst.set(iterableId, start); 988 if (start == null) { 989 iterableNodesLast.set(iterableId, start); 990 } 991 return start; 992 } 993 994 /** 995 * @param node 996 * @return return the first live Node with a matching iterableId starting from {@code node} 997 */ 998 Node getIterableNodeNext(Node node) { 999 if (node == null) { 1000 return null; 1001 } 1002 Node n = node; 1003 if (n == null || !n.isDeleted()) { 1004 return n; 1005 } 1006 1007 return findNextLiveiterable(node); 1008 } 1009 1010 private Node findNextLiveiterable(Node start) { 1011 Node n = start; 1012 while (n != null && n.isDeleted()) { 1013 n = n.typeCacheNext; 1014 } 1015 if (n == null) { 1016 // Only dead nodes after this one 1017 start.typeCacheNext = null; 1018 int nodeClassId = start.getNodeClass().iterableId(); 1019 assert nodeClassId != Node.NOT_ITERABLE; 1020 iterableNodesLast.set(nodeClassId, start); 1021 } else { 1022 // Everything in between is dead 1023 start.typeCacheNext = n; 1024 } 1025 return n; 1026 } 1027 1028 public NodeBitMap createNodeBitMap() { 1029 return new NodeBitMap(this); 1030 } 1031 1032 public <T> NodeMap<T> createNodeMap() { 1033 return new NodeMap<>(this); 1034 } 1035 1036 public NodeFlood createNodeFlood() { 1037 return new NodeFlood(this); 1038 } 1039 1040 public NodeWorkList createNodeWorkList() { 1041 return new NodeWorkList.SingletonNodeWorkList(this); 1042 } 1043 1044 public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) { 1045 return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode); 1046 } 1047 1048 void register(Node node) { 1049 assert !isFrozen(); 1050 assert node.id() == Node.INITIAL_ID; 1051 if (nodes.length == nodesSize) { 1052 grow(); 1053 } 1054 int id = nodesSize++; 1055 nodes[id] = node; 1056 node.id = id; 1057 if (currentNodeSourcePosition != null && trackNodeSourcePosition()) { 1058 node.setNodeSourcePosition(currentNodeSourcePosition); 1059 } 1060 if (TrackNodeInsertion.getValue(getOptions())) { 1061 node.setInsertionPosition(new NodeInsertionStackTrace()); 1062 } 1063 1064 updateNodeCaches(node); 1065 1066 if (nodeEventListener != null) { 1067 nodeEventListener.event(NodeEvent.NODE_ADDED, node); 1068 } 1069 afterRegister(node); 1070 } 1071 1072 private void grow() { 1073 Node[] newNodes = new Node[(nodesSize * 2) + 1]; 1074 System.arraycopy(nodes, 0, newNodes, 0, nodesSize); 1075 nodes = newNodes; 1076 } 1077 1078 @SuppressWarnings("unused") 1079 protected void afterRegister(Node node) { 1080 1081 } 1082 1083 @SuppressWarnings("unused") 1084 private void postDeserialization() { 1085 recomputeIterableNodeLists(); 1086 } 1087 1088 /** 1089 * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for 1090 * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have 1091 * changed. 1092 */ 1093 private void recomputeIterableNodeLists() { 1094 iterableNodesFirst.clear(); 1095 iterableNodesLast.clear(); 1096 for (Node node : nodes) { 1097 if (node != null && node.isAlive()) { 1098 updateNodeCaches(node); 1099 } 1100 } 1101 } 1102 1103 private void updateNodeCaches(Node node) { 1104 int nodeClassId = node.getNodeClass().iterableId(); 1105 if (nodeClassId != Node.NOT_ITERABLE) { 1106 while (iterableNodesFirst.size() <= nodeClassId) { 1107 iterableNodesFirst.add(null); 1108 iterableNodesLast.add(null); 1109 } 1110 Node prev = iterableNodesLast.get(nodeClassId); 1111 if (prev != null) { 1112 prev.typeCacheNext = node; 1113 } else { 1114 iterableNodesFirst.set(nodeClassId, node); 1115 } 1116 iterableNodesLast.set(nodeClassId, node); 1117 } 1118 } 1119 1120 void unregister(Node node) { 1121 assert !isFrozen(); 1122 assert !node.isDeleted() : node; 1123 if (node.getNodeClass().isLeafNode() && node.getNodeClass().valueNumberable()) { 1124 removeNodeFromCache(node); 1125 } 1126 nodes[node.id] = null; 1127 nodesDeletedSinceLastCompression++; 1128 1129 if (nodeEventListener != null) { 1130 nodeEventListener.event(NodeEvent.NODE_REMOVED, node); 1131 } 1132 1133 // nodes aren't removed from the type cache here - they will be removed during iteration 1134 } 1135 1136 public boolean verify() { 1137 if (Options.VerifyGraalGraphs.getValue(options)) { 1138 for (Node node : getNodes()) { 1139 try { 1140 try { 1141 assert node.verify(); 1142 } catch (AssertionError t) { 1143 throw new GraalError(t); 1144 } catch (RuntimeException t) { 1145 throw new GraalError(t); 1146 } 1147 } catch (GraalError e) { 1148 throw GraalGraphError.transformAndAddContext(e, node).addContext(this); 1149 } 1150 } 1151 } 1152 return true; 1153 } 1154 1155 public boolean verifySourcePositions(boolean performConsistencyCheck) { 1156 if (trackNodeSourcePosition()) { 1157 ResolvedJavaMethod root = null; 1158 for (Node node : getNodes()) { 1159 NodeSourcePosition pos = node.getNodeSourcePosition(); 1160 if (pos != null) { 1161 if (root == null) { 1162 root = pos.getRootMethod(); 1163 } else { 1164 assert pos.verifyRootMethod(root) : node; 1165 } 1166 } 1167 1168 // More strict node-type-specific check 1169 if (performConsistencyCheck) { 1170 // Disabled due to GR-10445. 1171 // node.verifySourcePosition(); 1172 } 1173 } 1174 } 1175 return true; 1176 } 1177 1178 public Node getNode(int id) { 1179 return nodes[id]; 1180 } 1181 1182 /** 1183 * Returns the number of node ids generated so far. 1184 * 1185 * @return the number of node ids generated so far 1186 */ 1187 int nodeIdCount() { 1188 return nodesSize; 1189 } 1190 1191 /** 1192 * Adds duplicates of the nodes in {@code newNodes} to this graph. This will recreate any edges 1193 * between the duplicate nodes. The {@code replacement} map can be used to replace a node from 1194 * the source graph by a given node (which must already be in this graph). Edges between 1195 * duplicate and replacement nodes will also be recreated so care should be taken regarding the 1196 * matching of node types in the replacement map. 1197 * 1198 * @param newNodes the nodes to be duplicated 1199 * @param replacementsMap the replacement map (can be null if no replacement is to be performed) 1200 * @return a map which associates the original nodes from {@code nodes} to their duplicates 1201 */ 1202 public UnmodifiableEconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, EconomicMap<Node, Node> replacementsMap) { 1203 DuplicationReplacement replacements; 1204 if (replacementsMap == null) { 1205 replacements = null; 1206 } else { 1207 replacements = new MapReplacement(replacementsMap); 1208 } 1209 return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements); 1210 } 1211 1212 public interface DuplicationReplacement { 1213 1214 Node replacement(Node original); 1215 } 1216 1217 private static final class MapReplacement implements DuplicationReplacement { 1218 1219 private final EconomicMap<Node, Node> map; 1220 1221 MapReplacement(EconomicMap<Node, Node> map) { 1222 this.map = map; 1223 } 1224 1225 @Override 1226 public Node replacement(Node original) { 1227 Node replacement = map.get(original); 1228 return replacement != null ? replacement : original; 1229 } 1230 1231 } 1232 1233 private static final TimerKey DuplicateGraph = DebugContext.timer("DuplicateGraph"); 1234 1235 @SuppressWarnings({"all", "try"}) 1236 public EconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) { 1237 try (DebugCloseable s = DuplicateGraph.start(getDebug())) { 1238 return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements); 1239 } 1240 } 1241 1242 public boolean isFrozen() { 1243 return freezeState != FreezeState.Unfrozen; 1244 } 1245 1246 public void freeze() { 1247 this.freezeState = FreezeState.DeepFreeze; 1248 } 1249 1250 public void temporaryFreeze() { 1251 if (this.freezeState == FreezeState.DeepFreeze) { 1252 throw new GraalError("Graph was permanetly frozen."); 1253 } 1254 this.freezeState = FreezeState.TemporaryFreeze; 1255 } 1256 1257 public void unfreeze() { 1258 if (this.freezeState == FreezeState.DeepFreeze) { 1259 throw new GraalError("Graph was permanetly frozen."); 1260 } 1261 this.freezeState = FreezeState.Unfrozen; 1262 } 1263 }