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