gcc/graph.c

   1 /* Output routines for graphical representation.
   2    Copyright (C) 1998-2016 Free Software Foundation, Inc.
   3    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
   4    Rewritten for DOT output by Steven Bosscher, 2012.
   5
   6 This file is part of GCC.
   7
   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.
  12
  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.
  17
  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/>.  */
  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
  33 /* DOT files with the .dot extension are recognized as document templates
  34    by a well-known piece of word processing software out of Redmond, WA.
  35    Therefore some recommend using the .gv extension instead.  Obstinately
  36    ignore that recommendation...  */
  37 static const char *const graph_ext = ".dot";
  38
  39 /* Open a file with MODE for dumping our graph to.
  40    Return the file pointer.  */
  41 static FILE *
  42 open_graph_file (const char *base, const char *mode)
  43 {
  44   size_t namelen = strlen (base);
  45   size_t extlen = strlen (graph_ext) + 1;
  46   char *buf = XALLOCAVEC (char, namelen + extlen);
  47   FILE *fp;
  48
  49   memcpy (buf, base, namelen);
  50   memcpy (buf + namelen, graph_ext, extlen);
  51
  52   fp = fopen (buf, mode);
  53   if (fp == NULL)
  54     fatal_error (input_location, "can%'t open %s: %m", buf);
  55
  56   return fp;
  57 }
  58
  59 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
  60    as its unique number.  */
  61 static void
  62 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
  63 {
  64   const char *shape;
  65   const char *fillcolor;
  66
  67   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
  68     {
  69       shape = "Mdiamond";
  70       fillcolor = "white";
  71     }
  72   else
  73     {
  74       shape = "record";
  75       fillcolor =
  76         BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
  77         : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
  78         : "lightgrey";
  79     }
  80
  81   pp_printf (pp,
  82              "\tfn_%d_basic_block_%d "
  83              "[shape=%s,style=filled,fillcolor=%s,label=\"",
  84              funcdef_no, bb->index, shape, fillcolor);
  85
  86   if (bb->index == ENTRY_BLOCK)
  87     pp_string (pp, "ENTRY");
  88   else if (bb->index == EXIT_BLOCK)
  89     pp_string (pp, "EXIT");
  90   else
  91     {
  92       pp_left_brace (pp);
  93       pp_write_text_to_stream (pp);
  94       dump_bb_for_graph (pp, bb);
  95       pp_right_brace (pp);
  96     }
  97
  98   pp_string (pp, "\"];\n\n");
  99   pp_flush (pp);
 100 }
 101
 102 /* Draw all successor edges of a basic block BB belonging to the function
 103    with FUNCDEF_NO as its unique number.  */
 104 static void
 105 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
 106 {
 107   edge e;
 108   edge_iterator ei;
 109   FOR_EACH_EDGE (e, ei, bb->succs)
 110     {
 111       const char *style = "\"solid,bold\"";
 112       const char *color = "black";
 113       int weight = 10;
 114
 115       if (e->flags & EDGE_FAKE)
 116         {
 117           style = "dotted";
 118           color = "green";
 119           weight = 0;
 120         }
 121       else if (e->flags & EDGE_DFS_BACK)
 122         {
 123           style = "\"dotted,bold\"";
 124           color = "blue";
 125           weight = 10;
 126         }
 127       else if (e->flags & EDGE_FALLTHRU)
 128         {
 129           color = "blue";
 130           weight = 100;
 131         }
 132
 133       if (e->flags & EDGE_ABNORMAL)
 134         color = "red";
 135
 136       pp_printf (pp,
 137                  "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 138                  "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
 139                  funcdef_no, e->src->index,
 140                  funcdef_no, e->dest->index,
 141                  style, color, weight,
 142                  (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
 143                  e->probability * 100 / REG_BR_PROB_BASE);
 144     }
 145   pp_flush (pp);
 146 }
 147
 148 /* Draw all the basic blocks in the CFG in case loops are not available.
 149    First compute a topological order of the blocks to get a good ranking of
 150    the nodes.  Then, if any nodes are not reachable from ENTRY, add them at
 151    the end.  */
 152
 153 static void
 154 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
 155 {
 156   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
 157   int i, n;
 158   sbitmap visited;
 159
 160   visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
 161   bitmap_clear (visited);
 162
 163   n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
 164   for (i = n_basic_blocks_for_fn (fun) - n;
 165        i < n_basic_blocks_for_fn (fun); i++)
 166     {
 167       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
 168       draw_cfg_node (pp, fun->funcdef_no, bb);
 169       bitmap_set_bit (visited, bb->index);
 170     }
 171   free (rpo);
 172
 173   if (n != n_basic_blocks_for_fn (fun))
 174     {
 175       /* Some blocks are unreachable.  We still want to dump them.  */
 176       basic_block bb;
 177       FOR_ALL_BB_FN (bb, fun)
 178         if (! bitmap_bit_p (visited, bb->index))
 179           draw_cfg_node (pp, fun->funcdef_no, bb);
 180     }
 181
 182   sbitmap_free (visited);
 183 }
 184
 185 /* Draw all the basic blocks in LOOP.  Print the blocks in breath-first
 186    order to get a good ranking of the nodes.  This function is recursive:
 187    It first prints inner loops, then the body of LOOP itself.  */
 188
 189 static void
 190 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
 191                          struct loop *loop)
 192 {
 193   basic_block *body;
 194   unsigned int i;
 195   const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
 196
 197   if (loop->header != NULL
 198       && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 199     pp_printf (pp,
 200                "\tsubgraph cluster_%d_%d {\n"
 201                "\tstyle=\"filled\";\n"
 202                "\tcolor=\"darkgreen\";\n"
 203                "\tfillcolor=\"%s\";\n"
 204                "\tlabel=\"loop %d\";\n"
 205                "\tlabeljust=l;\n"
 206                "\tpenwidth=2;\n",
 207                funcdef_no, loop->num,
 208                fillcolors[(loop_depth (loop) - 1) % 3],
 209                loop->num);
 210
 211   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 212     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 213
 214   if (loop->header == NULL)
 215     return;
 216
 217   if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
 218     body = get_loop_body (loop);
 219   else
 220     body = get_loop_body_in_bfs_order (loop);
 221
 222   for (i = 0; i < loop->num_nodes; i++)
 223     {
 224       basic_block bb = body[i];
 225       if (bb->loop_father == loop)
 226         draw_cfg_node (pp, funcdef_no, bb);
 227     }
 228
 229   free (body);
 230
 231   if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 232     pp_printf (pp, "\t}\n");
 233 }
 234
 235 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 236    All loop bodys are printed in clusters.  */
 237
 238 static void
 239 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 240 {
 241   if (loops_for_fn (fun))
 242     draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
 243   else
 244     draw_cfg_nodes_no_loops (pp, fun);
 245 }
 246
 247 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 248    constraining, this makes the layout of the graph better.
 249    (??? Calling mark_dfs_back may change the compiler's behavior when
 250    dumping, but computing back edges here for ourselves is also not
 251    desirable.)  */
 252
 253 static void
 254 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 255 {
 256   basic_block bb;
 257   mark_dfs_back_edges ();
 258   FOR_ALL_BB_FN (bb, cfun)
 259     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 260
 261   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 262   pp_printf (pp,
 263              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 264              "[style=\"invis\",constraint=true];\n",
 265              fun->funcdef_no, ENTRY_BLOCK,
 266              fun->funcdef_no, EXIT_BLOCK);
 267   pp_flush (pp);
 268 }
 269
 270 /* Print a graphical representation of the CFG of function FUN.
 271    First print all basic blocks.  Draw all edges at the end to get
 272    subgraphs right for GraphViz, which requires nodes to be defined
 273    before edges to cluster nodes properly.  */
 274
 275 void
 276 print_graph_cfg (const char *base, struct function *fun)
 277 {
 278   const char *funcname = function_name (fun);
 279   FILE *fp = open_graph_file (base, "a");
 280   pretty_printer graph_slim_pp;
 281   graph_slim_pp.buffer->stream = fp;
 282   pretty_printer *const pp = &graph_slim_pp;
 283   pp_printf (pp, "subgraph \"cluster_%s\" {\n"
 284                  "\tstyle=\"dashed\";\n"
 285                  "\tcolor=\"black\";\n"
 286                  "\tlabel=\"%s ()\";\n",
 287                  funcname, funcname);
 288   draw_cfg_nodes (pp, fun);
 289   draw_cfg_edges (pp, fun);
 290   pp_printf (pp, "}\n");
 291   pp_flush (pp);
 292   fclose (fp);
 293 }
 294
 295 /* Start the dump of a graph.  */
 296 static void
 297 start_graph_dump (FILE *fp, const char *base)
 298 {
 299   pretty_printer graph_slim_pp;
 300   graph_slim_pp.buffer->stream = fp;
 301   pretty_printer *const pp = &graph_slim_pp;
 302   pp_string (pp, "digraph \"");
 303   pp_write_text_to_stream (pp);
 304   pp_string (pp, base);
 305   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 306   pp_string (pp, "\" {\n");
 307   pp_string (pp, "overlap=false;\n");
 308   pp_flush (pp);
 309 }
 310
 311 /* End the dump of a graph.  */
 312 static void
 313 end_graph_dump (FILE *fp)
 314 {
 315   fputs ("}\n", fp);
 316 }
 317
 318 /* Similar as clean_dump_file, but this time for graph output files.  */
 319 void
 320 clean_graph_dump_file (const char *base)
 321 {
 322   FILE *fp = open_graph_file (base, "w");
 323   start_graph_dump (fp, base);
 324   fclose (fp);
 325 }
 326
 327
 328 /* Do final work on the graph output file.  */
 329 void
 330 finish_graph_dump_file (const char *base)
 331 {
 332   FILE *fp = open_graph_file (base, "a");
 333   end_graph_dump (fp);
 334   fclose (fp);
 335 }