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