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.
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 "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"
44
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...  */
49static const char *const graph_ext = ".dot";
50
51/* Open a file with MODE for dumping our graph to.
52   Return the file pointer.  */
53static FILE *
54open_graph_file (const char *base, const char *mode)
55{
56  size_t namelen = strlen (base);
57  size_t extlen = strlen (graph_ext) + 1;
58  char *buf = XALLOCAVEC (char, namelen + extlen);
59  FILE *fp;
60
61  memcpy (buf, base, namelen);
62  memcpy (buf + namelen, graph_ext, extlen);
63
64  fp = fopen (buf, mode);
65  if (fp == NULL)
66    fatal_error (input_location, "can%'t open %s: %m", buf);
67
68  return fp;
69}
70
71/* Draw a basic block BB belonging to the function with FUNCDEF_NO
72   as its unique number.  */
73static void
74draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
75{
76  const char *shape;
77  const char *fillcolor;
78
79  if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
80    {
81      shape = "Mdiamond";
82      fillcolor = "white";
83    }
84  else
85    {
86      shape = "record";
87      fillcolor =
88	BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
89	: BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
90	: "lightgrey";
91    }
92
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);
97
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
103    {
104      pp_left_brace (pp);
105      pp_write_text_to_stream (pp);
106      dump_bb_for_graph (pp, bb);
107      pp_right_brace (pp);
108    }
109
110  pp_string (pp, "\"];\n\n");
111  pp_flush (pp);
112}
113
114/* Draw all successor edges of a basic block BB belonging to the function
115   with FUNCDEF_NO as its unique number.  */
116static void
117draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
118{
119  edge e;
120  edge_iterator ei;
121  FOR_EACH_EDGE (e, ei, bb->succs)
122    {
123      const char *style = "\"solid,bold\"";
124      const char *color = "black";
125      int weight = 10;
126
127      if (e->flags & EDGE_FAKE)
128	{
129	  style = "dotted";
130	  color = "green";
131	  weight = 0;
132	}
133      else if (e->flags & EDGE_DFS_BACK)
134	{
135	  style = "\"dotted,bold\"";
136	  color = "blue";
137	  weight = 10;
138	}
139      else if (e->flags & EDGE_FALLTHRU)
140	{
141	  color = "blue";
142	  weight = 100;
143	}
144
145      if (e->flags & EDGE_ABNORMAL)
146	color = "red";
147
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);
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  sbitmap visited;
171
172  visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
173  bitmap_clear (visited);
174
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++)
178    {
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);
182    }
183  free (rpo);
184
185  if (n != n_basic_blocks_for_fn (fun))
186    {
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);
192    }
193
194  sbitmap_free (visited);
195}
196
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.  */
200
201static void
202draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
203			 struct loop *loop)
204{
205  basic_block *body;
206  unsigned int i;
207  const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
208
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);
222
223  for (struct loop *inner = loop->inner; inner; inner = inner->next)
224    draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
225
226  if (loop->header == NULL)
227    return;
228
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);
233
234  for (i = 0; i < loop->num_nodes; i++)
235    {
236      basic_block bb = body[i];
237      if (bb->loop_father == loop)
238	draw_cfg_node (pp, funcdef_no, bb);
239    }
240
241  free (body);
242
243  if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
244    pp_printf (pp, "\t}\n");
245}
246
247/* Draw all the basic blocks in the CFG in case the loop tree is available.
248   All loop bodys are printed in clusters.  */
249
250static void
251draw_cfg_nodes (pretty_printer *pp, struct function *fun)
252{
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);
257}
258
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.)  */
264
265static void
266draw_cfg_edges (pretty_printer *pp, struct function *fun)
267{
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);
272
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);
280}
281
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.  */
286
287void
288print_graph_cfg (const char *base, struct function *fun)
289{
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);
305}
306
307/* Start the dump of a graph.  */
308static void
309start_graph_dump (FILE *fp, const char *base)
310{
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);
321}
322
323/* End the dump of a graph.  */
324static void
325end_graph_dump (FILE *fp)
326{
327  fputs ("}\n", fp);
328}
329
330/* Similar as clean_dump_file, but this time for graph output files.  */
331void
332clean_graph_dump_file (const char *base)
333{
334  FILE *fp = open_graph_file (base, "w");
335  start_graph_dump (fp, base);
336  fclose (fp);
337}
338
339
340/* Do final work on the graph output file.  */
341void
342finish_graph_dump_file (const char *base)
343{
344  FILE *fp = open_graph_file (base, "a");
345  end_graph_dump (fp);
346  fclose (fp);
347}
348