Source code

001/*
002 * Copyright (c) 2011, 2014, 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.compiler.common.Fields.*;
026import static com.oracle.graal.graph.Edges.*;
027import static com.oracle.graal.graph.InputEdges.*;
028import static com.oracle.graal.graph.Node.*;
029import static jdk.internal.jvmci.common.JVMCIError.*;
030
031import java.lang.annotation.*;
032import java.lang.reflect.*;
033import java.util.*;
034import java.util.concurrent.atomic.*;
035
036import jdk.internal.jvmci.common.*;
037import com.oracle.graal.debug.*;
038
039import com.oracle.graal.compiler.common.*;
040import com.oracle.graal.graph.Edges.Type;
041import com.oracle.graal.graph.Graph.DuplicationReplacement;
042import com.oracle.graal.graph.Node.Input;
043import com.oracle.graal.graph.Node.OptionalInput;
044import com.oracle.graal.graph.Node.Successor;
045import com.oracle.graal.graph.spi.*;
046import com.oracle.graal.graph.spi.Canonicalizable.BinaryCommutative;
047import com.oracle.graal.nodeinfo.*;
048
049/**
050 * Metadata for every {@link Node} type. The metadata includes:
051 * <ul>
052 * <li>The offsets of fields annotated with {@link Input} and {@link Successor} as well as methods
053 * for iterating over such fields.</li>
054 * <li>The identifier for an {@link IterableNodeType} class.</li>
055 * </ul>
056 */
057public final class NodeClass<T> extends FieldIntrospection<T> {
058
059    // Timers for creation of a NodeClass instance
060    private static final DebugTimer Init_FieldScanning = Debug.timer("NodeClass.Init.FieldScanning");
061    private static final DebugTimer Init_FieldScanningInner = Debug.timer("NodeClass.Init.FieldScanning.Inner");
062    private static final DebugTimer Init_AnnotationParsing = Debug.timer("NodeClass.Init.AnnotationParsing");
063    private static final DebugTimer Init_Edges = Debug.timer("NodeClass.Init.Edges");
064    private static final DebugTimer Init_Data = Debug.timer("NodeClass.Init.Data");
065    private static final DebugTimer Init_AllowedUsages = Debug.timer("NodeClass.Init.AllowedUsages");
066    private static final DebugTimer Init_IterableIds = Debug.timer("NodeClass.Init.IterableIds");
067
068    private static <T extends Annotation> T getAnnotationTimed(AnnotatedElement e, Class<T> annotationClass) {
069        try (DebugCloseable s = Init_AnnotationParsing.start()) {
070            return e.getAnnotation(annotationClass);
071        }
072    }
073
074    /**
075     * Gets the {@link NodeClass} associated with a given {@link Class}.
076     */
077    public static <T> NodeClass<T> create(Class<T> c) {
078        assert get(c) == null;
079        Class<? super T> superclass = c.getSuperclass();
080        NodeClass<? super T> nodeSuperclass = null;
081        if (superclass != NODE_CLASS) {
082            nodeSuperclass = get(superclass);
083        }
084        return new NodeClass<>(c, nodeSuperclass);
085    }
086
087    @SuppressWarnings("unchecked")
088    public static <T> NodeClass<T> get(Class<T> superclass) {
089        try {
090            Field field = superclass.getDeclaredField("TYPE");
091            field.setAccessible(true);
092            return (NodeClass<T>) field.get(null);
093        } catch (IllegalArgumentException | IllegalAccessException | NoSuchFieldException | SecurityException e) {
094            throw new RuntimeException(e);
095        }
096    }
097
098    private static final Class<?> NODE_CLASS = Node.class;
099    private static final Class<?> INPUT_LIST_CLASS = NodeInputList.class;
100    private static final Class<?> SUCCESSOR_LIST_CLASS = NodeSuccessorList.class;
101
102    private static AtomicInteger nextIterableId = new AtomicInteger();
103
104    private final InputEdges inputs;
105    private final SuccessorEdges successors;
106    private final NodeClass<? super T> superNodeClass;
107
108    private final boolean canGVN;
109    private final int startGVNNumber;
110    private final String nameTemplate;
111    private final int iterableId;
112    private final EnumSet<InputType> allowedUsageTypes;
113    private int[] iterableIds;
114
115    private static final DebugMetric ITERABLE_NODE_TYPES = Debug.metric("IterableNodeTypes");
116    private final DebugMetric nodeIterableCount;
117
118    /**
119     * Determines if this node type implements {@link Canonicalizable}.
120     */
121    private final boolean isCanonicalizable;
122
123    /**
124     * Determines if this node type implements {@link BinaryCommutative}.
125     */
126    private final boolean isCommutative;
127
128    /**
129     * Determines if this node type implements {@link Simplifiable}.
130     */
131    private final boolean isSimplifiable;
132    private final boolean isLeafNode;
133
134    public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass) {
135        this(clazz, superNodeClass, new FieldsScanner.DefaultCalcOffset(), null, 0);
136    }
137
138    public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass, FieldsScanner.CalcOffset calcOffset, int[] presetIterableIds, int presetIterableId) {
139        super(clazz);
140        this.superNodeClass = superNodeClass;
141        assert NODE_CLASS.isAssignableFrom(clazz);
142
143        this.isCanonicalizable = Canonicalizable.class.isAssignableFrom(clazz);
144        this.isCommutative = BinaryCommutative.class.isAssignableFrom(clazz);
145        if (Canonicalizable.Unary.class.isAssignableFrom(clazz) || Canonicalizable.Binary.class.isAssignableFrom(clazz)) {
146            assert Canonicalizable.Unary.class.isAssignableFrom(clazz) ^ Canonicalizable.Binary.class.isAssignableFrom(clazz) : clazz + " should implement either Unary or Binary, not both";
147        }
148
149        this.isSimplifiable = Simplifiable.class.isAssignableFrom(clazz);
150
151        NodeFieldsScanner fs = new NodeFieldsScanner(calcOffset, superNodeClass);
152        try (DebugCloseable t = Init_FieldScanning.start()) {
153            fs.scan(clazz, clazz.getSuperclass(), false);
154        }
155
156        try (DebugCloseable t1 = Init_Edges.start()) {
157            successors = new SuccessorEdges(fs.directSuccessors, fs.successors);
158            inputs = new InputEdges(fs.directInputs, fs.inputs);
159        }
160        try (DebugCloseable t1 = Init_Data.start()) {
161            data = new Fields(fs.data);
162        }
163
164        isLeafNode = inputs.getCount() + successors.getCount() == 0;
165
166        canGVN = Node.ValueNumberable.class.isAssignableFrom(clazz);
167        startGVNNumber = clazz.getName().hashCode();
168
169        NodeInfo info = getAnnotationTimed(clazz, NodeInfo.class);
170        assert info != null : "Missing NodeInfo annotation on " + clazz;
171        this.nameTemplate = info.nameTemplate();
172
173        try (DebugCloseable t1 = Init_AllowedUsages.start()) {
174            allowedUsageTypes = superNodeClass == null ? EnumSet.noneOf(InputType.class) : superNodeClass.allowedUsageTypes.clone();
175            allowedUsageTypes.addAll(Arrays.asList(info.allowedUsageTypes()));
176        }
177
178        if (presetIterableIds != null) {
179            this.iterableIds = presetIterableIds;
180            this.iterableId = presetIterableId;
181        } else if (IterableNodeType.class.isAssignableFrom(clazz)) {
182            ITERABLE_NODE_TYPES.increment();
183            try (DebugCloseable t1 = Init_IterableIds.start()) {
184                this.iterableId = nextIterableId.getAndIncrement();
185
186                NodeClass<?> snc = superNodeClass;
187                while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {
188                    snc.addIterableId(iterableId);
189                    snc = snc.superNodeClass;
190                }
191
192                this.iterableIds = new int[]{iterableId};
193            }
194        } else {
195            this.iterableId = Node.NOT_ITERABLE;
196            this.iterableIds = null;
197        }
198        nodeIterableCount = Debug.metric("NodeIterable_%s", clazz);
199        assert verifyIterableIds();
200    }
201
202    private synchronized void addIterableId(int newIterableId) {
203        assert !containsId(newIterableId, iterableIds);
204        int[] copy = Arrays.copyOf(iterableIds, iterableIds.length + 1);
205        copy[iterableIds.length] = newIterableId;
206        iterableIds = copy;
207    }
208
209    private boolean verifyIterableIds() {
210        NodeClass<?> snc = superNodeClass;
211        while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {
212            assert containsId(iterableId, snc.iterableIds);
213            snc = snc.superNodeClass;
214        }
215        return true;
216    }
217
218    private static boolean containsId(int iterableId, int[] iterableIds) {
219        for (int i : iterableIds) {
220            if (i == iterableId) {
221                return true;
222            }
223        }
224        return false;
225    }
226
227    private String shortName;
228
229    public String shortName() {
230        if (shortName == null) {
231            NodeInfo info = getClazz().getAnnotation(NodeInfo.class);
232            if (!info.shortName().isEmpty()) {
233                shortName = info.shortName();
234            } else {
235                String localShortName = getClazz().getSimpleName();
236                if (localShortName.endsWith("Node") && !localShortName.equals("StartNode") && !localShortName.equals("EndNode")) {
237                    shortName = localShortName.substring(0, localShortName.length() - 4);
238                } else {
239                    shortName = localShortName;
240                }
241            }
242        }
243        return shortName;
244    }
245
246    @Override
247    public Fields[] getAllFields() {
248        return new Fields[]{data, inputs, successors};
249    }
250
251    public int[] iterableIds() {
252        nodeIterableCount.increment();
253        return iterableIds;
254    }
255
256    public int iterableId() {
257        return iterableId;
258    }
259
260    public boolean valueNumberable() {
261        return canGVN;
262    }
263
264    /**
265     * Determines if this node type implements {@link Canonicalizable}.
266     */
267    public boolean isCanonicalizable() {
268        return isCanonicalizable;
269    }
270
271    /**
272     * Determines if this node type implements {@link BinaryCommutative}.
273     */
274    public boolean isCommutative() {
275        return isCommutative;
276    }
277
278    /**
279     * Determines if this node type implements {@link Simplifiable}.
280     */
281    public boolean isSimplifiable() {
282        return isSimplifiable;
283    }
284
285    static int allocatedNodeIterabledIds() {
286        return nextIterableId.get();
287    }
288
289    public EnumSet<InputType> getAllowedUsageTypes() {
290        return allowedUsageTypes;
291    }
292
293    /**
294     * Describes a field representing an input or successor edge in a node.
295     */
296    protected static class EdgeInfo extends FieldsScanner.FieldInfo {
297
298        public EdgeInfo(long offset, String name, Class<?> type, Class<?> declaringClass) {
299            super(offset, name, type, declaringClass);
300        }
301
302        /**
303         * Sorts non-list edges before list edges.
304         */
305        @Override
306        public int compareTo(FieldsScanner.FieldInfo o) {
307            if (NodeList.class.isAssignableFrom(o.type)) {
308                if (!NodeList.class.isAssignableFrom(type)) {
309                    return -1;
310                }
311            } else {
312                if (NodeList.class.isAssignableFrom(type)) {
313                    return 1;
314                }
315            }
316            return super.compareTo(o);
317        }
318    }
319
320    /**
321     * Describes a field representing an {@linkplain Type#Inputs input} edge in a node.
322     */
323    protected static class InputInfo extends EdgeInfo {
324        final InputType inputType;
325        final boolean optional;
326
327        public InputInfo(long offset, String name, Class<?> type, Class<?> declaringClass, InputType inputType, boolean optional) {
328            super(offset, name, type, declaringClass);
329            this.inputType = inputType;
330            this.optional = optional;
331        }
332
333        @Override
334        public String toString() {
335            return super.toString() + "{inputType=" + inputType + ", optional=" + optional + "}";
336        }
337    }
338
339    protected static class NodeFieldsScanner extends FieldsScanner {
340
341        public final ArrayList<InputInfo> inputs = new ArrayList<>();
342        public final ArrayList<EdgeInfo> successors = new ArrayList<>();
343        int directInputs;
344        int directSuccessors;
345
346        protected NodeFieldsScanner(FieldsScanner.CalcOffset calc, NodeClass<?> superNodeClass) {
347            super(calc);
348            if (superNodeClass != null) {
349                translateInto(superNodeClass.inputs, inputs);
350                translateInto(superNodeClass.successors, successors);
351                translateInto(superNodeClass.data, data);
352                directInputs = superNodeClass.inputs.getDirectCount();
353                directSuccessors = superNodeClass.successors.getDirectCount();
354            }
355        }
356
357        @Override
358        protected void scanField(Field field, long offset) {
359            Input inputAnnotation = getAnnotationTimed(field, Node.Input.class);
360            OptionalInput optionalInputAnnotation = getAnnotationTimed(field, Node.OptionalInput.class);
361            Successor successorAnnotation = getAnnotationTimed(field, Successor.class);
362            try (DebugCloseable s = Init_FieldScanningInner.start()) {
363                Class<?> type = field.getType();
364                int modifiers = field.getModifiers();
365
366                if (inputAnnotation != null || optionalInputAnnotation != null) {
367                    assert successorAnnotation == null : "field cannot be both input and successor";
368                    if (INPUT_LIST_CLASS.isAssignableFrom(type)) {
369                        // NodeInputList fields should not be final since they are
370                        // written (via Unsafe) in clearInputs()
371                        JVMCIError.guarantee(!Modifier.isFinal(modifiers), "NodeInputList input field %s should not be final", field);
372                        JVMCIError.guarantee(!Modifier.isPublic(modifiers), "NodeInputList input field %s should not be public", field);
373                    } else {
374                        JVMCIError.guarantee(NODE_CLASS.isAssignableFrom(type) || type.isInterface(), "invalid input type: %s", type);
375                        JVMCIError.guarantee(!Modifier.isFinal(modifiers), "Node input field %s should not be final", field);
376                        directInputs++;
377                    }
378                    InputType inputType;
379                    if (inputAnnotation != null) {
380                        assert optionalInputAnnotation == null : "inputs can either be optional or non-optional";
381                        inputType = inputAnnotation.value();
382                    } else {
383                        inputType = optionalInputAnnotation.value();
384                    }
385                    inputs.add(new InputInfo(offset, field.getName(), type, field.getDeclaringClass(), inputType, field.isAnnotationPresent(Node.OptionalInput.class)));
386                } else if (successorAnnotation != null) {
387                    if (SUCCESSOR_LIST_CLASS.isAssignableFrom(type)) {
388                        // NodeSuccessorList fields should not be final since they are
389                        // written (via Unsafe) in clearSuccessors()
390                        JVMCIError.guarantee(!Modifier.isFinal(modifiers), "NodeSuccessorList successor field % should not be final", field);
391                        JVMCIError.guarantee(!Modifier.isPublic(modifiers), "NodeSuccessorList successor field %s should not be public", field);
392                    } else {
393                        JVMCIError.guarantee(NODE_CLASS.isAssignableFrom(type), "invalid successor type: %s", type);
394                        JVMCIError.guarantee(!Modifier.isFinal(modifiers), "Node successor field %s should not be final", field);
395                        directSuccessors++;
396                    }
397                    successors.add(new EdgeInfo(offset, field.getName(), type, field.getDeclaringClass()));
398                } else {
399                    JVMCIError.guarantee(!NODE_CLASS.isAssignableFrom(type) || field.getName().equals("Null"), "suspicious node field: %s", field);
400                    JVMCIError.guarantee(!INPUT_LIST_CLASS.isAssignableFrom(type), "suspicious node input list field: %s", field);
401                    JVMCIError.guarantee(!SUCCESSOR_LIST_CLASS.isAssignableFrom(type), "suspicious node successor list field: %s", field);
402                    super.scanField(field, offset);
403                }
404            }
405        }
406    }
407
408    @Override
409    public String toString() {
410        StringBuilder str = new StringBuilder();
411        str.append("NodeClass ").append(getClazz().getSimpleName()).append(" [");
412        inputs.appendFields(str);
413        str.append("] [");
414        successors.appendFields(str);
415        str.append("] [");
416        data.appendFields(str);
417        str.append("]");
418        return str.toString();
419    }
420
421    private static int deepHashCode0(Object o) {
422        if (o instanceof Object[]) {
423            return Arrays.deepHashCode((Object[]) o);
424        } else if (o instanceof byte[]) {
425            return Arrays.hashCode((byte[]) o);
426        } else if (o instanceof short[]) {
427            return Arrays.hashCode((short[]) o);
428        } else if (o instanceof int[]) {
429            return Arrays.hashCode((int[]) o);
430        } else if (o instanceof long[]) {
431            return Arrays.hashCode((long[]) o);
432        } else if (o instanceof char[]) {
433            return Arrays.hashCode((char[]) o);
434        } else if (o instanceof float[]) {
435            return Arrays.hashCode((float[]) o);
436        } else if (o instanceof double[]) {
437            return Arrays.hashCode((double[]) o);
438        } else if (o instanceof boolean[]) {
439            return Arrays.hashCode((boolean[]) o);
440        } else if (o != null) {
441            return o.hashCode();
442        } else {
443            return 0;
444        }
445    }
446
447    public int valueNumber(Node n) {
448        int number = 0;
449        if (canGVN) {
450            number = startGVNNumber;
451            for (int i = 0; i < data.getCount(); ++i) {
452                Class<?> type = data.getType(i);
453                if (type.isPrimitive()) {
454                    if (type == Integer.TYPE) {
455                        int intValue = data.getInt(n, i);
456                        number += intValue;
457                    } else if (type == Long.TYPE) {
458                        long longValue = data.getLong(n, i);
459                        number += longValue ^ (longValue >>> 32);
460                    } else if (type == Boolean.TYPE) {
461                        boolean booleanValue = data.getBoolean(n, i);
462                        if (booleanValue) {
463                            number += 7;
464                        }
465                    } else if (type == Float.TYPE) {
466                        float floatValue = data.getFloat(n, i);
467                        number += Float.floatToRawIntBits(floatValue);
468                    } else if (type == Double.TYPE) {
469                        double doubleValue = data.getDouble(n, i);
470                        long longValue = Double.doubleToRawLongBits(doubleValue);
471                        number += longValue ^ (longValue >>> 32);
472                    } else if (type == Short.TYPE) {
473                        short shortValue = data.getShort(n, i);
474                        number += shortValue;
475                    } else if (type == Character.TYPE) {
476                        char charValue = data.getChar(n, i);
477                        number += charValue;
478                    } else if (type == Byte.TYPE) {
479                        byte byteValue = data.getByte(n, i);
480                        number += byteValue;
481                    } else {
482                        assert false : "unhandled property type: " + type;
483                    }
484                } else {
485                    Object o = data.getObject(n, i);
486                    number += deepHashCode0(o);
487                }
488                number *= 13;
489            }
490        }
491        return number;
492    }
493
494    private static boolean deepEquals0(Object e1, Object e2) {
495        assert e1 != null;
496        boolean eq;
497        if (e1 instanceof Object[] && e2 instanceof Object[]) {
498            eq = Arrays.deepEquals((Object[]) e1, (Object[]) e2);
499        } else if (e1 instanceof byte[] && e2 instanceof byte[]) {
500            eq = Arrays.equals((byte[]) e1, (byte[]) e2);
501        } else if (e1 instanceof short[] && e2 instanceof short[]) {
502            eq = Arrays.equals((short[]) e1, (short[]) e2);
503        } else if (e1 instanceof int[] && e2 instanceof int[]) {
504            eq = Arrays.equals((int[]) e1, (int[]) e2);
505        } else if (e1 instanceof long[] && e2 instanceof long[]) {
506            eq = Arrays.equals((long[]) e1, (long[]) e2);
507        } else if (e1 instanceof char[] && e2 instanceof char[]) {
508            eq = Arrays.equals((char[]) e1, (char[]) e2);
509        } else if (e1 instanceof float[] && e2 instanceof float[]) {
510            eq = Arrays.equals((float[]) e1, (float[]) e2);
511        } else if (e1 instanceof double[] && e2 instanceof double[]) {
512            eq = Arrays.equals((double[]) e1, (double[]) e2);
513        } else if (e1 instanceof boolean[] && e2 instanceof boolean[]) {
514            eq = Arrays.equals((boolean[]) e1, (boolean[]) e2);
515        } else {
516            eq = e1.equals(e2);
517        }
518        return eq;
519    }
520
521    public boolean dataEquals(Node a, Node b) {
522        assert a.getClass() == b.getClass();
523        for (int i = 0; i < data.getCount(); ++i) {
524            Class<?> type = data.getType(i);
525            if (type.isPrimitive()) {
526                if (type == Integer.TYPE) {
527                    int aInt = data.getInt(a, i);
528                    int bInt = data.getInt(b, i);
529                    if (aInt != bInt) {
530                        return false;
531                    }
532                } else if (type == Boolean.TYPE) {
533                    boolean aBoolean = data.getBoolean(a, i);
534                    boolean bBoolean = data.getBoolean(b, i);
535                    if (aBoolean != bBoolean) {
536                        return false;
537                    }
538                } else if (type == Long.TYPE) {
539                    long aLong = data.getLong(a, i);
540                    long bLong = data.getLong(b, i);
541                    if (aLong != bLong) {
542                        return false;
543                    }
544                } else if (type == Float.TYPE) {
545                    float aFloat = data.getFloat(a, i);
546                    float bFloat = data.getFloat(b, i);
547                    if (aFloat != bFloat) {
548                        return false;
549                    }
550                } else if (type == Double.TYPE) {
551                    double aDouble = data.getDouble(a, i);
552                    double bDouble = data.getDouble(b, i);
553                    if (aDouble != bDouble) {
554                        return false;
555                    }
556                } else if (type == Short.TYPE) {
557                    short aShort = data.getShort(a, i);
558                    short bShort = data.getShort(b, i);
559                    if (aShort != bShort) {
560                        return false;
561                    }
562                } else if (type == Character.TYPE) {
563                    char aChar = data.getChar(a, i);
564                    char bChar = data.getChar(b, i);
565                    if (aChar != bChar) {
566                        return false;
567                    }
568                } else if (type == Byte.TYPE) {
569                    byte aByte = data.getByte(a, i);
570                    byte bByte = data.getByte(b, i);
571                    if (aByte != bByte) {
572                        return false;
573                    }
574                } else {
575                    assert false : "unhandled type: " + type;
576                }
577            } else {
578                Object objectA = data.getObject(a, i);
579                Object objectB = data.getObject(b, i);
580                if (objectA != objectB) {
581                    if (objectA != null && objectB != null) {
582                        if (!deepEquals0(objectA, objectB)) {
583                            return false;
584                        }
585                    } else {
586                        return false;
587                    }
588                }
589            }
590        }
591        return true;
592    }
593
594    public boolean isValid(Position pos, NodeClass<?> from, Edges fromEdges) {
595        if (this == from) {
596            return true;
597        }
598        Edges toEdges = getEdges(fromEdges.type());
599        if (pos.getIndex() >= toEdges.getCount()) {
600            return false;
601        }
602        if (pos.getIndex() >= fromEdges.getCount()) {
603            return false;
604        }
605        return toEdges.isSame(fromEdges, pos.getIndex());
606    }
607
608    static void updateEdgesInPlace(Node node, InplaceUpdateClosure duplicationReplacement, Edges edges) {
609        int index = 0;
610        Type curType = edges.type();
611        int directCount = edges.getDirectCount();
612        final long[] curOffsets = edges.getOffsets();
613        while (index < directCount) {
614            Node edge = Edges.getNode(node, curOffsets, index);
615            if (edge != null) {
616                Node newEdge = duplicationReplacement.replacement(edge, curType);
617                if (curType == Edges.Type.Inputs) {
618                    node.updateUsages(null, newEdge);
619                } else {
620                    node.updatePredecessor(null, newEdge);
621                }
622                assert assertUpdateValid(node, edges, index, newEdge);
623                Edges.initializeNode(node, curOffsets, index, newEdge);
624            }
625            index++;
626        }
627
628        while (index < edges.getCount()) {
629            NodeList<Node> list = Edges.getNodeList(node, curOffsets, index);
630            if (list != null) {
631                Edges.initializeList(node, curOffsets, index, updateEdgeListCopy(node, list, duplicationReplacement, curType));
632            }
633            index++;
634        }
635    }
636
637    private static boolean assertUpdateValid(Node node, Edges edges, int index, Node newEdge) {
638        assert newEdge == null || edges.getType(index).isAssignableFrom(newEdge.getClass()) : "Can not assign " + newEdge.getClass() + " to " + edges.getType(index) + " in " + node;
639        return true;
640    }
641
642    void updateInputSuccInPlace(Node node, InplaceUpdateClosure duplicationReplacement) {
643        updateEdgesInPlace(node, duplicationReplacement, inputs);
644        updateEdgesInPlace(node, duplicationReplacement, successors);
645    }
646
647    private static NodeList<Node> updateEdgeListCopy(Node node, NodeList<Node> list, InplaceUpdateClosure duplicationReplacement, Edges.Type type) {
648        NodeList<Node> result = type == Edges.Type.Inputs ? new NodeInputList<>(node, list.size()) : new NodeSuccessorList<>(node, list.size());
649
650        for (int i = 0; i < list.count(); ++i) {
651            Node oldNode = list.get(i);
652            if (oldNode != null) {
653                Node newNode = duplicationReplacement.replacement(oldNode, type);
654                result.set(i, newNode);
655            }
656        }
657        return result;
658    }
659
660    /**
661     * Gets the input or successor edges defined by this node class.
662     */
663    public Edges getEdges(Edges.Type type) {
664        return type == Edges.Type.Inputs ? inputs : successors;
665    }
666
667    public Edges getInputEdges() {
668        return inputs;
669    }
670
671    public Edges getSuccessorEdges() {
672        return successors;
673    }
674
675    /**
676     * Returns a newly allocated node for which no subclass-specific constructor has been called.
677     */
678    @SuppressWarnings("unchecked")
679    public Node allocateInstance() {
680        try {
681            Node node = (Node) UnsafeAccess.unsafe.allocateInstance(getJavaClass());
682            node.init((NodeClass<? extends Node>) this);
683            return node;
684        } catch (InstantiationException ex) {
685            throw shouldNotReachHere(ex);
686        }
687    }
688
689    public Class<T> getJavaClass() {
690        return getClazz();
691    }
692
693    /**
694     * The template used to build the {@link Verbosity#Name} version. Variable parts are specified
695     * using &#123;i#inputName&#125; or &#123;p#propertyName&#125;.
696     */
697    public String getNameTemplate() {
698        return nameTemplate.isEmpty() ? shortName() : nameTemplate;
699    }
700
701    interface InplaceUpdateClosure {
702
703        Node replacement(Node node, Edges.Type type);
704    }
705
706    static Map<Node, Node> addGraphDuplicate(final Graph graph, final Graph oldGraph, int estimatedNodeCount, Iterable<? extends Node> nodes, final DuplicationReplacement replacements) {
707        final Map<Node, Node> newNodes;
708        int denseThreshold = oldGraph.getNodeCount() + oldGraph.getNodesDeletedSinceLastCompression() >> 4;
709        if (estimatedNodeCount > denseThreshold) {
710            // Use dense map
711            newNodes = new NodeNodeMap(oldGraph);
712        } else {
713            // Use sparse map
714            newNodes = newIdentityMap();
715        }
716        createNodeDuplicates(graph, nodes, replacements, newNodes);
717
718        InplaceUpdateClosure replacementClosure = new InplaceUpdateClosure() {
719
720            public Node replacement(Node node, Edges.Type type) {
721                Node target = newNodes.get(node);
722                if (target == null) {
723                    Node replacement = node;
724                    if (replacements != null) {
725                        replacement = replacements.replacement(node);
726                    }
727                    if (replacement != node) {
728                        target = replacement;
729                    } else if (node.graph() == graph && type == Edges.Type.Inputs) {
730                        // patch to the outer world
731                        target = node;
732                    }
733
734                }
735                return target;
736            }
737
738        };
739
740        // re-wire inputs
741        for (Node oldNode : nodes) {
742            Node node = newNodes.get(oldNode);
743            NodeClass<?> nodeClass = node.getNodeClass();
744            if (replacements == null || replacements.replacement(oldNode) == oldNode) {
745                nodeClass.updateInputSuccInPlace(node, replacementClosure);
746            } else {
747                transferEdgesDifferentNodeClass(graph, replacements, newNodes, oldNode, node);
748            }
749        }
750
751        return newNodes;
752    }
753
754    private static void createNodeDuplicates(final Graph graph, Iterable<? extends Node> nodes, final DuplicationReplacement replacements, final Map<Node, Node> newNodes) {
755        for (Node node : nodes) {
756            if (node != null) {
757                assert !node.isDeleted() : "trying to duplicate deleted node: " + node;
758                Node replacement = node;
759                if (replacements != null) {
760                    replacement = replacements.replacement(node);
761                }
762                if (replacement != node) {
763                    if (Fingerprint.ENABLED) {
764                        Fingerprint.submit("replacing %s with %s", node, replacement);
765                    }
766                    assert replacement != null;
767                    newNodes.put(node, replacement);
768                } else {
769                    if (Fingerprint.ENABLED) {
770                        Fingerprint.submit("duplicating %s", node);
771                    }
772                    Node newNode = node.clone(graph, WithAllEdges);
773                    assert newNode.inputs().isEmpty() || newNode.hasNoUsages();
774                    assert newNode.getClass() == node.getClass();
775                    newNodes.put(node, newNode);
776                }
777            }
778        }
779    }
780
781    private static void transferEdgesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final Map<Node, Node> newNodes, Node oldNode, Node node) {
782        transferEdges(graph, replacements, newNodes, oldNode, node, Edges.Type.Inputs);
783        transferEdges(graph, replacements, newNodes, oldNode, node, Edges.Type.Successors);
784    }
785
786    private static void transferEdges(final Graph graph, final DuplicationReplacement replacements, final Map<Node, Node> newNodes, Node oldNode, Node node, Edges.Type type) {
787        NodeClass<?> nodeClass = node.getNodeClass();
788        NodeClass<?> oldNodeClass = oldNode.getNodeClass();
789        Edges oldEdges = oldNodeClass.getEdges(type);
790        for (NodePosIterator oldIter = oldEdges.getIterable(oldNode).iterator(); oldIter.hasNext();) {
791            Position pos = oldIter.nextPosition();
792            if (!nodeClass.isValid(pos, oldNodeClass, oldEdges)) {
793                continue;
794            }
795            Node oldEdge = pos.get(oldNode);
796            Node target = newNodes.get(oldEdge);
797            if (target == null) {
798                Node replacement = oldEdge;
799                if (replacements != null) {
800                    replacement = replacements.replacement(oldEdge);
801                }
802                if (replacement != oldEdge) {
803                    target = replacement;
804                } else if (type == Edges.Type.Inputs && oldEdge.graph() == graph) {
805                    // patch to the outer world
806                    target = oldEdge;
807                }
808            }
809            pos.set(node, target);
810        }
811    }
812
813    /**
814     * @returns true if the node has no inputs and no successors
815     */
816    public boolean isLeafNode() {
817        return isLeafNode;
818    }
819}