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 /**
116 * The orderId that always represents {@code null}.
117 */
118 public static final int NULL_ORDER_ID = 0;
119 /**
120 * The orderId of the {@link StructuredGraph#start() start node} of the encoded graph.
121 */
122 public static final int START_NODE_ORDER_ID = 1;
123 /**
124 * The orderId of the first actual node after the {@link StructuredGraph#start() start node}.
125 */
126 public static final int FIRST_NODE_ORDER_ID = 2;
127
128 /**
129 * The known offset between the orderId of a {@link AbstractBeginNode} and its
130 * {@link AbstractBeginNode#next() successor}.
131 */
132 protected static final int BEGIN_NEXT_ORDER_ID_OFFSET = 1;
133
134 protected final Architecture architecture;
135
136 /**
137 * Collects all non-primitive data referenced from nodes. The encoding uses an index into an
138 * array for decoding. Because of the variable-length encoding, it is beneficial that frequently
139 * used objects have the small indices.
140 */
141 protected final FrequencyEncoder<Object> objects;
142 /**
143 * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass}
144 * currently does not have a unique id.
145 */
146 protected final FrequencyEncoder<NodeClass<?>> nodeClasses;
147 /** The writer for the encoded graphs. */
148 protected final UnsafeArrayTypeWriter writer;
149
150 /** The last snapshot of {@link #objects} that was retrieved. */
151 protected Object[] objectsArray;
152 /** The last snapshot of {@link #nodeClasses} that was retrieved. */
153 protected NodeClass<?>[] nodeClassesArray;
154
155 protected DebugContext debug;
156
157 /**
158 * Utility method that does everything necessary to encode a single graph.
159 */
160 public static EncodedGraph encodeSingleGraph(StructuredGraph graph, Architecture architecture) {
161 GraphEncoder encoder = new GraphEncoder(architecture);
162 encoder.prepare(graph);
163 encoder.finishPrepare();
164 int startOffset = encoder.encode(graph);
165 return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph);
166 }
167
168 public GraphEncoder(Architecture architecture) {
169 this(architecture, null);
170 }
171
172 public GraphEncoder(Architecture architecture, DebugContext debug) {
173 this.architecture = architecture;
174 this.debug = debug;
175 objects = FrequencyEncoder.createEqualityEncoder();
176 nodeClasses = FrequencyEncoder.createIdentityEncoder();
177 writer = UnsafeArrayTypeWriter.create(architecture.supportsUnalignedMemoryAccess());
178 }
179
180 /**
181 * Must be invoked before {@link #finishPrepare()} and {@link #encode}.
182 */
183 public void prepare(StructuredGraph graph) {
184 objects.addObject(graph.getGuardsStage());
185 for (Node node : graph.getNodes()) {
186 NodeClass<? extends Node> nodeClass = node.getNodeClass();
187 nodeClasses.addObject(nodeClass);
188 objects.addObject(node.getNodeSourcePosition());
189 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
190 if (!nodeClass.getData().getType(i).isPrimitive()) {
191 objects.addObject(nodeClass.getData().get(node, i));
192 }
193 }
194 if (node instanceof Invoke) {
195 objects.addObject(((Invoke) node).getContextType());
196 }
197 }
198 }
199
200 public void finishPrepare() {
201 objectsArray = objects.encodeAll(new Object[objects.getLength()]);
202 nodeClassesArray = nodeClasses.encodeAll(new NodeClass<?>[nodeClasses.getLength()]);
203 }
204
205 public Object[] getObjects() {
206 return objectsArray;
207 }
208
209 public NodeClass<?>[] getNodeClasses() {
210 return nodeClassesArray;
211 }
212
213 /**
214 * Compresses a graph to a byte array. Multiple graphs can be compressed with the same
215 * {@link GraphEncoder}.
216 *
217 * @param graph The graph to encode
218 */
219 public int encode(StructuredGraph graph) {
220 assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()";
221
222 NodeOrder nodeOrder = new NodeOrder(graph);
223 int nodeCount = nodeOrder.nextOrderId;
224 assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID;
225 assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID;
226
227 long[] nodeStartOffsets = new long[nodeCount];
228 UnmodifiableMapCursor<Node, Integer> cursor = nodeOrder.orderIds.getEntries();
229 while (cursor.advance()) {
230 Node node = cursor.getKey();
231 Integer orderId = cursor.getValue();
232
233 assert !(node instanceof AbstractBeginNode) || nodeOrder.orderIds.get(((AbstractBeginNode) node).next()) == orderId + BEGIN_NEXT_ORDER_ID_OFFSET;
234 assert nodeStartOffsets[orderId] == 0;
235 nodeStartOffsets[orderId] = writer.getBytesWritten();
236
237 /* Write out the type, properties, and edges. */
238 NodeClass<?> nodeClass = node.getNodeClass();
239 writer.putUV(nodeClasses.getIndex(nodeClass));
240 writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder);
241 writeProperties(node, nodeClass.getData());
242 writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), nodeOrder);
243
244 /* Special handling for some nodes that require additional information for decoding. */
245 if (node instanceof AbstractEndNode) {
246 AbstractEndNode end = (AbstractEndNode) node;
247 AbstractMergeNode merge = end.merge();
248 /*
249 * Write the orderId of the merge. The merge is not a successor in the Graal graph
250 * (only the merge has an input edge to the EndNode).
251 */
252 writeOrderId(merge, nodeOrder);
253
254 /*
255 * Write all phi mappings (the oderId of the phi input for this EndNode, and the
256 * orderId of the phi node.
257 */
258 writer.putUV(merge.phis().count());
259 for (PhiNode phi : merge.phis()) {
260 writeOrderId(phi.valueAt(end), nodeOrder);
261 writeOrderId(phi, nodeOrder);
262 }
263
264 } else if (node instanceof LoopExitNode) {
265 LoopExitNode exit = (LoopExitNode) node;
266 writeOrderId(exit.stateAfter(), nodeOrder);
267 /* Write all proxy nodes of the LoopExitNode. */
268 writer.putUV(exit.proxies().count());
269 for (ProxyNode proxy : exit.proxies()) {
270 writeOrderId(proxy, nodeOrder);
271 }
272
273 } else if (node instanceof Invoke) {
274 Invoke invoke = (Invoke) node;
275 assert invoke.stateDuring() == null : "stateDuring is not used in high-level graphs";
276
277 writeObjectId(invoke.getContextType());
278 writeOrderId(invoke.callTarget(), nodeOrder);
279 writeOrderId(invoke.stateAfter(), nodeOrder);
280 writeOrderId(invoke.next(), nodeOrder);
281 if (invoke instanceof InvokeWithExceptionNode) {
282 InvokeWithExceptionNode invokeWithExcpetion = (InvokeWithExceptionNode) invoke;
283 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExcpetion.exceptionEdge();
284
285 writeOrderId(invokeWithExcpetion.next().next(), nodeOrder);
286 writeOrderId(invokeWithExcpetion.exceptionEdge(), nodeOrder);
287 writeOrderId(exceptionEdge.stateAfter(), nodeOrder);
288 writeOrderId(exceptionEdge.next(), nodeOrder);
289 }
290 }
291 }
292
293 /*
294 * Write out the metadata (maximum fixed node order id and the table of contents with the
295 * start offset for all nodes).
296 */
297 int metadataStart = TypeConversion.asS4(writer.getBytesWritten());
298 writer.putUV(nodeOrder.maxFixedNodeOrderId);
299 writer.putUV(nodeCount);
300 for (int i = 0; i < nodeCount; i++) {
301 writer.putUV(metadataStart - nodeStartOffsets[i]);
302 }
303 writeObjectId(graph.getGuardsStage());
304
305 /* Check that the decoding of the encode graph is the same as the input. */
306 assert verifyEncoding(graph, new EncodedGraph(getEncoding(), metadataStart, getObjects(), getNodeClasses(), graph));
307
308 return metadataStart;
309 }
310
311 public byte[] getEncoding() {
312 return writer.toArray(new byte[TypeConversion.asS4(writer.getBytesWritten())]);
313 }
314
315 static class NodeOrder {
316 protected final NodeMap<Integer> orderIds;
317 protected int nextOrderId;
318 protected int maxFixedNodeOrderId;
319
320 NodeOrder(StructuredGraph graph) {
321 this.orderIds = new NodeMap<>(graph);
322 this.nextOrderId = START_NODE_ORDER_ID;
323
324 /* Order the fixed nodes of the graph in reverse postorder. */
325 Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
326 FixedNode current = graph.start();
327 do {
328 add(current);
329 if (current instanceof AbstractBeginNode) {
330 add(((AbstractBeginNode) current).next());
331 }
332
333 if (current instanceof FixedWithNextNode) {
334 current = ((FixedWithNextNode) current).next;
335 } else {
336 if (current instanceof ControlSplitNode) {
337 for (Node successor : current.successors()) {
338 if (successor != null) {
339 nodeQueue.addFirst((AbstractBeginNode) successor);
340 }
341 }
342 } else if (current instanceof EndNode) {
343 AbstractMergeNode merge = ((AbstractEndNode) current).merge();
344 boolean allForwardEndsVisited = true;
345 for (int i = 0; i < merge.forwardEndCount(); i++) {
346 if (orderIds.get(merge.forwardEndAt(i)) == null) {
347 allForwardEndsVisited = false;
348 break;
349 }
350 }
351 if (allForwardEndsVisited) {
352 nodeQueue.add(merge);
353 }
354 }
355 current = nodeQueue.pollFirst();
356 }
357 } while (current != null);
358
359 maxFixedNodeOrderId = nextOrderId - 1;
360
361 /*
362 * Emit all parameters consecutively at a known location (after all fixed nodes). This
363 * allows substituting parameters when inlining during decoding by pre-initializing the
364 * decoded node list.
365 *
366 * Note that not all parameters must be present (unused parameters are deleted after
367 * parsing). This leads to holes in the orderId, i.e., unused orderIds.
368 */
369 int parameterCount = graph.method().getSignature().getParameterCount(!graph.method().isStatic());
370 for (ParameterNode node : graph.getNodes(ParameterNode.TYPE)) {
371 assert orderIds.get(node) == null : "Parameter node must not be ordered yet";
372 assert node.index() < parameterCount : "Parameter index out of range";
373 orderIds.set(node, nextOrderId + node.index());
374 }
375 nextOrderId += parameterCount;
376
377 for (Node node : graph.getNodes()) {
378 assert (node instanceof FixedNode || node instanceof ParameterNode) == (orderIds.get(node) != null) : "all fixed nodes and ParameterNodes must be ordered: " + node;
379 add(node);
380 }
381 }
382
383 private void add(Node node) {
384 if (orderIds.get(node) == null) {
385 orderIds.set(node, nextOrderId);
386 nextOrderId++;
387 }
388 }
389 }
390
391 protected void writeProperties(Node node, Fields fields) {
392 writeObjectId(node.getNodeSourcePosition());
393 for (int idx = 0; idx < fields.getCount(); idx++) {
394 if (fields.getType(idx).isPrimitive()) {
395 long primitive = fields.getRawPrimitive(node, idx);
396 writer.putSV(primitive);
397 } else {
398 Object property = fields.get(node, idx);
399 writeObjectId(property);
400 }
401 }
402 }
403
404 protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) {
405 if (node instanceof PhiNode) {
406 /* Edges are not needed for decoding, so we must not write it. */
407 return;
408 }
409
410 for (int idx = 0; idx < edges.getDirectCount(); idx++) {
411 if (GraphDecoder.skipDirectEdge(node, edges, idx)) {
412 /* Edge is not needed for decoding, so we must not write it. */
413 continue;
414 }
415 Node edge = Edges.getNode(node, edges.getOffsets(), idx);
416 writeOrderId(edge, nodeOrder);
417 }
418
419 if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs) {
420 /* The ends of merge nodes are decoded manually when the ends are processed. */
421 } else {
422 for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) {
423 NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx);
424 if (edgeList == null) {
425 writer.putSV(-1);
426 } else {
427 writer.putSV(edgeList.size());
428 for (Node edge : edgeList) {
429 writeOrderId(edge, nodeOrder);
430 }
431 }
432 }
433 }
434
435 }
436
437 protected void writeOrderId(Node node, NodeOrder nodeOrder) {
438 writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node));
439 }
440
441 protected void writeObjectId(Object object) {
442 writer.putUV(objects.getIndex(object));
443 }
444
445 /**
446 * Verification code that checks that the decoding of an encode graph is the same as the
447 * original graph.
448 */
449 @SuppressWarnings("try")
450 public boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph) {
451 DebugContext debugContext = debug != null ? debug : originalGraph.getDebug();
452 // @formatter:off
453 StructuredGraph decodedGraph = new StructuredGraph.Builder(originalGraph.getOptions(), debugContext, AllowAssumptions.YES).
454 method(originalGraph.method()).
455 setIsSubstitution(originalGraph.isSubstitution()).
456 trackNodeSourcePosition(originalGraph.trackNodeSourcePosition()).
457 build();
458 // @formatter:off
459 GraphDecoder decoder = new GraphDecoder(architecture, decodedGraph);
460 decoder.decode(encodedGraph);
461
462 decodedGraph.verify();
463 try {
464 GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph);
465 } catch (Throwable ex) {
466 originalGraph.getDebug();
467 try (DebugContext.Scope scope = debugContext.scope("GraphEncoder")) {
468 debugContext.dump(DebugContext.VERBOSE_LEVEL, originalGraph, "Original Graph");
469 debugContext.dump(DebugContext.VERBOSE_LEVEL, decodedGraph, "Decoded Graph");
470 }
471 throw ex;
472 }
473 return true;
474 }
475 }
476
477 class GraphComparison {
478 public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) {
479 NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph);
480 Deque<Pair<Node, Node>> workList = new ArrayDeque<>();
481
482 pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList);
483 while (!workList.isEmpty()) {
484 Pair<Node, Node> pair = workList.removeFirst();
485 Node expectedNode = pair.getLeft();
486 Node actualNode = pair.getRight();
487 assert expectedNode.getClass() == actualNode.getClass();
488
489 NodeClass<?> nodeClass = expectedNode.getNodeClass();
490 assert nodeClass == actualNode.getNodeClass();
491
492 if (expectedNode instanceof MergeNode) {
493 /* The order of the ends can be different, so ignore them. */
494 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true);
495 } else if (expectedNode instanceof PhiNode) {
496 verifyPhi((PhiNode) expectedNode, (PhiNode) actualNode, nodeMapping, workList);
497 } else {
498 verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false);
499 }
500 verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false);
501
502 if (expectedNode instanceof LoopEndNode) {
503 LoopEndNode actualLoopEnd = (LoopEndNode) actualNode;
504 assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex();
505 } else {
506 for (int i = 0; i < nodeClass.getData().getCount(); i++) {
507 Object expectedProperty = nodeClass.getData().get(expectedNode, i);
508 Object actualProperty = nodeClass.getData().get(actualNode, i);
509 assert Objects.equals(expectedProperty, actualProperty);
510 }
511 }
512
513 if (expectedNode instanceof EndNode) {
514 /* Visit the merge node, which is the one and only usage of the EndNode. */
515 assert expectedNode.usages().count() == 1;
516 assert actualNode.usages().count() == 1;
517 verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false);
518 }
519
520 if (expectedNode instanceof AbstractEndNode) {
521 /* Visit the input values of the merge phi functions for this EndNode. */
522 verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList);
523 }
524 }
525
526 return true;
527 }
528
529 protected static void verifyPhi(PhiNode expectedPhi, PhiNode actualPhi, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
530 AbstractMergeNode expectedMergeNode = expectedPhi.merge();
531 AbstractMergeNode actualMergeNode = actualPhi.merge();
532 assert actualMergeNode == nodeMapping.get(expectedMergeNode);
533
534 for (EndNode expectedEndNode : expectedMergeNode.ends) {
535 EndNode actualEndNode = (EndNode) nodeMapping.get(expectedEndNode);
536 if (actualEndNode != null) {
537 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
538 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
539 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
540 }
541 }
542 }
543
544 protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
545 AbstractMergeNode expectedMergeNode = expectedEndNode.merge();
546 AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode);
547 assert actualMergeNode != null;
548
549 for (PhiNode expectedPhi : expectedMergeNode.phis()) {
550 PhiNode actualPhi = (PhiNode) nodeMapping.get(expectedPhi);
551 if (actualPhi != null) {
552 ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
553 ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
554 verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
555 }
556 }
557 }
558
559 private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
560 Iterator<Node> actualIter = actualNodes.iterator();
561 for (Node expectedNode : expectedNodes) {
562 verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode);
563 }
564 assert !actualIter.hasNext();
565 }
566
567 protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
568 assert expectedNode.getClass() == actualNode.getClass();
569 if (ignoreEndNode && expectedNode instanceof EndNode) {
570 return;
571 }
572
573 Node existing = nodeMapping.get(expectedNode);
574 if (existing != null) {
575 assert existing == actualNode;
576 } else {
577 pushToWorklist(expectedNode, actualNode, nodeMapping, workList);
578 }
579 }
580
581 protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
582 nodeMapping.set(expectedNode, actualNode);
583 if (expectedNode instanceof AbstractEndNode) {
584 /* To ensure phi nodes have been added, we handle everything before block ends. */
585 workList.addLast(Pair.create(expectedNode, actualNode));
586 } else {
587 workList.addFirst(Pair.create(expectedNode, actualNode));
588 }
589 }
590 }