[gcc r12-5424] analyzer: fix false leak due to overeager state merging [PR103217]

[gcc r12-5424] analyzer: fix false leak due to overeager state merging [PR103217]

[David Malcolm]

https://gcc.gnu.org/g:f573d35147ca8433c102e1721d8c99fc432cb44b

commit r12-5424-gf573d35147ca8433c102e1721d8c99fc432cb44b
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Nov 18 15:23:30 2021 -0500

    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>

Diff:
---
 gcc/analyzer/engine.cc                    | 10 +++++---
 gcc/analyzer/program-state.cc             |  9 ++++---
 gcc/analyzer/program-state.h              |  3 ++-
 gcc/analyzer/region-model.cc              | 33 ++++++++++++++++++++++--
 gcc/analyzer/region-model.h               | 20 ++++++++++++---
 gcc/analyzer/svalue.cc                    |  8 ++++++
 gcc/testsuite/gcc.dg/analyzer/explode-1.c |  4 +--
 gcc/testsuite/gcc.dg/analyzer/pr103217.c  | 42 +++++++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/analyzer/pr94858-1.c |  2 ++
 9 files changed, 117 insertions(+), 14 deletions(-)

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 096e219392d..e8a7cca0f8c 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 1c87af0f00b..47e4eca06d0 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 eb49006d777..4579e2a6822 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 bbb15abdfe2..dccf9024a14 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 543401167ae..bffbdf24bca 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 5f2fe4c6449..7cbcf0c9cb6 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 f48408e8426..9b95afd9a03 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 00000000000..a0ef8bf3210
--- /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 f7be1c617da..d33c17495f9 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;