[43/49] analyzer: new file: exploded-graph.h
diff mbox series

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

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m. UTC
This patch adds exploded_graph and related classes, for managing
exploring paths through the user's code as a directed graph
of <point, state> pairs.

gcc/ChangeLog:
	* analyzer/exploded-graph.h: New file.
---
 gcc/analyzer/exploded-graph.h | 754 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 754 insertions(+)
 create mode 100644 gcc/analyzer/exploded-graph.h

Comments

Jeff Law Dec. 11, 2019, 8:04 p.m. UTC | #1
On Fri, 2019-11-15 at 20:23 -0500, David Malcolm wrote:
> This patch adds exploded_graph and related classes, for managing
> exploring paths through the user's code as a directed graph
> of <point, state> pairs.
> 
> gcc/ChangeLog:
> 	* analyzer/exploded-graph.h: New file.
> ---
>  gcc/analyzer/exploded-graph.h | 754
> ++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 754 insertions(+)
>  create mode 100644 gcc/analyzer/exploded-graph.h
> 
> diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-
> graph.h
> new file mode 100644
> index 0000000..f97d2b6
> --- /dev/null
> +++ b/gcc/analyzer/exploded-graph.h
> @@ -0,0 +1,754 @@
> +/* Classes for managing a directed graph of <point, state> pairs.
> +   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_EXPLODED_GRAPH_H
> +#define GCC_ANALYZER_EXPLODED_GRAPH_H
> +
> +#include "fibonacci_heap.h"
> +#include "analyzer/analyzer-logging.h"
> +#include "analyzer/constraint-manager.h"
> +#include "analyzer/diagnostic-manager.h"
> +#include "analyzer/program-point.h"
> +#include "analyzer/program-state.h"
> +#include "analyzer/shortest-paths.h"
> +
> +////////////////////////////////////////////////////////////////////
NIT.  Is there some reason you don't just use whitespace for these kind
of vertical separators.  THe more I see them, the more they bug me,
probably because that's not been the style we've used for GCC.



> ///////
> +
> +/* Concrete implementation of region_model_context, wiring it up to
> the
> +   rest of the analysis engine.  */
> +
> +class impl_region_model_context : public region_model_context,
> public log_user
Multiple inheritance?  Is it really needed?  Can we handle via
composition instead?



> +/* A <program_point, program_state> pair, used internally by
> +   exploded_node as its immutable data, and as a key for identifying
> +   exploded_nodes we've already seen in the graph.  */
> +
> +struct point_and_state
Shouldn't this be a class?

+
> +/* Per-program_point data for an exploded_graph.  */
> +
> +struct per_program_point_data
Here too?  THere may be others.  I'd suggest reviewing all your
"structs" and determine if we're better off calling them "class".  I'm
not going to insist on it though since I think the last discussion in
this space was to relax the conventions :-)

> +
> +class exploded_graph : public digraph<eg_traits>, public log_user
Multiple inheritance again?

Jeff
David Malcolm Dec. 12, 2019, 3:28 p.m. UTC | #2
On Wed, 2019-12-11 at 13:04 -0700, Jeff Law wrote:
> On Fri, 2019-11-15 at 20:23 -0500, David Malcolm wrote:
> > This patch adds exploded_graph and related classes, for managing
> > exploring paths through the user's code as a directed graph
> > of <point, state> pairs.
> > 
> > gcc/ChangeLog:
> > 	* analyzer/exploded-graph.h: New file.
> > ---
> >  gcc/analyzer/exploded-graph.h | 754
> > ++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 754 insertions(+)
> >  create mode 100644 gcc/analyzer/exploded-graph.h
> > 
> > diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-
> > graph.h
> > new file mode 100644
> > index 0000000..f97d2b6
> > --- /dev/null
> > +++ b/gcc/analyzer/exploded-graph.h
> > @@ -0,0 +1,754 @@
> > +/* Classes for managing a directed graph of <point, state> pairs.
> > +   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_EXPLODED_GRAPH_H
> > +#define GCC_ANALYZER_EXPLODED_GRAPH_H
> > +
> > +#include "fibonacci_heap.h"
> > +#include "analyzer/analyzer-logging.h"
> > +#include "analyzer/constraint-manager.h"
> > +#include "analyzer/diagnostic-manager.h"
> > +#include "analyzer/program-point.h"
> > +#include "analyzer/program-state.h"
> > +#include "analyzer/shortest-paths.h"
> > +
> > +//////////////////////////////////////////////////////////////////
> > //
> NIT.  Is there some reason you don't just use whitespace for these
> kind
> of vertical separators.  THe more I see them, the more they bug me,
> probably because that's not been the style we've used for GCC.

I've been using them to highlight new "chapters" in a source file;
typically there's another comment following them.  I'm happy to drop
the one where there isn't a trailing comment, but, I'm hoping there's
an acceptable way to have an "section-header"-style comment.

We have "^L" in a bunch of places, but my editor (emacs) doesn't do a
great job of highlighting them.

There's some precedence for: e.g. 

gengtype.c:5094:/******* Manage input files.  ******/

lto-section-in.c has e.g.:

/*****************************************************************************/
/* Record renamings of static declarations                                   */
/*****************************************************************************/

tree-vect-loop-manip.c has:

/*************************************************************************
  Simple Loop Peeling Utilities

  Utilities to support loop peeling for vectorization purposes.
 *************************************************************************/

but I suspect given how sporadic these are that this stuff snuck past
review.

Alternatively I can just drop these and retain the trailing comments,
keeping their formatting.

> > ///////
> > +
> > +/* Concrete implementation of region_model_context, wiring it up
> > to
> > the
> > +   rest of the analysis engine.  */
> > +
> > +class impl_region_model_context : public region_model_context,
> > public log_user
> Multiple inheritance?  Is it really needed?  Can we handle via
> composition instead?

It's handy here, but I can probably eliminate it.

> 
> > +/* A <program_point, program_state> pair, used internally by
> > +   exploded_node as its immutable data, and as a key for
> > identifying
> > +   exploded_nodes we've already seen in the graph.  */
> > +
> > +struct point_and_state
> Shouldn't this be a class?

Will fix (originally was just a pair of public fields, but then I added
the cached hash value, so there's an argument for "class-ifying" this).

> +
> > +/* Per-program_point data for an exploded_graph.  */
> > +
> > +struct per_program_point_data
> Here too?  THere may be others.  I'd suggest reviewing all your
> "structs" and determine if we're better off calling them
> "class".  I'm
> not going to insist on it though since I think the last discussion in
> this space was to relax the conventions :-)

Both fields are public, but they're not-POD.

I'll look into them.

> > +
> > +class exploded_graph : public digraph<eg_traits>, public log_user
> Multiple inheritance again?

Again, it's handy here, but I think I can probably eliminate it.



Dave
David Malcolm Dec. 12, 2019, 6:22 p.m. UTC | #3
On Thu, 2019-12-12 at 10:28 -0500, David Malcolm wrote:
> On Wed, 2019-12-11 at 13:04 -0700, Jeff Law wrote:
> > On Fri, 2019-11-15 at 20:23 -0500, David Malcolm wrote:

[...]

> > > +
> > > +////////////////////////////////////////////////////////////////
> > > //
> > > //
> > NIT.  Is there some reason you don't just use whitespace for these
> > kind
> > of vertical separators.  THe more I see them, the more they bug me,
> > probably because that's not been the style we've used for GCC.
> 
> I've been using them to highlight new "chapters" in a source file;
> typically there's another comment following them.  I'm happy to drop
> the one where there isn't a trailing comment, but, I'm hoping there's
> an acceptable way to have an "section-header"-style comment.
> 
> We have "^L" in a bunch of places, but my editor (emacs) doesn't do a
> great job of highlighting them.
> 
> There's some precedence for: e.g. 
> 
> gengtype.c:5094:/******* Manage input files.  ******/
> 
> lto-section-in.c has e.g.:
> 
> /********************************************************************
> *********/
> /* Record renamings of static
> declarations                                   */
> /********************************************************************
> *********/
> 
> tree-vect-loop-manip.c has:
> 
> /********************************************************************
> *****
>   Simple Loop Peeling Utilities
> 
>   Utilities to support loop peeling for vectorization purposes.
>  ********************************************************************
> *****/
> 
> but I suspect given how sporadic these are that this stuff snuck past
> review.
> 
> Alternatively I can just drop these and retain the trailing comments,
> keeping their formatting.

I went ahead and did that, and the result is growing on me; sorry for
the noise.


Dave

Patch
diff mbox series

diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
new file mode 100644
index 0000000..f97d2b6
--- /dev/null
+++ b/gcc/analyzer/exploded-graph.h
@@ -0,0 +1,754 @@ 
+/* Classes for managing a directed graph of <point, state> pairs.
+   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_EXPLODED_GRAPH_H
+#define GCC_ANALYZER_EXPLODED_GRAPH_H
+
+#include "fibonacci_heap.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/constraint-manager.h"
+#include "analyzer/diagnostic-manager.h"
+#include "analyzer/program-point.h"
+#include "analyzer/program-state.h"
+#include "analyzer/shortest-paths.h"
+
+///////////////////////////////////////////////////////////////////////////
+
+/* Concrete implementation of region_model_context, wiring it up to the
+   rest of the analysis engine.  */
+
+class impl_region_model_context : public region_model_context, public log_user
+{
+ public:
+  impl_region_model_context (exploded_graph &eg,
+			     const exploded_node *enode_for_diag,
+
+			     /* TODO: should we be getting the ECs from the
+				old state, rather than the new?  */
+			     const program_state *old_state,
+			     program_state *new_state,
+			     state_change *change,
+
+			     const gimple *stmt,
+			     stmt_finder *stmt_finder = NULL);
+
+  impl_region_model_context (program_state *state,
+			     state_change *change,
+			     const extrinsic_state &ext_state);
+
+  void warn (pending_diagnostic *d) FINAL OVERRIDE;
+
+  void remap_svalue_ids (const svalue_id_map &map) FINAL OVERRIDE;
+
+  int on_svalue_purge (svalue_id first_unused_sid,
+		       const svalue_id_map &map) FINAL OVERRIDE;
+
+  logger *get_logger () FINAL OVERRIDE
+  {
+    return log_user::get_logger ();
+  }
+
+  void on_state_leak (const state_machine &sm,
+		      int sm_idx,
+		      svalue_id sid,
+		      svalue_id first_unused_sid,
+		      const svalue_id_map &map,
+		      state_machine::state_t state);
+
+  void on_inherited_svalue (svalue_id parent_sid,
+			    svalue_id child_sid) FINAL OVERRIDE;
+
+  void on_cast (svalue_id src_sid,
+		svalue_id dst_sid) FINAL OVERRIDE;
+
+  void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE;
+
+  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 gimple *m_stmt;
+  stmt_finder *m_stmt_finder;
+  const extrinsic_state &m_ext_state;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* A <program_point, program_state> pair, used internally by
+   exploded_node as its immutable data, and as a key for identifying
+   exploded_nodes we've already seen in the graph.  */
+
+struct point_and_state
+{
+  point_and_state (const program_point &point,
+		   const program_state &state)
+  : m_point (point),
+    m_state (state),
+    m_hash (m_point.hash () ^ m_state.hash ())
+  {
+  }
+
+  hashval_t hash () const
+  {
+    return m_hash;
+  }
+  bool operator== (const point_and_state &other) const
+  {
+    return m_point == other.m_point && m_state == other.m_state;
+  }
+
+  void set_state (const program_state &state)
+  {
+    m_state = state;
+    m_hash = m_point.hash () ^ m_state.hash ();
+  }
+
+  program_point m_point;
+  program_state m_state;
+  hashval_t m_hash;
+};
+
+/* A traits class for exploded graphs and their nodes and edges.  */
+
+struct eg_traits
+{
+  typedef exploded_node node_t;
+  typedef exploded_edge edge_t;
+  typedef exploded_graph graph_t;
+  struct dump_args_t
+  {
+    dump_args_t (const exploded_graph &eg) : m_eg (eg) {}
+    const exploded_graph &m_eg;
+  };
+  typedef exploded_cluster cluster_t;
+};
+
+/* An exploded_node is a unique, immutable <point, state> pair within the
+   exploded_graph.
+   Each exploded_node has a unique index within the graph
+   (for ease of debugging).  */
+
+class exploded_node : public dnode<eg_traits>
+{
+ public:
+  exploded_node (point_and_state ps,
+		 int index)
+  : m_ps (ps), m_index (index)
+  {
+    gcc_checking_assert (ps.m_state.m_region_model->canonicalized_p ());
+  }
+
+  hashval_t hash () const { return m_ps.hash (); }
+
+  void dump_dot (graphviz_out *gv, const dump_args_t &args)
+    const FINAL OVERRIDE;
+  void dump_dot_id (pretty_printer *pp) const;
+
+  void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const;
+  void dump (FILE *fp, const extrinsic_state &ext_state) const;
+  void dump (const extrinsic_state &ext_state) const;
+
+  bool on_stmt (exploded_graph &eg,
+		const supernode *snode,
+		const gimple *stmt,
+		program_state *state,
+		state_change *change) const;
+  bool on_edge (exploded_graph &eg,
+		const superedge *succ,
+		program_point *next_point,
+		program_state *next_state,
+		state_change *change) const;
+  void on_longjmp (exploded_graph &eg,
+		   const gcall *call,
+		   program_state *new_state,
+		   region_model_context *ctxt) const;
+
+  void detect_leaks (exploded_graph &eg) const;
+
+  const program_point &get_point () const { return m_ps.m_point; }
+  const supernode *get_supernode () const
+  {
+    return get_point ().get_supernode ();
+  }
+  function *get_function () const
+  {
+    return get_point ().get_function ();
+  }
+  int get_stack_depth () const
+  {
+    return get_point ().get_stack_depth ();
+  }
+  const gimple *get_stmt () const { return get_point ().get_stmt (); }
+
+  const program_state &get_state () const { return m_ps.m_state; }
+
+  const point_and_state *get_ps_key () const { return &m_ps; }
+  const program_point *get_point_key () const { return &m_ps.m_point; }
+
+  void dump_succs_and_preds (FILE *outf) const;
+
+private:
+  const char * get_dot_fillcolor () const;
+
+  /* The <program_point, program_state> pair.  This is const, as it
+     is immutable once the exploded_node has been created.  */
+  const point_and_state m_ps;
+
+public:
+  /* The index of this exploded_node.  */
+  const int m_index;
+};
+
+/* Extra data for an exploded_edge that represents a rewind from a
+   longjmp to a setjmp.  */
+
+class rewind_info_t
+{
+public:
+  rewind_info_t (const exploded_node *enode_origin)
+  : m_enode_origin (enode_origin)
+  {}
+
+  const program_point &get_setjmp_point () const
+  {
+    const program_point &origin_point = m_enode_origin->get_point ();
+
+    /* "origin_point" ought to be before the call to "setjmp".  */
+    gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT);
+
+    /* TODO: assert that it's the final stmt in its supernode.  */
+
+    return origin_point;
+  }
+
+  const gcall *get_setjmp_call () const
+  {
+    return as_a <const gcall *> (get_setjmp_point ().get_stmt ());
+  }
+
+  const exploded_node *get_enode_origin () const { return m_enode_origin; }
+
+private:
+  const exploded_node *m_enode_origin;
+};
+
+/* An edge within the exploded graph.
+   Some exploded_edges have an underlying superedge; others don't.  */
+
+class exploded_edge : public dedge<eg_traits>
+{
+ public:
+  exploded_edge (exploded_node *src, exploded_node *dest,
+		 const superedge *sedge,
+		 const state_change &change,
+		 rewind_info_t *rewind_info);
+  ~exploded_edge ();
+  void dump_dot (graphviz_out *gv, const dump_args_t &args)
+    const FINAL OVERRIDE;
+
+  //private:
+  const superedge *const m_sedge;
+
+  const state_change m_change;
+
+  /* NULL for most edges; will be non-NULL for an unwind from a longjmp
+     to a setjmp (owned by this class).  */
+  rewind_info_t *m_rewind_info;
+};
+
+/* Statistics about aspects of an exploded_graph.  */
+
+struct stats
+{
+  stats (int num_supernodes);
+  void log (logger *logger) const;
+  void dump (FILE *out) const;
+
+  int m_num_nodes[NUM_POINT_KINDS];
+  int m_node_reuse_count;
+  int m_node_reuse_after_merge_count;
+  int m_num_supernodes;
+};
+
+/* Traits class for ensuring uniqueness of point_and_state data within
+   an exploded_graph.  */
+
+struct eg_hash_map_traits
+{
+  typedef const point_and_state *key_type;
+  typedef exploded_node *value_type;
+  typedef exploded_node *compare_type;
+
+  static inline hashval_t hash (const key_type &k)
+  {
+    gcc_assert (k != NULL);
+    gcc_assert (k != reinterpret_cast<key_type> (1));
+    return k->hash ();
+  }
+  static inline bool equal_keys (const key_type &k1, const key_type &k2)
+  {
+    gcc_assert (k1 != NULL);
+    gcc_assert (k2 != NULL);
+    gcc_assert (k1 != reinterpret_cast<key_type> (1));
+    gcc_assert (k2 != reinterpret_cast<key_type> (1));
+    if (k1 && k2)
+      return *k1 == *k2;
+    else
+      /* Otherwise they must both be non-NULL.  */
+      return k1 == k2;
+  }
+  template <typename T>
+  static inline void remove (T &)
+  {
+    /* empty; the nodes are handled elsewhere.  */
+  }
+  template <typename T>
+  static inline void mark_deleted (T &entry)
+  {
+    entry.m_key = reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline void mark_empty (T &entry)
+  {
+    entry.m_key = NULL;
+  }
+  template <typename T>
+  static inline bool is_deleted (const T &entry)
+  {
+    return entry.m_key == reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline bool is_empty (const T &entry)
+  {
+    return entry.m_key == NULL;
+  }
+};
+
+/* Per-program_point data for an exploded_graph.  */
+
+struct per_program_point_data
+{
+  per_program_point_data (const program_point &key)
+  : m_key (key)
+  {}
+
+  program_point m_key;
+  auto_vec<exploded_node *> m_enodes;
+};
+
+/* Traits class for storing per-program_point data within
+   an exploded_graph.  */
+
+struct eg_point_hash_map_traits
+{
+  typedef const program_point *key_type;
+  typedef per_program_point_data *value_type;
+  typedef per_program_point_data *compare_type;
+
+  static inline hashval_t hash (const key_type &k)
+  {
+    gcc_assert (k != NULL);
+    gcc_assert (k != reinterpret_cast<key_type> (1));
+    return k->hash ();
+  }
+  static inline bool equal_keys (const key_type &k1, const key_type &k2)
+  {
+    gcc_assert (k1 != NULL);
+    gcc_assert (k2 != NULL);
+    gcc_assert (k1 != reinterpret_cast<key_type> (1));
+    gcc_assert (k2 != reinterpret_cast<key_type> (1));
+    if (k1 && k2)
+      return *k1 == *k2;
+    else
+      /* Otherwise they must both be non-NULL.  */
+      return k1 == k2;
+  }
+  template <typename T>
+  static inline void remove (T &)
+  {
+    /* empty; the nodes are handled elsewhere.  */
+  }
+  template <typename T>
+  static inline void mark_deleted (T &entry)
+  {
+    entry.m_key = reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline void mark_empty (T &entry)
+  {
+    entry.m_key = NULL;
+  }
+  template <typename T>
+  static inline bool is_deleted (const T &entry)
+  {
+    return entry.m_key == reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline bool is_empty (const T &entry)
+  {
+    return entry.m_key == NULL;
+  }
+};
+
+/* Data about a particular call_string within an exploded_graph.  */
+
+struct per_call_string_data
+{
+  per_call_string_data (const call_string &key, int num_supernodes)
+  : m_key (key), m_stats (num_supernodes)
+  {}
+
+  call_string m_key;
+  stats m_stats;
+};
+
+/* Traits class for storing per-call_string data within
+   an exploded_graph.  */
+
+struct eg_call_string_hash_map_traits
+{
+  typedef const call_string *key_type;
+  typedef per_call_string_data *value_type;
+  typedef per_call_string_data *compare_type;
+
+  static inline hashval_t hash (const key_type &k)
+  {
+    gcc_assert (k != NULL);
+    gcc_assert (k != reinterpret_cast<key_type> (1));
+    return k->hash ();
+  }
+  static inline bool equal_keys (const key_type &k1, const key_type &k2)
+  {
+    gcc_assert (k1 != NULL);
+    gcc_assert (k2 != NULL);
+    gcc_assert (k1 != reinterpret_cast<key_type> (1));
+    gcc_assert (k2 != reinterpret_cast<key_type> (1));
+    if (k1 && k2)
+      return *k1 == *k2;
+    else
+      /* Otherwise they must both be non-NULL.  */
+      return k1 == k2;
+  }
+  template <typename T>
+  static inline void remove (T &)
+  {
+    /* empty; the nodes are handled elsewhere.  */
+  }
+  template <typename T>
+  static inline void mark_deleted (T &entry)
+  {
+    entry.m_key = reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline void mark_empty (T &entry)
+  {
+    entry.m_key = NULL;
+  }
+  template <typename T>
+  static inline bool is_deleted (const T &entry)
+  {
+    return entry.m_key == reinterpret_cast<key_type> (1);
+  }
+  template <typename T>
+  static inline bool is_empty (const T &entry)
+  {
+    return entry.m_key == NULL;
+  }
+};
+
+/* Data about a particular function within an exploded_graph.  */
+
+struct per_function_data
+{
+  per_function_data () {}
+
+  void add_call_summary (exploded_node *node)
+  {
+    m_summaries.safe_push (node);
+  }
+
+  auto_vec<exploded_node *> m_summaries;
+};
+
+
+/* The strongly connected components of a supergraph.
+   In particular, this allows us to compute a partial ordering
+   of supernodes.  */
+
+class strongly_connected_components
+{
+public:
+  strongly_connected_components (const supergraph &sg, logger *logger);
+
+  int get_scc_id (int node_index) const
+  {
+    return m_per_node[node_index].m_lowlink;
+  }
+
+  void dump () const;
+
+private:
+  struct per_node_data
+  {
+    per_node_data ()
+      : m_index (-1), m_lowlink (-1), m_on_stack (false)
+    {}
+
+    int m_index;
+    int m_lowlink;
+    bool m_on_stack;
+  };
+
+  void strong_connect (unsigned index);
+
+  const supergraph &m_sg;
+  auto_vec<unsigned> m_stack;
+  auto_vec<per_node_data> m_per_node;
+};
+
+/* The worklist of exploded_node instances that have been added to
+   an exploded_graph, but that haven't yet been processed to find
+   their successors (or warnings).
+
+   The enodes are stored in a priority queue, ordered by a topological
+   sort of the SCCs in the supergraph, so that enodes for the same
+   program_point should appear at the front of the queue together.
+   This allows for state-merging at CFG join-points, so that
+   sufficiently-similar enodes can be merged into one.  */
+
+class worklist
+{
+public:
+  worklist (const exploded_graph &eg, const analysis_plan &plan);
+  unsigned length () const;
+  exploded_node *take_next ();
+  exploded_node *peek_next ();
+  void add_node (exploded_node *enode);
+
+private:
+  class key_t
+  {
+  public:
+    key_t (const worklist &w, exploded_node *enode)
+    : m_worklist (w), m_enode (enode)
+    {}
+
+    bool operator< (const key_t &other) const
+    {
+      return cmp (*this, other) < 0;
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return cmp (*this, other) == 0;
+    }
+
+    bool operator> (const key_t &other) const
+    {
+      return !(*this == other || *this < other);
+    }
+
+  private:
+    static int cmp_1 (const key_t &ka, const key_t &kb);
+    static int cmp (const key_t &ka, const key_t &kb);
+
+    int get_scc_id (const exploded_node *enode) const
+    {
+      const supernode *snode = enode->get_supernode ();
+      if (snode == NULL)
+	return 0;
+      return m_worklist.m_scc.get_scc_id (snode->m_index);
+    }
+
+    const worklist &m_worklist;
+    exploded_node *m_enode;
+  };
+
+  /* The order is important here: m_scc needs to stick around
+     until after m_queue has finished being cleaned up (the dtor
+     calls the ordering fns).  */
+  const exploded_graph &m_eg;
+  strongly_connected_components m_scc;
+  const analysis_plan &m_plan;
+
+  /* Priority queue, backed by a fibonacci_heap.  */
+  typedef fibonacci_heap<key_t, exploded_node> queue_t;
+  queue_t m_queue;
+};
+
+/* An exploded_graph is a directed graph of unique <point, state> pairs.
+   It also has a worklist of nodes that are waiting for their successors
+   to be added to the graph.  */
+
+class exploded_graph : public digraph<eg_traits>, public log_user
+{
+public:
+  typedef hash_map <const call_string *, per_call_string_data *,
+		    eg_call_string_hash_map_traits> call_string_data_map_t;
+
+  exploded_graph (const supergraph &sg, logger *logger,
+		  const extrinsic_state &ext_state,
+		  const state_purge_map *purge_map,
+		  const analysis_plan &plan,
+		  int verbosity);
+  ~exploded_graph ();
+
+  const supergraph &get_supergraph () const { return m_sg; }
+  const extrinsic_state &get_ext_state () const { return m_ext_state; }
+  const state_purge_map *get_purge_map () const { return m_purge_map; }
+  const analysis_plan &get_analysis_plan () const { return m_plan; }
+
+  exploded_node *get_origin () const { return m_origin; }
+
+  exploded_node *add_function_entry (function *fun);
+
+  void build_initial_worklist ();
+  void process_worklist ();
+  void process_node (exploded_node *node);
+
+  exploded_node *get_or_create_node (const program_point &point,
+				     const program_state &state,
+				     state_change *change);
+  void add_edge (exploded_node *src, exploded_node *dest,
+		 const superedge *sedge,
+		 const state_change &change,
+		 rewind_info_t *rewind_info = NULL);
+
+  per_program_point_data *
+  get_or_create_per_program_point_data (const program_point &);
+
+  per_call_string_data *
+  get_or_create_per_call_string_data (const call_string &);
+
+  per_function_data *
+  get_or_create_per_function_data (function *);
+  per_function_data *get_per_function_data (function *) const;
+
+  void save_diagnostic (const state_machine &sm,
+			const exploded_node *enode,
+			const supernode *node, const gimple *stmt,
+			stmt_finder *finder,
+			tree var, state_machine::state_t state,
+			pending_diagnostic *d);
+
+  diagnostic_manager &get_diagnostic_manager ()
+  {
+    return m_diagnostic_manager;
+  }
+
+  stats *get_global_stats () { return &m_global_stats; }
+  stats *get_or_create_function_stats (function *fn);
+  void log_stats () const;
+  void dump_stats (FILE *) const;
+  void dump_states_for_supernode (FILE *, const supernode *snode) const;
+  void dump_exploded_nodes () const;
+
+  const call_string_data_map_t *get_per_call_string_data () const
+  { return &m_per_call_string_data; }
+
+private:
+  const supergraph &m_sg;
+
+  /* Map from point/state to exploded node.
+     To avoid duplication we store point_and_state
+     *pointers* as keys, rather than point_and_state, using the
+     instance from within the exploded_node, with a custom hasher.  */
+  typedef hash_map <const point_and_state *, exploded_node *,
+		    eg_hash_map_traits> map_t;
+  map_t m_point_and_state_to_node;
+
+  /* Map from program_point to per-program_point data.  */
+  typedef hash_map <const program_point *, per_program_point_data *,
+		    eg_point_hash_map_traits> point_map_t;
+  point_map_t m_per_point_data;
+
+  worklist m_worklist;
+
+  exploded_node *m_origin;
+
+  const extrinsic_state &m_ext_state;
+
+  const state_purge_map *const m_purge_map;
+
+  const analysis_plan &m_plan;
+
+  typedef hash_map<function *, per_function_data *> per_function_data_t;
+  per_function_data_t m_per_function_data;
+
+  diagnostic_manager m_diagnostic_manager;
+
+  /* Stats.  */
+  stats m_global_stats;
+  typedef ordered_hash_map<function *, stats *> function_stat_map_t;
+  function_stat_map_t m_per_function_stats;
+  stats m_functionless_stats;
+
+  call_string_data_map_t m_per_call_string_data;
+
+
+  auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode;
+};
+
+/* A path within an exploded_graph: a sequence of edges.  */
+
+class exploded_path
+{
+public:
+  exploded_path () : m_edges () {}
+  exploded_path (const exploded_path &other);
+  exploded_path & operator= (const exploded_path &other);
+
+  unsigned length () const { return m_edges.length (); }
+
+  bool find_stmt_backwards (const gimple *search_stmt,
+			    int *out_idx) const;
+
+  exploded_node *get_final_enode () const;
+
+  void dump_to_pp (pretty_printer *pp) const;
+  void dump (FILE *fp) const;
+  void dump () const;
+
+  bool feasible_p (logger *logger) const;
+
+  auto_vec<const exploded_edge *> m_edges;
+};
+
+/* Finding the shortest exploded_path within an exploded_graph.  */
+
+typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths;
+
+/* Abstract base class for use when passing NULL as the stmt for
+   a possible warning, allowing the choice of stmt to be deferred
+   until after we have an emission path (and know we're emitting a
+   warning).  */
+
+class stmt_finder
+{
+public:
+  virtual ~stmt_finder () {}
+  virtual stmt_finder *clone () const = 0;
+  virtual const gimple *find_stmt (const exploded_path &epath) = 0;
+};
+
+// TODO: split the above up?
+
+#endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */