gcc/graph.c

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