/* Output routines for graphical representation.
- Copyright (C) 1998, 1999, 2000, 2001, 2003, 2004
- Free Software Foundation, Inc.
+ Copyright (C) 1998-2014 Free Software Foundation, Inc.
Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
+ Rewritten for DOT output by Steven Bosscher, 2012.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
-#include <config.h>
+#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "diagnostic-core.h" /* for fatal_error */
+#include "sbitmap.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
#include "tm.h"
-#include "rtl.h"
-#include "flags.h"
-#include "output.h"
-#include "function.h"
#include "hard-reg-set.h"
-#include "obstack.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
-#include "toplev.h"
+#include "cfgloop.h"
#include "graph.h"
-
-static const char *const graph_ext[] =
+#include "dumpfile.h"
+#include "pretty-print.h"
+
+/* DOT files with the .dot extension are recognized as document templates
+ by a well-known piece of word processing software out of Redmond, WA.
+ Therefore some recommend using the .gv extension instead. Obstinately
+ ignore that recommendation... */
+static const char *const graph_ext = ".dot";
+
+/* Open a file with MODE for dumping our graph to.
+ Return the file pointer. */
+static FILE *
+open_graph_file (const char *base, const char *mode)
{
- /* no_graph */ "",
- /* vcg */ ".vcg",
-};
-
-static void start_fct (FILE *);
-static void start_bb (FILE *, int);
-static void node_data (FILE *, rtx);
-static void draw_edge (FILE *, int, int, int, int);
-static void end_fct (FILE *);
-static void end_bb (FILE *);
-
-/* Output text for new basic block. */
-static void
-start_fct (FILE *fp)
-{
- switch (graph_dump_format)
- {
- case vcg:
- fprintf (fp, "\
-graph: { title: \"%s\"\nfolding: 1\nhidden: 2\nnode: { title: \"%s.0\" }\n",
- current_function_name (), current_function_name ());
- break;
- case no_graph:
- break;
- }
+ size_t namelen = strlen (base);
+ size_t extlen = strlen (graph_ext) + 1;
+ char *buf = XALLOCAVEC (char, namelen + extlen);
+ FILE *fp;
+
+ memcpy (buf, base, namelen);
+ memcpy (buf + namelen, graph_ext, extlen);
+
+ fp = fopen (buf, mode);
+ if (fp == NULL)
+ fatal_error ("can%'t open %s: %m", buf);
+
+ return fp;
}
+/* Draw a basic block BB belonging to the function with FUNCDEF_NO
+ as its unique number. */
static void
-start_bb (FILE *fp, int bb)
+draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
{
-#if 0
- reg_set_iterator rsi;
-#endif
+ const char *shape;
+ const char *fillcolor;
- switch (graph_dump_format)
+ if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
{
- case vcg:
- fprintf (fp, "\
-graph: {\ntitle: \"%s.BB%d\"\nfolding: 1\ncolor: lightblue\n\
-label: \"basic block %d",
- current_function_name (), bb, bb);
- break;
- case no_graph:
- break;
+ shape = "Mdiamond";
+ fillcolor = "white";
}
-
-#if 0
- /* FIXME Should this be printed? It makes the graph significantly larger. */
-
- /* Print the live-at-start register list. */
- fputc ('\n', fp);
- EXECUTE_IF_SET_IN_REG_SET (basic_block_live_at_start[bb], 0, i, rsi)
+ else
{
- fprintf (fp, " %d", i);
- if (i < FIRST_PSEUDO_REGISTER)
- fprintf (fp, " [%s]", reg_names[i]);
+ shape = "record";
+ fillcolor =
+ BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
+ : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
+ : "lightgrey";
}
-#endif
- switch (graph_dump_format)
+ pp_printf (pp,
+ "\tfn_%d_basic_block_%d "
+ "[shape=%s,style=filled,fillcolor=%s,label=\"",
+ funcdef_no, bb->index, shape, fillcolor);
+
+ if (bb->index == ENTRY_BLOCK)
+ pp_string (pp, "ENTRY");
+ else if (bb->index == EXIT_BLOCK)
+ pp_string (pp, "EXIT");
+ else
{
- case vcg:
- fputs ("\"\n\n", fp);
- break;
- case no_graph:
- break;
+ pp_left_brace (pp);
+ pp_write_text_to_stream (pp);
+ dump_bb_for_graph (pp, bb);
+ pp_right_brace (pp);
}
+
+ pp_string (pp, "\"];\n\n");
+ pp_flush (pp);
}
+/* Draw all successor edges of a basic block BB belonging to the function
+ with FUNCDEF_NO as its unique number. */
static void
-node_data (FILE *fp, rtx tmp_rtx)
+draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
{
- if (PREV_INSN (tmp_rtx) == 0)
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- /* This is the first instruction. Add an edge from the starting
- block. */
- switch (graph_dump_format)
+ const char *style = "\"solid,bold\"";
+ const char *color = "black";
+ int weight = 10;
+
+ if (e->flags & EDGE_FAKE)
{
- case vcg:
- fprintf (fp, "\
-edge: { sourcename: \"%s.0\" targetname: \"%s.%d\" }\n",
- current_function_name (),
- current_function_name (), XINT (tmp_rtx, 0));
- break;
- case no_graph:
- break;
+ style = "dotted";
+ color = "green";
+ weight = 0;
+ }
+ else if (e->flags & EDGE_DFS_BACK)
+ {
+ style = "\"dotted,bold\"";
+ color = "blue";
+ weight = 10;
+ }
+ else if (e->flags & EDGE_FALLTHRU)
+ {
+ color = "blue";
+ weight = 100;
}
- }
-
- switch (graph_dump_format)
- {
- case vcg:
- fprintf (fp, "node: {\n title: \"%s.%d\"\n color: %s\n \
-label: \"%s %d\n",
- current_function_name (), XINT (tmp_rtx, 0),
- NOTE_P (tmp_rtx) ? "lightgrey"
- : NONJUMP_INSN_P (tmp_rtx) ? "green"
- : JUMP_P (tmp_rtx) ? "darkgreen"
- : CALL_P (tmp_rtx) ? "darkgreen"
- : LABEL_P (tmp_rtx) ? "\
-darkgrey\n shape: ellipse" : "white",
- GET_RTX_NAME (GET_CODE (tmp_rtx)), XINT (tmp_rtx, 0));
- break;
- case no_graph:
- break;
- }
-
- /* Print the RTL. */
- if (NOTE_P (tmp_rtx))
- {
- const char *name = "";
- if (NOTE_LINE_NUMBER (tmp_rtx) < 0)
- name = GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (tmp_rtx));
- fprintf (fp, " %s", name);
- }
- else if (INSN_P (tmp_rtx))
- print_rtl_single (fp, PATTERN (tmp_rtx));
- else
- print_rtl_single (fp, tmp_rtx);
- switch (graph_dump_format)
- {
- case vcg:
- fputs ("\"\n}\n", fp);
- break;
- case no_graph:
- break;
+ if (e->flags & EDGE_ABNORMAL)
+ color = "red";
+
+ pp_printf (pp,
+ "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
+ "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
+ funcdef_no, e->src->index,
+ funcdef_no, e->dest->index,
+ style, color, weight,
+ (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
+ e->probability * 100 / REG_BR_PROB_BASE);
}
+ pp_flush (pp);
}
-static void
-draw_edge (FILE *fp, int from, int to, int bb_edge, int class)
-{
- const char * color;
- switch (graph_dump_format)
- {
- case vcg:
- color = "";
- if (class == 2)
- color = "color: red ";
- else if (bb_edge)
- color = "color: blue ";
- else if (class == 3)
- color = "color: green ";
- fprintf (fp,
- "edge: { sourcename: \"%s.%d\" targetname: \"%s.%d\" %s",
- current_function_name (), from,
- current_function_name (), to, color);
- if (class)
- fprintf (fp, "class: %d ", class);
- fputs ("}\n", fp);
- break;
- case no_graph:
- break;
- }
-}
+/* Draw all the basic blocks in the CFG in case loops are not available.
+ First compute a topological order of the blocks to get a good ranking of
+ the nodes. Then, if any nodes are not reachable from ENTRY, add them at
+ the end. */
static void
-end_bb (FILE *fp)
+draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
{
- switch (graph_dump_format)
+ int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
+ int i, n;
+ sbitmap visited;
+
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ bitmap_clear (visited);
+
+ n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
+ for (i = n_basic_blocks_for_fn (fun) - n;
+ i < n_basic_blocks_for_fn (fun); i++)
{
- case vcg:
- fputs ("}\n", fp);
- break;
- case no_graph:
- break;
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
+ draw_cfg_node (pp, fun->funcdef_no, bb);
+ bitmap_set_bit (visited, bb->index);
}
-}
+ free (rpo);
-static void
-end_fct (FILE *fp)
-{
- switch (graph_dump_format)
+ if (n != n_basic_blocks_for_fn (fun))
{
- case vcg:
- fprintf (fp, "node: { title: \"%s.999999\" label: \"END\" }\n}\n",
- current_function_name ());
- break;
- case no_graph:
- break;
+ /* Some blocks are unreachable. We still want to dump them. */
+ basic_block bb;
+ FOR_ALL_BB_FN (bb, fun)
+ if (! bitmap_bit_p (visited, bb->index))
+ draw_cfg_node (pp, fun->funcdef_no, bb);
}
-}
-\f
-/* Like print_rtl, but also print out live information for the start of each
- basic block. */
-void
-print_rtl_graph_with_bb (const char *base, rtx rtx_first)
-{
- rtx tmp_rtx;
- size_t namelen = strlen (base);
- size_t extlen = strlen (graph_ext[graph_dump_format]) + 1;
- char *buf = alloca (namelen + extlen);
- FILE *fp;
- if (basic_block_info == NULL)
- return;
+ sbitmap_free (visited);
+}
- memcpy (buf, base, namelen);
- memcpy (buf + namelen, graph_ext[graph_dump_format], extlen);
+/* Draw all the basic blocks in LOOP. Print the blocks in breath-first
+ order to get a good ranking of the nodes. This function is recursive:
+ It first prints inner loops, then the body of LOOP itself. */
- fp = fopen (buf, "a");
- if (fp == NULL)
+static void
+draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
+ struct loop *loop)
+{
+ basic_block *body;
+ unsigned int i;
+ const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
+
+ if (loop->header != NULL
+ && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
+ pp_printf (pp,
+ "\tsubgraph cluster_%d_%d {\n"
+ "\tstyle=\"filled\";\n"
+ "\tcolor=\"darkgreen\";\n"
+ "\tfillcolor=\"%s\";\n"
+ "\tlabel=\"loop %d\";\n"
+ "\tlabeljust=l;\n"
+ "\tpenwidth=2;\n",
+ funcdef_no, loop->num,
+ fillcolors[(loop_depth (loop) - 1) % 3],
+ loop->num);
+
+ for (struct loop *inner = loop->inner; inner; inner = inner->next)
+ draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
+
+ if (loop->header == NULL)
return;
- if (rtx_first == 0)
- fprintf (fp, "(nil)\n");
+ if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
+ body = get_loop_body (loop);
else
- {
- enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
- int max_uid = get_max_uid ();
- int *start = xmalloc (max_uid * sizeof (int));
- int *end = xmalloc (max_uid * sizeof (int));
- enum bb_state *in_bb_p = xmalloc (max_uid * sizeof (enum bb_state));
- basic_block bb;
- int i;
+ body = get_loop_body_in_bfs_order (loop);
- for (i = 0; i < max_uid; ++i)
- {
- start[i] = end[i] = -1;
- in_bb_p[i] = NOT_IN_BB;
- }
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = body[i];
+ if (bb->loop_father == loop)
+ draw_cfg_node (pp, funcdef_no, bb);
+ }
- FOR_EACH_BB_REVERSE (bb)
- {
- rtx x;
- start[INSN_UID (BB_HEAD (bb))] = bb->index;
- end[INSN_UID (BB_END (bb))] = bb->index;
- for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
- {
- in_bb_p[INSN_UID (x)]
- = (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
- ? IN_ONE_BB : IN_MULTIPLE_BB;
- if (x == BB_END (bb))
- break;
- }
- }
+ free (body);
- /* Tell print-rtl that we want graph output. */
- dump_for_graph = 1;
+ if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
+ pp_printf (pp, "\t}\n");
+}
- /* Start new function. */
- start_fct (fp);
+/* Draw all the basic blocks in the CFG in case the loop tree is available.
+ All loop bodys are printed in clusters. */
- for (tmp_rtx = NEXT_INSN (rtx_first); NULL != tmp_rtx;
- tmp_rtx = NEXT_INSN (tmp_rtx))
- {
- int edge_printed = 0;
- rtx next_insn;
-
- if (start[INSN_UID (tmp_rtx)] < 0 && end[INSN_UID (tmp_rtx)] < 0)
- {
- if (BARRIER_P (tmp_rtx))
- continue;
- if (NOTE_P (tmp_rtx)
- && (1 || in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB))
- continue;
- }
-
- if ((i = start[INSN_UID (tmp_rtx)]) >= 0)
- {
- /* We start a subgraph for each basic block. */
- start_bb (fp, i);
-
- if (i == 0)
- draw_edge (fp, 0, INSN_UID (tmp_rtx), 1, 0);
- }
-
- /* Print the data for this node. */
- node_data (fp, tmp_rtx);
- next_insn = next_nonnote_insn (tmp_rtx);
-
- if ((i = end[INSN_UID (tmp_rtx)]) >= 0)
- {
- edge e;
- edge_iterator ei;
-
- bb = BASIC_BLOCK (i);
-
- /* End of the basic block. */
- end_bb (fp);
-
- /* Now specify the edges to all the successors of this
- basic block. */
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- if (e->dest != EXIT_BLOCK_PTR)
- {
- rtx block_head = BB_HEAD (e->dest);
-
- draw_edge (fp, INSN_UID (tmp_rtx),
- INSN_UID (block_head),
- next_insn != block_head,
- (e->flags & EDGE_ABNORMAL ? 2 : 0));
-
- if (block_head == next_insn)
- edge_printed = 1;
- }
- else
- {
- draw_edge (fp, INSN_UID (tmp_rtx), 999999,
- next_insn != 0,
- (e->flags & EDGE_ABNORMAL ? 2 : 0));
-
- if (next_insn == 0)
- edge_printed = 1;
- }
- }
- }
-
- if (!edge_printed)
- {
- /* Don't print edges to barriers. */
- if (next_insn == 0
- || !BARRIER_P (next_insn))
- draw_edge (fp, XINT (tmp_rtx, 0),
- next_insn ? INSN_UID (next_insn) : 999999, 0, 0);
- else
- {
- /* We draw the remaining edges in class 3. We have
- to skip over the barrier since these nodes are
- not printed at all. */
- do
- next_insn = NEXT_INSN (next_insn);
- while (next_insn
- && (NOTE_P (next_insn)
- || BARRIER_P (next_insn)));
-
- draw_edge (fp, XINT (tmp_rtx, 0),
- next_insn ? INSN_UID (next_insn) : 999999, 0, 3);
- }
- }
- }
+static void
+draw_cfg_nodes (pretty_printer *pp, struct function *fun)
+{
+ if (loops_for_fn (fun))
+ draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
+ else
+ draw_cfg_nodes_no_loops (pp, fun);
+}
- dump_for_graph = 0;
+/* Draw all edges in the CFG. Retreating edges are drawin as not
+ constraining, this makes the layout of the graph better.
+ (??? Calling mark_dfs_back may change the compiler's behavior when
+ dumping, but computing back edges here for ourselves is also not
+ desirable.) */
- end_fct (fp);
+static void
+draw_cfg_edges (pretty_printer *pp, struct function *fun)
+{
+ basic_block bb;
+ mark_dfs_back_edges ();
+ FOR_ALL_BB_FN (bb, cfun)
+ draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
+
+ /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
+ pp_printf (pp,
+ "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
+ "[style=\"invis\",constraint=true];\n",
+ fun->funcdef_no, ENTRY_BLOCK,
+ fun->funcdef_no, EXIT_BLOCK);
+ pp_flush (pp);
+}
- /* Clean up. */
- free (start);
- free (end);
- free (in_bb_p);
- }
+/* Print a graphical representation of the CFG of function FUN.
+ First print all basic blocks. Draw all edges at the end to get
+ subgraphs right for GraphViz, which requires nodes to be defined
+ before edges to cluster nodes properly. */
+void
+print_graph_cfg (const char *base, struct function *fun)
+{
+ const char *funcname = function_name (fun);
+ FILE *fp = open_graph_file (base, "a");
+ pretty_printer graph_slim_pp;
+ graph_slim_pp.buffer->stream = fp;
+ pretty_printer *const pp = &graph_slim_pp;
+ pp_printf (pp, "subgraph \"%s\" {\n"
+ "\tcolor=\"black\";\n"
+ "\tlabel=\"%s\";\n",
+ funcname, funcname);
+ draw_cfg_nodes (pp, fun);
+ draw_cfg_edges (pp, fun);
+ pp_printf (pp, "}\n");
+ pp_flush (pp);
fclose (fp);
}
+/* Start the dump of a graph. */
+static void
+start_graph_dump (FILE *fp, const char *base)
+{
+ pretty_printer graph_slim_pp;
+ graph_slim_pp.buffer->stream = fp;
+ pretty_printer *const pp = &graph_slim_pp;
+ pp_string (pp, "digraph \"");
+ pp_write_text_to_stream (pp);
+ pp_string (pp, base);
+ pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
+ pp_string (pp, "\" {\n");
+ pp_string (pp, "overlap=false;\n");
+ pp_flush (pp);
+}
-/* Similar as clean_dump_file, but this time for graph output files. */
+/* End the dump of a graph. */
+static void
+end_graph_dump (FILE *fp)
+{
+ fputs ("}\n", fp);
+}
+/* Similar as clean_dump_file, but this time for graph output files. */
void
clean_graph_dump_file (const char *base)
{
- size_t namelen = strlen (base);
- size_t extlen = strlen (graph_ext[graph_dump_format]) + 1;
- char *buf = alloca (namelen + extlen);
- FILE *fp;
-
- memcpy (buf, base, namelen);
- memcpy (buf + namelen, graph_ext[graph_dump_format], extlen);
-
- fp = fopen (buf, "w");
-
- if (fp == NULL)
- fatal_error ("can't open %s: %m", buf);
-
- gcc_assert (graph_dump_format == vcg);
- fputs ("graph: {\nport_sharing: no\n", fp);
-
+ FILE *fp = open_graph_file (base, "w");
+ start_graph_dump (fp, base);
fclose (fp);
}
void
finish_graph_dump_file (const char *base)
{
- size_t namelen = strlen (base);
- size_t extlen = strlen (graph_ext[graph_dump_format]) + 1;
- char *buf = alloca (namelen + extlen);
- FILE *fp;
-
- memcpy (buf, base, namelen);
- memcpy (buf + namelen, graph_ext[graph_dump_format], extlen);
-
- fp = fopen (buf, "a");
- if (fp != NULL)
- {
- gcc_assert (graph_dump_format == vcg);
- fputs ("}\n", fp);
- fclose (fp);
- }
+ FILE *fp = open_graph_file (base, "a");
+ end_graph_dump (fp);
+ fclose (fp);
}