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