CFGPrinter.java revision 12657:6ef01bd40ce2 
1169689Skan/*
2169689Skan * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
3169689Skan * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4169689Skan *
5169689Skan * This code is free software; you can redistribute it and/or modify it
6169689Skan * under the terms of the GNU General Public License version 2 only, as
7169689Skan * published by the Free Software Foundation.
8169689Skan *
9169689Skan * This code is distributed in the hope that it will be useful, but WITHOUT
10169689Skan * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11169689Skan * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12169689Skan * version 2 for more details (a copy is included in the LICENSE file that
13169689Skan * accompanied this code).
14169689Skan *
15169689Skan * You should have received a copy of the GNU General Public License version
16169689Skan * 2 along with this work; if not, write to the Free Software Foundation,
17169689Skan * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18169689Skan *
19169689Skan * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20169689Skan * or visit www.oracle.com if you need additional information or have any
21169689Skan * questions.
22169689Skan */
23169689Skanpackage org.graalvm.compiler.printer;
24169689Skan
25169689Skanimport static java.lang.Character.toLowerCase;
26169689Skan
27169689Skanimport java.io.OutputStream;
28169689Skanimport java.util.ArrayList;
29169689Skanimport java.util.Arrays;
30169689Skanimport java.util.BitSet;
31169689Skanimport java.util.Iterator;
32169689Skanimport java.util.List;
33169689Skanimport java.util.Map;
34169689Skanimport java.util.TreeMap;
35169689Skan
36169689Skanimport org.graalvm.compiler.bytecode.BytecodeDisassembler;
37import org.graalvm.compiler.bytecode.Bytecode;
38import org.graalvm.compiler.core.common.alloc.Trace;
39import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
40import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
41import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
42import org.graalvm.compiler.core.gen.NodeLIRBuilder;
43import org.graalvm.compiler.graph.Node;
44import org.graalvm.compiler.graph.NodeBitMap;
45import org.graalvm.compiler.graph.NodeMap;
46import org.graalvm.compiler.graph.Position;
47import org.graalvm.compiler.java.BciBlockMapping;
48import org.graalvm.compiler.lir.LIR;
49import org.graalvm.compiler.lir.LIRInstruction;
50import org.graalvm.compiler.lir.debug.IntervalDumper;
51import org.graalvm.compiler.lir.debug.IntervalDumper.IntervalVisitor;
52import org.graalvm.compiler.nodeinfo.Verbosity;
53import org.graalvm.compiler.nodes.AbstractBeginNode;
54import org.graalvm.compiler.nodes.AbstractEndNode;
55import org.graalvm.compiler.nodes.AbstractMergeNode;
56import org.graalvm.compiler.nodes.FixedNode;
57import org.graalvm.compiler.nodes.FixedWithNextNode;
58import org.graalvm.compiler.nodes.FrameState;
59import org.graalvm.compiler.nodes.PhiNode;
60import org.graalvm.compiler.nodes.StateSplit;
61import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
62import org.graalvm.compiler.nodes.ValueNode;
63import org.graalvm.compiler.nodes.ValuePhiNode;
64import org.graalvm.compiler.nodes.calc.FloatingNode;
65import org.graalvm.compiler.nodes.cfg.Block;
66import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
67
68import jdk.vm.ci.code.DebugInfo;
69import jdk.vm.ci.code.TargetDescription;
70import jdk.vm.ci.meta.JavaKind;
71import jdk.vm.ci.meta.ResolvedJavaMethod;
72import jdk.vm.ci.meta.Value;
73
74/**
75 * Utility for printing Graal IR at various compilation phases.
76 */
77class CFGPrinter extends CompilationPrinter {
78
79    protected TargetDescription target;
80    protected LIR lir;
81    protected NodeLIRBuilder nodeLirGenerator;
82    protected ControlFlowGraph cfg;
83    protected ScheduleResult schedule;
84    protected ResolvedJavaMethod method;
85
86    /**
87     * Creates a control flow graph printer.
88     *
89     * @param out where the output generated via this printer shown be written
90     */
91    CFGPrinter(OutputStream out) {
92        super(out);
93    }
94
95    /**
96     * Prints the control flow graph denoted by a given block map.
97     *
98     * @param label A label describing the compilation phase that produced the control flow graph.
99     * @param blockMap A data structure describing the blocks in a method and how they are
100     *            connected.
101     */
102    public void printCFG(String label, BciBlockMapping blockMap) {
103        begin("cfg");
104        out.print("name \"").print(label).println('"');
105        for (BciBlockMapping.BciBlock block : blockMap.getBlocks()) {
106            begin("block");
107            printBlock(block);
108            end("block");
109        }
110        end("cfg");
111    }
112
113    private void printBlock(BciBlockMapping.BciBlock block) {
114        out.print("name \"B").print(block.startBci).println('"');
115        out.print("from_bci ").println(block.startBci);
116        out.print("to_bci ").println(block.endBci);
117
118        out.println("predecessors ");
119
120        out.print("successors ");
121        for (BciBlockMapping.BciBlock succ : block.getSuccessors()) {
122            if (!succ.isExceptionEntry) {
123                out.print("\"B").print(succ.startBci).print("\" ");
124            }
125        }
126        out.println();
127
128        out.print("xhandlers");
129        for (BciBlockMapping.BciBlock succ : block.getSuccessors()) {
130            if (succ.isExceptionEntry) {
131                out.print("\"B").print(succ.startBci).print("\" ");
132            }
133        }
134        out.println();
135
136        out.print("flags ");
137        if (block.isExceptionEntry) {
138            out.print("\"ex\" ");
139        }
140        if (block.isLoopHeader) {
141            out.print("\"plh\" ");
142        }
143        out.println();
144
145        out.print("loop_depth ").println(Long.bitCount(block.loops));
146    }
147
148    private NodeMap<Block> latestScheduling;
149    private NodeBitMap printedNodes;
150
151    private boolean inFixedSchedule(Node node) {
152        return lir != null || schedule != null || node.isDeleted() || cfg.getNodeToBlock().get(node) != null;
153    }
154
155    /**
156     * Prints the specified list of blocks.
157     *
158     * @param label A label describing the compilation phase that produced the control flow graph.
159     * @param blocks The list of blocks to be printed.
160     */
161    public void printCFG(String label, AbstractBlockBase<?>[] blocks, boolean printNodes) {
162        if (lir == null) {
163            latestScheduling = new NodeMap<>(cfg.getNodeToBlock());
164            for (AbstractBlockBase<?> abstractBlock : blocks) {
165                if (abstractBlock == null) {
166                    continue;
167                }
168                Block block = (Block) abstractBlock;
169                Node cur = block.getBeginNode();
170                while (true) {
171                    assert inFixedSchedule(cur) && latestScheduling.get(cur) == block;
172                    scheduleInputs(cur, block);
173
174                    if (cur == block.getEndNode()) {
175                        break;
176                    }
177                    assert cur.successors().count() == 1;
178                    cur = cur.successors().first();
179                }
180            }
181        }
182
183        begin("cfg");
184        out.print("name \"").print(label).println('"');
185        for (AbstractBlockBase<?> block : blocks) {
186            printBlock(block, printNodes);
187        }
188        end("cfg");
189        // NOTE: we do this only because the c1visualizer does not recognize the bytecode block if
190        // it is proceeding the cfg blocks. Currently we have no direct influence on the emit order.
191        // As a workaround we dump the bytecode after every cfg.
192        if (method != null) {
193            printBytecodes(new BytecodeDisassembler(false).disassemble(method));
194        }
195
196        latestScheduling = null;
197    }
198
199    private void scheduleInputs(Node node, Block nodeBlock) {
200        if (node instanceof ValuePhiNode) {
201            PhiNode phi = (PhiNode) node;
202            Block phiBlock = latestScheduling.get(phi.merge());
203            assert phiBlock != null;
204            for (Block pred : phiBlock.getPredecessors()) {
205                schedule(phi.valueAt((AbstractEndNode) pred.getEndNode()), pred);
206            }
207
208        } else {
209            for (Node input : node.inputs()) {
210                schedule(input, nodeBlock);
211            }
212        }
213    }
214
215    private void schedule(Node input, Block block) {
216        if (!inFixedSchedule(input)) {
217            Block inputBlock = block;
218            if (latestScheduling.get(input) != null) {
219                inputBlock = AbstractControlFlowGraph.commonDominatorTyped(inputBlock, latestScheduling.get(input));
220            }
221            if (inputBlock != latestScheduling.get(input)) {
222                latestScheduling.set(input, inputBlock);
223                scheduleInputs(input, inputBlock);
224            }
225        }
226    }
227
228    private void printBlock(AbstractBlockBase<?> block, boolean printNodes) {
229        if (block == null) {
230            return;
231        }
232        printBlockProlog(block);
233        if (printNodes) {
234            assert block instanceof Block;
235            printNodes((Block) block);
236        }
237        printBlockEpilog(block);
238    }
239
240    private void printBlockEpilog(AbstractBlockBase<?> block) {
241        printLIR(block);
242        end("block");
243    }
244
245    private void printBlockProlog(AbstractBlockBase<?> block) {
246        begin("block");
247
248        out.print("name \"").print(blockToString(block)).println('"');
249        out.println("from_bci -1");
250        out.println("to_bci -1");
251
252        out.print("predecessors ");
253        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
254            out.print("\"").print(blockToString(pred)).print("\" ");
255        }
256        out.println();
257
258        out.print("successors ");
259        for (AbstractBlockBase<?> succ : block.getSuccessors()) {
260            if (!succ.isExceptionEntry()) {
261                out.print("\"").print(blockToString(succ)).print("\" ");
262            }
263        }
264        out.println();
265
266        out.print("xhandlers");
267        for (AbstractBlockBase<?> succ : block.getSuccessors()) {
268            if (succ.isExceptionEntry()) {
269                out.print("\"").print(blockToString(succ)).print("\" ");
270            }
271        }
272        out.println();
273
274        out.print("flags ");
275        if (block.isLoopHeader()) {
276            out.print("\"llh\" ");
277        }
278        if (block.isLoopEnd()) {
279            out.print("\"lle\" ");
280        }
281        if (block.isExceptionEntry()) {
282            out.print("\"ex\" ");
283        }
284        out.println();
285
286        if (block.getLoop() != null) {
287            out.print("loop_index ").println(block.getLoop().getIndex());
288            out.print("loop_depth ").println(block.getLoop().getDepth());
289        }
290
291        out.print("probability ").println(Double.doubleToRawLongBits(block.probability()));
292    }
293
294    private void printNodes(Block block) {
295        printedNodes = new NodeBitMap(cfg.graph);
296        begin("IR");
297        out.println("HIR");
298        out.disableIndentation();
299
300        if (block.getBeginNode() instanceof AbstractMergeNode) {
301            // Currently phi functions are not in the schedule, so print them separately here.
302            for (ValueNode phi : ((AbstractMergeNode) block.getBeginNode()).phis()) {
303                printNode(phi, false);
304            }
305        }
306
307        Node cur = block.getBeginNode();
308        while (true) {
309            printNode(cur, false);
310
311            if (cur == block.getEndNode()) {
312                for (Map.Entry<Node, Block> entry : latestScheduling.entries()) {
313                    if (entry.getValue() == block && !inFixedSchedule(entry.getKey()) && !printedNodes.isMarked(entry.getKey())) {
314                        printNode(entry.getKey(), true);
315                    }
316                }
317                break;
318            }
319            assert cur.successors().count() == 1;
320            cur = cur.successors().first();
321        }
322
323        out.enableIndentation();
324        end("IR");
325        printedNodes = null;
326    }
327
328    private void printNode(Node node, boolean unscheduled) {
329        assert !printedNodes.isMarked(node);
330        printedNodes.mark(node);
331
332        if (!(node instanceof ValuePhiNode)) {
333            for (Node input : node.inputs()) {
334                if (!inFixedSchedule(input) && !printedNodes.isMarked(input)) {
335                    printNode(input, true);
336                }
337            }
338        }
339
340        if (unscheduled) {
341            assert lir == null && schedule == null : "unscheduled nodes can only be present before LIR generation";
342            out.print("f ").print(HOVER_START).print("u").print(HOVER_SEP).print("unscheduled").print(HOVER_END).println(COLUMN_END);
343        } else if (node instanceof FixedWithNextNode) {
344            out.print("f ").print(HOVER_START).print("#").print(HOVER_SEP).print("fixed with next").print(HOVER_END).println(COLUMN_END);
345        } else if (node instanceof FixedNode) {
346            out.print("f ").print(HOVER_START).print("*").print(HOVER_SEP).print("fixed").print(HOVER_END).println(COLUMN_END);
347        } else if (node instanceof FloatingNode) {
348            out.print("f ").print(HOVER_START).print("~").print(HOVER_SEP).print("floating").print(HOVER_END).println(COLUMN_END);
349        }
350        out.print("tid ").print(nodeToString(node)).println(COLUMN_END);
351
352        if (nodeLirGenerator != null) {
353            Value operand = nodeLirGenerator.hasOperand(node) ? nodeLirGenerator.operand(node) : null;
354            if (operand != null) {
355                out.print("result ").print(operand.toString()).println(COLUMN_END);
356            }
357        }
358
359        if (node instanceof StateSplit) {
360            StateSplit stateSplit = (StateSplit) node;
361            if (stateSplit.stateAfter() != null) {
362                String state = stateToString(stateSplit.stateAfter());
363                out.print("st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).println(COLUMN_END);
364            }
365        }
366
367        Map<Object, Object> props = new TreeMap<>(node.getDebugProperties());
368        out.print("d ").print(HOVER_START).print("d").print(HOVER_SEP);
369        out.println("=== Debug Properties ===");
370        for (Map.Entry<Object, Object> entry : props.entrySet()) {
371            out.print(entry.getKey().toString()).print(": ").print(entry.getValue() == null ? "[null]" : entry.getValue().toString()).println();
372        }
373        out.println("=== Inputs ===");
374        printNamedNodes(node, node.inputPositions().iterator(), "", "\n", null);
375        out.println("=== Succesors ===");
376        printNamedNodes(node, node.successorPositions().iterator(), "", "\n", null);
377        out.println("=== Usages ===");
378        if (!node.hasNoUsages()) {
379            for (Node usage : node.usages()) {
380                out.print(nodeToString(usage)).print(" ");
381            }
382            out.println();
383        }
384        out.println("=== Predecessor ===");
385        out.print(nodeToString(node.predecessor())).print(" ");
386        out.print(HOVER_END).println(COLUMN_END);
387
388        out.print("instruction ");
389        out.print(HOVER_START).print(node.getNodeClass().shortName()).print(HOVER_SEP).print(node.getClass().getName()).print(HOVER_END).print(" ");
390        printNamedNodes(node, node.inputPositions().iterator(), "", "", "#NDF");
391        printNamedNodes(node, node.successorPositions().iterator(), "#", "", "#NDF");
392        for (Map.Entry<Object, Object> entry : props.entrySet()) {
393            String key = entry.getKey().toString();
394            if (key.startsWith("data.") && !key.equals("data.stamp")) {
395                out.print(key.substring("data.".length())).print(": ").print(entry.getValue() == null ? "[null]" : entry.getValue().toString()).print(" ");
396            }
397        }
398        out.print(COLUMN_END).print(' ').println(COLUMN_END);
399    }
400
401    private void printNamedNodes(Node node, Iterator<Position> iter, String prefix, String suffix, String hideSuffix) {
402        int lastIndex = -1;
403        while (iter.hasNext()) {
404            Position pos = iter.next();
405            if (hideSuffix != null && pos.getName().endsWith(hideSuffix)) {
406                continue;
407            }
408
409            if (pos.getIndex() != lastIndex) {
410                if (lastIndex != -1) {
411                    out.print(suffix);
412                }
413                out.print(prefix).print(pos.getName()).print(": ");
414                lastIndex = pos.getIndex();
415            }
416            out.print(nodeToString(pos.get(node))).print(" ");
417        }
418        if (lastIndex != -1) {
419            out.print(suffix);
420        }
421    }
422
423    private String stateToString(FrameState state) {
424        StringBuilder buf = new StringBuilder();
425        FrameState curState = state;
426        do {
427            buf.append(Bytecode.toLocation(curState.getCode(), curState.bci)).append('\n');
428
429            if (curState.stackSize() > 0) {
430                buf.append("stack: ");
431                for (int i = 0; i < curState.stackSize(); i++) {
432                    buf.append(stateValueToString(curState.stackAt(i))).append(' ');
433                }
434                buf.append("\n");
435            }
436
437            buf.append("locals: ");
438            for (int i = 0; i < curState.localsSize(); i++) {
439                buf.append(stateValueToString(curState.localAt(i))).append(' ');
440            }
441            buf.append("\n");
442
443            buf.append("locks: ");
444            for (int i = 0; i < curState.locksSize(); i++) {
445                buf.append(stateValueToString(curState.lockAt(i))).append(' ');
446            }
447            buf.append("\n");
448
449            curState = curState.outerFrameState();
450        } while (curState != null);
451
452        return buf.toString();
453    }
454
455    private String stateValueToString(ValueNode value) {
456        String result = nodeToString(value);
457        if (nodeLirGenerator != null && value != null && nodeLirGenerator.hasOperand(value)) {
458            Value operand = nodeLirGenerator.operand(value);
459            assert operand != null;
460            result += ": " + operand;
461        }
462        return result;
463    }
464
465    /**
466     * Prints the LIR for each instruction in a given block.
467     *
468     * @param block the block to print
469     */
470    private void printLIR(AbstractBlockBase<?> block) {
471        if (lir == null) {
472            return;
473        }
474        List<LIRInstruction> lirInstructions = lir.getLIRforBlock(block);
475        if (lirInstructions == null) {
476            return;
477        }
478
479        begin("IR");
480        out.println("LIR");
481
482        for (int i = 0; i < lirInstructions.size(); i++) {
483            LIRInstruction inst = lirInstructions.get(i);
484            printLIRInstruction(inst);
485        }
486        end("IR");
487    }
488
489    private void printLIRInstruction(LIRInstruction inst) {
490        if (inst == null) {
491            out.print("nr   -1 ").print(COLUMN_END).print(" instruction ").print("<deleted>").print(COLUMN_END);
492            out.println(COLUMN_END);
493        } else {
494            out.printf("nr %4d ", inst.id()).print(COLUMN_END);
495
496            final StringBuilder stateString = new StringBuilder();
497            inst.forEachState(state -> {
498                if (state.hasDebugInfo()) {
499                    DebugInfo di = state.debugInfo();
500                    stateString.append(debugInfoToString(di.getBytecodePosition(), di.getReferenceMap(), state.getLiveBasePointers(), di.getCalleeSaveInfo()));
501                } else {
502                    stateString.append(debugInfoToString(state.topFrame, null, state.getLiveBasePointers(), null));
503                }
504            });
505            if (stateString.length() > 0) {
506                int level = out.indentationLevel();
507                out.adjustIndentation(-level);
508                out.print(" st ").print(HOVER_START).print("st").print(HOVER_SEP).print(stateString.toString()).print(HOVER_END).print(COLUMN_END);
509                out.adjustIndentation(level);
510            }
511
512            out.print(" instruction ").print(inst.toString()).print(COLUMN_END);
513            out.println(COLUMN_END);
514        }
515    }
516
517    private String nodeToString(Node node) {
518        if (node == null) {
519            return "-";
520        }
521        String prefix;
522        if (node instanceof AbstractBeginNode && (lir == null && schedule == null)) {
523            prefix = "B";
524        } else if (node instanceof ValueNode) {
525            ValueNode value = (ValueNode) node;
526            if (value.getStackKind() == JavaKind.Illegal) {
527                prefix = "v";
528            } else {
529                prefix = String.valueOf(toLowerCase(value.getStackKind().getTypeChar()));
530            }
531        } else {
532            prefix = "?";
533        }
534        return prefix + node.toString(Verbosity.Id);
535    }
536
537    private String blockToString(AbstractBlockBase<?> block) {
538        if (lir == null && schedule == null && block instanceof Block) {
539            // During all the front-end phases, the block schedule is built only for the debug
540            // output.
541            // Therefore, the block numbers would be different for every CFG printed -> use the id
542            // of the first instruction.
543            return "B" + ((Block) block).getBeginNode().toString(Verbosity.Id);
544        } else {
545            // LIR instructions contain references to blocks and these blocks are printed as the
546            // blockID -> use the blockID.
547            return "B" + block.getId();
548        }
549    }
550
551    IntervalVisitor intervalVisitor = new IntervalVisitor() {
552
553        /**
554         * @return a formatted description of the operand that the C1Visualizer can handle.
555         */
556        String getFormattedOperand(Value operand) {
557            String s = operand.toString();
558            int last = s.lastIndexOf('|');
559            if (last != -1) {
560                return s.substring(0, last) + "|" + operand.getPlatformKind().getTypeChar();
561            }
562            return s;
563        }
564
565        @Override
566        public void visitIntervalStart(Value parentOperand, Value splitOperand, Value location, Value hint, String typeName) {
567            out.printf("%s %s ", getFormattedOperand(splitOperand), typeName);
568            if (location != null) {
569                out.printf("\"[%s]\"", getFormattedOperand(location));
570            } else {
571                out.printf("\"[%s]\"", getFormattedOperand(splitOperand));
572            }
573            out.printf(" %s %s ", getFormattedOperand(parentOperand), hint != null ? getFormattedOperand(hint) : -1);
574        }
575
576        @Override
577        public void visitRange(int from, int to) {
578            out.printf("[%d, %d[", from, to);
579        }
580
581        @Override
582        public void visitUsePos(int usePos, Object registerPriority) {
583            out.printf("%d %s ", usePos, registerPriority);
584        }
585
586        @Override
587        public void visitIntervalEnd(Object spillState) {
588            out.printf(" \"%s\"", spillState);
589            out.println();
590        }
591
592    };
593
594    public void printIntervals(String label, IntervalDumper intervals) {
595        begin("intervals");
596        out.println(String.format("name \"%s\"", label));
597
598        intervals.visitIntervals(intervalVisitor);
599
600        end("intervals");
601    }
602
603    public void printSchedule(String message, ScheduleResult theSchedule) {
604        schedule = theSchedule;
605        cfg = schedule.getCFG();
606        printedNodes = new NodeBitMap(cfg.graph);
607
608        begin("cfg");
609        out.print("name \"").print(message).println('"');
610        for (Block b : schedule.getCFG().getBlocks()) {
611            if (schedule.nodesFor(b) != null) {
612                printScheduledBlock(b, schedule.nodesFor(b));
613            }
614        }
615        end("cfg");
616
617        schedule = null;
618        cfg = null;
619        printedNodes = null;
620    }
621
622    private void printScheduledBlock(Block block, List<Node> nodesFor) {
623        printBlockProlog(block);
624        begin("IR");
625        out.println("HIR");
626        out.disableIndentation();
627
628        if (block.getBeginNode() instanceof AbstractMergeNode) {
629            // Currently phi functions are not in the schedule, so print them separately here.
630            for (ValueNode phi : ((AbstractMergeNode) block.getBeginNode()).phis()) {
631                printNode(phi, false);
632            }
633        }
634
635        for (Node n : nodesFor) {
636            printNode(n, false);
637        }
638
639        out.enableIndentation();
640        end("IR");
641
642        printBlockEpilog(block);
643    }
644
645    public void printTraces(String label, TraceBuilderResult traces) {
646        begin("cfg");
647        out.print("name \"").print(label).println('"');
648
649        for (Trace trace : traces.getTraces()) {
650            printTrace(trace, traces);
651        }
652
653        end("cfg");
654    }
655
656    private void printTrace(Trace trace, TraceBuilderResult traceBuilderResult) {
657        printTraceProlog(trace, traceBuilderResult);
658        printTraceInstructions(trace, traceBuilderResult);
659        printTraceEpilog();
660    }
661
662    private void printTraceProlog(Trace trace, TraceBuilderResult traceBuilderResult) {
663        begin("block");
664
665        out.print("name \"").print(traceToString(trace)).println('"');
666        out.println("from_bci -1");
667        out.println("to_bci -1");
668
669        out.print("predecessors ");
670        for (Trace pred : getPredecessors(trace, traceBuilderResult)) {
671            out.print("\"").print(traceToString(pred)).print("\" ");
672        }
673        out.println();
674
675        out.print("successors ");
676        for (Trace succ : getSuccessors(trace, traceBuilderResult)) {
677            // if (!succ.isExceptionEntry()) {
678            out.print("\"").print(traceToString(succ)).print("\" ");
679            // }
680        }
681        out.println();
682
683        out.print("xhandlers");
684        // TODO(je) add support for exception handler
685        out.println();
686
687        out.print("flags ");
688        // TODO(je) add support for flags
689        out.println();
690        // TODO(je) add support for loop infos
691    }
692
693    private void printTraceInstructions(Trace trace, TraceBuilderResult traceBuilderResult) {
694        if (lir == null) {
695            return;
696        }
697        begin("IR");
698        out.println("LIR");
699
700        for (AbstractBlockBase<?> block : trace.getBlocks()) {
701            List<LIRInstruction> lirInstructions = lir.getLIRforBlock(block);
702            if (lirInstructions == null) {
703                continue;
704            }
705            printBlockInstruction(block, traceBuilderResult);
706            for (int i = 0; i < lirInstructions.size(); i++) {
707                LIRInstruction inst = lirInstructions.get(i);
708                printLIRInstruction(inst);
709            }
710        }
711        end("IR");
712    }
713
714    private void printBlockInstruction(AbstractBlockBase<?> block, TraceBuilderResult traceBuilderResult) {
715        out.print("nr ").print(block.toString()).print(COLUMN_END).print(" instruction ");
716
717        if (block.getPredecessorCount() > 0) {
718            out.print("<- ");
719            printBlockListWithTrace(Arrays.asList(block.getPredecessors()), traceBuilderResult);
720            out.print(" ");
721        }
722        if (block.getSuccessorCount() > 0) {
723            out.print("-> ");
724            printBlockListWithTrace(Arrays.asList(block.getSuccessors()), traceBuilderResult);
725        }
726
727        out.print(COLUMN_END);
728        out.println(COLUMN_END);
729    }
730
731    private void printBlockListWithTrace(List<? extends AbstractBlockBase<?>> blocks, TraceBuilderResult traceBuilderResult) {
732        Iterator<? extends AbstractBlockBase<?>> it = blocks.iterator();
733        printBlockWithTrace(it.next(), traceBuilderResult);
734        while (it.hasNext()) {
735            out.print(",");
736            printBlockWithTrace(it.next(), traceBuilderResult);
737        }
738    }
739
740    private void printBlockWithTrace(AbstractBlockBase<?> block, TraceBuilderResult traceBuilderResult) {
741        out.print(block.toString());
742        out.print("[T").print(traceBuilderResult.getTraceForBlock(block).getId()).print("]");
743    }
744
745    private void printTraceEpilog() {
746        end("block");
747    }
748
749    private static boolean isLoopBackEdge(AbstractBlockBase<?> src, AbstractBlockBase<?> dst) {
750        return dst.isLoopHeader() && dst.getLoop().equals(src.getLoop());
751    }
752
753    private static List<Trace> getSuccessors(Trace trace, TraceBuilderResult traceBuilderResult) {
754        BitSet bs = new BitSet(traceBuilderResult.getTraces().size());
755        for (AbstractBlockBase<?> block : trace.getBlocks()) {
756            for (AbstractBlockBase<?> s : block.getSuccessors()) {
757                Trace otherTrace = traceBuilderResult.getTraceForBlock(s);
758                int otherTraceId = otherTrace.getId();
759                if (trace.getId() != otherTraceId || isLoopBackEdge(block, s)) {
760                    bs.set(otherTraceId);
761                }
762            }
763        }
764        List<Trace> succ = new ArrayList<>();
765        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
766            succ.add(traceBuilderResult.getTraces().get(i));
767        }
768        return succ;
769    }
770
771    private static List<Trace> getPredecessors(Trace trace, TraceBuilderResult traceBuilderResult) {
772        BitSet bs = new BitSet(traceBuilderResult.getTraces().size());
773        for (AbstractBlockBase<?> block : trace.getBlocks()) {
774            for (AbstractBlockBase<?> p : block.getPredecessors()) {
775                Trace otherTrace = traceBuilderResult.getTraceForBlock(p);
776                int otherTraceId = otherTrace.getId();
777                if (trace.getId() != otherTraceId || isLoopBackEdge(p, block)) {
778                    bs.set(traceBuilderResult.getTraceForBlock(p).getId());
779                }
780            }
781        }
782        List<Trace> pred = new ArrayList<>();
783        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
784            pred.add(traceBuilderResult.getTraces().get(i));
785        }
786        return pred;
787    }
788
789    private static String traceToString(Trace trace) {
790        return new StringBuilder("T").append(trace.getId()).toString();
791    }
792
793}
794