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 package org.graalvm.compiler.graph;
24
25 import static org.graalvm.compiler.graph.Edges.Type.Inputs;
26 import static org.graalvm.compiler.graph.Edges.Type.Successors;
27 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
28 import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;
29
30 import java.lang.annotation.ElementType;
31 import java.lang.annotation.RetentionPolicy;
32 import java.util.Collection;
33 import java.util.Collections;
34 import java.util.EnumSet;
35 import java.util.Formattable;
36 import java.util.FormattableFlags;
37 import java.util.Formatter;
38 import java.util.HashMap;
39 import java.util.List;
40 import java.util.Map;
41 import java.util.Objects;
42 import java.util.Set;
43 import java.util.function.Predicate;
44
45 import org.graalvm.compiler.core.common.CollectionsFactory;
46 import org.graalvm.compiler.core.common.Fields;
47 import org.graalvm.compiler.debug.DebugCloseable;
48 import org.graalvm.compiler.debug.Fingerprint;
49 import org.graalvm.compiler.graph.Graph.NodeEvent;
50 import org.graalvm.compiler.graph.Graph.NodeEventListener;
51 import org.graalvm.compiler.graph.Graph.Options;
52 import org.graalvm.compiler.graph.iterators.NodeIterable;
53 import org.graalvm.compiler.graph.iterators.NodePredicate;
54 import org.graalvm.compiler.graph.spi.Simplifiable;
55 import org.graalvm.compiler.graph.spi.SimplifierTool;
56 import org.graalvm.compiler.nodeinfo.InputType;
57 import org.graalvm.compiler.nodeinfo.NodeInfo;
58 import org.graalvm.compiler.nodeinfo.Verbosity;
59
60 import sun.misc.Unsafe;
61
62 /**
63 * This class is the base class for all nodes. It represents a node that can be inserted in a
64 * {@link Graph}.
65 * <p>
66 * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the
67 * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and
68 * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either
69 * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node
70 * this field points to.
71 * <p>
72 * Nodes which are be value numberable should implement the {@link ValueNumberable} interface.
73 *
74 * <h1>Replay Compilation</h1>
75 *
76 * To enable deterministic replay compilation, node sets and node maps should be instantiated with
77 * the following methods:
78 * <ul>
79 * <li>{@link #newSet()}</li>
80 * <li>{@link #newSet(Collection)}</li>
81 * <li>{@link #newMap()}</li>
82 * <li>{@link #newMap(int)}</li>
83 * <li>{@link #newMap(Map)}</li>
84 * <li>{@link #newIdentityMap()}</li>
85 * <li>{@link #newIdentityMap(int)}</li>
86 * <li>{@link #newIdentityMap(Map)}</li>
87 * </ul>
88 *
89 * <h1>Assertions and Verification</h1>
90 *
91 * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and
92 * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean
93 * and throw a VerificationError if it has the wrong value. Both methods will always either throw an
94 * exception or return true. They can thus be used within an assert statement, so that the check is
95 * only performed if assertions are enabled.
96 */
97 @NodeInfo
98 public abstract class Node implements Cloneable, Formattable, NodeInterface {
99
100 public static final NodeClass<?> TYPE = null;
101 public static final boolean USE_UNSAFE_TO_CLONE = Graph.Options.CloneNodesWithUnsafe.getValue();
102
103 static final int DELETED_ID_START = -1000000000;
104 static final int INITIAL_ID = -1;
105 static final int ALIVE_ID_START = 0;
106
107 // The use of fully qualified class names here and in the rest
108 // of this file works around a problem javac has resolving symbols
109
110 /**
111 * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of
112 * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of
113 * type {@link Node} outside of their constructor should call
114 * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input.
115 */
116 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
117 @java.lang.annotation.Target(ElementType.FIELD)
118 public static @interface Input {
119 InputType value() default InputType.Value;
120 }
121
241 init(c);
242 }
243
244 final void init(NodeClass<? extends Node> c) {
245 assert c.getJavaClass() == this.getClass();
246 this.nodeClass = c;
247 id = INITIAL_ID;
248 extraUsages = NO_NODES;
249 }
250
251 final int id() {
252 return id;
253 }
254
255 @Override
256 public Node asNode() {
257 return this;
258 }
259
260 /**
261 * @see CollectionsFactory#newSet()
262 */
263 public static <E extends Node> Set<E> newSet() {
264 return CollectionsFactory.newSet();
265 }
266
267 /**
268 * @see #newSet()
269 */
270 public static <E extends Node> Set<E> newSet(Collection<? extends E> c) {
271 return CollectionsFactory.newSet(c);
272 }
273
274 public static <K extends Node, V> Map<K, V> newMap() {
275 // Node.equals() and Node.hashCode() are final and are implemented
276 // purely in terms of identity so HashMap and IdentityHashMap with
277 // Node's as keys will behave the same. We choose to use the latter
278 // due to its lighter memory footprint.
279 return newIdentityMap();
280 }
281
282 public static <K extends Node, V> Map<K, V> newMap(Map<K, V> m) {
283 // Node.equals() and Node.hashCode() are final and are implemented
284 // purely in terms of identity so HashMap and IdentityHashMap with
285 // Node's as keys will behave the same. We choose to use the latter
286 // due to its lighter memory footprint.
287 return newIdentityMap(m);
288 }
289
290 public static <K extends Node, V> Map<K, V> newMap(int expectedMaxSize) {
291 // Node.equals() and Node.hashCode() are final and are implemented
292 // purely in terms of identity so HashMap and IdentityHashMap with
293 // Node's as keys will behave the same. We choose to use the latter
294 // due to its lighter memory footprint.
295 return newIdentityMap(expectedMaxSize);
296 }
297
298 public static <K extends Node, V> Map<K, V> newIdentityMap() {
299 return CollectionsFactory.newIdentityMap();
300 }
301
302 public static <K extends Node, V> Map<K, V> newIdentityMap(Map<K, V> m) {
303 return CollectionsFactory.newIdentityMap(m);
304 }
305
306 public static <K extends Node, V> Map<K, V> newIdentityMap(int expectedMaxSize) {
307 return CollectionsFactory.newIdentityMap(expectedMaxSize);
308 }
309
310 /**
311 * Gets the graph context of this node.
312 */
313 public Graph graph() {
314 return graph;
315 }
316
317 /**
318 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input
319 * edges of this node.
320 *
321 * @return an {@link NodeIterable iterable} for all non-null input edges.
322 */
323 public NodeIterable<Node> inputs() {
324 return nodeClass.getInputIterable(this);
325 }
326
327 /**
328 * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges
329 * of this node.
330 *
331 * @return an {@link Iterable iterable} for all non-null input edges.
332 */
333 public Iterable<Position> inputPositions() {
334 return nodeClass.getInputEdges().getPositionsIterable(this);
396 * Gets the list of nodes that use this node (i.e., as an input).
397 */
398 public final NodeIterable<Node> usages() {
399 return new NodeUsageIterable(this);
400 }
401
402 /**
403 * Checks whether this node has no usages.
404 */
405 public final boolean hasNoUsages() {
406 return this.usage0 == null;
407 }
408
409 /**
410 * Checks whether this node has usages.
411 */
412 public final boolean hasUsages() {
413 return this.usage0 != null;
414 }
415
416 void reverseUsageOrder() {
417 List<Node> snapshot = this.usages().snapshot();
418 for (Node n : snapshot) {
419 this.removeUsage(n);
420 }
421 Collections.reverse(snapshot);
422 for (Node n : snapshot) {
423 this.addUsage(n);
424 }
425 }
426
427 /**
428 * Adds a given node to this node's {@linkplain #usages() usages}.
429 *
430 * @param node the node to add
431 */
432 void addUsage(Node node) {
433 incUsageModCount();
434 if (usage0 == null) {
435 usage0 = node;
436 } else if (usage1 == null) {
437 usage1 = node;
438 } else {
439 int length = extraUsages.length;
440 if (length == 0) {
441 extraUsages = new Node[4];
442 } else if (extraUsagesCount == length) {
443 Node[] newExtraUsages = new Node[length * 2 + 1];
444 System.arraycopy(extraUsages, 0, newExtraUsages, 0, length);
516
517 final void incModCount() {
518 if (isModificationCountsEnabled() && graph != null) {
519 graph.incModCount(this);
520 }
521 }
522
523 final int usageModCount() {
524 if (isModificationCountsEnabled() && graph != null) {
525 return graph.usageModCount(this);
526 }
527 return 0;
528 }
529
530 final void incUsageModCount() {
531 if (isModificationCountsEnabled() && graph != null) {
532 graph.incUsageModCount(this);
533 }
534 }
535
536 public boolean isDeleted() {
537 return id <= DELETED_ID_START;
538 }
539
540 public boolean isAlive() {
541 return id >= ALIVE_ID_START;
542 }
543
544 /**
545 * Updates the usages sets of the given nodes after an input slot is changed from
546 * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and
547 * adds this node to {@code newInput}'s usages.
548 */
549 protected void updateUsages(Node oldInput, Node newInput) {
550 assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput;
551 if (oldInput != newInput) {
552 if (oldInput != null) {
553 boolean result = removeThisFromUsages(oldInput);
554 assert assertTrue(result, "not found in usages, old input: %s", oldInput);
555 }
556 maybeNotifyInputChanged(this);
557 if (newInput != null) {
558 newInput.addUsage(this);
559 }
560 if (oldInput != null && oldInput.hasNoUsages()) {
561 maybeNotifyZeroUsages(oldInput);
562 }
563 }
744 listener.usagesDroppedToZero(node);
745 }
746 if (Fingerprint.ENABLED) {
747 Fingerprint.submit("%s: %s", NodeEvent.ZERO_USAGES, node);
748 }
749 }
750 }
751
752 public void replaceAtPredecessor(Node other) {
753 assert checkReplaceWith(other);
754 if (predecessor != null) {
755 boolean result = predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other);
756 assert assertTrue(result, "not found in successors, predecessor: %s", predecessor);
757 predecessor.updatePredecessor(this, other);
758 }
759 }
760
761 public void replaceAndDelete(Node other) {
762 assert checkReplaceWith(other);
763 assert other != null;
764 replaceAtUsages(other);
765 replaceAtPredecessor(other);
766 this.safeDelete();
767 }
768
769 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) {
770 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) {
771 updatePredecessor(oldSuccessor, newSuccessor);
772 }
773 }
774
775 public void replaceFirstInput(Node oldInput, Node newInput) {
776 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) {
777 updateUsages(oldInput, newInput);
778 }
779 }
780
781 public void clearInputs() {
782 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
783 getNodeClass().unregisterAtInputsAsUsage(this);
784 }
835 * {@link Node} exists to obviate the need to cast a node before invoking
836 * {@link Simplifiable#simplify(SimplifierTool)}.
837 *
838 * @param tool
839 */
840 public void simplify(SimplifierTool tool) {
841 throw new UnsupportedOperationException();
842 }
843
844 /**
845 * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw
846 * allocating} a copy of this node
847 * @param type the type of edges to process
848 * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are
849 * cleared
850 */
851 private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) {
852 if (edgesToCopy.contains(type)) {
853 getNodeClass().getEdges(type).copy(this, newNode);
854 } else {
855 if (USE_UNSAFE_TO_CLONE) {
856 // The direct edges are already null
857 getNodeClass().getEdges(type).initializeLists(newNode, this);
858 } else {
859 getNodeClass().getEdges(type).clear(newNode);
860 }
861 }
862 }
863
864 public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class);
865 public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class);
866 public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs);
867 public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors);
868
869 /**
870 * Makes a copy of this node in(to) a given graph.
871 *
872 * @param into the graph in which the copy will be registered (which may be this node's graph)
873 * or null if the copy should not be registered in a graph
874 * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are
875 * initialized to their default value (i.e., {@code null} for a direct edge, an empty
876 * list for an edge list)
877 * @return the copy of this node
878 */
879 final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) {
880 final NodeClass<? extends Node> nodeClassTmp = getNodeClass();
881 boolean useIntoLeafNodeCache = false;
882 if (into != null) {
883 if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) {
884 useIntoLeafNodeCache = true;
885 Node otherNode = into.findNodeInCache(this);
886 if (otherNode != null) {
887 return otherNode;
888 }
889 }
890 }
891
892 Node newNode = null;
893 try {
894 if (USE_UNSAFE_TO_CLONE) {
895 newNode = (Node) UNSAFE.allocateInstance(getClass());
896 newNode.nodeClass = nodeClassTmp;
897 nodeClassTmp.getData().copy(this, newNode);
898 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
899 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
900 } else {
901 newNode = (Node) this.clone();
902 newNode.typeCacheNext = null;
903 newNode.usage0 = null;
904 newNode.usage1 = null;
905 newNode.predecessor = null;
906 newNode.extraUsagesCount = 0;
907 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
908 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
909 }
910 } catch (Exception e) {
911 throw new GraalGraphError(e).addContext(this);
912 }
913 newNode.graph = into;
914 newNode.id = INITIAL_ID;
915 if (into != null) {
916 into.register(newNode);
917 }
918 newNode.extraUsages = NO_NODES;
919
920 if (into != null && useIntoLeafNodeCache) {
921 into.putNodeIntoCache(newNode);
922 }
923 if (graph != null && into != null && sourcePosition != null) {
924 newNode.setNodeSourcePosition(sourcePosition);
925 }
926 newNode.afterClone(this);
927 return newNode;
928 }
929
930 protected void afterClone(@SuppressWarnings("unused") Node other) {
931 }
932
933 protected boolean verifyInputs() {
934 for (Position pos : inputPositions()) {
935 Node input = pos.get(this);
936 if (input == null) {
937 assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this);
938 } else {
939 assertFalse(input.isDeleted(), "input was deleted");
940 assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph");
941 assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType());
942 }
943 }
944 return true;
945 }
946
947 public boolean verify() {
948 assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id);
949 assertTrue(graph() != null, "null graph");
950 verifyInputs();
951 if (Options.VerifyGraalGraphEdges.getValue()) {
952 verifyEdges();
953 }
954 return true;
955 }
956
957 /**
958 * Perform expensive verification of inputs, usages, predecessors and successors.
959 *
960 * @return true
961 */
962 public boolean verifyEdges() {
963 for (Node input : inputs()) {
964 assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input);
965 }
966
967 for (Node successor : successors()) {
968 assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor());
969 assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor);
970 }
971 for (Node usage : usages()) {
1011 }
1012
1013 public Iterable<? extends Node> cfgPredecessors() {
1014 if (predecessor == null) {
1015 return Collections.emptySet();
1016 } else {
1017 return Collections.singleton(predecessor);
1018 }
1019 }
1020
1021 /**
1022 * Returns an iterator that will provide all control-flow successors of this node. Normally this
1023 * will be the contents of all fields annotated with {@link Successor}, but some node classes
1024 * (like EndNode) may return different nodes.
1025 */
1026 public Iterable<? extends Node> cfgSuccessors() {
1027 return successors();
1028 }
1029
1030 /**
1031 * Nodes always use an {@linkplain System#identityHashCode(Object) identity} hash code.
1032 */
1033 @Override
1034 public final int hashCode() {
1035 return System.identityHashCode(this);
1036 }
1037
1038 /**
1039 * Equality tests must rely solely on identity.
1040 */
1041 @Override
1042 public final boolean equals(Object obj) {
1043 return super.equals(obj);
1044 }
1045
1046 /**
1047 * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the
1048 * ideal graph visualizer).
1049 */
1050 public final Map<Object, Object> getDebugProperties() {
1051 return getDebugProperties(new HashMap<>());
1052 }
1053
1054 /**
1055 * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the
1056 * ideal graph visualizer). Subclasses overriding this method should also fill the map using
1057 * their superclass.
1058 *
1059 * @param map
1060 */
1061 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
1062 Fields properties = getNodeClass().getData();
1063 for (int i = 0; i < properties.getCount(); i++) {
1064 map.put(properties.getName(i), properties.get(this, i));
|
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 package org.graalvm.compiler.graph;
24
25 import static org.graalvm.compiler.graph.Edges.Type.Inputs;
26 import static org.graalvm.compiler.graph.Edges.Type.Successors;
27 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
28 import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;
29
30 import java.lang.annotation.ElementType;
31 import java.lang.annotation.RetentionPolicy;
32 import java.util.Collections;
33 import java.util.EnumSet;
34 import java.util.Formattable;
35 import java.util.FormattableFlags;
36 import java.util.Formatter;
37 import java.util.HashMap;
38 import java.util.Map;
39 import java.util.Objects;
40 import java.util.function.Predicate;
41
42 import org.graalvm.compiler.core.common.Fields;
43 import org.graalvm.compiler.debug.DebugCloseable;
44 import org.graalvm.compiler.debug.Fingerprint;
45 import org.graalvm.compiler.graph.Graph.NodeEvent;
46 import org.graalvm.compiler.graph.Graph.NodeEventListener;
47 import org.graalvm.compiler.graph.Graph.Options;
48 import org.graalvm.compiler.graph.iterators.NodeIterable;
49 import org.graalvm.compiler.graph.iterators.NodePredicate;
50 import org.graalvm.compiler.graph.spi.Simplifiable;
51 import org.graalvm.compiler.graph.spi.SimplifierTool;
52 import org.graalvm.compiler.nodeinfo.InputType;
53 import org.graalvm.compiler.nodeinfo.NodeInfo;
54 import org.graalvm.compiler.nodeinfo.Verbosity;
55 import org.graalvm.compiler.options.OptionValues;
56
57 import sun.misc.Unsafe;
58
59 /**
60 * This class is the base class for all nodes. It represents a node that can be inserted in a
61 * {@link Graph}.
62 * <p>
63 * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the
64 * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and
65 * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either
66 * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node
67 * this field points to.
68 * <p>
69 * Nodes which are be value numberable should implement the {@link ValueNumberable} interface.
70 *
71 * <h1>Assertions and Verification</h1>
72 *
73 * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and
74 * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean
75 * and throw a VerificationError if it has the wrong value. Both methods will always either throw an
76 * exception or return true. They can thus be used within an assert statement, so that the check is
77 * only performed if assertions are enabled.
78 */
79 @NodeInfo
80 public abstract class Node implements Cloneable, Formattable, NodeInterface {
81
82 public static final NodeClass<?> TYPE = null;
83 public static final boolean USE_UNSAFE_TO_CLONE = true;
84
85 static final int DELETED_ID_START = -1000000000;
86 static final int INITIAL_ID = -1;
87 static final int ALIVE_ID_START = 0;
88
89 // The use of fully qualified class names here and in the rest
90 // of this file works around a problem javac has resolving symbols
91
92 /**
93 * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of
94 * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of
95 * type {@link Node} outside of their constructor should call
96 * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input.
97 */
98 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
99 @java.lang.annotation.Target(ElementType.FIELD)
100 public static @interface Input {
101 InputType value() default InputType.Value;
102 }
103
223 init(c);
224 }
225
226 final void init(NodeClass<? extends Node> c) {
227 assert c.getJavaClass() == this.getClass();
228 this.nodeClass = c;
229 id = INITIAL_ID;
230 extraUsages = NO_NODES;
231 }
232
233 final int id() {
234 return id;
235 }
236
237 @Override
238 public Node asNode() {
239 return this;
240 }
241
242 /**
243 * Gets the graph context of this node.
244 */
245 public Graph graph() {
246 return graph;
247 }
248
249 /**
250 * Gets the option values associated with this node's graph.
251 */
252 public final OptionValues getOptions() {
253 return graph == null ? null : graph.getOptions();
254 }
255
256 /**
257 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input
258 * edges of this node.
259 *
260 * @return an {@link NodeIterable iterable} for all non-null input edges.
261 */
262 public NodeIterable<Node> inputs() {
263 return nodeClass.getInputIterable(this);
264 }
265
266 /**
267 * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges
268 * of this node.
269 *
270 * @return an {@link Iterable iterable} for all non-null input edges.
271 */
272 public Iterable<Position> inputPositions() {
273 return nodeClass.getInputEdges().getPositionsIterable(this);
335 * Gets the list of nodes that use this node (i.e., as an input).
336 */
337 public final NodeIterable<Node> usages() {
338 return new NodeUsageIterable(this);
339 }
340
341 /**
342 * Checks whether this node has no usages.
343 */
344 public final boolean hasNoUsages() {
345 return this.usage0 == null;
346 }
347
348 /**
349 * Checks whether this node has usages.
350 */
351 public final boolean hasUsages() {
352 return this.usage0 != null;
353 }
354
355 /**
356 * Checks whether this node has more than one usages.
357 */
358 public final boolean hasMoreThanOneUsage() {
359 return this.usage1 != null;
360 }
361
362 /**
363 * Checks whether this node has exactly one usgae.
364 */
365 public final boolean hasExactlyOneUsage() {
366 return hasUsages() && !hasMoreThanOneUsage();
367 }
368
369 /**
370 * Adds a given node to this node's {@linkplain #usages() usages}.
371 *
372 * @param node the node to add
373 */
374 void addUsage(Node node) {
375 incUsageModCount();
376 if (usage0 == null) {
377 usage0 = node;
378 } else if (usage1 == null) {
379 usage1 = node;
380 } else {
381 int length = extraUsages.length;
382 if (length == 0) {
383 extraUsages = new Node[4];
384 } else if (extraUsagesCount == length) {
385 Node[] newExtraUsages = new Node[length * 2 + 1];
386 System.arraycopy(extraUsages, 0, newExtraUsages, 0, length);
458
459 final void incModCount() {
460 if (isModificationCountsEnabled() && graph != null) {
461 graph.incModCount(this);
462 }
463 }
464
465 final int usageModCount() {
466 if (isModificationCountsEnabled() && graph != null) {
467 return graph.usageModCount(this);
468 }
469 return 0;
470 }
471
472 final void incUsageModCount() {
473 if (isModificationCountsEnabled() && graph != null) {
474 graph.incUsageModCount(this);
475 }
476 }
477
478 public final boolean isDeleted() {
479 return id <= DELETED_ID_START;
480 }
481
482 public final boolean isAlive() {
483 return id >= ALIVE_ID_START;
484 }
485
486 public final boolean isUnregistered() {
487 return id == INITIAL_ID;
488 }
489
490 /**
491 * Updates the usages sets of the given nodes after an input slot is changed from
492 * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and
493 * adds this node to {@code newInput}'s usages.
494 */
495 protected void updateUsages(Node oldInput, Node newInput) {
496 assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput;
497 if (oldInput != newInput) {
498 if (oldInput != null) {
499 boolean result = removeThisFromUsages(oldInput);
500 assert assertTrue(result, "not found in usages, old input: %s", oldInput);
501 }
502 maybeNotifyInputChanged(this);
503 if (newInput != null) {
504 newInput.addUsage(this);
505 }
506 if (oldInput != null && oldInput.hasNoUsages()) {
507 maybeNotifyZeroUsages(oldInput);
508 }
509 }
690 listener.usagesDroppedToZero(node);
691 }
692 if (Fingerprint.ENABLED) {
693 Fingerprint.submit("%s: %s", NodeEvent.ZERO_USAGES, node);
694 }
695 }
696 }
697
698 public void replaceAtPredecessor(Node other) {
699 assert checkReplaceWith(other);
700 if (predecessor != null) {
701 boolean result = predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other);
702 assert assertTrue(result, "not found in successors, predecessor: %s", predecessor);
703 predecessor.updatePredecessor(this, other);
704 }
705 }
706
707 public void replaceAndDelete(Node other) {
708 assert checkReplaceWith(other);
709 assert other != null;
710 if (this.hasUsages()) {
711 replaceAtUsages(other);
712 }
713 replaceAtPredecessor(other);
714 this.safeDelete();
715 }
716
717 public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) {
718 if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) {
719 updatePredecessor(oldSuccessor, newSuccessor);
720 }
721 }
722
723 public void replaceFirstInput(Node oldInput, Node newInput) {
724 if (nodeClass.replaceFirstInput(this, oldInput, newInput)) {
725 updateUsages(oldInput, newInput);
726 }
727 }
728
729 public void clearInputs() {
730 assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
731 getNodeClass().unregisterAtInputsAsUsage(this);
732 }
783 * {@link Node} exists to obviate the need to cast a node before invoking
784 * {@link Simplifiable#simplify(SimplifierTool)}.
785 *
786 * @param tool
787 */
788 public void simplify(SimplifierTool tool) {
789 throw new UnsupportedOperationException();
790 }
791
792 /**
793 * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw
794 * allocating} a copy of this node
795 * @param type the type of edges to process
796 * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are
797 * cleared
798 */
799 private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) {
800 if (edgesToCopy.contains(type)) {
801 getNodeClass().getEdges(type).copy(this, newNode);
802 } else {
803 // The direct edges are already null
804 getNodeClass().getEdges(type).initializeLists(newNode, this);
805 }
806 }
807
808 public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class);
809 public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class);
810 public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs);
811 public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors);
812
813 /**
814 * Makes a copy of this node in(to) a given graph.
815 *
816 * @param into the graph in which the copy will be registered (which may be this node's graph)
817 * or null if the copy should not be registered in a graph
818 * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are
819 * initialized to their default value (i.e., {@code null} for a direct edge, an empty
820 * list for an edge list)
821 * @return the copy of this node
822 */
823 final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) {
824 final NodeClass<? extends Node> nodeClassTmp = getNodeClass();
825 boolean useIntoLeafNodeCache = false;
826 if (into != null) {
827 if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) {
828 useIntoLeafNodeCache = true;
829 Node otherNode = into.findNodeInCache(this);
830 if (otherNode != null) {
831 return otherNode;
832 }
833 }
834 }
835
836 Node newNode = null;
837 try {
838 newNode = (Node) UNSAFE.allocateInstance(getClass());
839 newNode.nodeClass = nodeClassTmp;
840 nodeClassTmp.getData().copy(this, newNode);
841 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
842 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
843 } catch (Exception e) {
844 throw new GraalGraphError(e).addContext(this);
845 }
846 newNode.graph = into;
847 newNode.id = INITIAL_ID;
848 if (into != null) {
849 into.register(newNode);
850 }
851 newNode.extraUsages = NO_NODES;
852
853 if (into != null && useIntoLeafNodeCache) {
854 into.putNodeIntoCache(newNode);
855 }
856 if (graph != null && into != null && sourcePosition != null) {
857 newNode.setNodeSourcePosition(sourcePosition);
858 }
859 newNode.afterClone(this);
860 return newNode;
861 }
862
863 protected void afterClone(@SuppressWarnings("unused") Node other) {
864 }
865
866 protected boolean verifyInputs() {
867 for (Position pos : inputPositions()) {
868 Node input = pos.get(this);
869 if (input == null) {
870 assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this);
871 } else {
872 assertFalse(input.isDeleted(), "input was deleted %s", input);
873 assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph");
874 assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType());
875 }
876 }
877 return true;
878 }
879
880 public boolean verify() {
881 assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id);
882 assertTrue(graph() != null, "null graph");
883 verifyInputs();
884 if (Options.VerifyGraalGraphEdges.getValue(getOptions())) {
885 verifyEdges();
886 }
887 return true;
888 }
889
890 /**
891 * Perform expensive verification of inputs, usages, predecessors and successors.
892 *
893 * @return true
894 */
895 public boolean verifyEdges() {
896 for (Node input : inputs()) {
897 assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input);
898 }
899
900 for (Node successor : successors()) {
901 assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor());
902 assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor);
903 }
904 for (Node usage : usages()) {
944 }
945
946 public Iterable<? extends Node> cfgPredecessors() {
947 if (predecessor == null) {
948 return Collections.emptySet();
949 } else {
950 return Collections.singleton(predecessor);
951 }
952 }
953
954 /**
955 * Returns an iterator that will provide all control-flow successors of this node. Normally this
956 * will be the contents of all fields annotated with {@link Successor}, but some node classes
957 * (like EndNode) may return different nodes.
958 */
959 public Iterable<? extends Node> cfgSuccessors() {
960 return successors();
961 }
962
963 /**
964 * Nodes using their {@link #id} as the hash code. This works very well when nodes of the same
965 * graph are stored in sets. It can give bad behavior when storing nodes of different graphs in
966 * the same set.
967 */
968 @Override
969 public final int hashCode() {
970 assert !this.isUnregistered() : "node not yet constructed";
971 if (this.isDeleted()) {
972 return -id + DELETED_ID_START;
973 }
974 return id;
975 }
976
977 /**
978 * Do not overwrite the equality test of a node in subclasses. Equality tests must rely solely
979 * on identity.
980 */
981
982 /**
983 * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the
984 * ideal graph visualizer).
985 */
986 public final Map<Object, Object> getDebugProperties() {
987 return getDebugProperties(new HashMap<>());
988 }
989
990 /**
991 * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the
992 * ideal graph visualizer). Subclasses overriding this method should also fill the map using
993 * their superclass.
994 *
995 * @param map
996 */
997 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
998 Fields properties = getNodeClass().getData();
999 for (int i = 0; i < properties.getCount(); i++) {
1000 map.put(properties.getName(i), properties.get(this, i));
|