[27/49] analyzer: new files: supergraph.{cc|h}
diff mbox series

Message ID 1573867416-55618-28-git-send-email-dmalcolm@redhat.com
State New
Headers show
Series
  • RFC: Add a static analysis framework to GCC
Related show

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m. UTC
This patch adds a "supergraph" class that combines CFGs and callgraph into
one directed graph, along with "supernode" and "superedge" classes.

gcc/ChangeLog:
	* analyzer/supergraph.cc: New file.
	* analyzer/supergraph.h: New file.
---
 gcc/analyzer/supergraph.cc | 936 +++++++++++++++++++++++++++++++++++++++++++++
 gcc/analyzer/supergraph.h  | 560 +++++++++++++++++++++++++++
 2 files changed, 1496 insertions(+)
 create mode 100644 gcc/analyzer/supergraph.cc
 create mode 100644 gcc/analyzer/supergraph.h

Patch
diff mbox series

diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc
new file mode 100644
index 0000000..da5b13a
--- /dev/null
+++ b/gcc/analyzer/supergraph.cc
@@ -0,0 +1,936 @@ 
+/* "Supergraph" classes that combine CFGs and callgraph into one digraph.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "gcc-plugin.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "tm.h"
+#include "toplev.h"
+#include "hash-table.h"
+#include "vec.h"
+#include "ggc.h"
+#include "basic-block.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "timevar.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-pretty-print.h"
+#include "tree-pretty-print.h"
+#include "graphviz.h"
+#include "cgraph.h"
+#include "tree-dfa.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/analyzer-logging.h"
+
+/* Get the cgraph_edge, but only if there's an underlying function body.  */
+
+cgraph_edge *
+supergraph_call_edge (function *fun, gimple *stmt)
+{
+  gcall *call = dyn_cast<gcall *> (stmt);
+  if (!call)
+    return NULL;
+  cgraph_edge *edge = cgraph_node::get (fun->decl)->get_edge (stmt);
+  if (!edge)
+    return NULL;
+  if (!edge->callee)
+    return NULL; /* e.g. for a function pointer.  */
+  if (!edge->callee->get_fun ())
+    return NULL;
+  return edge;
+}
+
+/* supergraph's ctor.  Walk the callgraph, building supernodes for each
+   CFG basic block, splitting the basic blocks at callsites.  Join
+   together the supernodes with interprocedural and intraprocedural
+   superedges as appropriate.  */
+
+supergraph::supergraph (logger *logger)
+{
+  auto_client_timevar tv ("building supergraph");
+
+  LOG_FUNC (logger);
+
+  /* First pass: make supernodes.  */
+  {
+    /* Sort the cgraph_nodes?  */
+    cgraph_node *node;
+    FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+    {
+      function *fun = node->get_fun ();
+
+      /* Ensure that EDGE_DFS_BACK is correct for every CFG edge in
+	 the supergraph (by doing it per-function).  */
+      auto_cfun sentinel (fun);
+      mark_dfs_back_edges ();
+
+      const int start_idx = m_nodes.length ();
+
+      basic_block bb;
+      FOR_ALL_BB_FN (bb, fun)
+	{
+	  /* The initial supernode for the BB gets the phi nodes (if any).  */
+	  supernode *node_for_stmts = add_node (fun, bb, NULL, phi_nodes (bb));
+	  m_bb_to_initial_node.put (bb, node_for_stmts);
+	  for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
+	       gsi_next (&gpi))
+	    {
+	      gimple *stmt = gsi_stmt (gpi);
+	      m_stmt_to_node_t.put (stmt, node_for_stmts);
+	    }
+
+	  /* Append statements from BB to the current supernode, splitting
+	     them into a new supernode at each call site; such call statements
+	     appear in both supernodes (representing call and return).  */
+	  gimple_stmt_iterator gsi;
+	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	    {
+	      gimple *stmt = gsi_stmt (gsi);
+	      node_for_stmts->m_stmts.safe_push (stmt);
+	      m_stmt_to_node_t.put (stmt, node_for_stmts);
+	      if (cgraph_edge *edge = supergraph_call_edge (fun, stmt))
+		{
+		  m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts);
+		  node_for_stmts = add_node (fun, bb, as_a <gcall *> (stmt), NULL);
+		  m_cgraph_edge_to_caller_next_node.put (edge, node_for_stmts);
+		}
+	    }
+
+	  m_bb_to_final_node.put (bb, node_for_stmts);
+	}
+
+      const unsigned num_snodes = m_nodes.length () - start_idx;
+      m_function_to_num_snodes.put (fun, num_snodes);
+
+      if (logger)
+	{
+	  const int end_idx = m_nodes.length () - 1;
+	  logger->log ("SN: %i...%i: function %qD",
+		       start_idx, end_idx, fun->decl);
+	}
+    }
+  }
+
+  /* Second pass: make superedges.  */
+  {
+    /* Make superedges for CFG edges.  */
+    for (bb_to_node_t::iterator iter = m_bb_to_final_node.begin ();
+	 iter != m_bb_to_final_node.end ();
+	 ++iter)
+      {
+	basic_block bb = (*iter).first;
+	supernode *src_supernode = (*iter).second;
+
+	::edge cfg_edge;
+	int idx;
+	if (bb->succs)
+	  FOR_EACH_VEC_ELT (*bb->succs, idx, cfg_edge)
+	    {
+	      basic_block dest_cfg_block = cfg_edge->dest;
+	      supernode *dest_supernode
+		= *m_bb_to_initial_node.get (dest_cfg_block);
+	      cfg_superedge *cfg_sedge
+		= add_cfg_edge (src_supernode, dest_supernode, cfg_edge, idx);
+	      m_cfg_edge_to_cfg_superedge.put (cfg_edge, cfg_sedge);
+	    }
+      }
+
+    /* Make interprocedural superedges for calls.  */
+    {
+      for (cgraph_edge_to_node_t::iterator iter
+	     = m_cgraph_edge_to_caller_prev_node.begin ();
+	   iter != m_cgraph_edge_to_caller_prev_node.end ();
+	   ++iter)
+	{
+	  cgraph_edge *edge = (*iter).first;
+	  supernode *caller_prev_supernode = (*iter).second;
+	  basic_block callee_cfg_block
+	    = ENTRY_BLOCK_PTR_FOR_FN (edge->callee->get_fun ());
+	  supernode *callee_supernode
+	    = *m_bb_to_initial_node.get (callee_cfg_block);
+	  call_superedge *sedge
+	    = add_call_superedge (caller_prev_supernode,
+				  callee_supernode,
+				  edge);
+	  m_cgraph_edge_to_call_superedge.put (edge, sedge);
+	}
+    }
+
+    /* Make interprocedural superedges for returns.  */
+    {
+      for (cgraph_edge_to_node_t::iterator iter
+	     = m_cgraph_edge_to_caller_next_node.begin ();
+	   iter != m_cgraph_edge_to_caller_next_node.end ();
+	   ++iter)
+	{
+	  cgraph_edge *edge = (*iter).first;
+	  supernode *caller_next_supernode = (*iter).second;
+	  basic_block callee_cfg_block
+	    = EXIT_BLOCK_PTR_FOR_FN (edge->callee->get_fun ());
+	  supernode *callee_supernode
+	    = *m_bb_to_initial_node.get (callee_cfg_block);
+	  return_superedge *sedge
+	    = add_return_superedge (callee_supernode,
+				    caller_next_supernode,
+				    edge);
+	  m_cgraph_edge_to_return_superedge.put (edge, sedge);
+	}
+    }
+
+    /* Make intraprocedural superedges linking the two halves of a call.  */
+    {
+      for (cgraph_edge_to_node_t::iterator iter
+	     = m_cgraph_edge_to_caller_prev_node.begin ();
+	   iter != m_cgraph_edge_to_caller_prev_node.end ();
+	   ++iter)
+	{
+	  cgraph_edge *edge = (*iter).first;
+	  supernode *caller_prev_supernode = (*iter).second;
+	  supernode *caller_next_supernode
+	    = *m_cgraph_edge_to_caller_next_node.get (edge);
+	  superedge *sedge
+	    = new callgraph_superedge (caller_prev_supernode,
+				       caller_next_supernode,
+				       SUPEREDGE_INTRAPROCEDURAL_CALL,
+				       edge);
+	  add_edge (sedge);
+	  m_cgraph_edge_to_intraproc_superedge.put (edge, sedge);
+	}
+
+    }
+  }
+}
+
+/* Dump this graph in .dot format to PP, using DUMP_ARGS.
+   Cluster the supernodes by function, then by BB from original CFG.  */
+
+void
+supergraph::dump_dot_to_pp (pretty_printer *pp,
+			    const dump_args_t &dump_args) const
+{
+  graphviz_out gv (pp);
+
+  pp_string (pp, "digraph \"");
+  pp_write_text_to_stream (pp);
+  pp_string (pp, "supergraph");
+  pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
+  pp_string (pp, "\" {\n");
+  gv.indent ();
+
+  gv.println ("overlap=false;");
+  gv.println ("compound=true;");
+
+  /* TODO: maybe (optionally) sub-subdivide by TU, for LTO; see also:
+     https://gcc-python-plugin.readthedocs.io/en/latest/_images/sample-supergraph.png
+  */
+
+  /* Break out the supernodes into clusters by function.  */
+  {
+    cgraph_node *node;
+    FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+    {
+      function *fun = node->get_fun ();
+      const char *funcname = function_name (fun);
+      gv.println ("subgraph \"cluster_%s\" {",
+		  funcname);
+      gv.indent ();
+      pp_printf (pp,
+		 ("style=\"dashed\";"
+		  " color=\"black\";"
+		  " label=\"%s\";\n"),
+		 funcname);
+
+      /* Break out the nodes into clusters by BB from original CFG.  */
+      {
+	basic_block bb;
+	FOR_ALL_BB_FN (bb, fun)
+	  {
+	    if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
+	      {
+		gv.println ("subgraph \"cluster_%s_bb_%i\" {",
+			    funcname, bb->index);
+		gv.indent ();
+		pp_printf (pp,
+			   ("style=\"dashed\";"
+			    " color=\"black\";"
+			    " label=\"bb: %i\";\n"),
+			   bb->index);
+	      }
+
+	    // TODO: maybe keep an index per-function/per-bb to speed this up???
+	    int i;
+	    supernode *n;
+	    FOR_EACH_VEC_ELT (m_nodes, i, n)
+	      if (n->m_fun == fun && n->m_bb == bb)
+		n->dump_dot (&gv, dump_args);
+
+	    if (dump_args.m_flags & SUPERGRAPH_DOT_SHOW_BBS)
+	      {
+		/* Terminate per-bb "subgraph" */
+		gv.outdent ();
+		gv.println ("}");
+	      }
+	  }
+      }
+
+      /* Add an invisible edge from ENTRY to EXIT, to improve the graph layout.  */
+      pp_string (pp, "\t");
+      get_node_for_function_entry (fun)->dump_dot_id (pp);
+      pp_string (pp, ":s -> ");
+      get_node_for_function_exit (fun)->dump_dot_id (pp);
+      pp_string (pp, ":n [style=\"invis\",constraint=true];\n");
+
+      /* Terminate per-function "subgraph" */
+      gv.outdent ();
+      gv.println ("}");
+    }
+  }
+
+  /* Superedges.  */
+  int i;
+  superedge *e;
+  FOR_EACH_VEC_ELT (m_edges, i, e)
+    e->dump_dot (&gv, dump_args);
+
+  /* Terminate "digraph" */
+  gv.outdent ();
+  gv.println ("}");
+}
+
+/* Dump this graph in .dot format to FP, using DUMP_ARGS.  */
+
+void
+supergraph::dump_dot_to_file (FILE *fp, const dump_args_t &dump_args) const
+{
+  pretty_printer *pp = global_dc->printer->clone ();
+  pp_show_color (pp) = 0;
+  /* %qE in logs for SSA_NAMEs should show the ssa names, rather than
+     trying to prettify things by showing the underlying var.  */
+  pp_format_decoder (pp) = default_tree_printer;
+
+  pp->buffer->stream = fp;
+  dump_dot_to_pp (pp, dump_args);
+  pp_flush (pp);
+  delete pp;
+}
+
+/* Dump this graph in .dot format to PATH, using DUMP_ARGS.  */
+
+void
+supergraph::dump_dot (const char *path, const dump_args_t &dump_args) const
+{
+  FILE *fp = fopen (path, "w");
+  dump_dot_to_file (fp, dump_args);
+  fclose (fp);
+}
+
+/* Create a supernode for BB within FUN and add it to this supergraph.
+
+   If RETURNING_CALL is non-NULL, the supernode represents the resumption
+   of the basic block after returning from that call.
+
+   If PHI_NODES is non-NULL, this is the initial supernode for the basic
+   block, and is responsible for any handling of the phi nodes.  */
+
+supernode *
+supergraph::add_node (function *fun, basic_block bb, gcall *returning_call,
+		      gimple_seq phi_nodes)
+{
+  supernode *n = new supernode (fun, bb, returning_call, phi_nodes,
+				m_nodes.length ());
+  m_nodes.safe_push (n);
+  return n;
+}
+
+/* Create a new cfg_superedge from SRC to DEST for the underlying CFG edge E,
+   adding it to this supergraph.
+
+   If the edge is for a switch statement, create a switch_cfg_superedge
+   subclass using IDX (the index of E within the out-edges from SRC's
+   underlying basic block).  */
+
+cfg_superedge *
+supergraph::add_cfg_edge (supernode *src, supernode *dest, ::edge e, int idx)
+{
+  /* Special-case switch edges.  */
+  gimple *stmt = src->get_last_stmt ();
+  cfg_superedge *new_edge;
+  if (stmt && stmt->code == GIMPLE_SWITCH)
+    new_edge = new switch_cfg_superedge (src, dest, e, idx);
+  else
+    new_edge = new cfg_superedge (src, dest, e);
+  add_edge (new_edge);
+  return new_edge;
+}
+
+/* Create and add a call_superedge representing an interprocedural call
+   from SRC to DEST, using CEDGE.  */
+
+call_superedge *
+supergraph::add_call_superedge (supernode *src, supernode *dest,
+				cgraph_edge *cedge)
+{
+  call_superedge *new_edge = new call_superedge (src, dest, cedge);
+  add_edge (new_edge);
+  return new_edge;
+}
+
+/* Create and add a return_superedge representing returning from an
+   interprocedural call, returning from SRC to DEST, using CEDGE.  */
+
+return_superedge *
+supergraph::add_return_superedge (supernode *src, supernode *dest,
+				  cgraph_edge *cedge)
+{
+  return_superedge *new_edge = new return_superedge (src, dest, cedge);
+  add_edge (new_edge);
+  return new_edge;
+}
+
+/* Implementation of dnode::dump_dot vfunc for supernodes.
+
+   Write a cluster for the node, and within it a record showing
+   the phi nodes and stmts.  Call into any node annotator from ARGS to
+   potentially add other records to the cluster.  */
+
+void
+supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
+{
+  gv->println ("subgraph cluster_node_%i {",
+	       m_index);
+  gv->indent ();
+
+  gv->println("style=\"solid\";");
+  gv->println("color=\"black\";");
+  gv->println("fillcolor=\"lightgrey\";");
+  gv->println("label=\"sn: %i\";", m_index);
+
+  pretty_printer *pp = gv->get_pp ();
+
+  if (args.m_node_annotator)
+    args.m_node_annotator->add_node_annotations (pp, *this);
+
+  gv->write_indent ();
+  dump_dot_id (pp);
+  pp_printf (pp, " [shape=%s,style=filled,fillcolor=%s,label=\"",
+	     "record", "lightgrey");
+  pp_left_brace (pp);
+  pp_write_text_to_stream (pp);
+
+  if (m_returning_call)
+    {
+      pp_string (pp, "returning call: ");
+      pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (pp, m_returning_call);
+      pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+      pp_newline (pp);
+    }
+
+  if (entry_p ())
+    {
+      pp_string (pp, "ENTRY");
+      pp_newline (pp);
+    }
+
+  if (return_p ())
+    {
+      pp_string (pp, "EXIT");
+      pp_newline (pp);
+    }
+
+  /* Phi nodes.  */
+  for (gphi_iterator gpi = const_cast<supernode *> (this)->start_phis ();
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      const gimple *stmt = gsi_stmt (gpi);
+      pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (pp, stmt);
+      pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+      pp_newline (pp);
+    }
+
+  /* Statements.  */
+  int i;
+  gimple *stmt;
+  FOR_EACH_VEC_ELT (m_stmts, i, stmt)
+    {
+      pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (pp, stmt);
+      pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+      pp_newline (pp);
+    }
+
+  pp_right_brace (pp);
+  pp_string (pp, "\"];\n\n");
+  pp_flush (pp);
+
+  /* Terminate "subgraph" */
+  gv->outdent ();
+  gv->println ("}");
+}
+
+/* Write an ID for this node to PP, for use in .dot output.  */
+
+void
+supernode::dump_dot_id (pretty_printer *pp) const
+{
+  pp_printf (pp, "node_%i", m_index);
+}
+
+/* Get a location_t for the start of this supernode.  */
+
+location_t
+supernode::get_start_location () const
+{
+  if (m_returning_call && m_returning_call->location != UNKNOWN_LOCATION)
+    return m_returning_call->location;
+
+  int i;
+  gimple *stmt;
+  FOR_EACH_VEC_ELT (m_stmts, i, stmt)
+    if (stmt->location != UNKNOWN_LOCATION)
+      return stmt->location;
+
+  if (entry_p ())
+    {
+      // TWEAK: show the decl instead; this leads to more readable output:
+      return DECL_SOURCE_LOCATION (m_fun->decl);
+
+      return m_fun->function_start_locus;
+    }
+  if (return_p ())
+    return m_fun->function_end_locus;
+
+  return UNKNOWN_LOCATION;
+}
+
+/* Get a location_t for the end of this supernode.  */
+
+location_t
+supernode::get_end_location () const
+{
+  int i;
+  gimple *stmt;
+  FOR_EACH_VEC_ELT_REVERSE (m_stmts, i, stmt)
+    if (stmt->location != UNKNOWN_LOCATION)
+      return stmt->location;
+
+  if (m_returning_call && m_returning_call->location != UNKNOWN_LOCATION)
+    return m_returning_call->location;
+
+  if (entry_p ())
+    return m_fun->function_start_locus;
+  if (return_p ())
+    return m_fun->function_end_locus;
+
+  return UNKNOWN_LOCATION;
+}
+
+/* Given STMT within this supernode, return its index within m_stmts.  */
+
+unsigned int
+supernode::get_stmt_index (const gimple *stmt) const
+{
+  unsigned i;
+  gimple *iter_stmt;
+  FOR_EACH_VEC_ELT (m_stmts, i, iter_stmt)
+    if (iter_stmt == stmt)
+      return i;
+  gcc_unreachable ();
+}
+
+/* Implementation of dedge::dump_dot for superedges.
+   Write a .dot edge to GV representing this superedge.  */
+
+void
+superedge::dump_dot (graphviz_out *gv, const dump_args_t &) const
+{
+  const char *style = "\"solid,bold\"";
+  const char *color = "black";
+  int weight = 10;
+  const char *constraint = "true";
+
+  switch (m_kind)
+    {
+    default:
+      gcc_unreachable ();
+    case SUPEREDGE_CFG_EDGE:
+      break;
+    case SUPEREDGE_CALL:
+      color = "red";
+      break;
+    case SUPEREDGE_RETURN:
+      color = "green";
+      break;
+    case SUPEREDGE_INTRAPROCEDURAL_CALL:
+      style = "\"dotted\"";
+      break;
+    }
+
+  /* Adapted from graph.c:draw_cfg_node_succ_edges.  */
+  if (::edge cfg_edge = get_any_cfg_edge ())
+    {
+      if (cfg_edge->flags & EDGE_FAKE)
+	{
+	  style = "dotted";
+	  color = "green";
+	  weight = 0;
+	}
+      else if (cfg_edge->flags & EDGE_DFS_BACK)
+	{
+	  style = "\"dotted,bold\"";
+	  color = "blue";
+	  weight = 10;
+	}
+      else if (cfg_edge->flags & EDGE_FALLTHRU)
+	{
+	  color = "blue";
+	  weight = 100;
+	}
+
+      if (cfg_edge->flags & EDGE_ABNORMAL)
+	color = "red";
+    }
+
+  gv->write_indent ();
+
+  pretty_printer *pp = gv->get_pp ();
+
+  m_src->dump_dot_id (pp);
+  pp_string (pp, " -> ");
+  m_dest->dump_dot_id (pp);
+  pp_printf (pp,
+	     (" [style=%s, color=%s, weight=%d, constraint=%s,"
+	      " ltail=\"cluster_node_%i\", lhead=\"cluster_node_%i\""
+	      " headlabel=\""),
+	     style, color, weight, constraint,
+	     m_src->m_index, m_dest->m_index);
+
+  dump_label_to_pp (pp, false);
+
+  pp_printf (pp, "\"];\n");
+}
+
+/* If this is an intraprocedural superedge, return the associated
+   CFG edge.  Otherwise, return NULL.  */
+
+::edge
+superedge::get_any_cfg_edge () const
+{
+  if (const cfg_superedge *sub = dyn_cast_cfg_superedge ())
+    return sub->get_cfg_edge ();
+  return NULL;
+}
+
+/* If this is an interprocedural superedge, return the associated
+   cgraph_edge *.  Otherwise, return NULL.  */
+
+cgraph_edge *
+superedge::get_any_callgraph_edge () const
+{
+  if (const callgraph_superedge *sub = dyn_cast_callgraph_superedge ())
+    return sub->m_cedge;
+  return NULL;
+}
+
+/* Build a description of this superedge (e.g. "true" for the true
+   edge of a conditional, or "case 42:" for a switch case).
+
+   The caller is responsible for freeing the result.
+
+   If USER_FACING is false, the result also contains any underlying
+   CFG edge flags. e.g. " (flags FALLTHRU | DFS_BACK)".  */
+
+char *
+superedge::get_description (bool user_facing) const
+{
+  pretty_printer pp;
+  dump_label_to_pp (&pp, user_facing);
+  return xstrdup (pp_formatted_text (&pp));
+}
+
+/* Implementation of superedge::dump_label_to_pp for non-switch CFG
+   superedges.
+
+   For true/false edges, print "true" or "false" to PP.
+
+   If USER_FACING is false, also print flags on the underlying CFG edge to
+   PP.  */
+
+void
+cfg_superedge::dump_label_to_pp (pretty_printer *pp,
+				 bool user_facing) const
+{
+  if (true_value_p ())
+    pp_printf (pp, "true");
+  else if (false_value_p ())
+    pp_printf (pp, "false");
+
+  if (user_facing)
+    return;
+
+  /* Express edge flags as a string with " | " separator.
+     e.g. " (flags FALLTHRU | DFS_BACK)".  */
+  if (get_flags ())
+    {
+      pp_string (pp, " (flags ");
+      bool seen_flag = false;
+#define DEF_EDGE_FLAG(NAME,IDX)			\
+  do {						\
+    if (get_flags () & EDGE_##NAME)			\
+      {						\
+	if (seen_flag)				\
+	  pp_string (pp, " | ");			\
+	pp_printf (pp, "%s", (#NAME));		\
+	seen_flag = true;			\
+      }						\
+  } while (0);
+#include "cfg-flags.def"
+#undef DEF_EDGE_FLAG
+      pp_string (pp, ")");
+    }
+
+  /* Otherwise, no label.  */
+}
+
+/* Get the phi argument for PHI for this CFG edge.  */
+
+tree
+cfg_superedge::get_phi_arg (const gphi *phi) const
+{
+  size_t index = m_cfg_edge->dest_idx;
+  return gimple_phi_arg_def (phi, index);
+}
+
+/* Implementation of superedge::dump_label_to_pp for CFG superedges for
+   "switch" statements.
+
+   Print "case VAL:", "case LOWER ... UPPER:", or "default:" to PP.  */
+
+void
+switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
+					bool user_facing ATTRIBUTE_UNUSED) const
+{
+  tree case_label = get_case_label ();
+  gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
+  tree lower_bound = CASE_LOW (case_label);
+  tree upper_bound = CASE_HIGH (case_label);
+  if (lower_bound)
+    {
+      pp_printf (pp, "case ");
+      dump_generic_node (pp, lower_bound, 0, (dump_flags_t)0, false);
+      if (upper_bound)
+	{
+	  pp_printf (pp, " ... ");
+	  dump_generic_node (pp, upper_bound, 0, (dump_flags_t)0, false);
+	}
+      pp_printf (pp, ":");
+    }
+  else
+    pp_printf (pp, "default:");
+}
+
+/* Get the case label for this "switch" superedge.  */
+
+tree
+switch_cfg_superedge::get_case_label () const
+{
+  return gimple_switch_label (get_switch_stmt (), m_idx);
+}
+
+/* Implementation of superedge::dump_label_to_pp for interprocedural
+   superedges.  */
+
+void
+callgraph_superedge::dump_label_to_pp (pretty_printer *pp,
+				       bool user_facing ATTRIBUTE_UNUSED) const
+{
+  switch (m_kind)
+    {
+    default:
+    case SUPEREDGE_CFG_EDGE:
+      gcc_unreachable ();
+
+    case SUPEREDGE_CALL:
+      pp_printf (pp, "call");
+      break;
+
+    case SUPEREDGE_RETURN:
+      pp_printf (pp, "return");
+      break;
+
+    case SUPEREDGE_INTRAPROCEDURAL_CALL:
+      pp_printf (pp, "intraproc link");
+      break;
+    }
+}
+
+/* Get the function that was called at this interprocedural call/return
+   edge.  */
+
+function *
+callgraph_superedge::get_callee_function () const
+{
+  return m_cedge->callee->get_fun ();
+}
+
+/* Get the calling function at this interprocedural call/return edge.  */
+
+function *
+callgraph_superedge::get_caller_function () const
+{
+  return m_cedge->caller->get_fun ();
+}
+
+/* Get the fndecl that was called at this interprocedural call/return
+   edge.  */
+
+tree
+callgraph_superedge::get_callee_decl () const
+{
+  return get_callee_function ()->decl;
+}
+
+/* Get the calling fndecl at this interprocedural call/return edge.  */
+
+tree
+callgraph_superedge::get_caller_decl () const
+{
+  return get_caller_function ()->decl;
+}
+
+/* Given PARM_TO_FIND, a PARM_DECL, identify its index (writing it
+   to *OUT if OUT is non-NULL), and return the corresponding argument
+   at the callsite.  */
+
+tree
+callgraph_superedge::get_arg_for_parm (tree parm_to_find,
+				       callsite_expr *out) const
+{
+  gcc_assert  (TREE_CODE (parm_to_find) == PARM_DECL);
+
+  tree callee = get_callee_decl ();
+
+  int i = 0;
+  for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
+       iter_parm = DECL_CHAIN (iter_parm), ++i)
+    {
+      if (iter_parm == parm_to_find)
+	{
+	  if (out)
+	    *out = callsite_expr::from_zero_based_param (i);
+	  return gimple_call_arg (get_call_stmt (), i);
+	}
+    }
+
+  /* Not found.  */
+  return NULL_TREE;
+}
+
+/* Look for a use of ARG_TO_FIND as an argument at this callsite.
+   If found, return the default SSA def of the corresponding parm within
+   the callee, and if OUT is non-NULL, write the index to *OUT.
+   Only the first match is handled.  */
+
+tree
+callgraph_superedge::get_parm_for_arg (tree arg_to_find,
+				       callsite_expr *out) const
+{
+  tree callee = get_callee_decl ();
+
+  int i = 0;
+  for (tree iter_parm = DECL_ARGUMENTS (callee); iter_parm;
+       iter_parm = DECL_CHAIN (iter_parm), ++i)
+    {
+      tree param = gimple_call_arg (get_call_stmt (), i);
+      if (arg_to_find == param)
+	{
+	  if (out)
+	    *out = callsite_expr::from_zero_based_param (i);
+	  return ssa_default_def (get_callee_function (), iter_parm);
+	}
+    }
+
+  /* Not found.  */
+  return NULL_TREE;
+}
+
+/* Map caller_expr back to an expr within the callee, or return NULL_TREE.
+   If non-NULL is returned, populate OUT.  */
+
+tree
+callgraph_superedge::map_expr_from_caller_to_callee (tree caller_expr,
+						     callsite_expr *out) const
+{
+  /* Is it an argument (actual param)?  If so, convert to
+     parameter (formal param).  */
+  tree parm = get_parm_for_arg (caller_expr, out);
+  if (parm)
+    return parm;
+  /* Otherwise try return value.  */
+  if (caller_expr == gimple_call_lhs (get_call_stmt ()))
+    {
+      if (out)
+	*out = callsite_expr::from_return_value ();
+      return DECL_RESULT (get_callee_decl ());
+    }
+
+  return NULL_TREE;
+}
+
+/* Map callee_expr back to an expr within the caller, or return NULL_TREE.
+   If non-NULL is returned, populate OUT.  */
+
+tree
+callgraph_superedge::map_expr_from_callee_to_caller (tree callee_expr,
+						     callsite_expr *out) const
+{
+  if (callee_expr == NULL_TREE)
+    return NULL_TREE;
+
+  /* If it's a parameter (formal param), get the argument (actual param).  */
+  if (TREE_CODE (callee_expr) == PARM_DECL)
+    return get_arg_for_parm (callee_expr, out);
+
+  /* Similar for the default SSA name of the PARM_DECL.  */
+  if (TREE_CODE (callee_expr) == SSA_NAME
+      && SSA_NAME_IS_DEFAULT_DEF (callee_expr)
+      && TREE_CODE (SSA_NAME_VAR (callee_expr)) == PARM_DECL)
+    return get_arg_for_parm (SSA_NAME_VAR (callee_expr), out);
+
+  /* Otherwise try return value.  */
+  if (callee_expr == DECL_RESULT (get_callee_decl ()))
+    {
+      if (out)
+	*out = callsite_expr::from_return_value ();
+      return gimple_call_lhs (get_call_stmt ());
+    }
+
+  return NULL_TREE;
+}
diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h
new file mode 100644
index 0000000..78ae93a
--- /dev/null
+++ b/gcc/analyzer/supergraph.h
@@ -0,0 +1,560 @@ 
+/* "Supergraph" classes that combine CFGs and callgraph into one digraph.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_SUPERGRAPH_H
+#define GCC_ANALYZER_SUPERGRAPH_H
+
+#include "ordered-hash-map.h"
+#include "cgraph.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "analyzer/digraph.h"
+
+/* Forward decls, using indentation to show inheritance.  */
+
+class supergraph;
+class supernode;
+class superedge;
+  class callgraph_superedge;
+    class call_superedge;
+    class return_superedge;
+  class cfg_superedge;
+    class switch_cfg_superedge;
+class supercluster;
+class dot_annotator;
+
+class logger;
+
+/* An enum for discriminating between superedge subclasses.  */
+
+enum edge_kind
+{
+  SUPEREDGE_CFG_EDGE,
+  SUPEREDGE_CALL,
+  SUPEREDGE_RETURN,
+  SUPEREDGE_INTRAPROCEDURAL_CALL
+};
+
+/* Flags for controlling the appearance of .dot dumps.  */
+
+enum supergraph_dot_flags
+{
+  SUPERGRAPH_DOT_SHOW_BBS = (1 << 0)
+};
+
+/* A traits struct describing the family of node, edge and digraph
+   classes for supergraphs.  */
+
+struct supergraph_traits
+{
+  typedef supernode node_t;
+  typedef superedge edge_t;
+  typedef supergraph graph_t;
+  struct dump_args_t
+  {
+    dump_args_t (enum supergraph_dot_flags flags,
+		 const dot_annotator *node_annotator)
+    : m_flags (flags),
+      m_node_annotator (node_annotator)
+    {}
+
+    enum supergraph_dot_flags m_flags;
+    const dot_annotator *m_node_annotator;
+  };
+  typedef supercluster cluster_t;
+};
+
+/* A "supergraph" is a directed graph formed by joining together all CFGs,
+   linking them via interprocedural call and return edges.
+
+   Basic blocks are split at callsites, so that a call statement occurs
+   twice: once at the end of a supernode, and a second instance at the
+   start of the next supernode (to handle the return).  */
+
+class supergraph : public digraph<supergraph_traits>
+{
+public:
+  supergraph (logger *logger);
+
+  supernode *get_node_for_function_entry (function *fun) const
+  {
+    return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (fun));
+  }
+
+  supernode *get_node_for_function_exit (function *fun) const
+  {
+    return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (fun));
+  }
+
+  supernode *get_node_for_block (basic_block bb) const
+  {
+    return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
+  }
+
+  /* Get the supernode containing the second half of the gcall *
+     at an interprocedural call, within the caller.  */
+  supernode *get_caller_next_node (cgraph_edge *edge) const
+  {
+    return (*const_cast <cgraph_edge_to_node_t &>
+	      (m_cgraph_edge_to_caller_next_node).get (edge));
+  }
+
+  call_superedge *get_edge_for_call (cgraph_edge *edge) const
+  {
+    return (*const_cast <cgraph_edge_to_call_superedge_t &>
+	      (m_cgraph_edge_to_call_superedge).get (edge));
+  }
+
+  return_superedge *get_edge_for_return (cgraph_edge *edge) const
+  {
+    return (*const_cast <cgraph_edge_to_return_superedge_t &>
+	      (m_cgraph_edge_to_return_superedge).get (edge));
+  }
+
+  superedge *get_intraprocedural_edge_for_call (cgraph_edge *edge) const
+  {
+    return (*const_cast <cgraph_edge_to_intraproc_superedge_t &>
+	      (m_cgraph_edge_to_intraproc_superedge).get (edge));
+  }
+
+  cfg_superedge *get_edge_for_cfg_edge (edge e) const
+  {
+    return (*const_cast <cfg_edge_to_cfg_superedge_t &>
+	      (m_cfg_edge_to_cfg_superedge).get (e));
+  }
+
+  supernode *get_supernode_for_stmt (const gimple *stmt) const
+  {
+    return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get
+	    (const_cast <gimple *> (stmt)));
+  }
+
+  void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const;
+  void dump_dot_to_file (FILE *fp, const dump_args_t &) const;
+  void dump_dot (const char *path, const dump_args_t &) const;
+
+  int num_nodes () const { return m_nodes.length (); }
+  int num_edges () const { return m_edges.length (); }
+
+  supernode *get_node_by_index (int idx) const
+  {
+    return m_nodes[idx];
+  }
+
+  unsigned get_num_snodes (function *fun) const
+  {
+    function_to_num_snodes_t &map
+      = const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
+    return *map.get (fun);
+  }
+
+private:
+  supernode *add_node (function *fun, basic_block bb, gcall *returning_call,
+		       gimple_seq phi_nodes);
+  cfg_superedge *add_cfg_edge (supernode *src, supernode *dest, ::edge e, int idx);
+  call_superedge *add_call_superedge (supernode *src, supernode *dest,
+				      cgraph_edge *cedge);
+  return_superedge *add_return_superedge (supernode *src, supernode *dest,
+					  cgraph_edge *cedge);
+
+  /* Data.  */
+
+  typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t;
+  bb_to_node_t m_bb_to_initial_node;
+  bb_to_node_t m_bb_to_final_node;
+
+  typedef ordered_hash_map<cgraph_edge *, supernode *> cgraph_edge_to_node_t;
+  cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node;
+  cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node;
+
+  typedef ordered_hash_map< ::edge, cfg_superedge *>
+    cfg_edge_to_cfg_superedge_t;
+  cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge;
+
+  typedef ordered_hash_map<cgraph_edge *, call_superedge *>
+    cgraph_edge_to_call_superedge_t;
+  cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge;
+
+  typedef ordered_hash_map<cgraph_edge *, return_superedge *>
+    cgraph_edge_to_return_superedge_t;
+  cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge;
+
+  typedef ordered_hash_map<cgraph_edge *, superedge *>
+    cgraph_edge_to_intraproc_superedge_t;
+  cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge;
+
+  typedef ordered_hash_map<gimple *, supernode *> stmt_to_node_t;
+  stmt_to_node_t m_stmt_to_node_t;
+
+  typedef hash_map<function *, unsigned> function_to_num_snodes_t;
+  function_to_num_snodes_t m_function_to_num_snodes;
+};
+
+/* A node within a supergraph.  */
+
+class supernode : public dnode<supergraph_traits>
+{
+ public:
+  supernode (function *fun, basic_block bb, gcall *returning_call,
+	     gimple_seq phi_nodes, int index)
+  : m_fun (fun), m_bb (bb), m_returning_call (returning_call),
+    m_phi_nodes (phi_nodes), m_index (index)
+  {}
+
+  bool entry_p () const
+  {
+    return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
+  }
+
+  bool return_p () const
+  {
+    return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
+  }
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const OVERRIDE;
+  void dump_dot_id (pretty_printer *pp) const;
+
+  location_t get_start_location () const;
+  location_t get_end_location () const;
+
+  /* Returns iterator at the start of the list of phi nodes, if any.  */
+  gphi_iterator start_phis ()
+  {
+    gimple_seq *pseq = &m_phi_nodes;
+
+    /* Adapted from gsi_start_1. */
+    gphi_iterator i;
+
+    i.ptr = gimple_seq_first (*pseq);
+    i.seq = pseq;
+    i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
+
+    return i;
+  }
+
+  gimple *get_last_stmt () const
+  {
+    if (m_stmts.length () == 0)
+      return NULL;
+    return m_stmts[m_stmts.length () - 1];
+  }
+
+  gcall *get_final_call () const
+  {
+    gimple *stmt = get_last_stmt ();
+    if (stmt == NULL)
+      return NULL;
+    return dyn_cast<gcall *> (stmt);
+  }
+
+  unsigned int get_stmt_index (const gimple *stmt) const;
+
+  function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
+  const basic_block m_bb;
+  gcall * const m_returning_call; // for handling the result of a returned call
+  gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
+  auto_vec<gimple *> m_stmts;
+  const int m_index; /* unique within the supergraph as a whole.  */
+};
+
+/* An abstract base class encapsulating an edge within a supergraph.
+   Edges can be CFG edges, or calls/returns for callgraph edges.  */
+
+class superedge : public dedge<supergraph_traits>
+{
+ public:
+  virtual ~superedge () {}
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const;
+
+  virtual void dump_label_to_pp (pretty_printer *pp,
+				 bool user_facing) const = 0;
+
+  enum edge_kind get_kind () const { return m_kind; }
+
+  virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
+  virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
+  virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
+  virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
+  virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
+  virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
+  virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
+  virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
+  virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
+
+  ::edge get_any_cfg_edge () const;
+  cgraph_edge *get_any_callgraph_edge () const;
+
+  char *get_description (bool user_facing) const;
+
+ protected:
+  superedge (supernode *src, supernode *dest, enum edge_kind kind)
+  : dedge (src, dest),
+    m_kind (kind)
+  {}
+
+ public:
+  const enum edge_kind m_kind;
+};
+
+/* An ID representing an expression at a callsite:
+   either a parameter index, or the return value (or unknown).  */
+
+class callsite_expr
+{
+ public:
+  callsite_expr () : m_val (-1) {}
+
+  static callsite_expr from_zero_based_param (int idx)
+  {
+    return callsite_expr (idx + 1);
+  }
+
+  static callsite_expr from_return_value ()
+  {
+    return callsite_expr (0);
+  }
+
+  bool param_p () const
+  {
+    return m_val > 0;
+  }
+
+  bool return_value_p () const
+  {
+    return m_val == 0;
+  }
+
+ private:
+  callsite_expr (int val) : m_val (val) {}
+
+  int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown".  */
+};
+
+/* A subclass of superedge with an associated callgraph edge (either a
+   call or a return).  */
+
+class callgraph_superedge : public superedge
+{
+ public:
+  callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
+		       cgraph_edge *cedge)
+  : superedge (src, dst, kind),
+    m_cedge (cedge)
+  {}
+
+  void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
+    FINAL OVERRIDE;
+
+  function *get_callee_function () const;
+  function *get_caller_function () const;
+  tree get_callee_decl () const;
+  tree get_caller_decl () const;
+  gcall *get_call_stmt () const { return m_cedge->call_stmt; }
+  tree get_arg_for_parm (tree parm, callsite_expr *out) const;
+  tree get_parm_for_arg (tree arg, callsite_expr *out) const;
+  tree map_expr_from_caller_to_callee (tree caller_expr,
+				       callsite_expr *out) const;
+  tree map_expr_from_callee_to_caller (tree callee_expr,
+				       callsite_expr *out) const;
+
+  cgraph_edge *const m_cedge;
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
+{
+  return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
+	  || sedge->get_kind () == SUPEREDGE_CALL
+	  || sedge->get_kind () == SUPEREDGE_RETURN);
+}
+
+/* A subclass of superedge representing an interprocedural call.  */
+
+class call_superedge : public callgraph_superedge
+{
+ public:
+  call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
+  : callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
+  {}
+
+  callgraph_superedge *dyn_cast_callgraph_superedge () FINAL OVERRIDE
+  {
+    return this;
+  }
+  const callgraph_superedge *dyn_cast_callgraph_superedge () const
+    FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  call_superedge *dyn_cast_call_superedge () FINAL OVERRIDE
+  {
+    return this;
+  }
+  const call_superedge *dyn_cast_call_superedge () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  return_superedge *get_edge_for_return (const supergraph &sg) const
+  {
+    return sg.get_edge_for_return (m_cedge);
+  }
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const call_superedge *>::test (const superedge *sedge)
+{
+  return sedge->get_kind () == SUPEREDGE_CALL;
+}
+
+/* A subclass of superedge represesnting an interprocedural return.  */
+
+class return_superedge : public callgraph_superedge
+{
+ public:
+  return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
+  : callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
+  {}
+
+  callgraph_superedge *dyn_cast_callgraph_superedge () FINAL OVERRIDE
+  {
+    return this;
+  }
+  const callgraph_superedge *dyn_cast_callgraph_superedge () const
+    FINAL OVERRIDE
+  { return this; }
+
+  return_superedge *dyn_cast_return_superedge () FINAL OVERRIDE { return this; }
+  const return_superedge *dyn_cast_return_superedge () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  call_superedge *get_edge_for_call (const supergraph &sg) const
+  {
+    return sg.get_edge_for_call (m_cedge);
+  }
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const return_superedge *>::test (const superedge *sedge)
+{
+  return sedge->get_kind () == SUPEREDGE_RETURN;
+}
+
+/* A subclass of superedge that corresponds to a CFG edge.  */
+
+class cfg_superedge : public superedge
+{
+ public:
+  cfg_superedge (supernode *src, supernode *dst, ::edge e)
+  : superedge (src, dst, SUPEREDGE_CFG_EDGE),
+    m_cfg_edge (e)
+  {}
+
+  void dump_label_to_pp (pretty_printer *pp, bool user_facing) const OVERRIDE;
+  cfg_superedge *dyn_cast_cfg_superedge () FINAL OVERRIDE { return this; }
+  const cfg_superedge *dyn_cast_cfg_superedge () const FINAL OVERRIDE { return this; }
+
+  ::edge get_cfg_edge () const { return m_cfg_edge; }
+  int get_flags () const { return m_cfg_edge->flags; }
+  int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
+  int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
+  int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
+
+  tree get_phi_arg (const gphi *phi) const;
+
+ private:
+  const ::edge m_cfg_edge;
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
+{
+  return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
+}
+
+/* A subclass for edges from switch statements, retaining enough
+   information to identify the pertinent case, and for adding labels
+   when rendering via graphviz.  */
+
+class switch_cfg_superedge : public cfg_superedge {
+ public:
+  switch_cfg_superedge (supernode *src, supernode *dst, ::edge e, int idx)
+  : cfg_superedge (src, dst, e),
+    m_idx (idx)
+  {}
+
+  const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
+    FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
+    FINAL OVERRIDE;
+
+  gswitch *get_switch_stmt () const
+  {
+    return as_a <gswitch *> (m_src->get_last_stmt ());
+  }
+
+  tree get_case_label () const;
+
+ private:
+  const int m_idx;
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
+{
+  return sedge->dyn_cast_switch_cfg_superedge () != NULL;
+}
+
+/* Base class for adding additional content to the .dot output
+   for a supergraph.  */
+
+class dot_annotator
+{
+ public:
+  virtual ~dot_annotator () {}
+  virtual void add_node_annotations (pretty_printer *pp ATTRIBUTE_UNUSED,
+				     const supernode &n ATTRIBUTE_UNUSED)
+    const {}
+  virtual void add_stmt_annotations (pretty_printer *pp ATTRIBUTE_UNUSED,
+				     const gimple *stmt ATTRIBUTE_UNUSED)
+    const {}
+};
+
+extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt);
+
+#endif /* GCC_ANALYZER_SUPERGRAPH_H */