gcc/graph.c

   1 /* Output routines for graphical representation.
   2    Copyright (C) 1998-2012
   3    Free Software Foundation, Inc.
   4    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
   5    Rewritten for DOT output by Steven Bosscher, 2012.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "diagnostic-core.h" /* for fatal_error */
  27 #include "sbitmap.h"
  28 #include "basic-block.h"
  29 #include "cfgloop.h"
  30 #include "graph.h"
  31 #include "dumpfile.h"
  32 #include "pretty-print.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...  */
  38 static const char *const graph_ext = ".dot";
  39
  40 /* Open a file with MODE for dumping our graph to.
  41    Return the file pointer.  */
  42 static FILE *
  43 open_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 ("can%'t open %s: %m", buf);
  56
  57   return fp;
  58 }
  59
  60 /* Return a pretty-print buffer for output to file FP.  */
  61
  62 static pretty_printer *
  63 init_graph_slim_pretty_print (FILE *fp)
  64 {
  65   static bool initialized = false;
  66   static pretty_printer graph_slim_pp;
  67
  68   if (! initialized)
  69     {
  70       pp_construct (&graph_slim_pp, /*prefix=*/NULL, /*linewidth=*/0);
  71       initialized = true;
  72     }
  73   else
  74     gcc_assert (! pp_last_position_in_text (&graph_slim_pp));
  75
  76   graph_slim_pp.buffer->stream = fp;
  77   return &graph_slim_pp;
  78 }
  79
  80 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
  81    as its unique number.  */
  82 static void
  83 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
  84 {
  85   const char *shape;
  86   const char *fillcolor;
  87
  88   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
  89     {
  90       shape = "Mdiamond";
  91       fillcolor = "white";
  92     }
  93   else
  94     {
  95       shape = "record";
  96       fillcolor =
  97         BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
  98         : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
  99         : "lightgrey";
 100     }
 101
 102   pp_printf (pp,
 103              "\tfn_%d_basic_block_%d "
 104              "[shape=%s,style=filled,fillcolor=%s,label=\"",
 105              funcdef_no, bb->index, shape, fillcolor);
 106
 107   if (bb->index == ENTRY_BLOCK)
 108     pp_string (pp, "ENTRY");
 109   else if (bb->index == EXIT_BLOCK)
 110     pp_string (pp, "EXIT");
 111   else
 112     {
 113       pp_character (pp, '{');
 114       pp_write_text_to_stream (pp);
 115       dump_bb_for_graph (pp, bb);
 116       pp_character (pp, '}');
 117     }
 118
 119   pp_string (pp, "\"];\n\n");
 120   pp_flush (pp);
 121 }
 122
 123 /* Draw all successor edges of a basic block BB belonging to the function
 124    with FUNCDEF_NO as its unique number.  */
 125 static void
 126 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
 127 {
 128   edge e;
 129   edge_iterator ei;
 130   FOR_EACH_EDGE (e, ei, bb->succs)
 131     {
 132       const char *style = "\"solid,bold\"";
 133       const char *color = "black";
 134       int weight = 10;
 135
 136       if (e->flags & EDGE_FAKE)
 137         {
 138           style = "dotted";
 139           color = "green";
 140           weight = 0;
 141         }
 142       else if (e->flags & EDGE_DFS_BACK)
 143         {
 144           style = "\"dotted,bold\"";
 145           color = "blue";
 146           weight = 10;
 147         }
 148       else if (e->flags & EDGE_FALLTHRU)
 149         {
 150           color = "blue";
 151           weight = 100;
 152         }
 153
 154       if (e->flags & EDGE_ABNORMAL)
 155         color = "red";
 156
 157       pp_printf (pp,
 158                  "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 159                  "[style=%s,color=%s,weight=%d,constraint=%s];\n",
 160                  funcdef_no, e->src->index,
 161                  funcdef_no, e->dest->index,
 162                  style, color, weight,
 163                  (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true");
 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->latch != EXIT_BLOCK_PTR)
 218     pp_printf (pp,
 219                "\tsubgraph cluster_%d_%d {\n"
 220                "\tstyle=\"filled\";\n"
 221                "\tcolor=\"darkgreen\";\n"
 222                "\tfillcolor=\"%s\";\n"
 223                "\tlabel=\"loop %d\";\n"
 224                "\tlabeljust=l;\n"
 225                "\tpenwidth=2;\n",
 226                funcdef_no, loop->num,
 227                fillcolors[(loop_depth (loop) - 1) % 3],
 228                loop->num);
 229
 230   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 231     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 232
 233   if (loop->latch == EXIT_BLOCK_PTR)
 234     body = get_loop_body (loop);
 235   else
 236     body = get_loop_body_in_bfs_order (loop);
 237
 238   for (i = 0; i < loop->num_nodes; i++)
 239     {
 240       basic_block bb = body[i];
 241       if (bb->loop_father == loop)
 242         draw_cfg_node (pp, funcdef_no, bb);
 243     }
 244
 245   free (body);
 246
 247   if (loop->latch != EXIT_BLOCK_PTR)
 248     pp_printf (pp, "\t}\n");
 249 }
 250
 251 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 252    All loop bodys are printed in clusters.  */
 253
 254 static void
 255 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 256 {
 257   /* ??? This x_current_loops should be enapsulated.  */
 258   if (fun->x_current_loops)
 259     draw_cfg_nodes_for_loop (pp, fun->funcdef_no,
 260                              fun->x_current_loops->tree_root);
 261   else
 262     draw_cfg_nodes_no_loops (pp, fun);
 263 }
 264
 265 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 266    constraining, this makes the layout of the graph better.
 267    (??? Calling mark_dfs_back may change the compiler's behavior when
 268    dumping, but computing back edges here for ourselves is also not
 269    desirable.)  */
 270
 271 static void
 272 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 273 {
 274   basic_block bb;
 275   mark_dfs_back_edges ();
 276   FOR_ALL_BB (bb)
 277     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 278
 279   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 280   pp_printf (pp,
 281              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 282              "[style=\"invis\",constraint=true];\n",
 283              fun->funcdef_no, ENTRY_BLOCK,
 284              fun->funcdef_no, EXIT_BLOCK);
 285   pp_flush (pp);
 286 }
 287
 288 /* Print a graphical representation of the CFG of function FUN.
 289    First print all basic blocks.  Draw all edges at the end to get
 290    subgraphs right for GraphViz, which requires nodes to be defined
 291    before edges to cluster nodes properly.  */
 292
 293 void
 294 print_graph_cfg (const char *base, struct function *fun)
 295 {
 296   const char *funcname = function_name (fun);
 297   FILE *fp = open_graph_file (base, "a");
 298   pretty_printer *pp = init_graph_slim_pretty_print (fp);
 299   pp_printf (pp, "subgraph \"%s\" {\n"
 300                  "\tcolor=\"black\";\n"
 301                  "\tlabel=\"%s\";\n",
 302                  funcname, funcname);
 303   draw_cfg_nodes (pp, fun);
 304   draw_cfg_edges (pp, fun);
 305   pp_printf (pp, "}\n");
 306   pp_flush (pp);
 307   fclose (fp);
 308 }
 309
 310 /* Start the dump of a graph.  */
 311 static void
 312 start_graph_dump (FILE *fp)
 313 {
 314   fputs ("digraph \"\" {\n"
 315          "overlap=false;\n",
 316          fp);
 317 }
 318
 319 /* End the dump of a graph.  */
 320 static void
 321 end_graph_dump (FILE *fp)
 322 {
 323   fputs ("}\n", fp);
 324 }
 325
 326 /* Similar as clean_dump_file, but this time for graph output files.  */
 327 void
 328 clean_graph_dump_file (const char *base)
 329 {
 330   FILE *fp = open_graph_file (base, "w");
 331   start_graph_dump (fp);
 332   fclose (fp);
 333 }
 334
 335
 336 /* Do final work on the graph output file.  */
 337 void
 338 finish_graph_dump_file (const char *base)
 339 {
 340   FILE *fp = open_graph_file (base, "a");
 341   end_graph_dump (fp);
 342   fclose (fp);
 343 }