1 /*
   2  * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.graph;
  26 
  27 import static org.graalvm.compiler.core.common.Fields.translateInto;
  28 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
  29 import static org.graalvm.compiler.graph.Edges.translateInto;
  30 import static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
  31 import static org.graalvm.compiler.graph.InputEdges.translateInto;
  32 import static org.graalvm.compiler.graph.Node.WithAllEdges;
  33 import static org.graalvm.compiler.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                 Object v1 = Edges.getNodeListUnsafe(node, offset);
1221                 Object 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 }