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