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