1 /*
2 * Copyright (c) 2015, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.nodes;
26
27 import java.util.ArrayDeque;
28 import java.util.Deque;
29 import java.util.Iterator;
30 import java.util.Objects;
31
32 import jdk.internal.vm.compiler.collections.Pair;
33 import jdk.internal.vm.compiler.collections.UnmodifiableMapCursor;
34 import org.graalvm.compiler.core.common.Fields;
35 import org.graalvm.compiler.core.common.util.FrequencyEncoder;
36 import org.graalvm.compiler.core.common.util.TypeConversion;
37 import org.graalvm.compiler.core.common.util.TypeReader;
38 import org.graalvm.compiler.core.common.util.TypeWriter;
39 import org.graalvm.compiler.core.common.util.UnsafeArrayTypeWriter;
40 import org.graalvm.compiler.debug.DebugContext;
41 import org.graalvm.compiler.graph.Edges;
42 import org.graalvm.compiler.graph.Node;
43 import org.graalvm.compiler.graph.NodeClass;
44 import org.graalvm.compiler.graph.NodeList;
45 import org.graalvm.compiler.graph.NodeMap;
46 import org.graalvm.compiler.graph.iterators.NodeIterable;
47 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
48 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
49
50 import jdk.vm.ci.code.Architecture;
51
52 /**
53 * Encodes a {@link StructuredGraph} to a compact byte[] array. All nodes of the graph and edges
54 * between the nodes are encoded. Primitive data fields of nodes are stored in the byte[] array.
55 * Object data fields of nodes are stored in a separate Object[] array.
56 *
57 * One encoder instance can be used to encode multiple graphs. This requires that {@link #prepare}
58 * is called for all graphs first, followed by one call to {@link #finishPrepare}. Then
59 * {@link #encode} can be called for all graphs. The {@link #getObjects() objects} and
60 * {@link #getNodeClasses() node classes} arrays do not change anymore after preparation.
61 *
62 * Multiple encoded graphs share the Object[] array, and elements of the Object[] array are
63 * de-duplicated using {@link Object#equals Object equality}. This uses the assumption and good
64 * coding practice that data objects are immutable if {@link Object#equals} is implemented.
65 * Unfortunately, this cannot be enforced.
66 *
67 * The Graal {@link NodeClass} does not have a unique id that allows class lookup from an id.
68 * Therefore, the encoded graph contains a {@link NodeClass}[] array for lookup, and type ids are
69 * encoding-local.
70 *
71 * The encoded graph has the following structure: First, all nodes and their edges are serialized.
72 * The start offset of every node is then known. The raw node data is followed by metadata, i.e.,
73 * the maximum fixed node order id and a "table of contents" that lists the start offset for every
74 * node.
75 *
76 * The beginning of this metadata is the return value of {@link #encode} and stored in
77 * {@link EncodedGraph#getStartOffset()}. The order of nodes in the table of contents is the
78 * {@link NodeOrder#orderIds orderId} of a node. Note that the orderId is not the regular node id
79 * that every Graal graph node gets assigned. The orderId is computed and used just for encoding and
80 * decoding. The orderId of fixed nodes is assigned in reverse postorder. The decoder processes
81 * nodes using that order, which ensures that all predecessors of a node (including all
82 * {@link EndNode predecessors} of a {@link AbstractBeginNode block}) are decoded before the node.
83 * The order id of floating node does not matter during decoding, so floating nodes get order ids
84 * after all fixed nodes. The order id is used to encode edges between nodes
85 *
86 * Structure of an encoded node:
87 *
88 * <pre>
89 * struct Node {
90 * unsigned typeId
91 * unsigned[] inputOrderIds
92 * signed[] properties
93 * unsigned[] successorOrderIds
94 * }
95 * </pre>
96 *
97 * All numbers (unsigned and signed) are stored using a variable-length encoding as defined in
98 * {@link TypeReader} and {@link TypeWriter}. Especially orderIds are small, so the variable-length
99 * encoding is important to keep the encoding compact.
100 *
101 * The properties, successors, and inputs are written in the order as defined in
102 * {@link NodeClass#getData}, {@link NodeClass#getSuccessorEdges()}, and
103 * {@link NodeClass#getInputEdges()}. For variable-length successors and input lists, first the
104 * length is written and then the orderIds. There is a distinction between null lists (encoded as
105 * length -1) and empty lists (encoded as length 0). No reverse edges are written (predecessors,
106 * usages) since that information can be easily restored during decoding.
107 *
108 * Some nodes have additional information written after the properties, successors, and inputs:
109 * <li><item>{@link AbstractEndNode}: the orderId of the merge node and then all {@link PhiNode phi
110 * mappings} from this end to the merge node are written. <item>{@link LoopExitNode}: the orderId of
111 * all {@link ProxyNode proxy nodes} of the loop exit is written.</li>
112 */
113 public class GraphEncoder {
114
115 /** The orderId that always represents {@code null}. */
116 public static final int NULL_ORDER_ID = 0;
117 /** The orderId of the {@link StructuredGraph#start() start node} of the encoded graph. */
118 public static final int START_NODE_ORDER_ID = 1;
119 /**
120 * The orderId of the first actual node after the {@link StructuredGraph#start() start node}.
121 */
122 public static final int FIRST_NODE_ORDER_ID = 2;
123
124 /**
125 * The known offset between the orderId of a {@link AbstractBeginNode} and its
126 * {@link AbstractBeginNode#next() successor}.
127 */
128 protected static final int BEGIN_NEXT_ORDER_ID_OFFSET = 1;
129
130 protected final Architecture architecture;
131
132 /**
133 * Collects all non-primitive data referenced from nodes. The encoding uses an index into an
134 * array for decoding. Because of the variable-length encoding, it is beneficial that frequently
135 * used objects have the small indices.
136 */
137 protected final FrequencyEncoder<Object> objects;
138 /**
139 * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass}
140 * currently does not have a unique id.
141 */
142 protected final FrequencyEncoder<NodeClass<?>> nodeClasses;
143 /** The writer for the encoded graphs. */
144 protected final UnsafeArrayTypeWriter writer;
145
146 /** The last snapshot of {@link #objects} that was retrieved. */
147 protected Object[] objectsArray;
148 /** The last snapshot of {@link #nodeClasses} that was retrieved. */
149 protected NodeClass<?>[] nodeClassesArray;
150
151 /**
152 * Utility method that does everything necessary to encode a single graph.
153 */
154 public static EncodedGraph encodeSingleGraph(StructuredGraph graph, Architecture architecture) {
155 GraphEncoder encoder = new GraphEncoder(architecture);
156 encoder.prepare(graph);
157 encoder.finishPrepare();
158 int startOffset = encoder.encode(graph);
159 return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph);
160 }
161
162 public GraphEncoder(Architecture architecture) {
163 this.architecture = architecture;
164 objects = FrequencyEncoder.createEqualityEncoder();
165 nodeClasses = FrequencyEncoder.createIdentityEncoder();
166 writer = UnsafeArrayTypeWriter.create(architecture.supportsUnalignedMemoryAccess());
167 }
168
169 /**
170 * Must be invoked before {@link #finishPrepare()} and {@link #encode}.
171 */
172 public void prepare(StructuredGraph graph) {
173 for (Node node : graph.getNodes()) {
174 NodeClass<? extends Node> nodeClass = node.getNodeClass();
175 nodeClasses.addObject(nodeClass);
176 objects.addObject(node.getNodeSourcePosition());
177 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
178 if (!nodeClass.getData().getType(i).isPrimitive()) {
179 objects.addObject(nodeClass.getData().get(node, i));
180 }
181 }
182 if (node instanceof Invoke) {
183 objects.addObject(((Invoke) node).getContextType());
184 }
185 }
186 }
187
188 public void finishPrepare() {
189 objectsArray = objects.encodeAll(new Object[objects.getLength()]);
190 nodeClassesArray = nodeClasses.encodeAll(new NodeClass<?>[nodeClasses.getLength()]);
191 }
192
193 public Object[] getObjects() {
194 return objectsArray;
195 }
196
197 public NodeClass<?>[] getNodeClasses() {
198 return nodeClassesArray;
199 }
200
201 /**
202 * Compresses a graph to a byte array. Multiple graphs can be compressed with the same
203 * {@link GraphEncoder}.
204 *
205 * @param graph The graph to encode
206 */
207 public int encode(StructuredGraph graph) {
208 assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()";
209
210 NodeOrder nodeOrder = new NodeOrder(graph);
211 int nodeCount = nodeOrder.nextOrderId;
212 assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID;
213 assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID;
214
215 long[] nodeStartOffsets = new long[nodeCount];
216 UnmodifiableMapCursor<Node, Integer> cursor = nodeOrder.orderIds.getEntries();
217 while (cursor.advance()) {
218 Node node = cursor.getKey();
219 Integer orderId = cursor.getValue();
220
221 assert !(node instanceof AbstractBeginNode) || nodeOrder.orderIds.get(((AbstractBeginNode) node).next()) == orderId + BEGIN_NEXT_ORDER_ID_OFFSET;
222 assert nodeStartOffsets[orderId] == 0;
223 nodeStartOffsets[orderId] = writer.getBytesWritten();
224
225 /* Write out the type, properties, and edges. */
226 NodeClass<?> nodeClass = node.getNodeClass();
227 writer.putUV(nodeClasses.getIndex(nodeClass));
228 writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder);
229 writeProperties(node, nodeClass.getData());
230 writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), nodeOrder);
231
232 /* Special handling for some nodes that require additional information for decoding. */
233 if (node instanceof AbstractEndNode) {
234 AbstractEndNode end = (AbstractEndNode) node;
235 AbstractMergeNode merge = end.merge();
236 /*
237 * Write the orderId of the merge. The merge is not a successor in the Graal graph
238 * (only the merge has an input edge to the EndNode).
239 */
240 writeOrderId(merge, nodeOrder);
241
242 /*
243 * Write all phi mappings (the oderId of the phi input for this EndNode, and the
244 * orderId of the phi node.
245 */
246 writer.putUV(merge.phis().count());
247 for (PhiNode phi : merge.phis()) {
248 writeOrderId(phi.valueAt(end), nodeOrder);
249 writeOrderId(phi, nodeOrder);
250 }
251
252 } else if (node instanceof LoopExitNode) {
253 LoopExitNode exit = (LoopExitNode) node;
254 writeOrderId(exit.stateAfter(), nodeOrder);
255 /* Write all proxy nodes of the LoopExitNode. */
256 writer.putUV(exit.proxies().count());
257 for (ProxyNode proxy : exit.proxies()) {
258 writeOrderId(proxy, nodeOrder);
259 }
260
261 } else if (node instanceof Invoke) {
262 Invoke invoke = (Invoke) node;
263 assert invoke.stateDuring() == null : "stateDuring is not used in high-level graphs";
264
265 writeObjectId(invoke.getContextType());
266 writeOrderId(invoke.callTarget(), nodeOrder);
267 writeOrderId(invoke.stateAfter(), nodeOrder);
268 writeOrderId(invoke.next(), nodeOrder);
269 if (invoke instanceof InvokeWithExceptionNode) {
270 InvokeWithExceptionNode invokeWithExcpetion = (InvokeWithExceptionNode) invoke;
271 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExcpetion.exceptionEdge();
272
273 writeOrderId(invokeWithExcpetion.next().next(), nodeOrder);
274 writeOrderId(invokeWithExcpetion.exceptionEdge(), nodeOrder);
275 writeOrderId(exceptionEdge.stateAfter(), nodeOrder);
276 writeOrderId(exceptionEdge.next(), nodeOrder);
277 }
278 }
279 }
280
281 /*
282 * Write out the metadata (maximum fixed node order id and the table of contents with the
283 * start offset for all nodes).
284 */
285 int metadataStart = TypeConversion.asS4(writer.getBytesWritten());
286 writer.putUV(nodeOrder.maxFixedNodeOrderId);
287 writer.putUV(nodeCount);
288 for (int i = 0; i < nodeCount; i++) {
289 writer.putUV(metadataStart - nodeStartOffsets[i]);
290 }
291
292 /* Check that the decoding of the encode graph is the same as the input. */
293 assert verifyEncoding(graph, new EncodedGraph(getEncoding(), metadataStart, getObjects(), getNodeClasses(), graph), 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
348 /*
349 * Emit all parameters consecutively at a known location (after all fixed nodes). This
350 * allows substituting parameters when inlining during decoding by pre-initializing the
351 * decoded node list.
352 *
353 * Note that not all parameters must be present (unused parameters are deleted after
354 * parsing). This leads to holes in the orderId, i.e., unused orderIds.
355 */
356 int parameterCount = graph.method().getSignature().getParameterCount(!graph.method().isStatic());
357 for (ParameterNode node : graph.getNodes(ParameterNode.TYPE)) {
358 assert orderIds.get(node) == null : "Parameter node must not be ordered yet";
359 assert node.index() < parameterCount : "Parameter index out of range";
360 orderIds.set(node, nextOrderId + node.index());
361 }
362 nextOrderId += parameterCount;
363
364 for (Node node : graph.getNodes()) {
365 assert (node instanceof FixedNode || node instanceof ParameterNode) == (orderIds.get(node) != null) : "all fixed nodes and ParameterNodes must be ordered: " + node;
366 add(node);
367 }
368 }
369
370 private void add(Node node) {
371 if (orderIds.get(node) == null) {
372 orderIds.set(node, nextOrderId);
373 nextOrderId++;
374 }
375 }
376 }
377
378 protected void writeProperties(Node node, Fields fields) {
379 writeObjectId(node.getNodeSourcePosition());
380 for (int idx = 0; idx < fields.getCount(); idx++) {
381 if (fields.getType(idx).isPrimitive()) {
382 long primitive = fields.getRawPrimitive(node, idx);
383 writer.putSV(primitive);
384 } else {
385 Object property = fields.get(node, idx);
386 writeObjectId(property);
387 }
388 }
389 }
390
391 protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) {
392 if (node instanceof PhiNode) {
393 /* Edges are not needed for decoding, so we must not write it. */
394 return;
395 }
396
397 for (int idx = 0; idx < edges.getDirectCount(); idx++) {
398 if (GraphDecoder.skipDirectEdge(node, edges, idx)) {
399 /* Edge is not needed for decoding, so we must not write it. */
400 continue;
401 }
402 Node edge = Edges.getNode(node, edges.getOffsets(), idx);
403 writeOrderId(edge, nodeOrder);
404 }
405
406 if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs) {
407 /* The ends of merge nodes are decoded manually when the ends are processed. */
408 } else {
409 for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) {
410 NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx);
411 if (edgeList == null) {
412 writer.putSV(-1);
413 } else {
414 writer.putSV(edgeList.size());
415 for (Node edge : edgeList) {
416 writeOrderId(edge, nodeOrder);
417 }
418 }
419 }
420 }
421
422 }
423
424 protected void writeOrderId(Node node, NodeOrder nodeOrder) {
425 writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node));
426 }
427
428 protected void writeObjectId(Object object) {
429 writer.putUV(objects.getIndex(object));
430 }
431
432 /**
433 * Verification code that checks that the decoding of an encode graph is the same as the
434 * original graph.
435 */
436 @SuppressWarnings("try")
437 public static boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph, Architecture architecture) {
438 DebugContext debug = originalGraph.getDebug();
439 // @formatter:off
440 StructuredGraph decodedGraph = new StructuredGraph.Builder(originalGraph.getOptions(), debug, AllowAssumptions.YES).
441 method(originalGraph.method()).
442 setIsSubstitution(originalGraph.isSubstitution()).
443 trackNodeSourcePosition(originalGraph.trackNodeSourcePosition()).
444 build();
445 // @formatter:off
446 GraphDecoder decoder = new GraphDecoder(architecture, decodedGraph);
447 decoder.decode(encodedGraph);
448
449 decodedGraph.verify();
450 try {
451 GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph);
452 } catch (Throwable ex) {
453 originalGraph.getDebug();
454 try (DebugContext.Scope scope = debug.scope("GraphEncoder")) {
455 debug.dump(DebugContext.VERBOSE_LEVEL, originalGraph, "Original Graph");
456 debug.dump(DebugContext.VERBOSE_LEVEL, decodedGraph, "Decoded Graph");
457 }
458 throw ex;
459 }
460 return true;
461 }
462 }
463
464 class GraphComparison {
465 public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) {
466 NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph);
467 Deque<Pair<Node, Node>> workList = new ArrayDeque<>();
468
469 pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList);
470 while (!workList.isEmpty()) {
471 Pair<Node, Node> pair = workList.removeFirst();
472 Node expectedNode = pair.getLeft();
473 Node actualNode = pair.getRight();
474 assert expectedNode.getClass() == actualNode.getClass();
475
476 NodeClass<?> nodeClass = expectedNode.getNodeClass();
477 assert nodeClass == actualNode.getNodeClass();
478
479 if (expectedNode instanceof MergeNode) {
480 /* The order of the ends can be different, so ignore them. */
481 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true);
482 } else if (expectedNode instanceof PhiNode) {
483 verifyPhi((PhiNode) expectedNode, (PhiNode) actualNode, nodeMapping, workList);
484 } else {
485 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false);
486 }
487 verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false);
488
489 if (expectedNode instanceof LoopEndNode) {
490 LoopEndNode actualLoopEnd = (LoopEndNode) actualNode;
491 assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex();
492 } else {
493 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
494 Object expectedProperty = nodeClass.getData().get(expectedNode, i);
495 Object actualProperty = nodeClass.getData().get(actualNode, i);
496 assert Objects.equals(expectedProperty, actualProperty);
497 }
498 }
499
500 if (expectedNode instanceof EndNode) {
501 /* Visit the merge node, which is the one and only usage of the EndNode. */
502 assert expectedNode.usages().count() == 1;
503 assert actualNode.usages().count() == 1;
504 verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false);
505 }
506
507 if (expectedNode instanceof AbstractEndNode) {
508 /* Visit the input values of the merge phi functions for this EndNode. */
509 verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList);
510 }
511 }
512
513 return true;
514 }
515
516 protected static void verifyPhi(PhiNode expectedPhi, PhiNode actualPhi, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
517 AbstractMergeNode expectedMergeNode = expectedPhi.merge();
518 AbstractMergeNode actualMergeNode = actualPhi.merge();
519 assert actualMergeNode == nodeMapping.get(expectedMergeNode);
520
521 for (EndNode expectedEndNode : expectedMergeNode.ends) {
522 EndNode actualEndNode = (EndNode) nodeMapping.get(expectedEndNode);
523 if (actualEndNode != null) {
524 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
525 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
526 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
527 }
528 }
529 }
530
531 protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
532 AbstractMergeNode expectedMergeNode = expectedEndNode.merge();
533 AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode);
534 assert actualMergeNode != null;
535
536 for (PhiNode expectedPhi : expectedMergeNode.phis()) {
537 PhiNode actualPhi = (PhiNode) nodeMapping.get(expectedPhi);
538 if (actualPhi != null) {
539 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
540 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
541 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
542 }
543 }
544 }
545
546 private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
547 Iterator<Node> actualIter = actualNodes.iterator();
548 for (Node expectedNode : expectedNodes) {
549 verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode);
550 }
551 assert !actualIter.hasNext();
552 }
553
554 protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
555 assert expectedNode.getClass() == actualNode.getClass();
556 if (ignoreEndNode && expectedNode instanceof EndNode) {
557 return;
558 }
559
560 Node existing = nodeMapping.get(expectedNode);
561 if (existing != null) {
562 assert existing == actualNode;
563 } else {
564 pushToWorklist(expectedNode, actualNode, nodeMapping, workList);
565 }
566 }
567
568 protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
569 nodeMapping.set(expectedNode, actualNode);
570 if (expectedNode instanceof AbstractEndNode) {
571 /* To ensure phi nodes have been added, we handle everything before block ends. */
572 workList.addLast(Pair.create(expectedNode, actualNode));
573 } else {
574 workList.addFirst(Pair.create(expectedNode, actualNode));
575 }
576 }
577 }