gcc/analyzer/supergraph.cc

   1 /* "Supergraph" classes that combine CFGs and callgraph into one digraph.
   2    Copyright (C) 2019-2020 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "tm.h"
  26 #include "toplev.h"
  27 #include "hash-table.h"
  28 #include "vec.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "function.h"
  32 #include "gimple-fold.h"
  33 #include "tree-eh.h"
  34 #include "gimple-expr.h"
  35 #include "is-a.h"
  36 #include "timevar.h"
  37 #include "gimple.h"
  38 #include "gimple-iterator.h"
  39 #include "gimple-pretty-print.h"
  40 #include "tree-pretty-print.h"
  41 #include "graphviz.h"
  42 #include "cgraph.h"
  43 #include "tree-dfa.h"
  44 #include "cfganal.h"
  45 #include "function.h"
  46 #include "json.h"
  47 #include "analyzer/analyzer.h"
  48 #include "ordered-hash-map.h"
  49 #include "options.h"
  50 #include "cgraph.h"
  51 #include "cfg.h"
  52 #include "digraph.h"
  53 #include "analyzer/supergraph.h"
  54 #include "analyzer/analyzer-logging.h"
  55
  56 #if ENABLE_ANALYZER
  57
  58 namespace ana {
  59
  60 /* Get the function of the ultimate alias target being called at EDGE,
  61    if any.  */
  62
  63 static function *
  64 get_ultimate_function_for_cgraph_edge (cgraph_edge *edge)
  65 {
  66   cgraph_node *ultimate_node = edge->callee->ultimate_alias_target ();
  67   if (!ultimate_node)
  68     return NULL;
  69   return ultimate_node->get_fun ();
  70 }
  71
  72 /* Get the cgraph_edge, but only if there's an underlying function body.  */
  73
  74 cgraph_edge *
  75 supergraph_call_edge (function *fun, gimple *stmt)
  76 {
  77   gcall *call = dyn_cast<gcall *> (stmt);
  78   if (!call)
  79     return NULL;
  80   cgraph_edge *edge = cgraph_node::get (fun->decl)->get_edge (stmt);
  81   if (!edge)
  82     return NULL;
  83   if (!edge->callee)
  84     return NULL; /* e.g. for a function pointer.  */
  85   if (!get_ultimate_function_for_cgraph_edge (edge))
  86     return NULL;
  87   return edge;
  88 }
  89
  90 /* supergraph's ctor.  Walk the callgraph, building supernodes for each
  91    CFG basic block, splitting the basic blocks at callsites.  Join
  92    together the supernodes with interprocedural and intraprocedural
  93    superedges as appropriate.  */
  94
  95 supergraph::supergraph (logger *logger)
  96 {
  97   auto_timevar tv (TV_ANALYZER_SUPERGRAPH);
  98
  99   LOG_FUNC (logger);
 100
 101   /* First pass: make supernodes.  */
 102   {
 103     /* Sort the cgraph_nodes?  */
 104     cgraph_node *node;
 105     FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 106     {
 107       function *fun = node->get_fun ();
 108
 109       /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
 110          the supergraph (by doing it per-function).  */
 111       auto_cfun sentinel (fun);
 112       mark_dfs_back_edges ();
 113
 114       const int start_idx = m_nodes.length ();
 115
 116       basic_block bb;
 117       FOR_ALL_BB_FN (bb, fun)
 118         {
 119           /* The initial supernode for the BB gets the phi nodes (if any).  */
 120           supernode *node_for_stmts = add_node (fun, bb, NULL, phi_nodes (bb));
 121           m_bb_to_initial_node.put (bb, node_for_stmts);
 122           for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
 123                gsi_next (&gpi))
 124             {
 125               gimple *stmt = gsi_stmt (gpi);
 126               m_stmt_to_node_t.put (stmt, node_for_stmts);
 127             }
 128
 129           /* Append statements from BB to the current supernode, splitting
 130              them into a new supernode at each call site; such call statements
 131              appear in both supernodes (representing call and return).  */
 132           gimple_stmt_iterator gsi;
 133           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 134             {
 135               gimple *stmt = gsi_stmt (gsi);
 136               node_for_stmts->m_stmts.safe_push (stmt);
 137               m_stmt_to_node_t.put (stmt, node_for_stmts);
 138               if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
 139                 {
 140                   m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts);
 141                   node_for_stmts = add_node (fun, bb, as_a <gcall *> (stmt), NULL);
 142                   m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
 143                 }
 144             }
 145
 146           m_bb_to_final_node.put (bb, node_for_stmts);
 147         }
 148
 149       const unsigned num_snodes = m_nodes.length () - start_idx;
 150       m_function_to_num_snodes.put (fun, num_snodes);
 151
 152       if (logger)
 153         {
 154           const int end_idx = m_nodes.length () - 1;
 155           logger->log ("SN: %i...%i: function %qD",
 156                        start_idx, end_idx, fun->decl);
 157         }
 158     }
 159   }
 160
 161   /* Second pass: make superedges.  */
 162   {
 163     /* Make superedges for CFG edges.  */
 164     for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
 165          iter != m_bb_to_final_node.end ();
 166          ++iter)
 167       {
 168         basic_block bb = (*iter).first;
 169         supernode *src_supernode = (*iter).second;
 170
 171         ::edge cfg_edge;
 172         int idx;
 173         if (bb->succs)
 174           FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
 175             {
 176               basic_block dest_cfg_block = cfg_edge->dest;
 177               supernode *dest_supernode
 178                 = *m_bb_to_initial_node.get (dest_cfg_block);
 179               cfg_superedge *cfg_sedge
 180                 = add_cfg_edge (src_supernode, dest_supernode, cfg_edge, idx);
 181               m_cfg_edge_to_cfg_superedge.put (cfg_edge, cfg_sedge);
 182             }
 183       }
 184
 185     /* Make interprocedural superedges for calls.  */
 186     {
 187       for (cgraph_edge_to_node_t::iterator iter
 188              = m_cgraph_edge_to_caller_prev_node.begin ();
 189            iter != m_cgraph_edge_to_caller_prev_node.end ();
 190            ++iter)
 191         {
 192           cgraph_edge *edge = (*iter).first;
 193           supernode *caller_prev_supernode = (*iter).second;
 194           function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
 195           if (!callee_fn || !callee_fn->cfg)
 196             continue;
 197           basic_block callee_cfg_block = ENTRY_BLOCK_PTR_FOR_FN (callee_fn);
 198           supernode *callee_supernode
 199             = *m_bb_to_initial_node.get (callee_cfg_block);
 200           call_superedge *sedge
 201             = add_call_superedge (caller_prev_supernode,
 202                                   callee_supernode,
 203                                   edge);
 204           m_cgraph_edge_to_call_superedge.put (edge, sedge);
 205         }
 206     }
 207
 208     /* Make interprocedural superedges for returns.  */
 209     {
 210       for (cgraph_edge_to_node_t::iterator iter
 211              = m_cgraph_edge_to_caller_next_node.begin ();
 212            iter != m_cgraph_edge_to_caller_next_node.end ();
 213            ++iter)
 214         {
 215           cgraph_edge *edge = (*iter).first;
 216           supernode *caller_next_supernode = (*iter).second;
 217           function* callee_fn = get_ultimate_function_for_cgraph_edge (edge);
 218           if (!callee_fn || !callee_fn->cfg)
 219             continue;
 220           basic_block callee_cfg_block = EXIT_BLOCK_PTR_FOR_FN (callee_fn);
 221           supernode *callee_supernode
 222             = *m_bb_to_initial_node.get (callee_cfg_block);
 223           return_superedge *sedge
 224             = add_return_superedge (callee_supernode,
 225                                     caller_next_supernode,
 226                                     edge);
 227           m_cgraph_edge_to_return_superedge.put (edge, sedge);
 228         }
 229     }
 230
 231     /* Make intraprocedural superedges linking the two halves of a call.  */
 232     {
 233       for (cgraph_edge_to_node_t::iterator iter
 234              = m_cgraph_edge_to_caller_prev_node.begin ();
 235            iter != m_cgraph_edge_to_caller_prev_node.end ();
 236            ++iter)
 237         {
 238           cgraph_edge *edge = (*iter).first;
 239           supernode *caller_prev_supernode = (*iter).second;
 240           supernode *caller_next_supernode
 241             = *m_cgraph_edge_to_caller_next_node.get (edge);
 242           superedge *sedge
 243             = new callgraph_superedge (caller_prev_supernode,
 244                                        caller_next_supernode,
 245                                        SUPEREDGE_INTRAPROCEDURAL_CALL,
 246                                        edge);
 247           add_edge (sedge);
 248           m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
 249         }
 250
 251     }
 252   }
 253 }
 254
 255 /* Dump this graph in .dot format to PP, using DUMP_ARGS.
 256    Cluster the supernodes by function, then by BB from original CFG.  */
 257
 258 void
 259 supergraph::dump_dot_to_pp (pretty_printer *pp,
 260                             const dump_args_t &dump_args) const
 261 {
 262   graphviz_out gv (pp);
 263
 264   pp_string (pp, "digraph \"");
 265   pp_write_text_to_stream (pp);
 266   pp_string (pp, "supergraph");
 267   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
 268   pp_string (pp, "\" {\n");
 269   gv.indent ();
 270
 271   gv.println ("overlap=false;");
 272   gv.println ("compound=true;");
 273
 274   /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
 275      https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
 276   */
 277
 278   /* Break out the supernodes into clusters by function.  */
 279   {
 280     cgraph_node *node;
 281     FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 282     {
 283       function *fun = node->get_fun ();
 284       const char *funcname = function_name (fun);
 285       gv.println ("subgraph \"cluster_%s\" {",
 286                   funcname);
 287       gv.indent ();
 288       pp_printf (pp,
 289                  ("style=\"dashed\";"
 290                   " color=\"black\";"
 291                   " label=\"%s\";\n"),
 292                  funcname);
 293
 294       /* Break out the nodes into clusters by BB from original CFG.  */
 295       {
 296         basic_block bb;
 297         FOR_ALL_BB_FN (bb, fun)
 298           {
 299             if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
 300               {
 301                 gv.println ("subgraph \"cluster_%s_bb_%i\" {",
 302                             funcname, bb->index);
 303                 gv.indent ();
 304                 pp_printf (pp,
 305                            ("style=\"dashed\";"
 306                             " color=\"black\";"
 307                             " label=\"bb: %i\";\n"),
 308                            bb->index);
 309               }
 310
 311             // TODO: maybe keep an index per-function/per-bb to speed this up???
 312             int i;
 313             supernode *n;
 314             FOR_EACH_VEC_ELT (m_nodes, i, n)
 315               if (n->m_fun == fun && n->m_bb == bb)
 316                 n->dump_dot (&gv, dump_args);
 317
 318             if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
 319               {
 320                 /* Terminate per-bb "subgraph" */
 321                 gv.outdent ();
 322                 gv.println ("}");
 323               }
 324           }
 325       }
 326
 327       /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
 328       pp_string (pp, "\t");
 329       get_node_for_function_entry (fun)->dump_dot_id (pp);
 330       pp_string (pp, ":s -> ");
 331       get_node_for_function_exit (fun)->dump_dot_id (pp);
 332       pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
 333
 334       /* Terminate per-function "subgraph" */
 335       gv.outdent ();
 336       gv.println ("}");
 337     }
 338   }
 339
 340   /* Superedges.  */
 341   int i;
 342   superedge *e;
 343   FOR_EACH_VEC_ELT (m_edges, i, e)
 344     e->dump_dot (&gv, dump_args);
 345
 346   /* Terminate "digraph" */
 347   gv.outdent ();
 348   gv.println ("}");
 349 }
 350
 351 /* Dump this graph in .dot format to FP, using DUMP_ARGS.  */
 352
 353 void
 354 supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
 355 {
 356   pretty_printer *pp = global_dc->printer->clone ();
 357   pp_show_color (pp) = 0;
 358   /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
 359      trying to prettify things by showing the underlying var.  */
 360   pp_format_decoder (pp) = default_tree_printer;
 361
 362   pp->buffer->stream = fp;
 363   dump_dot_to_pp (pp, dump_args);
 364   pp_flush (pp);
 365   delete pp;
 366 }
 367
 368 /* Dump this graph in .dot format to PATH, using DUMP_ARGS.  */
 369
 370 void
 371 supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
 372 {
 373   FILE *fp = fopen (path, "w");
 374   dump_dot_to_file (fp, dump_args);
 375   fclose (fp);
 376 }
 377
 378 /* Return a new json::object of the form
 379    {"nodes" : [objs for snodes],
 380     "edges" : [objs for sedges]}.  */
 381
 382 json::object *
 383 supergraph::to_json () const
 384 {
 385   json::object *sgraph_obj = new json::object ();
 386
 387   /* Nodes.  */
 388   {
 389     json::array *nodes_arr = new json::array ();
 390     unsigned i;
 391     supernode *n;
 392     FOR_EACH_VEC_ELT (m_nodes, i, n)
 393       nodes_arr->append (n->to_json ());
 394     sgraph_obj->set ("nodes", nodes_arr);
 395   }
 396
 397   /* Edges.  */
 398   {
 399     json::array *edges_arr = new json::array ();
 400     unsigned i;
 401     superedge *n;
 402     FOR_EACH_VEC_ELT (m_edges, i, n)
 403       edges_arr->append (n->to_json ());
 404     sgraph_obj->set ("edges", edges_arr);
 405   }
 406
 407   return sgraph_obj;
 408 }
 409
 410 /* Create a supernode for BB within FUN and add it to this supergraph.
 411
 412    If RETURNING_CALL is non-NULL, the supernode represents the resumption
 413    of the basic block after returning from that call.
 414
 415    If PHI_NODES is non-NULL, this is the initial supernode for the basic
 416    block, and is responsible for any handling of the phi nodes.  */
 417
 418 supernode *
 419 supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
 420                       gimple_seq phi_nodes)
 421 {
 422   supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
 423                                 m_nodes.length ());
 424   m_nodes.safe_push (n);
 425   return n;
 426 }
 427
 428 /* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
 429    adding it to this supergraph.
 430
 431    If the edge is for a switch statement, create a switch_cfg_superedge
 432    subclass using IDX (the index of E within the out-edges from SRC's
 433    underlying basic block).  */
 434
 435 cfg_superedge *
 436 supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e, int idx)
 437 {
 438   /* Special-case switch edges.  */
 439   gimple *stmt = src->get_last_stmt ();
 440   cfg_superedge *new_edge;
 441   if (stmt && stmt->code == GIMPLE_SWITCH)
 442     new_edge = new switch_cfg_superedge (src, dest, e, idx);
 443   else
 444     new_edge = new cfg_superedge (src, dest, e);
 445   add_edge (new_edge);
 446   return new_edge;
 447 }
 448
 449 /* Create and add a call_superedge representing an interprocedural call
 450    from SRC to DEST, using CEDGE.  */
 451
 452 call_superedge *
 453 supergraph::add_call_superedge (supernode *src, supernode *dest,
 454                                 cgraph_edge *cedge)
 455 {
 456   call_superedge *new_edge = new call_superedge (src, dest, cedge);
 457   add_edge (new_edge);
 458   return new_edge;
 459 }
 460
 461 /* Create and add a return_superedge representing returning from an
 462    interprocedural call, returning from SRC to DEST, using CEDGE.  */
 463
 464 return_superedge *
 465 supergraph::add_return_superedge (supernode *src, supernode *dest,
 466                                   cgraph_edge *cedge)
 467 {
 468   return_superedge *new_edge = new return_superedge (src, dest, cedge);
 469   add_edge (new_edge);
 470   return new_edge;
 471 }
 472
 473 /* Implementation of dnode::dump_dot vfunc for supernodes.
 474
 475    Write a cluster for the node, and within it a .dot node showing
 476    the phi nodes and stmts.  Call into any node annotator from ARGS to
 477    potentially add other records to the cluster.  */
 478
 479 void
 480 supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
 481 {
 482   gv->println ("subgraph cluster_node_%i {",
 483                m_index);
 484   gv->indent ();
 485
 486   gv->println("style=\"solid\";");
 487   gv->println("color=\"black\";");
 488   gv->println("fillcolor=\"lightgrey\";");
 489   gv->println("label=\"sn: %i (bb: %i)\";", m_index, m_bb->index);
 490
 491   pretty_printer *pp = gv->get_pp ();
 492
 493   if (args.m_node_annotator)
 494     args.m_node_annotator->add_node_annotations (gv, *this, false);
 495
 496   gv->write_indent ();
 497   dump_dot_id (pp);
 498   pp_printf (pp,
 499              " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
 500              "lightgrey");
 501   pp_string (pp, "<TABLE BORDER=\"0\">");
 502   pp_write_text_to_stream (pp);
 503
 504   bool had_row = false;
 505
 506   /* Give any annotator the chance to add its own per-node TR elements. */
 507   if (args.m_node_annotator)
 508     if (args.m_node_annotator->add_node_annotations (gv, *this, true))
 509       had_row = true;
 510
 511   if (m_returning_call)
 512     {
 513       gv->begin_trtd ();
 514       pp_string (pp, "returning call: ");
 515       gv->end_tdtr ();
 516
 517       gv->begin_tr ();
 518       gv->begin_td ();
 519       pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
 520       pp_write_text_as_html_like_dot_to_stream (pp);
 521       gv->end_td ();
 522       /* Give any annotator the chance to add per-stmt TD elements to
 523          this row.  */
 524       if (args.m_node_annotator)
 525         args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
 526                                                      true);
 527       gv->end_tr ();
 528
 529       /* Give any annotator the chance to add per-stmt TR elements.  */
 530       if (args.m_node_annotator)
 531         args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
 532                                                      false);
 533       pp_newline (pp);
 534
 535       had_row = true;
 536     }
 537
 538   if (entry_p ())
 539     {
 540       pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
 541       pp_newline (pp);
 542       had_row = true;
 543     }
 544
 545   if (return_p ())
 546     {
 547       pp_string (pp, "<TR><TD>EXIT</TD></TR>");
 548       pp_newline (pp);
 549       had_row = true;
 550     }
 551
 552   /* Phi nodes.  */
 553   for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
 554        !gsi_end_p (gpi); gsi_next (&gpi))
 555     {
 556       const gimple *stmt = gsi_stmt (gpi);
 557       gv->begin_tr ();
 558       gv->begin_td ();
 559       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
 560       pp_write_text_as_html_like_dot_to_stream (pp);
 561       gv->end_td ();
 562       /* Give any annotator the chance to add per-phi TD elements to
 563          this row.  */
 564       if (args.m_node_annotator)
 565         args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
 566       gv->end_tr ();
 567
 568       /* Give any annotator the chance to add per-phi TR elements.  */
 569       if (args.m_node_annotator)
 570         args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
 571
 572       pp_newline (pp);
 573       had_row = true;
 574     }
 575
 576   /* Statements.  */
 577   int i;
 578   gimple *stmt;
 579   FOR_EACH_VEC_ELT (m_stmts, i, stmt)
 580     {
 581       gv->begin_tr ();
 582       gv->begin_td ();
 583       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
 584       pp_write_text_as_html_like_dot_to_stream (pp);
 585       gv->end_td ();
 586       /* Give any annotator the chance to add per-stmt TD elements to
 587          this row.  */
 588       if (args.m_node_annotator)
 589         args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
 590       gv->end_tr ();
 591
 592       /* Give any annotator the chance to add per-stmt TR elements.  */
 593       if (args.m_node_annotator)
 594         args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
 595
 596       pp_newline (pp);
 597       had_row = true;
 598     }
 599
 600   /* Give any annotator the chance to add additional per-node TR elements
 601      to the end of the TABLE. */
 602   if (args.m_node_annotator)
 603     if (args.m_node_annotator->add_after_node_annotations (gv, *this))
 604       had_row = true;
 605
 606   /* Graphviz requires a TABLE element to have at least one TR
 607      (and each TR to have at least one TD).  */
 608   if (!had_row)
 609     {
 610       pp_string (pp, "<TR><TD>(empty)</TD></TR>");
 611       pp_newline (pp);
 612     }
 613
 614   pp_string (pp, "</TABLE>>];\n\n");
 615   pp_flush (pp);
 616
 617   /* Terminate "subgraph" */
 618   gv->outdent ();
 619   gv->println ("}");
 620 }
 621
 622 /* Write an ID for this node to PP, for use in .dot output.  */
 623
 624 void
 625 supernode::dump_dot_id (pretty_printer *pp) const
 626 {
 627   pp_printf (pp, "node_%i", m_index);
 628 }
 629
 630 /* Return a new json::object of the form
 631    {"idx": int,
 632     "bb_idx": int,
 633     "m_returning_call": optional str,
 634     "phis": [str],
 635     "stmts" : [str]}.  */
 636
 637 json::object *
 638 supernode::to_json () const
 639 {
 640   json::object *snode_obj = new json::object ();
 641
 642   snode_obj->set ("idx", new json::integer_number (m_index));
 643   snode_obj->set ("bb_idx", new json::integer_number (m_bb->index));
 644
 645   if (m_returning_call)
 646     {
 647       pretty_printer pp;
 648       pp_format_decoder (&pp) = default_tree_printer;
 649       pp_gimple_stmt_1 (&pp, m_returning_call, 0, (dump_flags_t)0);
 650       snode_obj->set ("returning_call",
 651                       new json::string (pp_formatted_text (&pp)));
 652     }
 653
 654   /* Phi nodes.  */
 655   {
 656     json::array *phi_arr = new json::array ();
 657     for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
 658          !gsi_end_p (gpi); gsi_next (&gpi))
 659       {
 660         const gimple *stmt = gsi_stmt (gpi);
 661         pretty_printer pp;
 662         pp_format_decoder (&pp) = default_tree_printer;
 663         pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
 664         phi_arr->append (new json::string (pp_formatted_text (&pp)));
 665       }
 666     snode_obj->set ("phis", phi_arr);
 667   }
 668
 669   /* Statements.  */
 670   {
 671     json::array *stmt_arr = new json::array ();
 672     int i;
 673     gimple *stmt;
 674     FOR_EACH_VEC_ELT (m_stmts, i, stmt)
 675       {
 676         pretty_printer pp;
 677         pp_format_decoder (&pp) = default_tree_printer;
 678         pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
 679         stmt_arr->append (new json::string (pp_formatted_text (&pp)));
 680       }
 681     snode_obj->set ("stmts", stmt_arr);
 682   }
 683
 684   return snode_obj;
 685 }
 686
 687 /* Get a location_t for the start of this supernode.  */
 688
 689 location_t
 690 supernode::get_start_location () const
 691 {
 692   if (m_returning_call
 693       && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
 694     return m_returning_call->location;
 695
 696   int i;
 697   gimple *stmt;
 698   FOR_EACH_VEC_ELT (m_stmts, i, stmt)
 699     if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
 700       return stmt->location;
 701
 702   if (entry_p ())
 703     {
 704       // TWEAK: show the decl instead; this leads to more readable output:
 705       return DECL_SOURCE_LOCATION (m_fun->decl);
 706
 707       return m_fun->function_start_locus;
 708     }
 709   if (return_p ())
 710     return m_fun->function_end_locus;
 711
 712   return UNKNOWN_LOCATION;
 713 }
 714
 715 /* Get a location_t for the end of this supernode.  */
 716
 717 location_t
 718 supernode::get_end_location () const
 719 {
 720   int i;
 721   gimple *stmt;
 722   FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
 723     if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
 724       return stmt->location;
 725
 726   if (m_returning_call
 727       && get_pure_location (m_returning_call->location) != UNKNOWN_LOCATION)
 728     return m_returning_call->location;
 729
 730   if (entry_p ())
 731     return m_fun->function_start_locus;
 732   if (return_p ())
 733     return m_fun->function_end_locus;
 734
 735   return UNKNOWN_LOCATION;
 736 }
 737
 738 /* Given STMT within this supernode, return its index within m_stmts.  */
 739
 740 unsigned int
 741 supernode::get_stmt_index (const gimple *stmt) const
 742 {
 743   unsigned i;
 744   gimple *iter_stmt;
 745   FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
 746     if (iter_stmt == stmt)
 747       return i;
 748   gcc_unreachable ();
 749 }
 750
 751 /* Dump this superedge to PP.  */
 752
 753 void
 754 superedge::dump (pretty_printer *pp) const
 755 {
 756   pp_printf (pp, "edge: SN: %i -> SN: %i", m_src->m_index, m_dest->m_index);
 757   char *desc = get_description (false);
 758   if (strlen (desc) > 0)
 759     {
 760       pp_space (pp);
 761       pp_string (pp, desc);
 762     }
 763   free (desc);
 764 }
 765
 766 /* Dump this superedge to stderr.  */
 767
 768 DEBUG_FUNCTION void
 769 superedge::dump () const
 770 {
 771   pretty_printer pp;
 772   pp_format_decoder (&pp) = default_tree_printer;
 773   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 774   pp.buffer->stream = stderr;
 775   dump (&pp);
 776   pp_newline (&pp);
 777   pp_flush (&pp);
 778 }
 779
 780 /* Implementation of dedge::dump_dot for superedges.
 781    Write a .dot edge to GV representing this superedge.  */
 782
 783 void
 784 superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
 785 {
 786   const char *style = "\"solid,bold\"";
 787   const char *color = "black";
 788   int weight = 10;
 789   const char *constraint = "true";
 790
 791   switch (m_kind)
 792     {
 793     default:
 794       gcc_unreachable ();
 795     case SUPEREDGE_CFG_EDGE:
 796       break;
 797     case SUPEREDGE_CALL:
 798       color = "red";
 799       break;
 800     case SUPEREDGE_RETURN:
 801       color = "green";
 802       break;
 803     case SUPEREDGE_INTRAPROCEDURAL_CALL:
 804       style = "\"dotted\"";
 805       break;
 806     }
 807
 808   /* Adapted from graph.c:draw_cfg_node_succ_edges.  */
 809   if (::edge cfg_edge = get_any_cfg_edge ())
 810     {
 811       if (cfg_edge->flags & EDGE_FAKE)
 812         {
 813           style = "dotted";
 814           color = "green";
 815           weight = 0;
 816         }
 817       else if (cfg_edge->flags & EDGE_DFS_BACK)
 818         {
 819           style = "\"dotted,bold\"";
 820           color = "blue";
 821           weight = 10;
 822         }
 823       else if (cfg_edge->flags & EDGE_FALLTHRU)
 824         {
 825           color = "blue";
 826           weight = 100;
 827         }
 828
 829       if (cfg_edge->flags & EDGE_ABNORMAL)
 830         color = "red";
 831     }
 832
 833   gv->write_indent ();
 834
 835   pretty_printer *pp = gv->get_pp ();
 836
 837   m_src->dump_dot_id (pp);
 838   pp_string (pp, " -> ");
 839   m_dest->dump_dot_id (pp);
 840   pp_printf (pp,
 841              (" [style=%s, color=%s, weight=%d, constraint=%s,"
 842               " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
 843               " headlabel=\""),
 844              style, color, weight, constraint,
 845              m_src->m_index, m_dest->m_index);
 846
 847   dump_label_to_pp (pp, false);
 848
 849   pp_printf (pp, "\"];\n");
 850 }
 851
 852 /* Return a new json::object of the form
 853    {"src_idx": int, the index of the source supernode,
 854     "dst_idx": int, the index of the destination supernode,
 855     "desc"   : str.  */
 856
 857 json::object *
 858 superedge::to_json () const
 859 {
 860   json::object *sedge_obj = new json::object ();
 861   sedge_obj->set ("src_idx", new json::integer_number (m_src->m_index));
 862   sedge_obj->set ("dst_idx", new json::integer_number (m_dest->m_index));
 863
 864   {
 865     pretty_printer pp;
 866     pp_format_decoder (&pp) = default_tree_printer;
 867     dump_label_to_pp (&pp, false);
 868     sedge_obj->set ("desc", new json::string (pp_formatted_text (&pp)));
 869   }
 870
 871   return sedge_obj;
 872 }
 873
 874 /* If this is an intraprocedural superedge, return the associated
 875    CFG edge.  Otherwise, return NULL.  */
 876
 877 ::edge
 878 superedge::get_any_cfg_edge () const
 879 {
 880   if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
 881     return sub->get_cfg_edge ();
 882   return NULL;
 883 }
 884
 885 /* If this is an interprocedural superedge, return the associated
 886    cgraph_edge *.  Otherwise, return NULL.  */
 887
 888 cgraph_edge *
 889 superedge::get_any_callgraph_edge () const
 890 {
 891   if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
 892     return sub->m_cedge;
 893   return NULL;
 894 }
 895
 896 /* Build a description of this superedge (e.g. "true" for the true
 897    edge of a conditional, or "case 42:" for a switch case).
 898
 899    The caller is responsible for freeing the result.
 900
 901    If USER_FACING is false, the result also contains any underlying
 902    CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)".  */
 903
 904 char *
 905 superedge::get_description (bool user_facing) const
 906 {
 907   pretty_printer pp;
 908   dump_label_to_pp (&pp, user_facing);
 909   return xstrdup (pp_formatted_text (&pp));
 910 }
 911
 912 /* Implementation of superedge::dump_label_to_pp for non-switch CFG
 913    superedges.
 914
 915    For true/false edges, print "true" or "false" to PP.
 916
 917    If USER_FACING is false, also print flags on the underlying CFG edge to
 918    PP.  */
 919
 920 void
 921 cfg_superedge::dump_label_to_pp (pretty_printer *pp,
 922                                  bool user_facing) const
 923 {
 924   if (true_value_p ())
 925     pp_printf (pp, "true");
 926   else if (false_value_p ())
 927     pp_printf (pp, "false");
 928
 929   if (user_facing)
 930     return;
 931
 932   /* Express edge flags as a string with " | " separator.
 933      e.g. " (flags FALLTHRU | DFS_BACK)".  */
 934   if (get_flags ())
 935     {
 936       pp_string (pp, " (flags ");
 937       bool seen_flag = false;
 938 #define DEF_EDGE_FLAG(NAME,IDX)                 \
 939   do {                                          \
 940     if (get_flags () & EDGE_##NAME)                     \
 941       {                                         \
 942         if (seen_flag)                          \
 943           pp_string (pp, " | ");                        \
 944         pp_printf (pp, "%s", (#NAME));          \
 945         seen_flag = true;                       \
 946       }                                         \
 947   } while (0);
 948 #include "cfg-flags.def"
 949 #undef DEF_EDGE_FLAG
 950       pp_string (pp, ")");
 951     }
 952
 953   /* Otherwise, no label.  */
 954 }
 955
 956 /* Get the phi argument for PHI for this CFG edge.  */
 957
 958 tree
 959 cfg_superedge::get_phi_arg (const gphi *phi) const
 960 {
 961   size_t index = m_cfg_edge->dest_idx;
 962   return gimple_phi_arg_def (phi, index);
 963 }
 964
 965 /* Implementation of superedge::dump_label_to_pp for CFG superedges for
 966    "switch" statements.
 967
 968    Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP.  */
 969
 970 void
 971 switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
 972                                         bool user_facing ATTRIBUTE_UNUSED) const
 973 {
 974   tree case_label = get_case_label ();
 975   gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
 976   tree lower_bound = CASE_LOW (case_label);
 977   tree upper_bound = CASE_HIGH (case_label);
 978   if (lower_bound)
 979     {
 980       pp_printf (pp, "case ");
 981       dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
 982       if (upper_bound)
 983         {
 984           pp_printf (pp, " ... ");
 985           dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0, false);
 986         }
 987       pp_printf (pp, ":");
 988     }
 989   else
 990     pp_printf (pp, "default:");
 991 }
 992
 993 /* Get the case label for this "switch" superedge.  */
 994
 995 tree
 996 switch_cfg_superedge::get_case_label () const
 997 {
 998   return gimple_switch_label (get_switch_stmt (), m_idx);
 999 }
1000
1001 /* Implementation of superedge::dump_label_to_pp for interprocedural
1002    superedges.  */
1003
1004 void
1005 callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
1006                                        bool user_facing ATTRIBUTE_UNUSED) const
1007 {
1008   switch (m_kind)
1009     {
1010     default:
1011     case SUPEREDGE_CFG_EDGE:
1012       gcc_unreachable ();
1013
1014     case SUPEREDGE_CALL:
1015       pp_printf (pp, "call");
1016       break;
1017
1018     case SUPEREDGE_RETURN:
1019       pp_printf (pp, "return");
1020       break;
1021
1022     case SUPEREDGE_INTRAPROCEDURAL_CALL:
1023       pp_printf (pp, "intraproc link");
1024       break;
1025     }
1026 }
1027
1028 /* Get the function that was called at this interprocedural call/return
1029    edge.  */
1030
1031 function *
1032 callgraph_superedge::get_callee_function () const
1033 {
1034   return get_ultimate_function_for_cgraph_edge (m_cedge);
1035 }
1036
1037 /* Get the calling function at this interprocedural call/return edge.  */
1038
1039 function *
1040 callgraph_superedge::get_caller_function () const
1041 {
1042   return m_cedge->caller->get_fun ();
1043 }
1044
1045 /* Get the fndecl that was called at this interprocedural call/return
1046    edge.  */
1047
1048 tree
1049 callgraph_superedge::get_callee_decl () const
1050 {
1051   return get_callee_function ()->decl;
1052 }
1053
1054 /* Get the calling fndecl at this interprocedural call/return edge.  */
1055
1056 tree
1057 callgraph_superedge::get_caller_decl () const
1058 {
1059   return get_caller_function ()->decl;
1060 }
1061
1062 /* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
1063    to *OUT if OUT is non-NULL), and return the corresponding argument
1064    at the callsite.  */
1065
1066 tree
1067 callgraph_superedge::get_arg_for_parm (tree parm_to_find,
1068                                        callsite_expr *out) const
1069 {
1070   gcc_assert  (TREE_CODE (parm_to_find) == PARM_DECL);
1071
1072   tree callee = get_callee_decl ();
1073   const gcall *call_stmt = get_call_stmt ();
1074
1075   unsigned i = 0;
1076   for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1077        iter_parm = DECL_CHAIN (iter_parm), ++i)
1078     {
1079       if (i >= gimple_call_num_args (call_stmt))
1080         return NULL_TREE;
1081       if (iter_parm == parm_to_find)
1082         {
1083           if (out)
1084             *out = callsite_expr::from_zero_based_param (i);
1085           return gimple_call_arg (call_stmt, i);
1086         }
1087     }
1088
1089   /* Not found.  */
1090   return NULL_TREE;
1091 }
1092
1093 /* Look for a use of ARG_TO_FIND as an argument at this callsite.
1094    If found, return the default SSA def of the corresponding parm within
1095    the callee, and if OUT is non-NULL, write the index to *OUT.
1096    Only the first match is handled.  */
1097
1098 tree
1099 callgraph_superedge::get_parm_for_arg (tree arg_to_find,
1100                                        callsite_expr *out) const
1101 {
1102   tree callee = get_callee_decl ();
1103   const gcall *call_stmt = get_call_stmt ();
1104
1105   unsigned i = 0;
1106   for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
1107        iter_parm = DECL_CHAIN (iter_parm), ++i)
1108     {
1109       if (i >= gimple_call_num_args (call_stmt))
1110         return NULL_TREE;
1111       tree param = gimple_call_arg (call_stmt, i);
1112       if (arg_to_find == param)
1113         {
1114           if (out)
1115             *out = callsite_expr::from_zero_based_param (i);
1116           return ssa_default_def (get_callee_function (), iter_parm);
1117         }
1118     }
1119
1120   /* Not found.  */
1121   return NULL_TREE;
1122 }
1123
1124 /* Map caller_expr back to an expr within the callee, or return NULL_TREE.
1125    If non-NULL is returned, populate OUT.  */
1126
1127 tree
1128 callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
1129                                                      callsite_expr *out) const
1130 {
1131   /* Is it an argument (actual param)?  If so, convert to
1132      parameter (formal param).  */
1133   tree parm = get_parm_for_arg (caller_expr, out);
1134   if (parm)
1135     return parm;
1136   /* Otherwise try return value.  */
1137   if (caller_expr == gimple_call_lhs (get_call_stmt ()))
1138     {
1139       if (out)
1140         *out = callsite_expr::from_return_value ();
1141       return DECL_RESULT (get_callee_decl ());
1142     }
1143
1144   return NULL_TREE;
1145 }
1146
1147 /* Map callee_expr back to an expr within the caller, or return NULL_TREE.
1148    If non-NULL is returned, populate OUT.  */
1149
1150 tree
1151 callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
1152                                                      callsite_expr *out) const
1153 {
1154   if (callee_expr == NULL_TREE)
1155     return NULL_TREE;
1156
1157   /* If it's a parameter (formal param), get the argument (actual param).  */
1158   if (TREE_CODE (callee_expr) == PARM_DECL)
1159     return get_arg_for_parm (callee_expr, out);
1160
1161   /* Similar for the default SSA name of the PARM_DECL.  */
1162   if (TREE_CODE (callee_expr) == SSA_NAME
1163       && SSA_NAME_IS_DEFAULT_DEF (callee_expr)
1164       && TREE_CODE (SSA_NAME_VAR (callee_expr)) == PARM_DECL)
1165     return get_arg_for_parm (SSA_NAME_VAR (callee_expr), out);
1166
1167   /* Otherwise try return value.  */
1168   if (callee_expr == DECL_RESULT (get_callee_decl ()))
1169     {
1170       if (out)
1171         *out = callsite_expr::from_return_value ();
1172       return gimple_call_lhs (get_call_stmt ());
1173     }
1174
1175   return NULL_TREE;
1176 }
1177
1178 } // namespace ana
1179
1180 #endif /* #if ENABLE_ANALYZER */