gcc/graph.c

   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
   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 "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"
  34
  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";
  40
  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)
  45 {
  46   size_t namelen = strlen (base);
  47   size_t extlen = strlen (graph_ext) + 1;
  48   char *buf = XALLOCAVEC (char, namelen + extlen);
  49   FILE *fp;
  50
  51   memcpy (buf, base, namelen);
  52   memcpy (buf + namelen, graph_ext, extlen);
  53
  54   fp = fopen (buf, mode);
  55   if (fp == NULL)
  56     fatal_error (input_location, "can%'t open %s: %m", buf);
  57
  58   return fp;
  59 }
  60
  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)
  65 {
  66   const char *shape;
  67   const char *fillcolor;
  68
  69   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
  70     {
  71       shape = "Mdiamond";
  72       fillcolor = "white";
  73     }
  74   else
  75     {
  76       shape = "record";
  77       fillcolor =
  78         BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
  79         : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
  80         : "lightgrey";
  81     }
  82
  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);
  87
  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
  93     {
  94       pp_left_brace (pp);
  95       pp_write_text_to_stream (pp);
  96       dump_bb_for_graph (pp, bb);
  97       pp_right_brace (pp);
  98     }
  99
 100   pp_string (pp, "\"];\n\n");
 101   pp_flush (pp);
 102 }
 103
 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)
 108 {
 109   edge e;
 110   edge_iterator ei;
 111   FOR_EACH_EDGE (e, ei, bb->succs)
 112     {
 113       const char *style = "\"solid,bold\"";
 114       const char *color = "black";
 115       int weight = 10;
 116
 117       if (e->flags & EDGE_FAKE)
 118         {
 119           style = "dotted";
 120           color = "green";
 121           weight = 0;
 122         }
 123       else if (e->flags & EDGE_DFS_BACK)
 124         {
 125           style = "\"dotted,bold\"";
 126           color = "blue";
 127           weight = 10;
 128         }
 129       else if (e->flags & EDGE_FALLTHRU)
 130         {
 131           color = "blue";
 132           weight = 100;
 133         }
 134
 135       if (e->flags & EDGE_ABNORMAL)
 136         color = "red";
 137
 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);
 146     }
 147   pp_flush (pp);
 148 }
 149
 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.  */
 154
 155 static void
 156 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
 157 {
 158   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
 159   int i, n;
 160   sbitmap visited;
 161
 162   visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
 163   bitmap_clear (visited);
 164
 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++)
 168     {
 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);
 172     }
 173   free (rpo);
 174
 175   if (n != n_basic_blocks_for_fn (fun))
 176     {
 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);
 182     }
 183
 184   sbitmap_free (visited);
 185 }
 186
 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.  */
 190
 191 static void
 192 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
 193                          struct loop *loop)
 194 {
 195   basic_block *body;
 196   unsigned int i;
 197   const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
 198
 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);
 212
 213   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 214     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 215
 216   if (loop->header == NULL)
 217     return;
 218
 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);
 223
 224   for (i = 0; i < loop->num_nodes; i++)
 225     {
 226       basic_block bb = body[i];
 227       if (bb->loop_father == loop)
 228         draw_cfg_node (pp, funcdef_no, bb);
 229     }
 230
 231   free (body);
 232
 233   if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 234     pp_printf (pp, "\t}\n");
 235 }
 236
 237 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 238    All loop bodys are printed in clusters.  */
 239
 240 static void
 241 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 242 {
 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);
 247 }
 248
 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.)  */
 254
 255 static void
 256 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 257 {
 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);
 262
 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);
 270 }
 271
 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.  */
 276
 277 void
 278 print_graph_cfg (const char *base, struct function *fun)
 279 {
 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);
 295 }
 296
 297 /* Start the dump of a graph.  */
 298 static void
 299 start_graph_dump (FILE *fp, const char *base)
 300 {
 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);
 311 }
 312
 313 /* End the dump of a graph.  */
 314 static void
 315 end_graph_dump (FILE *fp)
 316 {
 317   fputs ("}\n", fp);
 318 }
 319
 320 /* Similar as clean_dump_file, but this time for graph output files.  */
 321 void
 322 clean_graph_dump_file (const char *base)
 323 {
 324   FILE *fp = open_graph_file (base, "w");
 325   start_graph_dump (fp, base);
 326   fclose (fp);
 327 }
 328
 329
 330 /* Do final work on the graph output file.  */
 331 void
 332 finish_graph_dump_file (const char *base)
 333 {
 334   FILE *fp = open_graph_file (base, "a");
 335   end_graph_dump (fp);
 336   fclose (fp);
 337 }