gcc/graph.c

   1 /* Output routines for graphical representation.
   2    Copyright (C) 1998-2017 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
 160   auto_sbitmap visited (last_basic_block_for_fn (cfun));
 161   bitmap_clear (visited);
 162
 163   n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
 164   for (i = n_basic_blocks_for_fn (fun) - n;
 165        i < n_basic_blocks_for_fn (fun); i++)
 166     {
 167       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
 168       draw_cfg_node (pp, fun->funcdef_no, bb);
 169       bitmap_set_bit (visited, bb->index);
 170     }
 171   free (rpo);
 172
 173   if (n != n_basic_blocks_for_fn (fun))
 174     {
 175       /* Some blocks are unreachable.  We still want to dump them.  */
 176       basic_block bb;
 177       FOR_ALL_BB_FN (bb, fun)
 178         if (! bitmap_bit_p (visited, bb->index))
 179           draw_cfg_node (pp, fun->funcdef_no, bb);
 180     }
 181 }
 182
 183 /* Draw all the basic blocks in LOOP.  Print the blocks in breath-first
 184    order to get a good ranking of the nodes.  This function is recursive:
 185    It first prints inner loops, then the body of LOOP itself.  */
 186
 187 static void
 188 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
 189                          struct loop *loop)
 190 {
 191   basic_block *body;
 192   unsigned int i;
 193   const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
 194
 195   if (loop->header != NULL
 196       && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 197     pp_printf (pp,
 198                "\tsubgraph cluster_%d_%d {\n"
 199                "\tstyle=\"filled\";\n"
 200                "\tcolor=\"darkgreen\";\n"
 201                "\tfillcolor=\"%s\";\n"
 202                "\tlabel=\"loop %d\";\n"
 203                "\tlabeljust=l;\n"
 204                "\tpenwidth=2;\n",
 205                funcdef_no, loop->num,
 206                fillcolors[(loop_depth (loop) - 1) % 3],
 207                loop->num);
 208
 209   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 210     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 211
 212   if (loop->header == NULL)
 213     return;
 214
 215   if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
 216     body = get_loop_body (loop);
 217   else
 218     body = get_loop_body_in_bfs_order (loop);
 219
 220   for (i = 0; i < loop->num_nodes; i++)
 221     {
 222       basic_block bb = body[i];
 223       if (bb->loop_father == loop)
 224         draw_cfg_node (pp, funcdef_no, bb);
 225     }
 226
 227   free (body);
 228
 229   if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 230     pp_printf (pp, "\t}\n");
 231 }
 232
 233 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 234    All loop bodys are printed in clusters.  */
 235
 236 static void
 237 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 238 {
 239   if (loops_for_fn (fun))
 240     draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
 241   else
 242     draw_cfg_nodes_no_loops (pp, fun);
 243 }
 244
 245 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 246    constraining, this makes the layout of the graph better.
 247    (??? Calling mark_dfs_back may change the compiler's behavior when
 248    dumping, but computing back edges here for ourselves is also not
 249    desirable.)  */
 250
 251 static void
 252 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 253 {
 254   basic_block bb;
 255   mark_dfs_back_edges ();
 256   FOR_ALL_BB_FN (bb, cfun)
 257     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 258
 259   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 260   pp_printf (pp,
 261              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 262              "[style=\"invis\",constraint=true];\n",
 263              fun->funcdef_no, ENTRY_BLOCK,
 264              fun->funcdef_no, EXIT_BLOCK);
 265   pp_flush (pp);
 266 }
 267
 268 /* Print a graphical representation of the CFG of function FUN.
 269    First print all basic blocks.  Draw all edges at the end to get
 270    subgraphs right for GraphViz, which requires nodes to be defined
 271    before edges to cluster nodes properly.  */
 272
 273 void DEBUG_FUNCTION
 274 print_graph_cfg (FILE *fp, struct function *fun)
 275 {
 276   pretty_printer graph_slim_pp;
 277   graph_slim_pp.buffer->stream = fp;
 278   pretty_printer *const pp = &graph_slim_pp;
 279   const char *funcname = function_name (fun);
 280   pp_printf (pp, "subgraph \"cluster_%s\" {\n"
 281                  "\tstyle=\"dashed\";\n"
 282                  "\tcolor=\"black\";\n"
 283                  "\tlabel=\"%s ()\";\n",
 284                  funcname, funcname);
 285   draw_cfg_nodes (pp, fun);
 286   draw_cfg_edges (pp, fun);
 287   pp_printf (pp, "}\n");
 288   pp_flush (pp);
 289 }
 290
 291 /* Overload with additional flag argument.  */
 292
 293 void DEBUG_FUNCTION
 294 print_graph_cfg (FILE *fp, struct function *fun, dump_flags_t flags)
 295 {
 296   dump_flags_t saved_dump_flags = dump_flags;
 297   dump_flags = flags;
 298   print_graph_cfg (fp, fun);
 299   dump_flags = saved_dump_flags;
 300 }
 301
 302
 303 /* Print a graphical representation of the CFG of function FUN.
 304    First print all basic blocks.  Draw all edges at the end to get
 305    subgraphs right for GraphViz, which requires nodes to be defined
 306    before edges to cluster nodes properly.  */
 307
 308 void
 309 print_graph_cfg (const char *base, struct function *fun)
 310 {
 311   FILE *fp = open_graph_file (base, "a");
 312   print_graph_cfg (fp, fun);
 313   fclose (fp);
 314 }
 315
 316 /* Start the dump of a graph.  */
 317 static void
 318 start_graph_dump (FILE *fp, const char *base)
 319 {
 320   pretty_printer graph_slim_pp;
 321   graph_slim_pp.buffer->stream = fp;
 322   pretty_printer *const pp = &graph_slim_pp;
 323   pp_string (pp, "digraph \"");
 324   pp_write_text_to_stream (pp);
 325   pp_string (pp, base);
 326   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 327   pp_string (pp, "\" {\n");
 328   pp_string (pp, "overlap=false;\n");
 329   pp_flush (pp);
 330 }
 331
 332 /* End the dump of a graph.  */
 333 static void
 334 end_graph_dump (FILE *fp)
 335 {
 336   fputs ("}\n", fp);
 337 }
 338
 339 /* Similar as clean_dump_file, but this time for graph output files.  */
 340 void
 341 clean_graph_dump_file (const char *base)
 342 {
 343   FILE *fp = open_graph_file (base, "w");
 344   start_graph_dump (fp, base);
 345   fclose (fp);
 346 }
 347
 348
 349 /* Do final work on the graph output file.  */
 350 void
 351 finish_graph_dump_file (const char *base)
 352 {
 353   FILE *fp = open_graph_file (base, "a");
 354   end_graph_dump (fp);
 355   fclose (fp);
 356 }