analyzer: eliminate irrelevant control-flow edges from paths

Paths emitted by the analyzer can be quite verbose at the default of
-fanalyzer-verbosity=2.

Consider the double-free in this example:

  #include <stdlib.h>

  int foo ();
  int bar ();

  void test (int a, int b, int c)
  {
    void *p = malloc (1024);
    while (a)
      foo ();
    if (b)
      foo ();
    else
      bar ();
    if (c)
      free (p);
    free (p);
  }

Previously, the analyzer would emit a checker_path containing all
control-flow information on the exploded_path leading to the
double-free:

  test.c: In function 'test':
  test.c:17:3: warning: double-'free' of 'p' [CWE-415] [-Wanalyzer-double-free]
     17 |   free (p);
        |   ^~~~~~~~
    'test': events 1-9
      |
      |    8 |   void *p = malloc (1024);
      |      |             ^~~~~~~~~~~~~
      |      |             |
      |      |             (1) allocated here
      |    9 |   while (a)
      |      |         ~
      |      |         |
      |      |         (2) following 'false' branch (when 'a == 0')...
      |   10 |     foo ();
      |   11 |   if (b)
      |      |      ~
      |      |      |
      |      |      (3) ...to here
      |      |      (4) following 'false' branch (when 'b == 0')...
      |......
      |   14 |     bar ();
      |      |     ~~~~~~
      |      |     |
      |      |     (5) ...to here
      |   15 |   if (c)
      |      |      ~
      |      |      |
      |      |      (6) following 'true' branch (when 'c != 0')...
      |   16 |     free (p);
      |      |     ~~~~~~~~
      |      |     |
      |      |     (7) ...to here
      |      |     (8) first 'free' here
      |   17 |   free (p);
      |      |   ~~~~~~~~
      |      |   |
      |      |   (9) second 'free' here; first 'free' was at (8)
      |

despite the fact that only the "if (c)" is relevant to triggering the
double-free.

This patch implements pruning of control flow events at
-fanalyzer-verbosity=2, based on reachability information within the
exploded_graph.
The diagnostic_manager pre-computes reachability information about
which exploded_nodes can reach the exploded_node of the diagnostic,
and uses this to prune irrelvent control flow edges.

The patch also adds a -fanalyzer-verbosity=3 to preserve these edges,
so that the "show me everything" debugging level becomes
-fanalyzer-verbosity=4.

With these changes, the "while (a)" and "if (b)" edges are pruned from
the above example, leading to:

  test.c: In function 'test':
  test.c:17:3: warning: double-'free' of 'p' [CWE-415] [-Wanalyzer-double-free]
     17 |   free (p);
        |   ^~~~~~~~
    'test': events 1-5
      |
      |    8 |   void *p = malloc (1024);
      |      |             ^~~~~~~~~~~~~
      |      |             |
      |      |             (1) allocated here
      |......
      |   15 |   if (c)
      |      |      ~
      |      |      |
      |      |      (2) following 'true' branch (when 'c != 0')...
      |   16 |     free (p);
      |      |     ~~~~~~~~
      |      |     |
      |      |     (3) ...to here
      |      |     (4) first 'free' here
      |   17 |   free (p);
      |      |   ~~~~~~~~
      |      |   |
      |      |   (5) second 'free' here; first 'free' was at (4)
      |

The above example is gcc.dg/analyzer/edges-2.c.

gcc/analyzer/ChangeLog:
	* checker-path.cc (superedge_event::should_filter_p): Update
	filter for empty descriptions to cover verbosity level 3 as well
	as 2.
	* diagnostic-manager.cc: Include "analyzer/reachability.h".
	(class path_builder): New class.
	(diagnostic_manager::emit_saved_diagnostic): Create a path_builder
	and pass it to build_emission_path, rather passing eg; similarly
	for add_events_for_eedge and ext_state.
	(diagnostic_manager::build_emission_path): Replace "eg" param
	with a path_builder, pass it to add_events_for_eedge.
	(diagnostic_manager::add_events_for_eedge): Replace ext_state
	param with path_builder; pass it to add_events_for_superedge.
	(diagnostic_manager::significant_edge_p): New.
	(diagnostic_manager::add_events_for_superedge): Add path_builder
	param.  Reject insignificant edges at verbosity levels below 3.
	(diagnostic_manager::prune_for_sm_diagnostic): Update highest
	verbosity level to 4.
	* diagnostic-manager.h (class path_builder): New forward decl.
	(diagnostic_manager::build_emission_path): Replace "eg" param
	with a path_builder.
	(diagnostic_manager::add_events_for_eedge): Replace ext_state
	param with path_builder.
	(diagnostic_manager::significant_edge_p): New.
	(diagnostic_manager::add_events_for_superedge): Add path_builder
	param.
	* reachability.h: New file.

gcc/ChangeLog:
	* doc/invoke.texi (-fanalyzer-verbosity=): "2" only shows
	significant control flow events; add a "3" which shows all
	control flow events; the old "3" becomes "4".

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/analyzer-verbosity-2a.c: New test.
	* gcc.dg/analyzer/analyzer-verbosity-3.c: New test, based on
	analyzer-verbosity-2.c
	* gcc.dg/analyzer/analyzer-verbosity-3a.c: New test.
	* gcc.dg/analyzer/edges-1.c: New test.
	* gcc.dg/analyzer/edges-2.c: New test.
	* gcc.dg/analyzer/file-paths-1.c: Add -fanalyzer-verbosity=3.

14 files changed, 607 insertions, 21 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e974410..2049bf5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2020-02-24  David Malcolm  <dmalcolm@redhat.com>
+
+	* doc/invoke.texi (-fanalyzer-verbosity=): "2" only shows
+	significant control flow events; add a "3" which shows all
+	control flow events; the old "3" becomes "4".
+
 2020-02-24  Jakub Jelinek  <jakub@redhat.com>
 
 	PR tree-optimization/93582
diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index d7db6ab..bc70e88 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,3 +1,32 @@
+2020-02-24  David Malcolm  <dmalcolm@redhat.com>
+
+	* checker-path.cc (superedge_event::should_filter_p): Update
+	filter for empty descriptions to cover verbosity level 3 as well
+	as 2.
+	* diagnostic-manager.cc: Include "analyzer/reachability.h".
+	(class path_builder): New class.
+	(diagnostic_manager::emit_saved_diagnostic): Create a path_builder
+	and pass it to build_emission_path, rather passing eg; similarly
+	for add_events_for_eedge and ext_state.
+	(diagnostic_manager::build_emission_path): Replace "eg" param
+	with a path_builder, pass it to add_events_for_eedge.
+	(diagnostic_manager::add_events_for_eedge): Replace ext_state
+	param with path_builder; pass it to add_events_for_superedge.
+	(diagnostic_manager::significant_edge_p): New.
+	(diagnostic_manager::add_events_for_superedge): Add path_builder
+	param.  Reject insignificant edges at verbosity levels below 3.
+	(diagnostic_manager::prune_for_sm_diagnostic): Update highest
+	verbosity level to 4.
+	* diagnostic-manager.h (class path_builder): New forward decl.
+	(diagnostic_manager::build_emission_path): Replace "eg" param
+	with a path_builder.
+	(diagnostic_manager::add_events_for_eedge): Replace ext_state
+	param with path_builder.
+	(diagnostic_manager::significant_edge_p): New.
+	(diagnostic_manager::add_events_for_superedge): Add path_builder
+	param.
+	* reachability.h: New file.
+
 2020-02-18  David Malcolm  <dmalcolm@redhat.com>
 
 	PR analyzer/93692
diff --git a/gcc/analyzer/checker-path.cc b/gcc/analyzer/checker-path.cc
index 7f6cdf5..c781cd8 100644
--- a/gcc/analyzer/checker-path.cc
+++ b/gcc/analyzer/checker-path.cc
@@ -334,7 +334,7 @@ superedge_event::should_filter_p (int verbosity) const
 	if (verbosity < 2)
 	  return true;
 
-	if (verbosity == 2)
+	if (verbosity < 4)
 	  {
 	    /* Filter events with empty descriptions.  This ought to filter
 	       FALLTHRU, but retain true/false/switch edges.  */
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index 5801525..78c5890 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -55,6 +55,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "analyzer/program-state.h"
 #include "analyzer/exploded-graph.h"
 #include "analyzer/checker-path.h"
+#include "analyzer/reachability.h"
 
 #if ENABLE_ANALYZER
 
@@ -107,6 +108,41 @@ saved_diagnostic::operator== (const saved_diagnostic &other) const
 	  && m_trailing_eedge == other.m_trailing_eedge);
 }
 
+/* State for building a checker_path from a particular exploded_path.
+   In particular, this precomputes reachability information: the set of
+   source enodes for which a a path be found to the diagnostic enode.  */
+
+class path_builder
+{
+public:
+  path_builder (const exploded_graph &eg,
+		const exploded_path &epath)
+  : m_eg (eg),
+    m_diag_enode (epath.get_final_enode ()),
+    m_reachability (eg, m_diag_enode)
+  {}
+
+  const exploded_node *get_diag_node () const { return m_diag_enode; }
+
+  bool reachable_from_p (const exploded_node *src_enode) const
+  {
+    return m_reachability.reachable_from_p (src_enode);
+  }
+
+  const extrinsic_state &get_ext_state () const { return m_eg.get_ext_state (); }
+
+private:
+  typedef reachability<eg_traits> enode_reachability;
+
+  const exploded_graph &m_eg;
+
+  /* The enode where the diagnostic occurs.  */
+  const exploded_node *m_diag_enode;
+
+  /* Precompute all enodes from which the diagnostic is reachable.  */
+  enode_reachability m_reachability;
+};
+
 /* class diagnostic_manager.  */
 
 /* diagnostic_manager's ctor.  */
@@ -470,10 +506,15 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
 
   pretty_printer *pp = global_dc->printer->clone ();
 
+  /* Precompute all enodes from which the diagnostic is reachable.  */
+  path_builder pb (eg, epath);
+
+  /* This is the diagnostic_path subclass that will be built for
+     the diagnostic.  */
   checker_path emission_path;
 
   /* Populate emission_path with a full description of EPATH.  */
-  build_emission_path (eg, epath, &emission_path);
+  build_emission_path (pb, epath, &emission_path);
 
   /* Now prune it to just cover the most pertinent events.  */
   prune_path (&emission_path, sd.m_sm, sd.m_var, sd.m_state);
@@ -489,8 +530,7 @@ diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
      trailing eedge stashed, add any events for it.  This is for use
      in handling longjmp, to show where a longjmp is rewinding to.  */
   if (sd.m_trailing_eedge)
-    add_events_for_eedge (*sd.m_trailing_eedge, eg.get_ext_state (),
-			  &emission_path);
+    add_events_for_eedge (pb, *sd.m_trailing_eedge, &emission_path);
 
   emission_path.prepare_for_emission (sd.m_d);
 
@@ -558,16 +598,15 @@ get_any_origin (const gimple *stmt,
    EPATH within EG.  */
 
 void
-diagnostic_manager::build_emission_path (const exploded_graph &eg,
+diagnostic_manager::build_emission_path (const path_builder &pb,
 					 const exploded_path &epath,
 					 checker_path *emission_path) const
 {
   LOG_SCOPE (get_logger ());
-  const extrinsic_state &ext_state = eg.get_ext_state ();
   for (unsigned i = 0; i < epath.m_edges.length (); i++)
     {
       const exploded_edge *eedge = epath.m_edges[i];
-      add_events_for_eedge (*eedge, ext_state, emission_path);
+      add_events_for_eedge (pb, *eedge, emission_path);
     }
 }
 
@@ -746,8 +785,8 @@ for_each_state_change (const program_state &src_state,
    Add any events for EEDGE to EMISSION_PATH.  */
 
 void
-diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
-					  const extrinsic_state &ext_state,
+diagnostic_manager::add_events_for_eedge (const path_builder &pb,
+					  const exploded_edge &eedge,
 					  checker_path *emission_path) const
 {
   const exploded_node *src_node = eedge.m_src;
@@ -786,7 +825,7 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
       |              |
       |              (3) ...to here        (end_cfg_edge_event).  */
   state_change_event_creator visitor (eedge, emission_path);
-  for_each_state_change (src_state, dst_state, ext_state,
+  for_each_state_change (src_state, dst_state, pb.get_ext_state (),
 			 &visitor);
 
   /* Allow non-standard edges to add events, e.g. when rewinding from
@@ -803,7 +842,7 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
       if (src_point.get_kind () == PK_AFTER_SUPERNODE)
 	{
 	  if (eedge.m_sedge)
-	    add_events_for_superedge (eedge, emission_path);
+	    add_events_for_superedge (pb, eedge, emission_path);
 	}
       /* Add function entry events.  */
       if (dst_point.get_supernode ()->entry_p ())
@@ -836,18 +875,95 @@ diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
     }
 }
 
+/* Return true if EEDGE is a significant edge in the path to the diagnostic
+   for PB.
+
+   Consider all of the sibling out-eedges from the same source enode
+   as EEDGE.
+   If there's no path from the destinations of those eedges to the
+   diagnostic enode, then we have to take this eedge and thus it's
+   significant.
+
+   Conversely if there is a path from the destination of any other sibling
+   eedge to the diagnostic enode, then this edge is insignificant.
+
+   Example 1: redundant if-else:
+
+     (A) if (...)            A
+     (B)   ...              / \
+         else              B   C
+     (C)   ...              \ /
+     (D) [DIAGNOSTIC]        D
+
+     D is reachable by either B or C, so neither of these edges
+     are significant.
+
+   Example 2: pertinent if-else:
+
+     (A) if (...)                         A
+     (B)   ...                           / \
+         else                           B   C
+     (C)   [NECESSARY CONDITION]        |   |
+     (D) [POSSIBLE DIAGNOSTIC]          D1  D2
+
+     D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
+     at D2.  D2 is only reachable via C, so the A -> C edge is significant.
+
+   Example 3: redundant loop:
+
+     (A) while (...)          +-->A
+     (B)   ...                |  / \
+     (C) ...                  +-B  C
+     (D) [DIAGNOSTIC]              |
+                                   D
+
+     D is reachable from both B and C, so the A->C edge is not significant.  */
+
+bool
+diagnostic_manager::significant_edge_p (const path_builder &pb,
+					const exploded_edge &eedge) const
+{
+  int i;
+  exploded_edge *sibling;
+  FOR_EACH_VEC_ELT (eedge.m_src->m_succs, i, sibling)
+    {
+      if (sibling == &eedge)
+	continue;
+      if (pb.reachable_from_p (sibling->m_dest))
+	{
+	  if (get_logger ())
+	    get_logger ()->log ("  edge EN: %i -> EN: %i is insignificant as"
+				" EN: %i is also reachable via"
+				" EN: %i -> EN: %i",
+				eedge.m_src->m_index, eedge.m_dest->m_index,
+				pb.get_diag_node ()->m_index,
+				sibling->m_src->m_index,
+				sibling->m_dest->m_index);
+	  return false;
+	}
+    }
+
+  return true;
+}
+
 /* Subroutine of diagnostic_manager::add_events_for_eedge
    where EEDGE has an underlying superedge i.e. a CFG edge,
    or an interprocedural call/return.
    Add any events for the superedge to EMISSION_PATH.  */
 
 void
-diagnostic_manager::add_events_for_superedge (const exploded_edge &eedge,
+diagnostic_manager::add_events_for_superedge (const path_builder &pb,
+					      const exploded_edge &eedge,
 					      checker_path *emission_path)
   const
 {
   gcc_assert (eedge.m_sedge);
 
+  /* Don't add events for insignificant edges at verbosity levels below 3.  */
+  if (m_verbosity < 3)
+    if (!significant_edge_p (pb, eedge))
+      return;
+
   const exploded_node *src_node = eedge.m_src;
   const program_point &src_point = src_node->get_point ();
   const exploded_node *dst_node = eedge.m_dest;
@@ -995,7 +1111,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
 	  gcc_unreachable ();
 
 	case EK_DEBUG:
-	  if (m_verbosity < 3)
+	  if (m_verbosity < 4)
 	    {
 	      log ("filtering event %i: debug event", idx);
 	      path->delete_event (idx);
@@ -1021,7 +1137,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
 		    var = new_var;
 		  }
 	      }
-	    if (m_verbosity < 3)
+	    if (m_verbosity < 4)
 	      {
 		log ("filtering event %i: statement event", idx);
 		path->delete_event (idx);
@@ -1054,7 +1170,7 @@ diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
 		     sm->get_state_name (state_change->m_from));
 		state = state_change->m_from;
 	      }
-	    else if (m_verbosity < 3)
+	    else if (m_verbosity < 4)
 	      {
 		if (var)
 		  log ("filtering event %i:"
diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h
index 171d279..f32ca75 100644
--- a/gcc/analyzer/diagnostic-manager.h
+++ b/gcc/analyzer/diagnostic-manager.h
@@ -53,6 +53,8 @@ private:
   DISABLE_COPY_AND_ASSIGN (saved_diagnostic);
 };
 
+class path_builder;
+
 /* A class with responsibility for saving pending diagnostics, so that
    they can be emitted after the exploded_graph is complete.
    This lets us de-duplicate diagnostics, and find the shortest path
@@ -101,15 +103,19 @@ public:
   }
 
 private:
-  void build_emission_path (const exploded_graph &eg,
+  void build_emission_path (const path_builder &pb,
 			    const exploded_path &epath,
 			    checker_path *emission_path) const;
 
-  void add_events_for_eedge (const exploded_edge &eedge,
-			     const extrinsic_state &ext_state,
+  void add_events_for_eedge (const path_builder &pb,
+			     const exploded_edge &eedge,
 			     checker_path *emission_path) const;
 
-  void add_events_for_superedge (const exploded_edge &eedge,
+  bool significant_edge_p (const path_builder &pb,
+			   const exploded_edge &eedge) const;
+
+  void add_events_for_superedge (const path_builder &pb,
+				 const exploded_edge &eedge,
 				 checker_path *emission_path) const;
 
   void prune_path (checker_path *path,
diff --git a/gcc/analyzer/reachability.h b/gcc/analyzer/reachability.h
new file mode 100644
index 0000000..445cc7d
--- /dev/null
+++ b/gcc/analyzer/reachability.h
@@ -0,0 +1,76 @@
+/* Digraph reachability.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_REACHABILITY_H
+#define GCC_ANALYZER_REACHABILITY_H
+
+namespace ana {
+
+/* The set of nodes from which a target node in a digraph can be reached.  */
+// TODO(stage1): move to gcc
+
+template <typename GraphTraits>
+class reachability
+{
+public:
+  typedef typename GraphTraits::graph_t graph_t;
+  typedef typename GraphTraits::node_t node_t;
+  typedef typename GraphTraits::edge_t edge_t;
+
+  reachability (const graph_t &graph,
+		const node_t *target_node)
+  : m_indices (graph.m_nodes.length ())
+  {
+    bitmap_clear (m_indices);
+    auto_vec<const node_t *> worklist;
+    worklist.safe_push (target_node);
+    bitmap_set_bit (m_indices, target_node->m_index);
+
+    while (worklist.length () > 0)
+      {
+	const node_t *next = worklist.pop ();
+	unsigned i;
+	edge_t *pred;
+	FOR_EACH_VEC_ELT (next->m_preds, i, pred)
+	  {
+	    if (!reachable_from_p (pred->m_src))
+	      {
+		worklist.safe_push (pred->m_src);
+		bitmap_set_bit (m_indices, pred->m_src->m_index);
+	      }
+	  }
+      }
+  }
+
+  bool reachable_from_p (const node_t *src_node) const
+  {
+    return bitmap_bit_p (m_indices, src_node->m_index);
+  }
+
+private:
+  /* The nodes that can reach the target.  */
+  auto_sbitmap m_indices;
+};
+
+//TODO: selftests for reachability
+
+} // namespace ana
+
+#endif /* GCC_ANALYZER_REACHABILITY_H */
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index d4fe9a4..183c256 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -8506,12 +8506,17 @@ As per the previous level, but also show events for the entry
 to each function.
 
 @item 2
-As per the previous level, but also show  events relating to
-control flow (e.g. ``true path taken'' at a conditional).
+As per the previous level, but also show events relating to
+control flow that are significant to triggering the issue
+(e.g. ``true path taken'' at a conditional).
 
 This level is the default.
 
 @item 3
+As per the previous level, but show all control flow events, not
+just significant ones.
+
+@item 4
 This level is intended for analyzer developers; it adds various
 other events intended for debugging the analyzer.
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 59cedcf..6d5abbb 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,13 @@
+2020-02-24  David Malcolm  <dmalcolm@redhat.com>
+
+	* gcc.dg/analyzer/analyzer-verbosity-2a.c: New test.
+	* gcc.dg/analyzer/analyzer-verbosity-3.c: New test, based on
+	analyzer-verbosity-2.c
+	* gcc.dg/analyzer/analyzer-verbosity-3a.c: New test.
+	* gcc.dg/analyzer/edges-1.c: New test.
+	* gcc.dg/analyzer/edges-2.c: New test.
+	* gcc.dg/analyzer/file-paths-1.c: Add -fanalyzer-verbosity=3.
+
 2020-02-24  Marek Polacek  <polacek@redhat.com>
 
 	PR c++/93869 - ICE with -Wmismatched-tags.
diff --git a/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-2a.c b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-2a.c
new file mode 100644
index 0000000..9faf5da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-2a.c
@@ -0,0 +1,20 @@
+/* { dg-additional-options "-fanalyzer-verbosity=2" } */
+
+#include <stdio.h>
+
+extern int foo ();
+extern void bar ();
+
+void test (const char *path, int flag)
+{
+  FILE *fp = fopen (path, "r"); /* { dg-message "opened here" } */
+
+  /* We shouldn't report this control flow at -fanalyzer-verbosity=2.  */
+  if (foo ()) /* { dg-bogus "" } */
+    bar ();
+  else
+    bar ();
+
+  if (flag) /* { dg-message "when 'flag == 0'" } */
+    fclose (fp); 
+} /* { dg-warning "leak of FILE 'fp'" } */
diff --git a/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3.c b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3.c
new file mode 100644
index 0000000..fb87d16
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3.c
@@ -0,0 +1,222 @@
+/* { dg-additional-options "-fdiagnostics-show-line-numbers -fdiagnostics-path-format=inline-events -fdiagnostics-show-caret -fanalyzer-verbosity=3" } */
+/* { dg-enable-nn-line-numbers "" } */
+
+#include <stdlib.h>
+
+void calls_free_1 (void *ptr)
+{
+  free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */
+}
+
+void test_1 (void *ptr, int a, int b)
+{
+  if (a)
+    calls_free_1 (ptr);
+
+  if (b)
+    {
+    }
+  else
+    calls_free_1 (ptr);
+}
+
+/* { dg-begin-multiline-output "" }
+   NN |   free (ptr);
+      |   ^~~~~~~~~~
+  'test_1': events 1-4
+    |
+    |   NN | void test_1 (void *ptr, int a, int b)
+    |      |      ^~~~~~
+    |      |      |
+    |      |      (1) entry to 'test_1'
+    |   NN | {
+    |   NN |   if (a)
+    |      |      ~
+    |      |      |
+    |      |      (2) following 'true' branch (when 'a != 0')...
+    |   NN |     calls_free_1 (ptr);
+    |      |     ~~~~~~~~~~~~~~~~~~
+    |      |     |
+    |      |     (3) ...to here
+    |      |     (4) calling 'calls_free_1' from 'test_1'
+    |
+    +--> 'calls_free_1': events 5-6
+           |
+           |   NN | void calls_free_1 (void *ptr)
+           |      |      ^~~~~~~~~~~~
+           |      |      |
+           |      |      (5) entry to 'calls_free_1'
+           |   NN | {
+           |   NN |   free (ptr);
+           |      |   ~~~~~~~~~~
+           |      |   |
+           |      |   (6) first 'free' here
+           |
+    <------+
+    |
+  'test_1': events 7-10
+    |
+    |   NN |     calls_free_1 (ptr);
+    |      |     ^~~~~~~~~~~~~~~~~~
+    |      |     |
+    |      |     (7) returning to 'test_1' from 'calls_free_1'
+    |   NN | 
+    |   NN |   if (b)
+    |      |      ~
+    |      |      |
+    |      |      (8) following 'false' branch (when 'b == 0')...
+    |......
+    |   NN |     calls_free_1 (ptr);
+    |      |     ~~~~~~~~~~~~~~~~~~
+    |      |     |
+    |      |     (9) ...to here
+    |      |     (10) passing freed pointer 'ptr' in call to 'calls_free_1' from 'test_1'
+    |
+    +--> 'calls_free_1': events 11-12
+           |
+           |   NN | void calls_free_1 (void *ptr)
+           |      |      ^~~~~~~~~~~~
+           |      |      |
+           |      |      (11) entry to 'calls_free_1'
+           |   NN | {
+           |   NN |   free (ptr);
+           |      |   ~~~~~~~~~~
+           |      |   |
+           |      |   (12) second 'free' here; first 'free' was at (6)
+           |
+  { dg-end-multiline-output "" } */
+
+void calls_free_2 (void *ptr)
+{
+  free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */
+}
+
+void test_2 (void *ptr, int a, int b)
+{
+  switch (a)
+    {
+    default:
+      break;
+    case 1:
+      break;
+    case 3:
+      calls_free_2 (ptr);
+      break;
+    }
+
+  switch (b)
+    {
+    default:
+      calls_free_2 (ptr);
+      break;
+    case 1:
+      break;
+    case 42:
+      break;
+    }
+}
+
+/* { dg-begin-multiline-output "" }
+   NN |   free (ptr);
+      |   ^~~~~~~~~~
+  'test_2': events 1-4
+    |
+    |   NN | void test_2 (void *ptr, int a, int b)
+    |      |      ^~~~~~
+    |      |      |
+    |      |      (1) entry to 'test_2'
+    |   NN | {
+    |   NN |   switch (a)
+    |      |   ~~~~~~
+    |      |   |
+    |      |   (2) following 'case 3:' branch...
+    |......
+    |   NN |     case 3:
+    |      |     ~~~~
+    |      |     |
+    |      |     (3) ...to here
+    |   NN |       calls_free_2 (ptr);
+    |      |       ~~~~~~~~~~~~~~~~~~
+    |      |       |
+    |      |       (4) calling 'calls_free_2' from 'test_2'
+    |
+    +--> 'calls_free_2': events 5-6
+           |
+           |   NN | void calls_free_2 (void *ptr)
+           |      |      ^~~~~~~~~~~~
+           |      |      |
+           |      |      (5) entry to 'calls_free_2'
+           |   NN | {
+           |   NN |   free (ptr);
+           |      |   ~~~~~~~~~~
+           |      |   |
+           |      |   (6) first 'free' here
+           |
+    <------+
+    |
+  'test_2': events 7-10
+    |
+    |   NN |       calls_free_2 (ptr);
+    |      |       ^~~~~~~~~~~~~~~~~~
+    |      |       |
+    |      |       (7) returning to 'test_2' from 'calls_free_2'
+    |......
+    |   NN |   switch (b)
+    |      |   ~~~~~~
+    |      |   |
+    |      |   (8) following 'default:' branch...
+    |   NN |     {
+    |   NN |     default:
+    |      |     ~~~~~~~
+    |      |     |
+    |      |     (9) ...to here
+    |   NN |       calls_free_2 (ptr);
+    |      |       ~~~~~~~~~~~~~~~~~~
+    |      |       |
+    |      |       (10) passing freed pointer 'ptr' in call to 'calls_free_2' from 'test_2'
+    |
+    +--> 'calls_free_2': events 11-12
+           |
+           |   NN | void calls_free_2 (void *ptr)
+           |      |      ^~~~~~~~~~~~
+           |      |      |
+           |      |      (11) entry to 'calls_free_2'
+           |   NN | {
+           |   NN |   free (ptr);
+           |      |   ~~~~~~~~~~
+           |      |   |
+           |      |   (12) second 'free' here; first 'free' was at (6)
+           |
+  { dg-end-multiline-output "" } */
+
+// TODO: range cases
+
+/* The call/return to this function shouldn't appear in the path.  */
+
+void called_by_test_3 (void)
+{
+}
+
+void test_3 (void *ptr)
+{
+  free (ptr);
+  called_by_test_3 ();
+  free (ptr); /* { dg-warning "double-'free' of 'ptr'" } */
+}
+
+/* { dg-begin-multiline-output "" }
+   NN |   free (ptr);
+      |   ^~~~~~~~~~
+  'test_3': events 1-2
+    |
+    |   NN |   free (ptr);
+    |      |   ^~~~~~~~~~
+    |      |   |
+    |      |   (1) first 'free' here
+    |   NN |   called_by_test_3 ();
+    |   NN |   free (ptr);
+    |      |   ~~~~~~~~~~
+    |      |   |
+    |      |   (2) second 'free' here; first 'free' was at (1)
+    |
+  { dg-end-multiline-output "" } */
diff --git a/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3a.c b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3a.c
new file mode 100644
index 0000000..1b2b798
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/analyzer-verbosity-3a.c
@@ -0,0 +1,20 @@
+/* { dg-additional-options "-fanalyzer-verbosity=3" } */
+
+#include <stdio.h>
+
+extern int foo ();
+extern void bar ();
+
+void test (const char *path, int flag)
+{
+  FILE *fp = fopen (path, "r"); /* { dg-message "opened here" } */
+
+  /* We should report this control flow at -fanalyzer-verbosity=3.  */
+  if (foo ()) /* { dg-message "branch" } */
+    bar ();
+  else
+    bar ();
+
+  if (flag) /* { dg-message "when 'flag == 0'" } */
+    fclose (fp); 
+} /* { dg-warning "leak of FILE 'fp'" } */
diff --git a/gcc/testsuite/gcc.dg/analyzer/edges-1.c b/gcc/testsuite/gcc.dg/analyzer/edges-1.c
new file mode 100644
index 0000000..6b53ddd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/edges-1.c
@@ -0,0 +1,54 @@
+#include <stdio.h>
+
+extern int foo ();
+extern void bar ();
+
+/* Verify that only significant edges are reported.  */
+
+void test_1 (const char *path, int flag)
+{
+  FILE *fp = fopen (path, "r");
+
+  if (!fp) /* { dg-message "when 'fp' is non-NULL" } */
+    return;
+
+  /* We shouldn't report this control flow.  */
+  while (foo ()) /* { dg-bogus "" } */
+    bar ();
+
+  if (flag) /* { dg-message "when 'flag == 0'" "branch event" } */
+    fclose (fp); /* { dg-bogus "leak" "warning at wrong location" { xfail *-*-* } .-1 } */
+} /* { dg-warning "leak of FILE 'fp'" "warning" { xfail *-*-* } } */
+// TODO(xfail): location of leak message ought to be on closing brace
+
+void test_2 (const char *path, int flag)
+{
+  FILE *fp = fopen (path, "r");
+
+  /* We shouldn't report this control flow.  */
+  if (foo ()) /* { dg-bogus "" } */
+    bar ();
+  else
+    bar ();
+
+  if (flag) /* { dg-message "when 'flag == 0'" } */
+    fclose (fp); 
+} /* { dg-warning "leak of FILE 'fp'" } */
+
+static void __attribute__((noinline))
+called_by_test_3 (int flag)
+{
+  if (flag)
+    foo ();
+}
+
+void test_3 (const char *path, int flag)
+{
+  FILE *fp = fopen (path, "r");
+
+  /* We shouldn't report the call/return here.  */
+  called_by_test_3 (flag); /* { dg-bogus "" } */
+
+  if (flag) /* { dg-message "when 'flag == 0'" } */
+    fclose (fp);
+} /* { dg-warning "leak of FILE 'fp'" } */
diff --git a/gcc/testsuite/gcc.dg/analyzer/edges-2.c b/gcc/testsuite/gcc.dg/analyzer/edges-2.c
new file mode 100644
index 0000000..847a708
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/edges-2.c
@@ -0,0 +1,20 @@
+#include <stdlib.h>
+
+int foo ();
+int bar ();
+
+/* Verify that only significant edges are reported.  */
+
+void test (int a, int b, int c)
+{
+  void *p = malloc (1024); /* { dg-message "allocated here" } */
+  while (a) /* { dg-bogus "" } */
+    foo ();
+  if (b) /* { dg-bogus "" } */
+    foo ();
+  else
+    bar ();
+  if (c) /* { dg-message "following 'true' branch" } */
+    free (p); /* { dg-message "first 'free' here" } */
+  free (p); /* { dg-warning "double-'free' of 'p'" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/file-paths-1.c b/gcc/testsuite/gcc.dg/analyzer/file-paths-1.c
index b284590..d346f7a 100644
--- a/gcc/testsuite/gcc.dg/analyzer/file-paths-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/file-paths-1.c
@@ -1,3 +1,5 @@
+/* { dg-additional-options "-fanalyzer-verbosity=3" } */
+
 #include <stdio.h>
 
 /* Verify that we correctly emit CFG events in the face of buffers