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 java.util.ArrayDeque;
26 import java.util.Deque;
27 import java.util.Iterator;
28 import java.util.Objects;
29
30 import org.graalvm.compiler.core.common.Fields;
31 import org.graalvm.compiler.core.common.util.FrequencyEncoder;
32 import org.graalvm.compiler.core.common.util.TypeConversion;
33 import org.graalvm.compiler.core.common.util.TypeReader;
34 import org.graalvm.compiler.core.common.util.TypeWriter;
35 import org.graalvm.compiler.core.common.util.UnsafeArrayTypeWriter;
36 import org.graalvm.compiler.debug.DebugContext;
37 import org.graalvm.compiler.graph.Edges;
38 import org.graalvm.compiler.graph.Node;
39 import org.graalvm.compiler.graph.NodeClass;
40 import org.graalvm.compiler.graph.NodeList;
41 import org.graalvm.compiler.graph.NodeMap;
42 import org.graalvm.compiler.graph.iterators.NodeIterable;
43 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
44 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
45 import org.graalvm.util.Pair;
46 import org.graalvm.util.UnmodifiableMapCursor;
47
48 import jdk.vm.ci.code.Architecture;
49
50 /**
51 * Encodes a {@link StructuredGraph} to a compact byte[] array. All nodes of the graph and edges
52 * between the nodes are encoded. Primitive data fields of nodes are stored in the byte[] array.
53 * Object data fields of nodes are stored in a separate Object[] array.
54 *
55 * One encoder instance can be used to encode multiple graphs. This requires that {@link #prepare}
56 * is called for all graphs first, followed by one call to {@link #finishPrepare}. Then
57 * {@link #encode} can be called for all graphs. The {@link #getObjects() objects} and
58 * {@link #getNodeClasses() node classes} arrays do not change anymore after preparation.
59 *
60 * Multiple encoded graphs share the Object[] array, and elements of the Object[] array are
61 * de-duplicated using {@link Object#equals Object equality}. This uses the assumption and good
62 * coding practice that data objects are immutable if {@link Object#equals} is implemented.
63 * Unfortunately, this cannot be enforced.
64 *
65 * The Graal {@link NodeClass} does not have a unique id that allows class lookup from an id.
66 * Therefore, the encoded graph contains a {@link NodeClass}[] array for lookup, and type ids are
67 * encoding-local.
68 *
69 * The encoded graph has the following structure: First, all nodes and their edges are serialized.
70 * The start offset of every node is then known. The raw node data is followed by metadata, i.e.,
71 * the maximum fixed node order id and a "table of contents" that lists the start offset for every
72 * node.
73 *
74 * The beginning of this metadata 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 * unsigned[] inputOrderIds
90 * signed[] properties
91 * unsigned[] successorOrderIds
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 int 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 NodeClass<? extends Node> nodeClass = node.getNodeClass();
173 nodeClasses.addObject(nodeClass);
174 objects.addObject(node.getNodeSourcePosition());
175 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
176 if (!nodeClass.getData().getType(i).isPrimitive()) {
177 objects.addObject(nodeClass.getData().get(node, i));
178 }
179 }
180 if (node instanceof Invoke) {
181 objects.addObject(((Invoke) node).getContextType());
182 }
183 }
184 }
185
186 public void finishPrepare() {
187 objectsArray = objects.encodeAll(new Object[objects.getLength()]);
188 nodeClassesArray = nodeClasses.encodeAll(new NodeClass<?>[nodeClasses.getLength()]);
189 }
190
191 public Object[] getObjects() {
192 return objectsArray;
193 }
194
195 public NodeClass<?>[] getNodeClasses() {
196 return nodeClassesArray;
197 }
198
199 /**
200 * Compresses a graph to a byte array. Multiple graphs can be compressed with the same
201 * {@link GraphEncoder}.
202 *
203 * @param graph The graph to encode
204 */
205 public int encode(StructuredGraph graph) {
206 assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()";
207
208 NodeOrder nodeOrder = new NodeOrder(graph);
209 int nodeCount = nodeOrder.nextOrderId;
210 assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID;
211 assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID;
212 assert nodeCount == graph.getNodeCount() + 1;
213
214 long[] nodeStartOffsets = new long[nodeCount];
215 UnmodifiableMapCursor<Node, Integer> cursor = nodeOrder.orderIds.getEntries();
216 while (cursor.advance()) {
217 Node node = cursor.getKey();
218 Integer orderId = cursor.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 writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder);
227 writeProperties(node, nodeClass.getData());
228 writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), 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 /*
280 * Write out the metadata (maximum fixed node order id and the table of contents with the
281 * start offset for all nodes).
282 */
283 int metadataStart = TypeConversion.asS4(writer.getBytesWritten());
284 writer.putUV(nodeOrder.maxFixedNodeOrderId);
285 writer.putUV(nodeCount);
286 for (int i = 0; i < nodeCount; i++) {
287 assert i == NULL_ORDER_ID || i == START_NODE_ORDER_ID || nodeStartOffsets[i] > 0;
288 writer.putUV(metadataStart - nodeStartOffsets[i]);
289 }
290
291 /* Check that the decoding of the encode graph is the same as the input. */
292 assert verifyEncoding(graph, new EncodedGraph(getEncoding(), metadataStart, getObjects(), getNodeClasses(), graph.getAssumptions(), graph.getMethods()),
293 architecture);
294
295 return metadataStart;
296 }
297
298 public byte[] getEncoding() {
299 return writer.toArray(new byte[TypeConversion.asS4(writer.getBytesWritten())]);
300 }
301
302 static class NodeOrder {
303 protected final NodeMap<Integer> orderIds;
304 protected int nextOrderId;
305 protected int maxFixedNodeOrderId;
306
307 NodeOrder(StructuredGraph graph) {
308 this.orderIds = new NodeMap<>(graph);
309 this.nextOrderId = START_NODE_ORDER_ID;
310
311 /* Order the fixed nodes of the graph in reverse postorder. */
312 Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
313 FixedNode current = graph.start();
314 do {
315 add(current);
316 if (current instanceof AbstractBeginNode) {
317 add(((AbstractBeginNode) current).next());
318 }
319
320 if (current instanceof FixedWithNextNode) {
321 current = ((FixedWithNextNode) current).next;
322 } else {
323 if (current instanceof ControlSplitNode) {
324 for (Node successor : current.successors()) {
325 if (successor != null) {
326 nodeQueue.addFirst((AbstractBeginNode) successor);
327 }
328 }
329 } else if (current instanceof EndNode) {
330 AbstractMergeNode merge = ((AbstractEndNode) current).merge();
331 boolean allForwardEndsVisited = true;
332 for (int i = 0; i < merge.forwardEndCount(); i++) {
333 if (orderIds.get(merge.forwardEndAt(i)) == null) {
334 allForwardEndsVisited = false;
335 break;
336 }
337 }
338 if (allForwardEndsVisited) {
339 nodeQueue.add(merge);
340 }
341 }
342 current = nodeQueue.pollFirst();
343 }
344 } while (current != null);
345
346 maxFixedNodeOrderId = nextOrderId - 1;
347 for (Node node : graph.getNodes()) {
348 assert (node instanceof FixedNode) == (orderIds.get(node) != null) : "all fixed nodes must be ordered: " + node;
349 add(node);
350 }
351 }
352
353 private void add(Node node) {
354 if (orderIds.get(node) == null) {
355 orderIds.set(node, nextOrderId);
356 nextOrderId++;
357 }
358 }
359 }
360
361 protected void writeProperties(Node node, Fields fields) {
362 writeObjectId(node.getNodeSourcePosition());
363 for (int idx = 0; idx < fields.getCount(); idx++) {
364 if (fields.getType(idx).isPrimitive()) {
365 long primitive = fields.getRawPrimitive(node, idx);
366 writer.putSV(primitive);
367 } else {
368 Object property = fields.get(node, idx);
369 writeObjectId(property);
370 }
371 }
372 }
373
374 protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) {
375 if (node instanceof PhiNode) {
376 /* Edges are not needed for decoding, so we must not write it. */
377 return;
378 }
379
380 for (int idx = 0; idx < edges.getDirectCount(); idx++) {
381 if (GraphDecoder.skipDirectEdge(node, edges, idx)) {
382 /* Edge is not needed for decoding, so we must not write it. */
383 continue;
384 }
385 Node edge = Edges.getNode(node, edges.getOffsets(), idx);
386 writeOrderId(edge, nodeOrder);
387 }
388
389 if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs) {
390 /* The ends of merge nodes are decoded manually when the ends are processed. */
391 } else {
392 for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) {
393 NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx);
394 if (edgeList == null) {
395 writer.putSV(-1);
396 } else {
397 writer.putSV(edgeList.size());
398 for (Node edge : edgeList) {
399 writeOrderId(edge, nodeOrder);
400 }
401 }
402 }
403 }
404
405 }
406
407 protected void writeOrderId(Node node, NodeOrder nodeOrder) {
408 writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node));
409 }
410
411 protected void writeObjectId(Object object) {
412 writer.putUV(objects.getIndex(object));
413 }
414
415 /**
416 * Verification code that checks that the decoding of an encode graph is the same as the
417 * original graph.
418 */
419 @SuppressWarnings("try")
420 public static boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph, Architecture architecture) {
421 DebugContext debug = originalGraph.getDebug();
422 StructuredGraph decodedGraph = new StructuredGraph.Builder(originalGraph.getOptions(), debug, AllowAssumptions.YES).method(originalGraph.method()).build();
423 GraphDecoder decoder = new GraphDecoder(architecture, decodedGraph);
424 decoder.decode(encodedGraph);
425
426 decodedGraph.verify();
427 try {
428 GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph);
429 } catch (Throwable ex) {
430 originalGraph.getDebug();
431 try (DebugContext.Scope scope = debug.scope("GraphEncoder")) {
432 debug.dump(DebugContext.VERBOSE_LEVEL, originalGraph, "Original Graph");
433 debug.dump(DebugContext.VERBOSE_LEVEL, decodedGraph, "Decoded Graph");
434 }
435 throw ex;
436 }
437 return true;
438 }
439 }
440
441 class GraphComparison {
442 public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) {
443 NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph);
444 Deque<Pair<Node, Node>> workList = new ArrayDeque<>();
445
446 pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList);
447 while (!workList.isEmpty()) {
448 Pair<Node, Node> pair = workList.removeFirst();
449 Node expectedNode = pair.getLeft();
450 Node actualNode = pair.getRight();
451 assert expectedNode.getClass() == actualNode.getClass();
452
453 NodeClass<?> nodeClass = expectedNode.getNodeClass();
454 assert nodeClass == actualNode.getNodeClass();
455
456 if (expectedNode instanceof MergeNode) {
457 /* The order of the ends can be different, so ignore them. */
458 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true);
459 } else if (expectedNode instanceof PhiNode) {
460 verifyPhi((PhiNode) expectedNode, (PhiNode) actualNode, nodeMapping, workList);
461 } else {
462 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false);
463 }
464 verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false);
465
466 if (expectedNode instanceof LoopEndNode) {
467 LoopEndNode actualLoopEnd = (LoopEndNode) actualNode;
468 assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex();
469 } else {
470 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
471 Object expectedProperty = nodeClass.getData().get(expectedNode, i);
472 Object actualProperty = nodeClass.getData().get(actualNode, i);
473 assert Objects.equals(expectedProperty, actualProperty);
474 }
475 }
476
477 if (expectedNode instanceof EndNode) {
478 /* Visit the merge node, which is the one and only usage of the EndNode. */
479 assert expectedNode.usages().count() == 1;
480 assert actualNode.usages().count() == 1;
481 verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false);
482 }
483
484 if (expectedNode instanceof AbstractEndNode) {
485 /* Visit the input values of the merge phi functions for this EndNode. */
486 verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList);
487 }
488 }
489
490 return true;
491 }
492
493 protected static void verifyPhi(PhiNode expectedPhi, PhiNode actualPhi, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
494 AbstractMergeNode expectedMergeNode = expectedPhi.merge();
495 AbstractMergeNode actualMergeNode = actualPhi.merge();
496 assert actualMergeNode == nodeMapping.get(expectedMergeNode);
497
498 for (EndNode expectedEndNode : expectedMergeNode.ends) {
499 EndNode actualEndNode = (EndNode) nodeMapping.get(expectedEndNode);
500 if (actualEndNode != null) {
501 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
502 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
503 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
504 }
505 }
506 }
507
508 protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
509 AbstractMergeNode expectedMergeNode = expectedEndNode.merge();
510 AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode);
511 assert actualMergeNode != null;
512
513 for (PhiNode expectedPhi : expectedMergeNode.phis()) {
514 PhiNode actualPhi = (PhiNode) nodeMapping.get(expectedPhi);
515 if (actualPhi != null) {
516 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
517 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
518 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
519 }
520 }
521 }
522
523 private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
524 Iterator<Node> actualIter = actualNodes.iterator();
525 for (Node expectedNode : expectedNodes) {
526 verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode);
527 }
528 assert !actualIter.hasNext();
529 }
530
531 protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
532 assert expectedNode.getClass() == actualNode.getClass();
533 if (ignoreEndNode && expectedNode instanceof EndNode) {
534 return;
535 }
536
537 Node existing = nodeMapping.get(expectedNode);
538 if (existing != null) {
539 assert existing == actualNode;
540 } else {
541 pushToWorklist(expectedNode, actualNode, nodeMapping, workList);
542 }
543 }
544
545 protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
546 nodeMapping.set(expectedNode, actualNode);
547 if (expectedNode instanceof AbstractEndNode) {
548 /* To ensure phi nodes have been added, we handle everything before block ends. */
549 workList.addLast(Pair.create(expectedNode, actualNode));
550 } else {
551 workList.addFirst(Pair.create(expectedNode, actualNode));
552 }
553 }
554 }