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