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.Debug; 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.UnmodifiableMapCursor; 46 import org.graalvm.util.Pair; 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 a "table of 71 * contents" that lists the start offset for every node. 72 * 73 * The beginning of that table of contents is the return value of {@link #encode} and stored in 74 * {@link EncodedGraph#getStartOffset()}. The order of nodes in the table of contents is the 75 * {@link NodeOrder#orderIds orderId} of a node. Note that the orderId is not the regular node id 76 * that every Graal graph node gets assigned. The orderId is computed and used just for encoding and 77 * decoding. The orderId of fixed nodes is assigned in reverse postorder. The decoder processes 78 * nodes using that order, which ensures that all predecessors of a node (including all 79 * {@link EndNode predecessors} of a {@link AbstractBeginNode block}) are decoded before the node. 80 * The order id of floating node does not matter during decoding, so floating nodes get order ids 81 * after all fixed nodes. The order id is used to encode edges between nodes 82 * 83 * Structure of an encoded node: 84 * 85 * <pre> 86 * struct Node { 87 * unsigned typeId 88 * signed[] properties 89 * unsigned[] inputOrderIds 90 * unsigned[] successorOrderIds 91 * } 92 * </pre> 93 * 94 * All numbers (unsigned and signed) are stored using a variable-length encoding as defined in 95 * {@link TypeReader} and {@link TypeWriter}. Especially orderIds are small, so the variable-length 96 * encoding is important to keep the encoding compact. 97 * 98 * The properties, successors, and inputs are written in the order as defined in 99 * {@link NodeClass#getData}, {@link NodeClass#getSuccessorEdges()}, and 100 * {@link NodeClass#getInputEdges()}. For variable-length successors and input lists, first the 101 * length is written and then the orderIds. There is a distinction between null lists (encoded as 102 * length -1) and empty lists (encoded as length 0). No reverse edges are written (predecessors, 103 * usages) since that information can be easily restored during decoding. 104 * 105 * Some nodes have additional information written after the properties, successors, and inputs: 106 * <li><item>{@link AbstractEndNode}: the orderId of the merge node and then all {@link PhiNode phi 107 * mappings} from this end to the merge node are written. <item>{@link LoopExitNode}: the orderId of 108 * all {@link ProxyNode proxy nodes} of the loop exit is written.</li> 109 */ 110 public class GraphEncoder { 111 112 /** The orderId that always represents {@code null}. */ 113 public static final int NULL_ORDER_ID = 0; 114 /** The orderId of the {@link StructuredGraph#start() start node} of the encoded graph. */ 115 public static final int START_NODE_ORDER_ID = 1; 116 /** 117 * The orderId of the first actual node after the {@link StructuredGraph#start() start node}. 118 */ 119 public static final int FIRST_NODE_ORDER_ID = 2; 120 121 /** 122 * The known offset between the orderId of a {@link AbstractBeginNode} and its 123 * {@link AbstractBeginNode#next() successor}. 124 */ 125 protected static final int BEGIN_NEXT_ORDER_ID_OFFSET = 1; 126 127 protected final Architecture architecture; 128 129 /** 130 * Collects all non-primitive data referenced from nodes. The encoding uses an index into an 131 * array for decoding. Because of the variable-length encoding, it is beneficial that frequently 132 * used objects have the small indices. 133 */ 134 protected final FrequencyEncoder<Object> objects; 135 /** 136 * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass} 137 * currently does not have a unique id. 138 */ 139 protected final FrequencyEncoder<NodeClass<?>> nodeClasses; 140 /** The writer for the encoded graphs. */ 141 protected final UnsafeArrayTypeWriter writer; 142 143 /** The last snapshot of {@link #objects} that was retrieved. */ 144 protected Object[] objectsArray; 145 /** The last snapshot of {@link #nodeClasses} that was retrieved. */ 146 protected NodeClass<?>[] nodeClassesArray; 147 148 /** 149 * Utility method that does everything necessary to encode a single graph. 150 */ 151 public static EncodedGraph encodeSingleGraph(StructuredGraph graph, Architecture architecture) { 152 GraphEncoder encoder = new GraphEncoder(architecture); 153 encoder.prepare(graph); 154 encoder.finishPrepare(); 155 int startOffset = encoder.encode(graph); 156 return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph.getAssumptions(), graph.getMethods()); 157 } 158 159 public GraphEncoder(Architecture architecture) { 160 this.architecture = architecture; 161 objects = FrequencyEncoder.createEqualityEncoder(); 162 nodeClasses = FrequencyEncoder.createIdentityEncoder(); 163 writer = UnsafeArrayTypeWriter.create(architecture.supportsUnalignedMemoryAccess()); 164 } 165 166 /** 167 * Must be invoked before {@link #finishPrepare()} and {@link #encode}. 168 */ 169 public void prepare(StructuredGraph graph) { 170 for (Node node : graph.getNodes()) { 171 nodeClasses.addObject(node.getNodeClass()); 172 173 NodeClass<?> nodeClass = node.getNodeClass(); 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 writeProperties(node, nodeClass.getData()); 227 writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder); 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 /* Write out the table of contents with the start offset for all nodes. */ 280 int nodeTableStart = TypeConversion.asS4(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: " + node; 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.skipDirectEdge(node, edges, idx)) { 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.skipIndirectEdge(node, edges, idx, 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.Builder(originalGraph.getOptions(), AllowAssumptions.YES).method(originalGraph.method()).build(); 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.getLeft(); 434 Node actualNode = pair.getRight(); 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(Pair.create(expectedNode, actualNode)); 534 } else { 535 workList.addFirst(Pair.create(expectedNode, actualNode)); 536 } 537 } 538 }