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, 29 insertions, 0 deletions

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