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