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 {
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 * If {@code true} then this is lowered into a node that has side effects.
198 */
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
248 NodeStackTrace() {
249 this.stackTrace = new Throwable().getStackTrace();
250 }
251
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
263 String getStrackTraceString() {
264 return getString(null);
265 }
266
267 @Override
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
279 public Node(NodeClass<? extends Node> c) {
280 init(c);
281 }
282
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
293 final int id() {
294 return id;
295 }
296
297 @Override
298 public Node asNode() {
299 return this;
300 }
301
302 /**
303 * Gets the graph context of this node.
304 */
305 public Graph graph() {
306 return graph;
307 }
308
309 /**
310 * Gets the option values associated with this node's graph.
311 */
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 */
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 */
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 */
339 public Iterable<Position> inputPositions() {
340 return nodeClass.getInputEdges().getPositionsIterable(this);
341 }
342
343 public abstract static class EdgeVisitor {
344
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 */
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 */
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 */
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 */
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 */
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 */
404 public final NodeIterable<Node> usages() {
405 return new NodeUsageIterable(this);
406 }
407
408 /**
409 * Checks whether this node has no usages.
410 */
411 public final boolean hasNoUsages() {
412 return this.usage0 == null;
413 }
414
415 /**
416 * Checks whether this node has usages.
417 */
418 public final boolean hasUsages() {
419 return this.usage0 != null;
420 }
421
422 /**
423 * Checks whether this node has more than one usages.
424 */
425 public final boolean hasMoreThanOneUsage() {
426 return this.usage1 != null;
427 }
428
429 /**
430 * Checks whether this node has exactly one usgae.
431 */
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 */
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
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
471 private void movUsageFromEndToExtraUsages(int destExtraIndex) {
472 this.extraUsagesCount--;
473 Node n = extraUsages[extraUsagesCount];
474 extraUsages[destExtraIndex] = n;
475 extraUsages[extraUsagesCount] = null;
476 }
477
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
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 */
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
531 public final Node predecessor() {
532 return predecessor;
533 }
534
535 public final int modCount() {
536 if (isModificationCountsEnabled() && graph != null) {
537 return graph.modCount(this);
538 }
539 return 0;
540 }
541
542 final void incModCount() {
543 if (isModificationCountsEnabled() && graph != null) {
544 graph.incModCount(this);
545 }
546 }
547
548 final int usageModCount() {
549 if (isModificationCountsEnabled() && graph != null) {
550 return graph.usageModCount(this);
551 }
552 return 0;
553 }
554
555 final void incUsageModCount() {
556 if (isModificationCountsEnabled() && graph != null) {
557 graph.incUsageModCount(this);
558 }
559 }
560
561 public final boolean isDeleted() {
562 return id <= DELETED_ID_START;
563 }
564
565 public final boolean isAlive() {
566 return id >= ALIVE_ID_START;
567 }
568
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 */
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
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 */
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
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
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
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
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 */
687 public void setNodeSourcePosition(NodeSourcePosition sourcePosition) {
688 if (sourcePosition == null) {
689 return;
690 }
691 setNodeInfo(NodeSourcePosition.class, sourcePosition);
692 }
693
694 public void clearNodeSourcePosition() {
695 setNodeInfo(NodeSourcePosition.class, null);
696 }
697
698 public NodeCreationStackTrace getCreationPosition() {
699 return getNodeInfo(NodeCreationStackTrace.class);
700 }
701
702 public void setCreationPosition(NodeCreationStackTrace trace) {
703 setNodeInfo(NodeCreationStackTrace.class, trace);
704 }
705
706 public NodeInsertionStackTrace getInsertionPosition() {
707 return getNodeInfo(NodeInsertionStackTrace.class);
708 }
709
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 */
717 public void updateNodeSourcePosition(Supplier<NodeSourcePosition> sourcePositionSupp) {
718 if (this.getNodeSourcePosition() == null) {
719 setNodeSourcePosition(sourcePositionSupp.get());
720 }
721 }
722
723 public DebugCloseable withNodeSourcePosition() {
724 return graph.withNodeSourcePosition(this);
725 }
726
727 public final NodeClass<? extends Node> getNodeClass() {
728 return nodeClass;
729 }
730
731 public boolean isAllowedUsageType(InputType type) {
732 if (type == InputType.Value) {
733 return false;
734 }
735 return getNodeClass().getAllowedUsageTypes().contains(type);
736 }
737
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
754 public final void replaceAtUsages(Node other) {
755 replaceAtAllUsages(other, (Node) null);
756 }
757
758 public final void replaceAtUsages(Node other, Predicate<Node> filter) {
759 replaceAtUsages(other, filter, null);
760 }
761
762 public final void replaceAtUsagesAndDelete(Node other) {
763 replaceAtUsages(other, null, this);
764 safeDelete();
765 }
766
767 public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) {
768 replaceAtUsages(other, filter, this);
769 safeDelete();
770 }
771
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
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
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
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
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
848 public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) {
849 checkReplaceWith(other);
850 replaceAtMatchingUsages(other, usagePredicate, null);
851 }
852
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
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
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
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
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
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
927 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) {
928 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) {
929 updatePredecessor(oldSuccessor, newSuccessor);
930 }
931 }
932
933 public void replaceFirstInput(Node oldInput, Node newInput) {
934 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) {
935 updateUsages(oldInput, newInput);
936 }
937 }
938
939 public void replaceAllInputs(Node oldInput, Node newInput) {
940 while (nodeClass.replaceFirstInput(this, oldInput, newInput)) {
941 updateUsages(oldInput, newInput);
942 }
943 }
944
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
953 public void clearInputs() {
954 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
955 getNodeClass().unregisterAtInputsAsUsage(this);
956 }
957
958 boolean removeThisFromUsages(Node n) {
959 return n.removeUsage(this);
960 }
961
962 public void clearSuccessors() {
963 assert assertFalse(isDeleted(), "cannot clear successors of deleted node");
964 getNodeClass().unregisterAtSuccessorsAsPredecessor(this);
965 }
966
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 */
978 public void safeDelete() {
979 assert checkDeletion();
980 this.clearInputs();
981 this.clearSuccessors();
982 markDeleted();
983 }
984
985 public void markDeleted() {
986 graph.unregister(this);
987 id = DELETED_ID_START - id;
988 assert isDeleted();
989 }
990
991 public final Node copyWithInputs() {
992 return copyWithInputs(true);
993 }
994
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 */
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 */
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 */
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
1087 protected void afterClone(@SuppressWarnings("unused") Node other) {
1088 }
1089
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
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
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 */
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
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
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
1172 protected VerificationError fail(String message, Object... args) throws GraalGraphError {
1173 throw new VerificationError(message, args).addContext(this);
1174 }
1175
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 */
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
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 */
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 */
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
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 */
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
1284 public int getId() {
1285 return id;
1286 }
1287
1288 @Override
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 */
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 */
1366 public boolean dataFlowEquals(Node other) {
1367 return this == other || nodeClass == other.getNodeClass() && this.valueEquals(other) && nodeClass.equalInputs(this, other);
1368 }
1369
1370 public final void pushInputs(NodeStack stack) {
1371 getNodeClass().pushInputs(this, stack);
1372 }
1373
1374 public NodeSize estimatedNodeSize() {
1375 return nodeClass.size();
1376 }
1377
1378 public NodeCycles estimatedNodeCycles() {
1379 return nodeClass.cycles();
1380 }
1381
1382 }