Fix type in the changelog entry,
[official-gcc.git] / gcc / graph.c
blobf55ae22305847e5ee0819884d8f05b8a9ba005d5
1 /* Output routines for graphical representation.
2 Copyright (C) 1998-2015 Free Software Foundation, Inc.
3 Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
4 Rewritten for DOT output by Steven Bosscher, 2012.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "diagnostic-core.h" /* for fatal_error */
26 #include "backend.h"
27 #include "cfghooks.h"
28 #include "hard-reg-set.h"
29 #include "cfganal.h"
30 #include "cfgloop.h"
31 #include "graph.h"
32 #include "dumpfile.h"
33 #include "pretty-print.h"
35 /* DOT files with the .dot extension are recognized as document templates
36 by a well-known piece of word processing software out of Redmond, WA.
37 Therefore some recommend using the .gv extension instead. Obstinately
38 ignore that recommendation... */
39 static const char *const graph_ext = ".dot";
41 /* Open a file with MODE for dumping our graph to.
42 Return the file pointer. */
43 static FILE *
44 open_graph_file (const char *base, const char *mode)
46 size_t namelen = strlen (base);
47 size_t extlen = strlen (graph_ext) + 1;
48 char *buf = XALLOCAVEC (char, namelen + extlen);
49 FILE *fp;
51 memcpy (buf, base, namelen);
52 memcpy (buf + namelen, graph_ext, extlen);
54 fp = fopen (buf, mode);
55 if (fp == NULL)
56 fatal_error (input_location, "can%'t open %s: %m", buf);
58 return fp;
61 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
62 as its unique number. */
63 static void
64 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
66 const char *shape;
67 const char *fillcolor;
69 if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
71 shape = "Mdiamond";
72 fillcolor = "white";
74 else
76 shape = "record";
77 fillcolor =
78 BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
79 : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
80 : "lightgrey";
83 pp_printf (pp,
84 "\tfn_%d_basic_block_%d "
85 "[shape=%s,style=filled,fillcolor=%s,label=\"",
86 funcdef_no, bb->index, shape, fillcolor);
88 if (bb->index == ENTRY_BLOCK)
89 pp_string (pp, "ENTRY");
90 else if (bb->index == EXIT_BLOCK)
91 pp_string (pp, "EXIT");
92 else
94 pp_left_brace (pp);
95 pp_write_text_to_stream (pp);
96 dump_bb_for_graph (pp, bb);
97 pp_right_brace (pp);
100 pp_string (pp, "\"];\n\n");
101 pp_flush (pp);
104 /* Draw all successor edges of a basic block BB belonging to the function
105 with FUNCDEF_NO as its unique number. */
106 static void
107 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
109 edge e;
110 edge_iterator ei;
111 FOR_EACH_EDGE (e, ei, bb->succs)
113 const char *style = "\"solid,bold\"";
114 const char *color = "black";
115 int weight = 10;
117 if (e->flags & EDGE_FAKE)
119 style = "dotted";
120 color = "green";
121 weight = 0;
123 else if (e->flags & EDGE_DFS_BACK)
125 style = "\"dotted,bold\"";
126 color = "blue";
127 weight = 10;
129 else if (e->flags & EDGE_FALLTHRU)
131 color = "blue";
132 weight = 100;
135 if (e->flags & EDGE_ABNORMAL)
136 color = "red";
138 pp_printf (pp,
139 "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
140 "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
141 funcdef_no, e->src->index,
142 funcdef_no, e->dest->index,
143 style, color, weight,
144 (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
145 e->probability * 100 / REG_BR_PROB_BASE);
147 pp_flush (pp);
150 /* Draw all the basic blocks in the CFG in case loops are not available.
151 First compute a topological order of the blocks to get a good ranking of
152 the nodes. Then, if any nodes are not reachable from ENTRY, add them at
153 the end. */
155 static void
156 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
158 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
159 int i, n;
160 sbitmap visited;
162 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
163 bitmap_clear (visited);
165 n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
166 for (i = n_basic_blocks_for_fn (fun) - n;
167 i < n_basic_blocks_for_fn (fun); i++)
169 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
170 draw_cfg_node (pp, fun->funcdef_no, bb);
171 bitmap_set_bit (visited, bb->index);
173 free (rpo);
175 if (n != n_basic_blocks_for_fn (fun))
177 /* Some blocks are unreachable. We still want to dump them. */
178 basic_block bb;
179 FOR_ALL_BB_FN (bb, fun)
180 if (! bitmap_bit_p (visited, bb->index))
181 draw_cfg_node (pp, fun->funcdef_no, bb);
184 sbitmap_free (visited);
187 /* Draw all the basic blocks in LOOP. Print the blocks in breath-first
188 order to get a good ranking of the nodes. This function is recursive:
189 It first prints inner loops, then the body of LOOP itself. */
191 static void
192 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
193 struct loop *loop)
195 basic_block *body;
196 unsigned int i;
197 const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
199 if (loop->header != NULL
200 && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
201 pp_printf (pp,
202 "\tsubgraph cluster_%d_%d {\n"
203 "\tstyle=\"filled\";\n"
204 "\tcolor=\"darkgreen\";\n"
205 "\tfillcolor=\"%s\";\n"
206 "\tlabel=\"loop %d\";\n"
207 "\tlabeljust=l;\n"
208 "\tpenwidth=2;\n",
209 funcdef_no, loop->num,
210 fillcolors[(loop_depth (loop) - 1) % 3],
211 loop->num);
213 for (struct loop *inner = loop->inner; inner; inner = inner->next)
214 draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
216 if (loop->header == NULL)
217 return;
219 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
220 body = get_loop_body (loop);
221 else
222 body = get_loop_body_in_bfs_order (loop);
224 for (i = 0; i < loop->num_nodes; i++)
226 basic_block bb = body[i];
227 if (bb->loop_father == loop)
228 draw_cfg_node (pp, funcdef_no, bb);
231 free (body);
233 if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
234 pp_printf (pp, "\t}\n");
237 /* Draw all the basic blocks in the CFG in case the loop tree is available.
238 All loop bodys are printed in clusters. */
240 static void
241 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
243 if (loops_for_fn (fun))
244 draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
245 else
246 draw_cfg_nodes_no_loops (pp, fun);
249 /* Draw all edges in the CFG. Retreating edges are drawin as not
250 constraining, this makes the layout of the graph better.
251 (??? Calling mark_dfs_back may change the compiler's behavior when
252 dumping, but computing back edges here for ourselves is also not
253 desirable.) */
255 static void
256 draw_cfg_edges (pretty_printer *pp, struct function *fun)
258 basic_block bb;
259 mark_dfs_back_edges ();
260 FOR_ALL_BB_FN (bb, cfun)
261 draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
263 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
264 pp_printf (pp,
265 "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
266 "[style=\"invis\",constraint=true];\n",
267 fun->funcdef_no, ENTRY_BLOCK,
268 fun->funcdef_no, EXIT_BLOCK);
269 pp_flush (pp);
272 /* Print a graphical representation of the CFG of function FUN.
273 First print all basic blocks. Draw all edges at the end to get
274 subgraphs right for GraphViz, which requires nodes to be defined
275 before edges to cluster nodes properly. */
277 void
278 print_graph_cfg (const char *base, struct function *fun)
280 const char *funcname = function_name (fun);
281 FILE *fp = open_graph_file (base, "a");
282 pretty_printer graph_slim_pp;
283 graph_slim_pp.buffer->stream = fp;
284 pretty_printer *const pp = &graph_slim_pp;
285 pp_printf (pp, "subgraph \"cluster_%s\" {\n"
286 "\tstyle=\"dashed\";\n"
287 "\tcolor=\"black\";\n"
288 "\tlabel=\"%s ()\";\n",
289 funcname, funcname);
290 draw_cfg_nodes (pp, fun);
291 draw_cfg_edges (pp, fun);
292 pp_printf (pp, "}\n");
293 pp_flush (pp);
294 fclose (fp);
297 /* Start the dump of a graph. */
298 static void
299 start_graph_dump (FILE *fp, const char *base)
301 pretty_printer graph_slim_pp;
302 graph_slim_pp.buffer->stream = fp;
303 pretty_printer *const pp = &graph_slim_pp;
304 pp_string (pp, "digraph \"");
305 pp_write_text_to_stream (pp);
306 pp_string (pp, base);
307 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
308 pp_string (pp, "\" {\n");
309 pp_string (pp, "overlap=false;\n");
310 pp_flush (pp);
313 /* End the dump of a graph. */
314 static void
315 end_graph_dump (FILE *fp)
317 fputs ("}\n", fp);
320 /* Similar as clean_dump_file, but this time for graph output files. */
321 void
322 clean_graph_dump_file (const char *base)
324 FILE *fp = open_graph_file (base, "w");
325 start_graph_dump (fp, base);
326 fclose (fp);
330 /* Do final work on the graph output file. */
331 void
332 finish_graph_dump_file (const char *base)
334 FILE *fp = open_graph_file (base, "a");
335 end_graph_dump (fp);
336 fclose (fp);