1 /* 2 * Copyright (c) 2011, 2019, 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 usgae. 431 */ hasExactlyOneUsage()432 public final boolean hasExactlyOneUsage() { 433 return hasUsages() && !hasMoreThanOneUsage(); 434 } 435 436 /** 437 * Adds a given node to this node's {@linkplain #usages() usages}. 438 * 439 * @param node the node to add 440 */ addUsage(Node node)441 void addUsage(Node node) { 442 incUsageModCount(); 443 if (usage0 == null) { 444 usage0 = node; 445 } else if (usage1 == null) { 446 usage1 = node; 447 } else { 448 int length = extraUsages.length; 449 if (length == 0) { 450 extraUsages = new Node[4]; 451 } else if (extraUsagesCount == length) { 452 Node[] newExtraUsages = new Node[length * 2 + 1]; 453 System.arraycopy(extraUsages, 0, newExtraUsages, 0, length); 454 extraUsages = newExtraUsages; 455 } 456 extraUsages[extraUsagesCount++] = node; 457 } 458 } 459 movUsageFromEndTo(int destIndex)460 private void movUsageFromEndTo(int destIndex) { 461 if (destIndex >= INLINE_USAGE_COUNT) { 462 movUsageFromEndToExtraUsages(destIndex - INLINE_USAGE_COUNT); 463 } else if (destIndex == 1) { 464 movUsageFromEndToIndexOne(); 465 } else { 466 assert destIndex == 0; 467 movUsageFromEndToIndexZero(); 468 } 469 } 470 movUsageFromEndToExtraUsages(int destExtraIndex)471 private void movUsageFromEndToExtraUsages(int destExtraIndex) { 472 this.extraUsagesCount--; 473 Node n = extraUsages[extraUsagesCount]; 474 extraUsages[destExtraIndex] = n; 475 extraUsages[extraUsagesCount] = null; 476 } 477 movUsageFromEndToIndexZero()478 private void movUsageFromEndToIndexZero() { 479 if (extraUsagesCount > 0) { 480 this.extraUsagesCount--; 481 usage0 = extraUsages[extraUsagesCount]; 482 extraUsages[extraUsagesCount] = null; 483 } else if (usage1 != null) { 484 usage0 = usage1; 485 usage1 = null; 486 } else { 487 usage0 = null; 488 } 489 } 490 movUsageFromEndToIndexOne()491 private void movUsageFromEndToIndexOne() { 492 if (extraUsagesCount > 0) { 493 this.extraUsagesCount--; 494 usage1 = extraUsages[extraUsagesCount]; 495 extraUsages[extraUsagesCount] = null; 496 } else { 497 assert usage1 != null; 498 usage1 = null; 499 } 500 } 501 502 /** 503 * Removes a given node from this node's {@linkplain #usages() usages}. 504 * 505 * @param node the node to remove 506 * @return whether or not {@code usage} was in the usage list 507 */ removeUsage(Node node)508 public boolean removeUsage(Node node) { 509 assert node != null; 510 // For large graphs, usage removal is performance critical. 511 // Furthermore, it is critical that this method maintains the invariant that the usage list 512 // has no null element preceding a non-null element. 513 incUsageModCount(); 514 if (usage0 == node) { 515 movUsageFromEndToIndexZero(); 516 return true; 517 } 518 if (usage1 == node) { 519 movUsageFromEndToIndexOne(); 520 return true; 521 } 522 for (int i = this.extraUsagesCount - 1; i >= 0; i--) { 523 if (extraUsages[i] == node) { 524 movUsageFromEndToExtraUsages(i); 525 return true; 526 } 527 } 528 return false; 529 } 530 predecessor()531 public final Node predecessor() { 532 return predecessor; 533 } 534 modCount()535 public final int modCount() { 536 if (isModificationCountsEnabled() && graph != null) { 537 return graph.modCount(this); 538 } 539 return 0; 540 } 541 incModCount()542 final void incModCount() { 543 if (isModificationCountsEnabled() && graph != null) { 544 graph.incModCount(this); 545 } 546 } 547 usageModCount()548 final int usageModCount() { 549 if (isModificationCountsEnabled() && graph != null) { 550 return graph.usageModCount(this); 551 } 552 return 0; 553 } 554 incUsageModCount()555 final void incUsageModCount() { 556 if (isModificationCountsEnabled() && graph != null) { 557 graph.incUsageModCount(this); 558 } 559 } 560 isDeleted()561 public final boolean isDeleted() { 562 return id <= DELETED_ID_START; 563 } 564 isAlive()565 public final boolean isAlive() { 566 return id >= ALIVE_ID_START; 567 } 568 isUnregistered()569 public final boolean isUnregistered() { 570 return id == INITIAL_ID; 571 } 572 573 /** 574 * Updates the usages sets of the given nodes after an input slot is changed from 575 * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and 576 * adds this node to {@code newInput}'s usages. 577 */ updateUsages(Node oldInput, Node newInput)578 protected void updateUsages(Node oldInput, Node newInput) { 579 assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput; 580 if (oldInput != newInput) { 581 if (oldInput != null) { 582 boolean result = removeThisFromUsages(oldInput); 583 assert assertTrue(result, "not found in usages, old input: %s", oldInput); 584 } 585 maybeNotifyInputChanged(this); 586 if (newInput != null) { 587 newInput.addUsage(this); 588 } 589 if (oldInput != null && oldInput.hasNoUsages()) { 590 maybeNotifyZeroUsages(oldInput); 591 } 592 } 593 } 594 updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput)595 protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) { 596 updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode()); 597 } 598 599 /** 600 * Updates the predecessor of the given nodes after a successor slot is changed from 601 * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds 602 * this node to newSuccessor's predecessors. 603 */ updatePredecessor(Node oldSuccessor, Node newSuccessor)604 protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) { 605 assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) || newSuccessor == null && !isAlive() : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor; 606 assert graph == null || !graph.isFrozen(); 607 if (oldSuccessor != newSuccessor) { 608 if (oldSuccessor != null) { 609 assert assertTrue(newSuccessor == null || oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this); 610 oldSuccessor.predecessor = null; 611 } 612 if (newSuccessor != null) { 613 assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this); 614 newSuccessor.predecessor = this; 615 } 616 maybeNotifyInputChanged(this); 617 } 618 } 619 initialize(Graph newGraph)620 void initialize(Graph newGraph) { 621 assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id); 622 this.graph = newGraph; 623 newGraph.register(this); 624 NodeClass<? extends Node> nc = nodeClass; 625 nc.registerAtInputsAsUsage(this); 626 nc.registerAtSuccessorsAsPredecessor(this); 627 } 628 629 /** 630 * Information associated with this node. A single value is stored directly in the field. 631 * Multiple values are stored by creating an Object[]. 632 */ 633 private Object annotation; 634 getNodeInfo(Class<T> clazz)635 private <T> T getNodeInfo(Class<T> clazz) { 636 assert clazz != Object[].class; 637 if (annotation == null) { 638 return null; 639 } 640 if (clazz.isInstance(annotation)) { 641 return clazz.cast(annotation); 642 } 643 if (annotation.getClass() == Object[].class) { 644 Object[] annotations = (Object[]) annotation; 645 for (Object ann : annotations) { 646 if (clazz.isInstance(ann)) { 647 return clazz.cast(ann); 648 } 649 } 650 } 651 return null; 652 } 653 setNodeInfo(Class<T> clazz, T value)654 private <T> void setNodeInfo(Class<T> clazz, T value) { 655 assert clazz != Object[].class; 656 if (annotation == null || clazz.isInstance(annotation)) { 657 // Replace the current value 658 this.annotation = value; 659 } else if (annotation.getClass() == Object[].class) { 660 Object[] annotations = (Object[]) annotation; 661 for (int i = 0; i < annotations.length; i++) { 662 if (clazz.isInstance(annotations[i])) { 663 annotations[i] = value; 664 return; 665 } 666 } 667 Object[] newAnnotations = Arrays.copyOf(annotations, annotations.length + 1); 668 newAnnotations[annotations.length] = value; 669 this.annotation = newAnnotations; 670 } else { 671 this.annotation = new Object[]{this.annotation, value}; 672 } 673 } 674 675 /** 676 * Gets the source position information for this node or null if it doesn't exist. 677 */ 678 getNodeSourcePosition()679 public NodeSourcePosition getNodeSourcePosition() { 680 return getNodeInfo(NodeSourcePosition.class); 681 } 682 683 /** 684 * Set the source position to {@code sourcePosition}. Setting it to null is ignored so that it's 685 * not accidentally cleared. Use {@link #clearNodeSourcePosition()} instead. 686 */ setNodeSourcePosition(NodeSourcePosition sourcePosition)687 public void setNodeSourcePosition(NodeSourcePosition sourcePosition) { 688 if (sourcePosition == null) { 689 return; 690 } 691 setNodeInfo(NodeSourcePosition.class, sourcePosition); 692 } 693 clearNodeSourcePosition()694 public void clearNodeSourcePosition() { 695 setNodeInfo(NodeSourcePosition.class, null); 696 } 697 getCreationPosition()698 public NodeCreationStackTrace getCreationPosition() { 699 return getNodeInfo(NodeCreationStackTrace.class); 700 } 701 setCreationPosition(NodeCreationStackTrace trace)702 public void setCreationPosition(NodeCreationStackTrace trace) { 703 setNodeInfo(NodeCreationStackTrace.class, trace); 704 } 705 getInsertionPosition()706 public NodeInsertionStackTrace getInsertionPosition() { 707 return getNodeInfo(NodeInsertionStackTrace.class); 708 } 709 setInsertionPosition(NodeInsertionStackTrace trace)710 public void setInsertionPosition(NodeInsertionStackTrace trace) { 711 setNodeInfo(NodeInsertionStackTrace.class, trace); 712 } 713 714 /** 715 * Update the source position only if it is null. 716 */ updateNodeSourcePosition(Supplier<NodeSourcePosition> sourcePositionSupp)717 public void updateNodeSourcePosition(Supplier<NodeSourcePosition> sourcePositionSupp) { 718 if (this.getNodeSourcePosition() == null) { 719 setNodeSourcePosition(sourcePositionSupp.get()); 720 } 721 } 722 withNodeSourcePosition()723 public DebugCloseable withNodeSourcePosition() { 724 return graph.withNodeSourcePosition(this); 725 } 726 getNodeClass()727 public final NodeClass<? extends Node> getNodeClass() { 728 return nodeClass; 729 } 730 isAllowedUsageType(InputType type)731 public boolean isAllowedUsageType(InputType type) { 732 if (type == InputType.Value) { 733 return false; 734 } 735 return getNodeClass().getAllowedUsageTypes().contains(type); 736 } 737 checkReplaceWith(Node other)738 private boolean checkReplaceWith(Node other) { 739 if (graph != null && graph.isFrozen()) { 740 fail("cannot modify frozen graph"); 741 } 742 if (other == this) { 743 fail("cannot replace a node with itself"); 744 } 745 if (isDeleted()) { 746 fail("cannot replace deleted node"); 747 } 748 if (other != null && other.isDeleted()) { 749 fail("cannot replace with deleted node %s", other); 750 } 751 return true; 752 } 753 replaceAtUsages(Node other)754 public final void replaceAtUsages(Node other) { 755 replaceAtAllUsages(other, (Node) null); 756 } 757 replaceAtUsages(Node other, Predicate<Node> filter)758 public final void replaceAtUsages(Node other, Predicate<Node> filter) { 759 replaceAtUsages(other, filter, null); 760 } 761 replaceAtUsagesAndDelete(Node other)762 public final void replaceAtUsagesAndDelete(Node other) { 763 replaceAtUsages(other, null, this); 764 safeDelete(); 765 } 766 replaceAtUsagesAndDelete(Node other, Predicate<Node> filter)767 public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) { 768 replaceAtUsages(other, filter, this); 769 safeDelete(); 770 } 771 replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted)772 protected void replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted) { 773 if (filter == null) { 774 replaceAtAllUsages(other, toBeDeleted); 775 } else { 776 replaceAtMatchingUsages(other, filter, toBeDeleted); 777 } 778 } 779 replaceAtAllUsages(Node other, Node toBeDeleted)780 protected void replaceAtAllUsages(Node other, Node toBeDeleted) { 781 checkReplaceWith(other); 782 if (usage0 == null) { 783 return; 784 } 785 replaceAtUsage(other, toBeDeleted, usage0); 786 usage0 = null; 787 788 if (usage1 == null) { 789 return; 790 } 791 replaceAtUsage(other, toBeDeleted, usage1); 792 usage1 = null; 793 794 if (extraUsagesCount <= 0) { 795 return; 796 } 797 for (int i = 0; i < extraUsagesCount; i++) { 798 Node usage = extraUsages[i]; 799 replaceAtUsage(other, toBeDeleted, usage); 800 } 801 this.extraUsages = NO_NODES; 802 this.extraUsagesCount = 0; 803 } 804 replaceAtUsage(Node other, Node toBeDeleted, Node usage)805 private void replaceAtUsage(Node other, Node toBeDeleted, Node usage) { 806 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other); 807 assert assertTrue(result, "not found in inputs, usage: %s", usage); 808 /* 809 * Don't notify for nodes which are about to be deleted. 810 */ 811 if (toBeDeleted == null || usage != toBeDeleted) { 812 maybeNotifyInputChanged(usage); 813 } 814 if (other != null) { 815 other.addUsage(usage); 816 } 817 } 818 replaceAtMatchingUsages(Node other, Predicate<Node> filter, Node toBeDeleted)819 private void replaceAtMatchingUsages(Node other, Predicate<Node> filter, Node toBeDeleted) { 820 if (filter == null) { 821 throw fail("filter cannot be null"); 822 } 823 checkReplaceWith(other); 824 int i = 0; 825 int usageCount = this.getUsageCount(); 826 while (i < usageCount) { 827 Node usage = this.getUsageAt(i); 828 if (filter.test(usage)) { 829 replaceAtUsage(other, toBeDeleted, usage); 830 this.movUsageFromEndTo(i); 831 usageCount--; 832 } else { 833 ++i; 834 } 835 } 836 } 837 getUsageAt(int index)838 private Node getUsageAt(int index) { 839 if (index == 0) { 840 return this.usage0; 841 } else if (index == 1) { 842 return this.usage1; 843 } else { 844 return this.extraUsages[index - INLINE_USAGE_COUNT]; 845 } 846 } 847 replaceAtMatchingUsages(Node other, NodePredicate usagePredicate)848 public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) { 849 checkReplaceWith(other); 850 replaceAtMatchingUsages(other, usagePredicate, null); 851 } 852 replaceAtUsagePos(Node other, Node usage, Position pos)853 private void replaceAtUsagePos(Node other, Node usage, Position pos) { 854 pos.initialize(usage, other); 855 maybeNotifyInputChanged(usage); 856 if (other != null) { 857 other.addUsage(usage); 858 } 859 } 860 replaceAtUsages(InputType type, Node other)861 public void replaceAtUsages(InputType type, Node other) { 862 checkReplaceWith(other); 863 int i = 0; 864 int usageCount = this.getUsageCount(); 865 if (usageCount == 0) { 866 return; 867 } 868 usages: while (i < usageCount) { 869 Node usage = this.getUsageAt(i); 870 for (Position pos : usage.inputPositions()) { 871 if (pos.getInputType() == type && pos.get(usage) == this) { 872 replaceAtUsagePos(other, usage, pos); 873 this.movUsageFromEndTo(i); 874 usageCount--; 875 continue usages; 876 } 877 } 878 i++; 879 } 880 if (hasNoUsages()) { 881 maybeNotifyZeroUsages(this); 882 } 883 } 884 maybeNotifyInputChanged(Node node)885 private void maybeNotifyInputChanged(Node node) { 886 if (graph != null) { 887 assert !graph.isFrozen(); 888 NodeEventListener listener = graph.nodeEventListener; 889 if (listener != null) { 890 listener.event(Graph.NodeEvent.INPUT_CHANGED, node); 891 } 892 } 893 } 894 maybeNotifyZeroUsages(Node node)895 public void maybeNotifyZeroUsages(Node node) { 896 if (graph != null) { 897 assert !graph.isFrozen(); 898 NodeEventListener listener = graph.nodeEventListener; 899 if (listener != null && node.isAlive()) { 900 listener.event(Graph.NodeEvent.ZERO_USAGES, node); 901 } 902 } 903 } 904 replaceAtPredecessor(Node other)905 public void replaceAtPredecessor(Node other) { 906 checkReplaceWith(other); 907 if (predecessor != null) { 908 if (!predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other)) { 909 fail("not found in successors, predecessor: %s", predecessor); 910 } 911 predecessor.updatePredecessor(this, other); 912 } 913 } 914 replaceAndDelete(Node other)915 public void replaceAndDelete(Node other) { 916 checkReplaceWith(other); 917 if (other == null) { 918 fail("cannot replace with null"); 919 } 920 if (this.hasUsages()) { 921 replaceAtUsages(other); 922 } 923 replaceAtPredecessor(other); 924 this.safeDelete(); 925 } 926 replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor)927 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) { 928 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) { 929 updatePredecessor(oldSuccessor, newSuccessor); 930 } 931 } 932 replaceFirstInput(Node oldInput, Node newInput)933 public void replaceFirstInput(Node oldInput, Node newInput) { 934 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) { 935 updateUsages(oldInput, newInput); 936 } 937 } 938 replaceAllInputs(Node oldInput, Node newInput)939 public void replaceAllInputs(Node oldInput, Node newInput) { 940 while (nodeClass.replaceFirstInput(this, oldInput, newInput)) { 941 updateUsages(oldInput, newInput); 942 } 943 } 944 replaceFirstInput(Node oldInput, Node newInput, InputType type)945 public void replaceFirstInput(Node oldInput, Node newInput, InputType type) { 946 for (Position pos : inputPositions()) { 947 if (pos.getInputType() == type && pos.get(this) == oldInput) { 948 pos.set(this, newInput); 949 } 950 } 951 } 952 clearInputs()953 public void clearInputs() { 954 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node"); 955 getNodeClass().unregisterAtInputsAsUsage(this); 956 } 957 removeThisFromUsages(Node n)958 boolean removeThisFromUsages(Node n) { 959 return n.removeUsage(this); 960 } 961 clearSuccessors()962 public void clearSuccessors() { 963 assert assertFalse(isDeleted(), "cannot clear successors of deleted node"); 964 getNodeClass().unregisterAtSuccessorsAsPredecessor(this); 965 } 966 checkDeletion()967 private boolean checkDeletion() { 968 assertTrue(isAlive(), "must be alive"); 969 assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages()); 970 assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor); 971 return true; 972 } 973 974 /** 975 * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages} 976 * and no {@linkplain #predecessor() predecessor}. 977 */ safeDelete()978 public void safeDelete() { 979 assert checkDeletion(); 980 this.clearInputs(); 981 this.clearSuccessors(); 982 markDeleted(); 983 } 984 markDeleted()985 public void markDeleted() { 986 graph.unregister(this); 987 id = DELETED_ID_START - id; 988 assert isDeleted(); 989 } 990 copyWithInputs()991 public final Node copyWithInputs() { 992 return copyWithInputs(true); 993 } 994 copyWithInputs(boolean insertIntoGraph)995 public final Node copyWithInputs(boolean insertIntoGraph) { 996 Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges); 997 if (insertIntoGraph) { 998 for (Node input : inputs()) { 999 input.addUsage(newNode); 1000 } 1001 } 1002 return newNode; 1003 } 1004 1005 /** 1006 * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in 1007 * {@link Node} exists to obviate the need to cast a node before invoking 1008 * {@link Simplifiable#simplify(SimplifierTool)}. 1009 * 1010 * @param tool 1011 */ simplify(SimplifierTool tool)1012 public void simplify(SimplifierTool tool) { 1013 throw new UnsupportedOperationException(); 1014 } 1015 1016 /** 1017 * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw 1018 * allocating} a copy of this node 1019 * @param type the type of edges to process 1020 * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are 1021 * cleared 1022 */ copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy)1023 private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) { 1024 if (edgesToCopy.contains(type)) { 1025 getNodeClass().getEdges(type).copy(this, newNode); 1026 } else { 1027 // The direct edges are already null 1028 getNodeClass().getEdges(type).initializeLists(newNode, this); 1029 } 1030 } 1031 1032 public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class); 1033 public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class); 1034 public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs); 1035 public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors); 1036 1037 /** 1038 * Makes a copy of this node in(to) a given graph. 1039 * 1040 * @param into the graph in which the copy will be registered (which may be this node's graph) 1041 * or null if the copy should not be registered in a graph 1042 * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are 1043 * initialized to their default value (i.e., {@code null} for a direct edge, an empty 1044 * list for an edge list) 1045 * @return the copy of this node 1046 */ clone(Graph into, EnumSet<Edges.Type> edgesToCopy)1047 final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) { 1048 final NodeClass<? extends Node> nodeClassTmp = getNodeClass(); 1049 boolean useIntoLeafNodeCache = false; 1050 if (into != null) { 1051 if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) { 1052 useIntoLeafNodeCache = true; 1053 Node otherNode = into.findNodeInCache(this); 1054 if (otherNode != null) { 1055 return otherNode; 1056 } 1057 } 1058 } 1059 1060 Node newNode = null; 1061 try { 1062 newNode = (Node) UNSAFE.allocateInstance(getClass()); 1063 newNode.nodeClass = nodeClassTmp; 1064 nodeClassTmp.getData().copy(this, newNode); 1065 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy); 1066 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy); 1067 } catch (Exception e) { 1068 throw new GraalGraphError(e).addContext(this); 1069 } 1070 newNode.graph = into; 1071 newNode.id = INITIAL_ID; 1072 if (getNodeSourcePosition() != null && (into == null || into.trackNodeSourcePosition())) { 1073 newNode.setNodeSourcePosition(getNodeSourcePosition()); 1074 } 1075 if (into != null) { 1076 into.register(newNode); 1077 } 1078 newNode.extraUsages = NO_NODES; 1079 1080 if (into != null && useIntoLeafNodeCache) { 1081 into.putNodeIntoCache(newNode); 1082 } 1083 newNode.afterClone(this); 1084 return newNode; 1085 } 1086 afterClone(@uppressWarningsR) Node other)1087 protected void afterClone(@SuppressWarnings("unused") Node other) { 1088 } 1089 verifyInputs()1090 protected boolean verifyInputs() { 1091 for (Position pos : inputPositions()) { 1092 Node input = pos.get(this); 1093 if (input == null) { 1094 assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this); 1095 } else { 1096 assertFalse(input.isDeleted(), "input was deleted %s", input); 1097 assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph"); 1098 assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType()); 1099 Class<?> expectedType = pos.getType(); 1100 assertTrue(expectedType.isAssignableFrom(input.getClass()), "Invalid input type for %s: expected a %s but was a %s", pos, expectedType, input.getClass()); 1101 } 1102 } 1103 return true; 1104 } 1105 verify()1106 public boolean verify() { 1107 assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id); 1108 assertTrue(graph() != null, "null graph"); 1109 verifyInputs(); 1110 if (Options.VerifyGraalGraphEdges.getValue(getOptions())) { 1111 verifyEdges(); 1112 } 1113 return true; 1114 } 1115 verifySourcePosition()1116 public boolean verifySourcePosition() { 1117 return true; 1118 } 1119 1120 /** 1121 * Perform expensive verification of inputs, usages, predecessors and successors. 1122 * 1123 * @return true 1124 */ verifyEdges()1125 public boolean verifyEdges() { 1126 for (Node input : inputs()) { 1127 assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input); 1128 } 1129 1130 for (Node successor : successors()) { 1131 assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor()); 1132 assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor); 1133 } 1134 for (Node usage : usages()) { 1135 assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage); 1136 assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage); 1137 boolean foundThis = false; 1138 for (Position pos : usage.inputPositions()) { 1139 if (pos.get(usage) == this) { 1140 foundThis = true; 1141 if (pos.getInputType() != InputType.Unchecked) { 1142 assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type %s from %s to %s (%s)", pos.getInputType(), usage, this, pos.getName()); 1143 } 1144 } 1145 } 1146 assertTrue(foundThis, "missing input in usage %s", usage); 1147 } 1148 1149 if (predecessor != null) { 1150 assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor); 1151 assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor); 1152 } 1153 return true; 1154 } 1155 assertTrue(boolean condition, String message, Object... args)1156 public boolean assertTrue(boolean condition, String message, Object... args) { 1157 if (condition) { 1158 return true; 1159 } else { 1160 throw fail(message, args); 1161 } 1162 } 1163 assertFalse(boolean condition, String message, Object... args)1164 public boolean assertFalse(boolean condition, String message, Object... args) { 1165 if (condition) { 1166 throw fail(message, args); 1167 } else { 1168 return true; 1169 } 1170 } 1171 fail(String message, Object... args)1172 protected VerificationError fail(String message, Object... args) throws GraalGraphError { 1173 throw new VerificationError(message, args).addContext(this); 1174 } 1175 cfgPredecessors()1176 public Iterable<? extends Node> cfgPredecessors() { 1177 if (predecessor == null) { 1178 return Collections.emptySet(); 1179 } else { 1180 return Collections.singleton(predecessor); 1181 } 1182 } 1183 1184 /** 1185 * Returns an iterator that will provide all control-flow successors of this node. Normally this 1186 * will be the contents of all fields annotated with {@link Successor}, but some node classes 1187 * (like EndNode) may return different nodes. 1188 */ cfgSuccessors()1189 public Iterable<? extends Node> cfgSuccessors() { 1190 return successors(); 1191 } 1192 1193 /** 1194 * Nodes using their {@link #id} as the hash code. This works very well when nodes of the same 1195 * graph are stored in sets. It can give bad behavior when storing nodes of different graphs in 1196 * the same set. 1197 */ 1198 @Override hashCode()1199 public final int hashCode() { 1200 assert !this.isUnregistered() : "node not yet constructed"; 1201 if (this.isDeleted()) { 1202 return -id + DELETED_ID_START; 1203 } 1204 return id; 1205 } 1206 1207 /** 1208 * Do not overwrite the equality test of a node in subclasses. Equality tests must rely solely 1209 * on identity. 1210 */ 1211 1212 /** 1213 * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the 1214 * ideal graph visualizer). 1215 */ getDebugProperties()1216 public final Map<Object, Object> getDebugProperties() { 1217 return getDebugProperties(new HashMap<>()); 1218 } 1219 1220 /** 1221 * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the 1222 * ideal graph visualizer). Subclasses overriding this method should also fill the map using 1223 * their superclass. 1224 * 1225 * @param map 1226 */ getDebugProperties(Map<Object, Object> map)1227 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) { 1228 Fields properties = getNodeClass().getData(); 1229 for (int i = 0; i < properties.getCount(); i++) { 1230 map.put(properties.getName(i), properties.get(this, i)); 1231 } 1232 NodeSourcePosition pos = getNodeSourcePosition(); 1233 if (pos != null) { 1234 map.put("nodeSourcePosition", pos); 1235 } 1236 NodeCreationStackTrace creation = getCreationPosition(); 1237 if (creation != null) { 1238 map.put("nodeCreationPosition", creation.getStrackTraceString()); 1239 } 1240 NodeInsertionStackTrace insertion = getInsertionPosition(); 1241 if (insertion != null) { 1242 map.put("nodeInsertionPosition", insertion.getStrackTraceString()); 1243 } 1244 return map; 1245 } 1246 1247 /** 1248 * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}. 1249 */ 1250 @Override toString()1251 public final String toString() { 1252 return toString(Verbosity.Short); 1253 } 1254 1255 /** 1256 * Creates a String representation for this node with a given {@link Verbosity}. 1257 */ toString(Verbosity verbosity)1258 public String toString(Verbosity verbosity) { 1259 switch (verbosity) { 1260 case Id: 1261 return Integer.toString(id); 1262 case Name: 1263 return getNodeClass().shortName(); 1264 case Short: 1265 return toString(Verbosity.Id) + "|" + toString(Verbosity.Name); 1266 case Long: 1267 return toString(Verbosity.Short); 1268 case Debugger: 1269 case All: { 1270 StringBuilder str = new StringBuilder(); 1271 str.append(toString(Verbosity.Short)).append(" { "); 1272 for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) { 1273 str.append(entry.getKey()).append("=").append(entry.getValue()).append(", "); 1274 } 1275 str.append(" }"); 1276 return str.toString(); 1277 } 1278 default: 1279 throw new RuntimeException("unknown verbosity: " + verbosity); 1280 } 1281 } 1282 1283 @Deprecated getId()1284 public int getId() { 1285 return id; 1286 } 1287 1288 @Override formatTo(Formatter formatter, int flags, int width, int precision)1289 public void formatTo(Formatter formatter, int flags, int width, int precision) { 1290 if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) { 1291 formatter.format("%s", toString(Verbosity.Id)); 1292 } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) { 1293 // Use All here since Long is only slightly longer than Short. 1294 formatter.format("%s", toString(Verbosity.All)); 1295 } else { 1296 formatter.format("%s", toString(Verbosity.Short)); 1297 } 1298 1299 boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY); 1300 int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0); 1301 if (width > 0) { 1302 if (this.predecessor != null) { 1303 formatter.format(" pred={"); 1304 this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0); 1305 formatter.format("}"); 1306 } 1307 1308 for (Position position : this.inputPositions()) { 1309 Node input = position.get(this); 1310 if (input != null) { 1311 formatter.format(" "); 1312 formatter.format(position.getName()); 1313 formatter.format("={"); 1314 input.formatTo(formatter, neighborsFlags, width - 1, 0); 1315 formatter.format("}"); 1316 } 1317 } 1318 } 1319 1320 if (precision > 0) { 1321 if (!hasNoUsages()) { 1322 formatter.format(" usages={"); 1323 int z = 0; 1324 for (Node usage : usages()) { 1325 if (z != 0) { 1326 formatter.format(", "); 1327 } 1328 usage.formatTo(formatter, neighborsFlags, 0, precision - 1); 1329 ++z; 1330 } 1331 formatter.format("}"); 1332 } 1333 1334 for (Position position : this.successorPositions()) { 1335 Node successor = position.get(this); 1336 if (successor != null) { 1337 formatter.format(" "); 1338 formatter.format(position.getName()); 1339 formatter.format("={"); 1340 successor.formatTo(formatter, neighborsFlags, 0, precision - 1); 1341 formatter.format("}"); 1342 } 1343 } 1344 } 1345 } 1346 1347 /** 1348 * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data 1349 * fields of another node of the same type. Primitive fields are compared by value and 1350 * non-primitive fields are compared by {@link Objects#equals(Object, Object)}. 1351 * 1352 * The result of this method undefined if {@code other.getClass() != this.getClass()}. 1353 * 1354 * @param other a node of exactly the same type as this node 1355 * @return true if the data fields of this object and {@code other} are equal 1356 */ valueEquals(Node other)1357 public boolean valueEquals(Node other) { 1358 return getNodeClass().dataEquals(this, other); 1359 } 1360 1361 /** 1362 * Determines if this node is equal to the other node while ignoring differences in 1363 * {@linkplain Successor control-flow} edges. 1364 * 1365 */ dataFlowEquals(Node other)1366 public boolean dataFlowEquals(Node other) { 1367 return this == other || nodeClass == other.getNodeClass() && this.valueEquals(other) && nodeClass.equalInputs(this, other); 1368 } 1369 pushInputs(NodeStack stack)1370 public final void pushInputs(NodeStack stack) { 1371 getNodeClass().pushInputs(this, stack); 1372 } 1373 estimatedNodeSize()1374 public NodeSize estimatedNodeSize() { 1375 return nodeClass.size(); 1376 } 1377 estimatedNodeCycles()1378 public NodeCycles estimatedNodeCycles() { 1379 return nodeClass.cycles(); 1380 } 1381 1382 } 1383