kernel - support dummy reallocblks in devfs
[dragonfly.git] / contrib / gcc-5.0 / gcc / graph.c
blob5fb0d781bc211532410b51e796865afa9e59ea3e
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 "sbitmap.h"
27 #include "predict.h"
28 #include "vec.h"
29 #include "hashtab.h"
30 #include "hash-set.h"
31 #include "machmode.h"
32 #include "tm.h"
33 #include "hard-reg-set.h"
34 #include "input.h"
35 #include "function.h"
36 #include "dominance.h"
37 #include "cfg.h"
38 #include "cfganal.h"
39 #include "basic-block.h"
40 #include "cfgloop.h"
41 #include "graph.h"
42 #include "dumpfile.h"
43 #include "pretty-print.h"
45 /* DOT files with the .dot extension are recognized as document templates
46 by a well-known piece of word processing software out of Redmond, WA.
47 Therefore some recommend using the .gv extension instead. Obstinately
48 ignore that recommendation... */
49 static const char *const graph_ext = ".dot";
51 /* Open a file with MODE for dumping our graph to.
52 Return the file pointer. */
53 static FILE *
54 open_graph_file (const char *base, const char *mode)
56 size_t namelen = strlen (base);
57 size_t extlen = strlen (graph_ext) + 1;
58 char *buf = XALLOCAVEC (char, namelen + extlen);
59 FILE *fp;
61 memcpy (buf, base, namelen);
62 memcpy (buf + namelen, graph_ext, extlen);
64 fp = fopen (buf, mode);
65 if (fp == NULL)
66 fatal_error (input_location, "can%'t open %s: %m", buf);
68 return fp;
71 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
72 as its unique number. */
73 static void
74 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
76 const char *shape;
77 const char *fillcolor;
79 if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
81 shape = "Mdiamond";
82 fillcolor = "white";
84 else
86 shape = "record";
87 fillcolor =
88 BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
89 : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
90 : "lightgrey";
93 pp_printf (pp,
94 "\tfn_%d_basic_block_%d "
95 "[shape=%s,style=filled,fillcolor=%s,label=\"",
96 funcdef_no, bb->index, shape, fillcolor);
98 if (bb->index == ENTRY_BLOCK)
99 pp_string (pp, "ENTRY");
100 else if (bb->index == EXIT_BLOCK)
101 pp_string (pp, "EXIT");
102 else
104 pp_left_brace (pp);
105 pp_write_text_to_stream (pp);
106 dump_bb_for_graph (pp, bb);
107 pp_right_brace (pp);
110 pp_string (pp, "\"];\n\n");
111 pp_flush (pp);
114 /* Draw all successor edges of a basic block BB belonging to the function
115 with FUNCDEF_NO as its unique number. */
116 static void
117 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
119 edge e;
120 edge_iterator ei;
121 FOR_EACH_EDGE (e, ei, bb->succs)
123 const char *style = "\"solid,bold\"";
124 const char *color = "black";
125 int weight = 10;
127 if (e->flags & EDGE_FAKE)
129 style = "dotted";
130 color = "green";
131 weight = 0;
133 else if (e->flags & EDGE_DFS_BACK)
135 style = "\"dotted,bold\"";
136 color = "blue";
137 weight = 10;
139 else if (e->flags & EDGE_FALLTHRU)
141 color = "blue";
142 weight = 100;
145 if (e->flags & EDGE_ABNORMAL)
146 color = "red";
148 pp_printf (pp,
149 "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
150 "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
151 funcdef_no, e->src->index,
152 funcdef_no, e->dest->index,
153 style, color, weight,
154 (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
155 e->probability * 100 / REG_BR_PROB_BASE);
157 pp_flush (pp);
160 /* Draw all the basic blocks in the CFG in case loops are not available.
161 First compute a topological order of the blocks to get a good ranking of
162 the nodes. Then, if any nodes are not reachable from ENTRY, add them at
163 the end. */
165 static void
166 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
168 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
169 int i, n;
170 sbitmap visited;
172 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
173 bitmap_clear (visited);
175 n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
176 for (i = n_basic_blocks_for_fn (fun) - n;
177 i < n_basic_blocks_for_fn (fun); i++)
179 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
180 draw_cfg_node (pp, fun->funcdef_no, bb);
181 bitmap_set_bit (visited, bb->index);
183 free (rpo);
185 if (n != n_basic_blocks_for_fn (fun))
187 /* Some blocks are unreachable. We still want to dump them. */
188 basic_block bb;
189 FOR_ALL_BB_FN (bb, fun)
190 if (! bitmap_bit_p (visited, bb->index))
191 draw_cfg_node (pp, fun->funcdef_no, bb);
194 sbitmap_free (visited);
197 /* Draw all the basic blocks in LOOP. Print the blocks in breath-first
198 order to get a good ranking of the nodes. This function is recursive:
199 It first prints inner loops, then the body of LOOP itself. */
201 static void
202 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
203 struct loop *loop)
205 basic_block *body;
206 unsigned int i;
207 const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
209 if (loop->header != NULL
210 && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
211 pp_printf (pp,
212 "\tsubgraph cluster_%d_%d {\n"
213 "\tstyle=\"filled\";\n"
214 "\tcolor=\"darkgreen\";\n"
215 "\tfillcolor=\"%s\";\n"
216 "\tlabel=\"loop %d\";\n"
217 "\tlabeljust=l;\n"
218 "\tpenwidth=2;\n",
219 funcdef_no, loop->num,
220 fillcolors[(loop_depth (loop) - 1) % 3],
221 loop->num);
223 for (struct loop *inner = loop->inner; inner; inner = inner->next)
224 draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
226 if (loop->header == NULL)
227 return;
229 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
230 body = get_loop_body (loop);
231 else
232 body = get_loop_body_in_bfs_order (loop);
234 for (i = 0; i < loop->num_nodes; i++)
236 basic_block bb = body[i];
237 if (bb->loop_father == loop)
238 draw_cfg_node (pp, funcdef_no, bb);
241 free (body);
243 if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
244 pp_printf (pp, "\t}\n");
247 /* Draw all the basic blocks in the CFG in case the loop tree is available.
248 All loop bodys are printed in clusters. */
250 static void
251 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
253 if (loops_for_fn (fun))
254 draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
255 else
256 draw_cfg_nodes_no_loops (pp, fun);
259 /* Draw all edges in the CFG. Retreating edges are drawin as not
260 constraining, this makes the layout of the graph better.
261 (??? Calling mark_dfs_back may change the compiler's behavior when
262 dumping, but computing back edges here for ourselves is also not
263 desirable.) */
265 static void
266 draw_cfg_edges (pretty_printer *pp, struct function *fun)
268 basic_block bb;
269 mark_dfs_back_edges ();
270 FOR_ALL_BB_FN (bb, cfun)
271 draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
273 /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout. */
274 pp_printf (pp,
275 "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
276 "[style=\"invis\",constraint=true];\n",
277 fun->funcdef_no, ENTRY_BLOCK,
278 fun->funcdef_no, EXIT_BLOCK);
279 pp_flush (pp);
282 /* Print a graphical representation of the CFG of function FUN.
283 First print all basic blocks. Draw all edges at the end to get
284 subgraphs right for GraphViz, which requires nodes to be defined
285 before edges to cluster nodes properly. */
287 void
288 print_graph_cfg (const char *base, struct function *fun)
290 const char *funcname = function_name (fun);
291 FILE *fp = open_graph_file (base, "a");
292 pretty_printer graph_slim_pp;
293 graph_slim_pp.buffer->stream = fp;
294 pretty_printer *const pp = &graph_slim_pp;
295 pp_printf (pp, "subgraph \"cluster_%s\" {\n"
296 "\tstyle=\"dashed\";\n"
297 "\tcolor=\"black\";\n"
298 "\tlabel=\"%s ()\";\n",
299 funcname, funcname);
300 draw_cfg_nodes (pp, fun);
301 draw_cfg_edges (pp, fun);
302 pp_printf (pp, "}\n");
303 pp_flush (pp);
304 fclose (fp);
307 /* Start the dump of a graph. */
308 static void
309 start_graph_dump (FILE *fp, const char *base)
311 pretty_printer graph_slim_pp;
312 graph_slim_pp.buffer->stream = fp;
313 pretty_printer *const pp = &graph_slim_pp;
314 pp_string (pp, "digraph \"");
315 pp_write_text_to_stream (pp);
316 pp_string (pp, base);
317 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
318 pp_string (pp, "\" {\n");
319 pp_string (pp, "overlap=false;\n");
320 pp_flush (pp);
323 /* End the dump of a graph. */
324 static void
325 end_graph_dump (FILE *fp)
327 fputs ("}\n", fp);
330 /* Similar as clean_dump_file, but this time for graph output files. */
331 void
332 clean_graph_dump_file (const char *base)
334 FILE *fp = open_graph_file (base, "w");
335 start_graph_dump (fp, base);
336 fclose (fp);
340 /* Do final work on the graph output file. */
341 void
342 finish_graph_dump_file (const char *base)
344 FILE *fp = open_graph_file (base, "a");
345 end_graph_dump (fp);
346 fclose (fp);