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