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
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();
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();
|
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
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();
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();
|