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