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