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