Initial commit of analyzer

This patch adds a static analysis pass to the middle-end, focusing
for this release on C code, and malloc/free issues in particular.

See:
 https://gcc.gnu.org/wiki/DavidMalcolm/StaticAnalyzer

gcc/ChangeLog:
	* Makefile.in (lang_opt_files): Add analyzer.opt.
	(ANALYZER_OBJS): New.
	(OBJS): Add digraph.o, graphviz.o, ordered-hash-map-tests.o,
	tristate.o and ANALYZER_OBJS.
	(TEXI_GCCINT_FILES): Add analyzer.texi.
	* common.opt (-fanalyzer): New driver option.
	* config.in: Regenerate.
	* configure: Regenerate.
	* configure.ac (--disable-analyzer, ENABLE_ANALYZER): New option.
	(gccdepdir): Also create depdir for "analyzer" subdir.
	* digraph.cc: New file.
	* digraph.h: New file.
	* doc/analyzer.texi: New file.
	* doc/gccint.texi ("Static Analyzer") New menu item.
	(analyzer.texi): Include it.
	* doc/invoke.texi ("Static Analyzer Options"): New list and new section.
	("Warning Options"): Add static analysis warnings to the list.
	(-Wno-analyzer-double-fclose): New option.
	(-Wno-analyzer-double-free): New option.
	(-Wno-analyzer-exposure-through-output-file): New option.
	(-Wno-analyzer-file-leak): New option.
	(-Wno-analyzer-free-of-non-heap): New option.
	(-Wno-analyzer-malloc-leak): New option.
	(-Wno-analyzer-possible-null-argument): New option.
	(-Wno-analyzer-possible-null-dereference): New option.
	(-Wno-analyzer-null-argument): New option.
	(-Wno-analyzer-null-dereference): New option.
	(-Wno-analyzer-stale-setjmp-buffer): New option.
	(-Wno-analyzer-tainted-array-index): New option.
	(-Wno-analyzer-use-after-free): New option.
	(-Wno-analyzer-use-of-pointer-in-stale-stack-frame): New option.
	(-Wno-analyzer-use-of-uninitialized-value): New option.
	(-Wanalyzer-too-complex): New option.
	(-fanalyzer-call-summaries): New warning.
	(-fanalyzer-checker=): New warning.
	(-fanalyzer-fine-grained): New warning.
	(-fno-analyzer-state-merge): New warning.
	(-fno-analyzer-state-purge): New warning.
	(-fanalyzer-transitivity): New warning.
	(-fanalyzer-verbose-edges): New warning.
	(-fanalyzer-verbose-state-changes): New warning.
	(-fanalyzer-verbosity=): New warning.
	(-fdump-analyzer): New warning.
	(-fdump-analyzer-callgraph): New warning.
	(-fdump-analyzer-exploded-graph): New warning.
	(-fdump-analyzer-exploded-nodes): New warning.
	(-fdump-analyzer-exploded-nodes-2): New warning.
	(-fdump-analyzer-exploded-nodes-3): New warning.
	(-fdump-analyzer-supergraph): New warning.
	* doc/sourcebuild.texi (dg-require-dot): New.
	(dg-check-dot): New.
	* gdbinit.in (break-on-saved-diagnostic): New command.
	* graphviz.cc: New file.
	* graphviz.h: New file.
	* ordered-hash-map-tests.cc: New file.
	* ordered-hash-map.h: New file.
	* passes.def (pass_analyzer): Add before
	pass_ipa_whole_program_visibility.
	* selftest-run-tests.c (selftest::run_tests): Call
	selftest::ordered_hash_map_tests_cc_tests.
	* selftest.h (selftest::ordered_hash_map_tests_cc_tests): New
	decl.
	* shortest-paths.h: New file.
	* timevar.def (TV_ANALYZER): New timevar.
	(TV_ANALYZER_SUPERGRAPH): Likewise.
	(TV_ANALYZER_STATE_PURGE): Likewise.
	(TV_ANALYZER_PLAN): Likewise.
	(TV_ANALYZER_SCC): Likewise.
	(TV_ANALYZER_WORKLIST): Likewise.
	(TV_ANALYZER_DUMP): Likewise.
	(TV_ANALYZER_DIAGNOSTICS): Likewise.
	(TV_ANALYZER_SHORTEST_PATHS): Likewise.
	* tree-pass.h (make_pass_analyzer): New decl.
	* tristate.cc: New file.
	* tristate.h: New file.

gcc/analyzer/ChangeLog:
	* ChangeLog: New file.
	* analyzer-selftests.cc: New file.
	* analyzer-selftests.h: New file.
	* analyzer.opt: New file.
	* analysis-plan.cc: New file.
	* analysis-plan.h: New file.
	* analyzer-logging.cc: New file.
	* analyzer-logging.h: New file.
	* analyzer-pass.cc: New file.
	* analyzer.cc: New file.
	* analyzer.h: New file.
	* call-string.cc: New file.
	* call-string.h: New file.
	* checker-path.cc: New file.
	* checker-path.h: New file.
	* constraint-manager.cc: New file.
	* constraint-manager.h: New file.
	* diagnostic-manager.cc: New file.
	* diagnostic-manager.h: New file.
	* engine.cc: New file.
	* engine.h: New file.
	* exploded-graph.h: New file.
	* pending-diagnostic.cc: New file.
	* pending-diagnostic.h: New file.
	* program-point.cc: New file.
	* program-point.h: New file.
	* program-state.cc: New file.
	* program-state.h: New file.
	* region-model.cc: New file.
	* region-model.h: New file.
	* sm-file.cc: New file.
	* sm-malloc.cc: New file.
	* sm-malloc.dot: New file.
	* sm-pattern-test.cc: New file.
	* sm-sensitive.cc: New file.
	* sm-signal.cc: New file.
	* sm-taint.cc: New file.
	* sm.cc: New file.
	* sm.h: New file.
	* state-purge.cc: New file.
	* state-purge.h: New file.
	* supergraph.cc: New file.
	* supergraph.h: New file.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/CVE-2005-1689-minimal.c: New test.
	* gcc.dg/analyzer/abort.c: New test.
	* gcc.dg/analyzer/alloca-leak.c: New test.
	* gcc.dg/analyzer/analyzer-decls.h: New header.
	* gcc.dg/analyzer/analyzer-verbosity-0.c: New test.
	* gcc.dg/analyzer/analyzer-verbosity-1.c: New test.
	* gcc.dg/analyzer/analyzer-verbosity-2.c: New test.
	* gcc.dg/analyzer/analyzer.exp: New suite.
	* gcc.dg/analyzer/attribute-nonnull.c: New test.
	* gcc.dg/analyzer/call-summaries-1.c: New test.
	* gcc.dg/analyzer/conditionals-2.c: New test.
	* gcc.dg/analyzer/conditionals-3.c: New test.
	* gcc.dg/analyzer/conditionals-notrans.c: New test.
	* gcc.dg/analyzer/conditionals-trans.c: New test.
	* gcc.dg/analyzer/data-model-1.c: New test.
	* gcc.dg/analyzer/data-model-2.c: New test.
	* gcc.dg/analyzer/data-model-3.c: New test.
	* gcc.dg/analyzer/data-model-4.c: New test.
	* gcc.dg/analyzer/data-model-5.c: New test.
	* gcc.dg/analyzer/data-model-5b.c: New test.
	* gcc.dg/analyzer/data-model-5c.c: New test.
	* gcc.dg/analyzer/data-model-5d.c: New test.
	* gcc.dg/analyzer/data-model-6.c: New test.
	* gcc.dg/analyzer/data-model-7.c: New test.
	* gcc.dg/analyzer/data-model-8.c: New test.
	* gcc.dg/analyzer/data-model-9.c: New test.
	* gcc.dg/analyzer/data-model-11.c: New test.
	* gcc.dg/analyzer/data-model-12.c: New test.
	* gcc.dg/analyzer/data-model-13.c: New test.
	* gcc.dg/analyzer/data-model-14.c: New test.
	* gcc.dg/analyzer/data-model-15.c: New test.
	* gcc.dg/analyzer/data-model-16.c: New test.
	* gcc.dg/analyzer/data-model-17.c: New test.
	* gcc.dg/analyzer/data-model-18.c: New test.
	* gcc.dg/analyzer/data-model-19.c: New test.
	* gcc.dg/analyzer/data-model-path-1.c: New test.
	* gcc.dg/analyzer/disabling.c: New test.
	* gcc.dg/analyzer/dot-output.c: New test.
	* gcc.dg/analyzer/double-free-lto-1-a.c: New test.
	* gcc.dg/analyzer/double-free-lto-1-b.c: New test.
	* gcc.dg/analyzer/double-free-lto-1.h: New header.
	* gcc.dg/analyzer/equivalence.c: New test.
	* gcc.dg/analyzer/explode-1.c: New test.
	* gcc.dg/analyzer/explode-2.c: New test.
	* gcc.dg/analyzer/factorial.c: New test.
	* gcc.dg/analyzer/fibonacci.c: New test.
	* gcc.dg/analyzer/fields.c: New test.
	* gcc.dg/analyzer/file-1.c: New test.
	* gcc.dg/analyzer/file-2.c: New test.
	* gcc.dg/analyzer/function-ptr-1.c: New test.
	* gcc.dg/analyzer/function-ptr-2.c: New test.
	* gcc.dg/analyzer/function-ptr-3.c: New test.
	* gcc.dg/analyzer/gzio-2.c: New test.
	* gcc.dg/analyzer/gzio-3.c: New test.
	* gcc.dg/analyzer/gzio-3a.c: New test.
	* gcc.dg/analyzer/gzio.c: New test.
	* gcc.dg/analyzer/infinite-recursion.c: New test.
	* gcc.dg/analyzer/loop-2.c: New test.
	* gcc.dg/analyzer/loop-2a.c: New test.
	* gcc.dg/analyzer/loop-3.c: New test.
	* gcc.dg/analyzer/loop-4.c: New test.
	* gcc.dg/analyzer/loop.c: New test.
	* gcc.dg/analyzer/malloc-1.c: New test.
	* gcc.dg/analyzer/malloc-2.c: New test.
	* gcc.dg/analyzer/malloc-3.c: New test.
	* gcc.dg/analyzer/malloc-callbacks.c: New test.
	* gcc.dg/analyzer/malloc-dce.c: New test.
	* gcc.dg/analyzer/malloc-dedupe-1.c: New test.
	* gcc.dg/analyzer/malloc-ipa-1.c: New test.
	* gcc.dg/analyzer/malloc-ipa-10.c: New test.
	* gcc.dg/analyzer/malloc-ipa-11.c: New test.
	* gcc.dg/analyzer/malloc-ipa-12.c: New test.
	* gcc.dg/analyzer/malloc-ipa-13.c: New test.
	* gcc.dg/analyzer/malloc-ipa-2.c: New test.
	* gcc.dg/analyzer/malloc-ipa-3.c: New test.
	* gcc.dg/analyzer/malloc-ipa-4.c: New test.
	* gcc.dg/analyzer/malloc-ipa-5.c: New test.
	* gcc.dg/analyzer/malloc-ipa-6.c: New test.
	* gcc.dg/analyzer/malloc-ipa-7.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-double-free.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-a.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-b.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto-c.c: New test.
	* gcc.dg/analyzer/malloc-ipa-8-lto.h: New test.
	* gcc.dg/analyzer/malloc-ipa-8-unchecked.c: New test.
	* gcc.dg/analyzer/malloc-ipa-9.c: New test.
	* gcc.dg/analyzer/malloc-macro-inline-events.c: New test.
	* gcc.dg/analyzer/malloc-macro-separate-events.c: New test.
	* gcc.dg/analyzer/malloc-macro.h: New header.
	* gcc.dg/analyzer/malloc-many-paths-1.c: New test.
	* gcc.dg/analyzer/malloc-many-paths-2.c: New test.
	* gcc.dg/analyzer/malloc-many-paths-3.c: New test.
	* gcc.dg/analyzer/malloc-paths-1.c: New test.
	* gcc.dg/analyzer/malloc-paths-10.c: New test.
	* gcc.dg/analyzer/malloc-paths-2.c: New test.
	* gcc.dg/analyzer/malloc-paths-3.c: New test.
	* gcc.dg/analyzer/malloc-paths-4.c: New test.
	* gcc.dg/analyzer/malloc-paths-5.c: New test.
	* gcc.dg/analyzer/malloc-paths-6.c: New test.
	* gcc.dg/analyzer/malloc-paths-7.c: New test.
	* gcc.dg/analyzer/malloc-paths-8.c: New test.
	* gcc.dg/analyzer/malloc-paths-9.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-1a.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-1b.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-2.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-3.c: New test.
	* gcc.dg/analyzer/malloc-vs-local-4.c: New test.
	* gcc.dg/analyzer/operations.c: New test.
	* gcc.dg/analyzer/params-2.c: New test.
	* gcc.dg/analyzer/params.c: New test.
	* gcc.dg/analyzer/paths-1.c: New test.
	* gcc.dg/analyzer/paths-1a.c: New test.
	* gcc.dg/analyzer/paths-2.c: New test.
	* gcc.dg/analyzer/paths-3.c: New test.
	* gcc.dg/analyzer/paths-4.c: New test.
	* gcc.dg/analyzer/paths-5.c: New test.
	* gcc.dg/analyzer/paths-6.c: New test.
	* gcc.dg/analyzer/paths-7.c: New test.
	* gcc.dg/analyzer/pattern-test-1.c: New test.
	* gcc.dg/analyzer/pattern-test-2.c: New test.
	* gcc.dg/analyzer/pointer-merging.c: New test.
	* gcc.dg/analyzer/pr61861.c: New test.
	* gcc.dg/analyzer/pragma-1.c: New test.
	* gcc.dg/analyzer/scope-1.c: New test.
	* gcc.dg/analyzer/sensitive-1.c: New test.
	* gcc.dg/analyzer/setjmp-1.c: New test.
	* gcc.dg/analyzer/setjmp-2.c: New test.
	* gcc.dg/analyzer/setjmp-3.c: New test.
	* gcc.dg/analyzer/setjmp-4.c: New test.
	* gcc.dg/analyzer/setjmp-5.c: New test.
	* gcc.dg/analyzer/setjmp-6.c: New test.
	* gcc.dg/analyzer/setjmp-7.c: New test.
	* gcc.dg/analyzer/setjmp-7a.c: New test.
	* gcc.dg/analyzer/setjmp-8.c: New test.
	* gcc.dg/analyzer/setjmp-9.c: New test.
	* gcc.dg/analyzer/signal-1.c: New test.
	* gcc.dg/analyzer/signal-2.c: New test.
	* gcc.dg/analyzer/signal-3.c: New test.
	* gcc.dg/analyzer/signal-4a.c: New test.
	* gcc.dg/analyzer/signal-4b.c: New test.
	* gcc.dg/analyzer/strcmp-1.c: New test.
	* gcc.dg/analyzer/switch.c: New test.
	* gcc.dg/analyzer/taint-1.c: New test.
	* gcc.dg/analyzer/zlib-1.c: New test.
	* gcc.dg/analyzer/zlib-2.c: New test.
	* gcc.dg/analyzer/zlib-3.c: New test.
	* gcc.dg/analyzer/zlib-4.c: New test.
	* gcc.dg/analyzer/zlib-5.c: New test.
	* gcc.dg/analyzer/zlib-6.c: New test.
	* lib/gcc-defs.exp (dg-check-dot): New procedure.
	* lib/target-supports.exp (check_dot_available): New procedure.
	(check_effective_target_analyzer): New.
	* lib/target-supports-dg.exp (dg-require-dot): New procedure.

1 files changed, 554 insertions, 0 deletions

diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
new file mode 100644
index 0000000..e85f1ba
--- /dev/null
+++ b/gcc/analyzer/program-point.cc
@@ -0,0 +1,554 @@
+/* Classes for representing locations within the program.
+   Copyright (C) 2019-2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "gimple-pretty-print.h"
+#include "gcc-rich-location.h"
+#include "analyzer/call-string.h"
+#include "ordered-hash-map.h"
+#include "options.h"
+#include "cgraph.h"
+#include "function.h"
+#include "cfg.h"
+#include "basic-block.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "digraph.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/program-point.h"
+#include "sbitmap.h"
+#include "tristate.h"
+#include "selftest.h"
+#include "analyzer/region-model.h"
+#include "analyzer/sm.h"
+#include "analyzer/program-state.h"
+#include "alloc-pool.h"
+#include "fibonacci_heap.h"
+#include "diagnostic-event-id.h"
+#include "analyzer/pending-diagnostic.h"
+#include "analyzer/diagnostic-manager.h"
+#include "shortest-paths.h"
+#include "analyzer/exploded-graph.h"
+#include "analyzer/analysis-plan.h"
+
+#if ENABLE_ANALYZER
+
+/* Get a string for PK.  */
+
+const char *
+point_kind_to_string (enum point_kind pk)
+{
+  switch (pk)
+    {
+    default:
+      gcc_unreachable ();
+    case PK_ORIGIN:
+      return "PK_ORIGIN";
+    case PK_BEFORE_SUPERNODE:
+      return "PK_BEFORE_SUPERNODE";
+    case PK_BEFORE_STMT:
+      return "PK_BEFORE_STMT";
+    case PK_AFTER_SUPERNODE:
+      return "PK_AFTER_SUPERNODE";
+    case PK_EMPTY:
+      return "PK_EMPTY";
+    case PK_DELETED:
+      return "PK_DELETED";
+    }
+}
+
+/* class function_point.  */
+
+/* Print this function_point to PP.  */
+
+void
+function_point::print (pretty_printer *pp, const format &f) const
+{
+  switch (get_kind ())
+    {
+    default:
+      gcc_unreachable ();
+
+    case PK_ORIGIN:
+      pp_printf (pp, "origin");
+      break;
+
+    case PK_BEFORE_SUPERNODE:
+      {
+	if (m_from_edge)
+	  pp_printf (pp, "before SN: %i (from SN: %i)",
+		     m_supernode->m_index, m_from_edge->m_src->m_index);
+	else
+	  pp_printf (pp, "before SN: %i (NULL from-edge)",
+		     m_supernode->m_index);
+	f.spacer (pp);
+	for (gphi_iterator gpi
+	       = const_cast<supernode *>(get_supernode ())->start_phis ();
+	     !gsi_end_p (gpi); gsi_next (&gpi))
+	  {
+	    const gphi *phi = gpi.phi ();
+	    pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
+	  }
+      }
+      break;
+
+    case PK_BEFORE_STMT:
+      pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
+		 m_stmt_idx);
+      f.spacer (pp);
+      pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
+      if (f.m_newlines)
+	{
+	  pp_newline (pp);
+	  print_source_line (pp);
+	}
+      break;
+
+    case PK_AFTER_SUPERNODE:
+      pp_printf (pp, "after SN: %i", m_supernode->m_index);
+      break;
+    }
+}
+
+/* Generate a hash value for this function_point.  */
+
+hashval_t
+function_point::hash () const
+{
+  inchash::hash hstate;
+  if (m_supernode)
+    hstate.add_int (m_supernode->m_index);
+  hstate.add_ptr (m_from_edge);
+  hstate.add_int (m_stmt_idx);
+  hstate.add_int (m_kind);
+  return hstate.end ();
+}
+
+/* Get the gimple stmt for this function_point, if any.  */
+
+const gimple *
+function_point::get_stmt () const
+{
+  if (m_kind == PK_BEFORE_STMT)
+    return m_supernode->m_stmts[m_stmt_idx];
+  else if (m_kind == PK_AFTER_SUPERNODE)
+    return m_supernode->get_last_stmt ();
+  else
+    return NULL;
+}
+
+/* Get a location for this function_point, if any.  */
+
+location_t
+function_point::get_location () const
+{
+  const gimple *stmt = get_stmt ();
+  if (stmt)
+    return stmt->location;
+
+  return UNKNOWN_LOCATION;
+}
+
+/* A subclass of diagnostic_context for use by
+   program_point::print_source_line.  */
+
+class debug_diagnostic_context : public diagnostic_context
+{
+public:
+  debug_diagnostic_context ()
+  {
+    diagnostic_initialize (this, 0);
+    show_line_numbers_p = true;
+    show_caret = true;
+  }
+  ~debug_diagnostic_context ()
+  {
+    diagnostic_finish (this);
+  }
+};
+
+/* Print the source line (if any) for this function_point to PP.  */
+
+void
+function_point::print_source_line (pretty_printer *pp) const
+{
+  const gimple *stmt = get_stmt ();
+  if (!stmt)
+    return;
+  // TODO: monospace font
+  debug_diagnostic_context tmp_dc;
+  gcc_rich_location richloc (stmt->location);
+  diagnostic_show_locus (&tmp_dc, &richloc, DK_ERROR);
+  pp_string (pp, pp_formatted_text (tmp_dc.printer));
+}
+
+/* class program_point.  */
+
+/* Print this program_point to PP.  */
+
+void
+program_point::print (pretty_printer *pp, const format &f) const
+{
+  pp_string (pp, "callstring: ");
+  m_call_string.print (pp);
+  f.spacer (pp);
+
+  m_function_point.print (pp, f);
+}
+
+/* Dump this point to stderr.  */
+
+DEBUG_FUNCTION void
+program_point::dump () const
+{
+  pretty_printer pp;
+  pp_show_color (&pp) = pp_show_color (global_dc->printer);
+  pp.buffer->stream = stderr;
+  print (&pp, format (true));
+  pp_flush (&pp);
+}
+
+/* Generate a hash value for this program_point.  */
+
+hashval_t
+program_point::hash () const
+{
+  inchash::hash hstate;
+  hstate.merge_hash (m_function_point.hash ());
+  hstate.merge_hash (m_call_string.hash ());
+  return hstate.end ();
+}
+
+/* Get the function * at DEPTH within the call stack.  */
+
+function *
+program_point::get_function_at_depth (unsigned depth) const
+{
+  gcc_assert (depth <= m_call_string.length ());
+  if (depth == m_call_string.length ())
+    return m_function_point.get_function ();
+  else
+    return m_call_string[depth]->get_caller_function ();
+}
+
+/* Assert that this object is sane.  */
+
+void
+program_point::validate () const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  m_call_string.validate ();
+  /* The "callee" of the final entry in the callstring should be the
+     function of the m_function_point.  */
+  if (m_call_string.length () > 0)
+    gcc_assert (m_call_string[m_call_string.length () - 1]->get_callee_function ()
+		== get_function ());
+}
+
+/* Check to see if SUCC is a valid edge to take (ensuring that we have
+   interprocedurally valid paths in the exploded graph, and enforcing
+   recursion limits).
+
+   Update the call string if SUCC is a call or a return.
+
+   Return true if SUCC can be taken, or false otherwise.
+
+   This is the "point" half of exploded_node::on_edge.  */
+
+bool
+program_point::on_edge (exploded_graph &eg,
+			const superedge *succ)
+{
+  logger * const logger = eg.get_logger ();
+  LOG_FUNC (logger);
+  switch (succ->m_kind)
+    {
+    case SUPEREDGE_CFG_EDGE:
+      {
+	const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);
+
+	/* Reject abnormal edges; we special-case setjmp/longjmp.  */
+	if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
+	  return false;
+      }
+      break;
+
+    case SUPEREDGE_CALL:
+      {
+	const call_superedge *call_sedge = as_a <const call_superedge *> (succ);
+
+	if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
+	  {
+	    if (logger)
+	      logger->log ("rejecting call edge: using summary instead");
+	    return false;
+	  }
+
+	/* Add the callsite to the call string.  */
+	m_call_string.push_call (eg.get_supergraph (), call_sedge);
+
+	/* Impose a maximum recursion depth and don't analyze paths
+	   that exceed it further.
+	   This is something of a blunt workaround, but it only
+	   applies to recursion (and mutual recursion), not to
+	   general call stacks.  */
+	if (m_call_string.calc_recursion_depth ()
+	    > param_analyzer_max_recursion_depth)
+	  {
+	    if (logger)
+	      logger->log ("rejecting call edge: recursion limit exceeded");
+	    // TODO: issue a sorry for this?
+	    return false;
+	  }
+      }
+      break;
+
+    case SUPEREDGE_RETURN:
+      {
+	/* Require that we return to the call site in the call string.  */
+	if (m_call_string.empty_p ())
+	  {
+	    if (logger)
+	      logger->log ("rejecting return edge: empty call string");
+	    return false;
+	  }
+	const return_superedge *top_of_stack = m_call_string.pop ();
+	if (top_of_stack != succ)
+	  {
+	    if (logger)
+	      logger->log ("rejecting return edge: return to wrong callsite");
+	    return false;
+	  }
+      }
+      break;
+
+    case SUPEREDGE_INTRAPROCEDURAL_CALL:
+      {
+	const callgraph_superedge *cg_sedge
+	  = as_a <const callgraph_superedge *> (succ);
+	/* Consider turning this edge into a use of an
+	   interprocedural summary.  */
+	if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
+	  {
+	    if (logger)
+	      logger->log ("using function summary for %qE in %qE",
+			   cg_sedge->get_callee_decl (),
+			   cg_sedge->get_caller_decl ());
+	    return true;
+	  }
+	else
+	  {
+	    /* Otherwise, we ignore these edges  */
+	    if (logger)
+	      logger->log ("rejecting interprocedural edge");
+	    return false;
+	  }
+      }
+    }
+
+  return true;
+}
+
+/* Comparator for program points within the same supernode,
+   for implementing worklist::key_t comparison operators.
+   Return negative if POINT_A is before POINT_B
+   Return positive if POINT_A is after POINT_B
+   Return 0 if they are equal.  */
+
+int
+function_point::cmp_within_supernode_1 (const function_point &point_a,
+					const function_point &point_b)
+{
+  gcc_assert (point_a.get_supernode () == point_b.get_supernode ());
+
+  switch (point_a.m_kind)
+    {
+    default:
+      gcc_unreachable ();
+    case PK_BEFORE_SUPERNODE:
+      switch (point_b.m_kind)
+	{
+	default:
+	  gcc_unreachable ();
+	case PK_BEFORE_SUPERNODE:
+	  {
+	    int a_src_idx = -1;
+	    int b_src_idx = -1;
+	    if (point_a.m_from_edge)
+	      a_src_idx = point_a.m_from_edge->m_src->m_index;
+	    if (point_b.m_from_edge)
+	      b_src_idx = point_b.m_from_edge->m_src->m_index;
+	    return a_src_idx - b_src_idx;
+	  }
+	  break;
+
+	case PK_BEFORE_STMT:
+	case PK_AFTER_SUPERNODE:
+	  return -1;
+	}
+      break;
+    case PK_BEFORE_STMT:
+      switch (point_b.m_kind)
+	{
+	default:
+	  gcc_unreachable ();
+	case PK_BEFORE_SUPERNODE:
+	  return 1;
+
+	case PK_BEFORE_STMT:
+	  return point_a.m_stmt_idx - point_b.m_stmt_idx;
+
+	case PK_AFTER_SUPERNODE:
+	  return -1;
+	}
+      break;
+    case PK_AFTER_SUPERNODE:
+      switch (point_b.m_kind)
+	{
+	default:
+	  gcc_unreachable ();
+	case PK_BEFORE_SUPERNODE:
+	case PK_BEFORE_STMT:
+	  return 1;
+
+	case PK_AFTER_SUPERNODE:
+	  return 0;
+	}
+      break;
+    }
+}
+
+/* Comparator for program points within the same supernode,
+   for implementing worklist::key_t comparison operators.
+   Return negative if POINT_A is before POINT_B
+   Return positive if POINT_A is after POINT_B
+   Return 0 if they are equal.  */
+
+int
+function_point::cmp_within_supernode (const function_point &point_a,
+				      const function_point &point_b)
+{
+  int result = cmp_within_supernode_1 (point_a, point_b);
+
+  /* Check that the ordering is symmetric  */
+#if CHECKING_P
+  int reversed = cmp_within_supernode_1 (point_b, point_a);
+  gcc_assert (reversed == -result);
+#endif
+
+  return result;
+}
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Verify that function_point::operator== works as expected.  */
+
+static void
+test_function_point_equality ()
+{
+  const supernode *snode = NULL;
+
+  function_point a = function_point (snode, NULL, 0,
+				     PK_BEFORE_SUPERNODE);
+  function_point b = function_point::before_supernode (snode, NULL);
+  ASSERT_EQ (a, b);
+}
+
+/* Verify that function_point::cmp_within_supernode works as expected.  */
+
+static void
+test_function_point_ordering ()
+{
+  const supernode *snode = NULL;
+  const call_string call_string;
+
+  /* Populate an array with various points within the same
+     snode, in order.  */
+  auto_vec<function_point> points;
+  points.safe_push (function_point::before_supernode (snode, NULL));
+  points.safe_push (function_point::before_stmt (snode, 0));
+  points.safe_push (function_point::before_stmt (snode, 1));
+  points.safe_push (function_point::after_supernode (snode));
+
+  /* Check all pairs.  */
+  unsigned i;
+  function_point *point_a;
+  FOR_EACH_VEC_ELT (points, i, point_a)
+    {
+      unsigned j;
+      function_point *point_b;
+      FOR_EACH_VEC_ELT (points, j, point_b)
+	{
+	  int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
+	  if (i == j)
+	    ASSERT_EQ (cmp, 0);
+	  if (i < j)
+	    ASSERT_TRUE (cmp < 0);
+	  if (i > j)
+	    ASSERT_TRUE (cmp > 0);
+	}
+    }
+}
+
+/* Verify that program_point::operator== works as expected.  */
+
+static void
+test_program_point_equality ()
+{
+  const supernode *snode = NULL;
+
+  const call_string cs;
+
+  program_point a = program_point::before_supernode (snode, NULL,
+						     cs);
+
+  program_point b = program_point::before_supernode (snode, NULL,
+						     cs);
+
+  ASSERT_EQ (a, b);
+  // TODO: verify with non-empty callstrings, with different edges
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+analyzer_program_point_cc_tests ()
+{
+  test_function_point_equality ();
+  test_function_point_ordering ();
+  test_program_point_equality ();
+}
+
+} // namespace selftest
+
+#endif /* CHECKING_P */
+
+#endif /* #if ENABLE_ANALYZER */