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