001/*
002 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph;
024
025import static com.oracle.graal.graph.Edges.Type.*;
026import static com.oracle.graal.graph.Graph.*;
027
028import java.lang.annotation.*;
029import java.util.*;
030import java.util.function.*;
031
032import jdk.internal.jvmci.common.*;
033import com.oracle.graal.debug.*;
034import sun.misc.*;
035
036import com.oracle.graal.compiler.common.*;
037import com.oracle.graal.graph.Graph.NodeEvent;
038import com.oracle.graal.graph.Graph.NodeEventListener;
039import com.oracle.graal.graph.Graph.Options;
040import com.oracle.graal.graph.iterators.*;
041import com.oracle.graal.graph.spi.*;
042import com.oracle.graal.nodeinfo.*;
043
044/**
045 * This class is the base class for all nodes. It represents a node that can be inserted in a
046 * {@link Graph}.
047 * <p>
048 * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the
049 * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and
050 * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either
051 * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node
052 * this field points to.
053 * <p>
054 * Nodes which are be value numberable should implement the {@link ValueNumberable} interface.
055 *
056 * <h1>Replay Compilation</h1>
057 *
058 * To enable deterministic replay compilation, node sets and node maps should be instantiated with
059 * the following methods:
060 * <ul>
061 * <li>{@link #newSet()}</li>
062 * <li>{@link #newSet(Collection)}</li>
063 * <li>{@link #newMap()}</li>
064 * <li>{@link #newMap(int)}</li>
065 * <li>{@link #newMap(Map)}</li>
066 * <li>{@link #newIdentityMap()}</li>
067 * <li>{@link #newIdentityMap(int)}</li>
068 * <li>{@link #newIdentityMap(Map)}</li>
069 * </ul>
070 *
071 * <h1>Assertions and Verification</h1>
072 *
073 * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and
074 * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean
075 * and throw a VerificationError if it has the wrong value. Both methods will always either throw an
076 * exception or return true. They can thus be used within an assert statement, so that the check is
077 * only performed if assertions are enabled.
078 */
079@NodeInfo
080public abstract class Node implements Cloneable, Formattable {
081
082    public static final NodeClass<?> TYPE = null;
083    public static final boolean USE_UNSAFE_TO_CLONE = Boolean.parseBoolean(System.getProperty("graal.node.useUnsafeToClone", "true"));
084
085    static final int DELETED_ID_START = -1000000000;
086    static final int INITIAL_ID = -1;
087    static final int ALIVE_ID_START = 0;
088
089    // The use of fully qualified class names here and in the rest
090    // of this file works around a problem javac has resolving symbols
091
092    /**
093     * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of
094     * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of
095     * type {@link Node} outside of their constructor should call
096     * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input.
097     */
098    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
099    @java.lang.annotation.Target(ElementType.FIELD)
100    public static @interface Input {
101        InputType value() default InputType.Value;
102    }
103
104    /**
105     * Denotes an optional (nullable) node input. This should be applied to exactly the fields of a
106     * node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of type
107     * {@link Node} outside of their constructor should call {@link Node#updateUsages(Node, Node)}
108     * just prior to doing the update of the input.
109     */
110    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
111    @java.lang.annotation.Target(ElementType.FIELD)
112    public static @interface OptionalInput {
113        InputType value() default InputType.Value;
114    }
115
116    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
117    @java.lang.annotation.Target(ElementType.FIELD)
118    public static @interface Successor {
119    }
120
121    /**
122     * Denotes that a parameter of an {@linkplain NodeIntrinsic intrinsic} method must be a compile
123     * time constant at all call sites to the intrinsic method.
124     */
125    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
126    @java.lang.annotation.Target(ElementType.PARAMETER)
127    public static @interface ConstantNodeParameter {
128    }
129
130    /**
131     * Denotes an injected parameter in a {@linkplain NodeIntrinsic node intrinsic} constructor. If
132     * the constructor is called as part of node intrinsification, the node intrinsifier will inject
133     * an argument for the annotated parameter. Injected parameters must precede all non-injected
134     * parameters in a constructor.
135     */
136    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
137    @java.lang.annotation.Target(ElementType.PARAMETER)
138    public static @interface InjectedNodeParameter {
139    }
140
141    /**
142     * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the
143     * annotated method can be replaced with an instance of the node class denoted by
144     * {@link #value()}. For this reason, the signature of the annotated method must match the
145     * signature (excluding a prefix of {@linkplain InjectedNodeParameter injected} parameters) of a
146     * factory method named {@code "create"} in the node class.
147     */
148    @java.lang.annotation.Retention(RetentionPolicy.RUNTIME)
149    @java.lang.annotation.Target(ElementType.METHOD)
150    public static @interface NodeIntrinsic {
151
152        /**
153         * Gets the {@link Node} subclass instantiated when intrinsifying a call to the annotated
154         * method. If not specified, then the class in which the annotated method is declared is
155         * used (and is assumed to be a {@link Node} subclass).
156         */
157        Class<?> value() default NodeIntrinsic.class;
158
159        /**
160         * Determines if the stamp of the instantiated intrinsic node has its stamp set from the
161         * return type of the annotated method.
162         * <p>
163         * When it is set to true, the stamp that is passed in to the constructor of ValueNode is
164         * ignored and can therefore safely be {@code null}.
165         */
166        boolean setStampFromReturnType() default false;
167
168        /**
169         * Determines if this intrinsic can be compile-time executed. An attempt to execute a call
170         * (via reflection) to this intrinsic at compile-time will be made if all of its arguments
171         * are compile-time constant. If the execution succeeds without an exception, the result is
172         * inserted as a constant node in the graph.
173         */
174        boolean foldable() default false;
175    }
176
177    /**
178     * Marker for a node that can be replaced by another node via global value numbering. A
179     * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same
180     * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node
181     * can be replaced by another node of the same type that has exactly the same data values as
182     * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors()
183     * successors}.
184     */
185    public interface ValueNumberable {
186    }
187
188    private Graph graph;
189    int id;
190
191    // this next pointer is used in Graph to implement fast iteration over NodeClass types, it
192    // therefore points to the next Node of the same type.
193    Node typeCacheNext;
194
195    static final int INLINE_USAGE_COUNT = 2;
196    private static final Node[] NO_NODES = {};
197
198    /**
199     * Head of usage list. The elements of the usage list in order are {@link #usage0},
200     * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list.
201     */
202    Node usage0;
203    Node usage1;
204    Node[] extraUsages;
205    int extraUsagesCount;
206
207    private Node predecessor;
208    private NodeClass<? extends Node> nodeClass;
209
210    public static final int NODE_LIST = -2;
211    public static final int NOT_ITERABLE = -1;
212
213    public Node(NodeClass<? extends Node> c) {
214        init(c);
215    }
216
217    final void init(NodeClass<? extends Node> c) {
218        assert c.getJavaClass() == this.getClass();
219        this.nodeClass = c;
220        id = INITIAL_ID;
221        extraUsages = NO_NODES;
222    }
223
224    int id() {
225        return id;
226    }
227
228    /**
229     * @see CollectionsFactory#newSet()
230     */
231    public static <E extends Node> Set<E> newSet() {
232        return CollectionsFactory.newSet();
233    }
234
235    /**
236     * @see #newSet()
237     */
238    public static <E extends Node> Set<E> newSet(Collection<? extends E> c) {
239        return CollectionsFactory.newSet(c);
240    }
241
242    public static <K extends Node, V> Map<K, V> newMap() {
243        // Node.equals() and Node.hashCode() are final and are implemented
244        // purely in terms of identity so HashMap and IdentityHashMap with
245        // Node's as keys will behave the same. We choose to use the latter
246        // due to its lighter memory footprint.
247        return newIdentityMap();
248    }
249
250    public static <K extends Node, V> Map<K, V> newMap(Map<K, V> m) {
251        // Node.equals() and Node.hashCode() are final and are implemented
252        // purely in terms of identity so HashMap and IdentityHashMap with
253        // Node's as keys will behave the same. We choose to use the latter
254        // due to its lighter memory footprint.
255        return newIdentityMap(m);
256    }
257
258    public static <K extends Node, V> Map<K, V> newMap(int expectedMaxSize) {
259        // Node.equals() and Node.hashCode() are final and are implemented
260        // purely in terms of identity so HashMap and IdentityHashMap with
261        // Node's as keys will behave the same. We choose to use the latter
262        // due to its lighter memory footprint.
263        return newIdentityMap(expectedMaxSize);
264    }
265
266    public static <K extends Node, V> Map<K, V> newIdentityMap() {
267        return CollectionsFactory.newIdentityMap();
268    }
269
270    public static <K extends Node, V> Map<K, V> newIdentityMap(Map<K, V> m) {
271        return CollectionsFactory.newIdentityMap(m);
272    }
273
274    public static <K extends Node, V> Map<K, V> newIdentityMap(int expectedMaxSize) {
275        return CollectionsFactory.newIdentityMap(expectedMaxSize);
276    }
277
278    /**
279     * Gets the graph context of this node.
280     */
281    public Graph graph() {
282        return graph;
283    }
284
285    /**
286     * Returns an {@link NodeClassIterable iterable} which can be used to traverse all non-null
287     * input edges of this node.
288     *
289     * @return an {@link NodeClassIterable iterable} for all non-null input edges.
290     */
291    public NodeClassIterable inputs() {
292        return nodeClass.getInputEdges().getIterable(this);
293    }
294
295    /**
296     * Applies the given consumer to all inputs of this node.
297     *
298     * @param consumer the consumer to be applied to the inputs
299     */
300    public void acceptInputs(BiConsumer<Node, Node> consumer) {
301        nodeClass.getInputEdges().accept(this, consumer);
302    }
303
304    /**
305     * Returns an {@link NodeClassIterable iterable} which can be used to traverse all non-null
306     * successor edges of this node.
307     *
308     * @return an {@link NodeClassIterable iterable} for all non-null successor edges.
309     */
310    public NodeClassIterable successors() {
311        return nodeClass.getSuccessorEdges().getIterable(this);
312    }
313
314    /**
315     * Applies the given consumer to all successors of this node.
316     *
317     * @param consumer the consumer to be applied to the inputs
318     */
319    public void acceptSuccessors(BiConsumer<Node, Node> consumer) {
320        nodeClass.getSuccessorEdges().accept(this, consumer);
321    }
322
323    /**
324     * Gets the maximum number of usages this node has had at any point in time.
325     */
326    public int getUsageCount() {
327        if (usage0 == null) {
328            return 0;
329        }
330        if (usage1 == null) {
331            return 1;
332        }
333        return 2 + extraUsagesCount;
334    }
335
336    /**
337     * Gets the list of nodes that use this node (i.e., as an input).
338     */
339    public final NodeIterable<Node> usages() {
340        return new NodeUsageIterable(this);
341    }
342
343    /**
344     * Checks whether this node has no usages.
345     */
346    public final boolean hasNoUsages() {
347        return this.usage0 == null;
348    }
349
350    /**
351     * Checks whether this node has usages.
352     */
353    public final boolean hasUsages() {
354        return this.usage0 != null;
355    }
356
357    void reverseUsageOrder() {
358        List<Node> snapshot = this.usages().snapshot();
359        for (Node n : snapshot) {
360            this.removeUsage(n);
361        }
362        Collections.reverse(snapshot);
363        for (Node n : snapshot) {
364            this.addUsage(n);
365        }
366    }
367
368    /**
369     * Adds a given node to this node's {@linkplain #usages() usages}.
370     *
371     * @param node the node to add
372     */
373    private void addUsage(Node node) {
374        incUsageModCount();
375        if (usage0 == null) {
376            usage0 = node;
377        } else if (usage1 == null) {
378            usage1 = node;
379        } else {
380            int length = extraUsages.length;
381            if (length == 0) {
382                extraUsages = new Node[4];
383            } else if (extraUsagesCount == length) {
384                Node[] newExtraUsages = new Node[length * 2 + 1];
385                System.arraycopy(extraUsages, 0, newExtraUsages, 0, length);
386                extraUsages = newExtraUsages;
387            }
388            extraUsages[extraUsagesCount++] = node;
389        }
390    }
391
392    private void movUsageFromEndTo(int destIndex) {
393        int lastIndex = this.getUsageCount() - 1;
394        if (destIndex == 0) {
395            if (lastIndex == 0) {
396                usage0 = null;
397                return;
398            } else if (lastIndex == 1) {
399                usage0 = usage1;
400                usage1 = null;
401                return;
402            } else {
403                usage0 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
404            }
405        } else if (destIndex == 1) {
406            if (lastIndex == 1) {
407                usage1 = null;
408                return;
409            }
410            usage1 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
411        } else {
412            Node n = extraUsages[lastIndex - INLINE_USAGE_COUNT];
413            extraUsages[destIndex - INLINE_USAGE_COUNT] = n;
414        }
415        extraUsages[lastIndex - INLINE_USAGE_COUNT] = null;
416        this.extraUsagesCount--;
417    }
418
419    /**
420     * Removes a given node from this node's {@linkplain #usages() usages}.
421     *
422     * @param node the node to remove
423     * @return whether or not {@code usage} was in the usage list
424     */
425    public boolean removeUsage(Node node) {
426        assert node != null;
427        // It is critical that this method maintains the invariant that
428        // the usage list has no null element preceding a non-null element
429        incUsageModCount();
430        if (usage0 == node) {
431            this.movUsageFromEndTo(0);
432            return true;
433        }
434        if (usage1 == node) {
435            this.movUsageFromEndTo(1);
436            return true;
437        }
438        for (int i = this.extraUsagesCount - 1; i >= 0; i--) {
439            if (extraUsages[i] == node) {
440                this.movUsageFromEndTo(i + INLINE_USAGE_COUNT);
441                return true;
442            }
443        }
444        return false;
445    }
446
447    public final Node predecessor() {
448        return predecessor;
449    }
450
451    public final int modCount() {
452        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
453            return graph.modCount(this);
454        }
455        return 0;
456    }
457
458    final void incModCount() {
459        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
460            graph.incModCount(this);
461        }
462    }
463
464    final int usageModCount() {
465        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
466            return graph.usageModCount(this);
467        }
468        return 0;
469    }
470
471    final void incUsageModCount() {
472        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
473            graph.incUsageModCount(this);
474        }
475    }
476
477    public boolean isDeleted() {
478        return id <= DELETED_ID_START;
479    }
480
481    public boolean isAlive() {
482        return id >= ALIVE_ID_START;
483    }
484
485    /**
486     * Updates the usages sets of the given nodes after an input slot is changed from
487     * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and
488     * adds this node to {@code newInput}'s usages.
489     */
490    protected void updateUsages(Node oldInput, Node newInput) {
491        assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput;
492        if (oldInput != newInput) {
493            if (oldInput != null) {
494                boolean result = removeThisFromUsages(oldInput);
495                assert assertTrue(result, "not found in usages, old input: %s", oldInput);
496            }
497            maybeNotifyInputChanged(this);
498            if (newInput != null) {
499                newInput.addUsage(this);
500            }
501            if (oldInput != null && oldInput.hasNoUsages()) {
502                maybeNotifyZeroUsages(oldInput);
503            }
504        }
505    }
506
507    protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) {
508        updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode());
509    }
510
511    /**
512     * Updates the predecessor of the given nodes after a successor slot is changed from
513     * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds
514     * this node to newSuccessor's predecessors.
515     */
516    protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) {
517        assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor;
518        assert graph == null || !graph.isFrozen();
519        if (oldSuccessor != newSuccessor) {
520            if (oldSuccessor != null) {
521                assert assertTrue(oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this);
522                oldSuccessor.predecessor = null;
523            }
524            if (newSuccessor != null) {
525                assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this);
526                newSuccessor.predecessor = this;
527            }
528        }
529    }
530
531    void initialize(Graph newGraph) {
532        assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id);
533        this.graph = newGraph;
534        newGraph.register(this);
535        this.acceptInputs((n, i) -> {
536            if (!i.isAlive()) {
537                throw new IllegalStateException(String.format("Input %s of newly created node %s is not alive.", i, n));
538            }
539            n.updateUsages(null, i);
540        });
541        this.acceptSuccessors((n, s) -> {
542            if (!s.isAlive()) {
543                throw new IllegalStateException(String.format("Successor %s of newly created node %s is not alive.", s, n));
544            }
545            n.updatePredecessor(null, s);
546        });
547    }
548
549    public final NodeClass<? extends Node> getNodeClass() {
550        return nodeClass;
551    }
552
553    public boolean isAllowedUsageType(InputType type) {
554        return getNodeClass().getAllowedUsageTypes().contains(type);
555    }
556
557    private boolean checkReplaceWith(Node other) {
558        assert assertTrue(graph == null || !graph.isFrozen(), "cannot modify frozen graph");
559        assert assertFalse(other == this, "cannot replace a node with itself");
560        assert assertFalse(isDeleted(), "cannot replace deleted node");
561        assert assertTrue(other == null || !other.isDeleted(), "cannot replace with deleted node %s", other);
562        return true;
563    }
564
565    public final void replaceAtUsages(Node other) {
566        replaceAtUsages(other, null);
567    }
568
569    public final void replaceAtUsages(Node other, Predicate<Node> filter) {
570        assert checkReplaceWith(other);
571        int i = 0;
572        while (i < this.getUsageCount()) {
573            Node usage = this.getUsageAt(i);
574            if (filter == null || filter.test(usage)) {
575                boolean result = usage.getNodeClass().getInputEdges().replaceFirst(usage, this, other);
576                assert assertTrue(result, "not found in inputs, usage: %s", usage);
577                maybeNotifyInputChanged(usage);
578                if (other != null) {
579                    other.addUsage(usage);
580                }
581                this.movUsageFromEndTo(i);
582            } else {
583                ++i;
584            }
585        }
586    }
587
588    public Node getUsageAt(int index) {
589        if (index == 0) {
590            return this.usage0;
591        } else if (index == 1) {
592            return this.usage1;
593        } else {
594            return this.extraUsages[index - INLINE_USAGE_COUNT];
595        }
596    }
597
598    public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) {
599        assert checkReplaceWith(other);
600        int index = 0;
601        while (index < this.getUsageCount()) {
602            Node usage = getUsageAt(index);
603            if (usagePredicate.apply(usage)) {
604                boolean result = usage.getNodeClass().getInputEdges().replaceFirst(usage, this, other);
605                assert assertTrue(result, "not found in inputs, usage: %s", usage);
606                if (other != null) {
607                    maybeNotifyInputChanged(usage);
608                    other.addUsage(usage);
609                }
610                this.movUsageFromEndTo(index);
611            } else {
612                index++;
613            }
614        }
615    }
616
617    public void replaceAtUsages(InputType type, Node other) {
618        assert checkReplaceWith(other);
619        for (Node usage : usages().snapshot()) {
620            NodePosIterator iter = usage.inputs().iterator();
621            while (iter.hasNext()) {
622                Position pos = iter.nextPosition();
623                if (pos.getInputType() == type && pos.get(usage) == this) {
624                    pos.set(usage, other);
625                }
626            }
627        }
628    }
629
630    private void maybeNotifyInputChanged(Node node) {
631        if (graph != null) {
632            assert !graph.isFrozen();
633            NodeEventListener listener = graph.nodeEventListener;
634            if (listener != null) {
635                listener.inputChanged(node);
636            }
637            if (Fingerprint.ENABLED) {
638                Fingerprint.submit("%s: %s", NodeEvent.INPUT_CHANGED, node);
639            }
640        }
641    }
642
643    private void maybeNotifyZeroUsages(Node node) {
644        if (graph != null) {
645            assert !graph.isFrozen();
646            NodeEventListener listener = graph.nodeEventListener;
647            if (listener != null && node.isAlive()) {
648                listener.usagesDroppedToZero(node);
649            }
650            if (Fingerprint.ENABLED) {
651                Fingerprint.submit("%s: %s", NodeEvent.ZERO_USAGES, node);
652            }
653        }
654    }
655
656    public void replaceAtPredecessor(Node other) {
657        assert checkReplaceWith(other);
658        if (predecessor != null) {
659            boolean result = predecessor.getNodeClass().getSuccessorEdges().replaceFirst(predecessor, this, other);
660            assert assertTrue(result, "not found in successors, predecessor: %s", predecessor);
661            predecessor.updatePredecessor(this, other);
662        }
663    }
664
665    public void replaceAndDelete(Node other) {
666        assert checkReplaceWith(other);
667        assert other != null;
668        clearInputs();
669        clearSuccessors();
670        replaceAtUsages(other);
671        replaceAtPredecessor(other);
672        safeDelete();
673    }
674
675    public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) {
676        if (nodeClass.getSuccessorEdges().replaceFirst(this, oldSuccessor, newSuccessor)) {
677            updatePredecessor(oldSuccessor, newSuccessor);
678        }
679    }
680
681    public void replaceFirstInput(Node oldInput, Node newInput) {
682        if (nodeClass.getInputEdges().replaceFirst(this, oldInput, newInput)) {
683            updateUsages(oldInput, newInput);
684        }
685    }
686
687    private void unregisterInputs() {
688        acceptInputs((node, input) -> {
689            node.removeThisFromUsages(input);
690            if (input.hasNoUsages()) {
691                node.maybeNotifyZeroUsages(input);
692            }
693        });
694    }
695
696    public void clearInputs() {
697        assert assertFalse(isDeleted(), "cannot clear inputs of deleted node");
698
699        unregisterInputs();
700        getNodeClass().getInputEdges().clear(this);
701    }
702
703    private boolean removeThisFromUsages(Node n) {
704        return n.removeUsage(this);
705    }
706
707    private void unregisterSuccessors() {
708        this.acceptSuccessors((n, successor) -> successor.predecessor = null);
709    }
710
711    public void clearSuccessors() {
712        assert assertFalse(isDeleted(), "cannot clear successors of deleted node");
713
714        unregisterSuccessors();
715        getNodeClass().getSuccessorEdges().clear(this);
716    }
717
718    private boolean checkDeletion() {
719        assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages());
720        assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor);
721        return true;
722    }
723
724    /**
725     * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages}
726     * and no {@linkplain #predecessor() predecessor}.
727     */
728    public void safeDelete() {
729        assert checkDeletion();
730        unregisterInputs();
731        unregisterSuccessors();
732        markDeleted();
733    }
734
735    public void markDeleted() {
736        graph.unregister(this);
737        id = DELETED_ID_START - id;
738        assert isDeleted();
739    }
740
741    public final Node copyWithInputs() {
742        return copyWithInputs(true);
743    }
744
745    public final Node copyWithInputs(boolean insertIntoGraph) {
746        Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges);
747        if (insertIntoGraph) {
748            for (Node input : inputs()) {
749                input.addUsage(newNode);
750            }
751        }
752        return newNode;
753    }
754
755    /**
756     * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in
757     * {@link Node} exists to obviate the need to cast a node before invoking
758     * {@link Simplifiable#simplify(SimplifierTool)}.
759     *
760     * @param tool
761     */
762    public void simplify(SimplifierTool tool) {
763        throw new UnsupportedOperationException();
764    }
765
766    /**
767     * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw
768     *            allocating} a copy of this node
769     * @param type the type of edges to process
770     * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are
771     *            cleared
772     */
773    private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) {
774        if (edgesToCopy.contains(type)) {
775            getNodeClass().getEdges(type).copy(this, newNode);
776        } else {
777            if (USE_UNSAFE_TO_CLONE) {
778                // The direct edges are already null
779                getNodeClass().getEdges(type).initializeLists(newNode, this);
780            } else {
781                getNodeClass().getEdges(type).clear(newNode);
782            }
783        }
784    }
785
786    public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class);
787    public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class);
788    public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs);
789    public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors);
790
791    /**
792     * Makes a copy of this node in(to) a given graph.
793     *
794     * @param into the graph in which the copy will be registered (which may be this node's graph)
795     *            or null if the copy should not be registered in a graph
796     * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are
797     *            initialized to their default value (i.e., {@code null} for a direct edge, an empty
798     *            list for an edge list)
799     * @return the copy of this node
800     */
801    final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) {
802        final NodeClass<? extends Node> nodeClassTmp = getNodeClass();
803        boolean useIntoLeafNodeCache = false;
804        if (into != null) {
805            if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) {
806                useIntoLeafNodeCache = true;
807                Node otherNode = into.findNodeInCache(this);
808                if (otherNode != null) {
809                    return otherNode;
810                }
811            }
812        }
813
814        Node newNode = null;
815        try {
816            if (USE_UNSAFE_TO_CLONE) {
817                newNode = (Node) UnsafeAccess.unsafe.allocateInstance(getClass());
818                newNode.nodeClass = nodeClassTmp;
819                nodeClassTmp.getData().copy(this, newNode);
820                copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
821                copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
822            } else {
823                newNode = (Node) this.clone();
824                newNode.typeCacheNext = null;
825                newNode.usage0 = null;
826                newNode.usage1 = null;
827                newNode.predecessor = null;
828                newNode.extraUsagesCount = 0;
829                copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
830                copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
831            }
832        } catch (Exception e) {
833            throw new GraalGraphJVMCIError(e).addContext(this);
834        }
835        newNode.graph = into;
836        newNode.id = INITIAL_ID;
837        if (into != null) {
838            into.register(newNode);
839        }
840        newNode.extraUsages = NO_NODES;
841
842        if (into != null && useIntoLeafNodeCache) {
843            into.putNodeIntoCache(newNode);
844        }
845        newNode.afterClone(this);
846        return newNode;
847    }
848
849    protected void afterClone(@SuppressWarnings("unused") Node other) {
850    }
851
852    public boolean verifyInputs() {
853        for (Node input : inputs()) {
854            assertFalse(input.isDeleted(), "input was deleted");
855            assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph");
856        }
857        return true;
858    }
859
860    public boolean verify() {
861        assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id);
862        assertTrue(graph() != null, "null graph");
863        if (Options.VerifyGraalGraphEdges.getValue()) {
864            verifyEdges();
865        }
866        return true;
867    }
868
869    /**
870     * Perform expensive verification of inputs, usages, predecessors and successors.
871     *
872     * @return true
873     */
874    public boolean verifyEdges() {
875        verifyInputs();
876        for (Node input : inputs()) {
877            assertTrue(input.usages().contains(this), "missing usage in input %s", input);
878        }
879        for (Node successor : successors()) {
880            assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor());
881            assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor);
882        }
883        for (Node usage : usages()) {
884            assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage);
885            assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage);
886            NodePosIterator iterator = usage.inputs().iterator();
887            while (iterator.hasNext()) {
888                Position pos = iterator.nextPosition();
889                if (pos.get(usage) == this && pos.getInputType() != InputType.Unchecked) {
890                    assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type " + pos.getInputType() + " from " + usage + " to " + this + " (" + pos.getName() + ")");
891                }
892            }
893        }
894        NodePosIterator iterator = inputs().withNullIterator();
895        while (iterator.hasNext()) {
896            Position pos = iterator.nextPosition();
897            assert pos.isInputOptional() || pos.get(this) != null : "non-optional input " + pos.getName() + " cannot be null in " + this + " (fix nullness or use @OptionalInput)";
898        }
899        if (predecessor != null) {
900            assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor);
901            assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor);
902        }
903        return true;
904    }
905
906    public boolean assertTrue(boolean condition, String message, Object... args) {
907        if (condition) {
908            return true;
909        } else {
910            throw fail(message, args);
911        }
912    }
913
914    public boolean assertFalse(boolean condition, String message, Object... args) {
915        if (condition) {
916            throw fail(message, args);
917        } else {
918            return true;
919        }
920    }
921
922    protected VerificationError fail(String message, Object... args) throws GraalGraphJVMCIError {
923        throw new VerificationError(message, args).addContext(this);
924    }
925
926    public Iterable<? extends Node> cfgPredecessors() {
927        if (predecessor == null) {
928            return Collections.emptySet();
929        } else {
930            return Collections.singleton(predecessor);
931        }
932    }
933
934    /**
935     * Returns an iterator that will provide all control-flow successors of this node. Normally this
936     * will be the contents of all fields marked as NodeSuccessor, but some node classes (like
937     * EndNode) may return different nodes. Note that the iterator may generate null values if the
938     * fields contain them.
939     */
940    public Iterable<? extends Node> cfgSuccessors() {
941        return successors();
942    }
943
944    /**
945     * Nodes always use an {@linkplain System#identityHashCode(Object) identity} hash code.
946     */
947    @Override
948    public final int hashCode() {
949        return System.identityHashCode(this);
950    }
951
952    /**
953     * Equality tests must rely solely on identity.
954     */
955    @Override
956    public final boolean equals(Object obj) {
957        return super.equals(obj);
958    }
959
960    /**
961     * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the
962     * ideal graph visualizer).
963     */
964    public final Map<Object, Object> getDebugProperties() {
965        return getDebugProperties(new HashMap<>());
966    }
967
968    /**
969     * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the
970     * ideal graph visualizer). Subclasses overriding this method should also fill the map using
971     * their superclass.
972     *
973     * @param map
974     */
975    public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
976        Fields properties = getNodeClass().getData();
977        for (int i = 0; i < properties.getCount(); i++) {
978            map.put(properties.getName(i), properties.get(this, i));
979        }
980        return map;
981    }
982
983    /**
984     * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}.
985     */
986    @Override
987    public final String toString() {
988        return toString(Verbosity.Short);
989    }
990
991    /**
992     * Creates a String representation for this node with a given {@link Verbosity}.
993     */
994    public String toString(Verbosity verbosity) {
995        switch (verbosity) {
996            case Id:
997                return Integer.toString(id);
998            case Name:
999                return getNodeClass().shortName();
1000            case Short:
1001                return toString(Verbosity.Id) + "|" + toString(Verbosity.Name);
1002            case Long:
1003                return toString(Verbosity.Short);
1004            case Debugger:
1005            case All: {
1006                StringBuilder str = new StringBuilder();
1007                str.append(toString(Verbosity.Short)).append(" { ");
1008                for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) {
1009                    str.append(entry.getKey()).append("=").append(entry.getValue()).append(", ");
1010                }
1011                str.append(" }");
1012                return str.toString();
1013            }
1014            default:
1015                throw new RuntimeException("unknown verbosity: " + verbosity);
1016        }
1017    }
1018
1019    @Deprecated
1020    public int getId() {
1021        return id;
1022    }
1023
1024    @Override
1025    public void formatTo(Formatter formatter, int flags, int width, int precision) {
1026        if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) {
1027            formatter.format("%s", toString(Verbosity.Id));
1028        } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) {
1029            // Use All here since Long is only slightly longer than Short.
1030            formatter.format("%s", toString(Verbosity.All));
1031        } else {
1032            formatter.format("%s", toString(Verbosity.Short));
1033        }
1034
1035        boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY);
1036        int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0);
1037        if (width > 0) {
1038            if (this.predecessor != null) {
1039                formatter.format(" pred={");
1040                this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0);
1041                formatter.format("}");
1042            }
1043
1044            NodePosIterator inputIter = inputs().iterator();
1045            while (inputIter.hasNext()) {
1046                Position position = inputIter.nextPosition();
1047                Node input = position.get(this);
1048                if (input != null) {
1049                    formatter.format(" ");
1050                    formatter.format(position.getName());
1051                    formatter.format("={");
1052                    input.formatTo(formatter, neighborsFlags, width - 1, 0);
1053                    formatter.format("}");
1054                }
1055            }
1056        }
1057
1058        if (precision > 0) {
1059            if (!hasNoUsages()) {
1060                formatter.format(" usages={");
1061                int z = 0;
1062                for (Node usage : usages()) {
1063                    if (z != 0) {
1064                        formatter.format(", ");
1065                    }
1066                    usage.formatTo(formatter, neighborsFlags, 0, precision - 1);
1067                    ++z;
1068                }
1069                formatter.format("}");
1070            }
1071
1072            NodePosIterator succIter = successors().iterator();
1073            while (succIter.hasNext()) {
1074                Position position = succIter.nextPosition();
1075                Node successor = position.get(this);
1076                if (successor != null) {
1077                    formatter.format(" ");
1078                    formatter.format(position.getName());
1079                    formatter.format("={");
1080                    successor.formatTo(formatter, neighborsFlags, 0, precision - 1);
1081                    formatter.format("}");
1082                }
1083            }
1084        }
1085    }
1086
1087    /**
1088     * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data
1089     * fields of another node of the same type. Primitive fields are compared by value and
1090     * non-primitive fields are compared by {@link Objects#equals(Object, Object)}.
1091     *
1092     * The result of this method undefined if {@code other.getClass() != this.getClass()}.
1093     *
1094     * @param other a node of exactly the same type as this node
1095     * @return true if the data fields of this object and {@code other} are equal
1096     */
1097    public boolean valueEquals(Node other) {
1098        return getNodeClass().dataEquals(this, other);
1099    }
1100
1101    public final void pushInputs(NodeStack stack) {
1102        getNodeClass().getInputEdges().pushAll(this, stack);
1103    }
1104}