1/* Output routines for graphical representation.
2   Copyright (C) 1998-2020 Free Software Foundation, Inc.
3   Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
4   Rewritten for DOT output by Steven Bosscher, 2012.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3.  If not see
20<http://www.gnu.org/licenses/>.  */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "cfghooks.h"
27#include "pretty-print.h"
28#include "diagnostic-core.h" /* for fatal_error */
29#include "cfganal.h"
30#include "cfgloop.h"
31#include "graph.h"
32#include "dumpfile.h"
33
34/* DOT files with the .dot extension are recognized as document templates
35   by a well-known piece of word processing software out of Redmond, WA.
36   Therefore some recommend using the .gv extension instead.  Obstinately
37   ignore that recommendation...  */
38static const char *const graph_ext = ".dot";
39
40/* Open a file with MODE for dumping our graph to.
41   Return the file pointer.  */
42static FILE *
43open_graph_file (const char *base, const char *mode)
44{
45  size_t namelen = strlen (base);
46  size_t extlen = strlen (graph_ext) + 1;
47  char *buf = XALLOCAVEC (char, namelen + extlen);
48  FILE *fp;
49
50  memcpy (buf, base, namelen);
51  memcpy (buf + namelen, graph_ext, extlen);
52
53  fp = fopen (buf, mode);
54  if (fp == NULL)
55    fatal_error (input_location, "cannot open %s: %m", buf);
56
57  return fp;
58}
59
60/* Disable warnings about quoting issues in the pp_xxx calls below
61   that (intentionally) don't follow GCC diagnostic conventions.  */
62#if __GNUC__ >= 10
63#  pragma GCC diagnostic push
64#  pragma GCC diagnostic ignored "-Wformat-diag"
65#endif
66
67/* Draw a basic block BB belonging to the function with FUNCDEF_NO
68   as its unique number.  */
69static void
70draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
71{
72  const char *shape;
73  const char *fillcolor;
74
75  if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
76    {
77      shape = "Mdiamond";
78      fillcolor = "white";
79    }
80  else
81    {
82      shape = "record";
83      fillcolor =
84	BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
85	: BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
86	: "lightgrey";
87    }
88
89  pp_printf (pp,
90	     "\tfn_%d_basic_block_%d "
91	     "[shape=%s,style=filled,fillcolor=%s,label=\"",
92	     funcdef_no, bb->index, shape, fillcolor);
93
94  if (bb->index == ENTRY_BLOCK)
95    pp_string (pp, "ENTRY");
96  else if (bb->index == EXIT_BLOCK)
97    pp_string (pp, "EXIT");
98  else
99    {
100      pp_left_brace (pp);
101      pp_write_text_to_stream (pp);
102      dump_bb_for_graph (pp, bb);
103      pp_right_brace (pp);
104    }
105
106  pp_string (pp, "\"];\n\n");
107  pp_flush (pp);
108}
109
110/* Draw all successor edges of a basic block BB belonging to the function
111   with FUNCDEF_NO as its unique number.  */
112static void
113draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
114{
115  edge e;
116  edge_iterator ei;
117  FOR_EACH_EDGE (e, ei, bb->succs)
118    {
119      const char *style = "\"solid,bold\"";
120      const char *color = "black";
121      int weight = 10;
122
123      if (e->flags & EDGE_FAKE)
124	{
125	  style = "dotted";
126	  color = "green";
127	  weight = 0;
128	}
129      else if (e->flags & EDGE_DFS_BACK)
130	{
131	  style = "\"dotted,bold\"";
132	  color = "blue";
133	  weight = 10;
134	}
135      else if (e->flags & EDGE_FALLTHRU)
136	{
137	  color = "blue";
138	  weight = 100;
139	}
140
141      if (e->flags & EDGE_ABNORMAL)
142	color = "red";
143
144      pp_printf (pp,
145		 "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
146		 "[style=%s,color=%s,weight=%d,constraint=%s",
147		 funcdef_no, e->src->index,
148		 funcdef_no, e->dest->index,
149		 style, color, weight,
150		 (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true");
151      if (e->probability.initialized_p ())
152        pp_printf (pp, ",label=\"[%i%%]\"",
153		   e->probability.to_reg_br_prob_base ()
154		   * 100 / REG_BR_PROB_BASE);
155      pp_printf (pp, "];\n");
156    }
157  pp_flush (pp);
158}
159
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.  */
164
165static void
166draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
167{
168  int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
169  int i, n;
170
171  auto_sbitmap visited (last_basic_block_for_fn (cfun));
172  bitmap_clear (visited);
173
174  n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
175  for (i = n_basic_blocks_for_fn (fun) - n;
176       i < n_basic_blocks_for_fn (fun); i++)
177    {
178      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
179      draw_cfg_node (pp, fun->funcdef_no, bb);
180      bitmap_set_bit (visited, bb->index);
181    }
182  free (rpo);
183
184  if (n != n_basic_blocks_for_fn (fun))
185    {
186      /* Some blocks are unreachable.  We still want to dump them.  */
187      basic_block bb;
188      FOR_ALL_BB_FN (bb, fun)
189	if (! bitmap_bit_p (visited, bb->index))
190	  draw_cfg_node (pp, fun->funcdef_no, bb);
191    }
192}
193
194/* Draw all the basic blocks in LOOP.  Print the blocks in breath-first
195   order to get a good ranking of the nodes.  This function is recursive:
196   It first prints inner loops, then the body of LOOP itself.  */
197
198static void
199draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
200			 class loop *loop)
201{
202  basic_block *body;
203  unsigned int i;
204  const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
205
206  if (loop->header != NULL
207      && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
208    pp_printf (pp,
209	       "\tsubgraph cluster_%d_%d {\n"
210	       "\tstyle=\"filled\";\n"
211	       "\tcolor=\"darkgreen\";\n"
212	       "\tfillcolor=\"%s\";\n"
213	       "\tlabel=\"loop %d\";\n"
214	       "\tlabeljust=l;\n"
215	       "\tpenwidth=2;\n",
216	       funcdef_no, loop->num,
217	       fillcolors[(loop_depth (loop) - 1) % 3],
218	       loop->num);
219
220  for (class loop *inner = loop->inner; inner; inner = inner->next)
221    draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
222
223  if (loop->header == NULL)
224    return;
225
226  if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
227    body = get_loop_body (loop);
228  else
229    body = get_loop_body_in_bfs_order (loop);
230
231  for (i = 0; i < loop->num_nodes; i++)
232    {
233      basic_block bb = body[i];
234      if (bb->loop_father == loop)
235	draw_cfg_node (pp, funcdef_no, bb);
236    }
237
238  free (body);
239
240  if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
241    pp_printf (pp, "\t}\n");
242}
243
244/* Draw all the basic blocks in the CFG in case the loop tree is available.
245   All loop bodys are printed in clusters.  */
246
247static void
248draw_cfg_nodes (pretty_printer *pp, struct function *fun)
249{
250  if (loops_for_fn (fun))
251    draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
252  else
253    draw_cfg_nodes_no_loops (pp, fun);
254}
255
256/* Draw all edges in the CFG.  Retreating edges are drawin as not
257   constraining, this makes the layout of the graph better.  */
258
259static void
260draw_cfg_edges (pretty_printer *pp, struct function *fun)
261{
262  basic_block bb;
263
264  /* Save EDGE_DFS_BACK flag to dfs_back.  */
265  auto_bitmap dfs_back;
266  edge e;
267  edge_iterator ei;
268  unsigned int idx = 0;
269  FOR_EACH_BB_FN (bb, cfun)
270    FOR_EACH_EDGE (e, ei, bb->succs)
271      {
272	if (e->flags & EDGE_DFS_BACK)
273	  bitmap_set_bit (dfs_back, idx);
274	idx++;
275      }
276
277  mark_dfs_back_edges ();
278  FOR_ALL_BB_FN (bb, cfun)
279    draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
280
281  /* Restore EDGE_DFS_BACK flag from dfs_back.  */
282  idx = 0;
283  FOR_EACH_BB_FN (bb, cfun)
284    FOR_EACH_EDGE (e, ei, bb->succs)
285      {
286	if (bitmap_bit_p (dfs_back, idx))
287	  e->flags |= EDGE_DFS_BACK;
288	else
289	  e->flags &= ~EDGE_DFS_BACK;
290	idx++;
291      }
292
293  /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
294  pp_printf (pp,
295	     "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
296	     "[style=\"invis\",constraint=true];\n",
297	     fun->funcdef_no, ENTRY_BLOCK,
298	     fun->funcdef_no, EXIT_BLOCK);
299  pp_flush (pp);
300}
301
302/* Print a graphical representation of the CFG of function FUN.
303   First print all basic blocks.  Draw all edges at the end to get
304   subgraphs right for GraphViz, which requires nodes to be defined
305   before edges to cluster nodes properly.  */
306
307void DEBUG_FUNCTION
308print_graph_cfg (FILE *fp, struct function *fun)
309{
310  pretty_printer graph_slim_pp;
311  graph_slim_pp.buffer->stream = fp;
312  pretty_printer *const pp = &graph_slim_pp;
313  const char *funcname = function_name (fun);
314  pp_printf (pp, "subgraph \"cluster_%s\" {\n"
315		 "\tstyle=\"dashed\";\n"
316		 "\tcolor=\"black\";\n"
317		 "\tlabel=\"%s ()\";\n",
318		 funcname, funcname);
319  draw_cfg_nodes (pp, fun);
320  draw_cfg_edges (pp, fun);
321  pp_printf (pp, "}\n");
322  pp_flush (pp);
323}
324
325/* Overload with additional flag argument.  */
326
327void DEBUG_FUNCTION
328print_graph_cfg (FILE *fp, struct function *fun, dump_flags_t flags)
329{
330  dump_flags_t saved_dump_flags = dump_flags;
331  dump_flags = flags;
332  print_graph_cfg (fp, fun);
333  dump_flags = saved_dump_flags;
334}
335
336
337/* Print a graphical representation of the CFG of function FUN.
338   First print all basic blocks.  Draw all edges at the end to get
339   subgraphs right for GraphViz, which requires nodes to be defined
340   before edges to cluster nodes properly.  */
341
342void
343print_graph_cfg (const char *base, struct function *fun)
344{
345  FILE *fp = open_graph_file (base, "a");
346  print_graph_cfg (fp, fun);
347  fclose (fp);
348}
349
350/* Start the dump of a graph.  */
351static void
352start_graph_dump (FILE *fp, const char *base)
353{
354  pretty_printer graph_slim_pp;
355  graph_slim_pp.buffer->stream = fp;
356  pretty_printer *const pp = &graph_slim_pp;
357  pp_string (pp, "digraph \"");
358  pp_write_text_to_stream (pp);
359  pp_string (pp, base);
360  pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
361  pp_string (pp, "\" {\n");
362  pp_string (pp, "overlap=false;\n");
363  pp_flush (pp);
364}
365
366/* End the dump of a graph.  */
367static void
368end_graph_dump (FILE *fp)
369{
370  fputs ("}\n", fp);
371}
372
373/* Similar as clean_dump_file, but this time for graph output files.  */
374void
375clean_graph_dump_file (const char *base)
376{
377  FILE *fp = open_graph_file (base, "w");
378  start_graph_dump (fp, base);
379  fclose (fp);
380}
381
382
383/* Do final work on the graph output file.  */
384void
385finish_graph_dump_file (const char *base)
386{
387  FILE *fp = open_graph_file (base, "a");
388  end_graph_dump (fp);
389  fclose (fp);
390}
391
392#if __GNUC__ >= 10
393#  pragma GCC diagnostic pop
394#endif
395