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.

1 files changed, 130 insertions, 14 deletions

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:"