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