[45/49] analyzer: new files: engine.{cc|h}

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

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m.
This patch adds the core analysis code, which explores "interesting"
interprocedual paths in the code, updating state machines to check
for API misuses, and issuing diagnostics for such misuses.

gcc/ChangeLog:
	* analyzer/engine.cc: New file.
	* analyzer/engine.h: New file.
---
 gcc/analyzer/engine.cc | 3416 ++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/analyzer/engine.h  |   26 +
 2 files changed, 3442 insertions(+)
 create mode 100644 gcc/analyzer/engine.cc
 create mode 100644 gcc/analyzer/engine.h

-- 
1.8.5.3

Patch

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
new file mode 100644
index 0000000..34941d2
--- /dev/null
+++ b/gcc/analyzer/engine.cc
@@ -0,0 +1,3416 @@ 
+/* The analysis "engine".
+   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 "params.h"
+#include "gcc-rich-location.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/analysis-plan.h"
+#include "analyzer/state-purge.h"
+
+/* For an overview, see gcc/doc/analyzer.texi.  */
+
+static int readability_comparator (const void *p1, const void *p2);
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class impl_region_model_context : public region_model_context, public log_user.  */
+
+impl_region_model_context::
+impl_region_model_context (exploded_graph &eg,
+			   const exploded_node *enode_for_diag,
+			   const program_state *old_state,
+			   program_state *new_state,
+			   state_change *change,
+			   const gimple *stmt,
+			   stmt_finder *stmt_finder)
+: log_user (eg.get_logger ()), m_eg (&eg),
+  m_enode_for_diag (enode_for_diag),
+  m_old_state (old_state),
+  m_new_state (new_state),
+  m_change (change),
+  m_stmt (stmt),
+  m_stmt_finder (stmt_finder),
+  m_ext_state (eg.get_ext_state ())
+{
+}
+
+impl_region_model_context::
+impl_region_model_context (program_state *state,
+			   state_change *change,
+			   const extrinsic_state &ext_state)
+: log_user (NULL), m_eg (NULL), m_enode_for_diag (NULL),
+  m_old_state (NULL),
+  m_new_state (state),
+  m_change (change),
+  m_stmt (NULL),
+  m_stmt_finder (NULL),
+  m_ext_state (ext_state)
+{
+}
+
+void
+impl_region_model_context::warn (pending_diagnostic *d)
+{
+  LOG_FUNC (get_logger ());
+  if (m_eg)
+    m_eg->get_diagnostic_manager ().add_diagnostic
+      (m_enode_for_diag, m_enode_for_diag->get_supernode (),
+       m_stmt, m_stmt_finder, d);
+}
+
+void
+impl_region_model_context::remap_svalue_ids (const svalue_id_map &map)
+{
+  m_new_state->remap_svalue_ids (map);
+  if (m_change)
+    m_change->remap_svalue_ids (map);
+}
+
+int
+impl_region_model_context::on_svalue_purge (svalue_id first_unused_sid,
+					    const svalue_id_map &map)
+{
+  int total = 0;
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
+    {
+      const state_machine &sm = m_ext_state.get_sm (sm_idx);
+      total += smap->on_svalue_purge (sm, sm_idx, first_unused_sid,
+				      map, this);
+    }
+  if (m_change)
+    total += m_change->on_svalue_purge (first_unused_sid);
+  return total;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class setjmp_svalue : public svalue.  */
+
+/* Compare the fields of this setjmp_svalue with OTHER, returning true
+   if they are equal.
+   For use by svalue::operator==.  */
+
+bool
+setjmp_svalue::compare_fields (const setjmp_svalue &other) const
+{
+  return m_enode == other.m_enode;
+}
+
+/* Implementation of svalue::add_to_hash vfunc for setjmp_svalue.  */
+
+void
+setjmp_svalue::add_to_hash (inchash::hash &hstate) const
+{
+  hstate.add_int (m_enode->m_index);
+}
+
+/* Get the index of the stored exploded_node.  */
+
+int
+setjmp_svalue::get_index () const
+{
+  return m_enode->m_index;
+}
+
+/* Implementation of svalue::print_details vfunc for setjmp_svalue.  */
+
+void
+setjmp_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED,
+			      svalue_id this_sid ATTRIBUTE_UNUSED,
+			      pretty_printer *pp) const
+{
+  pp_printf (pp, "setjmp: EN: %i", m_enode->m_index);
+}
+
+
+////////////////////////////////////////////////////////////////////////////
+
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Concrete implementation of sm_context, wiring it up to the rest of this
+   file.  */
+
+class impl_sm_context : public sm_context, public log_user
+{
+public:
+  impl_sm_context (exploded_graph &eg,
+		   int sm_idx,
+		   const state_machine &sm,
+		   const exploded_node *enode_for_diag,
+		   const program_state *old_state,
+		   program_state *new_state,
+		   state_change *change,
+		   const sm_state_map *old_smap,
+		   sm_state_map *new_smap,
+		   stmt_finder *stmt_finder = NULL)
+  : sm_context (sm_idx, sm),
+    log_user (eg.get_logger ()),
+    m_eg (eg), m_enode_for_diag (enode_for_diag),
+    m_old_state (old_state), m_new_state (new_state),
+    m_change (change),
+    m_old_smap (old_smap), m_new_smap (new_smap),
+    m_stmt_finder (stmt_finder)
+  {
+  }
+
+  void on_transition (const supernode *node  ATTRIBUTE_UNUSED,
+		      const gimple *stmt  ATTRIBUTE_UNUSED,
+		      tree var,
+		      state_machine::state_t from,
+		      state_machine::state_t to,
+		      tree origin) FINAL OVERRIDE
+  {
+    LOG_FUNC (get_logger ());
+    impl_region_model_context old_ctxt
+      (m_eg, m_enode_for_diag, NULL, NULL/*m_enode->get_state ()*/,
+       m_change, stmt);
+    svalue_id var_old_sid
+      = m_old_state->m_region_model->get_rvalue (var, &old_ctxt);
+
+    impl_region_model_context new_ctxt (m_eg, m_enode_for_diag,
+					m_old_state, m_new_state,
+					m_change, NULL);
+    svalue_id var_new_sid
+      = m_new_state->m_region_model->get_rvalue (var, &new_ctxt);
+    svalue_id origin_new_sid
+      = m_new_state->m_region_model->get_rvalue (origin, &new_ctxt);
+
+    state_machine::state_t current = m_old_smap->get_state (var_old_sid);
+    if (current == from)
+      {
+	if (get_logger ())
+	  log ("%s: state transition of %qE: %s -> %s",
+	       m_sm.get_name (),
+	       var,
+	       m_sm.get_state_name (from),
+	       m_sm.get_state_name (to));
+	m_new_smap->set_state (m_new_state->m_region_model, var_new_sid,
+			       to, origin_new_sid);
+	if (m_change)
+	  m_change->add_sm_change (m_sm_idx, var_new_sid, from, to);
+      }
+  }
+
+  void warn_for_state (const supernode *snode, const gimple *stmt,
+		       tree var, state_machine::state_t state,
+		       pending_diagnostic *d) FINAL OVERRIDE
+  {
+    LOG_FUNC (get_logger ());
+    gcc_assert (d); // take ownership
+
+    impl_region_model_context old_ctxt
+      (m_eg, m_enode_for_diag, m_old_state, m_new_state, m_change, NULL);
+    svalue_id var_old_sid
+      = m_old_state->m_region_model->get_rvalue (var, &old_ctxt);
+    state_machine::state_t current = m_old_smap->get_state (var_old_sid);
+    if (state == current)
+      {
+	m_eg.get_diagnostic_manager ().add_diagnostic
+	  (&m_sm, m_enode_for_diag, snode, stmt, m_stmt_finder,
+	   var, state, d);
+      }
+    else
+      delete d;
+  }
+
+  /* Hook for picking more readable trees for SSA names of temporaries,
+     so that rather than e.g.
+       "double-free of '<unknown>'"
+     we can print:
+       "double-free of 'inbuf.data'".  */
+
+  tree get_readable_tree (tree expr) FINAL OVERRIDE
+  {
+    /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
+       likely to be the least surprising tree to report.  */
+    if (TREE_CODE (expr) != SSA_NAME)
+      return expr;
+    if (SSA_NAME_VAR (expr) != NULL)
+      return expr;
+
+    gcc_assert (m_new_state);
+    svalue_id sid = m_new_state->m_region_model->get_rvalue (expr, NULL);
+    /* Find trees for all regions storing the value.  */
+    auto_vec<path_var> pvs;
+    m_new_state->m_region_model->get_path_vars_for_svalue (sid, &pvs);
+    if (pvs.length () < 1)
+      return expr;
+    /* Pick the "best" such tree.  */
+    // TODO: should we also consider (and consolidate) equiv classes?
+    pvs.qsort (readability_comparator);
+    return pvs[0].m_tree;
+  }
+
+  exploded_graph &m_eg;
+  const exploded_node *m_enode_for_diag;
+  const program_state *m_old_state;
+  program_state *m_new_state;
+  state_change *m_change;
+  const sm_state_map *m_old_smap;
+  sm_state_map *m_new_smap;
+  stmt_finder *m_stmt_finder;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Subclass of stmt_finder for finding the best stmt to report the leak at,
+   given the emission path.  */
+
+class leak_stmt_finder : public stmt_finder
+{
+public:
+  leak_stmt_finder (const exploded_graph &eg, tree var)
+  : m_eg (eg), m_var (var) {}
+
+  stmt_finder *clone () const FINAL OVERRIDE
+  {
+    return new leak_stmt_finder (m_eg, m_var);
+  }
+
+  const gimple *find_stmt (const exploded_path &epath)
+    FINAL OVERRIDE
+  {
+    LOG_FUNC (m_eg.get_logger ());
+
+    if (TREE_CODE (m_var) == SSA_NAME)
+      {
+	/* Locate the final write to this SSA name in the path.  */
+	const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
+
+	int idx_of_def_stmt;
+	bool found = epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt);
+	if (!found)
+	  goto not_found;
+
+	/* What was the next write to the underlying var
+	   after the SSA name was set? (if any).  */
+
+	for (unsigned idx = idx_of_def_stmt + 1;
+	     idx < epath.m_edges.length ();
+	     ++idx)
+	  {
+	    const exploded_edge *eedge = epath.m_edges[idx];
+	    if (m_eg.get_logger ())
+	      m_eg.log ("eedge[%i]: EN %i -> EN %i",
+			idx,
+			eedge->m_src->m_index,
+			eedge->m_dest->m_index);
+	    const exploded_node *dst_node = eedge->m_dest;
+	    const program_point &dst_point = dst_node->get_point ();
+	    const gimple *stmt = dst_point.get_stmt ();
+	    if (!stmt)
+	      continue;
+	    if (const gassign *assign = dyn_cast <const gassign *> (stmt))
+	      {
+		tree lhs = gimple_assign_lhs (assign);
+		if (TREE_CODE (lhs) == SSA_NAME
+		    && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
+		  return assign;
+	      }
+	  }
+      }
+
+  not_found:
+
+    /* Look backwards for the first statement with a location.  */
+    int i;
+    const exploded_edge *eedge;
+    FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, i, eedge)
+      {
+	if (m_eg.get_logger ())
+	  m_eg.log ("eedge[%i]: EN %i -> EN %i",
+		    i,
+		    eedge->m_src->m_index,
+		    eedge->m_dest->m_index);
+	const exploded_node *dst_node = eedge->m_dest;
+	const program_point &dst_point = dst_node->get_point ();
+	const gimple *stmt = dst_point.get_stmt ();
+	if (stmt)
+	  if (stmt->location != UNKNOWN_LOCATION)
+	    return stmt;
+      }
+
+    gcc_unreachable ();
+    return NULL;
+  }
+
+private:
+  const exploded_graph &m_eg;
+  tree m_var;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* A measurement of how good EXPR is for presenting to the user, so
+   that e.g. we can say prefer printing
+     "leak of 'tmp.m_ptr'"
+   over:
+     "leak of '<unknown>'".  */
+
+static int
+readability (const_tree expr)
+{
+  gcc_assert (expr);
+  switch (TREE_CODE (expr))
+    {
+    case COMPONENT_REF:
+    case MEM_REF:
+      /* Impose a slight readability penalty relative to that of
+	 operand 0.  */
+      return readability (TREE_OPERAND (expr, 0)) - 1;
+
+    case SSA_NAME:
+      {
+	if (tree var = SSA_NAME_VAR (expr))
+	  return readability (var);
+	/* Avoid printing '<unknown>' for SSA names for temporaries.  */
+	return -1;
+      }
+      break;
+
+    case VAR_DECL:
+      /* Arbitrarily-chosen "high readability" value.  */
+      return 256;
+
+    default:
+      return 0;
+    }
+
+  return 0;
+}
+
+/* A qsort comparator for trees to sort them into most user-readable to
+   least user-readable.  */
+
+static int
+readability_comparator (const void *p1, const void *p2)
+{
+  path_var pv1 = *(path_var const *)p1;
+  path_var pv2 = *(path_var const *)p2;
+
+  /* TODO: should we consider stack depths?  */
+  int r1 = readability (pv1.m_tree);
+  int r2 = readability (pv2.m_tree);
+
+  return r2 - r1;
+}
+
+/* Create an sm_context and use it to call SM's on_leak vfunc, so that
+   it can potentially complain about a leak of DST_SID (in a new region_model)
+   in the given STATE, where MAP can be used to map SID back to an "old"
+   region_model.  */
+
+void
+impl_region_model_context::on_state_leak (const state_machine &sm,
+					  int sm_idx,
+					  svalue_id dst_sid,
+					  svalue_id first_unused_sid,
+					  const svalue_id_map &map,
+					  state_machine::state_t state)
+{
+  LOG_SCOPE (get_logger ());
+  if (get_logger ())
+    log ("considering leak of sv%i", dst_sid.as_int ());
+
+  if (!m_eg)
+    return;
+
+  /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
+     up the old state of the sid.  */
+  gcc_assert (m_old_state);
+
+  /* Don't report on sid leaking if it's equal to one of the used sids.
+     For example, given:
+       some_non_trivial_expression = malloc (sizeof (struct foo));
+     we have:
+       _1 = malloc;                         (void *)
+       some_non_trivial_expression = _1;    (struct foo *)
+     and at leak-detection time we may have:
+       sv5: {type: 'struct foo *', &r3}  (used)
+       sv6: {type: 'void *', &r3}         (unused)
+     where both point to the same region.  We don't want to report a
+     leak of sv6, so we reject the report due to its equality with sv5.  */
+  gcc_assert (m_new_state);
+  gcc_assert (!first_unused_sid.null_p ());
+  for (int i = 0; i < first_unused_sid.as_int (); i++)
+    {
+      svalue_id used_sid = svalue_id::from_int (i);
+
+      /* Use the "_without_cm" form of eval_condition, since
+	 we're half-way through purging - we don't want to introduce new
+	 equivalence classes into the constraint_manager for "sid" and
+	 for each of the used_sids.  */
+      const region_model &rm = *m_new_state->m_region_model;
+      tristate eq = rm.eval_condition_without_cm (dst_sid, EQ_EXPR, used_sid);
+      if (eq.is_true ())
+	{
+	  log ("rejecting leak of sv%i due to equality with sv%i",
+	       dst_sid.as_int (), used_sid.as_int ());
+	  return;
+	}
+    }
+
+  /* SID has leaked within the new state: no regions use it.
+     We need to convert it back to a tree, but since no regions use it, we
+     have to use MAP to convert it back to an svalue_id within the old state.
+     We can then look that svalue_id up to locate regions and thus tree(s)
+     that use it.  */
+
+  svalue_id old_sid = map.get_src_for_dst (dst_sid);
+
+  auto_vec<path_var> leaked_pvs;
+  m_old_state->m_region_model->get_path_vars_for_svalue (old_sid, &leaked_pvs);
+
+  if (leaked_pvs.length () < 1)
+    return;
+
+  /* Find "best" leaked tree.
+     Sort the leaks into most human-readable first, through
+     to least user-readable.  Given that we only emit one
+     leak per EC, this ought to ensure that we pick the most
+     user-readable description of each leaking EC.
+     This assumes that all vars in the EC have the same state.  */
+  leaked_pvs.qsort (readability_comparator);
+
+  tree leaked_tree = leaked_pvs[0].m_tree;
+  if (get_logger ())
+    log ("best leaked_tree: %qE", leaked_tree);
+
+  leak_stmt_finder stmt_finder (*m_eg, leaked_tree);
+  impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
+			   m_old_state, m_new_state,
+			   m_change,
+			   m_old_state->m_checker_states[sm_idx],
+			   m_new_state->m_checker_states[sm_idx],
+			   &stmt_finder);
+  gcc_assert (m_enode_for_diag);
+
+  /* Don't complain about leaks when returning from "main".  */
+  if (m_enode_for_diag->get_supernode ()
+      && m_enode_for_diag->get_supernode ()->return_p ())
+    {
+      tree fndecl = m_enode_for_diag->get_function ()->decl;
+      if (0 == strcmp (IDENTIFIER_POINTER (DECL_NAME (fndecl)), "main"))
+	{
+	  log ("not reporting leak from main");
+	  return;
+	}
+    }
+
+  sm.on_leak (&sm_ctxt, m_enode_for_diag->get_supernode (), m_stmt,
+	      leaked_tree, state);
+}
+
+/* Implementation of region_model_context::on_inherited_svalue vfunc
+   for impl_region_model_context.
+   Notify all checkers that CHILD_SID has been created from PARENT_SID,
+   so that those state machines that inherit state can propagate the state
+   from parent to child.  */
+
+void
+impl_region_model_context::on_inherited_svalue (svalue_id parent_sid,
+						svalue_id child_sid)
+{
+  if (!m_new_state)
+    return;
+
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
+    {
+      const state_machine &sm = m_ext_state.get_sm (sm_idx);
+      if (sm.inherited_state_p ())
+	smap->on_inherited_svalue (parent_sid, child_sid);
+    }
+}
+
+/* Implementation of region_model_context::on_cast vfunc
+   for impl_region_model_context.
+   Notify all checkers that DST_SID is a cast of SRC_SID, so that sm-state
+   can be propagated from src to dst.  */
+
+void
+impl_region_model_context::on_cast (svalue_id src_sid,
+				    svalue_id dst_sid)
+{
+  if (!m_new_state)
+    return;
+
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
+    smap->on_cast (src_sid, dst_sid);
+}
+
+/* Implementation of region_model_context::on_condition vfunc.
+   Notify all state machines about the condition, which could lead to
+   state transitions.  */
+
+void
+impl_region_model_context::on_condition (tree lhs, enum tree_code op, tree rhs)
+{
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
+    {
+      const state_machine &sm = m_ext_state.get_sm (sm_idx);
+      impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
+			       m_old_state, m_new_state,
+			       m_change,
+			       m_old_state->m_checker_states[sm_idx],
+			       m_new_state->m_checker_states[sm_idx]);
+      sm.on_condition (&sm_ctxt,
+		       m_enode_for_diag->get_supernode (), m_stmt,
+		       lhs, op, rhs);
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Subroutine of print_enode_indices: print a run of indices from START_IDX
+   to END_IDX to PP, using and updating *FIRST_RUN.  */
+
+static void
+print_run (pretty_printer *pp, int start_idx, int end_idx,
+	   bool *first_run)
+{
+  if (!(*first_run))
+    pp_string (pp, ", ");
+  *first_run = false;
+  if (start_idx == end_idx)
+    pp_printf (pp, "EN: %i", start_idx);
+  else
+    pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
+}
+
+/* Print the indices within ENODES to PP, collecting them as
+   runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42".  */
+
+static void
+print_enode_indices (pretty_printer *pp,
+		     const auto_vec<exploded_node *> &enodes)
+{
+  int cur_start_idx = -1;
+  int cur_finish_idx = -1;
+  bool first_run = true;
+  unsigned i;
+  exploded_node *enode;
+  FOR_EACH_VEC_ELT (enodes, i, enode)
+    {
+      if (cur_start_idx == -1)
+	{
+	  gcc_assert (cur_finish_idx == -1);
+	  cur_start_idx = cur_finish_idx = enode->m_index;
+	}
+      else
+	{
+	  if (enode->m_index == cur_finish_idx + 1)
+	    /* Continuation of a run.  */
+	    cur_finish_idx = enode->m_index;
+	  else
+	    {
+	      /* Finish existing run, start a new one.  */
+	      gcc_assert (cur_start_idx >= 0);
+	      gcc_assert (cur_finish_idx >= 0);
+	      print_run (pp, cur_start_idx, cur_finish_idx,
+			 &first_run);
+	      cur_start_idx = cur_finish_idx = enode->m_index;
+	    }
+	}
+    }
+  /* Finish any existing run.  */
+  if (cur_start_idx >= 0)
+    {
+      gcc_assert (cur_finish_idx >= 0);
+      print_run (pp, cur_start_idx, cur_finish_idx,
+		 &first_run);
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
+   Colorize by sm-state, to make it easier to see how sm-state propagates
+   through the exploded_graph.  */
+
+const char *
+exploded_node::get_dot_fillcolor () const
+{
+  const program_state &state = get_state ();
+
+  /* We want to be able to easily distinguish the no-sm-state case,
+     and to be able to distinguish cases where there's a single state
+     from each other.
+
+     Sum the sm_states, and use the result to choose from a table,
+     modulo table-size, special-casing the "no sm-state" case.   */
+  int total_sm_state = 0;
+  int i;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
+    for (sm_state_map::iterator_t iter = smap->begin ();
+	 iter != smap->end ();
+	 ++iter)
+      total_sm_state += (*iter).second.m_state;
+
+  if (total_sm_state > 0)
+    {
+      /* An arbitrarily-picked collection of light colors.  */
+      const char * const colors[]
+	= {"azure", "coral", "cornsilk", "lightblue", "yellow"};
+      const int num_colors = sizeof (colors) / sizeof (colors[0]);
+      return colors[total_sm_state % num_colors];
+    }
+  else
+    /* No sm-state.   */
+    return "lightgrey";
+}
+
+/* Implementation of dnode::dump_dot vfunc for exploded_node.  */
+
+void
+exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
+{
+  pretty_printer *pp = gv->get_pp ();
+
+  dump_dot_id (pp);
+  pp_printf (pp, " [shape=%s,style=filled,fillcolor=%s,label=\"",
+	     "record",
+	     get_dot_fillcolor ());
+  pp_left_brace (pp);
+  pp_write_text_to_stream (pp);
+
+  pp_printf (pp, "EN: %i", m_index);
+  pp_newline (pp);
+
+  format f (true);
+  m_ps.m_point.print (pp, f);
+  pp_newline (pp);
+
+  const extrinsic_state &ext_state = args.m_eg.get_ext_state ();
+  m_ps.m_state.dump_to_pp (ext_state, true, pp);
+  pp_newline (pp);
+
+  {
+    int i;
+    sm_state_map *smap;
+    FOR_EACH_VEC_ELT (m_ps.m_state.m_checker_states, i, smap)
+      {
+	if (!smap->is_empty_p ())
+	  {
+	    pp_printf (pp, "%s: ", ext_state.get_name (i));
+	    smap->print (ext_state.get_sm (i), pp);
+	    pp_newline (pp);
+	  }
+      }
+  }
+
+  pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+
+  pp_right_brace (pp);
+  pp_string (pp, "\"];\n\n");
+  pp_flush (pp);
+}
+
+/* Dump this to PP in a form suitable for use as an id in .dot output.  */
+
+void
+exploded_node::dump_dot_id (pretty_printer *pp) const
+{
+  pp_printf (pp, "exploded_node_%i", m_index);
+}
+
+/* Dump a multiline representation of this node to PP.  */
+
+void
+exploded_node::dump_to_pp (pretty_printer *pp,
+			   const extrinsic_state &ext_state) const
+{
+  pp_printf (pp, "EN: %i", m_index);
+  pp_newline (pp);
+
+  format f (true);
+  m_ps.m_point.print (pp, f);
+  pp_newline (pp);
+
+  m_ps.m_state.dump_to_pp (ext_state, false, pp);
+  pp_newline (pp);
+}
+
+/* Dump a multiline representation of this node to FILE.  */
+
+void
+exploded_node::dump (FILE *fp,
+		     const extrinsic_state &ext_state) const
+{
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = fp;
+  dump_to_pp (&pp, ext_state);
+  pp_flush (&pp);
+}
+
+/* Dump a multiline representation of this node to stderr.  */
+
+DEBUG_FUNCTION void
+exploded_node::dump (const extrinsic_state &ext_state) const
+{
+  dump (stderr, ext_state);
+}
+
+/* Return true if FNDECL has a gimple body.  */
+// TODO: is there a pre-canned way to do this?
+
+static bool
+fndecl_has_gimple_body_p (tree fndecl)
+{
+  if (fndecl == NULL_TREE)
+    return false;
+
+  cgraph_node *n = cgraph_node::get (fndecl);
+  if (!n)
+    return false;
+
+  return n->has_gimple_body_p ();
+}
+
+/* A pending_diagnostic subclass for implementing "__analyzer_dump_path".  */
+
+class dump_path_diagnostic
+  : public pending_diagnostic_subclass<dump_path_diagnostic>
+{
+public:
+  bool emit (rich_location *richloc) FINAL OVERRIDE
+  {
+    inform (richloc, "path");
+    return true;
+  }
+
+  const char *get_kind () const FINAL OVERRIDE { return "dump_path_diagnostic"; }
+
+  bool operator== (const dump_path_diagnostic &) const
+  {
+    return true;
+  }
+};
+
+/* Modify STATE in place, applying the effects of the stmt at this node's
+   point.
+   Return true if there were any sm-state changes.  */
+
+bool
+exploded_node::on_stmt (exploded_graph &eg,
+			const supernode *snode,
+			const gimple *stmt,
+			program_state *state,
+			state_change *change) const
+{
+  /* Preserve the old state.  It is used here for looking
+     up old checker states, for determining state transitions, and
+     also within impl_region_model_context and impl_sm_context for
+     going from tree to svalue_id.  */
+  const program_state old_state (*state);
+
+  impl_region_model_context ctxt (eg, this,
+				  &old_state, state, change,
+				  stmt);
+
+  if (const gassign *assign = dyn_cast <const gassign *> (stmt))
+    state->m_region_model->on_assignment (assign, &ctxt);
+
+  if (const greturn *return_ = dyn_cast <const greturn *> (stmt))
+    state->m_region_model->on_return (return_, &ctxt);
+
+  if (const gcall *call = dyn_cast <const gcall *> (stmt))
+    {
+      /* Debugging/test support.  */
+      if (is_named_call_p (call, "__analyzer_dump", 0))
+	{
+	  /* Handle the builtin "__analyzer_dump" by dumping state
+	     to stderr.  */
+	  dump (eg.get_ext_state ());
+	}
+      else if (is_named_call_p (call, "__analyzer_dump_path", 0))
+	{
+	  /* Handle the builtin "__analyzer_dump_path" by queuing a
+	     diagnostic at this exploded_node.  */
+	  ctxt.warn (new dump_path_diagnostic ());
+	}
+      else if (is_named_call_p (call, "__analyzer_dump_region_model", 0))
+	{
+	  /* Handle the builtin "__analyzer_dump_region_model" by dumping
+	     the region model's state to stderr.  */
+	  state->m_region_model->dump (false);
+	}
+      else if (is_named_call_p (call, "__analyzer_eval", 1))
+	{
+	  /* Handle the builtin "__analyzer_eval" by evaluating the input
+	     and dumping as a dummy warning, so that test cases can use
+	     dg-warning to validate the result (and so unexpected warnings will
+	     lead to DejaGnu failures).  */
+	  tree t_arg = gimple_call_arg (call, 0);
+	  tristate t
+	    = state->m_region_model->eval_condition (t_arg,
+						     NE_EXPR,
+						     integer_zero_node,
+						     &ctxt);
+	  warning_at (call->location, 0, "%s", t.as_string ());
+	}
+      else if (is_named_call_p (call, "__analyzer_break", 0))
+	{
+	  /* Handle the builtin "__analyzer_break" by triggering a
+	     breakpoint.  */
+	  /* TODO: is there a good cross-platform way to do this?  */
+	  raise (SIGINT);
+	}
+      else if (is_setjmp_call_p (stmt))
+	state->m_region_model->on_setjmp (call, this, &ctxt);
+      else if (is_longjmp_call_p (call))
+	{
+	  on_longjmp (eg, call, state, &ctxt);
+	  return true;
+	}
+      else
+	state->m_region_model->on_call_pre (call, &ctxt);
+    }
+
+  bool any_sm_changes = false;
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
+    {
+      const state_machine &sm = eg.get_ext_state ().get_sm (sm_idx);
+      const sm_state_map *old_smap
+	= old_state.m_checker_states[sm_idx];
+      sm_state_map *new_smap = state->m_checker_states[sm_idx];
+      impl_sm_context ctxt (eg, sm_idx, sm, this, &old_state, state,
+			    change,
+			    old_smap, new_smap);
+      /* Allow the state_machine to handle the stmt.  */
+      if (!sm.on_stmt (&ctxt, snode, stmt))
+	{
+	  /* For those stmts that were not handled by the state machine.  */
+	  if (const gcall *call = dyn_cast <const gcall *> (stmt))
+	    {
+	      tree callee_fndecl = gimple_call_fndecl (call);
+	      // TODO: maybe we can be smarter about handling function pointers?
+
+	      if (!fndecl_has_gimple_body_p (callee_fndecl))
+		new_smap->purge_for_unknown_fncall (eg, sm, call, callee_fndecl,
+						    state->m_region_model);
+	    }
+	}
+      if (*old_smap != *new_smap)
+	any_sm_changes = true;
+    }
+
+  if (const gcall *call = dyn_cast <const gcall *> (stmt))
+    state->m_region_model->on_call_post (call, &ctxt);
+
+  return any_sm_changes;
+}
+
+/* Consider the effect of following superedge SUCC from this node.
+
+   Return true if it's feasible to follow the edge, or false
+   if it's infeasible.
+
+   Examples: if it's the "true" branch within
+   a CFG and we know the conditional is false, we know it's infeasible.
+   If it's one of multiple interprocedual "return" edges, then only
+   the edge back to the most recent callsite is feasible.
+
+   Update NEXT_STATE accordingly (e.g. to record that a condition was
+   true or false, or that the NULL-ness of a pointer has been checked,
+   pushing/popping stack frames, etc).
+
+   Update NEXT_POINT accordingly (updating the call string).  */
+
+bool
+exploded_node::on_edge (exploded_graph &eg,
+			const superedge *succ,
+			program_point *next_point,
+			program_state *next_state,
+			state_change *change) const
+{
+  LOG_FUNC (eg.get_logger ());
+
+  if (!next_point->on_edge (eg, succ))
+    return false;
+
+  if (!next_state->on_edge (eg, *this, succ, change))
+    return false;
+
+  return true;
+}
+
+/* Verify that the stack at LONGJMP_POINT is still valid, given a call
+   to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
+   called in must still be valid.
+
+   Caveat: this merely checks the call_strings in the points; it doesn't
+   detect the case where a frame returns and is then called again.  */
+
+static bool
+valid_longjmp_stack_p (const program_point &longjmp_point,
+		       const program_point &setjmp_point)
+{
+  const call_string &cs_at_longjmp = longjmp_point.get_call_string ();
+  const call_string &cs_at_setjmp = setjmp_point.get_call_string ();
+
+  if (cs_at_longjmp.length () < cs_at_setjmp.length ())
+    return false;
+
+  /* Check that the call strings match, up to the depth of the
+     setjmp point.  */
+  for (unsigned depth = 0; depth < cs_at_setjmp.length (); depth++)
+    if (cs_at_longjmp[depth] != cs_at_setjmp[depth])
+      return false;
+
+  return true;
+}
+
+/* A pending_diagnostic subclass for complaining about bad longjmps,
+   where the enclosing function of the "setjmp" has returned (and thus
+   the stack frame no longer exists).  */
+
+class stale_jmp_buf : public pending_diagnostic_subclass<dump_path_diagnostic>
+{
+public:
+  stale_jmp_buf (const gcall *setjmp_call, const gcall *longjmp_call)
+  : m_setjmp_call (setjmp_call), m_longjmp_call (longjmp_call)
+  {}
+
+  bool emit (rich_location *richloc) FINAL OVERRIDE
+  {
+    return warning_at
+      (richloc, OPT_Wanalyzer_stale_setjmp_buffer,
+       "%qs called after enclosing function of %qs has returned",
+       "longjmp", "setjmp");
+  }
+
+  const char *get_kind () const FINAL OVERRIDE
+  { return "stale_jmp_buf"; }
+
+  bool operator== (const stale_jmp_buf &other) const
+  {
+    return (m_setjmp_call == other.m_setjmp_call
+	    && m_longjmp_call == other.m_longjmp_call);
+  }
+
+private:
+  const gcall *m_setjmp_call;
+  const gcall *m_longjmp_call;
+};
+
+/* Handle LONGJMP_CALL, a call to "longjmp".
+
+   Attempt to locate where "setjmp" was called on the jmp_buf and build an
+   exploded_node and exploded_edge to it representing a rewind to that frame,
+   handling the various kinds of failure that can occur.  */
+
+void
+exploded_node::on_longjmp (exploded_graph &eg,
+			   const gcall *longjmp_call,
+			   program_state *new_state,
+			   region_model_context *ctxt) const
+{
+  tree buf_ptr = gimple_call_arg (longjmp_call, 0);
+
+  region_model *new_region_model = new_state->m_region_model;
+  region_id buf_rid = new_region_model->deref_rvalue (buf_ptr, ctxt);
+  region *buf = new_region_model->get_region (buf_rid);
+  if (!buf)
+    return;
+
+  svalue_id buf_content_sid
+    = buf->get_value (*new_region_model, false, ctxt);
+  svalue *buf_content_sval = new_region_model->get_svalue (buf_content_sid);
+  if (!buf_content_sval)
+    return;
+  setjmp_svalue *setjmp_sval = buf_content_sval->dyn_cast_setjmp_svalue ();
+  if (!setjmp_sval)
+    return;
+
+  /* Build a custom enode and eedge for rewinding from the longjmp
+     call back to the setjmp.  */
+
+  const exploded_node *enode_origin = setjmp_sval->get_exploded_node ();
+  rewind_info_t rewind_info (enode_origin);
+
+  const gcall *setjmp_call = rewind_info.get_setjmp_call ();
+  const program_point &setjmp_point = rewind_info.get_setjmp_point ();
+
+  const program_point &longjmp_point = get_point ();
+
+  /* Verify that the setjmp's call_stack hasn't been popped.  */
+  if (!valid_longjmp_stack_p (longjmp_point, setjmp_point))
+    {
+      ctxt->warn (new stale_jmp_buf (setjmp_call, longjmp_call));
+      return;
+    }
+
+  gcc_assert (longjmp_point.get_stack_depth ()
+	      >= setjmp_point.get_stack_depth ());
+
+  /* Update the state for use by the destination node.  */
+  new_region_model->on_longjmp (longjmp_call, setjmp_call,
+				setjmp_point.get_stack_depth (), ctxt);
+
+  program_point next_point
+    = program_point::after_supernode (setjmp_point.get_supernode (),
+				      setjmp_point.get_call_string ());
+
+  state_change change;
+  exploded_node *next = eg.get_or_create_node (next_point, *new_state, &change);
+
+  /* Create custom exploded_edge for a longjmp.  */
+  if (next)
+    eg.add_edge (const_cast<exploded_node *> (this), next, NULL,
+		 change,
+		 new rewind_info_t (enode_origin));
+}
+
+/* Subroutine of exploded_graph::process_node for finding the successors
+   of the supernode for a function exit basic block.
+
+   Ensure that pop_frame is called, potentially queuing diagnostics about
+   leaks.  */
+
+void
+exploded_node::detect_leaks (exploded_graph &eg) const
+{
+  LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
+
+  gcc_assert (get_point ().get_supernode ()->return_p ());
+
+  /* If we're not a "top-level" function, do nothing; pop_frame
+     will be called when handling the return superedge.  */
+  if (get_point ().get_stack_depth () > 1)
+    return;
+
+  /* We have a "top-level" function.  */
+  gcc_assert (get_point ().get_stack_depth () == 1);
+
+  const program_state &old_state = get_state ();
+
+  /* Work with a temporary copy of the state: pop the frame, and see
+     what leaks (via purge_unused_svalues).  */
+  program_state new_state (old_state);
+
+  gcc_assert (new_state.m_region_model);
+
+  purge_stats stats;
+  impl_region_model_context ctxt (eg, this,
+				  &old_state, &new_state,
+				  NULL,
+				  get_stmt ());
+  new_state.m_region_model->pop_frame (true, &stats, &ctxt);
+}
+
+/* Dump the successors and predecessors of this enode to OUTF.  */
+
+void
+exploded_node::dump_succs_and_preds (FILE *outf) const
+{
+  unsigned i;
+  exploded_edge *e;
+  {
+    auto_vec<exploded_node *> preds (m_preds.length ());
+    FOR_EACH_VEC_ELT (m_preds, i, e)
+      preds.quick_push (e->m_src);
+    pretty_printer pp;
+    print_enode_indices (&pp, preds);
+    fprintf (outf, "preds: %s\n",
+	     pp_formatted_text (&pp));
+  }
+  {
+    auto_vec<exploded_node *> succs (m_succs.length ());
+    FOR_EACH_VEC_ELT (m_succs, i, e)
+      succs.quick_push (e->m_dest);
+    pretty_printer pp;
+    print_enode_indices (&pp, succs);
+    fprintf (outf, "succs: %s\n",
+	     pp_formatted_text (&pp));
+  }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class exploded_edge : public dedge.  */
+
+/* exploded_edge's ctor.  */
+
+exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
+			      const superedge *sedge,
+			      const state_change &change,
+			      rewind_info_t *rewind_info)
+: dedge (src, dest), m_sedge (sedge), m_change (change),
+  m_rewind_info (rewind_info)
+{
+  change.validate (dest->get_state ());
+}
+
+/* exploded_edge's dtor.  */
+
+exploded_edge::~exploded_edge ()
+{
+  delete m_rewind_info;
+}
+
+/* Implementation of dedge::dump_dot vfunc for exploded_edge.
+   Use the label of the underlying superedge, if any.  */
+
+void
+exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
+{
+  pretty_printer *pp = gv->get_pp ();
+
+  const char *style = "\"solid,bold\"";
+  const char *color = "black";
+  int weight = 10;
+  const char *constraint = "true";
+
+  if (m_sedge)
+    switch (m_sedge->m_kind)
+      {
+      default:
+	gcc_unreachable ();
+      case SUPEREDGE_CFG_EDGE:
+	break;
+      case SUPEREDGE_CALL:
+	color = "red";
+	//constraint = "false";
+	break;
+      case SUPEREDGE_RETURN:
+	color = "green";
+	//constraint = "false";
+	break;
+      case SUPEREDGE_INTRAPROCEDURAL_CALL:
+	style = "\"dotted\"";
+	break;
+      }
+  if (m_rewind_info)
+    {
+      color = "red";
+      style = "\"dotted\"";
+    }
+
+  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,"
+	      " headlabel=\""),
+	     style, color, weight, constraint);
+
+  if (m_sedge)
+    m_sedge->dump_label_to_pp (pp, false);
+  else if (m_rewind_info)
+    pp_string (pp, "rewind");
+
+  m_change.dump (pp, args.m_eg.get_ext_state ());
+  //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
+
+  pp_printf (pp, "\"];\n");
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* struct stats.  */
+
+/* stats' ctor.  */
+
+stats::stats (int num_supernodes)
+: m_node_reuse_count (0),
+  m_node_reuse_after_merge_count (0),
+  m_num_supernodes (num_supernodes)
+{
+  for (int i = 0; i < NUM_POINT_KINDS; i++)
+    m_num_nodes[i] = 0;
+}
+
+/* Log these stats in multiline form to LOGGER.  */
+
+void
+stats::log (logger *logger) const
+{
+  gcc_assert (logger);
+  for (int i = 0; i < NUM_POINT_KINDS; i++)
+    logger->log ("m_num_nodes[%s]: %i",
+		 point_kind_to_string (static_cast <enum point_kind> (i)),
+		 m_num_nodes[i]);
+  logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
+  logger->log ("m_node_reuse_after_merge_count: %i",
+	       m_node_reuse_after_merge_count);
+}
+
+/* Dump these stats in multiline form to OUT.  */
+
+void
+stats::dump (FILE *out) const
+{
+  for (int i = 0; i < NUM_POINT_KINDS; i++)
+    fprintf (out, "m_num_nodes[%s]: %i\n",
+	     point_kind_to_string (static_cast <enum point_kind> (i)),
+	     m_num_nodes[i]);
+  fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
+  fprintf (out, "m_node_reuse_after_merge_count: %i\n",
+	   m_node_reuse_after_merge_count);
+
+  if (m_num_supernodes > 0)
+    fprintf (out, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
+	     (float)m_num_nodes[PK_AFTER_SUPERNODE] / (float)m_num_supernodes);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* strongly_connected_components's ctor.  Tarjan's SCC algorithm.  */
+
+strongly_connected_components::
+strongly_connected_components (const supergraph &sg, logger *logger)
+: m_sg (sg), m_per_node (m_sg.num_nodes ())
+{
+  LOG_SCOPE (logger);
+  auto_client_timevar tv ("computing scc");
+
+  for (int i = 0; i < m_sg.num_nodes (); i++)
+    m_per_node.quick_push (per_node_data ());
+
+  for (int i = 0; i < m_sg.num_nodes (); i++)
+    if (m_per_node[i].m_index == -1)
+      strong_connect (i);
+
+  if (0)
+    dump ();
+}
+
+/* Dump this object to stderr.  */
+
+DEBUG_FUNCTION void
+strongly_connected_components::dump () const
+{
+  for (int i = 0; i < m_sg.num_nodes (); i++)
+    {
+      const per_node_data &v = m_per_node[i];
+      fprintf (stderr, "SN %i: index: %i lowlink: %i on_stack: %i\n",
+	       i, v.m_index, v.m_lowlink, v.m_on_stack);
+    }
+}
+
+/* Subroutine of strongly_connected_components's ctor, part of Tarjan's
+   SCC algorithm.  */
+
+void
+strongly_connected_components::strong_connect (unsigned index)
+{
+  supernode *v_snode = m_sg.get_node_by_index (index);
+
+  /* Set the depth index for v to the smallest unused index.  */
+  per_node_data *v = &m_per_node[index];
+  v->m_index = index;
+  v->m_lowlink = index;
+  m_stack.safe_push (index);
+  v->m_on_stack = true;
+  index++;
+
+  /* Consider successors of v.  */
+  unsigned i;
+  superedge *sedge;
+  FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
+    {
+      supernode *w_snode = sedge->m_dest;
+      per_node_data *w = &m_per_node[w_snode->m_index];
+      if (w->m_index == -1)
+	{
+	  /* Successor w has not yet been visited; recurse on it.  */
+	  strong_connect (w_snode->m_index);
+	  v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
+	}
+      else if (w->m_on_stack)
+	{
+	  /* Successor w is in stack S and hence in the current SCC
+	     If w is not on stack, then (v, w) is a cross-edge in the DFS
+	     tree and must be ignored.  */
+	  v->m_lowlink = MIN (v->m_lowlink, w->m_index);
+	}
+    }
+
+  /* If v is a root node, pop the stack and generate an SCC.  */
+
+  if (v->m_lowlink == v->m_index)
+    {
+      per_node_data *w;
+      do {
+	int idx = m_stack.pop ();
+	w = &m_per_node[idx];
+	w->m_on_stack = false;
+      } while (w != v);
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* worklist's ctor.  */
+
+worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
+: m_eg (eg),
+  m_scc (eg.get_supergraph (), eg.get_logger ()),
+  m_plan (plan),
+  m_queue (key_t (*this, NULL))
+{
+}
+
+/* Return the number of nodes in the worklist.  */
+
+unsigned
+worklist::length () const
+{
+  return m_queue.nodes ();
+}
+
+/* Return the next node in the worklist, removing it.  */
+
+exploded_node *
+worklist::take_next ()
+{
+  return m_queue.extract_min ();
+}
+
+/* Return the next node in the worklist without removing it.  */
+
+exploded_node *
+worklist::peek_next ()
+{
+  return m_queue.min ();
+}
+
+/* Add ENODE to the worklist.  */
+
+void
+worklist::add_node (exploded_node *enode)
+{
+  m_queue.insert (key_t (*this, enode), enode);
+}
+
+/* Comparator for implementing worklist::key_t comparison operators.
+   Return negative if KA is before KB
+   Return positive if KA is after KB
+   Return 0 if they are equal.  */
+
+int
+worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb)
+{
+  const program_point &point_a = ka.m_enode->get_point ();
+  const program_point &point_b = kb.m_enode->get_point ();
+  const call_string &call_string_a = point_a.get_call_string ();
+  const call_string &call_string_b = point_b.get_call_string ();
+
+  /* Order empty-callstring points with different functions based on the
+     analysis_plan, so that we generate summaries before they are used.  */
+  if (flag_analyzer_call_summaries
+      && call_string_a.empty_p ()
+      && call_string_b.empty_p ()
+      && point_a.get_function () != NULL
+      && point_b.get_function () != NULL
+      && point_a.get_function () != point_b.get_function ())
+    {
+      return ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
+						point_b.get_function ());
+    }
+
+  /* First, order by SCC.  */
+  int scc_id_a = ka.get_scc_id (ka.m_enode);
+  int scc_id_b = kb.get_scc_id (kb.m_enode);
+  if (scc_id_a != scc_id_b)
+    return scc_id_a - scc_id_b;
+
+  /* If in same SCC, order by supernode index (an arbitrary but stable
+     ordering).  */
+  const supernode *snode_a = ka.m_enode->get_supernode ();
+  const supernode *snode_b = kb.m_enode->get_supernode ();
+  if (snode_a == NULL)
+    {
+      if (snode_b != NULL)
+	/* One is NULL.  */
+	return -1;
+      else
+	/* Both are NULL.  */
+	return 0;
+    }
+  if (snode_b == NULL)
+    /* One is NULL.  */
+    return 1;
+  /* Neither are NULL.  */
+  gcc_assert (snode_a && snode_b);
+  if (snode_a->m_index != snode_b->m_index)
+    return snode_a->m_index - snode_b->m_index;
+
+  gcc_assert (snode_a == snode_b);
+
+  /* Order within supernode via program point.  */
+  int within_snode_cmp
+    = function_point::cmp_within_supernode (point_a.get_function_point (),
+					    point_b.get_function_point ());
+  if (within_snode_cmp)
+    return within_snode_cmp;
+
+  /* The points might vary by callstring; try sorting by callstring.  */
+  int cs_cmp = call_string::cmp (call_string_a, call_string_b);
+  if (cs_cmp)
+    return cs_cmp;
+
+  /* Otherwise, we ought to have the same program_point.  */
+  gcc_assert (point_a == point_b);
+
+  const program_state &state_a = ka.m_enode->get_state ();
+  const program_state &state_b = kb.m_enode->get_state ();
+
+  /* Sort by sm-state, so that identical sm-states are grouped
+     together in the worklist.
+     For now, sort by the hash value (might not be deterministic).  */
+  for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
+       ++sm_idx)
+    {
+      sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
+      sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
+
+      int sm_cmp = smap_a->hash () - smap_b->hash ();
+      if (sm_cmp)
+	return sm_cmp;
+    }
+
+  /* Otherwise, we have two enodes at the same program point but with
+     different states.  We don't have a good total ordering on states,
+     so order them by enode index, so that we have at least have a
+     stable sort.  */
+  return ka.m_enode->m_index - kb.m_enode->m_index;
+}
+
+/* Comparator for implementing worklist::key_t comparison operators.
+   Return negative if KA is before KB
+   Return positive if KA is after KB
+   Return 0 if they are equal.  */
+
+int
+worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
+{
+  int result = cmp_1 (ka, kb);
+
+  /* Check that the ordering is symmetric  */
+#if CHECKING_P
+  int reversed = cmp_1 (kb, ka);
+  gcc_assert (reversed == -result);
+#endif
+
+  /* We should only have 0 for equal (point, state) pairs.  */
+  gcc_assert (result != 0
+	      || (*ka.m_enode->get_ps_key ()
+		  == *kb.m_enode->get_ps_key ()));
+
+  return result;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* exploded_graph's ctor.  */
+
+exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
+				const extrinsic_state &ext_state,
+				const state_purge_map *purge_map,
+				const analysis_plan &plan,
+				int verbosity)
+: log_user (logger), m_sg (sg),
+  m_worklist (*this, plan),
+  m_ext_state (ext_state),
+  m_purge_map (purge_map),
+  m_plan (plan),
+  m_diagnostic_manager (logger, verbosity),
+  m_global_stats (m_sg.num_nodes ()),
+  m_functionless_stats (m_sg.num_nodes ()),
+  m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
+{
+  m_origin = get_or_create_node (program_point (function_point (NULL, NULL,
+								0, PK_ORIGIN),
+						call_string ()),
+				 program_state (ext_state), NULL);
+  for (int i = 0; i < m_sg.num_nodes (); i++)
+    m_PK_AFTER_SUPERNODE_per_snode.quick_push (i);
+}
+
+/* exploded_graph's dtor.  */
+
+exploded_graph::~exploded_graph ()
+{
+  for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
+       iter != m_per_function_stats.end ();
+       ++iter)
+    delete (*iter).second;
+
+  for (point_map_t::iterator iter = m_per_point_data.begin ();
+       iter != m_per_point_data.end ();
+       ++iter)
+    delete (*iter).second;
+}
+
+/* Ensure that there is an exploded_node representing an external call to
+   FUN, adding it to the worklist if creating it.
+
+   Add an edge from the origin exploded_node to the function entrypoint
+   exploded_node.
+
+   Return the exploded_node for the entrypoint to the function.  */
+
+exploded_node *
+exploded_graph::add_function_entry (function *fun)
+{
+  program_point point = program_point::from_function_entry (m_sg, fun);
+  program_state state (m_ext_state);
+  state.m_region_model->push_frame (fun, NULL, NULL);
+
+  exploded_node *enode = get_or_create_node (point, state, NULL);
+  /* We should never fail to add such a node.  */
+  gcc_assert (enode);
+  state_change change;
+  add_edge (m_origin, enode, NULL, change);
+  return enode;
+}
+
+/* Get or create an exploded_node for (POINT, STATE).
+   If a new node is created, it is added to the worklist.
+   If CHANGE is non-NULL, use it to suppress some purging of state,
+   to make generation of state_change_event instances easier.  */
+
+exploded_node *
+exploded_graph::get_or_create_node (const program_point &point,
+				    const program_state &state,
+				    state_change *change)
+{
+  LOG_FUNC (get_logger ());
+  if (get_logger ())
+    {
+      format f (false);
+      pretty_printer *pp = get_logger ()->get_printer ();
+      start_log_line ();
+      pp_string (pp, "point: ");
+      point.print (pp, f);
+      end_log_line ();
+      start_log_line ();
+      pp_string (pp, "state: ");
+      state.dump (m_ext_state, true);
+      end_log_line ();
+    }
+
+  auto_cfun sentinel (point.get_function ());
+
+  state.validate (get_ext_state ());
+
+  //state.dump (get_ext_state ());
+
+  /* Prune state to try to improve the chances of a cache hit,
+     avoiding generating redundant nodes.  */
+  program_state pruned_state = state.prune_for_point (*this, point, change);
+
+  pruned_state.validate (get_ext_state ());
+
+  //pruned_state.dump (get_ext_state ());
+
+  if (get_logger ())
+    {
+      pretty_printer *pp = get_logger ()->get_printer ();
+      start_log_line ();
+      pp_string (pp, "pruned_state: ");
+      pruned_state.dump_to_pp (m_ext_state, true, pp);
+      end_log_line ();
+      pruned_state.m_region_model->dump_to_pp (get_logger_pp (), true);
+    }
+
+  stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
+
+  stats *per_cs_stats
+    = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
+
+  point_and_state ps (point, pruned_state);
+  if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
+    {
+      /* An exploded_node for PS already exists.  */
+      log ("reused EN: %i", (*slot)->m_index);
+      m_global_stats.m_node_reuse_count++;
+      per_fn_stats->m_node_reuse_count++;
+      per_cs_stats->m_node_reuse_count++;
+      return *slot;
+    }
+
+  per_program_point_data *per_point_data
+    = get_or_create_per_program_point_data (point);
+
+  /* Consider merging state with another enode at this program_point.  */
+  if (flag_analyzer_state_merge)
+    {
+      exploded_node *existing_enode;
+      unsigned i;
+      FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
+	{
+	  log ("considering merging with existing EN: %i for point",
+	       existing_enode->m_index);
+	  gcc_assert (existing_enode->get_point () == point);
+	  const program_state &existing_state = existing_enode->get_state ();
+
+	  /* This merges successfully within the loop.  */
+
+	  program_state merged_state (m_ext_state);
+	  if (pruned_state.can_merge_with_p (existing_state, m_ext_state,
+					     &merged_state))
+	    {
+	      log ("merging new state with that of EN: %i",
+		   existing_enode->m_index);
+
+	      /* Try again for a cache hit.  */
+	      ps.set_state (merged_state);
+	      if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
+		{
+		  /* An exploded_node for PS already exists.  */
+		  log ("reused EN: %i", (*slot)->m_index);
+		  m_global_stats.m_node_reuse_after_merge_count++;
+		  per_fn_stats->m_node_reuse_after_merge_count++;
+		  per_cs_stats->m_node_reuse_after_merge_count++;
+		  return *slot;
+		}
+
+	      /* Otherwise, continue, using the merged state in "ps".
+		 Given that merged_state's svalue_ids have no relationship
+		 to those of the input state, and thus to those of CHANGE,
+		 purge any svalue_ids from *CHANGE.  */
+	      if (change)
+		change->on_svalue_purge (svalue_id::from_int (0));
+	    }
+	  else
+	    log ("not merging new state with that of EN: %i",
+		 existing_enode->m_index);
+	}
+    }
+
+  /* Impose a limit on the number of enodes per program point, and
+     simply stop if we exceed it.  */
+  if ((int)per_point_data->m_enodes.length ()
+      > PARAM_VALUE (PARAM_ANALYZER_MAX_ENODES_PER_PROGRAM_POINT))
+    {
+      log ("not creating enode; too many at program point");
+      warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
+		  "terminating analysis for this program point");
+      return NULL;
+    }
+
+  /* An exploded_node for "ps" doesn't already exist; create one.  */
+  exploded_node *node = new exploded_node (ps, m_nodes.length ());
+  add_node (node);
+  m_point_and_state_to_node.put (node->get_ps_key (), node);
+
+  /* Update per-program_point data.  */
+  per_point_data->m_enodes.safe_push (node);
+
+  const enum point_kind node_pk = node->get_point ().get_kind ();
+  m_global_stats.m_num_nodes[node_pk]++;
+  per_fn_stats->m_num_nodes[node_pk]++;
+  per_cs_stats->m_num_nodes[node_pk]++;
+
+  if (node_pk == PK_AFTER_SUPERNODE)
+    m_PK_AFTER_SUPERNODE_per_snode[point.get_supernode ()->m_index]++;
+
+  if (get_logger ())
+    {
+      format f (false);
+      pretty_printer *pp = get_logger ()->get_printer ();
+      log ("created EN: %i", node->m_index);
+      start_log_line ();
+      pp_string (pp, "point: ");
+      point.print (pp, f);
+      end_log_line ();
+      start_log_line ();
+      pp_string (pp, "pruned_state: ");
+      pruned_state.dump_to_pp (m_ext_state, true, pp);
+      end_log_line ();
+    }
+
+  /* Add the new node to the worlist.  */
+  m_worklist.add_node (node);
+  return node;
+}
+
+/* Add an exploded_edge from SRC to DEST, recording its association
+   with SEDGE (which may be NULL), and, if non-NULL, taking ownership
+   of REWIND_INFO.  */
+
+void
+exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
+			  const superedge *sedge,
+			  const state_change &change,
+			  rewind_info_t *rewind_info)
+{
+  exploded_edge *e = new exploded_edge (src, dest, sedge, change, rewind_info);
+  digraph::add_edge (e);
+}
+
+/* Ensure that this graph has per-program_point-data for POINT;
+   borrow a pointer to it.  */
+
+per_program_point_data *
+exploded_graph::
+get_or_create_per_program_point_data (const program_point &point)
+{
+  if (per_program_point_data **slot = m_per_point_data.get (&point))
+    return *slot;
+
+  per_program_point_data *per_point_data = new per_program_point_data (point);
+  m_per_point_data.put (&per_point_data->m_key, per_point_data);
+  return per_point_data;
+}
+
+/* Ensure that this graph has per-call_string-data for CS;
+   borrow a pointer to it.  */
+
+per_call_string_data *
+exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
+{
+  if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
+    return *slot;
+
+  per_call_string_data *data = new per_call_string_data (cs, m_sg.num_nodes ());
+  m_per_call_string_data.put (&data->m_key,
+			      data);
+  return data;
+}
+
+/* Ensure that this graph has per-function-data for FUN;
+   borrow a pointer to it.  */
+
+per_function_data *
+exploded_graph::get_or_create_per_function_data (function *fun)
+{
+  if (per_function_data **slot = m_per_function_data.get (fun))
+    return *slot;
+
+  per_function_data *data = new per_function_data ();
+  m_per_function_data.put (fun, data);
+  return data;
+}
+
+/* Get this graph's per-function-data for FUN if there is any,
+   otherwise NULL.  */
+
+per_function_data *
+exploded_graph::get_per_function_data (function *fun) const
+{
+  if (per_function_data **slot
+        = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
+    return *slot;
+
+  return NULL;
+}
+
+/* Return true if NODE and FUN should be traversed directly, rather than
+   called via other functions.  */
+
+static bool
+toplevel_function_p (cgraph_node *node, function *fun, logger *logger)
+{
+  /* TODO: better logic here
+     e.g. only if more than one caller, and significantly complicated.
+     Perhaps some whole-callgraph analysis to decide if it's worth summarizing
+     an edge, and if so, we need summaries.  */
+  if (flag_analyzer_call_summaries)
+    {
+      int num_call_sites = 0;
+      for (cgraph_edge *edge = node->callers; edge; edge = edge->next_caller)
+	++num_call_sites;
+
+      /* For now, if there's more than one in-edge, and we want call
+	 summaries, do it at the top level so that there's a chance
+	 we'll have a summary when we need one.  */
+      if (num_call_sites > 1)
+	{
+	  if (logger)
+	    logger->log ("traversing %qE (%i call sites)",
+			 fun->decl, num_call_sites);
+	  return true;
+	}
+    }
+
+  if (!TREE_PUBLIC (fun->decl))
+    {
+      if (logger)
+	logger->log ("not traversing %qE (static)", fun->decl);
+      return false;
+    }
+
+  if (logger)
+    logger->log ("traversing %qE (all checks passed)", fun->decl);
+
+  return true;
+}
+
+/* Add initial nodes to EG, with entrypoints for externally-callable
+   functions.  */
+
+void
+exploded_graph::build_initial_worklist ()
+{
+  LOG_SCOPE (get_logger ());
+
+  cgraph_node *node;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+  {
+    function *fun = node->get_fun ();
+    if (!toplevel_function_p (node, fun, get_logger ()))
+      continue;
+    exploded_node *enode = add_function_entry (fun);
+    if (get_logger ())
+      log ("created EN %i for %qE entrypoint", enode->m_index, fun->decl);
+  }
+}
+
+/* The main loop of the analysis.
+   Take freshly-created exploded_nodes from the worklist, calling
+   process_node on them to explore the <point, state> graph.
+   Add edges to their successors, potentially creating new successors
+   (which are also added to the worklist).  */
+
+void
+exploded_graph::process_worklist ()
+{
+  LOG_SCOPE (get_logger ());
+  auto_client_timevar tv ("exploded_graph::process_worklist");
+
+  while (m_worklist.length () > 0)
+    {
+      exploded_node *node = m_worklist.take_next ();
+      gcc_assert (node->m_succs.length () == 0
+		  || node == m_origin);
+
+      log ("next to process: EN: %i", node->m_index);
+
+      /* Avoid exponential explosions of nodes by attempting to merge
+	 nodes that are at the same program point and which have
+	 sufficiently similar state.  */
+      if (flag_analyzer_state_merge && node != m_origin)
+	if (exploded_node *node_2 = m_worklist.peek_next ())
+	  {
+	    gcc_assert (node->m_succs.length () == 0);
+	    gcc_assert (node_2->m_succs.length () == 0);
+
+	    gcc_assert (node != node_2);
+
+	    log ("peek worklist: EN: %i", node_2->m_index);
+
+	    if (node->get_point () == node_2->get_point ())
+	      {
+		if (get_logger ())
+		  {
+		    format f (false);
+		    pretty_printer *pp = get_logger ()->get_printer ();
+		    start_log_line ();
+		    get_logger ()->log_partial
+		      ("got potential merge EN: %i and EN: %i at ",
+		       node->m_index, node_2->m_index);
+		    node->get_point ().print (pp, f);
+		    end_log_line ();
+		  }
+
+		const program_state &state = node->get_state ();
+		const program_state &state_2 = node_2->get_state ();
+
+		/* They shouldn't be equal, or we wouldn't have two
+		   separate nodes.  */
+		gcc_assert (state != state_2);
+
+		program_state merged_state (m_ext_state);
+		state_change change;
+		if (state.can_merge_with_p (state_2, m_ext_state,
+					    &merged_state))
+		  {
+		    log ("merging EN: %i and EN: %i",
+			 node->m_index, node_2->m_index);
+
+		    if (merged_state == state)
+		      {
+			/* Then merge node_2 into node by adding an edge.  */
+			add_edge (node_2, node, NULL, change);
+
+			/* Remove node_2 from the worklist.  */
+			m_worklist.take_next ();
+
+			/* Continue processing "node" below.  */
+		      }
+		    else if (merged_state == state_2)
+		      {
+			/* Then merge node into node_2, and leave node_2
+			   in the worklist, to be processed on the next
+			   iteration.  */
+			add_edge (node, node_2, NULL, change);
+			continue;
+		      }
+		    else
+		      {
+			/* We have a merged state that differs from
+			   both state and state_2.  */
+
+			/* Remove node_2 from the worklist.  */
+			m_worklist.take_next ();
+
+			/* Create (or get) an exploded node for the merged
+			   states, adding to the worklist.  */
+			exploded_node *merged_enode
+			  = get_or_create_node (node->get_point (),
+						merged_state, &change);
+			if (merged_enode == NULL)
+			  continue;
+
+			log ("merged EN: %i and EN: %i into EN: %i",
+			     node->m_index, node_2->m_index,
+			     merged_enode->m_index);
+
+			/* "node" and "node_2" have both now been removed
+			   from the worklist; we should not process them.
+
+			   "merged_enode" may be a new node; if so it will be
+			   processed in a subsequent iteration.
+			   Alternatively, "merged_enode" could be an existing
+			   node; one way the latter can
+			   happen is if we end up merging a succession of
+			   similar nodes into one.  */
+
+			/* If merged_node is one of the two we were merging,
+			   add it back to the worklist to ensure it gets
+			   processed.
+
+			   Add edges from the merged nodes to it (but not a
+			   self-edge).  */
+			if (merged_enode == node)
+			  m_worklist.add_node (merged_enode);
+			else
+			  add_edge (node, merged_enode, NULL, change);
+
+			if (merged_enode == node_2)
+			  m_worklist.add_node (merged_enode);
+			else
+			  add_edge (node_2, merged_enode, NULL, change);
+
+			continue;
+		      }
+		  }
+
+		/* TODO: should we attempt more than two nodes,
+		   or just do pairs of nodes?  (and hope that we get
+		   a cascade of mergers).  */
+	      }
+	}
+
+      process_node (node);
+
+      /* Impose a hard limit on the number of exploded nodes, to ensure
+	 that the analysis terminates in the face of pathological state
+	 explosion (or bugs).
+
+	 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
+	 exploded nodes, looking at supernode exit events.
+
+	 We use exit rather than entry since there can be multiple
+	 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
+	 to be equivalent to the number of supernodes multiplied by the
+	 number of states.  */
+      const int limit
+	= m_sg.num_nodes () * PARAM_VALUE (PARAM_ANALYZER_BB_EXPLOSION_FACTOR);
+      if (m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE] > limit)
+	{
+	  log ("bailing out; too many nodes");
+	  warning_at (node->get_point ().get_location (),
+		      OPT_Wanalyzer_too_complex,
+		      "analysis bailed out early"
+		      " (%i 'after-snode' enodes; %i enodes)",
+		      m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE],
+		      m_nodes.length ());
+	  return;
+	}
+    }
+}
+
+/* Return true if STMT must appear at the start of its exploded node, and
+   thus we can't consolidate its effects within a run of other statements,
+   where PREV_STMT was the previous statement.  */
+
+static bool
+stmt_requires_new_enode_p (const gimple *stmt,
+			   const gimple *prev_stmt)
+{
+  /* Stop consolidating at calls to
+     "__analyzer_dump_exploded_nodes", so they always appear at the
+     start of an exploded_node.  */
+  if (const gcall *call = dyn_cast <const gcall *> (stmt))
+    if (is_named_call_p (call, "__analyzer_dump_exploded_nodes",
+			 1))
+      return true;
+
+  /* If we had a PREV_STMT with an unknown location, and this stmt
+     has a known location, then if a state change happens here, it
+     could be consolidated into PREV_STMT, giving us an event with
+     no location.  Ensure that STMT gets its own exploded_node to
+     avoid this.  */
+  if (prev_stmt->location == UNKNOWN_LOCATION
+      && stmt->location != UNKNOWN_LOCATION)
+    return true;
+
+  return false;
+}
+
+/* The core of exploded_graph::process_worklist (the main analysis loop),
+   handling one node in the worklist.
+
+   Get successor <point, state> pairs for NODE, calling get_or_create on
+   them, and adding an exploded_edge to each successors.
+
+   Freshly-created nodes will be added to the worklist.  */
+
+void
+exploded_graph::process_node (exploded_node *node)
+{
+  LOG_FUNC_1 (get_logger (), "EN: %i", node->m_index);
+
+  const program_point &point = node->get_point ();
+
+  /* Update cfun and input_location in case of an ICE: make it easier to
+     track down which source construct we're failing to handle.  */
+  auto_cfun sentinel (node->get_function ());
+  const gimple *stmt = point.get_stmt ();
+  if (stmt)
+    input_location = stmt->location;
+
+  const program_state &state = node->get_state ();
+  if (get_logger ())
+    {
+      pretty_printer *pp = get_logger ()->get_printer ();
+      start_log_line ();
+      pp_string (pp, "point: ");
+      point.print (pp, format (false));
+      pp_string (pp, ", state: ");
+      state.dump_to_pp (m_ext_state, true, pp);
+      end_log_line ();
+    }
+
+  switch (point.get_kind ())
+    {
+    default:
+      gcc_unreachable ();
+    case PK_ORIGIN:
+      /* This node exists to simplify finding the shortest path
+	 to an exploded_node.  */
+      break;
+
+    case PK_BEFORE_SUPERNODE:
+      {
+	program_state next_state (state);
+	state_change change;
+
+	if (point.get_from_edge ())
+	  {
+	    impl_region_model_context ctxt (*this, node,
+					    &state, &next_state, &change,
+					    NULL);
+	    const cfg_superedge *last_cfg_superedge
+	      = point.get_from_edge ()->dyn_cast_cfg_superedge ();
+	    if (last_cfg_superedge)
+	      next_state.m_region_model->update_for_phis
+		(node->get_supernode (),
+		 last_cfg_superedge,
+		 &ctxt);
+	  }
+
+	if (point.get_supernode ()->m_stmts.length () > 0)
+	  {
+	    program_point next_point
+	      = program_point::before_stmt (point.get_supernode (), 0,
+					    point.get_call_string ());
+	    exploded_node *next
+	      = get_or_create_node (next_point, next_state, &change);
+	    if (next)
+	      add_edge (node, next, NULL, change);
+	  }
+	else
+	  {
+	    program_point next_point
+	      = program_point::after_supernode (point.get_supernode (),
+						point.get_call_string ());
+	    exploded_node *next = get_or_create_node (next_point, next_state,
+						      &change);
+	    if (next)
+	      add_edge (node, next, NULL, change);
+	  }
+      }
+      break;
+    case PK_BEFORE_STMT:
+      {
+	/* Determine the effect of a run of one or more statements
+	   within one supernode, generating an edge to the program_point
+	   after the last statement that's processed.
+
+	   Stop iterating statements and thus consolidating into one enode
+	   when:
+	   - reaching the end of the statements in the supernode
+	   - if an sm-state-change occurs (so that it gets its own
+	     exploded_node)
+	   - if "-fanalyzer-fine-grained" is active
+	   - encountering certain statements must appear at the start of
+	   their enode (for which stmt_requires_new_enode_p returns true)
+
+	   Update next_state in-place, to get the result of the one
+	   or more stmts that are processed.  */
+	program_state next_state (state);
+	state_change change;
+	const supernode *snode = point.get_supernode ();
+	unsigned stmt_idx;
+	const gimple *prev_stmt = NULL;
+	for (stmt_idx = point.get_stmt_idx ();
+	     stmt_idx < snode->m_stmts.length ();
+	     stmt_idx++)
+	  {
+	    const gimple *stmt = snode->m_stmts[stmt_idx];
+
+	    if (stmt_idx > point.get_stmt_idx ())
+	      if (stmt_requires_new_enode_p (stmt, prev_stmt))
+		{
+		  stmt_idx--;
+		  break;
+		}
+	    prev_stmt = stmt;
+
+	    /* Process the stmt.  */
+	    bool any_sm_changes
+	      = node->on_stmt (*this, snode, stmt, &next_state, &change);
+
+	    if (any_sm_changes || flag_analyzer_fine_grained)
+	      break;
+	  }
+	unsigned next_idx = stmt_idx + 1;
+	program_point next_point
+	  = (next_idx < point.get_supernode ()->m_stmts.length ()
+	     ? program_point::before_stmt (point.get_supernode (), next_idx,
+					   point.get_call_string ())
+	     : program_point::after_supernode (point.get_supernode (),
+					       point.get_call_string ()));
+	exploded_node *next = get_or_create_node (next_point,
+						  next_state, &change);
+	if (next)
+	  add_edge (node, next, NULL, change);
+      }
+      break;
+    case PK_AFTER_SUPERNODE:
+      {
+	/* If this is an EXIT BB, detect leaks, and potentially
+	   create a function summary.  */
+	if (point.get_supernode ()->return_p ())
+	  {
+	    node->detect_leaks (*this);
+	    if (flag_analyzer_call_summaries
+		&& point.get_call_string ().empty_p ())
+	      {
+		/* TODO: create function summary
+		   There can be more than one; each corresponds to a different
+		   final enode in the function.  */
+		if (get_logger ())
+		  {
+		    pretty_printer *pp = get_logger ()->get_printer ();
+		    start_log_line ();
+		    get_logger ()->log_partial
+		      ("would create function summary for %qE; state: ",
+		       point.get_fndecl ());
+		    state.dump_to_pp (m_ext_state, true, pp);
+		    end_log_line ();
+		  }
+		per_function_data *per_fn_data
+		  = get_or_create_per_function_data (point.get_function ());
+		per_fn_data->add_call_summary (node);
+	      }
+	  }
+	/* Traverse into successors of the supernode.  */
+	int i;
+	superedge *succ;
+	FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
+	  {
+	    log ("considering SN: %i -> SN: %i",
+		 succ->m_src->m_index, succ->m_dest->m_index);
+
+	    state_change change;
+
+	    program_point next_point
+	      = program_point::before_supernode (succ->m_dest, succ,
+						 point.get_call_string ());
+	    program_state next_state (state);
+
+	    if (!node->on_edge (*this, succ, &next_point, &next_state, &change))
+	      {
+		log ("skipping impossible edge to SN: %i",
+		     succ->m_dest->m_index);
+		continue;
+	      }
+
+	    exploded_node *next = get_or_create_node (next_point, next_state,
+						      &change);
+	    if (next)
+	      add_edge (node, next, succ, change);
+	  }
+      }
+      break;
+    }
+}
+
+/* Ensure that this graph has a stats instance for FN, return it.
+   FN can be NULL, in which case a stats instances is returned covering
+   "functionless" parts of the graph (the origin node).  */
+
+stats *
+exploded_graph::get_or_create_function_stats (function *fn)
+{
+  if (!fn)
+    return &m_functionless_stats;
+
+  if (stats **slot = m_per_function_stats.get (fn))
+    return *slot;
+  else
+    {
+      int num_supernodes = fn ? n_basic_blocks_for_fn (fn) : 0;
+      /* not quite the num supernodes, but nearly.  */
+      stats *new_stats = new stats (num_supernodes);
+      m_per_function_stats.put (fn, new_stats);
+      return new_stats;
+    }
+}
+
+/* Write all stats information to this graph's logger, if any.  */
+
+void
+exploded_graph::log_stats () const
+{
+  if (!get_logger ())
+    return;
+
+  LOG_SCOPE (get_logger ());
+
+  log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
+  log ("m_nodes.length (): %i", m_nodes.length ());
+  log ("m_edges.length (): %i", m_edges.length ());
+
+  log ("global stats:");
+  m_global_stats.log (get_logger ());
+
+  for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
+       iter != m_per_function_stats.end ();
+       ++iter)
+    {
+      function *fn = (*iter).first;
+      log_scope s (get_logger (), function_name (fn));
+      (*iter).second->log (get_logger ());
+    }
+}
+
+/* Dump all stats information to OUT.  */
+
+void
+exploded_graph::dump_stats (FILE *out) const
+{
+  fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
+  fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
+  fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
+
+  fprintf (out, "global stats:\n");
+  m_global_stats.dump (out);
+
+  for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
+       iter != m_per_function_stats.end ();
+       ++iter)
+    {
+      function *fn = (*iter).first;
+      fprintf (out, "function: %s\n", function_name (fn));
+      (*iter).second->dump (out);
+    }
+
+  fprintf (out, "PK_AFTER_SUPERNODE per supernode:\n");
+  for (unsigned i = 0; i < m_PK_AFTER_SUPERNODE_per_snode.length (); i++)
+    fprintf (out, "  SN %i: %3i\n", i, m_PK_AFTER_SUPERNODE_per_snode[i]);
+}
+
+void
+exploded_graph::dump_states_for_supernode (FILE *out,
+					   const supernode *snode) const
+{
+  fprintf (out, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode->m_index);
+  int i;
+  exploded_node *enode;
+  int state_idx = 0;
+  FOR_EACH_VEC_ELT (m_nodes, i, enode)
+    {
+      const supernode *iter_snode = enode->get_supernode ();
+      if (enode->get_point ().get_kind () == PK_AFTER_SUPERNODE
+	  && iter_snode == snode)
+	{
+	  pretty_printer pp;
+	  pp_format_decoder (&pp) = default_tree_printer;
+	  enode->get_state ().dump_to_pp (m_ext_state, true, &pp);
+	  fprintf (out, "state %i: EN: %i\n  %s\n",
+		   state_idx++, enode->m_index,
+		   pp_formatted_text (&pp));
+	}
+    }
+  fprintf (out, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
+	   snode->m_index, state_idx);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Look for the last use of SEARCH_STMT within this path.
+   If found write the edge's index to *OUT_IDX and return true, otherwise
+   return false.  */
+
+bool
+exploded_path::find_stmt_backwards (const gimple *search_stmt,
+				    int *out_idx) const
+{
+  int i;
+  const exploded_edge *eedge;
+  FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge)
+    {
+      const exploded_node *dst_node = eedge->m_dest;
+      const program_point &dst_point = dst_node->get_point ();
+      const gimple *stmt = dst_point.get_stmt ();
+      if (stmt == search_stmt)
+	{
+	  *out_idx = i;
+	  return true;
+	}
+    }
+  return false;
+}
+
+/* Get the final exploded_node in this path, which must be non-empty.  */
+
+exploded_node *
+exploded_path::get_final_enode () const
+{
+  gcc_assert (m_edges.length () > 0);
+  return m_edges[m_edges.length () - 1]->m_dest;
+}
+
+/* Check state along this path, returning true if it is feasible.  */
+
+bool
+exploded_path::feasible_p (logger *logger) const
+{
+  LOG_SCOPE (logger);
+
+  /* Traverse the path, updating this model.  */
+  region_model model;
+  for (unsigned i = 0; i < m_edges.length (); i++)
+    {
+      const exploded_edge *eedge = m_edges[i];
+      if (logger)
+	logger->log ("considering edge %i: EN:%i -> EN:%i",
+		     i,
+		     eedge->m_src->m_index,
+		     eedge->m_dest->m_index);
+      const exploded_node &src_enode = *eedge->m_src;
+      const program_point &src_point = src_enode.get_point ();
+      if (logger)
+	{
+	  logger->start_log_line ();
+	  src_point.print (logger->get_printer (), format (false));
+	  logger->end_log_line ();
+	}
+
+      if (const gimple *stmt = src_point.get_stmt ())
+	{
+	  /* Update cfun and input_location in case of ICE: make it easier to
+	     track down which source construct we're failing to handle.  */
+	  auto_cfun sentinel (src_point.get_function ());
+	  input_location = stmt->location;
+
+	  if (const gassign *assign = dyn_cast <const gassign *> (stmt))
+	    model.on_assignment (assign, NULL);
+	  else if (const greturn *return_ = dyn_cast <const greturn *> (stmt))
+	    model.on_return (return_, NULL);
+	}
+
+      const superedge *sedge = eedge->m_sedge;
+      if (sedge)
+	{
+	  if (logger)
+	    logger->log ("  sedge: SN:%i -> SN:%i %s",
+			 sedge->m_src->m_index,
+			 sedge->m_dest->m_index,
+			 sedge->get_description (false));
+
+	  const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
+	  if (!model.maybe_update_for_edge (*sedge, last_stmt, NULL))
+	    {
+	      if (logger)
+		logger->log ("rejecting due to region model");
+	      return false;
+	    }
+	}
+      else
+	{
+	  /* Special-case the initial eedge from the origin node to the
+	     initial function by pushing a frame for it.  */
+	  if (i == 0)
+	    {
+	      gcc_assert (eedge->m_src->m_index == 0);
+	      gcc_assert (src_point.get_kind () == PK_ORIGIN);
+	      gcc_assert (eedge->m_dest->get_point ().get_kind ()
+			  == PK_BEFORE_SUPERNODE);
+	      function *fun = eedge->m_dest->get_function ();
+	      gcc_assert (fun);
+	      model.push_frame (fun, NULL, NULL);
+	      if (logger)
+		logger->log ("  pushing frame for %qD", fun->decl);
+	    }
+	  else if (eedge->m_rewind_info)
+	    {
+	      /* Update state for the special-case of a rewind of a longjmp
+		 to a setjmp (which doesn't have a superedge, but does affect
+		 state).  */
+	      const gimple *last_stmt
+		= src_point.get_supernode ()->get_last_stmt ();
+	      gcc_assert (last_stmt);
+	      const gcall *longjmp_call = as_a <const gcall *> (last_stmt);
+
+	      const program_point &longjmp_point = eedge->m_src->get_point ();
+	      const program_point &setjmp_point = eedge->m_dest->get_point ();
+
+	      gcc_assert (longjmp_point.get_stack_depth ()
+			  >= setjmp_point.get_stack_depth ());
+
+	      model.on_longjmp (longjmp_call,
+				eedge->m_rewind_info->get_setjmp_call (),
+				setjmp_point.get_stack_depth (), NULL);
+	    }
+	}
+
+      /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
+	 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
+	 This will typically not be associated with a superedge.  */
+      if (src_point.get_from_edge ())
+	{
+	  const cfg_superedge *last_cfg_superedge
+	    = src_point.get_from_edge ()->dyn_cast_cfg_superedge ();
+	  if (last_cfg_superedge)
+	    {
+	      if (logger)
+		logger->log ("  update for phis");
+	      model.update_for_phis (src_enode.get_supernode (),
+				     last_cfg_superedge,
+				     NULL);
+	    }
+	}
+
+      if (logger)
+	{
+	  logger->log ("state after edge %i: EN:%i -> EN:%i",
+		       i,
+		       eedge->m_src->m_index,
+		       eedge->m_dest->m_index);
+	  logger->start_log_line ();
+	  model.dump_to_pp (logger->get_printer (), true);
+	  logger->end_log_line ();
+	}
+    }
+
+  return true;
+}
+
+/* Dump this path in multiline form to PP.  */
+
+void
+exploded_path::dump_to_pp (pretty_printer *pp) const
+{
+  for (unsigned i = 0; i < m_edges.length (); i++)
+    {
+      const exploded_edge *eedge = m_edges[i];
+      pp_printf (pp, "m_edges[%i]: EN %i -> EN %i",
+		 i,
+		 eedge->m_src->m_index,
+		 eedge->m_dest->m_index);
+      pp_newline (pp);
+    }
+}
+
+/* Dump this path in multiline form to FP.  */
+
+void
+exploded_path::dump (FILE *fp) const
+{
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = fp;
+  dump_to_pp (&pp);
+  pp_flush (&pp);
+}
+
+/* Dump this path in multiline form to stderr.  */
+
+DEBUG_FUNCTION void
+exploded_path::dump () const
+{
+  dump (stderr);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* A family of cluster subclasses for use when generating .dot output for
+   exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
+   enodes into hierarchical boxes.
+
+   All functionless enodes appear in the top-level graph.
+   Every (function, call_string) pair gets its own cluster.  Within that
+   cluster, each supernode gets its own cluster.
+
+   Hence all enodes relating to a particular function with a particular
+   callstring will be be in a cluster together; all enodes for the same
+   function but with a different callstring will be in a different
+   cluster.  */
+
+/* Base class of cluster for clustering exploded_node instances in .dot
+   output, based on various subclass-specific criteria.  */
+
+class exploded_cluster : public cluster<eg_traits>
+{
+};
+
+/* Cluster containing all exploded_node instances for one supernode.  */
+
+class supernode_cluster : public exploded_cluster
+{
+public:
+  supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
+
+  // TODO: dtor?
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE
+  {
+    gv->println ("subgraph \"cluster_supernode_%p\" {",
+		 (const void *)this);
+    gv->indent ();
+    gv->println ("style=\"dashed\";");
+    gv->println ("label=\"SN: %i\";", m_supernode->m_index);
+
+    int i;
+    exploded_node *enode;
+    FOR_EACH_VEC_ELT (m_enodes, i, enode)
+      enode->dump_dot (gv, args);
+
+    /* Terminate subgraph.  */
+    gv->outdent ();
+    gv->println ("}");
+  }
+
+  void add_node (exploded_node *en) FINAL OVERRIDE
+  {
+    m_enodes.safe_push (en);
+  }
+
+private:
+  const supernode *m_supernode;
+  auto_vec <exploded_node *> m_enodes;
+};
+
+/* Cluster containing all supernode_cluster instances for one
+   (function, call_string) pair.  */
+
+class function_call_string_cluster : public exploded_cluster
+{
+public:
+  function_call_string_cluster (function *fun, call_string cs)
+  : m_fun (fun), m_cs (cs) {}
+
+  ~function_call_string_cluster ()
+  {
+    for (map_t::iterator iter = m_map.begin ();
+	 iter != m_map.end ();
+	 ++iter)
+      delete (*iter).second;
+  }
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE
+  {
+    const char *funcname = function_name (m_fun);
+
+    gv->println ("subgraph \"cluster_function_%p\" {", (const void *)this);
+    gv->indent ();
+    gv->write_indent ();
+    gv->print ("label=\"call string: ");
+    m_cs.print (gv->get_pp ());
+    gv->print (" function: %s \";", funcname);
+    gv->print ("\n");
+
+    for (map_t::iterator iter = m_map.begin ();
+	 iter != m_map.end ();
+	 ++iter)
+      (*iter).second->dump_dot (gv, args);
+
+    /* Terminate subgraph.  */
+    gv->outdent ();
+    gv->println ("}");
+  }
+
+  void add_node (exploded_node *en) FINAL OVERRIDE
+  {
+    const supernode *supernode = en->get_supernode ();
+    gcc_assert (supernode);
+    supernode_cluster **slot = m_map.get (supernode);
+    if (slot)
+      (*slot)->add_node (en);
+    else
+      {
+	supernode_cluster *child = new supernode_cluster (supernode);
+	m_map.put (supernode, child);
+	child->add_node (en);
+      }
+  }
+
+private:
+  function *m_fun;
+  call_string m_cs;
+  typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
+  map_t m_map;
+};
+
+/* Keys for root_cluster.  */
+
+struct function_call_string
+{
+  function_call_string (function *fun, call_string cs)
+  : m_fun (fun), m_cs (cs)
+  {
+    gcc_assert (fun);
+  }
+
+  function *m_fun;
+  call_string m_cs;
+};
+
+template <> struct default_hash_traits<function_call_string>
+: public pod_hash_traits<function_call_string>
+{
+};
+
+template <>
+inline hashval_t
+pod_hash_traits<function_call_string>::hash (value_type v)
+{
+  return pointer_hash <function>::hash (v.m_fun) ^ v.m_cs.hash ();
+}
+
+template <>
+inline bool
+pod_hash_traits<function_call_string>::equal (const value_type &existing,
+					      const value_type &candidate)
+{
+  return existing.m_fun == candidate.m_fun && existing.m_cs == candidate.m_cs;
+}
+template <>
+inline void
+pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
+{
+  v.m_fun = reinterpret_cast<function *> (1);
+}
+template <>
+inline void
+pod_hash_traits<function_call_string>::mark_empty (value_type &v)
+{
+  v.m_fun = reinterpret_cast<function *> (NULL);
+}
+template <>
+inline bool
+pod_hash_traits<function_call_string>::is_deleted (value_type v)
+{
+  return v.m_fun == reinterpret_cast<function *> (1);
+}
+template <>
+inline bool
+pod_hash_traits<function_call_string>::is_empty (value_type v)
+{
+  return v.m_fun == reinterpret_cast<function *> (NULL);
+}
+
+/* Top-level cluster for generating .dot output for exploded graphs,
+   handling the functionless nodes, and grouping the remaining nodes by
+   callstring.  */
+
+class root_cluster : public exploded_cluster
+{
+public:
+  ~root_cluster ()
+  {
+    for (map_t::iterator iter = m_map.begin ();
+	 iter != m_map.end ();
+	 ++iter)
+      delete (*iter).second;
+  }
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE
+  {
+    int i;
+    exploded_node *enode;
+    FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
+      enode->dump_dot (gv, args);
+
+    for (map_t::iterator iter = m_map.begin ();
+	 iter != m_map.end ();
+	 ++iter)
+      (*iter).second->dump_dot (gv, args);
+  }
+
+  void add_node (exploded_node *en) FINAL OVERRIDE
+  {
+    function *fun = en->get_function ();
+    if (!fun)
+      {
+	m_functionless_enodes.safe_push (en);
+	return;
+      }
+
+    const call_string &cs = en->get_point ().get_call_string ();
+    function_call_string key (fun, cs);
+    function_call_string_cluster **slot = m_map.get (key);
+    if (slot)
+      (*slot)->add_node (en);
+    else
+      {
+	function_call_string_cluster *child
+	  = new function_call_string_cluster (fun, cs);
+	m_map.put (key, child);
+	child->add_node (en);
+      }
+  }
+
+private:
+  /* This can't be an ordered_hash_map, as we can't store vec<call_string>,
+     since it's not a POD; vec<>::quick_push has:
+       *slot = obj;
+     and the slot isn't initialized, so the assignment op dies when cleaning up
+     un-inited *slot (within the truncate call).  */
+  typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
+  map_t m_map;
+
+  /* This should just be the origin exploded_node.  */
+  auto_vec <exploded_node *> m_functionless_enodes;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Subclass of range_label for use within
+   exploded_graph::dump_exploded_nodes for implementing
+   -fdump-analyzer-exploded-nodes: a label for a specific
+   exploded_node.  */
+
+class enode_label : public range_label
+{
+ public:
+  enode_label (const extrinsic_state &ext_state,
+	       exploded_node *enode)
+  : m_ext_state (ext_state), m_enode (enode) {}
+
+  label_text get_text (unsigned) const FINAL OVERRIDE
+  {
+    pretty_printer pp;
+    pp_format_decoder (&pp) = default_tree_printer;
+    m_enode->get_state ().dump_to_pp (m_ext_state, true, &pp);
+    return make_label_text (false, "EN: %i: %s",
+			    m_enode->m_index, pp_formatted_text (&pp));
+  }
+
+private:
+  const extrinsic_state &m_ext_state;
+  exploded_node *m_enode;
+};
+
+/* Postprocessing support for dumping the exploded nodes.
+   Handle -fdump-analyzer-exploded-nodes,
+   -fdump-analyzer-exploded-nodes-2, and the
+   "__analyzer_dump_exploded_nodes" builtin.  */
+
+void
+exploded_graph::dump_exploded_nodes () const
+{
+  // TODO
+  /* Locate calls to __analyzer_dump_exploded_nodes.  */
+  // Print how many egs there are for them?
+  /* Better: log them as we go, and record the exploded nodes
+     in question.  */
+
+  /* Show every enode.  */
+
+  /* Gather them by stmt, so that we can more clearly see the
+     "hotspots" requiring numerous exploded nodes.  */
+
+  /* Alternatively, simply throw them all into one big rich_location
+     and see if the label-printing will sort it out...
+     This requires them all to be in the same source file.  */
+
+  if (flag_dump_analyzer_exploded_nodes)
+    {
+      auto_client_timevar tv ("-fdump-analyzer-exploded-nodes");
+      gcc_rich_location richloc (UNKNOWN_LOCATION);
+      unsigned i;
+      exploded_node *enode;
+      FOR_EACH_VEC_ELT (m_nodes, i, enode)
+	{
+	  if (const gimple *stmt = enode->get_stmt ())
+	    {
+	      if (richloc.get_loc () == UNKNOWN_LOCATION)
+		richloc.set_range (0, stmt->location, SHOW_RANGE_WITH_CARET);
+	      else
+		richloc.add_range (stmt->location,
+				   SHOW_RANGE_WITHOUT_CARET,
+				   new enode_label (m_ext_state, enode));
+	    }
+	}
+      warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
+
+      /* Repeat the warning without all the labels, so that message is visible
+	 (the other one may well have scrolled past the terminal limit).  */
+      warning_at (richloc.get_loc (), 0,
+		  "%i exploded nodes", m_nodes.length ());
+
+      if (m_worklist.length () > 0)
+	warning_at (richloc.get_loc (), 0,
+		    "worklist still contains %i nodes", m_worklist.length ());
+    }
+
+  /* Dump the egraph in textual form to a dump file.  */
+  if (flag_dump_analyzer_exploded_nodes_2)
+    {
+      auto_client_timevar tv ("-fdump-analyzer-exploded-nodes-2");
+      char *filename
+	= concat (dump_base_name, ".eg.txt", NULL);
+      FILE *outf = fopen (filename, "w");
+      if (!outf)
+	error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
+      free (filename);
+
+      fprintf (outf, "exploded graph for %s\n", dump_base_name);
+      fprintf (outf, "  nodes: %i\n", m_nodes.length ());
+      fprintf (outf, "  edges: %i\n", m_edges.length ());
+
+      unsigned i;
+      exploded_node *enode;
+      FOR_EACH_VEC_ELT (m_nodes, i, enode)
+	{
+	  fprintf (outf, "\nEN %i:\n", enode->m_index);
+	  enode->dump_succs_and_preds (outf);
+	  pretty_printer pp;
+	  enode->get_point ().print (&pp, format (true));
+	  fprintf (outf, "%s\n", pp_formatted_text (&pp));
+	  enode->get_state ().dump_to_file (m_ext_state, false, outf);
+	}
+
+      fclose (outf);
+    }
+
+  /* Dump the egraph in textual form to multiple dump files, one per enode.  */
+  if (flag_dump_analyzer_exploded_nodes_3)
+    {
+      auto_client_timevar tv ("-fdump-analyzer-exploded-nodes-3");
+
+      unsigned i;
+      exploded_node *enode;
+      FOR_EACH_VEC_ELT (m_nodes, i, enode)
+	{
+	  char *filename
+	    = xasprintf ("%s.en-%i.txt", dump_base_name, i);
+	  FILE *outf = fopen (filename, "w");
+	  if (!outf)
+	    error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
+	  free (filename);
+
+	  fprintf (outf, "EN %i:\n", enode->m_index);
+	  enode->dump_succs_and_preds (outf);
+	  pretty_printer pp;
+	  enode->get_point ().print (&pp, format (true));
+	  fprintf (outf, "%s\n", pp_formatted_text (&pp));
+	  enode->get_state ().dump_to_file (m_ext_state, false, outf);
+
+	  fclose (outf);
+	}
+    }
+
+  /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
+     giving the number of exploded nodes for "before-stmt", and their
+     IDs.  */
+
+  unsigned i;
+  exploded_node *enode;
+  hash_set<const gimple *> seen;
+  FOR_EACH_VEC_ELT (m_nodes, i, enode)
+    {
+      if (enode->get_point ().get_kind () != PK_BEFORE_STMT)
+	continue;
+
+      if (const gimple *stmt = enode->get_stmt ())
+	if (const gcall *call = dyn_cast <const gcall *> (stmt))
+	  if (is_named_call_p (call, "__analyzer_dump_exploded_nodes", 1))
+	    {
+	      if (seen.contains (stmt))
+		continue;
+
+	      /* This is O(N^2).  */
+	      unsigned j;
+	      auto_vec<exploded_node *> enodes;
+	      exploded_node *other_enode;
+	      FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
+		{
+		  if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT)
+		    continue;
+		  if (other_enode->get_stmt () == stmt)
+		    enodes.safe_push (other_enode);
+		}
+
+	      pretty_printer pp;
+	      print_enode_indices (&pp, enodes);
+
+	      warning_n (stmt->location, 0, enodes.length (),
+			 "%i exploded node: %s",
+			 "%i exploded nodes: %s",
+			 enodes.length (), pp_formatted_text (&pp));
+	      seen.add (stmt);
+
+	      /* If the argument is non-zero, then print all of the states
+		 of the various enodes.  */
+	      tree t_arg = fold (gimple_call_arg (call, 0));
+	      if (TREE_CODE (t_arg) != INTEGER_CST)
+		{
+		  error_at (call->location,
+			    "integer constant required for arg 1");
+		  return;
+		}
+	      int i_arg = TREE_INT_CST_LOW (t_arg);
+	      if (i_arg)
+		{
+		  exploded_node *other_enode;
+		  FOR_EACH_VEC_ELT (enodes, j, other_enode)
+		    {
+		      fprintf (stderr, "%i of %i: EN %i:\n",
+			       j + 1, enodes.length (), other_enode->m_index);
+		      other_enode->dump_succs_and_preds (stderr);
+		      /* Dump state.  */
+		      other_enode->get_state ().dump (m_ext_state, false);
+		    }
+		}
+	    }
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* A collection of classes for visualizing the callgraph in .dot form
+   (as represented in the supergraph).  */
+
+/* Forward decls.  */
+class viz_callgraph_node;
+class viz_callgraph_edge;
+class viz_callgraph;
+class viz_callgraph_cluster;
+
+/* Traits for using "digraph.h" to visualize the callgraph.  */
+
+struct viz_callgraph_traits
+{
+  typedef viz_callgraph_node node_t;
+  typedef viz_callgraph_edge edge_t;
+  typedef viz_callgraph graph_t;
+  struct dump_args_t
+  {
+    dump_args_t (const exploded_graph *eg) : m_eg (eg) {}
+    const exploded_graph *m_eg;
+  };
+  typedef viz_callgraph_cluster cluster_t;
+};
+
+/* Subclass of dnode representing a function within the callgraph.  */
+
+class viz_callgraph_node : public dnode<viz_callgraph_traits>
+{
+  friend class viz_callgraph;
+
+public:
+  viz_callgraph_node (function *fun, int index)
+  : m_fun (fun), m_index (index), m_num_supernodes (0), m_num_superedges (0)
+  {
+    gcc_assert (fun);
+  }
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE
+  {
+    pretty_printer *pp = gv->get_pp ();
+
+    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);
+
+    pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
+    pp_newline (pp);
+
+    pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
+    pp_newline (pp);
+    pp_printf (pp, "superedges: %i\n", m_num_superedges);
+    pp_newline (pp);
+
+    if (args.m_eg)
+      {
+	unsigned i;
+	exploded_node *enode;
+	unsigned num_enodes = 0;
+	FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
+	  {
+	    if (enode->get_point ().get_function () == m_fun)
+	      num_enodes++;
+	  }
+	pp_printf (pp, "enodes: %i\n", num_enodes);
+	pp_newline (pp);
+
+	// TODO: also show the per-callstring breakdown
+	const exploded_graph::call_string_data_map_t *per_cs_data
+	  = args.m_eg->get_per_call_string_data ();
+	for (typename exploded_graph::call_string_data_map_t::iterator iter
+	       = per_cs_data->begin ();
+	     iter != per_cs_data->end ();
+	     ++iter)
+	  {
+	    const call_string *cs = (*iter).first;
+	    //per_call_string_data *data = (*iter).second;
+	    num_enodes = 0;
+	    FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
+	      {
+		if (enode->get_point ().get_function () == m_fun
+		    && enode->get_point ().get_call_string () == *cs)
+		  num_enodes++;
+	      }
+	    if (num_enodes > 0)
+	      {
+		cs->print (pp);
+		pp_printf (pp, ": %i\n", num_enodes);
+	      }
+	  }
+
+	/* Show any summaries.  */
+	per_function_data *data = args.m_eg->get_per_function_data (m_fun);
+	if (data)
+	  {
+	    pp_newline (pp);
+	    pp_printf (pp, "summaries: %i\n", data->m_summaries.length ());
+	  }
+      }
+
+    pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+    pp_right_brace (pp);
+    pp_string (pp, "\"];\n\n");
+    pp_flush (pp);
+  }
+
+  void dump_dot_id (pretty_printer *pp) const
+  {
+    pp_printf (pp, "vcg_%i", m_index);
+  }
+
+private:
+  function *m_fun;
+  int m_index;
+  int m_num_supernodes;
+  int m_num_superedges;
+};
+
+/* Subclass of dedge representing a callgraph edge.  */
+
+class viz_callgraph_edge : public dedge<viz_callgraph_traits>
+{
+public:
+  viz_callgraph_edge (viz_callgraph_node *src, viz_callgraph_node *dest,
+		     const call_superedge *call_sedge)
+  : dedge (src, dest),
+    m_call_sedge (call_sedge)
+  {}
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &) const
+    FINAL OVERRIDE
+  {
+    pretty_printer *pp = gv->get_pp ();
+
+    const char *style = "\"solid,bold\"";
+    const char *color = "black";
+    int weight = 10;
+    const char *constraint = "true";
+
+    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,"
+		" headlabel=\""),
+	       style, color, weight, constraint);
+    pp_printf (pp, "\"];\n");
+  }
+
+private:
+  const call_superedge * const m_call_sedge;
+};
+
+/* Subclass of digraph representing the callgraph.  */
+
+class viz_callgraph : public digraph<viz_callgraph_traits>
+{
+public:
+  viz_callgraph (const supergraph &sg);
+
+  viz_callgraph_node *get_vcg_node_for_function (function *fun)
+  {
+    return *m_map.get (fun);
+  }
+
+  viz_callgraph_node *get_vcg_node_for_snode (supernode *snode)
+  {
+    return get_vcg_node_for_function (snode->m_fun);
+  }
+
+private:
+  const supergraph &m_sg;
+  hash_map<function *, viz_callgraph_node *> m_map;
+};
+
+/* Placeholder subclass of cluster.  */
+
+class viz_callgraph_cluster : public cluster<viz_callgraph_traits>
+{
+};
+
+/* viz_callgraph's ctor.  */
+
+viz_callgraph::viz_callgraph (const supergraph &sg)
+: m_sg (sg)
+{
+  cgraph_node *node;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+    {
+      function *fun = node->get_fun ();
+      viz_callgraph_node *vcg_node
+	= new viz_callgraph_node (fun, m_nodes.length ());
+      m_map.put (fun, vcg_node);
+      add_node (vcg_node);
+    }
+
+  unsigned i;
+  superedge *sedge;
+  FOR_EACH_VEC_ELT (sg.m_edges, i, sedge)
+    {
+      viz_callgraph_node *vcg_src = get_vcg_node_for_snode (sedge->m_src);
+      if (vcg_src->m_fun)
+	get_vcg_node_for_function (vcg_src->m_fun)->m_num_superedges++;
+      if (const call_superedge *call_sedge = sedge->dyn_cast_call_superedge ())
+	{
+	  viz_callgraph_node *vcg_dest = get_vcg_node_for_snode (sedge->m_dest);
+	  viz_callgraph_edge *vcg_edge
+	    = new viz_callgraph_edge (vcg_src, vcg_dest, call_sedge);
+	  add_edge (vcg_edge);
+	}
+    }
+
+  supernode *snode;
+  FOR_EACH_VEC_ELT (sg.m_nodes, i, snode)
+    {
+      if (snode->m_fun)
+	get_vcg_node_for_function (snode->m_fun)->m_num_supernodes++;
+    }
+}
+
+/* Dump the callgraph to FILENAME.  */
+
+static void
+dump_callgraph (const supergraph &sg, const char *filename,
+		const exploded_graph *eg)
+{
+  FILE *outf = fopen (filename, "w");
+  if (!outf)
+    return;
+
+  // TODO
+  viz_callgraph vcg (sg);
+  vcg.dump_dot (filename, NULL, viz_callgraph_traits::dump_args_t (eg));
+
+  fclose (outf);
+}
+
+/* Dump the callgraph to "<srcfile>.callgraph.dot".  */
+
+static void
+dump_callgraph (const supergraph &sg, const exploded_graph *eg)
+{
+  auto_client_timevar tv ("writing .callgraph.dot");
+  char *filename = concat (dump_base_name, ".callgraph.dot", NULL);
+  dump_callgraph (sg, filename, eg);
+  free (filename);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Run the analysis "engine".  */
+
+void
+impl_run_checkers (logger *logger)
+{
+  LOG_SCOPE (logger);
+
+  /* If using LTO, ensure that the cgraph nodes have function bodies.  */
+  cgraph_node *node;
+  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
+    node->get_untransformed_body ();
+
+  /* Create the supergraph.  */
+  supergraph sg (logger);
+
+  state_purge_map *purge_map = NULL;
+
+  if (flag_analyzer_state_purge)
+    purge_map = new state_purge_map (sg, logger);
+
+  if (flag_dump_analyzer_supergraph)
+    {
+      auto_client_timevar tv ("writing .supergraph.dot");
+      char *filename = concat (dump_base_name, ".supergraph.dot", NULL);
+      supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL);
+      sg.dump_dot (filename, args);
+      free (filename);
+    }
+
+  if (flag_dump_analyzer_state_purge)
+    {
+      auto_client_timevar tv ("writing .state-purge.dot");
+      state_purge_annotator a (purge_map);
+      char *filename = concat (dump_base_name, ".state-purge.dot", NULL);
+      supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
+      sg.dump_dot (filename, args);
+      free (filename);
+    }
+
+  auto_delete_vec <state_machine> checkers;
+  make_checkers (checkers, logger);
+
+  if (logger)
+    {
+      int i;
+      state_machine *sm;
+      FOR_EACH_VEC_ELT (checkers, i, sm)
+	logger->log ("checkers[%i]: %s", i, sm->get_name ());
+    }
+
+  /* Extrinsic state shared by nodes in the graph.  */
+  const extrinsic_state ext_state (checkers);
+
+  const analysis_plan plan (sg, logger);
+
+  /* The exploded graph.  */
+  exploded_graph eg (sg, logger, ext_state, purge_map, plan,
+		     analyzer_verbosity);
+
+  /* Add entrypoints to the graph for externally-callable functions.  */
+  eg.build_initial_worklist ();
+
+  /* Now process the worklist, exploring the <point, state> graph.  */
+  eg.process_worklist ();
+
+  if (flag_dump_analyzer_exploded_graph)
+    {
+      auto_client_timevar tv ("writing .eg.dot");
+      char *filename
+	= concat (dump_base_name, ".eg.dot", NULL);
+      exploded_graph::dump_args_t args (eg);
+      root_cluster c;
+      eg.dump_dot (filename, &c, args);
+      free (filename);
+    }
+
+  /* Now emit any saved diagnostics.  */
+  eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
+
+  eg.dump_exploded_nodes ();
+
+  eg.log_stats ();
+
+  if (flag_dump_analyzer_callgraph)
+    dump_callgraph (sg, &eg);
+
+  delete purge_map;
+}
+
+/* External entrypoint to the analysis "engine".
+   Set up any dumps, then call impl_run_checkers.  */
+
+void
+run_checkers ()
+{
+  auto_client_timevar tv ("run_checkers");
+
+  /* Handle -fdump-analyzer and -fdump-analyzer-stderr.  */
+  FILE *dump_fout = NULL;
+  /* Track if we're responsible for closing dump_fout.  */
+  bool owns_dump_fout = false;
+  if (flag_dump_analyzer_stderr)
+    dump_fout = stderr;
+  else if (flag_dump_analyzer)
+    {
+      char *dump_filename = concat (dump_base_name, ".analyzer.txt", NULL);
+      dump_fout = fopen (dump_filename, "w");
+      free (dump_filename);
+      if (dump_fout)
+	owns_dump_fout = true;
+    }
+
+  {
+    log_user the_logger (NULL);
+    if (dump_fout)
+      the_logger.set_logger (new logger (dump_fout, 0, 0,
+					 *global_dc->printer));
+    LOG_SCOPE (the_logger.get_logger ());
+
+    impl_run_checkers (the_logger.get_logger ());
+
+    /* end of lifetime of the_logger (so that dump file is closed after the
+       various dtors run).  */
+  }
+
+  if (owns_dump_fout)
+    fclose (dump_fout);
+}
diff --git a/gcc/analyzer/engine.h b/gcc/analyzer/engine.h
new file mode 100644
index 0000000..b9b7e0b
--- /dev/null
+++ b/gcc/analyzer/engine.h
@@ -0,0 +1,26 @@ 
+/* The analysis "engine".
+   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_ENGINE_H
+#define GCC_ANALYZER_ENGINE_H
+
+extern void run_checkers ();
+
+#endif /* GCC_ANALYZER_ENGINE_H */