analyzer: fix false leak due to overeager state merging [PR103217]

PR analyzer/103217 reports a false positive from -Wanalyzer-malloc-leak.

The root cause is due to overzealous state merger, where the
state-merging code decided to merge these two states by merging
the stores:

state A:
  clusters within frame: ‘main’@1
    cluster for: one_3: CONJURED(val_4 = strdup (src_2(D));, val_4)
    cluster for: two_4: UNKNOWN(char *)
    cluster for: one_21: CONJURED(val_4 = strdup (src_2(D));, val_4)

state B:
  clusters within frame: ‘main’@1
    cluster for: one_3: UNKNOWN(char *)
    cluster for: two_4: CONJURED(val_4 = strdup (src_2(D));, val_4)
    cluster for: two_18: CONJURED(val_4 = strdup (src_2(D));, val_4)

into:
  clusters within frame: ‘main’@1
    cluster for: one_3: UNKNOWN(char *)
    cluster for: two_4: UNKNOWN(char *)
    cluster for: one_21: UNKNOWN(char *)
    cluster for: two_18: UNKNOWN(char *)

despite "CONJURED(val_4 = strdup (src_2(D));, val_4)" having sm-state,
in this case malloc:nonnull ({free}), thus leading to both references
to the conjured svalue being lost at merger.

This patch tweaks the state merger code so that it will not consider
merging two different svalues for the value of a region if either svalue
has non-purgable sm-state (in the above example, malloc:nonnull).  This
fixes the false leak report above.

Doing so uncovered an issue with explode-2a.c in which the warnings
moved from the correct location to the "while" stmt.  This turned out
to be a missing call to detect_leaks in phi-handling, which the patch
also fixes (in the PK_BEFORE_SUPERNODE case in
exploded_graph::process_node).  Doing this fixed the regression in
explode-2a.c and also fixed the location of the leak warning in
explode-1.c.

The other side effect of the change is that pr94858-1.c now emits
a -Wanalyzer-too-complex warning, since pertinent state is no longer
being thrown away.  There doesn't seem to be a good way of avoiding
this, so the patch also adds -Wno-analyzer-too-complex to that test
case (restoring the default).

gcc/analyzer/ChangeLog:
	PR analyzer/103217
	* engine.cc (exploded_graph::get_or_create_node): Pass in
	m_ext_state to program_state::can_merge_with_p.
	(exploded_graph::process_worklist): Likewise.
	(exploded_graph::maybe_process_run_of_before_supernode_enodes):
	Likewise.
	(exploded_graph::process_node): Add missing call to detect_leaks
	when handling phi nodes.
	* program-state.cc (program_state::can_merge_with_p): Add
	"ext_state" param.  Pass it and state ptrs to
	region_model::can_merge_with_p.
	(selftest::test_program_state_merging): Update for new ext_state
	param of program_state::can_merge_with_p.
	(selftest::test_program_state_merging_2): Likewise.
	* program-state.h (program_state::can_purge_p): Make const.
	(program_state::can_merge_with_p): Add "ext_state" param.
	* region-model.cc: Include "analyzer/program-state.h".
	(region_model::can_merge_with_p): Add params "ext_state",
	"state_a", and "state_b", use them when creating model_merger
	object.
	(model_merger::mergeable_svalue_p): New.
	* region-model.h (region_model::can_merge_with_p): Add params
	"ext_state", "state_a", and "state_b".
	(model_merger::model_merger) Likewise, initializing new fields.
	(model_merger::mergeable_svalue_p): New decl.
	(model_merger::m_ext_state): New field.
	(model_merger::m_state_a): New field.
	(model_merger::m_state_b): New field.
	* svalue.cc (svalue::can_merge_p): Call
	model_merger::mergeable_svalue_p on both states and reject the
	merger accordingly.

gcc/testsuite/ChangeLog:
	PR analyzer/103217
	* gcc.dg/analyzer/explode-1.c: Update for improvement to location
	of leak warning.
	* gcc.dg/analyzer/pr103217.c: New test.
	* gcc.dg/analyzer/pr94858-1.c: Add -Wno-analyzer-too-complex.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

9 files changed, 117 insertions, 14 deletions

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 096e219..e8a7cca 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -2417,7 +2417,7 @@ exploded_graph::get_or_create_node (const program_point &point,
 	  /* This merges successfully within the loop.  */
 
 	  program_state merged_state (m_ext_state);
-	  if (pruned_state.can_merge_with_p (existing_state, point,
+	  if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
 					     &merged_state))
 	    {
 	      merged_state.validate (m_ext_state);
@@ -2717,7 +2717,8 @@ exploded_graph::process_worklist ()
 		gcc_assert (state != state_2);
 
 		program_state merged_state (m_ext_state);
-		if (state.can_merge_with_p (state_2, point, &merged_state))
+		if (state.can_merge_with_p (state_2, m_ext_state,
+					    point, &merged_state))
 		  {
 		    if (logger)
 		      logger->log ("merging EN: %i and EN: %i",
@@ -2973,7 +2974,8 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
 	{
 	  merged_state->validate (m_ext_state);
 	  program_state merge (m_ext_state);
-	  if (it_state.can_merge_with_p (*merged_state, next_point, &merge))
+	  if (it_state.can_merge_with_p (*merged_state, m_ext_state,
+					 next_point, &merge))
 	    {
 	      *merged_state = merge;
 	      merged_state->validate (m_ext_state);
@@ -3305,6 +3307,8 @@ exploded_graph::process_node (exploded_node *node)
 		(node->get_supernode (),
 		 last_cfg_superedge,
 		 &ctxt);
+	    program_state::detect_leaks (state, next_state, NULL,
+					 get_ext_state (), &ctxt);
 	  }
 
 	program_point next_point (point.get_next ());
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 1c87af0..47e4eca 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1197,6 +1197,7 @@ program_state::get_representative_tree (const svalue *sval) const
 
 bool
 program_state::can_merge_with_p (const program_state &other,
+				 const extrinsic_state &ext_state,
 				 const program_point &point,
 				 program_state *out) const
 {
@@ -1213,7 +1214,9 @@ program_state::can_merge_with_p (const program_state &other,
   /* Attempt to merge the region_models.  */
   if (!m_region_model->can_merge_with_p (*other.m_region_model,
 					  point,
-					  out->m_region_model))
+					 out->m_region_model,
+					 &ext_state,
+					 this, &other))
     return false;
 
   /* Copy m_checker_states to OUT.  */
@@ -1645,7 +1648,7 @@ test_program_state_merging ()
      with the given sm-state.
      They ought to be mergeable, preserving the sm-state.  */
   program_state merged (ext_state);
-  ASSERT_TRUE (s0.can_merge_with_p (s1, point, &merged));
+  ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged));
   merged.validate (ext_state);
 
   /* Verify that the merged state has the sm-state for "p".  */
@@ -1703,7 +1706,7 @@ test_program_state_merging_2 ()
 
   /* They ought to not be mergeable.  */
   program_state merged (ext_state);
-  ASSERT_FALSE (s0.can_merge_with_p (s1, point, &merged));
+  ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged));
 }
 
 /* Run all of the selftests within this file.  */
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h
index eb49006..4579e2a 100644
--- a/gcc/analyzer/program-state.h
+++ b/gcc/analyzer/program-state.h
@@ -242,7 +242,7 @@ public:
   tree get_representative_tree (const svalue *sval) const;
 
   bool can_purge_p (const extrinsic_state &ext_state,
-		    const svalue *sval)
+		    const svalue *sval) const
   {
     /* Don't purge vars that have non-purgeable sm state, to avoid
        generating false "leak" complaints.  */
@@ -258,6 +258,7 @@ public:
   }
 
   bool can_merge_with_p (const program_state &other,
+			 const extrinsic_state &ext_state,
 			 const program_point &point,
 			 program_state *out) const;
 
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index bbb15ab..dccf902 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -64,6 +64,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "analyzer/pending-diagnostic.h"
 #include "analyzer/region-model-reachability.h"
 #include "analyzer/analyzer-selftests.h"
+#include "analyzer/program-state.h"
 #include "stor-layout.h"
 #include "attribs.h"
 #include "tree-object-size.h"
@@ -3683,7 +3684,10 @@ region_model::poison_any_pointers_to_descendents (const region *reg,
 bool
 region_model::can_merge_with_p (const region_model &other_model,
 				const program_point &point,
-				region_model *out_model) const
+				region_model *out_model,
+				const extrinsic_state *ext_state,
+				const program_state *state_a,
+				const program_state *state_b) const
 {
   gcc_assert (out_model);
   gcc_assert (m_mgr == other_model.m_mgr);
@@ -3693,7 +3697,8 @@ region_model::can_merge_with_p (const region_model &other_model,
     return false;
   out_model->m_current_frame = m_current_frame;
 
-  model_merger m (this, &other_model, point, out_model);
+  model_merger m (this, &other_model, point, out_model,
+		  ext_state, state_a, state_b);
 
   if (!store::can_merge_p (&m_store, &other_model.m_store,
 			   &out_model->m_store, m_mgr->get_store_manager (),
@@ -3897,6 +3902,30 @@ model_merger::dump (bool simple) const
   dump (stderr, simple);
 }
 
+/* Return true if it's OK to merge SVAL with other svalues.  */
+
+bool
+model_merger::mergeable_svalue_p (const svalue *sval) const
+{
+  if (m_ext_state)
+    {
+      /* Reject merging svalues that have non-purgable sm-state,
+	 to avoid falsely reporting memory leaks by merging them
+	 with something else.  For example, given a local var "p",
+	 reject the merger of a:
+	   store_a mapping "p" to a malloc-ed ptr
+	 with:
+	   store_b mapping "p" to a NULL ptr.  */
+      if (m_state_a)
+	if (!m_state_a->can_purge_p (*m_ext_state, sval))
+	  return false;
+      if (m_state_b)
+	if (!m_state_b->can_purge_p (*m_ext_state, sval))
+	  return false;
+    }
+  return true;
+}
+
 } // namespace ana
 
 /* Dump RMODEL fully to stderr (i.e. without summarization).  */
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index 5434011..bffbdf2 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -721,7 +721,10 @@ class region_model
 
   bool can_merge_with_p (const region_model &other_model,
 			 const program_point &point,
-			 region_model *out_model) const;
+			 region_model *out_model,
+			 const extrinsic_state *ext_state = NULL,
+			 const program_state *state_a = NULL,
+			 const program_state *state_b = NULL) const;
 
   tree get_fndecl_for_call (const gcall *call,
 			    region_model_context *ctxt);
@@ -987,10 +990,15 @@ struct model_merger
   model_merger (const region_model *model_a,
 		const region_model *model_b,
 		const program_point &point,
-		region_model *merged_model)
+		region_model *merged_model,
+		const extrinsic_state *ext_state,
+		const program_state *state_a,
+		const program_state *state_b)
   : m_model_a (model_a), m_model_b (model_b),
     m_point (point),
-    m_merged_model (merged_model)
+    m_merged_model (merged_model),
+    m_ext_state (ext_state),
+    m_state_a (state_a), m_state_b (state_b)
   {
   }
 
@@ -1003,10 +1011,16 @@ struct model_merger
     return m_model_a->get_manager ();
   }
 
+  bool mergeable_svalue_p (const svalue *) const;
+
   const region_model *m_model_a;
   const region_model *m_model_b;
   const program_point &m_point;
   region_model *m_merged_model;
+
+  const extrinsic_state *m_ext_state;
+  const program_state *m_state_a;
+  const program_state *m_state_b;
 };
 
 /* A record that can (optionally) be written out when
diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc
index 5f2fe4c..7cbcf0c 100644
--- a/gcc/analyzer/svalue.cc
+++ b/gcc/analyzer/svalue.cc
@@ -193,6 +193,14 @@ svalue::can_merge_p (const svalue *other,
 	return NULL;
     }
 
+  /* Reject merging svalues that have non-purgable sm-state,
+     to avoid falsely reporting memory leaks by merging them
+     with something else.  */
+  if (!merger->mergeable_svalue_p (this))
+    return NULL;
+  if (!merger->mergeable_svalue_p (other))
+    return NULL;
+
   /* Widening.  */
   /* Merge: (new_cst, existing_cst) -> widen (existing, new).  */
   if (maybe_get_constant () && other->maybe_get_constant ())
diff --git a/gcc/testsuite/gcc.dg/analyzer/explode-1.c b/gcc/testsuite/gcc.dg/analyzer/explode-1.c
index f48408e..9b95afd 100644
--- a/gcc/testsuite/gcc.dg/analyzer/explode-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/explode-1.c
@@ -12,7 +12,7 @@ void test (void)
 {
   void *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8;
   void **pp;
-  while (get ()) /* { dg-warning "leak" } */
+  while (get ())
     {
       switch (get ())
 	{
@@ -47,7 +47,7 @@ void test (void)
 	{
 	default:
 	case 0:
-	  *pp = malloc (16);
+	  *pp = malloc (16); /* { dg-warning "leak" } */
 	  break;
 	case 1:
 	  free (*pp);
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr103217.c b/gcc/testsuite/gcc.dg/analyzer/pr103217.c
new file mode 100644
index 0000000..a0ef8bf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr103217.c
@@ -0,0 +1,42 @@
+extern char *strdup (const char *__s)
+  __attribute__ ((__nothrow__ , __leaf__, __malloc__, __nonnull__ (1)));
+
+extern void abort (void)
+  __attribute__ ((__nothrow__ , __leaf__, __noreturn__));
+
+extern int getopt (int ___argc, char *const *___argv, const char *__shortopts)
+  __attribute__ ((__nothrow__ , __leaf__, __nonnull__ (2, 3)));
+extern char *optarg;
+
+extern void free (void *__ptr)
+  __attribute__ ((__nothrow__ , __leaf__));
+
+#define NULL ((void *)0)
+
+char *xstrdup(const char *src) {
+	char *val = strdup(src);
+	if (!val)
+		abort();
+	return val;
+}
+
+int main(int argc, char *argv[]) {
+	char *one = NULL, *two = NULL;
+	int rc;
+
+	while ((rc = getopt(argc, argv, "a:b:")) != -1) {
+		switch (rc) {
+		case 'a':
+			free(one);
+			one = xstrdup(optarg);
+			break;
+		case 'b':
+			free(two);
+			two = xstrdup(optarg);
+			break;
+		}
+	}
+	free(one);
+	free(two);
+	return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c b/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c
index f7be1c6..d33c174 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c
@@ -1,3 +1,5 @@
+/* { dg-additional-options "-Wno-analyzer-too-complex" } */
+
 #include <stdlib.h>
 
 typedef short hashNx;