1 /*
   2  * Copyright (c) 2015, 2015, 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 package org.graalvm.compiler.nodes;
  24 
  25 import static org.graalvm.compiler.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;
  26 
  27 import java.util.ArrayDeque;
  28 import java.util.Deque;
  29 import java.util.Iterator;
  30 import java.util.Map;
  31 import java.util.Objects;
  32 
  33 import org.graalvm.compiler.core.common.Fields;
  34 import org.graalvm.compiler.core.common.util.FrequencyEncoder;
  35 import org.graalvm.compiler.core.common.util.TypeConversion;
  36 import org.graalvm.compiler.core.common.util.TypeReader;
  37 import org.graalvm.compiler.core.common.util.TypeWriter;
  38 import org.graalvm.compiler.core.common.util.UnsafeArrayTypeWriter;
  39 import org.graalvm.compiler.debug.Debug;
  40 import org.graalvm.compiler.graph.Edges;
  41 import org.graalvm.compiler.graph.Node;
  42 import org.graalvm.compiler.graph.NodeClass;
  43 import org.graalvm.compiler.graph.NodeList;
  44 import org.graalvm.compiler.graph.NodeMap;
  45 import org.graalvm.compiler.graph.iterators.NodeIterable;
  46 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
  47 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
  48 
  49 import jdk.vm.ci.code.Architecture;
  50 
  51 /**
  52  * Encodes a {@link StructuredGraph} to a compact byte[] array. All nodes of the graph and edges
  53  * between the nodes are encoded. Primitive data fields of nodes are stored in the byte[] array.
  54  * Object data fields of nodes are stored in a separate Object[] array.
  55  *
  56  * One encoder instance can be used to encode multiple graphs. This requires that {@link #prepare}
  57  * is called for all graphs first, followed by one call to {@link #finishPrepare}. Then
  58  * {@link #encode} can be called for all graphs. The {@link #getObjects() objects} and
  59  * {@link #getNodeClasses() node classes} arrays do not change anymore after preparation.
  60  *
  61  * Multiple encoded graphs share the Object[] array, and elements of the Object[] array are
  62  * de-duplicated using {@link Object#equals Object equality}. This uses the assumption and good
  63  * coding practice that data objects are immutable if {@link Object#equals} is implemented.
  64  * Unfortunately, this cannot be enforced.
  65  *
  66  * The Graal {@link NodeClass} does not have a unique id that allows class lookup from an id.
  67  * Therefore, the encoded graph contains a {@link NodeClass}[] array for lookup, and type ids are
  68  * encoding-local.
  69  *
  70  * The encoded graph has the following structure: First, all nodes and their edges are serialized.
  71  * The start offset of every node is then known. The raw node data is followed by a "table of
  72  * contents" that lists the start offset for every node.
  73  *
  74  * The beginning of that table of contents is the return value of {@link #encode} and stored in
  75  * {@link EncodedGraph#getStartOffset()}. The order of nodes in the table of contents is the
  76  * {@link NodeOrder#orderIds orderId} of a node. Note that the orderId is not the regular node id
  77  * that every Graal graph node gets assigned. The orderId is computed and used just for encoding and
  78  * decoding. The orderId of fixed nodes is assigned in reverse postorder. The decoder processes
  79  * nodes using that order, which ensures that all predecessors of a node (including all
  80  * {@link EndNode predecessors} of a {@link AbstractBeginNode block}) are decoded before the node.
  81  * The order id of floating node does not matter during decoding, so floating nodes get order ids
  82  * after all fixed nodes. The order id is used to encode edges between nodes
  83  *
  84  * Structure of an encoded node:
  85  *
  86  * <pre>
  87  * struct Node {
  88  *   unsigned typeId
  89  *   signed[] properties
  90  *   unsigned[] successorOrderIds
  91  *   unsigned[] inputOrderIds
  92  * }
  93  * </pre>
  94  *
  95  * All numbers (unsigned and signed) are stored using a variable-length encoding as defined in
  96  * {@link TypeReader} and {@link TypeWriter}. Especially orderIds are small, so the variable-length
  97  * encoding is important to keep the encoding compact.
  98  *
  99  * The properties, successors, and inputs are written in the order as defined in
 100  * {@link NodeClass#getData}, {@link NodeClass#getSuccessorEdges()}, and
 101  * {@link NodeClass#getInputEdges()}. For variable-length successors and input lists, first the
 102  * length is written and then the orderIds. There is a distinction between null lists (encoded as
 103  * length -1) and empty lists (encoded as length 0). No reverse edges are written (predecessors,
 104  * usages) since that information can be easily restored during decoding.
 105  *
 106  * Some nodes have additional information written after the properties, successors, and inputs:
 107  * <li><item>{@link AbstractEndNode}: the orderId of the merge node and then all {@link PhiNode phi
 108  * mappings} from this end to the merge node are written. <item>{@link LoopExitNode}: the orderId of
 109  * all {@link ProxyNode proxy nodes} of the loop exit is written.</li>
 110  */
 111 public class GraphEncoder {
 112 
 113     /** The orderId that always represents {@code null}. */
 114     public static final int NULL_ORDER_ID = 0;
 115     /** The orderId of the {@link StructuredGraph#start() start node} of the encoded graph. */
 116     public static final int START_NODE_ORDER_ID = 1;
 117     /**
 118      * The orderId of the first actual node after the {@link StructuredGraph#start() start node}.
 119      */
 120     public static final int FIRST_NODE_ORDER_ID = 2;
 121 
 122     /**
 123      * The known offset between the orderId of a {@link AbstractBeginNode} and its
 124      * {@link AbstractBeginNode#next() successor}.
 125      */
 126     protected static final int BEGIN_NEXT_ORDER_ID_OFFSET = 1;
 127 
 128     protected final Architecture architecture;
 129 
 130     /**
 131      * Collects all non-primitive data referenced from nodes. The encoding uses an index into an
 132      * array for decoding. Because of the variable-length encoding, it is beneficial that frequently
 133      * used objects have the small indices.
 134      */
 135     protected final FrequencyEncoder<Object> objects;
 136     /**
 137      * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass}
 138      * currently does not have a unique id.
 139      */
 140     protected final FrequencyEncoder<NodeClass<?>> nodeClasses;
 141     /** The writer for the encoded graphs. */
 142     protected final UnsafeArrayTypeWriter writer;
 143 
 144     /** The last snapshot of {@link #objects} that was retrieved. */
 145     protected Object[] objectsArray;
 146     /** The last snapshot of {@link #nodeClasses} that was retrieved. */
 147     protected NodeClass<?>[] nodeClassesArray;
 148 
 149     /**
 150      * Utility method that does everything necessary to encode a single graph.
 151      */
 152     public static EncodedGraph encodeSingleGraph(StructuredGraph graph, Architecture architecture) {
 153         GraphEncoder encoder = new GraphEncoder(architecture);
 154         encoder.prepare(graph);
 155         encoder.finishPrepare();
 156         long startOffset = encoder.encode(graph);
 157         return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph.getAssumptions(), graph.getMethods());
 158     }
 159 
 160     public GraphEncoder(Architecture architecture) {
 161         this.architecture = architecture;
 162         objects = FrequencyEncoder.createEqualityEncoder();
 163         nodeClasses = FrequencyEncoder.createIdentityEncoder();
 164         writer = UnsafeArrayTypeWriter.create(architecture.supportsUnalignedMemoryAccess());
 165     }
 166 
 167     /**
 168      * Must be invoked before {@link #finishPrepare()} and {@link #encode}.
 169      */
 170     public void prepare(StructuredGraph graph) {
 171         for (Node node : graph.getNodes()) {
 172             nodeClasses.addObject(node.getNodeClass());
 173 
 174             NodeClass<?> nodeClass = node.getNodeClass();
 175             objects.addObject(node.getNodeSourcePosition());
 176             for (int i = 0; i < nodeClass.getData().getCount(); i++) {
 177                 if (!nodeClass.getData().getType(i).isPrimitive()) {
 178                     objects.addObject(nodeClass.getData().get(node, i));
 179                 }
 180             }
 181             if (node instanceof Invoke) {
 182                 objects.addObject(((Invoke) node).getContextType());
 183             }
 184         }
 185     }
 186 
 187     public void finishPrepare() {
 188         objectsArray = objects.encodeAll(new Object[objects.getLength()]);
 189         nodeClassesArray = nodeClasses.encodeAll(new NodeClass<?>[nodeClasses.getLength()]);
 190     }
 191 
 192     public Object[] getObjects() {
 193         return objectsArray;
 194     }
 195 
 196     public NodeClass<?>[] getNodeClasses() {
 197         return nodeClassesArray;
 198     }
 199 
 200     /**
 201      * Compresses a graph to a byte array. Multiple graphs can be compressed with the same
 202      * {@link GraphEncoder}.
 203      *
 204      * @param graph The graph to encode
 205      */
 206     public long encode(StructuredGraph graph) {
 207         assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()";
 208 
 209         NodeOrder nodeOrder = new NodeOrder(graph);
 210         int nodeCount = nodeOrder.nextOrderId;
 211         assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID;
 212         assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID;
 213         assert nodeCount == graph.getNodeCount() + 1;
 214 
 215         long[] nodeStartOffsets = new long[nodeCount];
 216         for (Map.Entry<Node, Integer> entry : nodeOrder.orderIds.entries()) {
 217             Node node = entry.getKey();
 218             Integer orderId = entry.getValue();
 219 
 220             assert !(node instanceof AbstractBeginNode) || nodeOrder.orderIds.get(((AbstractBeginNode) node).next()) == orderId + BEGIN_NEXT_ORDER_ID_OFFSET;
 221             nodeStartOffsets[orderId] = writer.getBytesWritten();
 222 
 223             /* Write out the type, properties, and edges. */
 224             NodeClass<?> nodeClass = node.getNodeClass();
 225             writer.putUV(nodeClasses.getIndex(nodeClass));
 226             writeProperties(node, nodeClass.getData());
 227             writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), nodeOrder);
 228             writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder);
 229 
 230             /* Special handling for some nodes that require additional information for decoding. */
 231             if (node instanceof AbstractEndNode) {
 232                 AbstractEndNode end = (AbstractEndNode) node;
 233                 AbstractMergeNode merge = end.merge();
 234                 /*
 235                  * Write the orderId of the merge. The merge is not a successor in the Graal graph
 236                  * (only the merge has an input edge to the EndNode).
 237                  */
 238                 writeOrderId(merge, nodeOrder);
 239 
 240                 /*
 241                  * Write all phi mappings (the oderId of the phi input for this EndNode, and the
 242                  * orderId of the phi node.
 243                  */
 244                 writer.putUV(merge.phis().count());
 245                 for (PhiNode phi : merge.phis()) {
 246                     writeOrderId(phi.valueAt(end), nodeOrder);
 247                     writeOrderId(phi, nodeOrder);
 248                 }
 249 
 250             } else if (node instanceof LoopExitNode) {
 251                 LoopExitNode exit = (LoopExitNode) node;
 252                 writeOrderId(exit.stateAfter(), nodeOrder);
 253                 /* Write all proxy nodes of the LoopExitNode. */
 254                 writer.putUV(exit.proxies().count());
 255                 for (ProxyNode proxy : exit.proxies()) {
 256                     writeOrderId(proxy, nodeOrder);
 257                 }
 258 
 259             } else if (node instanceof Invoke) {
 260                 Invoke invoke = (Invoke) node;
 261                 assert invoke.stateDuring() == null : "stateDuring is not used in high-level graphs";
 262 
 263                 writeObjectId(invoke.getContextType());
 264                 writeOrderId(invoke.callTarget(), nodeOrder);
 265                 writeOrderId(invoke.stateAfter(), nodeOrder);
 266                 writeOrderId(invoke.next(), nodeOrder);
 267                 if (invoke instanceof InvokeWithExceptionNode) {
 268                     InvokeWithExceptionNode invokeWithExcpetion = (InvokeWithExceptionNode) invoke;
 269                     ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExcpetion.exceptionEdge();
 270 
 271                     writeOrderId(invokeWithExcpetion.next().next(), nodeOrder);
 272                     writeOrderId(invokeWithExcpetion.exceptionEdge(), nodeOrder);
 273                     writeOrderId(exceptionEdge.stateAfter(), nodeOrder);
 274                     writeOrderId(exceptionEdge.next(), nodeOrder);
 275                 }
 276             }
 277         }
 278 
 279         /* Write out the table of contents with the start offset for all nodes. */
 280         long nodeTableStart = writer.getBytesWritten();
 281         writer.putUV(nodeCount);
 282         for (int i = 0; i < nodeCount; i++) {
 283             assert i == NULL_ORDER_ID || i == START_NODE_ORDER_ID || nodeStartOffsets[i] > 0;
 284             writer.putUV(nodeTableStart - nodeStartOffsets[i]);
 285         }
 286 
 287         /* Check that the decoding of the encode graph is the same as the input. */
 288         assert verifyEncoding(graph, new EncodedGraph(getEncoding(), nodeTableStart, getObjects(), getNodeClasses(), graph.getAssumptions(), graph.getMethods()), architecture);
 289 
 290         return nodeTableStart;
 291     }
 292 
 293     public byte[] getEncoding() {
 294         return writer.toArray(new byte[TypeConversion.asS4(writer.getBytesWritten())]);
 295     }
 296 
 297     static class NodeOrder {
 298         protected final NodeMap<Integer> orderIds;
 299         protected int nextOrderId;
 300 
 301         NodeOrder(StructuredGraph graph) {
 302             this.orderIds = new NodeMap<>(graph);
 303             this.nextOrderId = START_NODE_ORDER_ID;
 304 
 305             /* Order the fixed nodes of the graph in reverse postorder. */
 306             Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
 307             FixedNode current = graph.start();
 308             do {
 309                 add(current);
 310                 if (current instanceof AbstractBeginNode) {
 311                     add(((AbstractBeginNode) current).next());
 312                 }
 313 
 314                 if (current instanceof FixedWithNextNode) {
 315                     current = ((FixedWithNextNode) current).next;
 316                 } else {
 317                     if (current instanceof ControlSplitNode) {
 318                         for (Node successor : current.successors()) {
 319                             if (successor != null) {
 320                                 nodeQueue.addFirst((AbstractBeginNode) successor);
 321                             }
 322                         }
 323                     } else if (current instanceof EndNode) {
 324                         AbstractMergeNode merge = ((AbstractEndNode) current).merge();
 325                         boolean allForwardEndsVisited = true;
 326                         for (int i = 0; i < merge.forwardEndCount(); i++) {
 327                             if (orderIds.get(merge.forwardEndAt(i)) == null) {
 328                                 allForwardEndsVisited = false;
 329                                 break;
 330                             }
 331                         }
 332                         if (allForwardEndsVisited) {
 333                             nodeQueue.add(merge);
 334                         }
 335                     }
 336                     current = nodeQueue.pollFirst();
 337                 }
 338             } while (current != null);
 339 
 340             for (Node node : graph.getNodes()) {
 341                 assert (node instanceof FixedNode) == (orderIds.get(node) != null) : "all fixed nodes must be ordered";
 342                 add(node);
 343             }
 344         }
 345 
 346         private void add(Node node) {
 347             if (orderIds.get(node) == null) {
 348                 orderIds.set(node, nextOrderId);
 349                 nextOrderId++;
 350             }
 351         }
 352     }
 353 
 354     protected void writeProperties(Node node, Fields fields) {
 355         writeObjectId(node.getNodeSourcePosition());
 356         for (int idx = 0; idx < fields.getCount(); idx++) {
 357             if (fields.getType(idx).isPrimitive()) {
 358                 long primitive = fields.getRawPrimitive(node, idx);
 359                 writer.putSV(primitive);
 360             } else {
 361                 Object property = fields.get(node, idx);
 362                 writeObjectId(property);
 363             }
 364         }
 365     }
 366 
 367     protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) {
 368         for (int idx = 0; idx < edges.getDirectCount(); idx++) {
 369             if (GraphDecoder.skipEdge(node, edges, idx, true, false)) {
 370                 /* Edge is not needed for decoding, so we must not write it. */
 371                 continue;
 372             }
 373             Node edge = Edges.getNode(node, edges.getOffsets(), idx);
 374             writeOrderId(edge, nodeOrder);
 375         }
 376         for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) {
 377             if (GraphDecoder.skipEdge(node, edges, idx, false, false)) {
 378                 /* Edge is not needed for decoding, so we must not write it. */
 379                 continue;
 380             }
 381             NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx);
 382             if (edgeList == null) {
 383                 writer.putSV(-1);
 384             } else {
 385                 writer.putSV(edgeList.size());
 386                 for (Node edge : edgeList) {
 387                     writeOrderId(edge, nodeOrder);
 388                 }
 389             }
 390         }
 391     }
 392 
 393     protected void writeOrderId(Node node, NodeOrder nodeOrder) {
 394         writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node));
 395     }
 396 
 397     protected void writeObjectId(Object object) {
 398         writer.putUV(objects.getIndex(object));
 399     }
 400 
 401     /**
 402      * Verification code that checks that the decoding of an encode graph is the same as the
 403      * original graph.
 404      */
 405     @SuppressWarnings("try")
 406     public static boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph, Architecture architecture) {
 407         StructuredGraph decodedGraph = new StructuredGraph(originalGraph.method(), AllowAssumptions.YES, INVALID_COMPILATION_ID);
 408         GraphDecoder decoder = new GraphDecoder(architecture);
 409         decoder.decode(decodedGraph, encodedGraph);
 410 
 411         decodedGraph.verify();
 412         try {
 413             GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph);
 414         } catch (Throwable ex) {
 415             try (Debug.Scope scope = Debug.scope("GraphEncoder")) {
 416                 Debug.dump(Debug.INFO_LOG_LEVEL, originalGraph, "Original Graph");
 417                 Debug.dump(Debug.INFO_LOG_LEVEL, decodedGraph, "Decoded Graph");
 418             }
 419             throw ex;
 420         }
 421         return true;
 422     }
 423 }
 424 
 425 class GraphComparison {
 426     public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) {
 427         NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph);
 428         Deque<Pair<Node, Node>> workList = new ArrayDeque<>();
 429 
 430         pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList);
 431         while (!workList.isEmpty()) {
 432             Pair<Node, Node> pair = workList.removeFirst();
 433             Node expectedNode = pair.first;
 434             Node actualNode = pair.second;
 435             assert expectedNode.getClass() == actualNode.getClass();
 436 
 437             NodeClass<?> nodeClass = expectedNode.getNodeClass();
 438             assert nodeClass == actualNode.getNodeClass();
 439 
 440             if (expectedNode instanceof MergeNode) {
 441                 /* The order of the ends can be different, so ignore them. */
 442                 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true);
 443             } else if (expectedNode instanceof PhiNode) {
 444                 verifyPhi((PhiNode) expectedNode, (PhiNode) actualNode, nodeMapping, workList);
 445             } else {
 446                 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false);
 447             }
 448             verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false);
 449 
 450             if (expectedNode instanceof LoopEndNode) {
 451                 LoopEndNode actualLoopEnd = (LoopEndNode) actualNode;
 452                 assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex();
 453             } else {
 454                 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
 455                     Object expectedProperty = nodeClass.getData().get(expectedNode, i);
 456                     Object actualProperty = nodeClass.getData().get(actualNode, i);
 457                     assert Objects.equals(expectedProperty, actualProperty);
 458                 }
 459             }
 460 
 461             if (expectedNode instanceof EndNode) {
 462                 /* Visit the merge node, which is the one and only usage of the EndNode. */
 463                 assert expectedNode.usages().count() == 1;
 464                 assert actualNode.usages().count() == 1;
 465                 verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false);
 466             }
 467 
 468             if (expectedNode instanceof AbstractEndNode) {
 469                 /* Visit the input values of the merge phi functions for this EndNode. */
 470                 verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList);
 471             }
 472         }
 473 
 474         return true;
 475     }
 476 
 477     protected static void verifyPhi(PhiNode expectedPhi, PhiNode actualPhi, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
 478         AbstractMergeNode expectedMergeNode = expectedPhi.merge();
 479         AbstractMergeNode actualMergeNode = actualPhi.merge();
 480         assert actualMergeNode == nodeMapping.get(expectedMergeNode);
 481 
 482         for (EndNode expectedEndNode : expectedMergeNode.ends) {
 483             EndNode actualEndNode = (EndNode) nodeMapping.get(expectedEndNode);
 484             if (actualEndNode != null) {
 485                 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
 486                 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
 487                 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
 488             }
 489         }
 490     }
 491 
 492     protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
 493         AbstractMergeNode expectedMergeNode = expectedEndNode.merge();
 494         AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode);
 495         assert actualMergeNode != null;
 496 
 497         for (PhiNode expectedPhi : expectedMergeNode.phis()) {
 498             PhiNode actualPhi = (PhiNode) nodeMapping.get(expectedPhi);
 499             if (actualPhi != null) {
 500                 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
 501                 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
 502                 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
 503             }
 504         }
 505     }
 506 
 507     private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
 508         Iterator<Node> actualIter = actualNodes.iterator();
 509         for (Node expectedNode : expectedNodes) {
 510             verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode);
 511         }
 512         assert !actualIter.hasNext();
 513     }
 514 
 515     protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
 516         assert expectedNode.getClass() == actualNode.getClass();
 517         if (ignoreEndNode && expectedNode instanceof EndNode) {
 518             return;
 519         }
 520 
 521         Node existing = nodeMapping.get(expectedNode);
 522         if (existing != null) {
 523             assert existing == actualNode;
 524         } else {
 525             pushToWorklist(expectedNode, actualNode, nodeMapping, workList);
 526         }
 527     }
 528 
 529     protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
 530         nodeMapping.set(expectedNode, actualNode);
 531         if (expectedNode instanceof AbstractEndNode) {
 532             /* To ensure phi nodes have been added, we handle everything before block ends. */
 533             workList.addLast(new Pair<>(expectedNode, actualNode));
 534         } else {
 535             workList.addFirst(new Pair<>(expectedNode, actualNode));
 536         }
 537     }
 538 }
 539 
 540 class Pair<F, S> {
 541     public final F first;
 542     public final S second;
 543 
 544     Pair(F first, S second) {
 545         this.first = first;
 546         this.second = second;
 547     }
 548 }