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