[46/49] analyzer: new files: checker-path.{cc|h}
diff mbox series

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

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m. UTC
This patch adds a family of classes for representing paths of events
for analyzer diagnostics.

gcc/ChangeLog:
	* analyzer/checker-path.cc: New file.
	* analyzer/checker-path.h: New file.
---
 gcc/analyzer/checker-path.cc | 899 +++++++++++++++++++++++++++++++++++++++++++
 gcc/analyzer/checker-path.h  | 563 +++++++++++++++++++++++++++
 2 files changed, 1462 insertions(+)
 create mode 100644 gcc/analyzer/checker-path.cc
 create mode 100644 gcc/analyzer/checker-path.h

Comments

Jeff Law Dec. 11, 2019, 8:50 p.m. UTC | #1
On Fri, 2019-11-15 at 20:23 -0500, David Malcolm wrote:
> This patch adds a family of classes for representing paths of events
> for analyzer diagnostics.
> 
> gcc/ChangeLog:
> 	* analyzer/checker-path.cc: New file.
> 	* analyzer/checker-path.h: New file.
> 
> 
No significant concerns here.  My brain is turning to mush.  That's
probably it for today.

jeff

Patch
diff mbox series

diff --git a/gcc/analyzer/checker-path.cc b/gcc/analyzer/checker-path.cc
new file mode 100644
index 0000000..5302504
--- /dev/null
+++ b/gcc/analyzer/checker-path.cc
@@ -0,0 +1,899 @@ 
+/* Subclasses of diagnostic_path and diagnostic_event for analyzer diagnostics.
+   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 "gimple.h"
+#include "gimple-pretty-print.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/checker-path.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/diagnostic-manager.h"
+#include "analyzer/exploded-graph.h"
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Get a string for EK.  */
+
+const char *
+event_kind_to_string (enum event_kind ek)
+{
+  switch (ek)
+    {
+    default:
+      gcc_unreachable ();
+    case EK_DEBUG:
+      return "EK_DEBUG";
+    case EK_STMT:
+      return "EK_STMT";
+    case EK_FUNCTION_ENTRY:
+      return "EK_FUNCTION_ENTRY";
+    case EK_STATE_CHANGE:
+      return "EK_STATE_CHANGE";
+    case EK_START_CFG_EDGE:
+      return "EK_START_CFG_EDGE";
+    case EK_END_CFG_EDGE:
+      return "EK_END_CFG_EDGE";
+    case EK_CALL_EDGE:
+      return "EK_CALL_EDGE";
+    case EK_RETURN_EDGE:
+      return "EK_RETURN_EDGE";
+    case EK_SETJMP:
+      return "EK_SETJMP";
+    case EK_REWIND_FROM_LONGJMP:
+      return "EK_REWIND_FROM_LONGJMP";
+    case EK_REWIND_TO_SETJMP:
+      return "EK_REWIND_TO_SETJMP";
+    case EK_WARNING:
+      return "EK_WARNING";
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class checker_event : public diagnostic_event.  */
+
+/* Dump this event to PP (for debugging/logging purposes).  */
+
+void
+checker_event::dump (pretty_printer *pp) const
+{
+  label_text event_desc (get_desc (false));
+  pp_printf (pp, "\"%s\" (depth %i, m_loc=%x)",
+	     event_desc.m_buffer,
+	     get_stack_depth (),
+	     get_location ());
+  event_desc.maybe_free ();
+}
+
+/* Hook for being notified when this event has its final id EMISSION_ID
+   and is about to emitted for PD.
+
+   Base implementation of checker_event::prepare_for_emission vfunc;
+   subclasses that override this should chain up to it.
+
+   Record PD and EMISSION_ID, and call the get_desc vfunc, so that any
+   side-effects of the call to get_desc take place before
+   pending_diagnostic::emit is called.
+
+   For example, state_change_event::get_desc can call
+   pending_diagnostic::describe_state_change; free_of_non_heap can use this
+   to tweak the message (TODO: would be neater to simply capture the
+   pertinent data within the sm-state).  */
+
+void
+checker_event::prepare_for_emission (checker_path *,
+				     pending_diagnostic *pd,
+				     diagnostic_event_id_t emission_id)
+{
+  m_pending_diagnostic = pd;
+  m_emission_id = emission_id;
+
+  label_text desc = get_desc (false);
+  desc.maybe_free ();
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class debug_event : public checker_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   debug_event.
+   Use the saved string as the event's description.  */
+
+label_text
+debug_event::get_desc (bool) const
+{
+  return label_text::borrow (m_desc);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class statement_event : public checker_event.  */
+
+/* statement_event's ctor.  */
+
+statement_event::statement_event (const gimple *stmt, tree fndecl, int depth,
+				  const program_state &dst_state)
+: checker_event (EK_STMT, gimple_location (stmt), fndecl, depth),
+  m_stmt (stmt),
+  m_dst_state (dst_state)
+{
+}
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   statement_event.
+   Use the statement's dump form as the event's description.  */
+
+label_text
+statement_event::get_desc (bool) const
+{
+  pretty_printer pp;
+  pp_string (&pp, "stmt: ");
+  pp_gimple_stmt_1 (&pp, m_stmt, 0, (dump_flags_t)0);
+  return label_text::take (xstrdup (pp_formatted_text (&pp)));
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class function_entry_event : public checker_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   function_entry_event.
+
+   Use a string such as "entry to 'foo'" as the event's description.  */
+
+label_text
+function_entry_event::get_desc (bool can_colorize) const
+{
+  return make_label_text (can_colorize, "entry to %qE", m_fndecl);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class state_change_event : public checker_event.  */
+
+/* state_change_event's ctor.  */
+
+state_change_event::state_change_event (const supernode *node,
+					const gimple *stmt,
+					int stack_depth,
+					const state_machine &sm,
+					tree var,
+					state_machine::state_t from,
+					state_machine::state_t to,
+					tree origin,
+					const program_state &dst_state)
+: checker_event (EK_STATE_CHANGE,
+		 stmt->location, node->m_fun->decl,
+		 stack_depth),
+  m_node (node), m_stmt (stmt), m_sm (sm),
+  m_var (var), m_from (from), m_to (to),
+  m_origin (origin),
+  m_dst_state (dst_state)
+{
+}
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   state_change_event.
+
+   Attempt to generate a nicer human-readable description.
+   For greatest precision-of-wording, give the pending diagnostic
+   a chance to describe this state change (in terms of the
+   diagnostic).
+   Note that we only have a pending_diagnostic set on the event once
+   the diagnostic is about to being emitted, so the description for
+   an event can change.  */
+
+label_text
+state_change_event::get_desc (bool can_colorize) const
+{
+  if (m_pending_diagnostic)
+    {
+      label_text custom_desc
+	= m_pending_diagnostic->describe_state_change
+	    (evdesc::state_change (can_colorize, m_var, m_origin,
+				   m_from, m_to, m_emission_id));
+      if (custom_desc.m_buffer)
+	{
+	  if (flag_analyzer_verbose_state_changes)
+	    {
+	      /* Append debug version.  */
+	      label_text result;
+	      if (m_origin)
+		result = make_label_text
+		  (can_colorize,
+		   "%s (state of %qE: %qs -> %qs, origin: %qE)",
+		   custom_desc.m_buffer,
+		   m_var,
+		   m_sm.get_state_name (m_from),
+		   m_sm.get_state_name (m_to),
+		   m_origin);
+	      else
+		result = make_label_text
+		  (can_colorize,
+		   "%s (state of %qE: %qs -> %qs, origin: NULL)",
+		   custom_desc.m_buffer,
+		   m_var,
+		   m_sm.get_state_name (m_from),
+		   m_sm.get_state_name (m_to));
+	      custom_desc.maybe_free ();
+	      return result;
+	    }
+	  else
+	    return custom_desc;
+	}
+    }
+
+  /* Fallback description.  */
+  if (m_origin)
+    return make_label_text
+      (can_colorize,
+       "state of %qE: %qs -> %qs (origin: %qE)",
+       m_var,
+       m_sm.get_state_name (m_from),
+       m_sm.get_state_name (m_to),
+       m_origin);
+  else
+    return make_label_text
+      (can_colorize,
+       "state of %qE: %qs -> %qs (origin: NULL)",
+       m_var,
+       m_sm.get_state_name (m_from),
+       m_sm.get_state_name (m_to));
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class superedge_event : public checker_event.  */
+
+/* Get the callgraph_superedge for this superedge_event, which must be
+   for an interprocedural edge, rather than a CFG edge.  */
+
+const callgraph_superedge&
+superedge_event::get_callgraph_superedge () const
+{
+  gcc_assert (m_sedge->m_kind != SUPEREDGE_CFG_EDGE);
+  return *m_sedge->dyn_cast_callgraph_superedge ();
+}
+
+/* Determine if this event should be filtered at the given verbosity
+   level.  */
+
+bool
+superedge_event::should_filter_p (int verbosity) const
+{
+  switch (m_sedge->m_kind)
+    {
+    case SUPEREDGE_CFG_EDGE:
+      {
+	if (verbosity < 2)
+	  return true;
+
+	if (verbosity == 2)
+	  {
+	    /* Filter events with empty descriptions.  This ought to filter
+	       FALLTHRU, but retain true/false/switch edges.  */
+	    label_text desc = get_desc (false);
+	    gcc_assert (desc.m_buffer);
+	    if (desc.m_buffer[0] == '\0')
+	      return true;
+	    desc.maybe_free ();
+	  }
+      }
+      break;
+
+    default:
+      break;
+    }
+  return false;
+}
+
+/* superedge_event's ctor.  */
+
+superedge_event::superedge_event (enum event_kind kind,
+				  const exploded_edge &eedge,
+				  location_t loc, tree fndecl, int depth)
+: checker_event (kind, loc, fndecl, depth),
+  m_eedge (eedge), m_sedge (eedge.m_sedge),
+  m_var (NULL_TREE), m_critical_state (0)
+{
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class cfg_edge_event : public superedge_event.  */
+
+/* Get the cfg_superedge for this cfg_edge_event.  */
+
+const cfg_superedge &
+cfg_edge_event::get_cfg_superedge () const
+{
+  return *m_sedge->dyn_cast_cfg_superedge ();
+}
+
+/* cfg_edge_event's ctor.  */
+
+cfg_edge_event::cfg_edge_event (enum event_kind kind,
+				const exploded_edge &eedge,
+				location_t loc, tree fndecl, int depth)
+: superedge_event (kind, eedge, loc, fndecl, depth)
+{
+  gcc_assert (eedge.m_sedge->m_kind == SUPEREDGE_CFG_EDGE);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class start_cfg_edge_event : public cfg_edge_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   start_cfg_edge_event.
+
+   If -fanalyzer-verbose-edges, then generate low-level descriptions, such
+   as
+     "taking 'true' edge SN:7 -> SN:8".
+
+   Otherwise, generate strings using the label of the underlying CFG if
+   any, such as:
+     "following 'true' branch..." or
+     "following 'case 3' branch..."
+     "following 'default' branch..."
+
+   For conditionals, attempt to supply a description of the condition that
+   holds, such as:
+     "following 'false' branch (when 'ptr' is non-NULL)..."
+
+   Failing that, return an empty description (which will lead to this event
+   being filtered).  */
+
+label_text
+start_cfg_edge_event::get_desc (bool can_colorize) const
+{
+  bool user_facing = !flag_analyzer_verbose_edges;
+  char *edge_desc = m_sedge->get_description (user_facing);
+  if (user_facing)
+    {
+      if (edge_desc && strlen (edge_desc) > 0)
+	{
+	  label_text cond_desc = maybe_describe_condition (can_colorize);
+	  label_text result;
+	  if (cond_desc.m_buffer)
+	    {
+	      result = make_label_text (can_colorize,
+					"following %qs branch (%s)...",
+					edge_desc, cond_desc.m_buffer);
+	      cond_desc.maybe_free ();
+	    }
+	  else
+	    {
+	      result = make_label_text (can_colorize,
+					"following %qs branch...",
+					edge_desc);
+	    }
+	  free (edge_desc);
+	  return result;
+	}
+      else
+	{
+	  free (edge_desc);
+	  return label_text::borrow ("");
+	}
+    }
+  else
+    {
+      if (strlen (edge_desc) > 0)
+	{
+	  label_text result
+	    = make_label_text (can_colorize,
+			       "taking %qs edge SN:%i -> SN:%i",
+			       edge_desc,
+			       m_sedge->m_src->m_index,
+			       m_sedge->m_dest->m_index);
+	  free (edge_desc);
+	  return result;
+	}
+      else
+	{
+	  free (edge_desc);
+	  return make_label_text (can_colorize,
+				  "taking edge SN:%i -> SN:%i",
+				  m_sedge->m_src->m_index,
+				  m_sedge->m_dest->m_index);
+	}
+    }
+}
+
+/* Attempt to generate a description of any condition that holds at this edge.
+
+   The intent is to make the user-facing messages more clear, especially for
+   cases where there's a single or double-negative, such as
+   when describing the false branch of an inverted condition.
+
+   For example, rather than printing just:
+
+      |  if (!ptr)
+      |     ~
+      |     |
+      |     (1) following 'false' branch...
+
+   it's clearer to spell out the condition that holds:
+
+      |  if (!ptr)
+      |     ~
+      |     |
+      |     (1) following 'false' branch (when 'ptr' is non-NULL)...
+                                          ^^^^^^^^^^^^^^^^^^^^^^
+
+   In the above example, this function would generate the highlighted
+   string: "when 'ptr' is non-NULL".
+
+   If the edge is not a condition, or it's not clear that a description of
+   the condition would be helpful to the user, return NULL.  */
+
+label_text
+start_cfg_edge_event::maybe_describe_condition (bool can_colorize) const
+{
+  const cfg_superedge& cfg_sedge = get_cfg_superedge ();
+
+  if (cfg_sedge.true_value_p () || cfg_sedge.false_value_p ())
+    {
+      const gimple *last_stmt = m_sedge->m_src->get_last_stmt ();
+      if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt))
+	{
+	  enum tree_code op = gimple_cond_code (cond_stmt);
+	  tree lhs = gimple_cond_lhs (cond_stmt);
+	  tree rhs = gimple_cond_rhs (cond_stmt);
+	  if (cfg_sedge.false_value_p ())
+	    op = invert_tree_comparison (op, false /* honor_nans */);
+	  return maybe_describe_condition (can_colorize,
+					   lhs, op, rhs);
+	}
+    }
+  return label_text::borrow (NULL);
+}
+
+/* Subroutine of maybe_describe_condition above.
+
+   Attempt to generate a user-facing description of the condition
+   LHS OP RHS, but only if it is likely to make it easier for the
+   user to understand a condition.  */
+
+label_text
+start_cfg_edge_event::maybe_describe_condition (bool can_colorize,
+						tree lhs,
+						enum tree_code op,
+						tree rhs)
+{
+  /* In theory we could just build a tree via
+       fold_build2 (op, boolean_type_node, lhs, rhs)
+     and print it with %qE on it, but this leads to warts such as
+     parenthesizing vars, such as '(i) <= 9', and uses of '<unknown>'.  */
+
+  /* Only attempt to generate text for sufficiently simple expressions.  */
+  if (!should_print_expr_p (lhs))
+    return label_text::borrow (NULL);
+  if (!should_print_expr_p (rhs))
+    return label_text::borrow (NULL);
+
+  /* Special cases for pointer comparisons against NULL.  */
+  if (POINTER_TYPE_P (TREE_TYPE (lhs))
+      && POINTER_TYPE_P (TREE_TYPE (rhs))
+      && zerop (rhs))
+    {
+      if (op == EQ_EXPR)
+	return make_label_text (can_colorize, "when %qE is NULL",
+				lhs);
+      if (op == NE_EXPR)
+	return make_label_text (can_colorize, "when %qE is non-NULL",
+				lhs);
+    }
+
+  return make_label_text (can_colorize, "when %<%E %s %E%>",
+			  lhs, op_symbol_code (op), rhs);
+}
+
+/* Subroutine of maybe_describe_condition.
+
+   Return true if EXPR is we will get suitable user-facing output
+   from %E on it.  */
+
+bool
+start_cfg_edge_event::should_print_expr_p (tree expr)
+{
+  if (TREE_CODE (expr) == SSA_NAME)
+    {
+      if (SSA_NAME_VAR (expr))
+	return should_print_expr_p (SSA_NAME_VAR (expr));
+      else
+	return false;
+    }
+
+  if (DECL_P (expr))
+    return true;
+
+  if (CONSTANT_CLASS_P (expr))
+    return true;
+
+  return false;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class call_event : public superedge_event.  */
+
+/* call_event's ctor.  */
+
+call_event::call_event (const exploded_edge &eedge,
+			location_t loc, tree fndecl, int depth)
+: superedge_event (EK_CALL_EDGE, eedge, loc, fndecl, depth)
+{
+  gcc_assert (eedge.m_sedge->m_kind == SUPEREDGE_CALL);
+}
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   call_event.
+
+   If this call event passes critical state for an sm-based warning,
+   allow the diagnostic to generate a precise description, such as:
+
+     "passing freed pointer 'ptr' in call to 'foo' from 'bar'"
+
+   Otherwise, generate a description of the form
+   "calling 'foo' from 'bar'".  */
+
+label_text
+call_event::get_desc (bool can_colorize) const
+{
+  if (m_critical_state && m_pending_diagnostic)
+    {
+      gcc_assert (m_var);
+      label_text custom_desc
+	= m_pending_diagnostic->describe_call_with_state
+	    (evdesc::call_with_state (can_colorize,
+				      m_sedge->m_src->m_fun->decl,
+				      m_sedge->m_dest->m_fun->decl,
+				      m_var,
+				      m_critical_state));
+      if (custom_desc.m_buffer)
+	return custom_desc;
+    }
+
+  return make_label_text (can_colorize,
+			  "calling %qE from %qE",
+			  m_sedge->m_dest->m_fun->decl,
+			  m_sedge->m_src->m_fun->decl);
+}
+
+/* Override of checker_event::is_call_p for calls.  */
+
+bool
+call_event::is_call_p () const
+{
+  return true;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class return_event : public superedge_event.  */
+
+/* return_event's ctor.  */
+
+return_event::return_event (const exploded_edge &eedge,
+			    location_t loc, tree fndecl, int depth)
+: superedge_event (EK_RETURN_EDGE, eedge, loc, fndecl, depth)
+{
+  gcc_assert (eedge.m_sedge->m_kind == SUPEREDGE_RETURN);
+}
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   return_event.
+
+   If this return event returns critical state for an sm-based warning,
+   allow the diagnostic to generate a precise description, such as:
+
+      "possible of NULL to 'foo' from 'bar'"
+
+   Otherwise, generate a description of the form
+   "returning to 'foo' from 'bar'.  */
+
+label_text
+return_event::get_desc (bool can_colorize) const
+{
+  /*  For greatest precision-of-wording, if this is returning the
+      state involved in the pending diagnostic, give the pending
+      diagnostic a chance to describe this return (in terms of
+      itself).  */
+  if (m_critical_state && m_pending_diagnostic)
+    {
+      label_text custom_desc
+	= m_pending_diagnostic->describe_return_of_state
+	    (evdesc::return_of_state (can_colorize,
+				      m_sedge->m_dest->m_fun->decl,
+				      m_sedge->m_src->m_fun->decl,
+				      m_critical_state));
+      if (custom_desc.m_buffer)
+	return custom_desc;
+    }
+  return make_label_text (can_colorize,
+			  "returning to %qE from %qE",
+			  m_sedge->m_dest->m_fun->decl,
+			  m_sedge->m_src->m_fun->decl);
+}
+
+/* Override of checker_event::is_return_p for returns.  */
+
+bool
+return_event::is_return_p () const
+{
+  return true;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class setjmp_event : public checker_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   setjmp_event.  */
+
+label_text
+setjmp_event::get_desc (bool can_colorize) const
+{
+  return make_label_text (can_colorize,
+			  "%qs called here",
+			  "setjmp");
+}
+
+/* Implementation of checker_event::prepare_for_emission vfunc for setjmp_event.
+
+   Record this setjmp's event ID into the path, so that rewind events can
+   use it.  */
+
+void
+setjmp_event::prepare_for_emission (checker_path *path,
+				    pending_diagnostic *pd,
+				    diagnostic_event_id_t emission_id)
+{
+  checker_event::prepare_for_emission (path, pd, emission_id);
+  path->record_setjmp_event (m_enode, emission_id);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class rewind_event : public checker_event.  */
+
+/* Get the fndecl containing the site of the longjmp call.  */
+
+tree
+rewind_event::get_longjmp_caller () const
+{
+  return m_eedge->m_src->get_function ()->decl;
+}
+
+/* Get the fndecl containing the site of the setjmp call.  */
+
+tree
+rewind_event::get_setjmp_caller () const
+{
+  return m_eedge->m_dest->get_function ()->decl;
+}
+
+/* rewind_event's ctor.  */
+
+rewind_event::rewind_event (const exploded_edge *eedge,
+			    enum event_kind kind,
+			    location_t loc, tree fndecl, int depth)
+: checker_event (kind, loc, fndecl, depth),
+  m_eedge (eedge)
+{
+  gcc_assert (m_eedge->m_rewind_info);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class rewind_from_longjmp_event : public rewind_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   rewind_from_longjmp_event.  */
+
+label_text
+rewind_from_longjmp_event::get_desc (bool can_colorize) const
+{
+  const char *src_name = "longjmp";
+
+  if (get_longjmp_caller () == get_setjmp_caller ())
+    /* Special-case: purely intraprocedural rewind.  */
+    return make_label_text (can_colorize,
+			    "rewinding within %qE from %qs...",
+			    get_longjmp_caller (),
+			    src_name);
+  else
+    return make_label_text (can_colorize,
+			    "rewinding from %qs in %qE...",
+			    src_name,
+			    get_longjmp_caller ());
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class rewind_to_setjmp_event : public rewind_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   rewind_to_setjmp_event.  */
+
+label_text
+rewind_to_setjmp_event::get_desc (bool can_colorize) const
+{
+  const char *dst_name = "setjmp";
+
+  /* If we can, identify the ID of the setjmp_event.  */
+  if (m_original_setjmp_event_id.known_p ())
+    {
+      if (get_longjmp_caller () == get_setjmp_caller ())
+	/* Special-case: purely intraprocedural rewind.  */
+	return make_label_text (can_colorize,
+				"...to %qs (saved at %@)",
+				dst_name,
+				&m_original_setjmp_event_id);
+      else
+	return make_label_text (can_colorize,
+				"...to %qs in %qE (saved at %@)",
+				dst_name,
+				get_setjmp_caller (),
+				&m_original_setjmp_event_id);
+    }
+  else
+    {
+      if (get_longjmp_caller () == get_setjmp_caller ())
+	/* Special-case: purely intraprocedural rewind.  */
+	return make_label_text (can_colorize,
+				"...to %qs",
+				dst_name,
+				get_setjmp_caller ());
+      else
+	return make_label_text (can_colorize,
+				"...to %qs in %qE",
+				dst_name,
+				get_setjmp_caller ());
+    }
+}
+
+/* Implementation of checker_event::prepare_for_emission vfunc for
+   rewind_to_setjmp_event.
+
+   Attempt to look up the setjmp event ID that recorded the jmp_buf
+   for this rewind.  */
+
+void
+rewind_to_setjmp_event::prepare_for_emission (checker_path *path,
+					      pending_diagnostic *pd,
+					      diagnostic_event_id_t emission_id)
+{
+  checker_event::prepare_for_emission (path, pd, emission_id);
+  path->get_setjmp_event (get_eedge ()->m_rewind_info->get_enode_origin (),
+			  &m_original_setjmp_event_id);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class warning_event : public checker_event.  */
+
+/* Implementation of diagnostic_event::get_desc vfunc for
+   warning_event.
+
+   If the pending diagnostic implements describe_final_event, use it,
+   generating a precise description e.g.
+     "second 'free' here; first 'free' was at (7)"
+
+   Otherwise generate a generic description.  */
+
+label_text
+warning_event::get_desc (bool can_colorize) const
+{
+  if (m_pending_diagnostic)
+    {
+      label_text ev_desc
+	= m_pending_diagnostic->describe_final_event
+	    (evdesc::final_event (can_colorize, m_var, m_state));
+      if (ev_desc.m_buffer)
+	{
+	  if (m_sm && flag_analyzer_verbose_state_changes)
+	    {
+	      label_text result
+		= make_label_text (can_colorize,
+				   "%s (%qE is in state %qs)",
+				   ev_desc.m_buffer,
+				   m_var,m_sm->get_state_name (m_state));
+	      ev_desc.maybe_free ();
+	      return result;
+	    }
+	  else
+	    return ev_desc;
+	}
+    }
+
+  if (m_sm)
+    return make_label_text (can_colorize,
+			    "here (%qE is in state %qs)",
+			    m_var,
+			    m_sm->get_state_name (m_state));
+  else
+    return label_text::borrow ("here");
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Print a single-line representation of this path to PP.  */
+
+void
+checker_path::dump (pretty_printer *pp) const
+{
+  pp_character (pp, '[');
+
+  checker_event *e;
+  int i;
+  FOR_EACH_VEC_ELT (m_events, i, e)
+    {
+      if (i > 0)
+	pp_string (pp, ", ");
+      label_text event_desc (e->get_desc (false));
+      pp_printf (pp, "\"%s\"", event_desc.m_buffer);
+      event_desc.maybe_free ();
+    }
+  pp_character (pp, ']');
+}
+
+/* Print a multiline form of this path to LOGGER, prefixing it with DESC.  */
+
+void
+checker_path::maybe_log (logger *logger, const char *desc) const
+{
+  if (!logger)
+    return;
+  logger->start_log_line ();
+  logger->log_partial ("%s: ", desc);
+  dump (logger->get_printer ());
+  logger->end_log_line ();
+  for (unsigned i = 0; i < m_events.length (); i++)
+    {
+      logger->start_log_line ();
+      logger->log_partial ("%s[%i]: %s ", desc, i,
+			   event_kind_to_string (m_events[i]->m_kind));
+      m_events[i]->dump (logger->get_printer ());
+      logger->end_log_line ();
+    }
+}
+
+/* Add a warning_event to the end of this path.  */
+
+void
+checker_path::add_final_event (const state_machine *sm,
+			       const exploded_node *enode, const gimple *stmt,
+			       tree var, state_machine::state_t state)
+{
+  checker_event *end_of_path
+    = new warning_event (stmt->location,
+			 enode->get_function ()->decl,
+			 enode->get_stack_depth (),
+			 sm, var, state);
+  add_event (end_of_path);
+}
diff --git a/gcc/analyzer/checker-path.h b/gcc/analyzer/checker-path.h
new file mode 100644
index 0000000..f042f47
--- /dev/null
+++ b/gcc/analyzer/checker-path.h
@@ -0,0 +1,563 @@ 
+/* Subclasses of diagnostic_path and diagnostic_event for analyzer diagnostics.
+   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_CHECKER_PATH_H
+#define GCC_ANALYZER_CHECKER_PATH_H
+
+#include "diagnostic-path.h"
+#include "analyzer/program-state.h"
+
+////////////////////////////////////////////////////////////////////////////
+
+/* An enum for discriminating between the concrete subclasses of
+   checker_event.  */
+
+enum event_kind
+{
+  EK_DEBUG,
+  EK_STMT,
+  EK_FUNCTION_ENTRY,
+  EK_STATE_CHANGE,
+  EK_START_CFG_EDGE,
+  EK_END_CFG_EDGE,
+  EK_CALL_EDGE,
+  EK_RETURN_EDGE,
+  EK_SETJMP,
+  EK_REWIND_FROM_LONGJMP,
+  EK_REWIND_TO_SETJMP,
+  EK_WARNING
+};
+
+extern const char *event_kind_to_string (enum event_kind ek);
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Event subclasses.
+
+   The class hierarchy looks like this (using indentation to show
+   inheritance, and with event_kinds shown for the concrete subclasses):
+
+   diagnostic_event
+     checker_event
+       debug_event (EK_DEBUG)
+       statement_event (EK_STMT)
+       function_entry_event (EK_FUNCTION_ENTRY)
+       state_change_event (EK_STATE_CHANGE)
+       superedge_event
+         cfg_edge_event
+	   start_cfg_edge_event (EK_START_CFG_EDGE)
+	   end_cfg_edge_event (EK_END_CFG_EDGE)
+         call_event (EK_CALL_EDGE)
+         return_edge (EK_RETURN_EDGE)
+       setjmp_event (EK_SETJMP)
+       rewind_event
+         rewind_from_longjmp_event (EK_REWIND_FROM_LONGJMP)
+	 rewind_to_setjmp_event (EK_REWIND_TO_SETJMP)
+       warning_event (EK_WARNING).  */
+
+/* Abstract subclass of diagnostic_event; the base class for use in
+   checker_path (the analyzer's diagnostic_path subclass).  */
+
+class checker_event : public diagnostic_event
+{
+public:
+  checker_event (enum event_kind kind,
+		 location_t loc, tree fndecl, int depth)
+    : m_kind (kind), m_loc (loc), m_fndecl (fndecl), m_depth (depth),
+      m_pending_diagnostic (NULL), m_emission_id ()
+  {
+  }
+
+  /* Implementation of diagnostic_event.  */
+
+  location_t get_location () const FINAL OVERRIDE { return m_loc; }
+  tree get_fndecl () const FINAL OVERRIDE { return m_fndecl; }
+  int get_stack_depth () const FINAL OVERRIDE { return m_depth; }
+
+  /* Additional functionality.  */
+
+  virtual checker_event *clone () const = 0;
+
+  virtual void prepare_for_emission (checker_path *,
+				     pending_diagnostic *pd,
+				     diagnostic_event_id_t emission_id);
+  virtual bool is_call_p () const { return false; }
+  virtual bool is_function_entry_p () const  { return false; }
+  virtual bool is_return_p () const  { return false; }
+
+  void dump (pretty_printer *pp) const;
+
+ public:
+  const enum event_kind m_kind;
+ protected:
+  location_t m_loc;
+  tree m_fndecl;
+  int m_depth;
+  pending_diagnostic *m_pending_diagnostic;
+  diagnostic_event_id_t m_emission_id; // only set once all pruning has occurred
+};
+
+/* A concrete event subclass for a purely textual event, for use in
+   debugging path creation and filtering.  */
+
+class debug_event : public checker_event
+{
+public:
+  debug_event (location_t loc, tree fndecl, int depth,
+	      const char *desc)
+  : checker_event (EK_DEBUG, loc, fndecl, depth),
+    m_desc (xstrdup (desc))
+  {
+  }
+  ~debug_event ()
+  {
+    free (m_desc);
+  }
+
+  label_text get_desc (bool) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new debug_event (m_loc, m_fndecl, m_depth, m_desc);
+  }
+
+private:
+  char *m_desc;
+};
+
+/* A concrete event subclass describing the execution of a gimple statement,
+   for use at high verbosity levels when debugging paths.  */
+
+class statement_event : public checker_event
+{
+public:
+  statement_event (const gimple *stmt, tree fndecl, int depth,
+		   const program_state &dst_state);
+
+  label_text get_desc (bool) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new statement_event (m_stmt, m_fndecl, m_depth, m_dst_state);
+  }
+
+  const gimple * const m_stmt;
+  const program_state m_dst_state;
+};
+
+/* An event subclass describing the entry to a function.  */
+
+class function_entry_event : public checker_event
+{
+public:
+  function_entry_event (location_t loc, tree fndecl, int depth)
+  : checker_event (EK_FUNCTION_ENTRY, loc, fndecl, depth)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new function_entry_event (m_loc, m_fndecl, m_depth);
+  }
+
+  bool is_function_entry_p () const FINAL OVERRIDE { return true; }
+};
+
+/* Subclass of checker_event describing a state change.  */
+
+class state_change_event : public checker_event
+{
+public:
+  state_change_event (const supernode *node, const gimple *stmt,
+		      int stack_depth,
+		      const state_machine &sm,
+		      tree var,
+		      state_machine::state_t from,
+		      state_machine::state_t to,
+		      tree origin,
+		      const program_state &dst_state);
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new state_change_event (m_node, m_stmt, m_depth,
+				   m_sm, m_var, m_from, m_to, m_origin,
+				   m_dst_state);
+  }
+
+  region_id get_lvalue (tree expr) const
+  {
+    return m_dst_state.m_region_model->get_lvalue (expr, NULL);
+  }
+
+  const supernode *m_node;
+  const gimple *m_stmt;
+  const state_machine &m_sm;
+  tree m_var;
+  state_machine::state_t m_from;
+  state_machine::state_t m_to;
+  tree m_origin;
+  program_state m_dst_state;
+};
+
+/* Subclass of checker_event; parent class for subclasses that relate to
+   a superedge.  */
+
+class superedge_event : public checker_event
+{
+public:
+  /* Mark this edge event as being either an interprocedural call or
+     return in which VAR is in STATE, and that this is critical to the
+     diagnostic (so that get_desc can attempt to get a better description
+     from any pending_diagnostic).  */
+  void record_critical_state (tree var, state_machine::state_t state)
+  {
+    m_var = var;
+    m_critical_state = state;
+  }
+
+  const callgraph_superedge& get_callgraph_superedge () const;
+
+  bool should_filter_p (int verbosity) const;
+
+ protected:
+  superedge_event (enum event_kind kind, const exploded_edge &eedge,
+		   location_t loc, tree fndecl, int depth);
+
+ public:
+  const exploded_edge &m_eedge;
+  const superedge *m_sedge;
+  tree m_var;
+  state_machine::state_t m_critical_state;
+};
+
+/* An abstract event subclass for when a CFG edge is followed; it has two
+   subclasses, representing the start of the edge and the end of the
+   edge, which come in pairs.  */
+
+class cfg_edge_event : public superedge_event
+{
+public:
+  const cfg_superedge& get_cfg_superedge () const;
+
+ protected:
+  cfg_edge_event (enum event_kind kind, const exploded_edge &eedge,
+		  location_t loc, tree fndecl, int depth);
+};
+
+/* A concrete event subclass for the start of a CFG edge
+   e.g. "following 'false' branch...'.  */
+
+class start_cfg_edge_event : public cfg_edge_event
+{
+public:
+  start_cfg_edge_event (const exploded_edge &eedge,
+			location_t loc, tree fndecl, int depth)
+  : cfg_edge_event (EK_START_CFG_EDGE, eedge, loc, fndecl, depth)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new start_cfg_edge_event (m_eedge, m_loc, m_fndecl, m_depth);
+  }
+
+ private:
+  label_text maybe_describe_condition (bool can_colorize) const;
+
+  static label_text maybe_describe_condition (bool can_colorize,
+					      tree lhs,
+					      enum tree_code op,
+					      tree rhs);
+  static bool should_print_expr_p (tree);
+};
+
+/* A concrete event subclass for the end of a CFG edge
+   e.g. "...to here'.  */
+
+class end_cfg_edge_event : public cfg_edge_event
+{
+public:
+  end_cfg_edge_event (const exploded_edge &eedge,
+		      location_t loc, tree fndecl, int depth)
+  : cfg_edge_event (EK_END_CFG_EDGE, eedge, loc, fndecl, depth)
+  {
+  }
+
+  label_text get_desc (bool /*can_colorize*/) const FINAL OVERRIDE
+  {
+    return label_text::borrow ("...to here");
+  }
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new end_cfg_edge_event (m_eedge, m_loc, m_fndecl, m_depth);
+  }
+};
+
+/* A concrete event subclass for an interprocedural call.  */
+
+class call_event : public superedge_event
+{
+public:
+  call_event (const exploded_edge &eedge,
+	      location_t loc, tree fndecl, int depth);
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new call_event (m_eedge, m_loc, m_fndecl, m_depth);
+  }
+
+  bool is_call_p () const FINAL OVERRIDE;
+};
+
+/* A concrete event subclass for an interprocedural return.  */
+
+class return_event : public superedge_event
+{
+public:
+  return_event (const exploded_edge &eedge,
+		location_t loc, tree fndecl, int depth);
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  checker_event *clone () const FINAL OVERRIDE
+  {
+    return new return_event (m_eedge, m_loc, m_fndecl, m_depth);
+  }
+
+  bool is_return_p () const FINAL OVERRIDE;
+};
+
+/* A concrete event subclass for a setjmp call.  */
+
+class setjmp_event : public checker_event
+{
+public:
+  setjmp_event (location_t loc, const exploded_node *enode,
+		tree fndecl, int depth)
+  : checker_event (EK_SETJMP, loc, fndecl, depth),
+    m_enode (enode)
+  {
+  }
+
+  setjmp_event *clone () const FINAL OVERRIDE
+  {
+    return new setjmp_event (m_loc, m_enode, m_fndecl, m_depth);
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  void prepare_for_emission (checker_path *path,
+			     pending_diagnostic *pd,
+			     diagnostic_event_id_t emission_id) FINAL OVERRIDE;
+
+private:
+  const exploded_node *m_enode;
+};
+
+/* An abstract event subclass for rewinding from a longjmp to a setjmp.
+   Base class for two from/to subclasses, showing the two halves of the
+   rewind.  */
+
+class rewind_event : public checker_event
+{
+public:
+  tree get_longjmp_caller () const;
+  tree get_setjmp_caller () const;
+  const exploded_edge *get_eedge () const { return m_eedge; }
+
+ protected:
+  rewind_event (const exploded_edge *eedge,
+		enum event_kind kind,
+		location_t loc, tree fndecl, int depth);
+
+ private:
+  const exploded_edge *m_eedge;
+};
+
+/* A concrete event subclass for rewinding from a longjmp to a setjmp,
+   showing the longjmp.  */
+
+class rewind_from_longjmp_event : public rewind_event
+{
+public:
+  rewind_from_longjmp_event (const exploded_edge *eedge,
+			     location_t loc, tree fndecl, int depth)
+  : rewind_event (eedge, EK_REWIND_FROM_LONGJMP, loc, fndecl, depth)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  rewind_from_longjmp_event *clone () const FINAL OVERRIDE
+  {
+    return new rewind_from_longjmp_event (get_eedge (),
+					  m_loc, m_fndecl, m_depth);
+  }
+};
+
+/* A concrete event subclass for rewinding from a longjmp to a setjmp,
+   showing the setjmp.  */
+
+class rewind_to_setjmp_event : public rewind_event
+{
+public:
+  rewind_to_setjmp_event (const exploded_edge *eedge,
+			  location_t loc, tree fndecl, int depth)
+  : rewind_event (eedge, EK_REWIND_TO_SETJMP, loc, fndecl, depth)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  rewind_to_setjmp_event *clone () const FINAL OVERRIDE
+  {
+    return new rewind_to_setjmp_event (get_eedge (),
+				       m_loc, m_fndecl, m_depth);
+  }
+
+  void prepare_for_emission (checker_path *path,
+			     pending_diagnostic *pd,
+			     diagnostic_event_id_t emission_id) FINAL OVERRIDE;
+
+private:
+  diagnostic_event_id_t m_original_setjmp_event_id;
+};
+
+/* Concrete subclass of checker_event for use at the end of a path:
+   a repeat of the warning message at the end of the path (perhaps with
+   references to pertinent events that occurred on the way), at the point
+   where the problem occurs.  */
+
+class warning_event : public checker_event
+{
+public:
+  warning_event (location_t loc, tree fndecl, int depth,
+		 const state_machine *sm,
+		 tree var, state_machine::state_t state)
+  : checker_event (EK_WARNING, loc, fndecl, depth),
+    m_sm (sm), m_var (var), m_state (state)
+  {
+  }
+
+  label_text get_desc (bool can_colorize) const FINAL OVERRIDE;
+
+  warning_event *clone () const FINAL OVERRIDE
+  {
+    return new warning_event (m_loc, m_fndecl, m_depth, m_sm, m_var, m_state);
+  }
+
+private:
+  const state_machine *m_sm;
+  tree m_var;
+  state_machine::state_t m_state;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* Subclass of diagnostic_path for analyzer diagnostics.  */
+
+class checker_path : public diagnostic_path
+{
+public:
+  checker_path () : diagnostic_path () {}
+
+  /* Implementation of diagnostic_path vfuncs.  */
+
+  unsigned num_events () const FINAL OVERRIDE
+  {
+    return m_events.length ();
+  }
+
+  const diagnostic_event & get_event (int idx) const FINAL OVERRIDE
+  {
+    return *m_events[idx];
+  }
+
+
+  void dump (pretty_printer *pp) const;
+
+  void maybe_log (logger *logger, const char *desc) const;
+
+  void add_event (checker_event *event)
+  {
+    m_events.safe_push (event);
+  }
+
+  void delete_event (int idx)
+  {
+    checker_event *event = m_events[idx];
+    m_events.ordered_remove (idx);
+    delete event;
+  }
+
+  void add_final_event (const state_machine *sm,
+			const exploded_node *enode, const gimple *stmt,
+			tree var, state_machine::state_t state);
+
+  /* After all event-pruning, a hook for notifying each event what
+     its ID will be.  The events are notified in order, allowing
+     for later events to refer to the IDs of earlier events in
+     their descriptions.  */
+  void prepare_for_emission (pending_diagnostic *pd)
+  {
+    checker_event *e;
+    int i;
+    FOR_EACH_VEC_ELT (m_events, i, e)
+      e->prepare_for_emission (this, pd, diagnostic_event_id_t (i));
+  }
+
+  void record_setjmp_event (const exploded_node *enode,
+			    diagnostic_event_id_t setjmp_emission_id)
+  {
+    m_setjmp_event_ids.put (enode, setjmp_emission_id);
+  }
+
+  bool get_setjmp_event (const exploded_node *enode,
+			 diagnostic_event_id_t *out_emission_id)
+  {
+    if (diagnostic_event_id_t *emission_id = m_setjmp_event_ids.get (enode))
+      {
+	*out_emission_id = *emission_id;
+	return true;
+      }
+    return false;
+  }
+
+  ////////////////////////////////////////////////////////////////////////////
+
+  /* The events that have occurred along this path.  */
+  auto_delete_vec<checker_event> m_events;
+
+  /* During prepare_for_emission (and after), the setjmp_event for each
+     exploded_node *, so that rewind events can refer to them in their
+     descriptions.  */
+  hash_map <const exploded_node *, diagnostic_event_id_t> m_setjmp_event_ids;
+};
+
+#endif /* GCC_ANALYZER_CHECKER_PATH_H */