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