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 "sbitmap.h"
  27 #include "predict.h"
  28 #include "tm.h"
  29 #include "hard-reg-set.h"
  30 #include "function.h"
  31 #include "dominance.h"
  32 #include "cfg.h"
  33 #include "cfganal.h"
  34 #include "basic-block.h"
  35 #include "cfgloop.h"
  36 #include "graph.h"
  37 #include "dumpfile.h"
  38 #include "pretty-print.h"
  39
  40 /* DOT files with the .dot extension are recognized as document templates
  41    by a well-known piece of word processing software out of Redmond, WA.
  42    Therefore some recommend using the .gv extension instead.  Obstinately
  43    ignore that recommendation...  */
  44 static const char *const graph_ext = ".dot";
  45
  46 /* Open a file with MODE for dumping our graph to.
  47    Return the file pointer.  */
  48 static FILE *
  49 open_graph_file (const char *base, const char *mode)
  50 {
  51   size_t namelen = strlen (base);
  52   size_t extlen = strlen (graph_ext) + 1;
  53   char *buf = XALLOCAVEC (char, namelen + extlen);
  54   FILE *fp;
  55
  56   memcpy (buf, base, namelen);
  57   memcpy (buf + namelen, graph_ext, extlen);
  58
  59   fp = fopen (buf, mode);
  60   if (fp == NULL)
  61     fatal_error (input_location, "can%'t open %s: %m", buf);
  62
  63   return fp;
  64 }
  65
  66 /* Draw a basic block BB belonging to the function with FUNCDEF_NO
  67    as its unique number.  */
  68 static void
  69 draw_cfg_node (pretty_printer *pp, int funcdef_no, basic_block bb)
  70 {
  71   const char *shape;
  72   const char *fillcolor;
  73
  74   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
  75     {
  76       shape = "Mdiamond";
  77       fillcolor = "white";
  78     }
  79   else
  80     {
  81       shape = "record";
  82       fillcolor =
  83         BB_PARTITION (bb) == BB_HOT_PARTITION ? "lightpink"
  84         : BB_PARTITION (bb) == BB_COLD_PARTITION ? "lightblue"
  85         : "lightgrey";
  86     }
  87
  88   pp_printf (pp,
  89              "\tfn_%d_basic_block_%d "
  90              "[shape=%s,style=filled,fillcolor=%s,label=\"",
  91              funcdef_no, bb->index, shape, fillcolor);
  92
  93   if (bb->index == ENTRY_BLOCK)
  94     pp_string (pp, "ENTRY");
  95   else if (bb->index == EXIT_BLOCK)
  96     pp_string (pp, "EXIT");
  97   else
  98     {
  99       pp_left_brace (pp);
 100       pp_write_text_to_stream (pp);
 101       dump_bb_for_graph (pp, bb);
 102       pp_right_brace (pp);
 103     }
 104
 105   pp_string (pp, "\"];\n\n");
 106   pp_flush (pp);
 107 }
 108
 109 /* Draw all successor edges of a basic block BB belonging to the function
 110    with FUNCDEF_NO as its unique number.  */
 111 static void
 112 draw_cfg_node_succ_edges (pretty_printer *pp, int funcdef_no, basic_block bb)
 113 {
 114   edge e;
 115   edge_iterator ei;
 116   FOR_EACH_EDGE (e, ei, bb->succs)
 117     {
 118       const char *style = "\"solid,bold\"";
 119       const char *color = "black";
 120       int weight = 10;
 121
 122       if (e->flags & EDGE_FAKE)
 123         {
 124           style = "dotted";
 125           color = "green";
 126           weight = 0;
 127         }
 128       else if (e->flags & EDGE_DFS_BACK)
 129         {
 130           style = "\"dotted,bold\"";
 131           color = "blue";
 132           weight = 10;
 133         }
 134       else if (e->flags & EDGE_FALLTHRU)
 135         {
 136           color = "blue";
 137           weight = 100;
 138         }
 139
 140       if (e->flags & EDGE_ABNORMAL)
 141         color = "red";
 142
 143       pp_printf (pp,
 144                  "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 145                  "[style=%s,color=%s,weight=%d,constraint=%s, label=\"[%i%%]\"];\n",
 146                  funcdef_no, e->src->index,
 147                  funcdef_no, e->dest->index,
 148                  style, color, weight,
 149                  (e->flags & (EDGE_FAKE | EDGE_DFS_BACK)) ? "false" : "true",
 150                  e->probability * 100 / REG_BR_PROB_BASE);
 151     }
 152   pp_flush (pp);
 153 }
 154
 155 /* Draw all the basic blocks in the CFG in case loops are not available.
 156    First compute a topological order of the blocks to get a good ranking of
 157    the nodes.  Then, if any nodes are not reachable from ENTRY, add them at
 158    the end.  */
 159
 160 static void
 161 draw_cfg_nodes_no_loops (pretty_printer *pp, struct function *fun)
 162 {
 163   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
 164   int i, n;
 165   sbitmap visited;
 166
 167   visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
 168   bitmap_clear (visited);
 169
 170   n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, true);
 171   for (i = n_basic_blocks_for_fn (fun) - n;
 172        i < n_basic_blocks_for_fn (fun); i++)
 173     {
 174       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
 175       draw_cfg_node (pp, fun->funcdef_no, bb);
 176       bitmap_set_bit (visited, bb->index);
 177     }
 178   free (rpo);
 179
 180   if (n != n_basic_blocks_for_fn (fun))
 181     {
 182       /* Some blocks are unreachable.  We still want to dump them.  */
 183       basic_block bb;
 184       FOR_ALL_BB_FN (bb, fun)
 185         if (! bitmap_bit_p (visited, bb->index))
 186           draw_cfg_node (pp, fun->funcdef_no, bb);
 187     }
 188
 189   sbitmap_free (visited);
 190 }
 191
 192 /* Draw all the basic blocks in LOOP.  Print the blocks in breath-first
 193    order to get a good ranking of the nodes.  This function is recursive:
 194    It first prints inner loops, then the body of LOOP itself.  */
 195
 196 static void
 197 draw_cfg_nodes_for_loop (pretty_printer *pp, int funcdef_no,
 198                          struct loop *loop)
 199 {
 200   basic_block *body;
 201   unsigned int i;
 202   const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
 203
 204   if (loop->header != NULL
 205       && loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 206     pp_printf (pp,
 207                "\tsubgraph cluster_%d_%d {\n"
 208                "\tstyle=\"filled\";\n"
 209                "\tcolor=\"darkgreen\";\n"
 210                "\tfillcolor=\"%s\";\n"
 211                "\tlabel=\"loop %d\";\n"
 212                "\tlabeljust=l;\n"
 213                "\tpenwidth=2;\n",
 214                funcdef_no, loop->num,
 215                fillcolors[(loop_depth (loop) - 1) % 3],
 216                loop->num);
 217
 218   for (struct loop *inner = loop->inner; inner; inner = inner->next)
 219     draw_cfg_nodes_for_loop (pp, funcdef_no, inner);
 220
 221   if (loop->header == NULL)
 222     return;
 223
 224   if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
 225     body = get_loop_body (loop);
 226   else
 227     body = get_loop_body_in_bfs_order (loop);
 228
 229   for (i = 0; i < loop->num_nodes; i++)
 230     {
 231       basic_block bb = body[i];
 232       if (bb->loop_father == loop)
 233         draw_cfg_node (pp, funcdef_no, bb);
 234     }
 235
 236   free (body);
 237
 238   if (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun))
 239     pp_printf (pp, "\t}\n");
 240 }
 241
 242 /* Draw all the basic blocks in the CFG in case the loop tree is available.
 243    All loop bodys are printed in clusters.  */
 244
 245 static void
 246 draw_cfg_nodes (pretty_printer *pp, struct function *fun)
 247 {
 248   if (loops_for_fn (fun))
 249     draw_cfg_nodes_for_loop (pp, fun->funcdef_no, get_loop (fun, 0));
 250   else
 251     draw_cfg_nodes_no_loops (pp, fun);
 252 }
 253
 254 /* Draw all edges in the CFG.  Retreating edges are drawin as not
 255    constraining, this makes the layout of the graph better.
 256    (??? Calling mark_dfs_back may change the compiler's behavior when
 257    dumping, but computing back edges here for ourselves is also not
 258    desirable.)  */
 259
 260 static void
 261 draw_cfg_edges (pretty_printer *pp, struct function *fun)
 262 {
 263   basic_block bb;
 264   mark_dfs_back_edges ();
 265   FOR_ALL_BB_FN (bb, cfun)
 266     draw_cfg_node_succ_edges (pp, fun->funcdef_no, bb);
 267
 268   /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 269   pp_printf (pp,
 270              "\tfn_%d_basic_block_%d:s -> fn_%d_basic_block_%d:n "
 271              "[style=\"invis\",constraint=true];\n",
 272              fun->funcdef_no, ENTRY_BLOCK,
 273              fun->funcdef_no, EXIT_BLOCK);
 274   pp_flush (pp);
 275 }
 276
 277 /* Print a graphical representation of the CFG of function FUN.
 278    First print all basic blocks.  Draw all edges at the end to get
 279    subgraphs right for GraphViz, which requires nodes to be defined
 280    before edges to cluster nodes properly.  */
 281
 282 void
 283 print_graph_cfg (const char *base, struct function *fun)
 284 {
 285   const char *funcname = function_name (fun);
 286   FILE *fp = open_graph_file (base, "a");
 287   pretty_printer graph_slim_pp;
 288   graph_slim_pp.buffer->stream = fp;
 289   pretty_printer *const pp = &graph_slim_pp;
 290   pp_printf (pp, "subgraph \"cluster_%s\" {\n"
 291                  "\tstyle=\"dashed\";\n"
 292                  "\tcolor=\"black\";\n"
 293                  "\tlabel=\"%s ()\";\n",
 294                  funcname, funcname);
 295   draw_cfg_nodes (pp, fun);
 296   draw_cfg_edges (pp, fun);
 297   pp_printf (pp, "}\n");
 298   pp_flush (pp);
 299   fclose (fp);
 300 }
 301
 302 /* Start the dump of a graph.  */
 303 static void
 304 start_graph_dump (FILE *fp, const char *base)
 305 {
 306   pretty_printer graph_slim_pp;
 307   graph_slim_pp.buffer->stream = fp;
 308   pretty_printer *const pp = &graph_slim_pp;
 309   pp_string (pp, "digraph \"");
 310   pp_write_text_to_stream (pp);
 311   pp_string (pp, base);
 312   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 313   pp_string (pp, "\" {\n");
 314   pp_string (pp, "overlap=false;\n");
 315   pp_flush (pp);
 316 }
 317
 318 /* End the dump of a graph.  */
 319 static void
 320 end_graph_dump (FILE *fp)
 321 {
 322   fputs ("}\n", fp);
 323 }
 324
 325 /* Similar as clean_dump_file, but this time for graph output files.  */
 326 void
 327 clean_graph_dump_file (const char *base)
 328 {
 329   FILE *fp = open_graph_file (base, "w");
 330   start_graph_dump (fp, base);
 331   fclose (fp);
 332 }
 333
 334
 335 /* Do final work on the graph output file.  */
 336 void
 337 finish_graph_dump_file (const char *base)
 338 {
 339   FILE *fp = open_graph_file (base, "a");
 340   end_graph_dump (fp);
 341   fclose (fp);
 342 }