1 /*
2 * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.graph;
26
27 import static org.graalvm.compiler.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 {
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 {
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 */
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 */
194 boolean injectedStampIsNonNull() default false;
195 }
196
197 /**
198 * Marker for a node that can be replaced by another node via global value numbering. A
199 * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same
200 * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node
201 * can be replaced by another node of the same type that has exactly the same data values as
202 * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors()
203 * successors}.
204 */
205 public interface ValueNumberable {
206 }
207
208 /**
209 * Marker interface for nodes that contains other nodes. When the inputs to this node changes,
210 * users of this node should also be placed on the work list for canonicalization.
211 */
212 public interface IndirectCanonicalization {
213 }
214
215 private Graph graph;
216 int id;
217
218 // this next pointer is used in Graph to implement fast iteration over NodeClass types, it
219 // therefore points to the next Node of the same type.
220 Node typeCacheNext;
221
222 static final int INLINE_USAGE_COUNT = 2;
223 private static final Node[] NO_NODES = {};
224
225 /**
226 * Head of usage list. The elements of the usage list in order are {@link #usage0},
227 * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list.
228 */
229 Node usage0;
230 Node usage1;
231 Node[] extraUsages;
232 int extraUsagesCount;
233
234 private Node predecessor;
235 private NodeClass<? extends Node> nodeClass;
236
237 public static final int NODE_LIST = -2;
238 public static final int NOT_ITERABLE = -1;
239
240 static class NodeStackTrace {
241 final StackTraceElement[] stackTrace;
242
243 NodeStackTrace() {
244 this.stackTrace = new Throwable().getStackTrace();
245 }
246
247 private String getString(String label) {
248 StringBuilder sb = new StringBuilder();
249 if (label != null) {
250 sb.append(label).append(": ");
251 }
252 for (StackTraceElement ste : stackTrace) {
253 sb.append("at ").append(ste.toString()).append('\n');
254 }
255 return sb.toString();
256 }
257
258 String getStrackTraceString() {
259 return getString(null);
260 }
261
262 @Override
263 public String toString() {
264 return getString(getClass().getSimpleName());
265 }
266 }
267
268 static class NodeCreationStackTrace extends NodeStackTrace {
269 }
270
271 public static class NodeInsertionStackTrace extends NodeStackTrace {
272 }
273
274 public Node(NodeClass<? extends Node> c) {
275 init(c);
276 }
277
278 final void init(NodeClass<? extends Node> c) {
279 assert c.getJavaClass() == this.getClass();
280 this.nodeClass = c;
281 id = INITIAL_ID;
282 extraUsages = NO_NODES;
283 if (TRACK_CREATION_POSITION) {
284 setCreationPosition(new NodeCreationStackTrace());
285 }
286 }
287
288 final int id() {
289 return id;
290 }
291
292 @Override
293 public Node asNode() {
294 return this;
295 }
296
297 /**
298 * Gets the graph context of this node.
299 */
300 public Graph graph() {
301 return graph;
302 }
303
304 /**
305 * Gets the option values associated with this node's graph.
306 */
307 public final OptionValues getOptions() {
308 return graph == null ? null : graph.getOptions();
309 }
310
311 /**
312 * Gets the debug context associated with this node's graph.
313 */
314 public final DebugContext getDebug() {
315 return graph.getDebug();
316 }
317
318 /**
319 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input
320 * edges of this node.
321 *
322 * @return an {@link NodeIterable iterable} for all non-null input edges.
323 */
324 public NodeIterable<Node> inputs() {
325 return nodeClass.getInputIterable(this);
326 }
327
328 /**
329 * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges
330 * of this node.
331 *
332 * @return an {@link Iterable iterable} for all non-null input edges.
333 */
334 public Iterable<Position> inputPositions() {
335 return nodeClass.getInputEdges().getPositionsIterable(this);
336 }
337
338 public abstract static class EdgeVisitor {
339
340 public abstract Node apply(Node source, Node target);
341
342 }
343
344 /**
345 * Applies the given visitor to all inputs of this node.
346 *
347 * @param visitor the visitor to be applied to the inputs
348 */
349 public void applyInputs(EdgeVisitor visitor) {
350 nodeClass.applyInputs(this, visitor);
351 }
352
353 /**
354 * Applies the given visitor to all successors of this node.
355 *
356 * @param visitor the visitor to be applied to the successors
357 */
358 public void applySuccessors(EdgeVisitor visitor) {
359 nodeClass.applySuccessors(this, visitor);
360 }
361
362 /**
363 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null successor
364 * edges of this node.
365 *
366 * @return an {@link NodeIterable iterable} for all non-null successor edges.
367 */
368 public NodeIterable<Node> successors() {
369 assert !this.isDeleted() : this;
370 return nodeClass.getSuccessorIterable(this);
371 }
372
373 /**
374 * Returns an {@link Iterable iterable} which can be used to traverse all successor edge
375 * positions of this node.
376 *
377 * @return an {@link Iterable iterable} for all successor edge positoins.
378 */
379 public Iterable<Position> successorPositions() {
380 return nodeClass.getSuccessorEdges().getPositionsIterable(this);
381 }
382
383 /**
384 * Gets the maximum number of usages this node has had at any point in time.
385 */
386 public int getUsageCount() {
387 if (usage0 == null) {
388 return 0;
389 }
390 if (usage1 == null) {
391 return 1;
392 }
393 return INLINE_USAGE_COUNT + extraUsagesCount;
394 }
395
396 /**
397 * Gets the list of nodes that use this node (i.e., as an input).
398 */
399 public final NodeIterable<Node> usages() {
400 return new NodeUsageIterable(this);
401 }
402
403 /**
404 * Checks whether this node has no usages.
405 */
406 public final boolean hasNoUsages() {
407 return this.usage0 == null;
408 }
409
410 /**
411 * Checks whether this node has usages.
412 */
413 public final boolean hasUsages() {
414 return this.usage0 != null;
415 }
416
417 /**
418 * Checks whether this node has more than one usages.
419 */
420 public final boolean hasMoreThanOneUsage() {
421 return this.usage1 != null;
422 }
423
424 /**
425 * Checks whether this node has exactly one usgae.
426 */
427 public final boolean hasExactlyOneUsage() {
428 return hasUsages() && !hasMoreThanOneUsage();
429 }
430
431 /**
432 * Adds a given node to this node's {@linkplain #usages() usages}.
433 *
434 * @param node the node to add
435 */
436 void addUsage(Node node) {
437 incUsageModCount();
438 if (usage0 == null) {
439 usage0 = node;
440 } else if (usage1 == null) {
441 usage1 = node;
442 } else {
443 int length = extraUsages.length;
444 if (length == 0) {
445 extraUsages = new Node[4];
446 } else if (extraUsagesCount == length) {
447 Node[] newExtraUsages = new Node[length * 2 + 1];
448 System.arraycopy(extraUsages, 0, newExtraUsages, 0, length);
449 extraUsages = newExtraUsages;
450 }
451 extraUsages[extraUsagesCount++] = node;
452 }
453 }
454
455 private void movUsageFromEndTo(int destIndex) {
456 if (destIndex >= INLINE_USAGE_COUNT) {
457 movUsageFromEndToExtraUsages(destIndex - INLINE_USAGE_COUNT);
458 } else if (destIndex == 1) {
459 movUsageFromEndToIndexOne();
460 } else {
461 assert destIndex == 0;
462 movUsageFromEndToIndexZero();
463 }
464 }
465
466 private void movUsageFromEndToExtraUsages(int destExtraIndex) {
467 this.extraUsagesCount--;
468 Node n = extraUsages[extraUsagesCount];
469 extraUsages[destExtraIndex] = n;
470 extraUsages[extraUsagesCount] = null;
471 }
472
473 private void movUsageFromEndToIndexZero() {
474 if (extraUsagesCount > 0) {
475 this.extraUsagesCount--;
476 usage0 = extraUsages[extraUsagesCount];
477 extraUsages[extraUsagesCount] = null;
478 } else if (usage1 != null) {
479 usage0 = usage1;
480 usage1 = null;
481 } else {
482 usage0 = null;
483 }
484 }
485
486 private void movUsageFromEndToIndexOne() {
487 if (extraUsagesCount > 0) {
488 this.extraUsagesCount--;
489 usage1 = extraUsages[extraUsagesCount];
490 extraUsages[extraUsagesCount] = null;
491 } else {
492 assert usage1 != null;
493 usage1 = null;
494 }
495 }
496
497 /**
498 * Removes a given node from this node's {@linkplain #usages() usages}.
499 *
500 * @param node the node to remove
501 * @return whether or not {@code usage} was in the usage list
502 */
503 public boolean removeUsage(Node node) {
504 assert node != null;
505 // For large graphs, usage removal is performance critical.
506 // Furthermore, it is critical that this method maintains the invariant that the usage list
507 // has no null element preceding a non-null element.
508 incUsageModCount();
509 if (usage0 == node) {
510 movUsageFromEndToIndexZero();
511 return true;
512 }
513 if (usage1 == node) {
514 movUsageFromEndToIndexOne();
515 return true;
516 }
517 for (int i = this.extraUsagesCount - 1; i >= 0; i--) {
518 if (extraUsages[i] == node) {
519 movUsageFromEndToExtraUsages(i);
520 return true;
521 }
522 }
523 return false;
524 }
525
526 public final Node predecessor() {
527 return predecessor;
528 }
529
530 public final int modCount() {
531 if (isModificationCountsEnabled() && graph != null) {
532 return graph.modCount(this);
533 }
534 return 0;
535 }
536
537 final void incModCount() {
538 if (isModificationCountsEnabled() && graph != null) {
539 graph.incModCount(this);
540 }
541 }
542
543 final int usageModCount() {
544 if (isModificationCountsEnabled() && graph != null) {
545 return graph.usageModCount(this);
546 }
547 return 0;
548 }
549
550 final void incUsageModCount() {
551 if (isModificationCountsEnabled() && graph != null) {
552 graph.incUsageModCount(this);
553 }
554 }
555
556 public final boolean isDeleted() {
557 return id <= DELETED_ID_START;
558 }
559
560 public final boolean isAlive() {
561 return id >= ALIVE_ID_START;
562 }
563
564 public final boolean isUnregistered() {
565 return id == INITIAL_ID;
566 }
567
568 /**
569 * Updates the usages sets of the given nodes after an input slot is changed from
570 * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and
571 * adds this node to {@code newInput}'s usages.
572 */
573 protected void updateUsages(Node oldInput, Node newInput) {
574 assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput;
575 if (oldInput != newInput) {
576 if (oldInput != null) {
577 boolean result = removeThisFromUsages(oldInput);
578 assert assertTrue(result, "not found in usages, old input: %s", oldInput);
579 }
580 maybeNotifyInputChanged(this);
581 if (newInput != null) {
582 newInput.addUsage(this);
583 }
584 if (oldInput != null && oldInput.hasNoUsages()) {
585 maybeNotifyZeroUsages(oldInput);
586 }
587 }
588 }
589
590 protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) {
591 updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode());
592 }
593
594 /**
595 * Updates the predecessor of the given nodes after a successor slot is changed from
596 * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds
597 * this node to newSuccessor's predecessors.
598 */
599 protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) {
600 assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) || newSuccessor == null && !isAlive() : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor;
601 assert graph == null || !graph.isFrozen();
602 if (oldSuccessor != newSuccessor) {
603 if (oldSuccessor != null) {
604 assert assertTrue(newSuccessor == null || oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this);
605 oldSuccessor.predecessor = null;
606 }
607 if (newSuccessor != null) {
608 assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this);
609 newSuccessor.predecessor = this;
610 }
611 }
612 }
613
614 void initialize(Graph newGraph) {
615 assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id);
616 this.graph = newGraph;
617 newGraph.register(this);
618 NodeClass<? extends Node> nc = nodeClass;
619 nc.registerAtInputsAsUsage(this);
620 nc.registerAtSuccessorsAsPredecessor(this);
621 }
622
623 /**
624 * Information associated with this node. A single value is stored directly in the field.
625 * Multiple values are stored by creating an Object[].
626 */
627 private Object annotation;
628
629 private <T> T getNodeInfo(Class<T> clazz) {
630 assert clazz != Object[].class;
631 if (annotation == null) {
632 return null;
633 }
634 if (clazz.isInstance(annotation)) {
635 return clazz.cast(annotation);
636 }
637 if (annotation.getClass() == Object[].class) {
638 Object[] annotations = (Object[]) annotation;
639 for (Object ann : annotations) {
640 if (clazz.isInstance(ann)) {
641 return clazz.cast(ann);
642 }
643 }
644 }
645 return null;
646 }
647
648 private <T> void setNodeInfo(Class<T> clazz, T value) {
649 assert clazz != Object[].class;
650 if (annotation == null || clazz.isInstance(annotation)) {
651 // Replace the current value
652 this.annotation = value;
653 } else if (annotation.getClass() == Object[].class) {
654 Object[] annotations = (Object[]) annotation;
655 for (int i = 0; i < annotations.length; i++) {
656 if (clazz.isInstance(annotations[i])) {
657 annotations[i] = value;
658 return;
659 }
660 }
661 Object[] newAnnotations = Arrays.copyOf(annotations, annotations.length + 1);
662 newAnnotations[annotations.length] = value;
663 this.annotation = newAnnotations;
664 } else {
665 this.annotation = new Object[]{this.annotation, value};
666 }
667 }
668
669 /**
670 * Gets the source position information for this node or null if it doesn't exist.
671 */
672
673 public NodeSourcePosition getNodeSourcePosition() {
674 return getNodeInfo(NodeSourcePosition.class);
675 }
676
677 /**
678 * Set the source position to {@code sourcePosition}. Setting it to null is ignored so that it's
679 * not accidentally cleared. Use {@link #clearNodeSourcePosition()} instead.
680 */
681 public void setNodeSourcePosition(NodeSourcePosition sourcePosition) {
682 if (sourcePosition == null) {
683 return;
684 }
685 setNodeInfo(NodeSourcePosition.class, sourcePosition);
686 }
687
688 public void clearNodeSourcePosition() {
689 setNodeInfo(NodeSourcePosition.class, null);
690 }
691
692 public NodeCreationStackTrace getCreationPosition() {
693 return getNodeInfo(NodeCreationStackTrace.class);
694 }
695
696 public void setCreationPosition(NodeCreationStackTrace trace) {
697 setNodeInfo(NodeCreationStackTrace.class, trace);
698 }
699
700 public NodeInsertionStackTrace getInsertionPosition() {
701 return getNodeInfo(NodeInsertionStackTrace.class);
702 }
703
704 public void setInsertionPosition(NodeInsertionStackTrace trace) {
705 setNodeInfo(NodeInsertionStackTrace.class, trace);
706 }
707
708 /**
709 * Update the source position only if it is null.
710 */
711 public void updateNodeSourcePosition(Supplier<NodeSourcePosition> sourcePositionSupp) {
712 if (this.getNodeSourcePosition() == null) {
713 setNodeSourcePosition(sourcePositionSupp.get());
714 }
715 }
716
717 public DebugCloseable withNodeSourcePosition() {
718 return graph.withNodeSourcePosition(this);
719 }
720
721 public final NodeClass<? extends Node> getNodeClass() {
722 return nodeClass;
723 }
724
725 public boolean isAllowedUsageType(InputType type) {
726 if (type == InputType.Value) {
727 return false;
728 }
729 return getNodeClass().getAllowedUsageTypes().contains(type);
730 }
731
732 private boolean checkReplaceWith(Node other) {
733 if (graph != null && graph.isFrozen()) {
734 fail("cannot modify frozen graph");
735 }
736 if (other == this) {
737 fail("cannot replace a node with itself");
738 }
739 if (isDeleted()) {
740 fail("cannot replace deleted node");
741 }
742 if (other != null && other.isDeleted()) {
743 fail("cannot replace with deleted node %s", other);
744 }
745 return true;
746 }
747
748 public final void replaceAtUsages(Node other) {
749 replaceAtAllUsages(other, (Node) null);
750 }
751
752 public final void replaceAtUsages(Node other, Predicate<Node> filter) {
753 replaceAtUsages(other, filter, null);
754 }
755
756 public final void replaceAtUsagesAndDelete(Node other) {
757 replaceAtUsages(other, null, this);
758 safeDelete();
759 }
760
761 public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) {
762 replaceAtUsages(other, filter, this);
763 safeDelete();
764 }
765
766 protected void replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted) {
767 if (filter == null) {
768 replaceAtAllUsages(other, toBeDeleted);
769 } else {
770 replaceAtMatchingUsages(other, filter, toBeDeleted);
771 }
772 }
773
774 protected void replaceAtAllUsages(Node other, Node toBeDeleted) {
775 checkReplaceWith(other);
776 if (usage0 == null) {
777 return;
778 }
779 replaceAtUsage(other, toBeDeleted, usage0);
780 usage0 = null;
781
782 if (usage1 == null) {
783 return;
784 }
785 replaceAtUsage(other, toBeDeleted, usage1);
786 usage1 = null;
787
788 if (extraUsagesCount <= 0) {
789 return;
790 }
791 for (int i = 0; i < extraUsagesCount; i++) {
792 Node usage = extraUsages[i];
793 replaceAtUsage(other, toBeDeleted, usage);
794 }
795 this.extraUsages = NO_NODES;
796 this.extraUsagesCount = 0;
797 }
798
799 private void replaceAtUsage(Node other, Node toBeDeleted, Node usage) {
800 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other);
801 assert assertTrue(result, "not found in inputs, usage: %s", usage);
802 /*
803 * Don't notify for nodes which are about to be deleted.
804 */
805 if (toBeDeleted == null || usage != toBeDeleted) {
806 maybeNotifyInputChanged(usage);
807 }
808 if (other != null) {
809 other.addUsage(usage);
810 }
811 }
812
813 private void replaceAtMatchingUsages(Node other, Predicate<Node> filter, Node toBeDeleted) {
814 if (filter == null) {
815 fail("filter cannot be null");
816 }
817 checkReplaceWith(other);
818 int i = 0;
819 while (i < this.getUsageCount()) {
820 Node usage = this.getUsageAt(i);
821 if (filter.test(usage)) {
822 replaceAtUsage(other, toBeDeleted, usage);
823 this.movUsageFromEndTo(i);
824 } else {
825 ++i;
826 }
827 }
828 }
829
830 public Node getUsageAt(int index) {
831 if (index == 0) {
832 return this.usage0;
833 } else if (index == 1) {
834 return this.usage1;
835 } else {
836 return this.extraUsages[index - INLINE_USAGE_COUNT];
837 }
838 }
839
840 public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) {
841 checkReplaceWith(other);
842 replaceAtMatchingUsages(other, usagePredicate, null);
843 }
844
845 public void replaceAtUsages(InputType type, Node other) {
846 checkReplaceWith(other);
847 for (Node usage : usages().snapshot()) {
848 for (Position pos : usage.inputPositions()) {
849 if (pos.getInputType() == type && pos.get(usage) == this) {
850 pos.set(usage, other);
851 }
852 }
853 }
854 }
855
856 private void maybeNotifyInputChanged(Node node) {
857 if (graph != null) {
858 assert !graph.isFrozen();
859 NodeEventListener listener = graph.nodeEventListener;
860 if (listener != null) {
861 listener.event(Graph.NodeEvent.INPUT_CHANGED, node);
862 }
863 }
864 }
865
866 public void maybeNotifyZeroUsages(Node node) {
867 if (graph != null) {
868 assert !graph.isFrozen();
869 NodeEventListener listener = graph.nodeEventListener;
870 if (listener != null && node.isAlive()) {
871 listener.event(Graph.NodeEvent.ZERO_USAGES, node);
872 }
873 }
874 }
875
876 public void replaceAtPredecessor(Node other) {
877 checkReplaceWith(other);
878 if (predecessor != null) {
879 if (!predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other)) {
880 fail("not found in successors, predecessor: %s", predecessor);
881 }
882 predecessor.updatePredecessor(this, other);
883 }
884 }
885
886 public void replaceAndDelete(Node other) {
887 checkReplaceWith(other);
888 if (other == null) {
889 fail("cannot replace with null");
890 }
891 if (this.hasUsages()) {
892 replaceAtUsages(other);
893 }
894 replaceAtPredecessor(other);
895 this.safeDelete();
896 }
897
898 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) {
899 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) {
900 updatePredecessor(oldSuccessor, newSuccessor);
901 }
902 }
903
904 public void replaceFirstInput(Node oldInput, Node newInput) {
905 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) {
906 updateUsages(oldInput, newInput);
907 }
908 }
909
910 public void clearInputs() {
911 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
912 getNodeClass().unregisterAtInputsAsUsage(this);
913 }
914
915 boolean removeThisFromUsages(Node n) {
916 return n.removeUsage(this);
917 }
918
919 public void clearSuccessors() {
920 assert assertFalse(isDeleted(), "cannot clear successors of deleted node");
921 getNodeClass().unregisterAtSuccessorsAsPredecessor(this);
922 }
923
924 private boolean checkDeletion() {
925 assertTrue(isAlive(), "must be alive");
926 assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages());
927 assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor);
928 return true;
929 }
930
931 /**
932 * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages}
933 * and no {@linkplain #predecessor() predecessor}.
934 */
935 public void safeDelete() {
936 assert checkDeletion();
937 this.clearInputs();
938 this.clearSuccessors();
939 markDeleted();
940 }
941
942 public void markDeleted() {
943 graph.unregister(this);
944 id = DELETED_ID_START - id;
945 assert isDeleted();
946 }
947
948 public final Node copyWithInputs() {
949 return copyWithInputs(true);
950 }
951
952 public final Node copyWithInputs(boolean insertIntoGraph) {
953 Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges);
954 if (insertIntoGraph) {
955 for (Node input : inputs()) {
956 input.addUsage(newNode);
957 }
958 }
959 return newNode;
960 }
961
962 /**
963 * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in
964 * {@link Node} exists to obviate the need to cast a node before invoking
965 * {@link Simplifiable#simplify(SimplifierTool)}.
966 *
967 * @param tool
968 */
969 public void simplify(SimplifierTool tool) {
970 throw new UnsupportedOperationException();
971 }
972
973 /**
974 * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw
975 * allocating} a copy of this node
976 * @param type the type of edges to process
977 * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are
978 * cleared
979 */
980 private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) {
981 if (edgesToCopy.contains(type)) {
982 getNodeClass().getEdges(type).copy(this, newNode);
983 } else {
984 // The direct edges are already null
985 getNodeClass().getEdges(type).initializeLists(newNode, this);
986 }
987 }
988
989 public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class);
990 public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class);
991 public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs);
992 public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors);
993
994 /**
995 * Makes a copy of this node in(to) a given graph.
996 *
997 * @param into the graph in which the copy will be registered (which may be this node's graph)
998 * or null if the copy should not be registered in a graph
999 * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are
1000 * initialized to their default value (i.e., {@code null} for a direct edge, an empty
1001 * list for an edge list)
1002 * @return the copy of this node
1003 */
1004 final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) {
1005 final NodeClass<? extends Node> nodeClassTmp = getNodeClass();
1006 boolean useIntoLeafNodeCache = false;
1007 if (into != null) {
1008 if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) {
1009 useIntoLeafNodeCache = true;
1010 Node otherNode = into.findNodeInCache(this);
1011 if (otherNode != null) {
1012 return otherNode;
1013 }
1014 }
1015 }
1016
1017 Node newNode = null;
1018 try {
1019 newNode = (Node) UNSAFE.allocateInstance(getClass());
1020 newNode.nodeClass = nodeClassTmp;
1021 nodeClassTmp.getData().copy(this, newNode);
1022 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
1023 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
1024 } catch (Exception e) {
1025 throw new GraalGraphError(e).addContext(this);
1026 }
1027 newNode.graph = into;
1028 newNode.id = INITIAL_ID;
1029 if (getNodeSourcePosition() != null && (into == null || into.trackNodeSourcePosition())) {
1030 newNode.setNodeSourcePosition(getNodeSourcePosition());
1031 }
1032 if (into != null) {
1033 into.register(newNode);
1034 }
1035 newNode.extraUsages = NO_NODES;
1036
1037 if (into != null && useIntoLeafNodeCache) {
1038 into.putNodeIntoCache(newNode);
1039 }
1040 newNode.afterClone(this);
1041 return newNode;
1042 }
1043
1044 protected void afterClone(@SuppressWarnings("unused") Node other) {
1045 }
1046
1047 protected boolean verifyInputs() {
1048 for (Position pos : inputPositions()) {
1049 Node input = pos.get(this);
1050 if (input == null) {
1051 assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this);
1052 } else {
1053 assertFalse(input.isDeleted(), "input was deleted %s", input);
1054 assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph");
1055 assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType());
1056 }
1057 }
1058 return true;
1059 }
1060
1061 public boolean verify() {
1062 assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id);
1063 assertTrue(graph() != null, "null graph");
1064 verifyInputs();
1065 if (Options.VerifyGraalGraphEdges.getValue(getOptions())) {
1066 verifyEdges();
1067 }
1068 return true;
1069 }
1070
1071 public boolean verifySourcePosition() {
1072 return true;
1073 }
1074
1075 /**
1076 * Perform expensive verification of inputs, usages, predecessors and successors.
1077 *
1078 * @return true
1079 */
1080 public boolean verifyEdges() {
1081 for (Node input : inputs()) {
1082 assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input);
1083 }
1084
1085 for (Node successor : successors()) {
1086 assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor());
1087 assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor);
1088 }
1089 for (Node usage : usages()) {
1090 assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage);
1091 assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage);
1092 boolean foundThis = false;
1093 for (Position pos : usage.inputPositions()) {
1094 if (pos.get(usage) == this) {
1095 foundThis = true;
1096 if (pos.getInputType() != InputType.Unchecked) {
1097 assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type %s from %s to %s (%s)", pos.getInputType(), usage, this, pos.getName());
1098 }
1099 }
1100 }
1101 assertTrue(foundThis, "missing input in usage %s", usage);
1102 }
1103
1104 if (predecessor != null) {
1105 assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor);
1106 assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor);
1107 }
1108 return true;
1109 }
1110
1111 public boolean assertTrue(boolean condition, String message, Object... args) {
1112 if (condition) {
1113 return true;
1114 } else {
1115 throw fail(message, args);
1116 }
1117 }
1118
1119 public boolean assertFalse(boolean condition, String message, Object... args) {
1120 if (condition) {
1121 throw fail(message, args);
1122 } else {
1123 return true;
1124 }
1125 }
1126
1127 protected VerificationError fail(String message, Object... args) throws GraalGraphError {
1128 throw new VerificationError(message, args).addContext(this);
1129 }
1130
1131 public Iterable<? extends Node> cfgPredecessors() {
1132 if (predecessor == null) {
1133 return Collections.emptySet();
1134 } else {
1135 return Collections.singleton(predecessor);
1136 }
1137 }
1138
1139 /**
1140 * Returns an iterator that will provide all control-flow successors of this node. Normally this
1141 * will be the contents of all fields annotated with {@link Successor}, but some node classes
1142 * (like EndNode) may return different nodes.
1143 */
1144 public Iterable<? extends Node> cfgSuccessors() {
1145 return successors();
1146 }
1147
1148 /**
1149 * Nodes using their {@link #id} as the hash code. This works very well when nodes of the same
1150 * graph are stored in sets. It can give bad behavior when storing nodes of different graphs in
1151 * the same set.
1152 */
1153 @Override
1154 public final int hashCode() {
1155 assert !this.isUnregistered() : "node not yet constructed";
1156 if (this.isDeleted()) {
1157 return -id + DELETED_ID_START;
1158 }
1159 return id;
1160 }
1161
1162 /**
1163 * Do not overwrite the equality test of a node in subclasses. Equality tests must rely solely
1164 * on identity.
1165 */
1166
1167 /**
1168 * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the
1169 * ideal graph visualizer).
1170 */
1171 public final Map<Object, Object> getDebugProperties() {
1172 return getDebugProperties(new HashMap<>());
1173 }
1174
1175 /**
1176 * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the
1177 * ideal graph visualizer). Subclasses overriding this method should also fill the map using
1178 * their superclass.
1179 *
1180 * @param map
1181 */
1182 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
1183 Fields properties = getNodeClass().getData();
1184 for (int i = 0; i < properties.getCount(); i++) {
1185 map.put(properties.getName(i), properties.get(this, i));
1186 }
1187 NodeSourcePosition pos = getNodeSourcePosition();
1188 if (pos != null) {
1189 map.put("nodeSourcePosition", pos);
1190 }
1191 NodeCreationStackTrace creation = getCreationPosition();
1192 if (creation != null) {
1193 map.put("nodeCreationPosition", creation.getStrackTraceString());
1194 }
1195 NodeInsertionStackTrace insertion = getInsertionPosition();
1196 if (insertion != null) {
1197 map.put("nodeInsertionPosition", insertion.getStrackTraceString());
1198 }
1199 return map;
1200 }
1201
1202 /**
1203 * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}.
1204 */
1205 @Override
1206 public final String toString() {
1207 return toString(Verbosity.Short);
1208 }
1209
1210 /**
1211 * Creates a String representation for this node with a given {@link Verbosity}.
1212 */
1213 public String toString(Verbosity verbosity) {
1214 switch (verbosity) {
1215 case Id:
1216 return Integer.toString(id);
1217 case Name:
1218 return getNodeClass().shortName();
1219 case Short:
1220 return toString(Verbosity.Id) + "|" + toString(Verbosity.Name);
1221 case Long:
1222 return toString(Verbosity.Short);
1223 case Debugger:
1224 case All: {
1225 StringBuilder str = new StringBuilder();
1226 str.append(toString(Verbosity.Short)).append(" { ");
1227 for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) {
1228 str.append(entry.getKey()).append("=").append(entry.getValue()).append(", ");
1229 }
1230 str.append(" }");
1231 return str.toString();
1232 }
1233 default:
1234 throw new RuntimeException("unknown verbosity: " + verbosity);
1235 }
1236 }
1237
1238 @Deprecated
1239 public int getId() {
1240 return id;
1241 }
1242
1243 @Override
1244 public void formatTo(Formatter formatter, int flags, int width, int precision) {
1245 if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) {
1246 formatter.format("%s", toString(Verbosity.Id));
1247 } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) {
1248 // Use All here since Long is only slightly longer than Short.
1249 formatter.format("%s", toString(Verbosity.All));
1250 } else {
1251 formatter.format("%s", toString(Verbosity.Short));
1252 }
1253
1254 boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY);
1255 int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0);
1256 if (width > 0) {
1257 if (this.predecessor != null) {
1258 formatter.format(" pred={");
1259 this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0);
1260 formatter.format("}");
1261 }
1262
1263 for (Position position : this.inputPositions()) {
1264 Node input = position.get(this);
1265 if (input != null) {
1266 formatter.format(" ");
1267 formatter.format(position.getName());
1268 formatter.format("={");
1269 input.formatTo(formatter, neighborsFlags, width - 1, 0);
1270 formatter.format("}");
1271 }
1272 }
1273 }
1274
1275 if (precision > 0) {
1276 if (!hasNoUsages()) {
1277 formatter.format(" usages={");
1278 int z = 0;
1279 for (Node usage : usages()) {
1280 if (z != 0) {
1281 formatter.format(", ");
1282 }
1283 usage.formatTo(formatter, neighborsFlags, 0, precision - 1);
1284 ++z;
1285 }
1286 formatter.format("}");
1287 }
1288
1289 for (Position position : this.successorPositions()) {
1290 Node successor = position.get(this);
1291 if (successor != null) {
1292 formatter.format(" ");
1293 formatter.format(position.getName());
1294 formatter.format("={");
1295 successor.formatTo(formatter, neighborsFlags, 0, precision - 1);
1296 formatter.format("}");
1297 }
1298 }
1299 }
1300 }
1301
1302 /**
1303 * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data
1304 * fields of another node of the same type. Primitive fields are compared by value and
1305 * non-primitive fields are compared by {@link Objects#equals(Object, Object)}.
1306 *
1307 * The result of this method undefined if {@code other.getClass() != this.getClass()}.
1308 *
1309 * @param other a node of exactly the same type as this node
1310 * @return true if the data fields of this object and {@code other} are equal
1311 */
1312 public boolean valueEquals(Node other) {
1313 return getNodeClass().dataEquals(this, other);
1314 }
1315
1316 /**
1317 * Determines if this node is equal to the other node while ignoring differences in
1318 * {@linkplain Successor control-flow} edges.
1319 *
1320 */
1321 public boolean dataFlowEquals(Node other) {
1322 return this == other || nodeClass == other.getNodeClass() && this.valueEquals(other) && nodeClass.equalInputs(this, other);
1323 }
1324
1325 public final void pushInputs(NodeStack stack) {
1326 getNodeClass().pushInputs(this, stack);
1327 }
1328
1329 public NodeSize estimatedNodeSize() {
1330 return nodeClass.size();
1331 }
1332
1333 public NodeCycles estimatedNodeCycles() {
1334 return nodeClass.cycles();
1335 }
1336
1337 }