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