gcc/graph.c

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