gcc/graph.cc

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