1 /*
2 * Copyright (c) 2011, 2014, 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.printer;
24
25 import static org.graalvm.compiler.graph.Edges.Type.Inputs;
26 import static org.graalvm.compiler.graph.Edges.Type.Successors;
27
28 import java.io.IOException;
29 import java.nio.ByteBuffer;
30 import java.nio.channels.WritableByteChannel;
31 import java.nio.charset.Charset;
32 import java.util.Arrays;
33 import java.util.HashMap;
34 import java.util.LinkedHashMap;
35 import java.util.LinkedList;
36 import java.util.List;
37 import java.util.Map;
38 import java.util.Map.Entry;
39
40 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
41 import org.graalvm.compiler.core.common.cfg.BlockMap;
42 import org.graalvm.compiler.debug.Debug;
43 import org.graalvm.compiler.debug.GraalDebugConfig.Options;
44 import org.graalvm.compiler.graph.CachedGraph;
45 import org.graalvm.compiler.graph.Edges;
46 import org.graalvm.compiler.graph.Graph;
47 import org.graalvm.compiler.graph.InputEdges;
48 import org.graalvm.compiler.graph.Node;
49 import org.graalvm.compiler.graph.NodeClass;
50 import org.graalvm.compiler.graph.NodeList;
51 import org.graalvm.compiler.graph.NodeMap;
52 import org.graalvm.compiler.nodes.AbstractBeginNode;
53 import org.graalvm.compiler.nodes.AbstractEndNode;
54 import org.graalvm.compiler.nodes.AbstractMergeNode;
55 import org.graalvm.compiler.nodes.ConstantNode;
56 import org.graalvm.compiler.nodes.ControlSinkNode;
57 import org.graalvm.compiler.nodes.ControlSplitNode;
58 import org.graalvm.compiler.nodes.FixedNode;
59 import org.graalvm.compiler.nodes.PhiNode;
60 import org.graalvm.compiler.nodes.ProxyNode;
61 import org.graalvm.compiler.nodes.StructuredGraph;
62 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
63 import org.graalvm.compiler.nodes.VirtualState;
64 import org.graalvm.compiler.nodes.cfg.Block;
65 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
66 import org.graalvm.compiler.phases.schedule.SchedulePhase;
67
68 import jdk.vm.ci.meta.JavaType;
69 import jdk.vm.ci.meta.ResolvedJavaField;
70 import jdk.vm.ci.meta.ResolvedJavaMethod;
71 import jdk.vm.ci.meta.Signature;
72
73 public class BinaryGraphPrinter implements GraphPrinter {
74
75 private static final int CONSTANT_POOL_MAX_SIZE = 8000;
76
77 private static final int BEGIN_GROUP = 0x00;
78 private static final int BEGIN_GRAPH = 0x01;
79 private static final int CLOSE_GROUP = 0x02;
80
81 private static final int POOL_NEW = 0x00;
82 private static final int POOL_STRING = 0x01;
83 private static final int POOL_ENUM = 0x02;
84 private static final int POOL_CLASS = 0x03;
85 private static final int POOL_METHOD = 0x04;
86 private static final int POOL_NULL = 0x05;
87 private static final int POOL_NODE_CLASS = 0x06;
88 private static final int POOL_FIELD = 0x07;
89 private static final int POOL_SIGNATURE = 0x08;
90
91 private static final int PROPERTY_POOL = 0x00;
92 private static final int PROPERTY_INT = 0x01;
93 private static final int PROPERTY_LONG = 0x02;
94 private static final int PROPERTY_DOUBLE = 0x03;
95 private static final int PROPERTY_FLOAT = 0x04;
96 private static final int PROPERTY_TRUE = 0x05;
97 private static final int PROPERTY_FALSE = 0x06;
98 private static final int PROPERTY_ARRAY = 0x07;
99 private static final int PROPERTY_SUBGRAPH = 0x08;
100
101 private static final int KLASS = 0x00;
102 private static final int ENUM_KLASS = 0x01;
103
104 static final int CURRENT_MAJOR_VERSION = 1;
105 static final int CURRENT_MINOR_VERSION = 0;
106
107 static final byte[] MAGIC_BYTES = {'B', 'I', 'G', 'V'};
108
109 private void writeVersion() throws IOException {
110 writeBytesRaw(MAGIC_BYTES);
111 writeByte(CURRENT_MAJOR_VERSION);
112 writeByte(CURRENT_MINOR_VERSION);
113 }
114
115 private static final class ConstantPool extends LinkedHashMap<Object, Character> {
116
117 private final LinkedList<Character> availableIds;
118 private char nextId;
119 private static final long serialVersionUID = -2676889957907285681L;
120
121 ConstantPool() {
122 super(50, 0.65f);
123 availableIds = new LinkedList<>();
124 }
125
126 @Override
127 protected boolean removeEldestEntry(java.util.Map.Entry<Object, Character> eldest) {
128 if (size() > CONSTANT_POOL_MAX_SIZE) {
129 availableIds.addFirst(eldest.getValue());
130 return true;
131 }
132 return false;
133 }
134
135 private Character nextAvailableId() {
136 if (!availableIds.isEmpty()) {
137 return availableIds.removeFirst();
138 }
139 return nextId++;
140 }
141
142 public char add(Object obj) {
143 Character id = nextAvailableId();
144 put(obj, id);
145 return id;
146 }
147 }
148
149 private final ConstantPool constantPool;
150 private final ByteBuffer buffer;
151 private final WritableByteChannel channel;
152 private final SnippetReflectionProvider snippetReflection;
153
154 private static final Charset utf8 = Charset.forName("UTF-8");
155
156 public BinaryGraphPrinter(WritableByteChannel channel, SnippetReflectionProvider snippetReflection) throws IOException {
157 constantPool = new ConstantPool();
158 buffer = ByteBuffer.allocateDirect(256 * 1024);
159 this.snippetReflection = snippetReflection;
160 this.channel = channel;
161 writeVersion();
162 }
163
164 @Override
165 public SnippetReflectionProvider getSnippetReflectionProvider() {
166 return snippetReflection;
167 }
168
169 @Override
170 public void print(Graph graph, String title, Map<Object, Object> properties) throws IOException {
171 writeByte(BEGIN_GRAPH);
172 writePoolObject(title);
173 writeGraph(graph, properties);
174 flush();
175 }
176
177 private void writeGraph(Graph graph, Map<Object, Object> properties) throws IOException {
178 ScheduleResult scheduleResult = null;
179 if (graph instanceof StructuredGraph) {
180
181 StructuredGraph structuredGraph = (StructuredGraph) graph;
182 scheduleResult = structuredGraph.getLastSchedule();
183 if (scheduleResult == null) {
184
185 // Also provide a schedule when an error occurs
186 if (Options.PrintIdealGraphSchedule.getValue() || Debug.contextLookup(Throwable.class) != null) {
187 try {
188 SchedulePhase schedule = new SchedulePhase();
189 schedule.apply(structuredGraph);
190 scheduleResult = structuredGraph.getLastSchedule();
191 } catch (Throwable t) {
192 }
193 }
194
195 }
196 }
197 ControlFlowGraph cfg = scheduleResult == null ? Debug.contextLookup(ControlFlowGraph.class) : scheduleResult.getCFG();
198 BlockMap<List<Node>> blockToNodes = scheduleResult == null ? null : scheduleResult.getBlockToNodesMap();
199 NodeMap<Block> nodeToBlocks = scheduleResult == null ? null : scheduleResult.getNodeToBlockMap();
200 List<Block> blocks = cfg == null ? null : Arrays.asList(cfg.getBlocks());
201 writeProperties(properties);
202 writeNodes(graph, nodeToBlocks, cfg);
203 writeBlocks(blocks, blockToNodes);
204 }
205
206 private void flush() throws IOException {
207 buffer.flip();
208 channel.write(buffer);
209 buffer.compact();
210 }
211
212 private void ensureAvailable(int i) throws IOException {
213 assert buffer.capacity() >= i : "Can not make " + i + " bytes available, buffer is too small";
214 while (buffer.remaining() < i) {
215 flush();
216 }
217 }
218
219 private void writeByte(int b) throws IOException {
220 ensureAvailable(1);
221 buffer.put((byte) b);
222 }
223
224 private void writeInt(int b) throws IOException {
225 ensureAvailable(4);
226 buffer.putInt(b);
227 }
228
229 private void writeLong(long b) throws IOException {
230 ensureAvailable(8);
231 buffer.putLong(b);
232 }
233
234 private void writeDouble(double b) throws IOException {
235 ensureAvailable(8);
236 buffer.putDouble(b);
237 }
238
239 private void writeFloat(float b) throws IOException {
240 ensureAvailable(4);
241 buffer.putFloat(b);
242 }
243
244 private void writeShort(char b) throws IOException {
245 ensureAvailable(2);
246 buffer.putChar(b);
247 }
248
249 private void writeString(String str) throws IOException {
250 byte[] bytes = str.getBytes(utf8);
251 writeBytes(bytes);
252 }
253
254 private void writeBytes(byte[] b) throws IOException {
255 if (b == null) {
256 writeInt(-1);
257 } else {
258 writeInt(b.length);
259 writeBytesRaw(b);
260 }
261 }
262
263 private void writeBytesRaw(byte[] b) throws IOException {
264 int bytesWritten = 0;
265 while (bytesWritten < b.length) {
266 int toWrite = Math.min(b.length - bytesWritten, buffer.capacity());
267 ensureAvailable(toWrite);
268 buffer.put(b, bytesWritten, toWrite);
269 bytesWritten += toWrite;
270 }
271 }
272
273 private void writeInts(int[] b) throws IOException {
274 if (b == null) {
275 writeInt(-1);
276 } else {
277 writeInt(b.length);
278 int sizeInBytes = b.length * 4;
279 ensureAvailable(sizeInBytes);
280 buffer.asIntBuffer().put(b);
281 buffer.position(buffer.position() + sizeInBytes);
282 }
283 }
284
285 private void writeDoubles(double[] b) throws IOException {
286 if (b == null) {
287 writeInt(-1);
288 } else {
289 writeInt(b.length);
290 int sizeInBytes = b.length * 8;
291 ensureAvailable(sizeInBytes);
292 buffer.asDoubleBuffer().put(b);
293 buffer.position(buffer.position() + sizeInBytes);
294 }
295 }
296
297 private void writePoolObject(Object object) throws IOException {
298 if (object == null) {
299 writeByte(POOL_NULL);
300 return;
301 }
302 Character id = constantPool.get(object);
303 if (id == null) {
304 addPoolEntry(object);
305 } else {
306 if (object instanceof Enum<?>) {
307 writeByte(POOL_ENUM);
308 } else if (object instanceof Class<?> || object instanceof JavaType) {
309 writeByte(POOL_CLASS);
310 } else if (object instanceof NodeClass) {
311 writeByte(POOL_NODE_CLASS);
312 } else if (object instanceof ResolvedJavaMethod) {
313 writeByte(POOL_METHOD);
314 } else if (object instanceof ResolvedJavaField) {
315 writeByte(POOL_FIELD);
316 } else if (object instanceof Signature) {
317 writeByte(POOL_SIGNATURE);
318 } else {
319 writeByte(POOL_STRING);
320 }
321 writeShort(id.charValue());
322 }
323 }
324
325 private static String getClassName(Class<?> klass) {
326 if (!klass.isArray()) {
327 return klass.getName();
328 }
329 return getClassName(klass.getComponentType()) + "[]";
330 }
331
332 private void addPoolEntry(Object object) throws IOException {
333 char index = constantPool.add(object);
334 writeByte(POOL_NEW);
335 writeShort(index);
336 if (object instanceof Class<?>) {
337 Class<?> klass = (Class<?>) object;
338 writeByte(POOL_CLASS);
339 writeString(getClassName(klass));
340 if (klass.isEnum()) {
341 writeByte(ENUM_KLASS);
342 Object[] enumConstants = klass.getEnumConstants();
343 writeInt(enumConstants.length);
344 for (Object o : enumConstants) {
345 writePoolObject(((Enum<?>) o).name());
346 }
347 } else {
348 writeByte(KLASS);
349 }
350 } else if (object instanceof Enum<?>) {
351 writeByte(POOL_ENUM);
352 writePoolObject(object.getClass());
353 writeInt(((Enum<?>) object).ordinal());
354 } else if (object instanceof JavaType) {
355 JavaType type = (JavaType) object;
356 writeByte(POOL_CLASS);
357 writeString(type.toJavaName());
358 writeByte(KLASS);
359 } else if (object instanceof NodeClass) {
360 NodeClass<?> nodeClass = (NodeClass<?>) object;
361 writeByte(POOL_NODE_CLASS);
362 writeString(nodeClass.getJavaClass().getSimpleName());
363 writeString(nodeClass.getNameTemplate());
364 writeEdgesInfo(nodeClass, Inputs);
365 writeEdgesInfo(nodeClass, Successors);
366 } else if (object instanceof ResolvedJavaMethod) {
367 writeByte(POOL_METHOD);
368 ResolvedJavaMethod method = ((ResolvedJavaMethod) object);
369 writePoolObject(method.getDeclaringClass());
370 writePoolObject(method.getName());
371 writePoolObject(method.getSignature());
372 writeInt(method.getModifiers());
373 writeBytes(method.getCode());
374 } else if (object instanceof ResolvedJavaField) {
375 writeByte(POOL_FIELD);
376 ResolvedJavaField field = ((ResolvedJavaField) object);
377 writePoolObject(field.getDeclaringClass());
378 writePoolObject(field.getName());
379 writePoolObject(field.getType().getName());
380 writeInt(field.getModifiers());
381 } else if (object instanceof Signature) {
382 writeByte(POOL_SIGNATURE);
383 Signature signature = ((Signature) object);
384 int args = signature.getParameterCount(false);
385 writeShort((char) args);
386 for (int i = 0; i < args; i++) {
387 writePoolObject(signature.getParameterType(i, null).getName());
388 }
389 writePoolObject(signature.getReturnType(null).getName());
390 } else {
391 writeByte(POOL_STRING);
392 writeString(object.toString());
393 }
394 }
395
396 private void writeEdgesInfo(NodeClass<?> nodeClass, Edges.Type type) throws IOException {
397 Edges edges = nodeClass.getEdges(type);
398 writeShort((char) edges.getCount());
399 for (int i = 0; i < edges.getCount(); i++) {
400 writeByte(i < edges.getDirectCount() ? 0 : 1);
401 writePoolObject(edges.getName(i));
402 if (type == Inputs) {
403 writePoolObject(((InputEdges) edges).getInputType(i));
404 }
405 }
406 }
407
408 private void writePropertyObject(Object obj) throws IOException {
409 if (obj instanceof Integer) {
410 writeByte(PROPERTY_INT);
411 writeInt(((Integer) obj).intValue());
412 } else if (obj instanceof Long) {
413 writeByte(PROPERTY_LONG);
414 writeLong(((Long) obj).longValue());
415 } else if (obj instanceof Double) {
416 writeByte(PROPERTY_DOUBLE);
417 writeDouble(((Double) obj).doubleValue());
418 } else if (obj instanceof Float) {
419 writeByte(PROPERTY_FLOAT);
420 writeFloat(((Float) obj).floatValue());
421 } else if (obj instanceof Boolean) {
422 if (((Boolean) obj).booleanValue()) {
423 writeByte(PROPERTY_TRUE);
424 } else {
425 writeByte(PROPERTY_FALSE);
426 }
427 } else if (obj instanceof Graph) {
428 writeByte(PROPERTY_SUBGRAPH);
429 writeGraph((Graph) obj, null);
430 } else if (obj instanceof CachedGraph) {
431 writeByte(PROPERTY_SUBGRAPH);
432 writeGraph(((CachedGraph<?>) obj).getReadonlyCopy(), null);
433 } else if (obj != null && obj.getClass().isArray()) {
434 Class<?> componentType = obj.getClass().getComponentType();
435 if (componentType.isPrimitive()) {
436 if (componentType == Double.TYPE) {
437 writeByte(PROPERTY_ARRAY);
438 writeByte(PROPERTY_DOUBLE);
439 writeDoubles((double[]) obj);
440 } else if (componentType == Integer.TYPE) {
441 writeByte(PROPERTY_ARRAY);
442 writeByte(PROPERTY_INT);
443 writeInts((int[]) obj);
444 } else {
445 writeByte(PROPERTY_POOL);
446 writePoolObject(obj);
447 }
448 } else {
449 writeByte(PROPERTY_ARRAY);
450 writeByte(PROPERTY_POOL);
451 Object[] array = (Object[]) obj;
452 writeInt(array.length);
453 for (Object o : array) {
454 writePoolObject(o);
455 }
456 }
457 } else {
458 writeByte(PROPERTY_POOL);
459 writePoolObject(obj);
460 }
461 }
462
463 @SuppressWarnings("deprecation")
464 private static int getNodeId(Node node) {
465 return node.getId();
466 }
467
468 private Object getBlockForNode(Node node, NodeMap<Block> nodeToBlocks) {
469 if (nodeToBlocks.isNew(node)) {
470 return "NEW (not in schedule)";
471 } else {
472 Block block = nodeToBlocks.get(node);
473 if (block != null) {
474 return block.getId();
475 } else if (node instanceof PhiNode) {
476 return getBlockForNode(((PhiNode) node).merge(), nodeToBlocks);
477 }
478 }
479 return null;
480 }
481
482 private void writeNodes(Graph graph, NodeMap<Block> nodeToBlocks, ControlFlowGraph cfg) throws IOException {
483 Map<Object, Object> props = new HashMap<>();
484
485 writeInt(graph.getNodeCount());
486
487 for (Node node : graph.getNodes()) {
488 NodeClass<?> nodeClass = node.getNodeClass();
489 node.getDebugProperties(props);
490 if (cfg != null && Options.PrintGraphProbabilities.getValue() && node instanceof FixedNode) {
491 try {
492 props.put("probability", cfg.blockFor(node).probability());
493 } catch (Throwable t) {
494 props.put("probability", 0.0);
495 props.put("probability-exception", t);
496 }
497 }
498 if (nodeToBlocks != null) {
499 Object block = getBlockForNode(node, nodeToBlocks);
500 if (block != null) {
501 props.put("node-to-block", block);
502 }
503 }
504
505 if (node instanceof ControlSinkNode) {
506 props.put("category", "controlSink");
507 } else if (node instanceof ControlSplitNode) {
508 props.put("category", "controlSplit");
509 } else if (node instanceof AbstractMergeNode) {
510 props.put("category", "merge");
511 } else if (node instanceof AbstractBeginNode) {
512 props.put("category", "begin");
513 } else if (node instanceof AbstractEndNode) {
514 props.put("category", "end");
515 } else if (node instanceof FixedNode) {
516 props.put("category", "fixed");
517 } else if (node instanceof VirtualState) {
518 props.put("category", "state");
519 } else if (node instanceof PhiNode) {
520 props.put("category", "phi");
521 } else if (node instanceof ProxyNode) {
522 props.put("category", "proxy");
523 } else {
524 if (node instanceof ConstantNode) {
525 ConstantNode cn = (ConstantNode) node;
526 updateStringPropertiesForConstant(props, cn);
527 }
528 props.put("category", "floating");
529 }
530
531 writeInt(getNodeId(node));
532 writePoolObject(nodeClass);
533 writeByte(node.predecessor() == null ? 0 : 1);
534 writeProperties(props);
535 writeEdges(node, Inputs);
536 writeEdges(node, Successors);
537
538 props.clear();
539 }
540 }
541
542 private void writeProperties(Map<Object, Object> props) throws IOException {
543 if (props == null) {
544 writeShort((char) 0);
545 return;
546 }
547 // properties
548 writeShort((char) props.size());
549 for (Entry<Object, Object> entry : props.entrySet()) {
550 String key = entry.getKey().toString();
551 writePoolObject(key);
552 writePropertyObject(entry.getValue());
553 }
554 }
555
556 private void writeEdges(Node node, Edges.Type type) throws IOException {
557 NodeClass<?> nodeClass = node.getNodeClass();
558 Edges edges = nodeClass.getEdges(type);
559 final long[] curOffsets = edges.getOffsets();
560 for (int i = 0; i < edges.getDirectCount(); i++) {
561 writeNodeRef(Edges.getNode(node, curOffsets, i));
562 }
563 for (int i = edges.getDirectCount(); i < edges.getCount(); i++) {
564 NodeList<Node> list = Edges.getNodeList(node, curOffsets, i);
565 if (list == null) {
566 writeShort((char) 0);
567 } else {
568 int listSize = list.count();
569 assert listSize == ((char) listSize);
570 writeShort((char) listSize);
571 for (Node edge : list) {
572 writeNodeRef(edge);
573 }
574 }
575 }
576 }
577
578 private void writeNodeRef(Node edge) throws IOException {
579 if (edge != null) {
580 writeInt(getNodeId(edge));
581 } else {
582 writeInt(-1);
583 }
584 }
585
586 private void writeBlocks(List<Block> blocks, BlockMap<List<Node>> blockToNodes) throws IOException {
587 if (blocks != null && blockToNodes != null) {
588 for (Block block : blocks) {
589 List<Node> nodes = blockToNodes.get(block);
590 if (nodes == null) {
591 writeInt(0);
592 return;
593 }
594 }
595 writeInt(blocks.size());
596 for (Block block : blocks) {
597 List<Node> nodes = blockToNodes.get(block);
598 List<Node> extraNodes = new LinkedList<>();
599 writeInt(block.getId());
600 for (Node node : nodes) {
601 if (node instanceof AbstractMergeNode) {
602 AbstractMergeNode merge = (AbstractMergeNode) node;
603 for (PhiNode phi : merge.phis()) {
604 if (!nodes.contains(phi)) {
605 extraNodes.add(phi);
606 }
607 }
608 }
609 }
610 writeInt(nodes.size() + extraNodes.size());
611 for (Node node : nodes) {
612 writeInt(getNodeId(node));
613 }
614 for (Node node : extraNodes) {
615 writeInt(getNodeId(node));
616 }
617 writeInt(block.getSuccessors().length);
618 for (Block sux : block.getSuccessors()) {
619 writeInt(sux.getId());
620 }
621 }
622 } else {
623 writeInt(0);
624 }
625 }
626
627 @Override
628 public void beginGroup(String name, String shortName, ResolvedJavaMethod method, int bci, Map<Object, Object> properties) throws IOException {
629 writeByte(BEGIN_GROUP);
630 writePoolObject(name);
631 writePoolObject(shortName);
632 writePoolObject(method);
633 writeInt(bci);
634 writeProperties(properties);
635 }
636
637 @Override
638 public void endGroup() throws IOException {
639 writeByte(CLOSE_GROUP);
640 }
641
642 @Override
643 public void close() {
644 try {
645 flush();
646 channel.close();
647 } catch (IOException ex) {
648 throw new Error(ex);
649 }
650 }
651 }