1 /*
2 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.graph;
24
25 import static org.graalvm.compiler.core.common.Fields.translateInto;
26 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
27 import static org.graalvm.compiler.graph.Edges.translateInto;
28 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
29 import static org.graalvm.compiler.graph.InputEdges.translateInto;
30 import static org.graalvm.compiler.graph.Node.WithAllEdges;
31 import static org.graalvm.compiler.graph.Node.newIdentityMap;
32 import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;
33
34 import java.lang.annotation.Annotation;
35 import java.lang.reflect.AnnotatedElement;
36 import java.lang.reflect.Field;
37 import java.lang.reflect.Modifier;
38 import java.util.ArrayList;
39 import java.util.Arrays;
40 import java.util.EnumSet;
41 import java.util.Iterator;
42 import java.util.Map;
43 import java.util.NoSuchElementException;
44 import java.util.Objects;
45 import java.util.concurrent.atomic.AtomicInteger;
46
47 import org.graalvm.compiler.core.common.FieldIntrospection;
48 import org.graalvm.compiler.core.common.Fields;
49 import org.graalvm.compiler.core.common.FieldsScanner;
50 import org.graalvm.compiler.debug.Debug;
51 import org.graalvm.compiler.debug.DebugCloseable;
52 import org.graalvm.compiler.debug.DebugCounter;
53 import org.graalvm.compiler.debug.DebugTimer;
54 import org.graalvm.compiler.debug.Fingerprint;
55 import org.graalvm.compiler.debug.GraalError;
56 import org.graalvm.compiler.graph.Edges.Type;
57 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
58 import org.graalvm.compiler.graph.Node.EdgeVisitor;
59 import org.graalvm.compiler.graph.Node.Input;
60 import org.graalvm.compiler.graph.Node.OptionalInput;
61 import org.graalvm.compiler.graph.Node.Successor;
62 import org.graalvm.compiler.graph.iterators.NodeIterable;
63 import org.graalvm.compiler.graph.spi.Canonicalizable;
64 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative;
65 import org.graalvm.compiler.graph.spi.Simplifiable;
66 import org.graalvm.compiler.nodeinfo.InputType;
67 import org.graalvm.compiler.nodeinfo.NodeCycles;
68 import org.graalvm.compiler.nodeinfo.NodeInfo;
69 import org.graalvm.compiler.nodeinfo.NodeSize;
70 import org.graalvm.compiler.nodeinfo.Verbosity;
71 import org.graalvm.compiler.options.Option;
72 import org.graalvm.compiler.options.OptionValue;
73 import org.graalvm.compiler.options.StableOptionValue;
74
75 /**
76 * Metadata for every {@link Node} type. The metadata includes:
77 * <ul>
78 * <li>The offsets of fields annotated with {@link Input} and {@link Successor} as well as methods
79 * for iterating over such fields.</li>
80 * <li>The identifier for an {@link IterableNodeType} class.</li>
81 * </ul>
82 */
83 public final class NodeClass<T> extends FieldIntrospection<T> {
84
85 public static class Options {
86 // @formatter:off
87 @Option(help = "Verifies that receivers of NodeInfo#size() and NodeInfo#cycles() do not have UNSET values.")
88 public static final OptionValue<Boolean> VerifyNodeCostOnAccess = new StableOptionValue<>(false);
89 // @formatter:on
90 }
91
92 // Timers for creation of a NodeClass instance
93 private static final DebugTimer Init_FieldScanning = Debug.timer("NodeClass.Init.FieldScanning");
94 private static final DebugTimer Init_FieldScanningInner = Debug.timer("NodeClass.Init.FieldScanning.Inner");
95 private static final DebugTimer Init_AnnotationParsing = Debug.timer("NodeClass.Init.AnnotationParsing");
96 private static final DebugTimer Init_Edges = Debug.timer("NodeClass.Init.Edges");
97 private static final DebugTimer Init_Data = Debug.timer("NodeClass.Init.Data");
98 private static final DebugTimer Init_AllowedUsages = Debug.timer("NodeClass.Init.AllowedUsages");
99 private static final DebugTimer Init_IterableIds = Debug.timer("NodeClass.Init.IterableIds");
100
101 public static final long MAX_EDGES = 8;
102 public static final long MAX_LIST_EDGES = 6;
103 public static final long OFFSET_MASK = 0xFC;
104 public static final long LIST_MASK = 0x01;
105 public static final long NEXT_EDGE = 0x08;
106
107 @SuppressWarnings("try")
108 private static <T extends Annotation> T getAnnotationTimed(AnnotatedElement e, Class<T> annotationClass) {
109 try (DebugCloseable s = Init_AnnotationParsing.start()) {
110 return e.getAnnotation(annotationClass);
111 }
112 }
113
114 /**
115 * Gets the {@link NodeClass} associated with a given {@link Class}.
116 */
117 public static <T> NodeClass<T> create(Class<T> c) {
118 assert get(c) == null;
119 Class<? super T> superclass = c.getSuperclass();
120 NodeClass<? super T> nodeSuperclass = null;
121 if (superclass != NODE_CLASS) {
122 nodeSuperclass = get(superclass);
123 }
124 return new NodeClass<>(c, nodeSuperclass);
125 }
126
127 @SuppressWarnings("unchecked")
128 public static <T> NodeClass<T> get(Class<T> superclass) {
129 try {
130 Field field = superclass.getDeclaredField("TYPE");
131 field.setAccessible(true);
132 return (NodeClass<T>) field.get(null);
133 } catch (IllegalArgumentException | IllegalAccessException | NoSuchFieldException | SecurityException e) {
134 throw new RuntimeException(e);
135 }
136 }
137
138 private static final Class<?> NODE_CLASS = Node.class;
139 private static final Class<?> INPUT_LIST_CLASS = NodeInputList.class;
140 private static final Class<?> SUCCESSOR_LIST_CLASS = NodeSuccessorList.class;
141
142 private static AtomicInteger nextIterableId = new AtomicInteger();
143
144 private final InputEdges inputs;
145 private final SuccessorEdges successors;
146 private final NodeClass<? super T> superNodeClass;
147
148 private final boolean canGVN;
149 private final int startGVNNumber;
150 private final String nameTemplate;
151 private final int iterableId;
152 private final EnumSet<InputType> allowedUsageTypes;
153 private int[] iterableIds;
154 private final long inputsIteration;
155 private final long successorIteration;
156
157 private static final DebugCounter ITERABLE_NODE_TYPES = Debug.counter("IterableNodeTypes");
158 private final DebugCounter nodeIterableCount;
159
160 /**
161 * Determines if this node type implements {@link Canonicalizable}.
162 */
163 private final boolean isCanonicalizable;
164
165 /**
166 * Determines if this node type implements {@link BinaryCommutative}.
167 */
168 private final boolean isCommutative;
169
170 /**
171 * Determines if this node type implements {@link Simplifiable}.
172 */
173 private final boolean isSimplifiable;
174 private final boolean isLeafNode;
175
176 public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass) {
177 this(clazz, superNodeClass, new FieldsScanner.DefaultCalcOffset(), null, 0);
178 }
179
180 @SuppressWarnings("try")
181 public NodeClass(Class<T> clazz, NodeClass<? super T> superNodeClass, FieldsScanner.CalcOffset calcOffset, int[] presetIterableIds, int presetIterableId) {
182 super(clazz);
183 this.superNodeClass = superNodeClass;
184 assert NODE_CLASS.isAssignableFrom(clazz);
185
186 this.isCanonicalizable = Canonicalizable.class.isAssignableFrom(clazz);
187 this.isCommutative = BinaryCommutative.class.isAssignableFrom(clazz);
188 if (Canonicalizable.Unary.class.isAssignableFrom(clazz) || Canonicalizable.Binary.class.isAssignableFrom(clazz)) {
189 assert Canonicalizable.Unary.class.isAssignableFrom(clazz) ^ Canonicalizable.Binary.class.isAssignableFrom(clazz) : clazz + " should implement either Unary or Binary, not both";
190 }
191
192 this.isSimplifiable = Simplifiable.class.isAssignableFrom(clazz);
193
194 NodeFieldsScanner fs = new NodeFieldsScanner(calcOffset, superNodeClass);
195 try (DebugCloseable t = Init_FieldScanning.start()) {
196 fs.scan(clazz, clazz.getSuperclass(), false);
197 }
198
199 try (DebugCloseable t1 = Init_Edges.start()) {
200 successors = new SuccessorEdges(fs.directSuccessors, fs.successors);
201 successorIteration = computeIterationMask(successors.type(), successors.getDirectCount(), successors.getOffsets());
202 inputs = new InputEdges(fs.directInputs, fs.inputs);
203 inputsIteration = computeIterationMask(inputs.type(), inputs.getDirectCount(), inputs.getOffsets());
204 }
205 try (DebugCloseable t1 = Init_Data.start()) {
206 data = new Fields(fs.data);
207 }
208
209 isLeafNode = inputs.getCount() + successors.getCount() == 0;
210
211 canGVN = Node.ValueNumberable.class.isAssignableFrom(clazz);
212 startGVNNumber = clazz.getName().hashCode();
213
214 NodeInfo info = getAnnotationTimed(clazz, NodeInfo.class);
215 assert info != null : "Missing NodeInfo annotation on " + clazz;
216 this.nameTemplate = info.nameTemplate();
217
218 try (DebugCloseable t1 = Init_AllowedUsages.start()) {
219 allowedUsageTypes = superNodeClass == null ? EnumSet.noneOf(InputType.class) : superNodeClass.allowedUsageTypes.clone();
220 allowedUsageTypes.addAll(Arrays.asList(info.allowedUsageTypes()));
221 }
222
223 if (presetIterableIds != null) {
224 this.iterableIds = presetIterableIds;
225 this.iterableId = presetIterableId;
226 } else if (IterableNodeType.class.isAssignableFrom(clazz)) {
227 ITERABLE_NODE_TYPES.increment();
228 try (DebugCloseable t1 = Init_IterableIds.start()) {
229 this.iterableId = nextIterableId.getAndIncrement();
230
231 NodeClass<?> snc = superNodeClass;
232 while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {
233 snc.addIterableId(iterableId);
234 snc = snc.superNodeClass;
235 }
236
237 this.iterableIds = new int[]{iterableId};
238 }
239 } else {
240 this.iterableId = Node.NOT_ITERABLE;
241 this.iterableIds = null;
242 }
243 nodeIterableCount = Debug.counter("NodeIterable_%s", clazz);
244 assert verifyIterableIds();
245
246 try (Debug.Scope scope = Debug.scope("NodeCosts")) {
247 /*
248 * Note: We do not check for the existence of the node cost annotations during
249 * construction as not every node needs to have them set. However if costs are queried,
250 * after the construction of the node class, they must be properly set. This is
251 * important as we can not trust our cost model if there are unspecified nodes. Nodes
252 * that do not need cost annotations are e.g. abstractions like FixedNode or
253 * FloatingNode or ValueNode. Sub classes where costs are not specified will ask the
254 * superclass for their costs during node class initialization. Therefore getters for
255 * cycles and size can omit verification during creation.
256 */
257 NodeCycles c = info.cycles();
258 if (c == NodeCycles.CYCLES_UNSET) {
259 cycles = superNodeClass != null ? superNodeClass.cycles : NodeCycles.CYCLES_UNSET;
260 } else {
261 cycles = c;
262 }
263 assert cycles != null;
264 NodeSize s = info.size();
265 if (s == NodeSize.SIZE_UNSET) {
266 size = superNodeClass != null ? superNodeClass.size : NodeSize.SIZE_UNSET;
267 } else {
268 size = s;
269 }
270 assert size != null;
271 Debug.log("Node cost for node of type __| %s |_, cycles:%s,size:%s", clazz, cycles, size);
272 }
273
274 }
275
276 private final NodeCycles cycles;
277 private final NodeSize size;
278
279 public NodeCycles cycles() {
280 if (Options.VerifyNodeCostOnAccess.getValue() && cycles == NodeCycles.CYCLES_UNSET) {
281 throw new GraalError("Missing NodeCycles specification in the @NodeInfo annotation of the node %s", this);
282 }
283 return cycles;
284 }
285
286 public NodeSize size() {
287 if (Options.VerifyNodeCostOnAccess.getValue() && size == NodeSize.SIZE_UNSET) {
288 throw new GraalError("Missing NodeSize specification in the @NodeInfo annotation of the node %s", this);
289 }
290 return size;
291 }
292
293 public static long computeIterationMask(Type type, int directCount, long[] offsets) {
294 long mask = 0;
295 if (offsets.length > NodeClass.MAX_EDGES) {
296 throw new GraalError("Exceeded maximum of %d edges (%s)", NodeClass.MAX_EDGES, type);
297 }
298 if (offsets.length - directCount > NodeClass.MAX_LIST_EDGES) {
299 throw new GraalError("Exceeded maximum of %d list edges (%s)", NodeClass.MAX_LIST_EDGES, type);
300 }
301
302 for (int i = offsets.length - 1; i >= 0; i--) {
303 long offset = offsets[i];
304 assert ((offset & 0xFF) == offset) : "field offset too large!";
305 mask <<= NodeClass.NEXT_EDGE;
306 mask |= offset;
307 if (i >= directCount) {
308 mask |= 0x3;
309 }
310 }
311 return mask;
312 }
313
314 private synchronized void addIterableId(int newIterableId) {
315 assert !containsId(newIterableId, iterableIds);
316 int[] copy = Arrays.copyOf(iterableIds, iterableIds.length + 1);
317 copy[iterableIds.length] = newIterableId;
318 iterableIds = copy;
319 }
320
321 private boolean verifyIterableIds() {
322 NodeClass<?> snc = superNodeClass;
323 while (snc != null && IterableNodeType.class.isAssignableFrom(snc.getClazz())) {
324 assert containsId(iterableId, snc.iterableIds);
325 snc = snc.superNodeClass;
326 }
327 return true;
328 }
329
330 private static boolean containsId(int iterableId, int[] iterableIds) {
331 for (int i : iterableIds) {
332 if (i == iterableId) {
333 return true;
334 }
335 }
336 return false;
337 }
338
339 private String shortName;
340
341 public String shortName() {
342 if (shortName == null) {
343 NodeInfo info = getClazz().getAnnotation(NodeInfo.class);
344 if (!info.shortName().isEmpty()) {
345 shortName = info.shortName();
346 } else {
347 String localShortName = getClazz().getSimpleName();
348 if (localShortName.endsWith("Node") && !localShortName.equals("StartNode") && !localShortName.equals("EndNode")) {
349 shortName = localShortName.substring(0, localShortName.length() - 4);
350 } else {
351 shortName = localShortName;
352 }
353 }
354 }
355 return shortName;
356 }
357
358 @Override
359 public Fields[] getAllFields() {
360 return new Fields[]{data, inputs, successors};
361 }
362
363 public int[] iterableIds() {
364 nodeIterableCount.increment();
365 return iterableIds;
366 }
367
368 public int iterableId() {
369 return iterableId;
370 }
371
372 public boolean valueNumberable() {
373 return canGVN;
374 }
375
376 /**
377 * Determines if this node type implements {@link Canonicalizable}.
378 */
379 public boolean isCanonicalizable() {
380 return isCanonicalizable;
381 }
382
383 /**
384 * Determines if this node type implements {@link BinaryCommutative}.
385 */
386 public boolean isCommutative() {
387 return isCommutative;
388 }
389
390 /**
391 * Determines if this node type implements {@link Simplifiable}.
392 */
393 public boolean isSimplifiable() {
394 return isSimplifiable;
395 }
396
397 static int allocatedNodeIterabledIds() {
398 return nextIterableId.get();
399 }
400
401 public EnumSet<InputType> getAllowedUsageTypes() {
402 return allowedUsageTypes;
403 }
404
405 /**
406 * Describes a field representing an input or successor edge in a node.
407 */
408 protected static class EdgeInfo extends FieldsScanner.FieldInfo {
409
410 public EdgeInfo(long offset, String name, Class<?> type, Class<?> declaringClass) {
411 super(offset, name, type, declaringClass);
412 }
413
414 /**
415 * Sorts non-list edges before list edges.
416 */
417 @Override
418 public int compareTo(FieldsScanner.FieldInfo o) {
419 if (NodeList.class.isAssignableFrom(o.type)) {
420 if (!NodeList.class.isAssignableFrom(type)) {
421 return -1;
422 }
423 } else {
424 if (NodeList.class.isAssignableFrom(type)) {
425 return 1;
426 }
427 }
428 return super.compareTo(o);
429 }
430 }
431
432 /**
433 * Describes a field representing an {@linkplain Type#Inputs input} edge in a node.
434 */
435 protected static class InputInfo extends EdgeInfo {
436 final InputType inputType;
437 final boolean optional;
438
439 public InputInfo(long offset, String name, Class<?> type, Class<?> declaringClass, InputType inputType, boolean optional) {
440 super(offset, name, type, declaringClass);
441 this.inputType = inputType;
442 this.optional = optional;
443 }
444
445 @Override
446 public String toString() {
447 return super.toString() + "{inputType=" + inputType + ", optional=" + optional + "}";
448 }
449 }
450
451 protected static class NodeFieldsScanner extends FieldsScanner {
452
453 public final ArrayList<InputInfo> inputs = new ArrayList<>();
454 public final ArrayList<EdgeInfo> successors = new ArrayList<>();
455 int directInputs;
456 int directSuccessors;
457
458 protected NodeFieldsScanner(FieldsScanner.CalcOffset calc, NodeClass<?> superNodeClass) {
459 super(calc);
460 if (superNodeClass != null) {
461 translateInto(superNodeClass.inputs, inputs);
462 translateInto(superNodeClass.successors, successors);
463 translateInto(superNodeClass.data, data);
464 directInputs = superNodeClass.inputs.getDirectCount();
465 directSuccessors = superNodeClass.successors.getDirectCount();
466 }
467 }
468
469 @SuppressWarnings("try")
470 @Override
471 protected void scanField(Field field, long offset) {
472 Input inputAnnotation = getAnnotationTimed(field, Node.Input.class);
473 OptionalInput optionalInputAnnotation = getAnnotationTimed(field, Node.OptionalInput.class);
474 Successor successorAnnotation = getAnnotationTimed(field, Successor.class);
475 try (DebugCloseable s = Init_FieldScanningInner.start()) {
476 Class<?> type = field.getType();
477 int modifiers = field.getModifiers();
478
479 if (inputAnnotation != null || optionalInputAnnotation != null) {
480 assert successorAnnotation == null : "field cannot be both input and successor";
481 if (INPUT_LIST_CLASS.isAssignableFrom(type)) {
482 // NodeInputList fields should not be final since they are
483 // written (via Unsafe) in clearInputs()
484 GraalError.guarantee(!Modifier.isFinal(modifiers), "NodeInputList input field %s should not be final", field);
485 GraalError.guarantee(!Modifier.isPublic(modifiers), "NodeInputList input field %s should not be public", field);
486 } else {
487 GraalError.guarantee(NODE_CLASS.isAssignableFrom(type) || type.isInterface(), "invalid input type: %s", type);
488 GraalError.guarantee(!Modifier.isFinal(modifiers), "Node input field %s should not be final", field);
489 directInputs++;
490 }
491 InputType inputType;
492 if (inputAnnotation != null) {
493 assert optionalInputAnnotation == null : "inputs can either be optional or non-optional";
494 inputType = inputAnnotation.value();
495 } else {
496 inputType = optionalInputAnnotation.value();
497 }
498 inputs.add(new InputInfo(offset, field.getName(), type, field.getDeclaringClass(), inputType, field.isAnnotationPresent(Node.OptionalInput.class)));
499 } else if (successorAnnotation != null) {
500 if (SUCCESSOR_LIST_CLASS.isAssignableFrom(type)) {
501 // NodeSuccessorList fields should not be final since they are
502 // written (via Unsafe) in clearSuccessors()
503 GraalError.guarantee(!Modifier.isFinal(modifiers), "NodeSuccessorList successor field % should not be final", field);
504 GraalError.guarantee(!Modifier.isPublic(modifiers), "NodeSuccessorList successor field %s should not be public", field);
505 } else {
506 GraalError.guarantee(NODE_CLASS.isAssignableFrom(type), "invalid successor type: %s", type);
507 GraalError.guarantee(!Modifier.isFinal(modifiers), "Node successor field %s should not be final", field);
508 directSuccessors++;
509 }
510 successors.add(new EdgeInfo(offset, field.getName(), type, field.getDeclaringClass()));
511 } else {
512 GraalError.guarantee(!NODE_CLASS.isAssignableFrom(type) || field.getName().equals("Null"), "suspicious node field: %s", field);
513 GraalError.guarantee(!INPUT_LIST_CLASS.isAssignableFrom(type), "suspicious node input list field: %s", field);
514 GraalError.guarantee(!SUCCESSOR_LIST_CLASS.isAssignableFrom(type), "suspicious node successor list field: %s", field);
515 super.scanField(field, offset);
516 }
517 }
518 }
519 }
520
521 @Override
522 public String toString() {
523 StringBuilder str = new StringBuilder();
524 str.append("NodeClass ").append(getClazz().getSimpleName()).append(" [");
525 inputs.appendFields(str);
526 str.append("] [");
527 successors.appendFields(str);
528 str.append("] [");
529 data.appendFields(str);
530 str.append("]");
531 return str.toString();
532 }
533
534 private static int deepHashCode0(Object o) {
535 if (o instanceof Object[]) {
536 return Arrays.deepHashCode((Object[]) o);
537 } else if (o instanceof byte[]) {
538 return Arrays.hashCode((byte[]) o);
539 } else if (o instanceof short[]) {
540 return Arrays.hashCode((short[]) o);
541 } else if (o instanceof int[]) {
542 return Arrays.hashCode((int[]) o);
543 } else if (o instanceof long[]) {
544 return Arrays.hashCode((long[]) o);
545 } else if (o instanceof char[]) {
546 return Arrays.hashCode((char[]) o);
547 } else if (o instanceof float[]) {
548 return Arrays.hashCode((float[]) o);
549 } else if (o instanceof double[]) {
550 return Arrays.hashCode((double[]) o);
551 } else if (o instanceof boolean[]) {
552 return Arrays.hashCode((boolean[]) o);
553 } else if (o != null) {
554 return o.hashCode();
555 } else {
556 return 0;
557 }
558 }
559
560 public int valueNumber(Node n) {
561 int number = 0;
562 if (canGVN) {
563 number = startGVNNumber;
564 for (int i = 0; i < data.getCount(); ++i) {
565 Class<?> type = data.getType(i);
566 if (type.isPrimitive()) {
567 if (type == Integer.TYPE) {
568 int intValue = data.getInt(n, i);
569 number += intValue;
570 } else if (type == Long.TYPE) {
571 long longValue = data.getLong(n, i);
572 number += longValue ^ (longValue >>> 32);
573 } else if (type == Boolean.TYPE) {
574 boolean booleanValue = data.getBoolean(n, i);
575 if (booleanValue) {
576 number += 7;
577 }
578 } else if (type == Float.TYPE) {
579 float floatValue = data.getFloat(n, i);
580 number += Float.floatToRawIntBits(floatValue);
581 } else if (type == Double.TYPE) {
582 double doubleValue = data.getDouble(n, i);
583 long longValue = Double.doubleToRawLongBits(doubleValue);
584 number += longValue ^ (longValue >>> 32);
585 } else if (type == Short.TYPE) {
586 short shortValue = data.getShort(n, i);
587 number += shortValue;
588 } else if (type == Character.TYPE) {
589 char charValue = data.getChar(n, i);
590 number += charValue;
591 } else if (type == Byte.TYPE) {
592 byte byteValue = data.getByte(n, i);
593 number += byteValue;
594 } else {
595 assert false : "unhandled property type: " + type;
596 }
597 } else {
598 Object o = data.getObject(n, i);
599 number += deepHashCode0(o);
600 }
601 number *= 13;
602 }
603 }
604 return number;
605 }
606
607 private static boolean deepEquals0(Object e1, Object e2) {
608 assert e1 != null;
609 boolean eq;
610 if (e1 instanceof Object[] && e2 instanceof Object[]) {
611 eq = Arrays.deepEquals((Object[]) e1, (Object[]) e2);
612 } else if (e1 instanceof byte[] && e2 instanceof byte[]) {
613 eq = Arrays.equals((byte[]) e1, (byte[]) e2);
614 } else if (e1 instanceof short[] && e2 instanceof short[]) {
615 eq = Arrays.equals((short[]) e1, (short[]) e2);
616 } else if (e1 instanceof int[] && e2 instanceof int[]) {
617 eq = Arrays.equals((int[]) e1, (int[]) e2);
618 } else if (e1 instanceof long[] && e2 instanceof long[]) {
619 eq = Arrays.equals((long[]) e1, (long[]) e2);
620 } else if (e1 instanceof char[] && e2 instanceof char[]) {
621 eq = Arrays.equals((char[]) e1, (char[]) e2);
622 } else if (e1 instanceof float[] && e2 instanceof float[]) {
623 eq = Arrays.equals((float[]) e1, (float[]) e2);
624 } else if (e1 instanceof double[] && e2 instanceof double[]) {
625 eq = Arrays.equals((double[]) e1, (double[]) e2);
626 } else if (e1 instanceof boolean[] && e2 instanceof boolean[]) {
627 eq = Arrays.equals((boolean[]) e1, (boolean[]) e2);
628 } else {
629 eq = e1.equals(e2);
630 }
631 return eq;
632 }
633
634 public boolean dataEquals(Node a, Node b) {
635 assert a.getClass() == b.getClass();
636 for (int i = 0; i < data.getCount(); ++i) {
637 Class<?> type = data.getType(i);
638 if (type.isPrimitive()) {
639 if (type == Integer.TYPE) {
640 int aInt = data.getInt(a, i);
641 int bInt = data.getInt(b, i);
642 if (aInt != bInt) {
643 return false;
644 }
645 } else if (type == Boolean.TYPE) {
646 boolean aBoolean = data.getBoolean(a, i);
647 boolean bBoolean = data.getBoolean(b, i);
648 if (aBoolean != bBoolean) {
649 return false;
650 }
651 } else if (type == Long.TYPE) {
652 long aLong = data.getLong(a, i);
653 long bLong = data.getLong(b, i);
654 if (aLong != bLong) {
655 return false;
656 }
657 } else if (type == Float.TYPE) {
658 float aFloat = data.getFloat(a, i);
659 float bFloat = data.getFloat(b, i);
660 if (aFloat != bFloat) {
661 return false;
662 }
663 } else if (type == Double.TYPE) {
664 double aDouble = data.getDouble(a, i);
665 double bDouble = data.getDouble(b, i);
666 if (aDouble != bDouble) {
667 return false;
668 }
669 } else if (type == Short.TYPE) {
670 short aShort = data.getShort(a, i);
671 short bShort = data.getShort(b, i);
672 if (aShort != bShort) {
673 return false;
674 }
675 } else if (type == Character.TYPE) {
676 char aChar = data.getChar(a, i);
677 char bChar = data.getChar(b, i);
678 if (aChar != bChar) {
679 return false;
680 }
681 } else if (type == Byte.TYPE) {
682 byte aByte = data.getByte(a, i);
683 byte bByte = data.getByte(b, i);
684 if (aByte != bByte) {
685 return false;
686 }
687 } else {
688 assert false : "unhandled type: " + type;
689 }
690 } else {
691 Object objectA = data.getObject(a, i);
692 Object objectB = data.getObject(b, i);
693 if (objectA != objectB) {
694 if (objectA != null && objectB != null) {
695 if (!deepEquals0(objectA, objectB)) {
696 return false;
697 }
698 } else {
699 return false;
700 }
701 }
702 }
703 }
704 return true;
705 }
706
707 public boolean isValid(Position pos, NodeClass<?> from, Edges fromEdges) {
708 if (this == from) {
709 return true;
710 }
711 Edges toEdges = getEdges(fromEdges.type());
712 if (pos.getIndex() >= toEdges.getCount()) {
713 return false;
714 }
715 if (pos.getIndex() >= fromEdges.getCount()) {
716 return false;
717 }
718 return toEdges.isSame(fromEdges, pos.getIndex());
719 }
720
721 static void updateEdgesInPlace(Node node, InplaceUpdateClosure duplicationReplacement, Edges edges) {
722 int index = 0;
723 Type curType = edges.type();
724 int directCount = edges.getDirectCount();
725 final long[] curOffsets = edges.getOffsets();
726 while (index < directCount) {
727 Node edge = Edges.getNode(node, curOffsets, index);
728 if (edge != null) {
729 Node newEdge = duplicationReplacement.replacement(edge, curType);
730 if (curType == Edges.Type.Inputs) {
731 node.updateUsages(null, newEdge);
732 } else {
733 node.updatePredecessor(null, newEdge);
734 }
735 edges.initializeNode(node, index, newEdge);
736 }
737 index++;
738 }
739
740 while (index < edges.getCount()) {
741 NodeList<Node> list = Edges.getNodeList(node, curOffsets, index);
742 if (list != null) {
743 edges.initializeList(node, index, updateEdgeListCopy(node, list, duplicationReplacement, curType));
744 }
745 index++;
746 }
747 }
748
749 void updateInputSuccInPlace(Node node, InplaceUpdateClosure duplicationReplacement) {
750 updateEdgesInPlace(node, duplicationReplacement, inputs);
751 updateEdgesInPlace(node, duplicationReplacement, successors);
752 }
753
754 private static NodeList<Node> updateEdgeListCopy(Node node, NodeList<Node> list, InplaceUpdateClosure duplicationReplacement, Edges.Type type) {
755 NodeList<Node> result = type == Edges.Type.Inputs ? new NodeInputList<>(node, list.size()) : new NodeSuccessorList<>(node, list.size());
756
757 for (int i = 0; i < list.count(); ++i) {
758 Node oldNode = list.get(i);
759 if (oldNode != null) {
760 Node newNode = duplicationReplacement.replacement(oldNode, type);
761 result.set(i, newNode);
762 }
763 }
764 return result;
765 }
766
767 /**
768 * Gets the input or successor edges defined by this node class.
769 */
770 public Edges getEdges(Edges.Type type) {
771 return type == Edges.Type.Inputs ? inputs : successors;
772 }
773
774 public Edges getInputEdges() {
775 return inputs;
776 }
777
778 public Edges getSuccessorEdges() {
779 return successors;
780 }
781
782 /**
783 * Returns a newly allocated node for which no subclass-specific constructor has been called.
784 */
785 @SuppressWarnings("unchecked")
786 public Node allocateInstance() {
787 try {
788 Node node = (Node) UNSAFE.allocateInstance(getJavaClass());
789 node.init((NodeClass<? extends Node>) this);
790 return node;
791 } catch (InstantiationException ex) {
792 throw shouldNotReachHere(ex);
793 }
794 }
795
796 public Class<T> getJavaClass() {
797 return getClazz();
798 }
799
800 /**
801 * The template used to build the {@link Verbosity#Name} version. Variable parts are specified
802 * using {i#inputName} or {p#propertyName}.
803 */
804 public String getNameTemplate() {
805 return nameTemplate.isEmpty() ? shortName() : nameTemplate;
806 }
807
808 interface InplaceUpdateClosure {
809
810 Node replacement(Node node, Edges.Type type);
811 }
812
813 static Map<Node, Node> addGraphDuplicate(final Graph graph, final Graph oldGraph, int estimatedNodeCount, Iterable<? extends Node> nodes, final DuplicationReplacement replacements) {
814 final Map<Node, Node> newNodes;
815 int denseThreshold = oldGraph.getNodeCount() + oldGraph.getNodesDeletedSinceLastCompression() >> 4;
816 if (estimatedNodeCount > denseThreshold) {
817 // Use dense map
818 newNodes = new NodeNodeMap(oldGraph);
819 } else {
820 // Use sparse map
821 newNodes = newIdentityMap();
822 }
823 createNodeDuplicates(graph, nodes, replacements, newNodes);
824
825 InplaceUpdateClosure replacementClosure = new InplaceUpdateClosure() {
826
827 @Override
828 public Node replacement(Node node, Edges.Type type) {
829 Node target = newNodes.get(node);
830 if (target == null) {
831 Node replacement = node;
832 if (replacements != null) {
833 replacement = replacements.replacement(node);
834 }
835 if (replacement != node) {
836 target = replacement;
837 } else if (node.graph() == graph && type == Edges.Type.Inputs) {
838 // patch to the outer world
839 target = node;
840 }
841
842 }
843 return target;
844 }
845
846 };
847
848 // re-wire inputs
849 for (Node oldNode : nodes) {
850 Node node = newNodes.get(oldNode);
851 NodeClass<?> nodeClass = node.getNodeClass();
852 if (replacements == null || replacements.replacement(oldNode) == oldNode) {
853 nodeClass.updateInputSuccInPlace(node, replacementClosure);
854 } else {
855 transferEdgesDifferentNodeClass(graph, replacements, newNodes, oldNode, node);
856 }
857 }
858
859 return newNodes;
860 }
861
862 private static void createNodeDuplicates(final Graph graph, Iterable<? extends Node> nodes, final DuplicationReplacement replacements, final Map<Node, Node> newNodes) {
863 for (Node node : nodes) {
864 if (node != null) {
865 assert !node.isDeleted() : "trying to duplicate deleted node: " + node;
866 Node replacement = node;
867 if (replacements != null) {
868 replacement = replacements.replacement(node);
869 }
870 if (replacement != node) {
871 if (Fingerprint.ENABLED) {
872 Fingerprint.submit("replacing %s with %s", node, replacement);
873 }
874 assert replacement != null;
875 newNodes.put(node, replacement);
876 } else {
877 if (Fingerprint.ENABLED) {
878 Fingerprint.submit("duplicating %s", node);
879 }
880 Node newNode = node.clone(graph, WithAllEdges);
881 assert newNode.getNodeClass().isLeafNode() || newNode.hasNoUsages();
882 assert newNode.getClass() == node.getClass();
883 newNodes.put(node, newNode);
884 }
885 }
886 }
887 }
888
889 private static void transferEdgesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final Map<Node, Node> newNodes, Node oldNode, Node node) {
890 transferEdges(graph, replacements, newNodes, oldNode, node, Edges.Type.Inputs);
891 transferEdges(graph, replacements, newNodes, oldNode, node, Edges.Type.Successors);
892 }
893
894 private static void transferEdges(final Graph graph, final DuplicationReplacement replacements, final Map<Node, Node> newNodes, Node oldNode, Node node, Edges.Type type) {
895 NodeClass<?> nodeClass = node.getNodeClass();
896 NodeClass<?> oldNodeClass = oldNode.getNodeClass();
897 Edges oldEdges = oldNodeClass.getEdges(type);
898 for (Position pos : oldEdges.getPositionsIterable(oldNode)) {
899 if (!nodeClass.isValid(pos, oldNodeClass, oldEdges)) {
900 continue;
901 }
902 Node oldEdge = pos.get(oldNode);
903 if (oldEdge != null) {
904 Node target = newNodes.get(oldEdge);
905 if (target == null) {
906 Node replacement = oldEdge;
907 if (replacements != null) {
908 replacement = replacements.replacement(oldEdge);
909 }
910 if (replacement != oldEdge) {
911 target = replacement;
912 } else if (type == Edges.Type.Inputs && oldEdge.graph() == graph) {
913 // patch to the outer world
914 target = oldEdge;
915 }
916 }
917 pos.set(node, target);
918 }
919 }
920 }
921
922 /**
923 * @returns true if the node has no inputs and no successors
924 */
925 public boolean isLeafNode() {
926 return isLeafNode;
927 }
928
929 public long inputsIteration() {
930 return inputsIteration;
931 }
932
933 /**
934 * An iterator that will iterate over edges.
935 *
936 * An iterator of this type will not return null values, unless edges are modified concurrently.
937 * Concurrent modifications are detected by an assertion on a best-effort basis.
938 */
939 private static class RawEdgesIterator implements Iterator<Node> {
940 protected final Node node;
941 protected long mask;
942 protected Node nextValue;
943
944 RawEdgesIterator(Node node, long mask) {
945 this.node = node;
946 this.mask = mask;
947 }
948
949 @Override
950 public boolean hasNext() {
951 Node next = nextValue;
952 if (next != null) {
953 return true;
954 } else {
955 nextValue = forward();
956 return nextValue != null;
957 }
958 }
959
960 private Node forward() {
961 while (mask != 0) {
962 Node next = getInput();
963 mask = advanceInput();
964 if (next != null) {
965 return next;
966 }
967 }
968 return null;
969 }
970
971 @Override
972 public Node next() {
973 Node next = nextValue;
974 if (next == null) {
975 next = forward();
976 if (next == null) {
977 throw new NoSuchElementException();
978 } else {
979 return next;
980 }
981 } else {
982 nextValue = null;
983 return next;
984 }
985 }
986
987 public final long advanceInput() {
988 int state = (int) mask & 0x03;
989 if (state == 0) {
990 // Skip normal field.
991 return mask >>> NEXT_EDGE;
992 } else if (state == 1) {
993 // We are iterating a node list.
994 if ((mask & 0xFFFF00) != 0) {
995 // Node list count is non-zero, decrease by 1.
996 return mask - 0x100;
997 } else {
998 // Node list is finished => go to next input.
999 return mask >>> 24;
1000 }
1001 } else {
1002 // Need to expand node list.
1003 NodeList<?> nodeList = Edges.getNodeListUnsafe(node, mask & 0xFC);
1004 if (nodeList != null) {
1005 int size = nodeList.size();
1006 if (size != 0) {
1007 // Set pointer to upper most index of node list.
1008 return ((mask >>> NEXT_EDGE) << 24) | (mask & 0xFD) | ((size - 1) << NEXT_EDGE);
1009 }
1010 }
1011 // Node list is empty or null => skip.
1012 return mask >>> NEXT_EDGE;
1013 }
1014 }
1015
1016 public Node getInput() {
1017 int state = (int) mask & 0x03;
1018 if (state == 0) {
1019 return Edges.getNodeUnsafe(node, mask & 0xFC);
1020 } else if (state == 1) {
1021 // We are iterating a node list.
1022 NodeList<?> nodeList = Edges.getNodeListUnsafe(node, mask & 0xFC);
1023 return nodeList.nodes[nodeList.size() - 1 - (int) ((mask >>> NEXT_EDGE) & 0xFFFF)];
1024 } else {
1025 // Node list needs to expand first.
1026 return null;
1027 }
1028 }
1029
1030 @Override
1031 public void remove() {
1032 throw new UnsupportedOperationException();
1033 }
1034
1035 public Position nextPosition() {
1036 return null;
1037 }
1038 }
1039
1040 private static final class RawEdgesWithModCountIterator extends RawEdgesIterator {
1041 private final int modCount;
1042
1043 private RawEdgesWithModCountIterator(Node node, long mask) {
1044 super(node, mask);
1045 assert isModificationCountsEnabled();
1046 this.modCount = node.modCount();
1047 }
1048
1049 @Override
1050 public boolean hasNext() {
1051 try {
1052 return super.hasNext();
1053 } finally {
1054 assert modCount == node.modCount() : "must not be modified";
1055 }
1056 }
1057
1058 @Override
1059 public Node next() {
1060 try {
1061 return super.next();
1062 } finally {
1063 assert modCount == node.modCount() : "must not be modified";
1064 }
1065 }
1066
1067 @Override
1068 public Position nextPosition() {
1069 try {
1070 return super.nextPosition();
1071 } finally {
1072 assert modCount == node.modCount();
1073 }
1074 }
1075 }
1076
1077 public NodeIterable<Node> getSuccessorIterable(final Node node) {
1078 long mask = this.successorIteration;
1079 return new NodeIterable<Node>() {
1080
1081 @Override
1082 public Iterator<Node> iterator() {
1083 if (isModificationCountsEnabled()) {
1084 return new RawEdgesWithModCountIterator(node, mask);
1085 } else {
1086 return new RawEdgesIterator(node, mask);
1087 }
1088 }
1089 };
1090 }
1091
1092 public NodeIterable<Node> getInputIterable(final Node node) {
1093 long mask = this.inputsIteration;
1094 return new NodeIterable<Node>() {
1095
1096 @Override
1097 public Iterator<Node> iterator() {
1098 if (isModificationCountsEnabled()) {
1099 return new RawEdgesWithModCountIterator(node, mask);
1100 } else {
1101 return new RawEdgesIterator(node, mask);
1102 }
1103 }
1104 };
1105 }
1106
1107 public boolean equalSuccessors(Node node, Node other) {
1108 return equalEdges(node, other, successorIteration);
1109 }
1110
1111 public boolean equalInputs(Node node, Node other) {
1112 return equalEdges(node, other, inputsIteration);
1113 }
1114
1115 private boolean equalEdges(Node node, Node other, long mask) {
1116 long myMask = mask;
1117 assert other.getNodeClass() == this;
1118 while (myMask != 0) {
1119 long offset = (myMask & OFFSET_MASK);
1120 Object v1 = UNSAFE.getObject(node, offset);
1121 Object v2 = UNSAFE.getObject(other, offset);
1122 if ((myMask & LIST_MASK) == 0) {
1123 if (v1 != v2) {
1124 return false;
1125 }
1126 } else {
1127 if (!Objects.equals(v1, v2)) {
1128 return false;
1129 }
1130 }
1131 myMask >>>= NEXT_EDGE;
1132 }
1133 return true;
1134 }
1135
1136 public void pushInputs(Node node, NodeStack stack) {
1137 long myMask = this.inputsIteration;
1138 while (myMask != 0) {
1139 long offset = (myMask & OFFSET_MASK);
1140 if ((myMask & LIST_MASK) == 0) {
1141 Node curNode = Edges.getNodeUnsafe(node, offset);
1142 if (curNode != null) {
1143 stack.push(curNode);
1144 }
1145 } else {
1146 pushAllHelper(stack, node, offset);
1147 }
1148 myMask >>>= NEXT_EDGE;
1149 }
1150 }
1151
1152 private static void pushAllHelper(NodeStack stack, Node node, long offset) {
1153 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1154 if (list != null) {
1155 for (int i = 0; i < list.size(); ++i) {
1156 Node curNode = list.get(i);
1157 if (curNode != null) {
1158 stack.push(curNode);
1159 }
1160 }
1161 }
1162 }
1163
1164 public void applySuccessors(Node node, EdgeVisitor consumer) {
1165 applyEdges(node, consumer, this.successorIteration);
1166 }
1167
1168 public void applyInputs(Node node, EdgeVisitor consumer) {
1169 applyEdges(node, consumer, this.inputsIteration);
1170 }
1171
1172 private static void applyEdges(Node node, EdgeVisitor consumer, long mask) {
1173 long myMask = mask;
1174 while (myMask != 0) {
1175 long offset = (myMask & OFFSET_MASK);
1176 if ((myMask & LIST_MASK) == 0) {
1177 Node curNode = Edges.getNodeUnsafe(node, offset);
1178 if (curNode != null) {
1179 Node newNode = consumer.apply(node, curNode);
1180 if (newNode != curNode) {
1181 UNSAFE.putObject(node, offset, newNode);
1182 }
1183 }
1184 } else {
1185 applyHelper(node, consumer, offset);
1186 }
1187 myMask >>>= NEXT_EDGE;
1188 }
1189 }
1190
1191 private static void applyHelper(Node node, EdgeVisitor consumer, long offset) {
1192 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1193 if (list != null) {
1194 for (int i = 0; i < list.size(); ++i) {
1195 Node curNode = list.get(i);
1196 if (curNode != null) {
1197 Node newNode = consumer.apply(node, curNode);
1198 if (newNode != curNode) {
1199 list.initialize(i, newNode);
1200 }
1201 }
1202 }
1203 }
1204 }
1205
1206 public void unregisterAtSuccessorsAsPredecessor(Node node) {
1207 long myMask = this.successorIteration;
1208 while (myMask != 0) {
1209 long offset = (myMask & OFFSET_MASK);
1210 if ((myMask & LIST_MASK) == 0) {
1211 Node curNode = Edges.getNodeUnsafe(node, offset);
1212 if (curNode != null) {
1213 node.updatePredecessor(curNode, null);
1214 UNSAFE.putObject(node, offset, null);
1215 }
1216 } else {
1217 unregisterAtSuccessorsAsPredecessorHelper(node, offset);
1218 }
1219 myMask >>>= NEXT_EDGE;
1220 }
1221 }
1222
1223 private static void unregisterAtSuccessorsAsPredecessorHelper(Node node, long offset) {
1224 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1225 if (list != null) {
1226 for (int i = 0; i < list.size(); ++i) {
1227 Node curNode = list.get(i);
1228 if (curNode != null) {
1229 node.updatePredecessor(curNode, null);
1230 }
1231 }
1232 list.clearWithoutUpdate();
1233 }
1234 }
1235
1236 public void registerAtSuccessorsAsPredecessor(Node node) {
1237 long myMask = this.successorIteration;
1238 while (myMask != 0) {
1239 long offset = (myMask & OFFSET_MASK);
1240 if ((myMask & LIST_MASK) == 0) {
1241 Node curNode = Edges.getNodeUnsafe(node, offset);
1242 if (curNode != null) {
1243 assert curNode.isAlive() : "Successor not alive";
1244 node.updatePredecessor(null, curNode);
1245 }
1246 } else {
1247 registerAtSuccessorsAsPredecessorHelper(node, offset);
1248 }
1249 myMask >>>= NEXT_EDGE;
1250 }
1251 }
1252
1253 private static void registerAtSuccessorsAsPredecessorHelper(Node node, long offset) {
1254 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1255 if (list != null) {
1256 for (int i = 0; i < list.size(); ++i) {
1257 Node curNode = list.get(i);
1258 if (curNode != null) {
1259 assert curNode.isAlive() : "Successor not alive";
1260 node.updatePredecessor(null, curNode);
1261 }
1262 }
1263 }
1264 }
1265
1266 public boolean replaceFirstInput(Node node, Node key, Node replacement) {
1267 return replaceFirstEdge(node, key, replacement, this.inputsIteration);
1268 }
1269
1270 public boolean replaceFirstSuccessor(Node node, Node key, Node replacement) {
1271 return replaceFirstEdge(node, key, replacement, this.successorIteration);
1272 }
1273
1274 public static boolean replaceFirstEdge(Node node, Node key, Node replacement, long mask) {
1275 long myMask = mask;
1276 while (myMask != 0) {
1277 long offset = (myMask & OFFSET_MASK);
1278 if ((myMask & LIST_MASK) == 0) {
1279 Object curNode = UNSAFE.getObject(node, offset);
1280 if (curNode == key) {
1281 UNSAFE.putObject(node, offset, replacement);
1282 return true;
1283 }
1284 } else {
1285 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1286 if (list != null && list.replaceFirst(key, replacement)) {
1287 return true;
1288 }
1289 }
1290 myMask >>>= NEXT_EDGE;
1291 }
1292 return false;
1293 }
1294
1295 public void registerAtInputsAsUsage(Node node) {
1296 long myMask = this.inputsIteration;
1297 while (myMask != 0) {
1298 long offset = (myMask & OFFSET_MASK);
1299 if ((myMask & LIST_MASK) == 0) {
1300 Node curNode = Edges.getNodeUnsafe(node, offset);
1301 if (curNode != null) {
1302 assert curNode.isAlive() : "Input not alive " + curNode;
1303 curNode.addUsage(node);
1304 }
1305 } else {
1306 registerAtInputsAsUsageHelper(node, offset);
1307 }
1308 myMask >>>= NEXT_EDGE;
1309 }
1310 }
1311
1312 private static void registerAtInputsAsUsageHelper(Node node, long offset) {
1313 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1314 if (list != null) {
1315 for (int i = 0; i < list.size(); ++i) {
1316 Node curNode = list.get(i);
1317 if (curNode != null) {
1318 assert curNode.isAlive() : "Input not alive";
1319 curNode.addUsage(node);
1320 }
1321 }
1322 }
1323 }
1324
1325 public void unregisterAtInputsAsUsage(Node node) {
1326 long myMask = this.inputsIteration;
1327 while (myMask != 0) {
1328 long offset = (myMask & OFFSET_MASK);
1329 if ((myMask & LIST_MASK) == 0) {
1330 Node curNode = Edges.getNodeUnsafe(node, offset);
1331 if (curNode != null) {
1332 node.removeThisFromUsages(curNode);
1333 if (curNode.hasNoUsages()) {
1334 node.maybeNotifyZeroUsages(curNode);
1335 }
1336 UNSAFE.putObject(node, offset, null);
1337 }
1338 } else {
1339 unregisterAtInputsAsUsageHelper(node, offset);
1340 }
1341 myMask >>>= NEXT_EDGE;
1342 }
1343 }
1344
1345 private static void unregisterAtInputsAsUsageHelper(Node node, long offset) {
1346 NodeList<Node> list = Edges.getNodeListUnsafe(node, offset);
1347 if (list != null) {
1348 for (int i = 0; i < list.size(); ++i) {
1349 Node curNode = list.get(i);
1350 if (curNode != null) {
1351 node.removeThisFromUsages(curNode);
1352 if (curNode.hasNoUsages()) {
1353 node.maybeNotifyZeroUsages(curNode);
1354 }
1355 }
1356 }
1357 list.clearWithoutUpdate();
1358 }
1359 }
1360 }