analyzer: Call off a superseding when diagnostics are unrelated [PR110830]

Before this patch, a saved_diagnostic would supersede another at
the same statement if and only its vfunc supercedes_p returned true
for the other diagnostic's kind.
That both warning were unrelated - i.e. resolving one would not fix
the other - was not considered in making the above choice.

This patch makes it so that two saved_diagnostics taking a different
outcome of at least one common conditional branching cannot supersede
each other.

Signed-off-by: Benjamin Priour <vultkayn@gcc.gnu.org>
Co-authored-by: David Malcolm <dmalcolm@redhat.com>
Signed-off-by: David Malcolm <dmalcolm@redhat.com>

gcc/analyzer/ChangeLog:

	PR analyzer/110830
	* diagnostic-manager.cc
	(compatible_epaths_p): New function.
	(saved_diagnostic::supercedes_p): Now calls the above
	to determine if the diagnostics do overlap and the superseding
	may proceed.

gcc/testsuite/ChangeLog:

	PR analyzer/110830
	* c-c++-common/analyzer/pr110830.c: New test.

2 files changed, 200 insertions, 1 deletions

diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index 10fea48..0dd375d 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -887,6 +887,88 @@ saved_diagnostic::add_duplicate (saved_diagnostic *other)
   m_duplicates.safe_push (other);
 }
 
+/* Walk up the sedges of each of the two paths.
+   If the two sequences of sedges do not perfectly correspond,
+   then paths are incompatible.
+   If there is at least one sedge that either cannot be paired up
+   or its counterpart is not equal, then the paths are incompatible
+   and this function returns FALSE.
+   Otherwise return TRUE.
+
+   Incompatible paths:
+
+       <cond Y>
+       /      \
+      /        \
+    true      false
+     |          |
+    ...        ...
+     |          |
+    ...       stmt x
+     |
+   stmt x
+
+   Both LHS_PATH and RHS_PATH final enodes should be
+   over the same gimple statement.  */
+
+static bool
+compatible_epath_p (const exploded_path *lhs_path,
+		    const exploded_path *rhs_path)
+{
+  gcc_assert (lhs_path);
+  gcc_assert (rhs_path);
+  gcc_assert (rhs_path->length () > 0);
+  gcc_assert (rhs_path->length () > 0);
+  int lhs_eedge_idx = lhs_path->length () - 1;
+  int rhs_eedge_idx = rhs_path->length () - 1;
+  const exploded_edge *lhs_eedge;
+  const exploded_edge *rhs_eedge;
+
+  while (lhs_eedge_idx >= 0 && rhs_eedge_idx >= 0)
+    {
+      while (lhs_eedge_idx >= 0)
+	{
+	  /* Find LHS_PATH's next superedge.  */
+	  lhs_eedge = lhs_path->m_edges[lhs_eedge_idx];
+	  if (lhs_eedge->m_sedge)
+	    break;
+	  else
+	    lhs_eedge_idx--;
+	}
+      while (rhs_eedge_idx >= 0)
+	{
+	  /* Find RHS_PATH's next superedge.  */
+	  rhs_eedge = rhs_path->m_edges[rhs_eedge_idx];
+	  if (rhs_eedge->m_sedge)
+	    break;
+	  else
+	    rhs_eedge_idx--;
+	}
+
+      if (lhs_eedge->m_sedge && rhs_eedge->m_sedge)
+	{
+	  if (lhs_eedge->m_sedge != rhs_eedge->m_sedge)
+	    /* Both superedges do not match.
+	       Superedges are not dependent on the exploded path, so even
+	       different epaths will have similar sedges if they follow
+	       the same outcome of a conditional node.  */
+	    return false;
+
+	  lhs_eedge_idx--;
+	  rhs_eedge_idx--;
+	  continue;
+	}
+      else if (lhs_eedge->m_sedge == nullptr && rhs_eedge->m_sedge == nullptr)
+	/* Both paths were drained up entirely.
+	   No discriminant was found.  */
+	return true;
+
+      /* A superedge was found for only one of the two paths.  */
+      return false;
+    }
+}
+
+
 /* Return true if this diagnostic supercedes OTHER, and that OTHER should
    therefore not be emitted.  */
 
@@ -896,7 +978,13 @@ saved_diagnostic::supercedes_p (const saved_diagnostic &other) const
   /* They should be at the same stmt.  */
   if (m_stmt != other.m_stmt)
     return false;
-  return m_d->supercedes_p (*other.m_d);
+  /* return early if OTHER won't be superseded anyway.  */
+  if (!m_d->supercedes_p (*other.m_d))
+    return false;
+
+  /* If the two saved_diagnostics' path are not compatible
+     then they cannot supersede one another.  */
+  return compatible_epath_p (m_best_epath.get (), other.m_best_epath.get ());
 }
 
 /* Move any saved checker_events from this saved_diagnostic to
diff --git a/gcc/testsuite/c-c++-common/analyzer/pr110830.c b/gcc/testsuite/c-c++-common/analyzer/pr110830.c
new file mode 100644
index 0000000..f5a39b7
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/pr110830.c
@@ -0,0 +1,111 @@
+typedef __SIZE_TYPE__ size_t;
+
+void free(void *);
+void *malloc(__SIZE_TYPE__);
+
+extern int ext();
+
+void test_supersedes ()
+{
+  int *p = (int *)malloc(sizeof(int));
+  free(p);
+  int x = *p + 4; /* { dg-warning "use after 'free' of 'p'" } */
+  /* { dg-bogus "use of uninitialized value '\\*p" "" { target *-*-* } .-1 } */
+}
+
+int *called_by_test0()
+{
+  int *p = 0;
+  if (ext())
+  {
+    p = (int *)malloc(sizeof(int));
+    free(p);
+    return p;
+  }
+  else
+    return (int *)malloc(sizeof(int));
+}
+
+void test0()
+{
+  int *y = called_by_test0();
+  int x = 0;
+  if (y != 0)
+    x = *y; /* { dg-warning "use after 'free' of 'y'" } */
+    /* { dg-warning "use of uninitialized value '\\*y'" "don't supersede warnings with incompatible cfg path" { target *-*-* } .-1 } */
+  free(y); /* { dg-warning "double-'free'" }  */
+}
+
+void test1()
+{
+  int *p = 0;
+  if (ext())
+  {
+    p = (int *)malloc(sizeof(int));
+    free(p);
+  }
+  else
+    p = (int *)malloc(sizeof(int));
+
+  int x = 0;
+  if (p != 0)
+    x = *p; /* { dg-warning "use after 'free' of 'p'" } */
+    /* { dg-warning "use of uninitialized value '\\*p'" "don't supersede warnings with incompatible cfg path" { target *-*-* } .-1 } */
+  free(p); /* { dg-warning "double-'free'" }  */
+}
+
+void test2()
+{
+  int *p = 0;
+  p = (int *)malloc(sizeof(int));
+  if (ext())
+    free(p);
+
+  int x = 0;
+  if (p != 0)
+    x = *p; /* { dg-warning "use after 'free' of 'p'" } */
+    /* { dg-warning "use of uninitialized value '\\*p'" "don't supersede warnings with incompatible cfg path" { target *-*-* } .-1 } */
+  free(p); /* { dg-warning "double-'free'" }  */
+}
+
+void test3()
+{
+  int *p = 0;
+  p = (int *)malloc(sizeof(int));
+  int i = 100;
+  while (i--)
+  {
+    int x = 0;
+    if (p != 0)
+      x = *p; /* { dg-warning "use after 'free' of 'p'" } */
+      /* { dg-warning "use of uninitialized value '\\*p'" "don't supersede warnings with incompatible cfg path" { target *-*-* } .-1 } */
+    p = (int *)malloc(sizeof(int));
+    free(p);
+  }
+
+  free(p); /* { dg-warning "double-'free'" }  */
+}
+
+
+void test4()
+{
+  int *p = 0;
+  if (ext())
+  {
+    p = (int *) malloc(sizeof(int));
+    if (ext () > 5)
+    {
+      mal:
+      free (p);
+    }
+  }
+  else {
+    goto mal;
+  }
+
+  int x = 0;
+  if (p != 0)
+    x = *p; /* { dg-warning "use after 'free' of 'p'" } */
+    /* { dg-warning "use of uninitialized value '\\*p'" "" { target *-*-* } .-1 } */
+  free(p); /* { dg-warning "double-'free'" }  */
+}