Source code

001/*
002 * Copyright (c) 2009, 2014, 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.printer;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.io.*;
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.cfg.*;
034import com.oracle.graal.compiler.gen.*;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.java.*;
037import com.oracle.graal.lir.*;
038import com.oracle.graal.lir.alloc.lsra.*;
039import com.oracle.graal.lir.alloc.lsra.Interval.UsePosList;
040import com.oracle.graal.lir.stackslotalloc.*;
041import com.oracle.graal.nodeinfo.*;
042import com.oracle.graal.nodes.*;
043import com.oracle.graal.nodes.calc.*;
044import com.oracle.graal.nodes.cfg.*;
045import com.oracle.graal.phases.schedule.*;
046
047/**
048 * Utility for printing Graal IR at various compilation phases.
049 */
050class CFGPrinter extends CompilationPrinter {
051
052    protected TargetDescription target;
053    protected LIR lir;
054    protected NodeLIRBuilder nodeLirGenerator;
055    protected ControlFlowGraph cfg;
056    protected SchedulePhase schedule;
057    protected ResolvedJavaMethod method;
058
059    /**
060     * Creates a control flow graph printer.
061     *
062     * @param out where the output generated via this printer shown be written
063     */
064    public CFGPrinter(OutputStream out) {
065        super(out);
066    }
067
068    /**
069     * Prints the control flow graph denoted by a given block map.
070     *
071     * @param label A label describing the compilation phase that produced the control flow graph.
072     * @param blockMap A data structure describing the blocks in a method and how they are
073     *            connected.
074     */
075    public void printCFG(String label, BciBlockMapping blockMap) {
076        begin("cfg");
077        out.print("name \"").print(label).println('"');
078        for (BciBlockMapping.BciBlock block : blockMap.getBlocks()) {
079            begin("block");
080            printBlock(block);
081            end("block");
082        }
083        end("cfg");
084    }
085
086    private void printBlock(BciBlockMapping.BciBlock block) {
087        out.print("name \"B").print(block.startBci).println('"');
088        out.print("from_bci ").println(block.startBci);
089        out.print("to_bci ").println(block.endBci);
090
091        out.println("predecessors ");
092
093        out.print("successors ");
094        for (BciBlockMapping.BciBlock succ : block.getSuccessors()) {
095            if (!succ.isExceptionEntry) {
096                out.print("\"B").print(succ.startBci).print("\" ");
097            }
098        }
099        out.println();
100
101        out.print("xhandlers");
102        for (BciBlockMapping.BciBlock succ : block.getSuccessors()) {
103            if (succ.isExceptionEntry) {
104                out.print("\"B").print(succ.startBci).print("\" ");
105            }
106        }
107        out.println();
108
109        out.print("flags ");
110        if (block.isExceptionEntry) {
111            out.print("\"ex\" ");
112        }
113        if (block.isLoopHeader) {
114            out.print("\"plh\" ");
115        }
116        out.println();
117
118        out.print("loop_depth ").println(Long.bitCount(block.loops));
119    }
120
121    private NodeMap<Block> latestScheduling;
122    private NodeBitMap printedNodes;
123
124    private boolean inFixedSchedule(Node node) {
125        return lir != null || schedule != null || node.isDeleted() || cfg.getNodeToBlock().get(node) != null;
126    }
127
128    /**
129     * Prints the specified list of blocks.
130     *
131     * @param label A label describing the compilation phase that produced the control flow graph.
132     * @param blocks The list of blocks to be printed.
133     */
134    public void printCFG(String label, List<? extends AbstractBlockBase<?>> blocks, boolean printNodes) {
135        if (lir == null) {
136            latestScheduling = new NodeMap<>(cfg.getNodeToBlock());
137            for (AbstractBlockBase<?> abstractBlock : blocks) {
138                Block block = (Block) abstractBlock;
139                Node cur = block.getBeginNode();
140                while (true) {
141                    assert inFixedSchedule(cur) && latestScheduling.get(cur) == block;
142                    scheduleInputs(cur, block);
143
144                    if (cur == block.getEndNode()) {
145                        break;
146                    }
147                    assert cur.successors().count() == 1;
148                    cur = cur.successors().first();
149                }
150            }
151        }
152
153        begin("cfg");
154        out.print("name \"").print(label).println('"');
155        for (AbstractBlockBase<?> block : blocks) {
156            printBlock(block, printNodes);
157        }
158        end("cfg");
159        // NOTE: we do this only because the c1visualizer does not recognize the bytecode block if
160        // it is proceeding the cfg blocks. Currently we have no direct influence on the emit order.
161        // As a workaround we dump the bytecode after every cfg.
162        if (method != null) {
163            printBytecodes(new BytecodeDisassembler(false).disassemble(method));
164        }
165
166        latestScheduling = null;
167    }
168
169    private void scheduleInputs(Node node, Block nodeBlock) {
170        if (node instanceof ValuePhiNode) {
171            PhiNode phi = (PhiNode) node;
172            assert nodeBlock.getBeginNode() == phi.merge();
173            for (Block pred : nodeBlock.getPredecessors()) {
174                schedule(phi.valueAt((AbstractEndNode) pred.getEndNode()), pred);
175            }
176
177        } else {
178            for (Node input : node.inputs()) {
179                schedule(input, nodeBlock);
180            }
181        }
182    }
183
184    private void schedule(Node input, Block block) {
185        if (!inFixedSchedule(input)) {
186            Block inputBlock = block;
187            if (latestScheduling.get(input) != null) {
188                inputBlock = AbstractControlFlowGraph.commonDominatorTyped(inputBlock, latestScheduling.get(input));
189            }
190            if (inputBlock != latestScheduling.get(input)) {
191                latestScheduling.set(input, inputBlock);
192                scheduleInputs(input, inputBlock);
193            }
194        }
195    }
196
197    private void printBlock(AbstractBlockBase<?> block, boolean printNodes) {
198        printBlockProlog(block);
199        if (printNodes) {
200            assert block instanceof Block;
201            printNodes((Block) block);
202        }
203        printBlockEpilog(block);
204    }
205
206    private void printBlockEpilog(AbstractBlockBase<?> block) {
207        printLIR(block);
208        end("block");
209    }
210
211    private void printBlockProlog(AbstractBlockBase<?> block) {
212        begin("block");
213
214        out.print("name \"").print(blockToString(block)).println('"');
215        out.println("from_bci -1");
216        out.println("to_bci -1");
217
218        out.print("predecessors ");
219        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
220            out.print("\"").print(blockToString(pred)).print("\" ");
221        }
222        out.println();
223
224        out.print("successors ");
225        for (AbstractBlockBase<?> succ : block.getSuccessors()) {
226            if (!succ.isExceptionEntry()) {
227                out.print("\"").print(blockToString(succ)).print("\" ");
228            }
229        }
230        out.println();
231
232        out.print("xhandlers");
233        for (AbstractBlockBase<?> succ : block.getSuccessors()) {
234            if (succ.isExceptionEntry()) {
235                out.print("\"").print(blockToString(succ)).print("\" ");
236            }
237        }
238        out.println();
239
240        out.print("flags ");
241        if (block.isLoopHeader()) {
242            out.print("\"llh\" ");
243        }
244        if (block.isLoopEnd()) {
245            out.print("\"lle\" ");
246        }
247        if (block.isExceptionEntry()) {
248            out.print("\"ex\" ");
249        }
250        out.println();
251
252        if (block.getLoop() != null) {
253            out.print("loop_index ").println(block.getLoop().getIndex());
254            out.print("loop_depth ").println(block.getLoop().getDepth());
255        }
256    }
257
258    private void printNodes(Block block) {
259        printedNodes = new NodeBitMap(cfg.graph);
260        begin("IR");
261        out.println("HIR");
262        out.disableIndentation();
263
264        if (block.getBeginNode() instanceof AbstractMergeNode) {
265            // Currently phi functions are not in the schedule, so print them separately here.
266            for (ValueNode phi : ((AbstractMergeNode) block.getBeginNode()).phis()) {
267                printNode(phi, false);
268            }
269        }
270
271        Node cur = block.getBeginNode();
272        while (true) {
273            printNode(cur, false);
274
275            if (cur == block.getEndNode()) {
276                for (Map.Entry<Node, Block> entry : latestScheduling.entries()) {
277                    if (entry.getValue() == block && !inFixedSchedule(entry.getKey()) && !printedNodes.isMarked(entry.getKey())) {
278                        printNode(entry.getKey(), true);
279                    }
280                }
281                break;
282            }
283            assert cur.successors().count() == 1;
284            cur = cur.successors().first();
285        }
286
287        out.enableIndentation();
288        end("IR");
289        printedNodes = null;
290    }
291
292    private void printNode(Node node, boolean unscheduled) {
293        assert !printedNodes.isMarked(node);
294        printedNodes.mark(node);
295
296        if (!(node instanceof ValuePhiNode)) {
297            for (Node input : node.inputs()) {
298                if (!inFixedSchedule(input) && !printedNodes.isMarked(input)) {
299                    printNode(input, true);
300                }
301            }
302        }
303
304        if (unscheduled) {
305            assert lir == null && schedule == null : "unscheduled nodes can only be present before LIR generation";
306            out.print("f ").print(HOVER_START).print("u").print(HOVER_SEP).print("unscheduled").print(HOVER_END).println(COLUMN_END);
307        } else if (node instanceof FixedWithNextNode) {
308            out.print("f ").print(HOVER_START).print("#").print(HOVER_SEP).print("fixed with next").print(HOVER_END).println(COLUMN_END);
309        } else if (node instanceof FixedNode) {
310            out.print("f ").print(HOVER_START).print("*").print(HOVER_SEP).print("fixed").print(HOVER_END).println(COLUMN_END);
311        } else if (node instanceof FloatingNode) {
312            out.print("f ").print(HOVER_START).print("~").print(HOVER_SEP).print("floating").print(HOVER_END).println(COLUMN_END);
313        }
314        out.print("tid ").print(nodeToString(node)).println(COLUMN_END);
315
316        if (nodeLirGenerator != null) {
317            Value operand = nodeLirGenerator.hasOperand(node) ? nodeLirGenerator.operand(node) : null;
318            if (operand != null) {
319                out.print("result ").print(operand.toString()).println(COLUMN_END);
320            }
321        }
322
323        if (node instanceof StateSplit) {
324            StateSplit stateSplit = (StateSplit) node;
325            if (stateSplit.stateAfter() != null) {
326                String state = stateToString(stateSplit.stateAfter());
327                out.print("st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).println(COLUMN_END);
328            }
329        }
330
331        Map<Object, Object> props = new TreeMap<>(node.getDebugProperties());
332        out.print("d ").print(HOVER_START).print("d").print(HOVER_SEP);
333        out.println("=== Debug Properties ===");
334        for (Map.Entry<Object, Object> entry : props.entrySet()) {
335            out.print(entry.getKey().toString()).print(": ").print(entry.getValue() == null ? "[null]" : entry.getValue().toString()).println();
336        }
337        out.println("=== Inputs ===");
338        printNamedNodes(node, node.inputs().iterator(), "", "\n", null);
339        out.println("=== Succesors ===");
340        printNamedNodes(node, node.successors().iterator(), "", "\n", null);
341        out.println("=== Usages ===");
342        if (!node.hasNoUsages()) {
343            for (Node usage : node.usages()) {
344                out.print(nodeToString(usage)).print(" ");
345            }
346            out.println();
347        }
348        out.println("=== Predecessor ===");
349        out.print(nodeToString(node.predecessor())).print(" ");
350        out.print(HOVER_END).println(COLUMN_END);
351
352        out.print("instruction ");
353        out.print(HOVER_START).print(node.getNodeClass().shortName()).print(HOVER_SEP).print(node.getClass().getName()).print(HOVER_END).print(" ");
354        printNamedNodes(node, node.inputs().iterator(), "", "", "#NDF");
355        printNamedNodes(node, node.successors().iterator(), "#", "", "#NDF");
356        for (Map.Entry<Object, Object> entry : props.entrySet()) {
357            String key = entry.getKey().toString();
358            if (key.startsWith("data.") && !key.equals("data.stamp")) {
359                out.print(key.substring("data.".length())).print(": ").print(entry.getValue() == null ? "[null]" : entry.getValue().toString()).print(" ");
360            }
361        }
362        out.print(COLUMN_END).print(' ').println(COLUMN_END);
363    }
364
365    private void printNamedNodes(Node node, NodePosIterator iter, String prefix, String suffix, String hideSuffix) {
366        int lastIndex = -1;
367        while (iter.hasNext()) {
368            Position pos = iter.nextPosition();
369            if (hideSuffix != null && pos.getName().endsWith(hideSuffix)) {
370                continue;
371            }
372
373            if (pos.getIndex() != lastIndex) {
374                if (lastIndex != -1) {
375                    out.print(suffix);
376                }
377                out.print(prefix).print(pos.getName()).print(": ");
378                lastIndex = pos.getIndex();
379            }
380            out.print(nodeToString(pos.get(node))).print(" ");
381        }
382        if (lastIndex != -1) {
383            out.print(suffix);
384        }
385    }
386
387    private String stateToString(FrameState state) {
388        StringBuilder buf = new StringBuilder();
389        FrameState curState = state;
390        do {
391            buf.append(MetaUtil.toLocation(curState.method(), curState.bci)).append('\n');
392
393            if (curState.stackSize() > 0) {
394                buf.append("stack: ");
395                for (int i = 0; i < curState.stackSize(); i++) {
396                    buf.append(stateValueToString(curState.stackAt(i))).append(' ');
397                }
398                buf.append("\n");
399            }
400
401            buf.append("locals: ");
402            for (int i = 0; i < curState.localsSize(); i++) {
403                buf.append(stateValueToString(curState.localAt(i))).append(' ');
404            }
405            buf.append("\n");
406
407            buf.append("locks: ");
408            for (int i = 0; i < curState.locksSize(); i++) {
409                buf.append(stateValueToString(curState.lockAt(i))).append(' ');
410            }
411            buf.append("\n");
412
413            curState = curState.outerFrameState();
414        } while (curState != null);
415
416        return buf.toString();
417    }
418
419    private String stateValueToString(ValueNode value) {
420        String result = nodeToString(value);
421        if (nodeLirGenerator != null && value != null && nodeLirGenerator.hasOperand(value)) {
422            Value operand = nodeLirGenerator.operand(value);
423            assert operand != null;
424            result += ": " + operand;
425        }
426        return result;
427    }
428
429    /**
430     * Prints the LIR for each instruction in a given block.
431     *
432     * @param block the block to print
433     */
434    private void printLIR(AbstractBlockBase<?> block) {
435        if (lir == null) {
436            return;
437        }
438        List<LIRInstruction> lirInstructions = lir.getLIRforBlock(block);
439        if (lirInstructions == null) {
440            return;
441        }
442
443        begin("IR");
444        out.println("LIR");
445
446        for (int i = 0; i < lirInstructions.size(); i++) {
447            LIRInstruction inst = lirInstructions.get(i);
448            if (inst == null) {
449                out.print("nr   -1 ").print(COLUMN_END).print(" instruction ").print("<deleted>").print(COLUMN_END);
450                out.println(COLUMN_END);
451            } else {
452                out.printf("nr %4d ", inst.id()).print(COLUMN_END);
453
454                final StringBuilder stateString = new StringBuilder();
455                inst.forEachState(state -> {
456                    if (state.hasDebugInfo()) {
457                        DebugInfo di = state.debugInfo();
458                        stateString.append(debugInfoToString(di.getBytecodePosition(), di.getReferenceMap(), state.getLiveBasePointers(), di.getCalleeSaveInfo()));
459                    } else {
460                        stateString.append(debugInfoToString(state.topFrame, null, state.getLiveBasePointers(), null));
461                    }
462                });
463                if (stateString.length() > 0) {
464                    int level = out.indentationLevel();
465                    out.adjustIndentation(-level);
466                    out.print(" st ").print(HOVER_START).print("st").print(HOVER_SEP).print(stateString.toString()).print(HOVER_END).print(COLUMN_END);
467                    out.adjustIndentation(level);
468                }
469
470                out.print(" instruction ").print(inst.toString()).print(COLUMN_END);
471                out.println(COLUMN_END);
472            }
473        }
474        end("IR");
475    }
476
477    private String nodeToString(Node node) {
478        if (node == null) {
479            return "-";
480        }
481        String prefix;
482        if (node instanceof AbstractBeginNode && (lir == null && schedule == null)) {
483            prefix = "B";
484        } else if (node instanceof ValueNode) {
485            ValueNode value = (ValueNode) node;
486            if (value.getKind() == Kind.Illegal) {
487                prefix = "v";
488            } else {
489                prefix = String.valueOf(value.getKind().getTypeChar());
490            }
491        } else {
492            prefix = "?";
493        }
494        return prefix + node.toString(Verbosity.Id);
495    }
496
497    private String blockToString(AbstractBlockBase<?> block) {
498        if (lir == null && schedule == null && block instanceof Block) {
499            // During all the front-end phases, the block schedule is built only for the debug
500            // output.
501            // Therefore, the block numbers would be different for every CFG printed -> use the id
502            // of the first instruction.
503            return "B" + ((Block) block).getBeginNode().toString(Verbosity.Id);
504        } else {
505            // LIR instructions contain references to blocks and these blocks are printed as the
506            // blockID -> use the blockID.
507            return "B" + block.getId();
508        }
509    }
510
511    public void printIntervals(String label, Interval[] intervals) {
512        begin("intervals");
513        out.println(String.format("name \"%s\"", label));
514
515        for (Interval interval : intervals) {
516            if (interval != null) {
517                printInterval(interval);
518            }
519        }
520
521        end("intervals");
522    }
523
524    private void printInterval(Interval interval) {
525        out.printf("%s %s ", interval.operand, (isRegister(interval.operand) ? "fixed" : interval.kind().getPlatformKind()));
526        if (isRegister(interval.operand)) {
527            out.printf("\"[%s|%c]\"", interval.operand, interval.operand.getKind().getTypeChar());
528        } else {
529            if (interval.location() != null) {
530                out.printf("\"[%s|%c]\"", interval.location(), interval.location().getKind().getTypeChar());
531            }
532        }
533
534        Interval hint = interval.locationHint(false);
535        out.printf("%s %s ", interval.splitParent().operand, hint != null ? hint.operand : -1);
536
537        // print ranges
538        Range cur = interval.first();
539        while (cur != Range.EndMarker) {
540            out.printf("[%d, %d[", cur.from, cur.to);
541            cur = cur.next;
542            assert cur != null : "range list not closed with range sentinel";
543        }
544
545        // print use positions
546        int prev = -1;
547        UsePosList usePosList = interval.usePosList();
548        for (int i = usePosList.size() - 1; i >= 0; --i) {
549            assert prev < usePosList.usePos(i) : "use positions not sorted";
550            out.printf("%d %s ", usePosList.usePos(i), usePosList.registerPriority(i));
551            prev = usePosList.usePos(i);
552        }
553
554        out.printf(" \"%s\"", interval.spillState());
555        out.println();
556    }
557
558    public void printStackIntervals(String label, StackInterval[] intervals) {
559        begin("intervals");
560        out.println(String.format("name \"%s\"", label));
561
562        for (StackInterval interval : intervals) {
563            if (interval != null) {
564                printStackInterval(interval);
565            }
566        }
567
568        end("intervals");
569    }
570
571    private void printStackInterval(StackInterval interval) {
572        out.printf("%s %s ", interval.getOperand(), interval.isFixed() ? "fixed" : interval.kind().getPlatformKind());
573        if (interval.location() != null) {
574            out.printf("\"[%s|%c]\"", interval.location(), interval.location().getKind().getTypeChar());
575        } else {
576            out.printf("\"[%s|%c]\"", interval.getOperand(), interval.getOperand().getKind().getTypeChar());
577        }
578
579        StackInterval hint = interval.locationHint();
580        out.printf("%s %s ", interval.getOperand(), hint != null ? hint.getOperand() : -1);
581
582        out.printf("[%d, %d[", interval.from(), interval.to());
583
584        // print spill state
585        out.printf(" \"NOT_SUPPORTED\"");
586        out.println();
587    }
588
589    public void printSchedule(String message, SchedulePhase theSchedule) {
590        schedule = theSchedule;
591        cfg = schedule.getCFG();
592        printedNodes = new NodeBitMap(cfg.graph);
593
594        begin("cfg");
595        out.print("name \"").print(message).println('"');
596        for (Block b : schedule.getCFG().getBlocks()) {
597            if (schedule.nodesFor(b) != null) {
598                printScheduledBlock(b, schedule.nodesFor(b));
599            }
600        }
601        end("cfg");
602
603        schedule = null;
604        cfg = null;
605        printedNodes = null;
606    }
607
608    private void printScheduledBlock(Block block, List<Node> nodesFor) {
609        printBlockProlog(block);
610        begin("IR");
611        out.println("HIR");
612        out.disableIndentation();
613
614        if (block.getBeginNode() instanceof AbstractMergeNode) {
615            // Currently phi functions are not in the schedule, so print them separately here.
616            for (ValueNode phi : ((AbstractMergeNode) block.getBeginNode()).phis()) {
617                printNode(phi, false);
618            }
619        }
620
621        for (Node n : nodesFor) {
622            printNode(n, false);
623        }
624
625        out.enableIndentation();
626        end("IR");
627
628        printBlockEpilog(block);
629    }
630}