gcc/graph.c

   1 /* Output routines for graphical representation.
   2    Copyright (C) 1998-2013 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 "sbitmap.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "graph.h"
  30 #include "dumpfile.h"
  31 #include "pretty-print.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 ("can%'t open %s: %m", buf);
  55
  56   return fp;
  57 }
  58
  59 /* Return a pretty-print buffer for output to file FP.  */
  60
  61 static pretty_printer *
  62 init_graph_slim_pretty_print (FILE *fp)
  63 {
  64   static bool initialized = false;
  65   static pretty_printer graph_slim_pp;
  66
  67   if (! initialized)
  68     {
  69       pp_construct (&graph_slim_pp, /*prefix=*/NULL, /*linewidth=*/0);
  70       initialized = true;
  71     }
  72   else
  73     gcc_assert (! pp_last_position_in_text (&graph_slim_pp));
  74
  75   graph_slim_pp.buffer->stream = fp;
  76   return &graph_slim_pp;
  77 }
  78
  79 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
  80    as its unique number.  */
  81 static void
  82 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
  83 {
  84   const char *shape;
  85   const char *fillcolor;
  86
  87   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
  88     {
  89       shape = "Mdiamond";
  90       fillcolor = "white";
  91     }
  92   else
  93     {
  94       shape = "record";
  95       fillcolor =
  96         BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
  97         : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
  98         : "lightgrey";
  99     }
 100
 101   pp_printf (pp,
 102              "\tfn_%d_basic_block_%d "
 103              "[shape=%s,style=filled,fillcolor=%s,label=\"",
 104              funcdef_no, bb->index, shape, fillcolor);
 105
 106   if (bb->index == ENTRY_BLOCK)
 107     pp_string (pp, "ENTRY");
 108   else if (bb->index == EXIT_BLOCK)
 109     pp_string (pp, "EXIT");
 110   else
 111     {
 112       pp_character (pp, '{');
 113       pp_write_text_to_stream (pp);
 114       dump_bb_for_graph (pp, bb);
 115       pp_character (pp, '}');
 116     }
 117
 118   pp_string (pp, "\"];\n\n");
 119   pp_flush (pp);
 120 }
 121
 122 /* Draw all successor edges of a basic block BB belonging to the function
 123    with FUNCDEF_NO as its unique number.  */
 124 static void
 125 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
 126 {
 127   edge e;
 128   edge_iterator ei;
 129   FOR_EACH_EDGE (e, ei, bb->succs)
 130     {
 131       const char *style = "\"solid,bold\"";
 132       const char *color = "black";
 133       int weight = 10;
 134
 135       if (e->flags & EDGE_FAKE)
 136         {
 137           style = "dotted";
 138           color = "green";
 139           weight = 0;
 140         }
 141       else if (e->flags & EDGE_DFS_BACK)
 142         {
 143           style = "\"dotted,bold\"";
 144           color = "blue";
 145           weight = 10;
 146         }
 147       else if (e->flags & EDGE_FALLTHRU)
 148         {
 149           color = "blue";
 150           weight = 100;
 151         }
 152
 153       if (e->flags & EDGE_ABNORMAL)
 154         color = "red";
 155
 156       pp_printf (pp,
 157                  "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 158                  "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
 159                  funcdef_no, e->src->index,
 160                  funcdef_no, e->dest->index,
 161                  style, color, weight,
 162                  (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
 163                  e->probability * 100 / REG_BR_PROB_BASE);
 164     }
 165   pp_flush (pp);
 166 }
 167
 168 /* Draw all the basic blocks in the CFG in case loops are not available.
 169    First compute a topological order of the blocks to get a good ranking of
 170    the nodes.  Then, if any nodes are not reachable from ENTRY, add them at
 171    the end.  */
 172
 173 static void
 174 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
 175 {
 176   int *rpo = XNEWVEC (int, n_basic_blocks_for_function (fun));
 177   int i, n;
 178   sbitmap visited;
 179
 180   visited = sbitmap_alloc (last_basic_block);
 181   bitmap_clear (visited);
 182
 183   /* FIXME: pre_and_rev_post_order_compute only works if fun == cfun.  */
 184   n = pre_and_rev_post_order_compute (NULL, rpo, true);
 185   for (i = 0; i < n; i++)
 186     {
 187       basic_block bb = BASIC_BLOCK (rpo[i]);
 188       draw_cfg_node (pp, fun->funcdef_no, bb);
 189       bitmap_set_bit (visited, bb->index);
 190     }
 191   free (rpo);
 192
 193   if (n != n_basic_blocks_for_function (fun))
 194     {
 195       /* Some blocks are unreachable.  We still want to dump them.  */
 196       basic_block bb;
 197       FOR_ALL_BB_FN (bb, fun)
 198         if (! bitmap_bit_p (visited, bb->index))
 199           draw_cfg_node (pp, fun->funcdef_no, bb);
 200     }
 201
 202   sbitmap_free (visited);
 203 }
 204
 205 /* Draw all the basic blocks in LOOP.  Print the blocks in breath-first
 206    order to get a good ranking of the nodes.  This function is recursive:
 207    It first prints inner loops, then the body of LOOP itself.  */
 208
 209 static void
 210 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
 211                          struct loop *loop)
 212 {
 213   basic_block *body;
 214   unsigned int i;
 215   const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
 216
 217   if (loop->header != NULL
 218       && loop->latch != EXIT_BLOCK_PTR)
 219     pp_printf (pp,
 220                "\tsubgraph cluster_%d_%d {\n"
 221                "\tstyle=\"filled\";\n"
 222                "\tcolor=\"darkgreen\";\n"
 223                "\tfillcolor=\"%s\";\n"
 224                "\tlabel=\"loop %d\";\n"
 225                "\tlabeljust=l;\n"
 226                "\tpenwidth=2;\n",
 227                funcdef_no, loop->num,
 228                fillcolors[(loop_depth (loop) - 1) % 3],
 229                loop->num);
 230
 231   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 232     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 233
 234   if (loop->header == NULL)
 235     return;
 236
 237   if (loop->latch == EXIT_BLOCK_PTR)
 238     body = get_loop_body (loop);
 239   else
 240     body = get_loop_body_in_bfs_order (loop);
 241
 242   for (i = 0; i < loop->num_nodes; i++)
 243     {
 244       basic_block bb = body[i];
 245       if (bb->loop_father == loop)
 246         draw_cfg_node (pp, funcdef_no, bb);
 247     }
 248
 249   free (body);
 250
 251   if (loop->latch != EXIT_BLOCK_PTR)
 252     pp_printf (pp, "\t}\n");
 253 }
 254
 255 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 256    All loop bodys are printed in clusters.  */
 257
 258 static void
 259 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 260 {
 261   /* ??? This x_current_loops should be enapsulated.  */
 262   if (fun->x_current_loops)
 263     draw_cfg_nodes_for_loop (pp, fun->funcdef_no,
 264                              fun->x_current_loops->tree_root);
 265   else
 266     draw_cfg_nodes_no_loops (pp, fun);
 267 }
 268
 269 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 270    constraining, this makes the layout of the graph better.
 271    (??? Calling mark_dfs_back may change the compiler's behavior when
 272    dumping, but computing back edges here for ourselves is also not
 273    desirable.)  */
 274
 275 static void
 276 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 277 {
 278   basic_block bb;
 279   mark_dfs_back_edges ();
 280   FOR_ALL_BB (bb)
 281     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 282
 283   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 284   pp_printf (pp,
 285              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 286              "[style=\"invis\",constraint=true];\n",
 287              fun->funcdef_no, ENTRY_BLOCK,
 288              fun->funcdef_no, EXIT_BLOCK);
 289   pp_flush (pp);
 290 }
 291
 292 /* Print a graphical representation of the CFG of function FUN.
 293    First print all basic blocks.  Draw all edges at the end to get
 294    subgraphs right for GraphViz, which requires nodes to be defined
 295    before edges to cluster nodes properly.  */
 296
 297 void
 298 print_graph_cfg (const char *base, struct function *fun)
 299 {
 300   const char *funcname = function_name (fun);
 301   FILE *fp = open_graph_file (base, "a");
 302   pretty_printer *pp = init_graph_slim_pretty_print (fp);
 303   pp_printf (pp, "subgraph \"%s\" {\n"
 304                  "\tcolor=\"black\";\n"
 305                  "\tlabel=\"%s\";\n",
 306                  funcname, funcname);
 307   draw_cfg_nodes (pp, fun);
 308   draw_cfg_edges (pp, fun);
 309   pp_printf (pp, "}\n");
 310   pp_flush (pp);
 311   fclose (fp);
 312 }
 313
 314 /* Start the dump of a graph.  */
 315 static void
 316 start_graph_dump (FILE *fp, const char *base)
 317 {
 318   pretty_printer *pp = init_graph_slim_pretty_print (fp);
 319   pp_string (pp, "digraph \"");
 320   pp_write_text_to_stream (pp);
 321   pp_string (pp, base);
 322   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 323   pp_string (pp, "\" {\n");
 324   pp_string (pp, "overlap=false;\n");
 325   pp_flush (pp);
 326 }
 327
 328 /* End the dump of a graph.  */
 329 static void
 330 end_graph_dump (FILE *fp)
 331 {
 332   fputs ("}\n", fp);
 333 }
 334
 335 /* Similar as clean_dump_file, but this time for graph output files.  */
 336 void
 337 clean_graph_dump_file (const char *base)
 338 {
 339   FILE *fp = open_graph_file (base, "w");
 340   start_graph_dump (fp, base);
 341   fclose (fp);
 342 }
 343
 344
 345 /* Do final work on the graph output file.  */
 346 void
 347 finish_graph_dump_file (const char *base)
 348 {
 349   FILE *fp = open_graph_file (base, "a");
 350   end_graph_dump (fp);
 351   fclose (fp);
 352 }