1 /*
2 * Copyright (c) 2011, 2015, 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 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
122 /**
123 * Denotes an optional (nullable) node input. This should be applied to exactly the fields of a
124 * node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of type
125 * {@link Node} outside of their constructor should call {@link Node#updateUsages(Node, Node)}
126 * just prior to doing the update of the input.
127 */
128 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
129 @java.lang.annotation.Target(ElementType.FIELD)
130 public static @interface OptionalInput {
131 InputType value() default InputType.Value;
132 }
133
134 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
135 @java.lang.annotation.Target(ElementType.FIELD)
136 public static @interface Successor {
137 }
138
139 /**
140 * Denotes that a parameter of an {@linkplain NodeIntrinsic intrinsic} method must be a compile
141 * time constant at all call sites to the intrinsic method.
142 */
143 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
144 @java.lang.annotation.Target(ElementType.PARAMETER)
145 public static @interface ConstantNodeParameter {
146 }
147
148 /**
149 * Denotes an injected parameter in a {@linkplain NodeIntrinsic node intrinsic} constructor. If
150 * the constructor is called as part of node intrinsification, the node intrinsifier will inject
151 * an argument for the annotated parameter. Injected parameters must precede all non-injected
152 * parameters in a constructor.
153 */
154 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
155 @java.lang.annotation.Target(ElementType.PARAMETER)
156 public static @interface InjectedNodeParameter {
157 }
158
159 /**
160 * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the
161 * annotated method can be replaced with an instance of the node class denoted by
162 * {@link #value()}. For this reason, the signature of the annotated method must match the
163 * signature (excluding a prefix of {@linkplain InjectedNodeParameter injected} parameters) of a
164 * constructor in the node class.
165 * <p>
166 * If the node class has a static method {@code intrinsify} with a matching signature plus a
167 * {@code GraphBuilderContext} as first argument, this method is called instead of creating the
168 * node.
169 */
170 @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
171 @java.lang.annotation.Target(ElementType.METHOD)
172 public static @interface NodeIntrinsic {
173
174 /**
175 * Gets the {@link Node} subclass instantiated when intrinsifying a call to the annotated
176 * method. If not specified, then the class in which the annotated method is declared is
177 * used (and is assumed to be a {@link Node} subclass).
178 */
179 Class<?> value() default NodeIntrinsic.class;
180
181 /**
182 * Determines if the stamp of the instantiated intrinsic node has its stamp set from the
183 * return type of the annotated method.
184 * <p>
185 * When it is set to true, the stamp that is passed in to the constructor of ValueNode is
186 * ignored and can therefore safely be {@code null}.
187 */
188 boolean setStampFromReturnType() default false;
189
190 /**
191 * Determines if the stamp of the instantiated intrinsic node is guaranteed to be non-null.
192 * Generally used in conjunction with {@link #setStampFromReturnType()}.
193 */
194 boolean returnStampIsNonNull() default false;
195 }
196
197 /**
198 * Marker for a node that can be replaced by another node via global value numbering. A
199 * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same
200 * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node
201 * can be replaced by another node of the same type that has exactly the same data values as
202 * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors()
203 * successors}.
204 */
205 public interface ValueNumberable {
206 }
207
208 /**
209 * Marker interface for nodes that contains other nodes. When the inputs to this node changes,
210 * users of this node should also be placed on the work list for canonicalization.
211 */
212 public interface IndirectCanonicalization {
213 }
214
215 private Graph graph;
216 int id;
217
218 // this next pointer is used in Graph to implement fast iteration over NodeClass types, it
219 // therefore points to the next Node of the same type.
220 Node typeCacheNext;
221
222 static final int INLINE_USAGE_COUNT = 2;
223 private static final Node[] NO_NODES = {};
224
225 /**
226 * Head of usage list. The elements of the usage list in order are {@link #usage0},
227 * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list.
228 */
229 Node usage0;
230 Node usage1;
231 Node[] extraUsages;
232 int extraUsagesCount;
233
234 private Node predecessor;
235 private NodeClass<? extends Node> nodeClass;
236
237 public static final int NODE_LIST = -2;
238 public static final int NOT_ITERABLE = -1;
239
240 public Node(NodeClass<? extends Node> c) {
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);
335 }
336
337 public abstract static class EdgeVisitor {
338
339 public abstract Node apply(Node source, Node target);
340
341 }
342
343 /**
344 * Applies the given visitor to all inputs of this node.
345 *
346 * @param visitor the visitor to be applied to the inputs
347 */
348 public void applyInputs(EdgeVisitor visitor) {
349 nodeClass.applyInputs(this, visitor);
350 }
351
352 /**
353 * Applies the given visitor to all successors of this node.
354 *
355 * @param visitor the visitor to be applied to the successors
356 */
357 public void applySuccessors(EdgeVisitor visitor) {
358 nodeClass.applySuccessors(this, visitor);
359 }
360
361 /**
362 * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null successor
363 * edges of this node.
364 *
365 * @return an {@link NodeIterable iterable} for all non-null successor edges.
366 */
367 public NodeIterable<Node> successors() {
368 assert !this.isDeleted();
369 return nodeClass.getSuccessorIterable(this);
370 }
371
372 /**
373 * Returns an {@link Iterable iterable} which can be used to traverse all successor edge
374 * positions of this node.
375 *
376 * @return an {@link Iterable iterable} for all successor edge positoins.
377 */
378 public Iterable<Position> successorPositions() {
379 return nodeClass.getSuccessorEdges().getPositionsIterable(this);
380 }
381
382 /**
383 * Gets the maximum number of usages this node has had at any point in time.
384 */
385 public int getUsageCount() {
386 if (usage0 == null) {
387 return 0;
388 }
389 if (usage1 == null) {
390 return 1;
391 }
392 return 2 + extraUsagesCount;
393 }
394
395 /**
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);
445 extraUsages = newExtraUsages;
446 }
447 extraUsages[extraUsagesCount++] = node;
448 }
449 }
450
451 private void movUsageFromEndTo(int destIndex) {
452 int lastIndex = this.getUsageCount() - 1;
453 if (destIndex == 0) {
454 if (lastIndex == 0) {
455 usage0 = null;
456 return;
457 } else if (lastIndex == 1) {
458 usage0 = usage1;
459 usage1 = null;
460 return;
461 } else {
462 usage0 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
463 }
464 } else if (destIndex == 1) {
465 if (lastIndex == 1) {
466 usage1 = null;
467 return;
468 }
469 usage1 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
470 } else {
471 Node n = extraUsages[lastIndex - INLINE_USAGE_COUNT];
472 extraUsages[destIndex - INLINE_USAGE_COUNT] = n;
473 }
474 extraUsages[lastIndex - INLINE_USAGE_COUNT] = null;
475 this.extraUsagesCount--;
476 }
477
478 /**
479 * Removes a given node from this node's {@linkplain #usages() usages}.
480 *
481 * @param node the node to remove
482 * @return whether or not {@code usage} was in the usage list
483 */
484 public boolean removeUsage(Node node) {
485 assert node != null;
486 // It is critical that this method maintains the invariant that
487 // the usage list has no null element preceding a non-null element
488 incUsageModCount();
489 if (usage0 == node) {
490 this.movUsageFromEndTo(0);
491 return true;
492 }
493 if (usage1 == node) {
494 this.movUsageFromEndTo(1);
495 return true;
496 }
497 for (int i = this.extraUsagesCount - 1; i >= 0; i--) {
498 if (extraUsages[i] == node) {
499 this.movUsageFromEndTo(i + INLINE_USAGE_COUNT);
500 return true;
501 }
502 }
503 return false;
504 }
505
506 public final Node predecessor() {
507 return predecessor;
508 }
509
510 public final int modCount() {
511 if (isModificationCountsEnabled() && graph != null) {
512 return graph.modCount(this);
513 }
514 return 0;
515 }
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 }
564 }
565
566 protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) {
567 updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode());
568 }
569
570 /**
571 * Updates the predecessor of the given nodes after a successor slot is changed from
572 * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds
573 * this node to newSuccessor's predecessors.
574 */
575 protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) {
576 assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) || newSuccessor == null && !isAlive() : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor;
577 assert graph == null || !graph.isFrozen();
578 if (oldSuccessor != newSuccessor) {
579 if (oldSuccessor != null) {
580 assert assertTrue(newSuccessor == null || oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this);
581 oldSuccessor.predecessor = null;
582 }
583 if (newSuccessor != null) {
584 assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this);
585 newSuccessor.predecessor = this;
586 }
587 }
588 }
589
590 void initialize(Graph newGraph) {
591 assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id);
592 this.graph = newGraph;
593 newGraph.register(this);
594 this.getNodeClass().registerAtInputsAsUsage(this);
595 this.getNodeClass().registerAtSuccessorsAsPredecessor(this);
596 }
597
598 /**
599 * The position of the bytecode that generated this node.
600 */
601 NodeSourcePosition sourcePosition;
602
603 /**
604 * Gets the source position information for this node or null if it doesn't exist.
605 */
606
607 public NodeSourcePosition getNodeSourcePosition() {
608 return sourcePosition;
609 }
610
611 /**
612 * Set the source position to {@code sourcePosition}.
613 */
614 public void setNodeSourcePosition(NodeSourcePosition sourcePosition) {
615 this.sourcePosition = sourcePosition;
616 if (sourcePosition != null && graph != null && !graph.seenNodeSourcePosition) {
617 graph.seenNodeSourcePosition = true;
618 }
619 }
620
621 public DebugCloseable withNodeSourcePosition() {
622 return graph.withNodeSourcePosition(this);
623 }
624
625 public final NodeClass<? extends Node> getNodeClass() {
626 return nodeClass;
627 }
628
629 public boolean isAllowedUsageType(InputType type) {
630 if (type == InputType.Value) {
631 return false;
632 }
633 return getNodeClass().getAllowedUsageTypes().contains(type);
634 }
635
636 private boolean checkReplaceWith(Node other) {
637 assert assertTrue(graph == null || !graph.isFrozen(), "cannot modify frozen graph");
638 assert assertFalse(other == this, "cannot replace a node with itself");
639 assert assertFalse(isDeleted(), "cannot replace deleted node");
640 assert assertTrue(other == null || !other.isDeleted(), "cannot replace with deleted node %s", other);
641 return true;
642 }
643
644 public final void replaceAtUsages(Node other) {
645 replaceAtUsages(other, null, null);
646 }
647
648 public final void replaceAtUsages(Node other, Predicate<Node> filter) {
649 replaceAtUsages(other, filter, null);
650 }
651
652 public final void replaceAtUsagesAndDelete(Node other) {
653 replaceAtUsages(other, null, this);
654 safeDelete();
655 }
656
657 public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) {
658 replaceAtUsages(other, filter, this);
659 safeDelete();
660 }
661
662 protected void replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted) {
663 assert checkReplaceWith(other);
664 int i = 0;
665 while (i < this.getUsageCount()) {
666 Node usage = this.getUsageAt(i);
667 if (filter == null || filter.test(usage)) {
668 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other);
669 assert assertTrue(result, "not found in inputs, usage: %s", usage);
670 /*
671 * Don't notify for nodes which are about to be deleted.
672 */
673 if (toBeDeleted == null || usage != toBeDeleted) {
674 maybeNotifyInputChanged(usage);
675 }
676 if (other != null) {
677 other.addUsage(usage);
678 }
679 this.movUsageFromEndTo(i);
680 } else {
681 ++i;
682 }
683 }
684 }
685
686 public Node getUsageAt(int index) {
687 if (index == 0) {
688 return this.usage0;
689 } else if (index == 1) {
690 return this.usage1;
691 } else {
692 return this.extraUsages[index - INLINE_USAGE_COUNT];
693 }
694 }
695
696 public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) {
697 assert checkReplaceWith(other);
698 int index = 0;
699 while (index < this.getUsageCount()) {
700 Node usage = getUsageAt(index);
701 if (usagePredicate.apply(usage)) {
702 boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other);
703 assert assertTrue(result, "not found in inputs, usage: %s", usage);
704 if (other != null) {
705 maybeNotifyInputChanged(usage);
706 other.addUsage(usage);
707 }
708 this.movUsageFromEndTo(index);
709 } else {
710 index++;
711 }
712 }
713 }
714
715 public void replaceAtUsages(InputType type, Node other) {
716 assert checkReplaceWith(other);
717 for (Node usage : usages().snapshot()) {
718 for (Position pos : usage.inputPositions()) {
719 if (pos.getInputType() == type && pos.get(usage) == this) {
720 pos.set(usage, other);
721 }
722 }
723 }
724 }
725
726 private void maybeNotifyInputChanged(Node node) {
727 if (graph != null) {
728 assert !graph.isFrozen();
729 NodeEventListener listener = graph.nodeEventListener;
730 if (listener != null) {
731 listener.inputChanged(node);
732 }
733 if (Fingerprint.ENABLED) {
734 Fingerprint.submit("%s: %s", NodeEvent.INPUT_CHANGED, node);
735 }
736 }
737 }
738
739 public void maybeNotifyZeroUsages(Node node) {
740 if (graph != null) {
741 assert !graph.isFrozen();
742 NodeEventListener listener = graph.nodeEventListener;
743 if (listener != null && node.isAlive()) {
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 }
785
786 boolean removeThisFromUsages(Node n) {
787 return n.removeUsage(this);
788 }
789
790 public void clearSuccessors() {
791 assert assertFalse(isDeleted(), "cannot clear successors of deleted node");
792 getNodeClass().unregisterAtSuccessorsAsPredecessor(this);
793 }
794
795 private boolean checkDeletion() {
796 assertTrue(isAlive(), "must be alive");
797 assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages());
798 assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor);
799 return true;
800 }
801
802 /**
803 * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages}
804 * and no {@linkplain #predecessor() predecessor}.
805 */
806 public void safeDelete() {
807 assert checkDeletion();
808 this.clearInputs();
809 this.clearSuccessors();
810 markDeleted();
811 }
812
813 public void markDeleted() {
814 graph.unregister(this);
815 id = DELETED_ID_START - id;
816 assert isDeleted();
817 }
818
819 public final Node copyWithInputs() {
820 return copyWithInputs(true);
821 }
822
823 public final Node copyWithInputs(boolean insertIntoGraph) {
824 Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges);
825 if (insertIntoGraph) {
826 for (Node input : inputs()) {
827 input.addUsage(newNode);
828 }
829 }
830 return newNode;
831 }
832
833 /**
834 * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in
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()) {
972 assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage);
973 assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage);
974 boolean foundThis = false;
975 for (Position pos : usage.inputPositions()) {
976 if (pos.get(usage) == this) {
977 foundThis = true;
978 if (pos.getInputType() != InputType.Unchecked) {
979 assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type %s from %s to %s (%s)", pos.getInputType(), usage, this, pos.getName());
980 }
981 }
982 }
983 assertTrue(foundThis, "missing input in usage %s", usage);
984 }
985
986 if (predecessor != null) {
987 assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor);
988 assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor);
989 }
990 return true;
991 }
992
993 public boolean assertTrue(boolean condition, String message, Object... args) {
994 if (condition) {
995 return true;
996 } else {
997 throw fail(message, args);
998 }
999 }
1000
1001 public boolean assertFalse(boolean condition, String message, Object... args) {
1002 if (condition) {
1003 throw fail(message, args);
1004 } else {
1005 return true;
1006 }
1007 }
1008
1009 protected VerificationError fail(String message, Object... args) throws GraalGraphError {
1010 throw new VerificationError(message, args).addContext(this);
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));
1065 }
1066 NodeSourcePosition pos = getNodeSourcePosition();
1067 if (pos != null) {
1068 map.put("nodeSourcePosition", pos);
1069 }
1070 return map;
1071 }
1072
1073 /**
1074 * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}.
1075 */
1076 @Override
1077 public final String toString() {
1078 return toString(Verbosity.Short);
1079 }
1080
1081 /**
1082 * Creates a String representation for this node with a given {@link Verbosity}.
1083 */
1084 public String toString(Verbosity verbosity) {
1085 switch (verbosity) {
1086 case Id:
1087 return Integer.toString(id);
1088 case Name:
1089 return getNodeClass().shortName();
1090 case Short:
1091 return toString(Verbosity.Id) + "|" + toString(Verbosity.Name);
1092 case Long:
1093 return toString(Verbosity.Short);
1094 case Debugger:
1095 case All: {
1096 StringBuilder str = new StringBuilder();
1097 str.append(toString(Verbosity.Short)).append(" { ");
1098 for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) {
1099 str.append(entry.getKey()).append("=").append(entry.getValue()).append(", ");
1100 }
1101 str.append(" }");
1102 return str.toString();
1103 }
1104 default:
1105 throw new RuntimeException("unknown verbosity: " + verbosity);
1106 }
1107 }
1108
1109 @Deprecated
1110 public int getId() {
1111 return id;
1112 }
1113
1114 @Override
1115 public void formatTo(Formatter formatter, int flags, int width, int precision) {
1116 if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) {
1117 formatter.format("%s", toString(Verbosity.Id));
1118 } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) {
1119 // Use All here since Long is only slightly longer than Short.
1120 formatter.format("%s", toString(Verbosity.All));
1121 } else {
1122 formatter.format("%s", toString(Verbosity.Short));
1123 }
1124
1125 boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY);
1126 int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0);
1127 if (width > 0) {
1128 if (this.predecessor != null) {
1129 formatter.format(" pred={");
1130 this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0);
1131 formatter.format("}");
1132 }
1133
1134 for (Position position : this.inputPositions()) {
1135 Node input = position.get(this);
1136 if (input != null) {
1137 formatter.format(" ");
1138 formatter.format(position.getName());
1139 formatter.format("={");
1140 input.formatTo(formatter, neighborsFlags, width - 1, 0);
1141 formatter.format("}");
1142 }
1143 }
1144 }
1145
1146 if (precision > 0) {
1147 if (!hasNoUsages()) {
1148 formatter.format(" usages={");
1149 int z = 0;
1150 for (Node usage : usages()) {
1151 if (z != 0) {
1152 formatter.format(", ");
1153 }
1154 usage.formatTo(formatter, neighborsFlags, 0, precision - 1);
1155 ++z;
1156 }
1157 formatter.format("}");
1158 }
1159
1160 for (Position position : this.successorPositions()) {
1161 Node successor = position.get(this);
1162 if (successor != null) {
1163 formatter.format(" ");
1164 formatter.format(position.getName());
1165 formatter.format("={");
1166 successor.formatTo(formatter, neighborsFlags, 0, precision - 1);
1167 formatter.format("}");
1168 }
1169 }
1170 }
1171 }
1172
1173 /**
1174 * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data
1175 * fields of another node of the same type. Primitive fields are compared by value and
1176 * non-primitive fields are compared by {@link Objects#equals(Object, Object)}.
1177 *
1178 * The result of this method undefined if {@code other.getClass() != this.getClass()}.
1179 *
1180 * @param other a node of exactly the same type as this node
1181 * @return true if the data fields of this object and {@code other} are equal
1182 */
1183 public boolean valueEquals(Node other) {
1184 return getNodeClass().dataEquals(this, other);
1185 }
1186
1187 public final void pushInputs(NodeStack stack) {
1188 getNodeClass().pushInputs(this, stack);
1189 }
1190 }