001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes;
024
025import java.util.*;
026
027import jdk.internal.jvmci.code.*;
028import com.oracle.graal.debug.*;
029
030import com.oracle.graal.compiler.common.*;
031import com.oracle.graal.compiler.common.util.*;
032import com.oracle.graal.graph.*;
033import com.oracle.graal.graph.iterators.*;
034import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
035import com.oracle.graal.nodes.java.*;
036
037/**
038 * Encodes a {@link StructuredGraph} to a compact byte[] array. All nodes of the graph and edges
039 * between the nodes are encoded. Primitive data fields of nodes are stored in the byte[] array.
040 * Object data fields of nodes are stored in a separate Object[] array.
041 *
042 * One encoder instance can be used to encode multiple graphs. This requires that {@link #prepare}
043 * is called for all graphs first, followed by one call to {@link #finishPrepare}. Then
044 * {@link #encode} can be called for all graphs. The {@link #getObjects() objects} and
045 * {@link #getNodeClasses() node classes} arrays do not change anymore after preparation.
046 *
047 * Multiple encoded graphs share the Object[] array, and elements of the Object[] array are
048 * de-duplicated using {@link Object#equals Object equality}. This uses the assumption and good
049 * coding practice that data objects are immutable if {@link Object#equals} is implemented.
050 * Unfortunately, this cannot be enforced.
051 *
052 * The Graal {@link NodeClass} does not have a unique id that allows class lookup from an id.
053 * Therefore, the encoded graph contains a {@link NodeClass}[] array for lookup, and type ids are
054 * encoding-local.
055 *
056 * The encoded graph has the following structure: First, all nodes and their edges are serialized.
057 * The start offset of every node is then known. The raw node data is followed by a
058 * "table of contents" that lists the start offset for every node.
059 *
060 * The beginning of that table of contents is the return value of {@link #encode} and stored in
061 * {@link EncodedGraph#getStartOffset()}. The order of nodes in the table of contents is the
062 * {@link NodeOrder#orderIds orderId} of a node. Note that the orderId is not the regular node id
063 * that every Graal graph node gets assigned. The orderId is computed and used just for encoding and
064 * decoding. The orderId of fixed nodes is assigned in reverse postorder. The decoder processes
065 * nodes using that order, which ensures that all predecessors of a node (including all
066 * {@link EndNode predecessors} of a {@link AbstractBeginNode block}) are decoded before the node.
067 * The order id of floating node does not matter during decoding, so floating nodes get order ids
068 * after all fixed nodes. The order id is used to encode edges between nodes
069 *
070 * Structure of an encoded node:
071 *
072 * <pre>
073 * struct Node {
074 *   unsigned typeId
075 *   signed[] properties
076 *   unsigned[] successorOrderIds
077 *   unsigned[] inputOrderIds
078 * }
079 * </pre>
080 *
081 * All numbers (unsigned and signed) are stored using a variable-length encoding as defined in
082 * {@link TypeReader} and {@link TypeWriter}. Especially orderIds are small, so the variable-length
083 * encoding is important to keep the encoding compact.
084 *
085 * The properties, successors, and inputs are written in the order as defined in
086 * {@link NodeClass#getData}, {@link NodeClass#getSuccessorEdges()}, and
087 * {@link NodeClass#getInputEdges()}. For variable-length successors and input lists, first the
088 * length is written and then the orderIds. There is a distinction between null lists (encoded as
089 * length -1) and empty lists (encoded as length 0). No reverse edges are written (predecessors,
090 * usages) since that information can be easily restored during decoding.
091 *
092 * Some nodes have additional information written after the properties, successors, and inputs: <li>
093 * <item>{@link AbstractEndNode}: the orderId of the merge node and then all {@link PhiNode phi
094 * mappings} from this end to the merge node are written. <item>{@link LoopExitNode}: the orderId of
095 * all {@link ProxyNode proxy nodes} of the loop exit is written.</li>
096 */
097public class GraphEncoder {
098
099    /** The orderId that always represents {@code null}. */
100    public static final int NULL_ORDER_ID = 0;
101    /** The orderId of the {@link StructuredGraph#start() start node} of the encoded graph. */
102    public static final int START_NODE_ORDER_ID = 1;
103    /** The orderId of the first actual node after the {@link StructuredGraph#start() start node}. */
104    public static final int FIRST_NODE_ORDER_ID = 2;
105
106    /**
107     * The known offset between the orderId of a {@link AbstractBeginNode} and its
108     * {@link AbstractBeginNode#next() successor}.
109     */
110    protected static final int BEGIN_NEXT_ORDER_ID_OFFSET = 1;
111
112    protected final Architecture architecture;
113
114    /**
115     * Collects all non-primitive data referenced from nodes. The encoding uses an index into an
116     * array for decoding. Because of the variable-length encoding, it is beneficial that frequently
117     * used objects have the small indices.
118     */
119    protected final FrequencyEncoder<Object> objects;
120    /**
121     * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass}
122     * currently does not have a unique id.
123     */
124    protected final FrequencyEncoder<NodeClass<?>> nodeClasses;
125    /** The writer for the encoded graphs. */
126    protected final UnsafeArrayTypeWriter writer;
127
128    /** The last snapshot of {@link #objects} that was retrieved. */
129    protected Object[] objectsArray;
130    /** The last snapshot of {@link #nodeClasses} that was retrieved. */
131    protected NodeClass<?>[] nodeClassesArray;
132
133    /**
134     * Utility method that does everything necessary to encode a single graph.
135     */
136    public static EncodedGraph encodeSingleGraph(StructuredGraph graph, Architecture architecture) {
137        GraphEncoder encoder = new GraphEncoder(architecture);
138        encoder.prepare(graph);
139        encoder.finishPrepare();
140        long startOffset = encoder.encode(graph);
141        return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph.getAssumptions(), graph.getInlinedMethods());
142    }
143
144    public GraphEncoder(Architecture architecture) {
145        this.architecture = architecture;
146        objects = FrequencyEncoder.createEqualityEncoder();
147        nodeClasses = FrequencyEncoder.createIdentityEncoder();
148        writer = UnsafeArrayTypeWriter.create(architecture.supportsUnalignedMemoryAccess());
149    }
150
151    /**
152     * Must be invoked before {@link #finishPrepare()} and {@link #encode}.
153     */
154    public void prepare(StructuredGraph graph) {
155        for (Node node : graph.getNodes()) {
156            nodeClasses.addObject(node.getNodeClass());
157
158            NodeClass<?> nodeClass = node.getNodeClass();
159            for (int i = 0; i < nodeClass.getData().getCount(); i++) {
160                if (!nodeClass.getData().getType(i).isPrimitive()) {
161                    objects.addObject(nodeClass.getData().get(node, i));
162                }
163            }
164            if (node instanceof Invoke) {
165                objects.addObject(((Invoke) node).getContextType());
166            }
167        }
168    }
169
170    public void finishPrepare() {
171        objectsArray = objects.encodeAll(new Object[objects.getLength()]);
172        nodeClassesArray = nodeClasses.encodeAll(new NodeClass[nodeClasses.getLength()]);
173    }
174
175    public Object[] getObjects() {
176        return objectsArray;
177    }
178
179    public NodeClass<?>[] getNodeClasses() {
180        return nodeClassesArray;
181    }
182
183    /**
184     * Compresses a graph to a byte array. Multiple graphs can be compressed with the same
185     * {@link GraphEncoder}.
186     *
187     * @param graph The graph to encode
188     */
189    public long encode(StructuredGraph graph) {
190        assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()";
191
192        NodeOrder nodeOrder = new NodeOrder(graph);
193        int nodeCount = nodeOrder.nextOrderId;
194        assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID;
195        assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID;
196        assert nodeCount == graph.getNodeCount() + 1;
197
198        long[] nodeStartOffsets = new long[nodeCount];
199        for (Map.Entry<Node, Integer> entry : nodeOrder.orderIds.entries()) {
200            Node node = entry.getKey();
201            Integer orderId = entry.getValue();
202
203            assert !(node instanceof AbstractBeginNode) || nodeOrder.orderIds.get(((AbstractBeginNode) node).next()) == orderId + BEGIN_NEXT_ORDER_ID_OFFSET;
204            nodeStartOffsets[orderId] = writer.getBytesWritten();
205
206            /* Write out the type, properties, and edges. */
207            NodeClass<?> nodeClass = node.getNodeClass();
208            writer.putUV(nodeClasses.getIndex(nodeClass));
209            writeProperties(node, nodeClass.getData());
210            writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), nodeOrder);
211            writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder);
212
213            /* Special handling for some nodes that require additional information for decoding. */
214            if (node instanceof AbstractEndNode) {
215                AbstractEndNode end = (AbstractEndNode) node;
216                AbstractMergeNode merge = end.merge();
217                /*
218                 * Write the orderId of the merge. The merge is not a successor in the Graal graph
219                 * (only the merge has an input edge to the EndNode).
220                 */
221                writeOrderId(merge, nodeOrder);
222
223                /*
224                 * Write all phi mappings (the oderId of the phi input for this EndNode, and the
225                 * orderId of the phi node.
226                 */
227                writer.putUV(merge.phis().count());
228                for (PhiNode phi : merge.phis()) {
229                    writeOrderId(phi.valueAt(end), nodeOrder);
230                    writeOrderId(phi, nodeOrder);
231                }
232
233            } else if (node instanceof LoopExitNode) {
234                LoopExitNode exit = (LoopExitNode) node;
235                writeOrderId(exit.stateAfter(), nodeOrder);
236                /* Write all proxy nodes of the LoopExitNode. */
237                writer.putUV(exit.proxies().count());
238                for (ProxyNode proxy : exit.proxies()) {
239                    writeOrderId(proxy, nodeOrder);
240                }
241
242            } else if (node instanceof Invoke) {
243                Invoke invoke = (Invoke) node;
244                assert invoke.stateDuring() == null : "stateDuring is not used in high-level graphs";
245
246                writeObjectId(invoke.getContextType());
247                writeOrderId(invoke.callTarget(), nodeOrder);
248                writeOrderId(invoke.stateAfter(), nodeOrder);
249                writeOrderId(invoke.next(), nodeOrder);
250                if (invoke instanceof InvokeWithExceptionNode) {
251                    InvokeWithExceptionNode invokeWithExcpetion = (InvokeWithExceptionNode) invoke;
252                    ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExcpetion.exceptionEdge();
253
254                    writeOrderId(invokeWithExcpetion.next().next(), nodeOrder);
255                    writeOrderId(invokeWithExcpetion.exceptionEdge(), nodeOrder);
256                    writeOrderId(exceptionEdge.stateAfter(), nodeOrder);
257                    writeOrderId(exceptionEdge.next(), nodeOrder);
258                }
259            }
260        }
261
262        /* Write out the table of contents with the start offset for all nodes. */
263        long nodeTableStart = writer.getBytesWritten();
264        writer.putUV(nodeCount);
265        for (int i = 0; i < nodeCount; i++) {
266            assert i == NULL_ORDER_ID || i == START_NODE_ORDER_ID || nodeStartOffsets[i] > 0;
267            writer.putUV(nodeTableStart - nodeStartOffsets[i]);
268        }
269
270        /* Check that the decoding of the encode graph is the same as the input. */
271        assert verifyEncoding(graph, new EncodedGraph(getEncoding(), nodeTableStart, getObjects(), getNodeClasses(), graph.getAssumptions(), graph.getInlinedMethods()), architecture);
272
273        return nodeTableStart;
274    }
275
276    public byte[] getEncoding() {
277        return writer.toArray(new byte[TypeConversion.asS4(writer.getBytesWritten())]);
278    }
279
280    static class NodeOrder {
281        protected final NodeMap<Integer> orderIds;
282        protected int nextOrderId;
283
284        public NodeOrder(StructuredGraph graph) {
285            this.orderIds = new NodeMap<>(graph);
286            this.nextOrderId = START_NODE_ORDER_ID;
287
288            /* Order the fixed nodes of the graph in reverse postorder. */
289            Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
290            FixedNode current = graph.start();
291            do {
292                add(current);
293                if (current instanceof AbstractBeginNode) {
294                    add(((AbstractBeginNode) current).next());
295                }
296
297                if (current instanceof FixedWithNextNode) {
298                    current = ((FixedWithNextNode) current).next;
299                } else {
300                    if (current instanceof ControlSplitNode) {
301                        for (Node successor : current.successors()) {
302                            if (successor != null) {
303                                nodeQueue.addFirst((AbstractBeginNode) successor);
304                            }
305                        }
306                    } else if (current instanceof EndNode) {
307                        AbstractMergeNode merge = ((AbstractEndNode) current).merge();
308                        boolean allForwardEndsVisited = true;
309                        for (int i = 0; i < merge.forwardEndCount(); i++) {
310                            if (orderIds.get(merge.forwardEndAt(i)) == null) {
311                                allForwardEndsVisited = false;
312                                break;
313                            }
314                        }
315                        if (allForwardEndsVisited) {
316                            nodeQueue.add(merge);
317                        }
318                    }
319                    current = nodeQueue.pollFirst();
320                }
321            } while (current != null);
322
323            for (Node node : graph.getNodes()) {
324                assert (node instanceof FixedNode) == (orderIds.get(node) != null) : "all fixed nodes must be ordered";
325                add(node);
326            }
327        }
328
329        private void add(Node node) {
330            if (orderIds.get(node) == null) {
331                orderIds.set(node, nextOrderId);
332                nextOrderId++;
333            }
334        }
335    }
336
337    protected void writeProperties(Node node, Fields fields) {
338        for (int idx = 0; idx < fields.getCount(); idx++) {
339            if (fields.getType(idx).isPrimitive()) {
340                long primitive = fields.getRawPrimitive(node, idx);
341                writer.putSV(primitive);
342            } else {
343                Object property = fields.get(node, idx);
344                writeObjectId(property);
345            }
346        }
347    }
348
349    protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) {
350        for (int idx = 0; idx < edges.getDirectCount(); idx++) {
351            if (GraphDecoder.skipEdge(node, edges, idx, true, false)) {
352                /* Edge is not needed for decoding, so we must not write it. */
353                continue;
354            }
355            Node edge = Edges.getNode(node, edges.getOffsets(), idx);
356            writeOrderId(edge, nodeOrder);
357        }
358        for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) {
359            if (GraphDecoder.skipEdge(node, edges, idx, false, false)) {
360                /* Edge is not needed for decoding, so we must not write it. */
361                continue;
362            }
363            NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx);
364            if (edgeList == null) {
365                writer.putSV(-1);
366            } else {
367                writer.putSV(edgeList.size());
368                for (Node edge : edgeList) {
369                    writeOrderId(edge, nodeOrder);
370                }
371            }
372        }
373    }
374
375    protected void writeOrderId(Node node, NodeOrder nodeOrder) {
376        writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node));
377    }
378
379    protected void writeObjectId(Object object) {
380        writer.putUV(objects.getIndex(object));
381    }
382
383    /**
384     * Verification code that checks that the decoding of an encode graph is the same as the
385     * original graph.
386     */
387    public static boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph, Architecture architecture) {
388        StructuredGraph decodedGraph = new StructuredGraph(originalGraph.method(), AllowAssumptions.YES);
389        GraphDecoder decoder = new GraphDecoder(architecture);
390        decoder.decode(decodedGraph, encodedGraph);
391
392        decodedGraph.verify();
393        try {
394            GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph);
395        } catch (Throwable ex) {
396            try (Debug.Scope scope = Debug.scope("GraphEncoder")) {
397                Debug.dump(originalGraph, "Original Graph");
398                Debug.dump(decodedGraph, "Decoded Graph");
399            }
400            throw ex;
401        }
402        return true;
403    }
404}
405
406class GraphComparison {
407    public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) {
408        NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph);
409        Deque<Pair<Node, Node>> workList = new ArrayDeque<>();
410
411        pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList);
412        while (!workList.isEmpty()) {
413            Pair<Node, Node> pair = workList.removeFirst();
414            Node expectedNode = pair.first;
415            Node actualNode = pair.second;
416            assert expectedNode.getClass() == actualNode.getClass();
417
418            NodeClass<?> nodeClass = expectedNode.getNodeClass();
419            assert nodeClass == actualNode.getNodeClass();
420
421            if (expectedNode instanceof MergeNode) {
422                /* The order of the ends can be different, so ignore them. */
423                verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true);
424            } else if (expectedNode instanceof PhiNode) {
425                verifyPhi((PhiNode) expectedNode, (PhiNode) actualNode, nodeMapping, workList);
426            } else {
427                verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false);
428            }
429            verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false);
430
431            if (expectedNode instanceof LoopEndNode) {
432                LoopEndNode actualLoopEnd = (LoopEndNode) actualNode;
433                assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex();
434            } else {
435                for (int i = 0; i < nodeClass.getData().getCount(); i++) {
436                    Object expectedProperty = nodeClass.getData().get(expectedNode, i);
437                    Object actualProperty = nodeClass.getData().get(actualNode, i);
438                    assert Objects.equals(expectedProperty, actualProperty);
439                }
440            }
441
442            if (expectedNode instanceof EndNode) {
443                /* Visit the merge node, which is the one and only usage of the EndNode. */
444                assert expectedNode.usages().count() == 1;
445                assert actualNode.usages().count() == 1;
446                verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false);
447            }
448
449            if (expectedNode instanceof AbstractEndNode) {
450                /* Visit the input values of the merge phi functions for this EndNode. */
451                verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList);
452            }
453        }
454
455        return true;
456    }
457
458    protected static void verifyPhi(PhiNode expectedPhi, PhiNode actualPhi, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
459        AbstractMergeNode expectedMergeNode = expectedPhi.merge();
460        AbstractMergeNode actualMergeNode = actualPhi.merge();
461        assert actualMergeNode == nodeMapping.get(expectedMergeNode);
462
463        for (EndNode expectedEndNode : expectedMergeNode.ends) {
464            EndNode actualEndNode = (EndNode) nodeMapping.get(expectedEndNode);
465            if (actualEndNode != null) {
466                ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
467                ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
468                verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
469            }
470        }
471    }
472
473    protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
474        AbstractMergeNode expectedMergeNode = expectedEndNode.merge();
475        AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode);
476        assert actualMergeNode != null;
477
478        for (PhiNode expectedPhi : expectedMergeNode.phis()) {
479            PhiNode actualPhi = (PhiNode) nodeMapping.get(expectedPhi);
480            if (actualPhi != null) {
481                ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode);
482                ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode);
483                verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false);
484            }
485        }
486    }
487
488    private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
489        Iterator<Node> actualIter = actualNodes.iterator();
490        for (Node expectedNode : expectedNodes) {
491            verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode);
492        }
493        assert !actualIter.hasNext();
494    }
495
496    protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) {
497        assert expectedNode.getClass() == actualNode.getClass();
498        if (ignoreEndNode && expectedNode instanceof EndNode) {
499            return;
500        }
501
502        Node existing = nodeMapping.get(expectedNode);
503        if (existing != null) {
504            assert existing == actualNode;
505        } else {
506            pushToWorklist(expectedNode, actualNode, nodeMapping, workList);
507        }
508    }
509
510    protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) {
511        nodeMapping.set(expectedNode, actualNode);
512        if (expectedNode instanceof AbstractEndNode) {
513            /* To ensure phi nodes have been added, we handle everything before block ends. */
514            workList.addLast(new Pair<>(expectedNode, actualNode));
515        } else {
516            workList.addFirst(new Pair<>(expectedNode, actualNode));
517        }
518    }
519}
520
521class Pair<F, S> {
522    public final F first;
523    public final S second;
524
525    public Pair(F first, S second) {
526        this.first = first;
527        this.second = second;
528    }
529}