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