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