1 /* 2 * Copyright (c) 2011, 2015, 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 static org.graalvm.compiler.graph.Edges.Type.Inputs; 26 import static org.graalvm.compiler.graph.Edges.Type.Successors; 27 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled; 28 import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE; 29 30 import java.lang.annotation.ElementType; 31 import java.lang.annotation.RetentionPolicy; 32 import java.util.Collection; 33 import java.util.Collections; 34 import java.util.EnumSet; 35 import java.util.Formattable; 36 import java.util.FormattableFlags; 37 import java.util.Formatter; 38 import java.util.HashMap; 39 import java.util.List; 40 import java.util.Map; 41 import java.util.Objects; 42 import java.util.Set; 43 import java.util.function.Predicate; 44 45 import org.graalvm.compiler.core.common.CollectionsFactory; 46 import org.graalvm.compiler.core.common.Fields; 47 import org.graalvm.compiler.debug.DebugCloseable; 48 import org.graalvm.compiler.debug.Fingerprint; 49 import org.graalvm.compiler.graph.Graph.NodeEvent; 50 import org.graalvm.compiler.graph.Graph.NodeEventListener; 51 import org.graalvm.compiler.graph.Graph.Options; 52 import org.graalvm.compiler.graph.iterators.NodeIterable; 53 import org.graalvm.compiler.graph.iterators.NodePredicate; 54 import org.graalvm.compiler.graph.spi.Simplifiable; 55 import org.graalvm.compiler.graph.spi.SimplifierTool; 56 import org.graalvm.compiler.nodeinfo.InputType; 57 import org.graalvm.compiler.nodeinfo.NodeInfo; 58 import org.graalvm.compiler.nodeinfo.Verbosity; 59 60 import sun.misc.Unsafe; 61 62 /** 63 * This class is the base class for all nodes. It represents a node that can be inserted in a 64 * {@link Graph}. 65 * <p> 66 * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the 67 * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and 68 * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either 69 * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node 70 * this field points to. 71 * <p> 72 * Nodes which are be value numberable should implement the {@link ValueNumberable} interface. 73 * 74 * <h1>Replay Compilation</h1> 75 * 76 * To enable deterministic replay compilation, node sets and node maps should be instantiated with 77 * the following methods: 78 * <ul> 79 * <li>{@link #newSet()}</li> 80 * <li>{@link #newSet(Collection)}</li> 81 * <li>{@link #newMap()}</li> 82 * <li>{@link #newMap(int)}</li> 83 * <li>{@link #newMap(Map)}</li> 84 * <li>{@link #newIdentityMap()}</li> 85 * <li>{@link #newIdentityMap(int)}</li> 86 * <li>{@link #newIdentityMap(Map)}</li> 87 * </ul> 88 * 89 * <h1>Assertions and Verification</h1> 90 * 91 * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and 92 * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean 93 * and throw a VerificationError if it has the wrong value. Both methods will always either throw an 94 * exception or return true. They can thus be used within an assert statement, so that the check is 95 * only performed if assertions are enabled. 96 */ 97 @NodeInfo 98 public abstract class Node implements Cloneable, Formattable, NodeInterface { 99 100 public static final NodeClass<?> TYPE = null; 101 public static final boolean USE_UNSAFE_TO_CLONE = Graph.Options.CloneNodesWithUnsafe.getValue(); 102 103 static final int DELETED_ID_START = -1000000000; 104 static final int INITIAL_ID = -1; 105 static final int ALIVE_ID_START = 0; 106 107 // The use of fully qualified class names here and in the rest 108 // of this file works around a problem javac has resolving symbols 109 110 /** 111 * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of 112 * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of 113 * type {@link Node} outside of their constructor should call 114 * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input. 115 */ 116 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 117 @java.lang.annotation.Target(ElementType.FIELD) 118 public static @interface Input { 119 InputType value() default InputType.Value; 120 } 121 122 /** 123 * Denotes an optional (nullable) node input. This should be applied to exactly the fields of a 124 * node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of type 125 * {@link Node} outside of their constructor should call {@link Node#updateUsages(Node, Node)} 126 * just prior to doing the update of the input. 127 */ 128 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 129 @java.lang.annotation.Target(ElementType.FIELD) 130 public static @interface OptionalInput { 131 InputType value() default InputType.Value; 132 } 133 134 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 135 @java.lang.annotation.Target(ElementType.FIELD) 136 public static @interface Successor { 137 } 138 139 /** 140 * Denotes that a parameter of an {@linkplain NodeIntrinsic intrinsic} method must be a compile 141 * time constant at all call sites to the intrinsic method. 142 */ 143 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 144 @java.lang.annotation.Target(ElementType.PARAMETER) 145 public static @interface ConstantNodeParameter { 146 } 147 148 /** 149 * Denotes an injected parameter in a {@linkplain NodeIntrinsic node intrinsic} constructor. If 150 * the constructor is called as part of node intrinsification, the node intrinsifier will inject 151 * an argument for the annotated parameter. Injected parameters must precede all non-injected 152 * parameters in a constructor. 153 */ 154 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 155 @java.lang.annotation.Target(ElementType.PARAMETER) 156 public static @interface InjectedNodeParameter { 157 } 158 159 /** 160 * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the 161 * annotated method can be replaced with an instance of the node class denoted by 162 * {@link #value()}. For this reason, the signature of the annotated method must match the 163 * signature (excluding a prefix of {@linkplain InjectedNodeParameter injected} parameters) of a 164 * constructor in the node class. 165 * <p> 166 * If the node class has a static method {@code intrinsify} with a matching signature plus a 167 * {@code GraphBuilderContext} as first argument, this method is called instead of creating the 168 * node. 169 */ 170 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) 171 @java.lang.annotation.Target(ElementType.METHOD) 172 public static @interface NodeIntrinsic { 173 174 /** 175 * Gets the {@link Node} subclass instantiated when intrinsifying a call to the annotated 176 * method. If not specified, then the class in which the annotated method is declared is 177 * used (and is assumed to be a {@link Node} subclass). 178 */ 179 Class<?> value() default NodeIntrinsic.class; 180 181 /** 182 * Determines if the stamp of the instantiated intrinsic node has its stamp set from the 183 * return type of the annotated method. 184 * <p> 185 * When it is set to true, the stamp that is passed in to the constructor of ValueNode is 186 * ignored and can therefore safely be {@code null}. 187 */ 188 boolean setStampFromReturnType() default false; 189 190 /** 191 * Determines if the stamp of the instantiated intrinsic node is guaranteed to be non-null. 192 * Generally used in conjunction with {@link #setStampFromReturnType()}. 193 */ 194 boolean returnStampIsNonNull() default false; 195 } 196 197 /** 198 * Marker for a node that can be replaced by another node via global value numbering. A 199 * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same 200 * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node 201 * can be replaced by another node of the same type that has exactly the same data values as 202 * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors() 203 * successors}. 204 */ 205 public interface ValueNumberable { 206 } 207 208 /** 209 * Marker interface for nodes that contains other nodes. When the inputs to this node changes, 210 * users of this node should also be placed on the work list for canonicalization. 211 */ 212 public interface IndirectCanonicalization { 213 } 214 215 private Graph graph; 216 int id; 217 218 // this next pointer is used in Graph to implement fast iteration over NodeClass types, it 219 // therefore points to the next Node of the same type. 220 Node typeCacheNext; 221 222 static final int INLINE_USAGE_COUNT = 2; 223 private static final Node[] NO_NODES = {}; 224 225 /** 226 * Head of usage list. The elements of the usage list in order are {@link #usage0}, 227 * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list. 228 */ 229 Node usage0; 230 Node usage1; 231 Node[] extraUsages; 232 int extraUsagesCount; 233 234 private Node predecessor; 235 private NodeClass<? extends Node> nodeClass; 236 237 public static final int NODE_LIST = -2; 238 public static final int NOT_ITERABLE = -1; 239 240 public Node(NodeClass<? extends Node> c) { 241 init(c); 242 } 243 244 final void init(NodeClass<? extends Node> c) { 245 assert c.getJavaClass() == this.getClass(); 246 this.nodeClass = c; 247 id = INITIAL_ID; 248 extraUsages = NO_NODES; 249 } 250 251 final int id() { 252 return id; 253 } 254 255 @Override 256 public Node asNode() { 257 return this; 258 } 259 260 /** 261 * @see CollectionsFactory#newSet() 262 */ 263 public static <E extends Node> Set<E> newSet() { 264 return CollectionsFactory.newSet(); 265 } 266 267 /** 268 * @see #newSet() 269 */ 270 public static <E extends Node> Set<E> newSet(Collection<? extends E> c) { 271 return CollectionsFactory.newSet(c); 272 } 273 274 public static <K extends Node, V> Map<K, V> newMap() { 275 // Node.equals() and Node.hashCode() are final and are implemented 276 // purely in terms of identity so HashMap and IdentityHashMap with 277 // Node's as keys will behave the same. We choose to use the latter 278 // due to its lighter memory footprint. 279 return newIdentityMap(); 280 } 281 282 public static <K extends Node, V> Map<K, V> newMap(Map<K, V> m) { 283 // Node.equals() and Node.hashCode() are final and are implemented 284 // purely in terms of identity so HashMap and IdentityHashMap with 285 // Node's as keys will behave the same. We choose to use the latter 286 // due to its lighter memory footprint. 287 return newIdentityMap(m); 288 } 289 290 public static <K extends Node, V> Map<K, V> newMap(int expectedMaxSize) { 291 // Node.equals() and Node.hashCode() are final and are implemented 292 // purely in terms of identity so HashMap and IdentityHashMap with 293 // Node's as keys will behave the same. We choose to use the latter 294 // due to its lighter memory footprint. 295 return newIdentityMap(expectedMaxSize); 296 } 297 298 public static <K extends Node, V> Map<K, V> newIdentityMap() { 299 return CollectionsFactory.newIdentityMap(); 300 } 301 302 public static <K extends Node, V> Map<K, V> newIdentityMap(Map<K, V> m) { 303 return CollectionsFactory.newIdentityMap(m); 304 } 305 306 public static <K extends Node, V> Map<K, V> newIdentityMap(int expectedMaxSize) { 307 return CollectionsFactory.newIdentityMap(expectedMaxSize); 308 } 309 310 /** 311 * Gets the graph context of this node. 312 */ 313 public Graph graph() { 314 return graph; 315 } 316 317 /** 318 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input 319 * edges of this node. 320 * 321 * @return an {@link NodeIterable iterable} for all non-null input edges. 322 */ 323 public NodeIterable<Node> inputs() { 324 return nodeClass.getInputIterable(this); 325 } 326 327 /** 328 * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges 329 * of this node. 330 * 331 * @return an {@link Iterable iterable} for all non-null input edges. 332 */ 333 public Iterable<Position> inputPositions() { 334 return nodeClass.getInputEdges().getPositionsIterable(this); 335 } 336 337 public abstract static class EdgeVisitor { 338 339 public abstract Node apply(Node source, Node target); 340 341 } 342 343 /** 344 * Applies the given visitor to all inputs of this node. 345 * 346 * @param visitor the visitor to be applied to the inputs 347 */ 348 public void applyInputs(EdgeVisitor visitor) { 349 nodeClass.applyInputs(this, visitor); 350 } 351 352 /** 353 * Applies the given visitor to all successors of this node. 354 * 355 * @param visitor the visitor to be applied to the successors 356 */ 357 public void applySuccessors(EdgeVisitor visitor) { 358 nodeClass.applySuccessors(this, visitor); 359 } 360 361 /** 362 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null successor 363 * edges of this node. 364 * 365 * @return an {@link NodeIterable iterable} for all non-null successor edges. 366 */ 367 public NodeIterable<Node> successors() { 368 assert !this.isDeleted(); 369 return nodeClass.getSuccessorIterable(this); 370 } 371 372 /** 373 * Returns an {@link Iterable iterable} which can be used to traverse all successor edge 374 * positions of this node. 375 * 376 * @return an {@link Iterable iterable} for all successor edge positoins. 377 */ 378 public Iterable<Position> successorPositions() { 379 return nodeClass.getSuccessorEdges().getPositionsIterable(this); 380 } 381 382 /** 383 * Gets the maximum number of usages this node has had at any point in time. 384 */ 385 public int getUsageCount() { 386 if (usage0 == null) { 387 return 0; 388 } 389 if (usage1 == null) { 390 return 1; 391 } 392 return 2 + extraUsagesCount; 393 } 394 395 /** 396 * Gets the list of nodes that use this node (i.e., as an input). 397 */ 398 public final NodeIterable<Node> usages() { 399 return new NodeUsageIterable(this); 400 } 401 402 /** 403 * Checks whether this node has no usages. 404 */ 405 public final boolean hasNoUsages() { 406 return this.usage0 == null; 407 } 408 409 /** 410 * Checks whether this node has usages. 411 */ 412 public final boolean hasUsages() { 413 return this.usage0 != null; 414 } 415 416 void reverseUsageOrder() { 417 List<Node> snapshot = this.usages().snapshot(); 418 for (Node n : snapshot) { 419 this.removeUsage(n); 420 } 421 Collections.reverse(snapshot); 422 for (Node n : snapshot) { 423 this.addUsage(n); 424 } 425 } 426 427 /** 428 * Adds a given node to this node's {@linkplain #usages() usages}. 429 * 430 * @param node the node to add 431 */ 432 void addUsage(Node node) { 433 incUsageModCount(); 434 if (usage0 == null) { 435 usage0 = node; 436 } else if (usage1 == null) { 437 usage1 = node; 438 } else { 439 int length = extraUsages.length; 440 if (length == 0) { 441 extraUsages = new Node[4]; 442 } else if (extraUsagesCount == length) { 443 Node[] newExtraUsages = new Node[length * 2 + 1]; 444 System.arraycopy(extraUsages, 0, newExtraUsages, 0, length); 445 extraUsages = newExtraUsages; 446 } 447 extraUsages[extraUsagesCount++] = node; 448 } 449 } 450 451 private void movUsageFromEndTo(int destIndex) { 452 int lastIndex = this.getUsageCount() - 1; 453 if (destIndex == 0) { 454 if (lastIndex == 0) { 455 usage0 = null; 456 return; 457 } else if (lastIndex == 1) { 458 usage0 = usage1; 459 usage1 = null; 460 return; 461 } else { 462 usage0 = extraUsages[lastIndex - INLINE_USAGE_COUNT]; 463 } 464 } else if (destIndex == 1) { 465 if (lastIndex == 1) { 466 usage1 = null; 467 return; 468 } 469 usage1 = extraUsages[lastIndex - INLINE_USAGE_COUNT]; 470 } else { 471 Node n = extraUsages[lastIndex - INLINE_USAGE_COUNT]; 472 extraUsages[destIndex - INLINE_USAGE_COUNT] = n; 473 } 474 extraUsages[lastIndex - INLINE_USAGE_COUNT] = null; 475 this.extraUsagesCount--; 476 } 477 478 /** 479 * Removes a given node from this node's {@linkplain #usages() usages}. 480 * 481 * @param node the node to remove 482 * @return whether or not {@code usage} was in the usage list 483 */ 484 public boolean removeUsage(Node node) { 485 assert node != null; 486 // It is critical that this method maintains the invariant that 487 // the usage list has no null element preceding a non-null element 488 incUsageModCount(); 489 if (usage0 == node) { 490 this.movUsageFromEndTo(0); 491 return true; 492 } 493 if (usage1 == node) { 494 this.movUsageFromEndTo(1); 495 return true; 496 } 497 for (int i = this.extraUsagesCount - 1; i >= 0; i--) { 498 if (extraUsages[i] == node) { 499 this.movUsageFromEndTo(i + INLINE_USAGE_COUNT); 500 return true; 501 } 502 } 503 return false; 504 } 505 506 public final Node predecessor() { 507 return predecessor; 508 } 509 510 public final int modCount() { 511 if (isModificationCountsEnabled() && graph != null) { 512 return graph.modCount(this); 513 } 514 return 0; 515 } 516 517 final void incModCount() { 518 if (isModificationCountsEnabled() && graph != null) { 519 graph.incModCount(this); 520 } 521 } 522 523 final int usageModCount() { 524 if (isModificationCountsEnabled() && graph != null) { 525 return graph.usageModCount(this); 526 } 527 return 0; 528 } 529 530 final void incUsageModCount() { 531 if (isModificationCountsEnabled() && graph != null) { 532 graph.incUsageModCount(this); 533 } 534 } 535 536 public boolean isDeleted() { 537 return id <= DELETED_ID_START; 538 } 539 540 public boolean isAlive() { 541 return id >= ALIVE_ID_START; 542 } 543 544 /** 545 * Updates the usages sets of the given nodes after an input slot is changed from 546 * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and 547 * adds this node to {@code newInput}'s usages. 548 */ 549 protected void updateUsages(Node oldInput, Node newInput) { 550 assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput; 551 if (oldInput != newInput) { 552 if (oldInput != null) { 553 boolean result = removeThisFromUsages(oldInput); 554 assert assertTrue(result, "not found in usages, old input: %s", oldInput); 555 } 556 maybeNotifyInputChanged(this); 557 if (newInput != null) { 558 newInput.addUsage(this); 559 } 560 if (oldInput != null && oldInput.hasNoUsages()) { 561 maybeNotifyZeroUsages(oldInput); 562 } 563 } 564 } 565 566 protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) { 567 updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode()); 568 } 569 570 /** 571 * Updates the predecessor of the given nodes after a successor slot is changed from 572 * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds 573 * this node to newSuccessor's predecessors. 574 */ 575 protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) { 576 assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) || newSuccessor == null && !isAlive() : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor; 577 assert graph == null || !graph.isFrozen(); 578 if (oldSuccessor != newSuccessor) { 579 if (oldSuccessor != null) { 580 assert assertTrue(newSuccessor == null || oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this); 581 oldSuccessor.predecessor = null; 582 } 583 if (newSuccessor != null) { 584 assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this); 585 newSuccessor.predecessor = this; 586 } 587 } 588 } 589 590 void initialize(Graph newGraph) { 591 assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id); 592 this.graph = newGraph; 593 newGraph.register(this); 594 this.getNodeClass().registerAtInputsAsUsage(this); 595 this.getNodeClass().registerAtSuccessorsAsPredecessor(this); 596 } 597 598 /** 599 * The position of the bytecode that generated this node. 600 */ 601 NodeSourcePosition sourcePosition; 602 603 /** 604 * Gets the source position information for this node or null if it doesn't exist. 605 */ 606 607 public NodeSourcePosition getNodeSourcePosition() { 608 return sourcePosition; 609 } 610 611 /** 612 * Set the source position to {@code sourcePosition}. 613 */ 614 public void setNodeSourcePosition(NodeSourcePosition sourcePosition) { 615 this.sourcePosition = sourcePosition; 616 if (sourcePosition != null && graph != null && !graph.seenNodeSourcePosition) { 617 graph.seenNodeSourcePosition = true; 618 } 619 } 620 621 public DebugCloseable withNodeSourcePosition() { 622 return graph.withNodeSourcePosition(this); 623 } 624 625 public final NodeClass<? extends Node> getNodeClass() { 626 return nodeClass; 627 } 628 629 public boolean isAllowedUsageType(InputType type) { 630 if (type == InputType.Value) { 631 return false; 632 } 633 return getNodeClass().getAllowedUsageTypes().contains(type); 634 } 635 636 private boolean checkReplaceWith(Node other) { 637 assert assertTrue(graph == null || !graph.isFrozen(), "cannot modify frozen graph"); 638 assert assertFalse(other == this, "cannot replace a node with itself"); 639 assert assertFalse(isDeleted(), "cannot replace deleted node"); 640 assert assertTrue(other == null || !other.isDeleted(), "cannot replace with deleted node %s", other); 641 return true; 642 } 643 644 public final void replaceAtUsages(Node other) { 645 replaceAtUsages(other, null, null); 646 } 647 648 public final void replaceAtUsages(Node other, Predicate<Node> filter) { 649 replaceAtUsages(other, filter, null); 650 } 651 652 public final void replaceAtUsagesAndDelete(Node other) { 653 replaceAtUsages(other, null, this); 654 safeDelete(); 655 } 656 657 public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) { 658 replaceAtUsages(other, filter, this); 659 safeDelete(); 660 } 661 662 protected void replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted) { 663 assert checkReplaceWith(other); 664 int i = 0; 665 while (i < this.getUsageCount()) { 666 Node usage = this.getUsageAt(i); 667 if (filter == null || filter.test(usage)) { 668 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other); 669 assert assertTrue(result, "not found in inputs, usage: %s", usage); 670 /* 671 * Don't notify for nodes which are about to be deleted. 672 */ 673 if (toBeDeleted == null || usage != toBeDeleted) { 674 maybeNotifyInputChanged(usage); 675 } 676 if (other != null) { 677 other.addUsage(usage); 678 } 679 this.movUsageFromEndTo(i); 680 } else { 681 ++i; 682 } 683 } 684 } 685 686 public Node getUsageAt(int index) { 687 if (index == 0) { 688 return this.usage0; 689 } else if (index == 1) { 690 return this.usage1; 691 } else { 692 return this.extraUsages[index - INLINE_USAGE_COUNT]; 693 } 694 } 695 696 public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) { 697 assert checkReplaceWith(other); 698 int index = 0; 699 while (index < this.getUsageCount()) { 700 Node usage = getUsageAt(index); 701 if (usagePredicate.apply(usage)) { 702 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other); 703 assert assertTrue(result, "not found in inputs, usage: %s", usage); 704 if (other != null) { 705 maybeNotifyInputChanged(usage); 706 other.addUsage(usage); 707 } 708 this.movUsageFromEndTo(index); 709 } else { 710 index++; 711 } 712 } 713 } 714 715 public void replaceAtUsages(InputType type, Node other) { 716 assert checkReplaceWith(other); 717 for (Node usage : usages().snapshot()) { 718 for (Position pos : usage.inputPositions()) { 719 if (pos.getInputType() == type && pos.get(usage) == this) { 720 pos.set(usage, other); 721 } 722 } 723 } 724 } 725 726 private void maybeNotifyInputChanged(Node node) { 727 if (graph != null) { 728 assert !graph.isFrozen(); 729 NodeEventListener listener = graph.nodeEventListener; 730 if (listener != null) { 731 listener.inputChanged(node); 732 } 733 if (Fingerprint.ENABLED) { 734 Fingerprint.submit("%s: %s", NodeEvent.INPUT_CHANGED, node); 735 } 736 } 737 } 738 739 public void maybeNotifyZeroUsages(Node node) { 740 if (graph != null) { 741 assert !graph.isFrozen(); 742 NodeEventListener listener = graph.nodeEventListener; 743 if (listener != null && node.isAlive()) { 744 listener.usagesDroppedToZero(node); 745 } 746 if (Fingerprint.ENABLED) { 747 Fingerprint.submit("%s: %s", NodeEvent.ZERO_USAGES, node); 748 } 749 } 750 } 751 752 public void replaceAtPredecessor(Node other) { 753 assert checkReplaceWith(other); 754 if (predecessor != null) { 755 boolean result = predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other); 756 assert assertTrue(result, "not found in successors, predecessor: %s", predecessor); 757 predecessor.updatePredecessor(this, other); 758 } 759 } 760 761 public void replaceAndDelete(Node other) { 762 assert checkReplaceWith(other); 763 assert other != null; 764 replaceAtUsages(other); 765 replaceAtPredecessor(other); 766 this.safeDelete(); 767 } 768 769 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) { 770 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) { 771 updatePredecessor(oldSuccessor, newSuccessor); 772 } 773 } 774 775 public void replaceFirstInput(Node oldInput, Node newInput) { 776 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) { 777 updateUsages(oldInput, newInput); 778 } 779 } 780 781 public void clearInputs() { 782 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node"); 783 getNodeClass().unregisterAtInputsAsUsage(this); 784 } 785 786 boolean removeThisFromUsages(Node n) { 787 return n.removeUsage(this); 788 } 789 790 public void clearSuccessors() { 791 assert assertFalse(isDeleted(), "cannot clear successors of deleted node"); 792 getNodeClass().unregisterAtSuccessorsAsPredecessor(this); 793 } 794 795 private boolean checkDeletion() { 796 assertTrue(isAlive(), "must be alive"); 797 assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages()); 798 assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor); 799 return true; 800 } 801 802 /** 803 * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages} 804 * and no {@linkplain #predecessor() predecessor}. 805 */ 806 public void safeDelete() { 807 assert checkDeletion(); 808 this.clearInputs(); 809 this.clearSuccessors(); 810 markDeleted(); 811 } 812 813 public void markDeleted() { 814 graph.unregister(this); 815 id = DELETED_ID_START - id; 816 assert isDeleted(); 817 } 818 819 public final Node copyWithInputs() { 820 return copyWithInputs(true); 821 } 822 823 public final Node copyWithInputs(boolean insertIntoGraph) { 824 Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges); 825 if (insertIntoGraph) { 826 for (Node input : inputs()) { 827 input.addUsage(newNode); 828 } 829 } 830 return newNode; 831 } 832 833 /** 834 * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in 835 * {@link Node} exists to obviate the need to cast a node before invoking 836 * {@link Simplifiable#simplify(SimplifierTool)}. 837 * 838 * @param tool 839 */ 840 public void simplify(SimplifierTool tool) { 841 throw new UnsupportedOperationException(); 842 } 843 844 /** 845 * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw 846 * allocating} a copy of this node 847 * @param type the type of edges to process 848 * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are 849 * cleared 850 */ 851 private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) { 852 if (edgesToCopy.contains(type)) { 853 getNodeClass().getEdges(type).copy(this, newNode); 854 } else { 855 if (USE_UNSAFE_TO_CLONE) { 856 // The direct edges are already null 857 getNodeClass().getEdges(type).initializeLists(newNode, this); 858 } else { 859 getNodeClass().getEdges(type).clear(newNode); 860 } 861 } 862 } 863 864 public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class); 865 public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class); 866 public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs); 867 public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors); 868 869 /** 870 * Makes a copy of this node in(to) a given graph. 871 * 872 * @param into the graph in which the copy will be registered (which may be this node's graph) 873 * or null if the copy should not be registered in a graph 874 * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are 875 * initialized to their default value (i.e., {@code null} for a direct edge, an empty 876 * list for an edge list) 877 * @return the copy of this node 878 */ 879 final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) { 880 final NodeClass<? extends Node> nodeClassTmp = getNodeClass(); 881 boolean useIntoLeafNodeCache = false; 882 if (into != null) { 883 if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) { 884 useIntoLeafNodeCache = true; 885 Node otherNode = into.findNodeInCache(this); 886 if (otherNode != null) { 887 return otherNode; 888 } 889 } 890 } 891 892 Node newNode = null; 893 try { 894 if (USE_UNSAFE_TO_CLONE) { 895 newNode = (Node) UNSAFE.allocateInstance(getClass()); 896 newNode.nodeClass = nodeClassTmp; 897 nodeClassTmp.getData().copy(this, newNode); 898 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy); 899 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy); 900 } else { 901 newNode = (Node) this.clone(); 902 newNode.typeCacheNext = null; 903 newNode.usage0 = null; 904 newNode.usage1 = null; 905 newNode.predecessor = null; 906 newNode.extraUsagesCount = 0; 907 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy); 908 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy); 909 } 910 } catch (Exception e) { 911 throw new GraalGraphError(e).addContext(this); 912 } 913 newNode.graph = into; 914 newNode.id = INITIAL_ID; 915 if (into != null) { 916 into.register(newNode); 917 } 918 newNode.extraUsages = NO_NODES; 919 920 if (into != null && useIntoLeafNodeCache) { 921 into.putNodeIntoCache(newNode); 922 } 923 if (graph != null && into != null && sourcePosition != null) { 924 newNode.setNodeSourcePosition(sourcePosition); 925 } 926 newNode.afterClone(this); 927 return newNode; 928 } 929 930 protected void afterClone(@SuppressWarnings("unused") Node other) { 931 } 932 933 protected boolean verifyInputs() { 934 for (Position pos : inputPositions()) { 935 Node input = pos.get(this); 936 if (input == null) { 937 assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this); 938 } else { 939 assertFalse(input.isDeleted(), "input was deleted"); 940 assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph"); 941 assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType()); 942 } 943 } 944 return true; 945 } 946 947 public boolean verify() { 948 assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id); 949 assertTrue(graph() != null, "null graph"); 950 verifyInputs(); 951 if (Options.VerifyGraalGraphEdges.getValue()) { 952 verifyEdges(); 953 } 954 return true; 955 } 956 957 /** 958 * Perform expensive verification of inputs, usages, predecessors and successors. 959 * 960 * @return true 961 */ 962 public boolean verifyEdges() { 963 for (Node input : inputs()) { 964 assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input); 965 } 966 967 for (Node successor : successors()) { 968 assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor()); 969 assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor); 970 } 971 for (Node usage : usages()) { 972 assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage); 973 assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage); 974 boolean foundThis = false; 975 for (Position pos : usage.inputPositions()) { 976 if (pos.get(usage) == this) { 977 foundThis = true; 978 if (pos.getInputType() != InputType.Unchecked) { 979 assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type %s from %s to %s (%s)", pos.getInputType(), usage, this, pos.getName()); 980 } 981 } 982 } 983 assertTrue(foundThis, "missing input in usage %s", usage); 984 } 985 986 if (predecessor != null) { 987 assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor); 988 assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor); 989 } 990 return true; 991 } 992 993 public boolean assertTrue(boolean condition, String message, Object... args) { 994 if (condition) { 995 return true; 996 } else { 997 throw fail(message, args); 998 } 999 } 1000 1001 public boolean assertFalse(boolean condition, String message, Object... args) { 1002 if (condition) { 1003 throw fail(message, args); 1004 } else { 1005 return true; 1006 } 1007 } 1008 1009 protected VerificationError fail(String message, Object... args) throws GraalGraphError { 1010 throw new VerificationError(message, args).addContext(this); 1011 } 1012 1013 public Iterable<? extends Node> cfgPredecessors() { 1014 if (predecessor == null) { 1015 return Collections.emptySet(); 1016 } else { 1017 return Collections.singleton(predecessor); 1018 } 1019 } 1020 1021 /** 1022 * Returns an iterator that will provide all control-flow successors of this node. Normally this 1023 * will be the contents of all fields annotated with {@link Successor}, but some node classes 1024 * (like EndNode) may return different nodes. 1025 */ 1026 public Iterable<? extends Node> cfgSuccessors() { 1027 return successors(); 1028 } 1029 1030 /** 1031 * Nodes always use an {@linkplain System#identityHashCode(Object) identity} hash code. 1032 */ 1033 @Override 1034 public final int hashCode() { 1035 return System.identityHashCode(this); 1036 } 1037 1038 /** 1039 * Equality tests must rely solely on identity. 1040 */ 1041 @Override 1042 public final boolean equals(Object obj) { 1043 return super.equals(obj); 1044 } 1045 1046 /** 1047 * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the 1048 * ideal graph visualizer). 1049 */ 1050 public final Map<Object, Object> getDebugProperties() { 1051 return getDebugProperties(new HashMap<>()); 1052 } 1053 1054 /** 1055 * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the 1056 * ideal graph visualizer). Subclasses overriding this method should also fill the map using 1057 * their superclass. 1058 * 1059 * @param map 1060 */ 1061 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) { 1062 Fields properties = getNodeClass().getData(); 1063 for (int i = 0; i < properties.getCount(); i++) { 1064 map.put(properties.getName(i), properties.get(this, i)); 1065 } 1066 NodeSourcePosition pos = getNodeSourcePosition(); 1067 if (pos != null) { 1068 map.put("nodeSourcePosition", pos); 1069 } 1070 return map; 1071 } 1072 1073 /** 1074 * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}. 1075 */ 1076 @Override 1077 public final String toString() { 1078 return toString(Verbosity.Short); 1079 } 1080 1081 /** 1082 * Creates a String representation for this node with a given {@link Verbosity}. 1083 */ 1084 public String toString(Verbosity verbosity) { 1085 switch (verbosity) { 1086 case Id: 1087 return Integer.toString(id); 1088 case Name: 1089 return getNodeClass().shortName(); 1090 case Short: 1091 return toString(Verbosity.Id) + "|" + toString(Verbosity.Name); 1092 case Long: 1093 return toString(Verbosity.Short); 1094 case Debugger: 1095 case All: { 1096 StringBuilder str = new StringBuilder(); 1097 str.append(toString(Verbosity.Short)).append(" { "); 1098 for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) { 1099 str.append(entry.getKey()).append("=").append(entry.getValue()).append(", "); 1100 } 1101 str.append(" }"); 1102 return str.toString(); 1103 } 1104 default: 1105 throw new RuntimeException("unknown verbosity: " + verbosity); 1106 } 1107 } 1108 1109 @Deprecated 1110 public int getId() { 1111 return id; 1112 } 1113 1114 @Override 1115 public void formatTo(Formatter formatter, int flags, int width, int precision) { 1116 if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) { 1117 formatter.format("%s", toString(Verbosity.Id)); 1118 } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) { 1119 // Use All here since Long is only slightly longer than Short. 1120 formatter.format("%s", toString(Verbosity.All)); 1121 } else { 1122 formatter.format("%s", toString(Verbosity.Short)); 1123 } 1124 1125 boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY); 1126 int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0); 1127 if (width > 0) { 1128 if (this.predecessor != null) { 1129 formatter.format(" pred={"); 1130 this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0); 1131 formatter.format("}"); 1132 } 1133 1134 for (Position position : this.inputPositions()) { 1135 Node input = position.get(this); 1136 if (input != null) { 1137 formatter.format(" "); 1138 formatter.format(position.getName()); 1139 formatter.format("={"); 1140 input.formatTo(formatter, neighborsFlags, width - 1, 0); 1141 formatter.format("}"); 1142 } 1143 } 1144 } 1145 1146 if (precision > 0) { 1147 if (!hasNoUsages()) { 1148 formatter.format(" usages={"); 1149 int z = 0; 1150 for (Node usage : usages()) { 1151 if (z != 0) { 1152 formatter.format(", "); 1153 } 1154 usage.formatTo(formatter, neighborsFlags, 0, precision - 1); 1155 ++z; 1156 } 1157 formatter.format("}"); 1158 } 1159 1160 for (Position position : this.successorPositions()) { 1161 Node successor = position.get(this); 1162 if (successor != null) { 1163 formatter.format(" "); 1164 formatter.format(position.getName()); 1165 formatter.format("={"); 1166 successor.formatTo(formatter, neighborsFlags, 0, precision - 1); 1167 formatter.format("}"); 1168 } 1169 } 1170 } 1171 } 1172 1173 /** 1174 * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data 1175 * fields of another node of the same type. Primitive fields are compared by value and 1176 * non-primitive fields are compared by {@link Objects#equals(Object, Object)}. 1177 * 1178 * The result of this method undefined if {@code other.getClass() != this.getClass()}. 1179 * 1180 * @param other a node of exactly the same type as this node 1181 * @return true if the data fields of this object and {@code other} are equal 1182 */ 1183 public boolean valueEquals(Node other) { 1184 return getNodeClass().dataEquals(this, other); 1185 } 1186 1187 public final void pushInputs(NodeStack stack) { 1188 getNodeClass().pushInputs(this, stack); 1189 } 1190 }