| /* |
| * Copyright (c) 2011, 2015, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| |
| package org.graalvm.compiler.graph; |
| |
| import static org.graalvm.compiler.graph.Edges.Type.Inputs; |
| import static org.graalvm.compiler.graph.Edges.Type.Successors; |
| import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled; |
| import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE; |
| |
| import java.lang.annotation.ElementType; |
| import java.lang.annotation.RetentionPolicy; |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.EnumSet; |
| import java.util.Formattable; |
| import java.util.FormattableFlags; |
| import java.util.Formatter; |
| import java.util.HashMap; |
| import java.util.Map; |
| import java.util.Objects; |
| import java.util.function.Predicate; |
| import java.util.function.Supplier; |
| |
| import org.graalvm.compiler.core.common.Fields; |
| import org.graalvm.compiler.core.common.type.AbstractPointerStamp; |
| import org.graalvm.compiler.core.common.type.Stamp; |
| import org.graalvm.compiler.debug.DebugCloseable; |
| import org.graalvm.compiler.debug.DebugContext; |
| import org.graalvm.compiler.graph.Graph.NodeEventListener; |
| import org.graalvm.compiler.graph.Graph.Options; |
| import org.graalvm.compiler.graph.iterators.NodeIterable; |
| import org.graalvm.compiler.graph.iterators.NodePredicate; |
| import org.graalvm.compiler.graph.spi.Simplifiable; |
| import org.graalvm.compiler.graph.spi.SimplifierTool; |
| import org.graalvm.compiler.nodeinfo.InputType; |
| import org.graalvm.compiler.nodeinfo.NodeCycles; |
| import org.graalvm.compiler.nodeinfo.NodeInfo; |
| import org.graalvm.compiler.nodeinfo.NodeSize; |
| import org.graalvm.compiler.nodeinfo.Verbosity; |
| import org.graalvm.compiler.options.OptionValues; |
| |
| import sun.misc.Unsafe; |
| |
| /** |
| * This class is the base class for all nodes. It represents a node that can be inserted in a |
| * {@link Graph}. |
| * <p> |
| * Once a node has been added to a graph, it has a graph-unique {@link #id()}. Edges in the |
| * subclasses are represented with annotated fields. There are two kind of edges : {@link Input} and |
| * {@link Successor}. If a field, of a type compatible with {@link Node}, annotated with either |
| * {@link Input} and {@link Successor} is not null, then there is an edge from this node to the node |
| * this field points to. |
| * <p> |
| * Nodes which are be value numberable should implement the {@link ValueNumberable} interface. |
| * |
| * <h1>Assertions and Verification</h1> |
| * |
| * The Node class supplies the {@link #assertTrue(boolean, String, Object...)} and |
| * {@link #assertFalse(boolean, String, Object...)} methods, which will check the supplied boolean |
| * and throw a VerificationError if it has the wrong value. Both methods will always either throw an |
| * exception or return true. They can thus be used within an assert statement, so that the check is |
| * only performed if assertions are enabled. |
| */ |
| @NodeInfo |
| public abstract class Node implements Cloneable, Formattable, NodeInterface { |
| |
| public static final NodeClass<?> TYPE = null; |
| |
| public static final boolean TRACK_CREATION_POSITION = Boolean.getBoolean("debug.graal.TrackNodeCreationPosition"); |
| |
| static final int DELETED_ID_START = -1000000000; |
| static final int INITIAL_ID = -1; |
| static final int ALIVE_ID_START = 0; |
| |
| // The use of fully qualified class names here and in the rest |
| // of this file works around a problem javac has resolving symbols |
| |
| /** |
| * Denotes a non-optional (non-null) node input. This should be applied to exactly the fields of |
| * a node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of |
| * type {@link Node} outside of their constructor should call |
| * {@link Node#updateUsages(Node, Node)} just prior to doing the update of the input. |
| */ |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.FIELD) |
| public static @interface Input { |
| InputType value() default InputType.Value; |
| } |
| |
| /** |
| * Denotes an optional (nullable) node input. This should be applied to exactly the fields of a |
| * node that are of type {@link Node} or {@link NodeInputList}. Nodes that update fields of type |
| * {@link Node} outside of their constructor should call {@link Node#updateUsages(Node, Node)} |
| * just prior to doing the update of the input. |
| */ |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.FIELD) |
| public static @interface OptionalInput { |
| InputType value() default InputType.Value; |
| } |
| |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.FIELD) |
| public static @interface Successor { |
| } |
| |
| /** |
| * Denotes that a parameter of an {@linkplain NodeIntrinsic intrinsic} method must be a compile |
| * time constant at all call sites to the intrinsic method. |
| */ |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.PARAMETER) |
| public static @interface ConstantNodeParameter { |
| } |
| |
| /** |
| * Denotes an injected parameter in a {@linkplain NodeIntrinsic node intrinsic} constructor. If |
| * the constructor is called as part of node intrinsification, the node intrinsifier will inject |
| * an argument for the annotated parameter. Injected parameters must precede all non-injected |
| * parameters in a constructor. If the type of the annotated parameter is {@link Stamp}, the |
| * {@linkplain Stamp#javaType type} of the injected stamp is the return type of the annotated |
| * method (which cannot be {@code void}). |
| */ |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.PARAMETER) |
| public static @interface InjectedNodeParameter { |
| } |
| |
| /** |
| * Annotates a method that can be replaced by a compiler intrinsic. A (resolved) call to the |
| * annotated method will be processed by a generated {@code InvocationPlugin} that calls either |
| * a factory method or a constructor corresponding with the annotated method. |
| * <p> |
| * A factory method corresponding to an annotated method is a static method named |
| * {@code intrinsify} defined in the class denoted by {@link #value()}. In order, its signature |
| * is as follows: |
| * <ol> |
| * <li>A {@code GraphBuilderContext} parameter.</li> |
| * <li>A {@code ResolvedJavaMethod} parameter.</li> |
| * <li>A sequence of zero or more {@linkplain InjectedNodeParameter injected} parameters.</li> |
| * <li>Remaining parameters that match the declared parameters of the annotated method.</li> |
| * </ol> |
| * A constructor corresponding to an annotated method is defined in the class denoted by |
| * {@link #value()}. In order, its signature is as follows: |
| * <ol> |
| * <li>A sequence of zero or more {@linkplain InjectedNodeParameter injected} parameters.</li> |
| * <li>Remaining parameters that match the declared parameters of the annotated method.</li> |
| * </ol> |
| * There must be exactly one such factory method or constructor corresponding to a |
| * {@link NodeIntrinsic} annotated method. |
| */ |
| @java.lang.annotation.Retention(RetentionPolicy.RUNTIME) |
| @java.lang.annotation.Target(ElementType.METHOD) |
| public static @interface NodeIntrinsic { |
| |
| /** |
| * The class declaring the factory method or {@link Node} subclass declaring the constructor |
| * used to intrinsify a call to the annotated method. The default value is the class in |
| * which the annotated method is declared. |
| */ |
| Class<?> value() default NodeIntrinsic.class; |
| |
| /** |
| * If {@code true}, the factory method or constructor selected by the annotation must have |
| * an {@linkplain InjectedNodeParameter injected} {@link Stamp} parameter. Calling |
| * {@link AbstractPointerStamp#nonNull()} on the injected stamp is guaranteed to return |
| * {@code true}. |
| */ |
| boolean injectedStampIsNonNull() default false; |
| } |
| |
| /** |
| * Marker for a node that can be replaced by another node via global value numbering. A |
| * {@linkplain NodeClass#isLeafNode() leaf} node can be replaced by another node of the same |
| * type that has exactly the same {@linkplain NodeClass#getData() data} values. A non-leaf node |
| * can be replaced by another node of the same type that has exactly the same data values as |
| * well as the same {@linkplain Node#inputs() inputs} and {@linkplain Node#successors() |
| * successors}. |
| */ |
| public interface ValueNumberable { |
| } |
| |
| /** |
| * Marker interface for nodes that contains other nodes. When the inputs to this node changes, |
| * users of this node should also be placed on the work list for canonicalization. |
| */ |
| public interface IndirectCanonicalization { |
| } |
| |
| private Graph graph; |
| int id; |
| |
| // this next pointer is used in Graph to implement fast iteration over NodeClass types, it |
| // therefore points to the next Node of the same type. |
| Node typeCacheNext; |
| |
| static final int INLINE_USAGE_COUNT = 2; |
| private static final Node[] NO_NODES = {}; |
| |
| /** |
| * Head of usage list. The elements of the usage list in order are {@link #usage0}, |
| * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list. |
| */ |
| Node usage0; |
| Node usage1; |
| Node[] extraUsages; |
| int extraUsagesCount; |
| |
| private Node predecessor; |
| private NodeClass<? extends Node> nodeClass; |
| |
| public static final int NODE_LIST = -2; |
| public static final int NOT_ITERABLE = -1; |
| |
| static class NodeStackTrace { |
| final StackTraceElement[] stackTrace; |
| |
| NodeStackTrace() { |
| this.stackTrace = new Throwable().getStackTrace(); |
| } |
| |
| private String getString(String label) { |
| StringBuilder sb = new StringBuilder(); |
| if (label != null) { |
| sb.append(label).append(": "); |
| } |
| for (StackTraceElement ste : stackTrace) { |
| sb.append("at ").append(ste.toString()).append('\n'); |
| } |
| return sb.toString(); |
| } |
| |
| String getStrackTraceString() { |
| return getString(null); |
| } |
| |
| @Override |
| public String toString() { |
| return getString(getClass().getSimpleName()); |
| } |
| } |
| |
| static class NodeCreationStackTrace extends NodeStackTrace { |
| } |
| |
| public static class NodeInsertionStackTrace extends NodeStackTrace { |
| } |
| |
| public Node(NodeClass<? extends Node> c) { |
| init(c); |
| } |
| |
| final void init(NodeClass<? extends Node> c) { |
| assert c.getJavaClass() == this.getClass(); |
| this.nodeClass = c; |
| id = INITIAL_ID; |
| extraUsages = NO_NODES; |
| if (TRACK_CREATION_POSITION) { |
| setCreationPosition(new NodeCreationStackTrace()); |
| } |
| } |
| |
| final int id() { |
| return id; |
| } |
| |
| @Override |
| public Node asNode() { |
| return this; |
| } |
| |
| /** |
| * Gets the graph context of this node. |
| */ |
| public Graph graph() { |
| return graph; |
| } |
| |
| /** |
| * Gets the option values associated with this node's graph. |
| */ |
| public final OptionValues getOptions() { |
| return graph == null ? null : graph.getOptions(); |
| } |
| |
| /** |
| * Gets the debug context associated with this node's graph. |
| */ |
| public final DebugContext getDebug() { |
| return graph.getDebug(); |
| } |
| |
| /** |
| * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null input |
| * edges of this node. |
| * |
| * @return an {@link NodeIterable iterable} for all non-null input edges. |
| */ |
| public NodeIterable<Node> inputs() { |
| return nodeClass.getInputIterable(this); |
| } |
| |
| /** |
| * Returns an {@link Iterable iterable} which can be used to traverse all non-null input edges |
| * of this node. |
| * |
| * @return an {@link Iterable iterable} for all non-null input edges. |
| */ |
| public Iterable<Position> inputPositions() { |
| return nodeClass.getInputEdges().getPositionsIterable(this); |
| } |
| |
| public abstract static class EdgeVisitor { |
| |
| public abstract Node apply(Node source, Node target); |
| |
| } |
| |
| /** |
| * Applies the given visitor to all inputs of this node. |
| * |
| * @param visitor the visitor to be applied to the inputs |
| */ |
| public void applyInputs(EdgeVisitor visitor) { |
| nodeClass.applyInputs(this, visitor); |
| } |
| |
| /** |
| * Applies the given visitor to all successors of this node. |
| * |
| * @param visitor the visitor to be applied to the successors |
| */ |
| public void applySuccessors(EdgeVisitor visitor) { |
| nodeClass.applySuccessors(this, visitor); |
| } |
| |
| /** |
| * Returns an {@link NodeIterable iterable} which can be used to traverse all non-null successor |
| * edges of this node. |
| * |
| * @return an {@link NodeIterable iterable} for all non-null successor edges. |
| */ |
| public NodeIterable<Node> successors() { |
| assert !this.isDeleted() : this; |
| return nodeClass.getSuccessorIterable(this); |
| } |
| |
| /** |
| * Returns an {@link Iterable iterable} which can be used to traverse all successor edge |
| * positions of this node. |
| * |
| * @return an {@link Iterable iterable} for all successor edge positoins. |
| */ |
| public Iterable<Position> successorPositions() { |
| return nodeClass.getSuccessorEdges().getPositionsIterable(this); |
| } |
| |
| /** |
| * Gets the maximum number of usages this node has had at any point in time. |
| */ |
| public int getUsageCount() { |
| if (usage0 == null) { |
| return 0; |
| } |
| if (usage1 == null) { |
| return 1; |
| } |
| return INLINE_USAGE_COUNT + extraUsagesCount; |
| } |
| |
| /** |
| * Gets the list of nodes that use this node (i.e., as an input). |
| */ |
| public final NodeIterable<Node> usages() { |
| return new NodeUsageIterable(this); |
| } |
| |
| /** |
| * Checks whether this node has no usages. |
| */ |
| public final boolean hasNoUsages() { |
| return this.usage0 == null; |
| } |
| |
| /** |
| * Checks whether this node has usages. |
| */ |
| public final boolean hasUsages() { |
| return this.usage0 != null; |
| } |
| |
| /** |
| * Checks whether this node has more than one usages. |
| */ |
| public final boolean hasMoreThanOneUsage() { |
| return this.usage1 != null; |
| } |
| |
| /** |
| * Checks whether this node has exactly one usgae. |
| */ |
| public final boolean hasExactlyOneUsage() { |
| return hasUsages() && !hasMoreThanOneUsage(); |
| } |
| |
| /** |
| * Adds a given node to this node's {@linkplain #usages() usages}. |
| * |
| * @param node the node to add |
| */ |
| void addUsage(Node node) { |
| incUsageModCount(); |
| if (usage0 == null) { |
| usage0 = node; |
| } else if (usage1 == null) { |
| usage1 = node; |
| } else { |
| int length = extraUsages.length; |
| if (length == 0) { |
| extraUsages = new Node[4]; |
| } else if (extraUsagesCount == length) { |
| Node[] newExtraUsages = new Node[length * 2 + 1]; |
| System.arraycopy(extraUsages, 0, newExtraUsages, 0, length); |
| extraUsages = newExtraUsages; |
| } |
| extraUsages[extraUsagesCount++] = node; |
| } |
| } |
| |
| private void movUsageFromEndTo(int destIndex) { |
| if (destIndex >= INLINE_USAGE_COUNT) { |
| movUsageFromEndToExtraUsages(destIndex - INLINE_USAGE_COUNT); |
| } else if (destIndex == 1) { |
| movUsageFromEndToIndexOne(); |
| } else { |
| assert destIndex == 0; |
| movUsageFromEndToIndexZero(); |
| } |
| } |
| |
| private void movUsageFromEndToExtraUsages(int destExtraIndex) { |
| this.extraUsagesCount--; |
| Node n = extraUsages[extraUsagesCount]; |
| extraUsages[destExtraIndex] = n; |
| extraUsages[extraUsagesCount] = null; |
| } |
| |
| private void movUsageFromEndToIndexZero() { |
| if (extraUsagesCount > 0) { |
| this.extraUsagesCount--; |
| usage0 = extraUsages[extraUsagesCount]; |
| extraUsages[extraUsagesCount] = null; |
| } else if (usage1 != null) { |
| usage0 = usage1; |
| usage1 = null; |
| } else { |
| usage0 = null; |
| } |
| } |
| |
| private void movUsageFromEndToIndexOne() { |
| if (extraUsagesCount > 0) { |
| this.extraUsagesCount--; |
| usage1 = extraUsages[extraUsagesCount]; |
| extraUsages[extraUsagesCount] = null; |
| } else { |
| assert usage1 != null; |
| usage1 = null; |
| } |
| } |
| |
| /** |
| * Removes a given node from this node's {@linkplain #usages() usages}. |
| * |
| * @param node the node to remove |
| * @return whether or not {@code usage} was in the usage list |
| */ |
| public boolean removeUsage(Node node) { |
| assert node != null; |
| // For large graphs, usage removal is performance critical. |
| // Furthermore, it is critical that this method maintains the invariant that the usage list |
| // has no null element preceding a non-null element. |
| incUsageModCount(); |
| if (usage0 == node) { |
| movUsageFromEndToIndexZero(); |
| return true; |
| } |
| if (usage1 == node) { |
| movUsageFromEndToIndexOne(); |
| return true; |
| } |
| for (int i = this.extraUsagesCount - 1; i >= 0; i--) { |
| if (extraUsages[i] == node) { |
| movUsageFromEndToExtraUsages(i); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| public final Node predecessor() { |
| return predecessor; |
| } |
| |
| public final int modCount() { |
| if (isModificationCountsEnabled() && graph != null) { |
| return graph.modCount(this); |
| } |
| return 0; |
| } |
| |
| final void incModCount() { |
| if (isModificationCountsEnabled() && graph != null) { |
| graph.incModCount(this); |
| } |
| } |
| |
| final int usageModCount() { |
| if (isModificationCountsEnabled() && graph != null) { |
| return graph.usageModCount(this); |
| } |
| return 0; |
| } |
| |
| final void incUsageModCount() { |
| if (isModificationCountsEnabled() && graph != null) { |
| graph.incUsageModCount(this); |
| } |
| } |
| |
| public final boolean isDeleted() { |
| return id <= DELETED_ID_START; |
| } |
| |
| public final boolean isAlive() { |
| return id >= ALIVE_ID_START; |
| } |
| |
| public final boolean isUnregistered() { |
| return id == INITIAL_ID; |
| } |
| |
| /** |
| * Updates the usages sets of the given nodes after an input slot is changed from |
| * {@code oldInput} to {@code newInput} by removing this node from {@code oldInput}'s usages and |
| * adds this node to {@code newInput}'s usages. |
| */ |
| protected void updateUsages(Node oldInput, Node newInput) { |
| assert isAlive() && (newInput == null || newInput.isAlive()) : "adding " + newInput + " to " + this + " instead of " + oldInput; |
| if (oldInput != newInput) { |
| if (oldInput != null) { |
| boolean result = removeThisFromUsages(oldInput); |
| assert assertTrue(result, "not found in usages, old input: %s", oldInput); |
| } |
| maybeNotifyInputChanged(this); |
| if (newInput != null) { |
| newInput.addUsage(this); |
| } |
| if (oldInput != null && oldInput.hasNoUsages()) { |
| maybeNotifyZeroUsages(oldInput); |
| } |
| } |
| } |
| |
| protected void updateUsagesInterface(NodeInterface oldInput, NodeInterface newInput) { |
| updateUsages(oldInput == null ? null : oldInput.asNode(), newInput == null ? null : newInput.asNode()); |
| } |
| |
| /** |
| * Updates the predecessor of the given nodes after a successor slot is changed from |
| * oldSuccessor to newSuccessor: removes this node from oldSuccessor's predecessors and adds |
| * this node to newSuccessor's predecessors. |
| */ |
| protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) { |
| assert isAlive() && (newSuccessor == null || newSuccessor.isAlive()) || newSuccessor == null && !isAlive() : "adding " + newSuccessor + " to " + this + " instead of " + oldSuccessor; |
| assert graph == null || !graph.isFrozen(); |
| if (oldSuccessor != newSuccessor) { |
| if (oldSuccessor != null) { |
| assert assertTrue(newSuccessor == null || oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s, should be %s", oldSuccessor, oldSuccessor.predecessor, this); |
| oldSuccessor.predecessor = null; |
| } |
| if (newSuccessor != null) { |
| assert assertTrue(newSuccessor.predecessor == null, "unexpected non-null predecessor in new successor (%s): %s, this=%s", newSuccessor, newSuccessor.predecessor, this); |
| newSuccessor.predecessor = this; |
| } |
| } |
| } |
| |
| void initialize(Graph newGraph) { |
| assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id); |
| this.graph = newGraph; |
| newGraph.register(this); |
| NodeClass<? extends Node> nc = nodeClass; |
| nc.registerAtInputsAsUsage(this); |
| nc.registerAtSuccessorsAsPredecessor(this); |
| } |
| |
| /** |
| * Information associated with this node. A single value is stored directly in the field. |
| * Multiple values are stored by creating an Object[]. |
| */ |
| private Object annotation; |
| |
| private <T> T getNodeInfo(Class<T> clazz) { |
| assert clazz != Object[].class; |
| if (annotation == null) { |
| return null; |
| } |
| if (clazz.isInstance(annotation)) { |
| return clazz.cast(annotation); |
| } |
| if (annotation.getClass() == Object[].class) { |
| Object[] annotations = (Object[]) annotation; |
| for (Object ann : annotations) { |
| if (clazz.isInstance(ann)) { |
| return clazz.cast(ann); |
| } |
| } |
| } |
| return null; |
| } |
| |
| private <T> void setNodeInfo(Class<T> clazz, T value) { |
| assert clazz != Object[].class; |
| if (annotation == null || clazz.isInstance(annotation)) { |
| // Replace the current value |
| this.annotation = value; |
| } else if (annotation.getClass() == Object[].class) { |
| Object[] annotations = (Object[]) annotation; |
| for (int i = 0; i < annotations.length; i++) { |
| if (clazz.isInstance(annotations[i])) { |
| annotations[i] = value; |
| return; |
| } |
| } |
| Object[] newAnnotations = Arrays.copyOf(annotations, annotations.length + 1); |
| newAnnotations[annotations.length] = value; |
| this.annotation = newAnnotations; |
| } else { |
| this.annotation = new Object[]{this.annotation, value}; |
| } |
| } |
| |
| /** |
| * Gets the source position information for this node or null if it doesn't exist. |
| */ |
| |
| public NodeSourcePosition getNodeSourcePosition() { |
| return getNodeInfo(NodeSourcePosition.class); |
| } |
| |
| /** |
| * Set the source position to {@code sourcePosition}. Setting it to null is ignored so that it's |
| * not accidentally cleared. Use {@link #clearNodeSourcePosition()} instead. |
| */ |
| public void setNodeSourcePosition(NodeSourcePosition sourcePosition) { |
| if (sourcePosition == null) { |
| return; |
| } |
| setNodeInfo(NodeSourcePosition.class, sourcePosition); |
| } |
| |
| public void clearNodeSourcePosition() { |
| setNodeInfo(NodeSourcePosition.class, null); |
| } |
| |
| public NodeCreationStackTrace getCreationPosition() { |
| return getNodeInfo(NodeCreationStackTrace.class); |
| } |
| |
| public void setCreationPosition(NodeCreationStackTrace trace) { |
| setNodeInfo(NodeCreationStackTrace.class, trace); |
| } |
| |
| public NodeInsertionStackTrace getInsertionPosition() { |
| return getNodeInfo(NodeInsertionStackTrace.class); |
| } |
| |
| public void setInsertionPosition(NodeInsertionStackTrace trace) { |
| setNodeInfo(NodeInsertionStackTrace.class, trace); |
| } |
| |
| /** |
| * Update the source position only if it is null. |
| */ |
| public void updateNodeSourcePosition(Supplier<NodeSourcePosition> sourcePositionSupp) { |
| if (this.getNodeSourcePosition() == null) { |
| setNodeSourcePosition(sourcePositionSupp.get()); |
| } |
| } |
| |
| public DebugCloseable withNodeSourcePosition() { |
| return graph.withNodeSourcePosition(this); |
| } |
| |
| public final NodeClass<? extends Node> getNodeClass() { |
| return nodeClass; |
| } |
| |
| public boolean isAllowedUsageType(InputType type) { |
| if (type == InputType.Value) { |
| return false; |
| } |
| return getNodeClass().getAllowedUsageTypes().contains(type); |
| } |
| |
| private boolean checkReplaceWith(Node other) { |
| if (graph != null && graph.isFrozen()) { |
| fail("cannot modify frozen graph"); |
| } |
| if (other == this) { |
| fail("cannot replace a node with itself"); |
| } |
| if (isDeleted()) { |
| fail("cannot replace deleted node"); |
| } |
| if (other != null && other.isDeleted()) { |
| fail("cannot replace with deleted node %s", other); |
| } |
| return true; |
| } |
| |
| public final void replaceAtUsages(Node other) { |
| replaceAtAllUsages(other, (Node) null); |
| } |
| |
| public final void replaceAtUsages(Node other, Predicate<Node> filter) { |
| replaceAtUsages(other, filter, null); |
| } |
| |
| public final void replaceAtUsagesAndDelete(Node other) { |
| replaceAtUsages(other, null, this); |
| safeDelete(); |
| } |
| |
| public final void replaceAtUsagesAndDelete(Node other, Predicate<Node> filter) { |
| replaceAtUsages(other, filter, this); |
| safeDelete(); |
| } |
| |
| protected void replaceAtUsages(Node other, Predicate<Node> filter, Node toBeDeleted) { |
| if (filter == null) { |
| replaceAtAllUsages(other, toBeDeleted); |
| } else { |
| replaceAtMatchingUsages(other, filter, toBeDeleted); |
| } |
| } |
| |
| protected void replaceAtAllUsages(Node other, Node toBeDeleted) { |
| checkReplaceWith(other); |
| if (usage0 == null) { |
| return; |
| } |
| replaceAtUsage(other, toBeDeleted, usage0); |
| usage0 = null; |
| |
| if (usage1 == null) { |
| return; |
| } |
| replaceAtUsage(other, toBeDeleted, usage1); |
| usage1 = null; |
| |
| if (extraUsagesCount <= 0) { |
| return; |
| } |
| for (int i = 0; i < extraUsagesCount; i++) { |
| Node usage = extraUsages[i]; |
| replaceAtUsage(other, toBeDeleted, usage); |
| } |
| this.extraUsages = NO_NODES; |
| this.extraUsagesCount = 0; |
| } |
| |
| private void replaceAtUsage(Node other, Node toBeDeleted, Node usage) { |
| boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other); |
| assert assertTrue(result, "not found in inputs, usage: %s", usage); |
| /* |
| * Don't notify for nodes which are about to be deleted. |
| */ |
| if (toBeDeleted == null || usage != toBeDeleted) { |
| maybeNotifyInputChanged(usage); |
| } |
| if (other != null) { |
| other.addUsage(usage); |
| } |
| } |
| |
| private void replaceAtMatchingUsages(Node other, Predicate<Node> filter, Node toBeDeleted) { |
| if (filter == null) { |
| fail("filter cannot be null"); |
| } |
| checkReplaceWith(other); |
| int i = 0; |
| while (i < this.getUsageCount()) { |
| Node usage = this.getUsageAt(i); |
| if (filter.test(usage)) { |
| replaceAtUsage(other, toBeDeleted, usage); |
| this.movUsageFromEndTo(i); |
| } else { |
| ++i; |
| } |
| } |
| } |
| |
| public Node getUsageAt(int index) { |
| if (index == 0) { |
| return this.usage0; |
| } else if (index == 1) { |
| return this.usage1; |
| } else { |
| return this.extraUsages[index - INLINE_USAGE_COUNT]; |
| } |
| } |
| |
| public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) { |
| checkReplaceWith(other); |
| replaceAtMatchingUsages(other, usagePredicate, null); |
| } |
| |
| public void replaceAtUsages(InputType type, Node other) { |
| checkReplaceWith(other); |
| for (Node usage : usages().snapshot()) { |
| for (Position pos : usage.inputPositions()) { |
| if (pos.getInputType() == type && pos.get(usage) == this) { |
| pos.set(usage, other); |
| } |
| } |
| } |
| } |
| |
| private void maybeNotifyInputChanged(Node node) { |
| if (graph != null) { |
| assert !graph.isFrozen(); |
| NodeEventListener listener = graph.nodeEventListener; |
| if (listener != null) { |
| listener.event(Graph.NodeEvent.INPUT_CHANGED, node); |
| } |
| } |
| } |
| |
| public void maybeNotifyZeroUsages(Node node) { |
| if (graph != null) { |
| assert !graph.isFrozen(); |
| NodeEventListener listener = graph.nodeEventListener; |
| if (listener != null && node.isAlive()) { |
| listener.event(Graph.NodeEvent.ZERO_USAGES, node); |
| } |
| } |
| } |
| |
| public void replaceAtPredecessor(Node other) { |
| checkReplaceWith(other); |
| if (predecessor != null) { |
| if (!predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other)) { |
| fail("not found in successors, predecessor: %s", predecessor); |
| } |
| predecessor.updatePredecessor(this, other); |
| } |
| } |
| |
| public void replaceAndDelete(Node other) { |
| checkReplaceWith(other); |
| if (other == null) { |
| fail("cannot replace with null"); |
| } |
| if (this.hasUsages()) { |
| replaceAtUsages(other); |
| } |
| replaceAtPredecessor(other); |
| this.safeDelete(); |
| } |
| |
| public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) { |
| if (nodeClass.replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) { |
| updatePredecessor(oldSuccessor, newSuccessor); |
| } |
| } |
| |
| public void replaceFirstInput(Node oldInput, Node newInput) { |
| if (nodeClass.replaceFirstInput(this, oldInput, newInput)) { |
| updateUsages(oldInput, newInput); |
| } |
| } |
| |
| public void clearInputs() { |
| assert assertFalse(isDeleted(), "cannot clear inputs of deleted node"); |
| getNodeClass().unregisterAtInputsAsUsage(this); |
| } |
| |
| boolean removeThisFromUsages(Node n) { |
| return n.removeUsage(this); |
| } |
| |
| public void clearSuccessors() { |
| assert assertFalse(isDeleted(), "cannot clear successors of deleted node"); |
| getNodeClass().unregisterAtSuccessorsAsPredecessor(this); |
| } |
| |
| private boolean checkDeletion() { |
| assertTrue(isAlive(), "must be alive"); |
| assertTrue(hasNoUsages(), "cannot delete node %s because of usages: %s", this, usages()); |
| assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor); |
| return true; |
| } |
| |
| /** |
| * Removes this node from its graph. This node must have no {@linkplain Node#usages() usages} |
| * and no {@linkplain #predecessor() predecessor}. |
| */ |
| public void safeDelete() { |
| assert checkDeletion(); |
| this.clearInputs(); |
| this.clearSuccessors(); |
| markDeleted(); |
| } |
| |
| public void markDeleted() { |
| graph.unregister(this); |
| id = DELETED_ID_START - id; |
| assert isDeleted(); |
| } |
| |
| public final Node copyWithInputs() { |
| return copyWithInputs(true); |
| } |
| |
| public final Node copyWithInputs(boolean insertIntoGraph) { |
| Node newNode = clone(insertIntoGraph ? graph : null, WithOnlyInputEdges); |
| if (insertIntoGraph) { |
| for (Node input : inputs()) { |
| input.addUsage(newNode); |
| } |
| } |
| return newNode; |
| } |
| |
| /** |
| * Must be overridden by subclasses that implement {@link Simplifiable}. The implementation in |
| * {@link Node} exists to obviate the need to cast a node before invoking |
| * {@link Simplifiable#simplify(SimplifierTool)}. |
| * |
| * @param tool |
| */ |
| public void simplify(SimplifierTool tool) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * @param newNode the result of cloning this node or {@link Unsafe#allocateInstance(Class) raw |
| * allocating} a copy of this node |
| * @param type the type of edges to process |
| * @param edgesToCopy if {@code type} is in this set, the edges are copied otherwise they are |
| * cleared |
| */ |
| private void copyOrClearEdgesForClone(Node newNode, Edges.Type type, EnumSet<Edges.Type> edgesToCopy) { |
| if (edgesToCopy.contains(type)) { |
| getNodeClass().getEdges(type).copy(this, newNode); |
| } else { |
| // The direct edges are already null |
| getNodeClass().getEdges(type).initializeLists(newNode, this); |
| } |
| } |
| |
| public static final EnumSet<Edges.Type> WithNoEdges = EnumSet.noneOf(Edges.Type.class); |
| public static final EnumSet<Edges.Type> WithAllEdges = EnumSet.allOf(Edges.Type.class); |
| public static final EnumSet<Edges.Type> WithOnlyInputEdges = EnumSet.of(Inputs); |
| public static final EnumSet<Edges.Type> WithOnlySucessorEdges = EnumSet.of(Successors); |
| |
| /** |
| * Makes a copy of this node in(to) a given graph. |
| * |
| * @param into the graph in which the copy will be registered (which may be this node's graph) |
| * or null if the copy should not be registered in a graph |
| * @param edgesToCopy specifies the edges to be copied. The edges not specified in this set are |
| * initialized to their default value (i.e., {@code null} for a direct edge, an empty |
| * list for an edge list) |
| * @return the copy of this node |
| */ |
| final Node clone(Graph into, EnumSet<Edges.Type> edgesToCopy) { |
| final NodeClass<? extends Node> nodeClassTmp = getNodeClass(); |
| boolean useIntoLeafNodeCache = false; |
| if (into != null) { |
| if (nodeClassTmp.valueNumberable() && nodeClassTmp.isLeafNode()) { |
| useIntoLeafNodeCache = true; |
| Node otherNode = into.findNodeInCache(this); |
| if (otherNode != null) { |
| return otherNode; |
| } |
| } |
| } |
| |
| Node newNode = null; |
| try { |
| newNode = (Node) UNSAFE.allocateInstance(getClass()); |
| newNode.nodeClass = nodeClassTmp; |
| nodeClassTmp.getData().copy(this, newNode); |
| copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy); |
| copyOrClearEdgesForClone(newNode, Successors, edgesToCopy); |
| } catch (Exception e) { |
| throw new GraalGraphError(e).addContext(this); |
| } |
| newNode.graph = into; |
| newNode.id = INITIAL_ID; |
| if (getNodeSourcePosition() != null && (into == null || into.updateNodeSourcePosition())) { |
| newNode.setNodeSourcePosition(getNodeSourcePosition()); |
| } |
| if (into != null) { |
| into.register(newNode); |
| } |
| newNode.extraUsages = NO_NODES; |
| |
| if (into != null && useIntoLeafNodeCache) { |
| into.putNodeIntoCache(newNode); |
| } |
| newNode.afterClone(this); |
| return newNode; |
| } |
| |
| protected void afterClone(@SuppressWarnings("unused") Node other) { |
| } |
| |
| protected boolean verifyInputs() { |
| for (Position pos : inputPositions()) { |
| Node input = pos.get(this); |
| if (input == null) { |
| assertTrue(pos.isInputOptional(), "non-optional input %s cannot be null in %s (fix nullness or use @OptionalInput)", pos, this); |
| } else { |
| assertFalse(input.isDeleted(), "input was deleted %s", input); |
| assertTrue(input.isAlive(), "input is not alive yet, i.e., it was not yet added to the graph"); |
| assertTrue(pos.getInputType() == InputType.Unchecked || input.isAllowedUsageType(pos.getInputType()), "invalid usage type %s %s", input, pos.getInputType()); |
| } |
| } |
| return true; |
| } |
| |
| public boolean verify() { |
| assertTrue(isAlive(), "cannot verify inactive nodes (id=%d)", id); |
| assertTrue(graph() != null, "null graph"); |
| verifyInputs(); |
| if (Options.VerifyGraalGraphEdges.getValue(getOptions())) { |
| verifyEdges(); |
| } |
| return true; |
| } |
| |
| public boolean verifySourcePosition() { |
| return true; |
| } |
| |
| /** |
| * Perform expensive verification of inputs, usages, predecessors and successors. |
| * |
| * @return true |
| */ |
| public boolean verifyEdges() { |
| for (Node input : inputs()) { |
| assertTrue(input == null || input.usages().contains(this), "missing usage of %s in input %s", this, input); |
| } |
| |
| for (Node successor : successors()) { |
| assertTrue(successor.predecessor() == this, "missing predecessor in %s (actual: %s)", successor, successor.predecessor()); |
| assertTrue(successor.graph() == graph(), "mismatching graph in successor %s", successor); |
| } |
| for (Node usage : usages()) { |
| assertFalse(usage.isDeleted(), "usage %s must never be deleted", usage); |
| assertTrue(usage.inputs().contains(this), "missing input in usage %s", usage); |
| boolean foundThis = false; |
| for (Position pos : usage.inputPositions()) { |
| if (pos.get(usage) == this) { |
| foundThis = true; |
| if (pos.getInputType() != InputType.Unchecked) { |
| assertTrue(isAllowedUsageType(pos.getInputType()), "invalid input of type %s from %s to %s (%s)", pos.getInputType(), usage, this, pos.getName()); |
| } |
| } |
| } |
| assertTrue(foundThis, "missing input in usage %s", usage); |
| } |
| |
| if (predecessor != null) { |
| assertFalse(predecessor.isDeleted(), "predecessor %s must never be deleted", predecessor); |
| assertTrue(predecessor.successors().contains(this), "missing successor in predecessor %s", predecessor); |
| } |
| return true; |
| } |
| |
| public boolean assertTrue(boolean condition, String message, Object... args) { |
| if (condition) { |
| return true; |
| } else { |
| throw fail(message, args); |
| } |
| } |
| |
| public boolean assertFalse(boolean condition, String message, Object... args) { |
| if (condition) { |
| throw fail(message, args); |
| } else { |
| return true; |
| } |
| } |
| |
| protected VerificationError fail(String message, Object... args) throws GraalGraphError { |
| throw new VerificationError(message, args).addContext(this); |
| } |
| |
| public Iterable<? extends Node> cfgPredecessors() { |
| if (predecessor == null) { |
| return Collections.emptySet(); |
| } else { |
| return Collections.singleton(predecessor); |
| } |
| } |
| |
| /** |
| * Returns an iterator that will provide all control-flow successors of this node. Normally this |
| * will be the contents of all fields annotated with {@link Successor}, but some node classes |
| * (like EndNode) may return different nodes. |
| */ |
| public Iterable<? extends Node> cfgSuccessors() { |
| return successors(); |
| } |
| |
| /** |
| * Nodes using their {@link #id} as the hash code. This works very well when nodes of the same |
| * graph are stored in sets. It can give bad behavior when storing nodes of different graphs in |
| * the same set. |
| */ |
| @Override |
| public final int hashCode() { |
| assert !this.isUnregistered() : "node not yet constructed"; |
| if (this.isDeleted()) { |
| return -id + DELETED_ID_START; |
| } |
| return id; |
| } |
| |
| /** |
| * Do not overwrite the equality test of a node in subclasses. Equality tests must rely solely |
| * on identity. |
| */ |
| |
| /** |
| * Provides a {@link Map} of properties of this node for use in debugging (e.g., to view in the |
| * ideal graph visualizer). |
| */ |
| public final Map<Object, Object> getDebugProperties() { |
| return getDebugProperties(new HashMap<>()); |
| } |
| |
| /** |
| * Fills a {@link Map} with properties of this node for use in debugging (e.g., to view in the |
| * ideal graph visualizer). Subclasses overriding this method should also fill the map using |
| * their superclass. |
| * |
| * @param map |
| */ |
| public Map<Object, Object> getDebugProperties(Map<Object, Object> map) { |
| Fields properties = getNodeClass().getData(); |
| for (int i = 0; i < properties.getCount(); i++) { |
| map.put(properties.getName(i), properties.get(this, i)); |
| } |
| NodeSourcePosition pos = getNodeSourcePosition(); |
| if (pos != null) { |
| map.put("nodeSourcePosition", pos); |
| } |
| NodeCreationStackTrace creation = getCreationPosition(); |
| if (creation != null) { |
| map.put("nodeCreationPosition", creation.getStrackTraceString()); |
| } |
| NodeInsertionStackTrace insertion = getInsertionPosition(); |
| if (insertion != null) { |
| map.put("nodeInsertionPosition", insertion.getStrackTraceString()); |
| } |
| return map; |
| } |
| |
| /** |
| * This method is a shortcut for {@link #toString(Verbosity)} with {@link Verbosity#Short}. |
| */ |
| @Override |
| public final String toString() { |
| return toString(Verbosity.Short); |
| } |
| |
| /** |
| * Creates a String representation for this node with a given {@link Verbosity}. |
| */ |
| public String toString(Verbosity verbosity) { |
| switch (verbosity) { |
| case Id: |
| return Integer.toString(id); |
| case Name: |
| return getNodeClass().shortName(); |
| case Short: |
| return toString(Verbosity.Id) + "|" + toString(Verbosity.Name); |
| case Long: |
| return toString(Verbosity.Short); |
| case Debugger: |
| case All: { |
| StringBuilder str = new StringBuilder(); |
| str.append(toString(Verbosity.Short)).append(" { "); |
| for (Map.Entry<Object, Object> entry : getDebugProperties().entrySet()) { |
| str.append(entry.getKey()).append("=").append(entry.getValue()).append(", "); |
| } |
| str.append(" }"); |
| return str.toString(); |
| } |
| default: |
| throw new RuntimeException("unknown verbosity: " + verbosity); |
| } |
| } |
| |
| @Deprecated |
| public int getId() { |
| return id; |
| } |
| |
| @Override |
| public void formatTo(Formatter formatter, int flags, int width, int precision) { |
| if ((flags & FormattableFlags.ALTERNATE) == FormattableFlags.ALTERNATE) { |
| formatter.format("%s", toString(Verbosity.Id)); |
| } else if ((flags & FormattableFlags.UPPERCASE) == FormattableFlags.UPPERCASE) { |
| // Use All here since Long is only slightly longer than Short. |
| formatter.format("%s", toString(Verbosity.All)); |
| } else { |
| formatter.format("%s", toString(Verbosity.Short)); |
| } |
| |
| boolean neighborsAlternate = ((flags & FormattableFlags.LEFT_JUSTIFY) == FormattableFlags.LEFT_JUSTIFY); |
| int neighborsFlags = (neighborsAlternate ? FormattableFlags.ALTERNATE | FormattableFlags.LEFT_JUSTIFY : 0); |
| if (width > 0) { |
| if (this.predecessor != null) { |
| formatter.format(" pred={"); |
| this.predecessor.formatTo(formatter, neighborsFlags, width - 1, 0); |
| formatter.format("}"); |
| } |
| |
| for (Position position : this.inputPositions()) { |
| Node input = position.get(this); |
| if (input != null) { |
| formatter.format(" "); |
| formatter.format(position.getName()); |
| formatter.format("={"); |
| input.formatTo(formatter, neighborsFlags, width - 1, 0); |
| formatter.format("}"); |
| } |
| } |
| } |
| |
| if (precision > 0) { |
| if (!hasNoUsages()) { |
| formatter.format(" usages={"); |
| int z = 0; |
| for (Node usage : usages()) { |
| if (z != 0) { |
| formatter.format(", "); |
| } |
| usage.formatTo(formatter, neighborsFlags, 0, precision - 1); |
| ++z; |
| } |
| formatter.format("}"); |
| } |
| |
| for (Position position : this.successorPositions()) { |
| Node successor = position.get(this); |
| if (successor != null) { |
| formatter.format(" "); |
| formatter.format(position.getName()); |
| formatter.format("={"); |
| successor.formatTo(formatter, neighborsFlags, 0, precision - 1); |
| formatter.format("}"); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Determines if this node's {@link NodeClass#getData() data} fields are equal to the data |
| * fields of another node of the same type. Primitive fields are compared by value and |
| * non-primitive fields are compared by {@link Objects#equals(Object, Object)}. |
| * |
| * The result of this method undefined if {@code other.getClass() != this.getClass()}. |
| * |
| * @param other a node of exactly the same type as this node |
| * @return true if the data fields of this object and {@code other} are equal |
| */ |
| public boolean valueEquals(Node other) { |
| return getNodeClass().dataEquals(this, other); |
| } |
| |
| /** |
| * Determines if this node is equal to the other node while ignoring differences in |
| * {@linkplain Successor control-flow} edges. |
| * |
| */ |
| public boolean dataFlowEquals(Node other) { |
| return this == other || nodeClass == other.getNodeClass() && this.valueEquals(other) && nodeClass.equalInputs(this, other); |
| } |
| |
| public final void pushInputs(NodeStack stack) { |
| getNodeClass().pushInputs(this, stack); |
| } |
| |
| public NodeSize estimatedNodeSize() { |
| return nodeClass.size(); |
| } |
| |
| public NodeCycles estimatedNodeCycles() { |
| return nodeClass.cycles(); |
| } |
| |
| } |
