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 }