gcc/graph.c

   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 (cfun));
 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 (cfun, 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   if (loops_for_fn (fun))
 252     draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
 253   else
 254     draw_cfg_nodes_no_loops (pp, fun);
 255 }
 256
 257 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 258    constraining, this makes the layout of the graph better.  */
 259
 260 static void
 261 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 262 {
 263   basic_block bb;
 264
 265   /* Save EDGE_DFS_BACK flag to dfs_back.  */
 266   auto_bitmap dfs_back;
 267   edge e;
 268   edge_iterator ei;
 269   unsigned int idx = 0;
 270   FOR_EACH_BB_FN (bb, cfun)
 271     FOR_EACH_EDGE (e, ei, bb->succs)
 272       {
 273         if (e->flags & EDGE_DFS_BACK)
 274           bitmap_set_bit (dfs_back, idx);
 275         idx++;
 276       }
 277
 278   mark_dfs_back_edges ();
 279   FOR_ALL_BB_FN (bb, cfun)
 280     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 281
 282   /* Restore EDGE_DFS_BACK flag from dfs_back.  */
 283   idx = 0;
 284   FOR_EACH_BB_FN (bb, cfun)
 285     FOR_EACH_EDGE (e, ei, bb->succs)
 286       {
 287         if (bitmap_bit_p (dfs_back, idx))
 288           e->flags |= EDGE_DFS_BACK;
 289         else
 290           e->flags &= ~EDGE_DFS_BACK;
 291         idx++;
 292       }
 293
 294   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 295   pp_printf (pp,
 296              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 297              "[style=\"invis\",constraint=true];\n",
 298              fun->funcdef_no, ENTRY_BLOCK,
 299              fun->funcdef_no, EXIT_BLOCK);
 300   pp_flush (pp);
 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 DEBUG_FUNCTION
 309 print_graph_cfg (FILE *fp, struct function *fun)
 310 {
 311   pretty_printer graph_slim_pp;
 312   graph_slim_pp.buffer->stream = fp;
 313   pretty_printer *const pp = &graph_slim_pp;
 314   const char *funcname = function_name (fun);
 315   pp_printf (pp, "subgraph \"cluster_%s\" {\n"
 316                  "\tstyle=\"dashed\";\n"
 317                  "\tcolor=\"black\";\n"
 318                  "\tlabel=\"%s ()\";\n",
 319                  funcname, funcname);
 320   draw_cfg_nodes (pp, fun);
 321   draw_cfg_edges (pp, fun);
 322   pp_printf (pp, "}\n");
 323   pp_flush (pp);
 324 }
 325
 326 /* Overload with additional flag argument.  */
 327
 328 void DEBUG_FUNCTION
 329 print_graph_cfg (FILE *fp, struct function *fun, dump_flags_t flags)
 330 {
 331   dump_flags_t saved_dump_flags = dump_flags;
 332   dump_flags = flags;
 333   print_graph_cfg (fp, fun);
 334   dump_flags = saved_dump_flags;
 335 }
 336
 337
 338 /* Print a graphical representation of the CFG of function FUN.
 339    First print all basic blocks.  Draw all edges at the end to get
 340    subgraphs right for GraphViz, which requires nodes to be defined
 341    before edges to cluster nodes properly.  */
 342
 343 void
 344 print_graph_cfg (const char *base, struct function *fun)
 345 {
 346   FILE *fp = open_graph_file (base, "a");
 347   print_graph_cfg (fp, fun);
 348   fclose (fp);
 349 }
 350
 351 /* Start the dump of a graph.  */
 352 static void
 353 start_graph_dump (FILE *fp, const char *base)
 354 {
 355   pretty_printer graph_slim_pp;
 356   graph_slim_pp.buffer->stream = fp;
 357   pretty_printer *const pp = &graph_slim_pp;
 358   pp_string (pp, "digraph \"");
 359   pp_write_text_to_stream (pp);
 360   pp_string (pp, base);
 361   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 362   pp_string (pp, "\" {\n");
 363   pp_string (pp, "overlap=false;\n");
 364   pp_flush (pp);
 365 }
 366
 367 /* End the dump of a graph.  */
 368 static void
 369 end_graph_dump (FILE *fp)
 370 {
 371   fputs ("}\n", fp);
 372 }
 373
 374 /* Similar as clean_dump_file, but this time for graph output files.  */
 375 void
 376 clean_graph_dump_file (const char *base)
 377 {
 378   FILE *fp = open_graph_file (base, "w");
 379   start_graph_dump (fp, base);
 380   fclose (fp);
 381 }
 382
 383
 384 /* Do final work on the graph output file.  */
 385 void
 386 finish_graph_dump_file (const char *base)
 387 {
 388   FILE *fp = open_graph_file (base, "a");
 389   end_graph_dump (fp);
 390   fclose (fp);
 391 }
 392
 393 #if __GNUC__ >= 10
 394 #  pragma GCC diagnostic pop
 395 #endif