[18/41] analyzer: new files: supergraph.{cc|h}

Message ID 20200108090302.2425-19-dmalcolm@redhat.com
State New
Headers show
Series
  • v5 of analyzer patch kit
Related show

Commit Message

David Malcolm Jan. 8, 2020, 9:02 a.m.
Needs review.

Changed in v5:
- update ChangeLog path
- updated copyright years to include 2020

Changed in v4:
- Rework includes to avoid gcc-plugin.h
- Wrap everything with #if ENABLE_ANALYZER
- Replace auto_client_timevar with TV_ANALYZER_SUPERGRAPH
- Fix .dot output
  https://gcc.gnu.org/ml/gcc-patches/2019-11/msg02461.html
- Update for move of digraph.h

This patch adds a "supergraph" class that combines CFGs and callgraph into
one directed graph, along with "supernode" and "superedge" classes.

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

-- 
2.21.0

Comments

Jeff Law Jan. 10, 2020, 5:24 p.m. | #1
On Wed, 2020-01-08 at 04:02 -0500, David Malcolm wrote:
> Needs review.

> 

> Changed in v5:

> - update ChangeLog path

> - updated copyright years to include 2020

> 

> Changed in v4:

> - Rework includes to avoid gcc-plugin.h

> - Wrap everything with #if ENABLE_ANALYZER

> - Replace auto_client_timevar with TV_ANALYZER_SUPERGRAPH

> - Fix .dot output

>   https://gcc.gnu.org/ml/gcc-patches/2019-11/msg02461.html

> - Update for move of digraph.h

> 

> This patch adds a "supergraph" class that combines CFGs and callgraph into

> one directed graph, along with "supernode" and "superedge" classes.

> 

> gcc/analyzer/ChangeLog:

> 	* supergraph.cc: New file.

> 	* supergraph.h: New file.

So in the back of my mind has always been how else can we use the
infrastructure you're designing & implementing.  I'd always hoped the
supergraph in particular would prove useful and it may.  But I just
realized something as I was looking at the implementation.

It appears that you copy phis/statements from basic blocks into the
supernodes.  That has important implications.  For example, we don't
have mechanisms to keep the two views in sync.  So if we need the
supergraph for something, we're probably going to need to rebuild it.

I don't think that implies we need to do anything now, just an
important restriction we need to keep in mind if we want to re-use some
of this stuff later.

I don't see any EH handling mechansisms.  I realize we haven't focused
on C++ and thus EH hasn't been the top of our minds, but are we going
to have to handle that at some point?


> diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h

> new file mode 100644

> index 000000000000..81ea3ac08198

> --- /dev/null

> +++ b/gcc/analyzer/supergraph.h

> @@ -0,0 +1,564 @@

> +/* "Supergraph" classes that combine CFGs and callgraph into one digraph.

> +   Copyright (C) 2019-2020 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 "options.h"

> +#include "cgraph.h"

> +#include "function.h"

> +#include "cfg.h"

> +#include "basic-block.h"

> +#include "gimple.h"

> +#include "gimple-iterator.h"

> +#include "digraph.h"

Ugh.  Policy is to avoid doing this kind of thing.  Instead the
includes are supposed to be in the .cc files.  This can be fixed
without going through another review cycle.

OK with the #includes fixed.

jeff
David Malcolm Jan. 10, 2020, 5:40 p.m. | #2
On Fri, 2020-01-10 at 10:24 -0700, Jeff Law wrote:
> On Wed, 2020-01-08 at 04:02 -0500, David Malcolm wrote:

> > Needs review.

> > 

> > Changed in v5:

> > - update ChangeLog path

> > - updated copyright years to include 2020

> > 

> > Changed in v4:

> > - Rework includes to avoid gcc-plugin.h

> > - Wrap everything with #if ENABLE_ANALYZER

> > - Replace auto_client_timevar with TV_ANALYZER_SUPERGRAPH

> > - Fix .dot output

> >   https://gcc.gnu.org/ml/gcc-patches/2019-11/msg02461.html

> > - Update for move of digraph.h

> > 

> > This patch adds a "supergraph" class that combines CFGs and

> > callgraph into

> > one directed graph, along with "supernode" and "superedge" classes.

> > 

> > gcc/analyzer/ChangeLog:

> > 	* supergraph.cc: New file.

> > 	* supergraph.h: New file.

> So in the back of my mind has always been how else can we use the

> infrastructure you're designing & implementing.  I'd always hoped the

> supergraph in particular would prove useful and it may.  But I just

> realized something as I was looking at the implementation.

> 

> It appears that you copy phis/statements from basic blocks into the

> supernodes.  That has important implications.  For example, we don't

> have mechanisms to keep the two views in sync.  So if we need the

> supergraph for something, we're probably going to need to rebuild it.

> 

> I don't think that implies we need to do anything now, just an

> important restriction we need to keep in mind if we want to re-use

> some

> of this stuff later.


Right - the analyzer pass builds a representation that's useful for it,
does a bunch of things to it, then tears it down; there's no
interaction with changes to the IR - but for the analyzer there doesn't
need to be.

> I don't see any EH handling mechansisms.  I realize we haven't

> focused

> on C++ and thus EH hasn't been the top of our minds, but are we going

> to have to handle that at some point?


Fair point.  The scope of the analyzer is C only right now, though I
think the only place I've documented that is in the internal docs,
where the Limitations section has "Only for C so far".  But I want to
support C++ in future releases.

> > diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h

> > new file mode 100644

> > index 000000000000..81ea3ac08198

> > --- /dev/null

> > +++ b/gcc/analyzer/supergraph.h

> > @@ -0,0 +1,564 @@

> > +/* "Supergraph" classes that combine CFGs and callgraph into one

> > digraph.

> > +   Copyright (C) 2019-2020 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 "options.h"

> > +#include "cgraph.h"

> > +#include "function.h"

> > +#include "cfg.h"

> > +#include "basic-block.h"

> > +#include "gimple.h"

> > +#include "gimple-iterator.h"

> > +#include "digraph.h"

> Ugh.  Policy is to avoid doing this kind of thing.  Instead the

> includes are supposed to be in the .cc files.  


<rant>
FWIW, I've never understood the benefit of this policy; it feels like a
violation of the DRY principle, and I always find myself wondering
things like "what do I need to include before I can include gimple.h?".
</rant>

But time is short; I'll copy and paste the includes.

> This can be fixed

> without going through another review cycle.

> 

> OK with the #includes fixed.


Thanks; will do.

> jeff

>
Jeff Law Jan. 10, 2020, 5:44 p.m. | #3
On Fri, 2020-01-10 at 12:40 -0500, David Malcolm wrote:
> > 


> On Fri, 2020-01-10 at 10:24 -0700, Jeff Law wrote:

> > I don't see any EH handling mechansisms.  I realize we haven't

> > focused

> > on C++ and thus EH hasn't been the top of our minds, but are we going

> > to have to handle that at some point?

> 

> Fair point.  The scope of the analyzer is C only right now, though I

> think the only place I've documented that is in the internal docs,

> where the Limitations section has "Only for C so far".  But I want to

> support C++ in future releases.

I'd probably have to review the low level EH implementation internals. 
Worst case it's just  more edges where it's not immediately obvious
when/why/how those edges get traversed.


> 

> > > diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h

> > > new file mode 100644

> > > index 000000000000..81ea3ac08198

> > > --- /dev/null

> > > +++ b/gcc/analyzer/supergraph.h

> > > @@ -0,0 +1,564 @@

> > > +/* "Supergraph" classes that combine CFGs and callgraph into one

> > > digraph.

> > > +   Copyright (C) 2019-2020 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 "options.h"

> > > +#include "cgraph.h"

> > > +#include "function.h"

> > > +#include "cfg.h"

> > > +#include "basic-block.h"

> > > +#include "gimple.h"

> > > +#include "gimple-iterator.h"

> > > +#include "digraph.h"

> > Ugh.  Policy is to avoid doing this kind of thing.  Instead the

> > includes are supposed to be in the .cc files.  

> 

> <rant>

> FWIW, I've never understood the benefit of this policy; it feels like a

> violation of the DRY principle, and I always find myself wondering

> things like "what do I need to include before I can include gimple.h?".

> </rant>

> 

> But time is short; I'll copy and paste the includes.


It was to help us untangle the headers, which was effectively done a
few cycles ago.  What needs to happen now is a re-introduction of
*sane* inclusions.    But that keeps getting pushed out.

Jeff

Patch

diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc
new file mode 100644
index 000000000000..a17e7d6e9e53
--- /dev/null
+++ b/gcc/analyzer/supergraph.cc
@@ -0,0 +1,955 @@ 
+/* "Supergraph" classes that combine CFGs and callgraph into one digraph.
+   Copyright (C) 2019-2020 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 "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 "function.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 "cfganal.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/analyzer-logging.h"
+
+#if ENABLE_ANALYZER
+
+/* 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_timevar tv (TV_ANALYZER_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 .dot node 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 (gv, *this);
+
+  gv->write_indent ();
+  dump_dot_id (pp);
+  pp_printf (pp,
+	     " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
+	     "lightgrey");
+  pp_string (pp, "<TABLE BORDER=\"0\">");
+  pp_write_text_to_stream (pp);
+
+  if (m_returning_call)
+    {
+      gv->begin_tr ();
+      pp_string (pp, "returning call: ");
+      gv->end_tr ();
+
+      gv->begin_tr ();
+      pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
+      pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_tr ();
+
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, m_returning_call);
+      pp_newline (pp);
+    }
+
+  if (entry_p ())
+    {
+      pp_string (pp, "<TR><TD>ENTRY</TD></TR>");
+      pp_newline (pp);
+    }
+
+  if (return_p ())
+    {
+      pp_string (pp, "<TR><TD>EXIT</TD></TR>");
+      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);
+      gv->begin_tr ();
+      pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
+      pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_tr ();
+
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, stmt);
+
+      pp_newline (pp);
+    }
+
+  /* Statements.  */
+  int i;
+  gimple *stmt;
+  FOR_EACH_VEC_ELT (m_stmts, i, stmt)
+    {
+      gv->begin_tr ();
+      pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
+      pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_tr ();
+
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, stmt);
+
+      pp_newline (pp);
+    }
+
+  pp_string (pp, "</TABLE>>];\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;
+}
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h
new file mode 100644
index 000000000000..81ea3ac08198
--- /dev/null
+++ b/gcc/analyzer/supergraph.h
@@ -0,0 +1,564 @@ 
+/* "Supergraph" classes that combine CFGs and callgraph into one digraph.
+   Copyright (C) 2019-2020 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 "options.h"
+#include "cgraph.h"
+#include "function.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "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 (graphviz_out *gv ATTRIBUTE_UNUSED,
+				     const supernode &n ATTRIBUTE_UNUSED)
+    const {}
+  virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
+				     const gimple *stmt ATTRIBUTE_UNUSED)
+    const {}
+};
+
+extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt);
+
+#endif /* GCC_ANALYZER_SUPERGRAPH_H */