[gcc r13-6393] analyzer: fix infinite recursion false +ves [PR108935]

[gcc r13-6393] analyzer: fix infinite recursion false +ves [PR108935]

[David Malcolm]

https://gcc.gnu.org/g:070523b9d4c6cfa69060255893006efaf39bf617

commit r13-6393-g070523b9d4c6cfa69060255893006efaf39bf617
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Wed Mar 1 08:54:43 2023 -0500

    analyzer: fix infinite recursion false +ves [PR108935]
    
    gcc/analyzer/ChangeLog:
            PR analyzer/108935
            * infinite-recursion.cc (contains_unknown_p): New.
            (sufficiently_different_region_binding_p): New function, splitting
            out inner loop from...
            (sufficiently_different_p): ...here.  Extend detection of unknown
            svalues to also include svalues that contain unknown.  Treat
            changes in frames below the entry to the recursion as being
            sufficiently different to reject being an infinite recursion.
    
    gcc/testsuite/ChangeLog:
            PR analyzer/108935
            * gcc.dg/analyzer/infinite-recursion-pr108935-1.c: New test.
            * gcc.dg/analyzer/infinite-recursion-pr108935-1a.c: New test.
            * gcc.dg/analyzer/infinite-recursion-pr108935-2.c: New test.
    
    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

Diff:
---
 gcc/analyzer/infinite-recursion.cc                 | 151 ++++++++++++++-------
 .../analyzer/infinite-recursion-pr108935-1.c       |  17 +++
 .../analyzer/infinite-recursion-pr108935-1a.c      |  17 +++
 .../analyzer/infinite-recursion-pr108935-2.c       |  18 +++
 4 files changed, 152 insertions(+), 51 deletions(-)

diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc
index 1886534313e..c262e391953 100644
--- a/gcc/analyzer/infinite-recursion.cc
+++ b/gcc/analyzer/infinite-recursion.cc
@@ -394,12 +394,108 @@ remap_enclosing_frame (const region *base_reg,
     }
 }
 
+/* Return true iff SVAL is unknown, or contains an unknown svalue.  */
+
+static bool
+contains_unknown_p (const svalue *sval)
+{
+  if (sval->get_kind () == SK_UNKNOWN)
+    return true;
+  if (const compound_svalue *compound_sval
+	= sval->dyn_cast_compound_svalue ())
+    for (auto iter : *compound_sval)
+      if (iter.second->get_kind () == SK_UNKNOWN)
+	return true;
+  return false;
+}
+
+/* Subroutine of sufficiently_different_p.  Compare the store bindings
+   for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
+
+   Return true if the state of NEW_ENTRY_ENODE is sufficiently different
+   from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
+   being modified, and thus the recursion isn't infinite.
+
+   Return false if the states for BASE_REG are effectively the same.  */
+
+static bool
+sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
+					 exploded_node *prev_entry_enode,
+					 const region *base_reg)
+{
+  /* Compare the stores of the two enodes.  */
+  const region_model &new_model
+    = *new_entry_enode->get_state ().m_region_model;
+  const region_model &prev_model
+    = *prev_entry_enode->get_state ().m_region_model;
+
+  /* Get the value within the new frame.  */
+  const svalue *new_sval
+    = new_model.get_store_value (base_reg, NULL);
+
+  /* If any part of the value is UNKNOWN (e.g. due to hitting
+     complexity limits) assume that it differs from the previous
+     value.  */
+  if (contains_unknown_p (new_sval))
+    return true;
+
+  /* Get the equivalent value within the old enode.  */
+  const svalue *prev_sval;
+
+  if (const frame_region *enclosing_frame
+      = base_reg->maybe_get_frame_region ())
+    {
+      /* We have a binding within a frame in the new entry enode.  */
+
+      /* Consider changes in bindings below the original entry
+	 to the recursion.  */
+      const int old_stack_depth = prev_entry_enode->get_stack_depth ();
+      if (enclosing_frame->get_stack_depth () < old_stack_depth)
+	prev_sval = prev_model.get_store_value (base_reg, NULL);
+      else
+	{
+	  /* Ignore bindings within frames below the new entry node.  */
+	  const int new_stack_depth = new_entry_enode->get_stack_depth ();
+	  if (enclosing_frame->get_stack_depth () < new_stack_depth)
+	    return false;
+
+	  /* We have a binding within the frame of the new entry node,
+	     presumably a parameter.  */
+
+	  /* Get the value within the equivalent frame of
+	     the old entrypoint; typically will be the initial_svalue
+	     of the parameter.  */
+	  const frame_region *equiv_prev_frame
+	    = prev_model.get_current_frame ();
+	  const region *equiv_prev_base_reg
+	    = remap_enclosing_frame (base_reg,
+				     enclosing_frame,
+				     equiv_prev_frame,
+				     new_model.get_manager ());
+	  prev_sval
+	    = prev_model.get_store_value (equiv_prev_base_reg, NULL);
+	}
+    }
+  else
+    prev_sval = prev_model.get_store_value (base_reg, NULL);
+
+  /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
+     assume that it will differ from any new value.  */
+  if (contains_unknown_p (prev_sval))
+    return true;
+
+  if (new_sval != prev_sval)
+    return true;
+
+  return false;
+}
+
 /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
    both of which are entrypoints to the same function, where recursion has
    occurred.
 
    Return true if the state of NEW_ENTRY_ENODE is sufficiently different
-   from PREV_ENTRY_ENODE to suggests that some variant is being modified,
+   from PREV_ENTRY_ENODE to suggest that some variant is being modified,
    and thus the recursion isn't infinite.
 
    Return false if the states are effectively the same, suggesting that
@@ -459,64 +555,17 @@ sufficiently_different_p (exploded_node *new_entry_enode,
   gcc_assert (is_entrypoint_p (new_entry_enode));
   gcc_assert (is_entrypoint_p (prev_entry_enode));
 
-  const int new_stack_depth = new_entry_enode->get_stack_depth ();
-
   /* Compare the stores of the two enodes.  */
   const region_model &new_model
     = *new_entry_enode->get_state ().m_region_model;
-  const region_model &prev_model
-    = *prev_entry_enode->get_state ().m_region_model;
   const store &new_store = *new_model.get_store ();
 
   for (auto kv : new_store)
     {
       const region *base_reg = kv.first;
-
-      /* Get the value within the new frame.  */
-      const svalue *new_sval
-	= new_model.get_store_value (base_reg, NULL);
-
-      /* If the value is UNKNOWN (e.g. due to hitting complexity limits)
-	 assume that it differs from the previous value.  */
-      if (new_sval->get_kind () == SK_UNKNOWN)
-	return true;
-
-      /* Get the equivalent value within the old enode.  */
-      const svalue *prev_sval;
-
-      if (const frame_region *enclosing_frame
-	    = base_reg->maybe_get_frame_region ())
-	{
-	  /* We have a binding within a frame in the new entry enode.  */
-
-	  /* Ignore bindings within frames below the new entry node.  */
-	  if (enclosing_frame->get_stack_depth () < new_stack_depth)
-	    continue;
-
-	  /* We have a binding within the frame of the new entry node,
-	     presumably a parameter.  */
-
-	  /* Get the value within the equivalent frame of
-	     the old entrypoint; typically will be the initial_svalue
-	     of the parameter.  */
-	  const frame_region *equiv_prev_frame
-	    = prev_model.get_current_frame ();
-	  const region *equiv_prev_base_reg
-	    = remap_enclosing_frame (base_reg,
-				     enclosing_frame,
-				     equiv_prev_frame,
-				     new_model.get_manager ());
-	  prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL);
-	}
-      else
-	prev_sval = prev_model.get_store_value (base_reg, NULL);
-
-      /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits)
-	 assume that it will differ from any new value.  */
-      if (prev_sval->get_kind () == SK_UNKNOWN)
-	return true;
-
-      if (new_sval != prev_sval)
+      if (sufficiently_different_region_binding_p (new_entry_enode,
+						   prev_entry_enode,
+						   base_reg))
 	return true;
     }
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c
new file mode 100644
index 00000000000..83efe9bb7e0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c
@@ -0,0 +1,17 @@
+typedef struct {
+    unsigned idx;
+    int vals[512];
+} foo_t;
+
+int ended(foo_t* f) {
+    return f->idx >= 512;
+}
+unsigned foo(foo_t* f) {
+    if (ended(f)) {
+        return f->idx;
+    }
+    do {
+        f->idx++;
+    } while(!ended(f) && !f->vals[f->idx]);
+    return foo(f); /* { dg-bogus "infinite recursion" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c
new file mode 100644
index 00000000000..b3c4920b10d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c
@@ -0,0 +1,17 @@
+typedef struct {
+    unsigned idx;
+    int vals[512];
+} foo_t;
+
+int ended(foo_t* f) {
+    return f->idx >= 512;
+}
+unsigned foo(foo_t* f) {
+    if (ended(f)) {
+        return f->idx;
+    }
+    do {
+        f->idx += 1000;
+    } while(!ended(f) && !f->vals[f->idx]);
+    return foo(f); /* { dg-bogus "infinite recursion" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c
new file mode 100644
index 00000000000..c46f1f8012c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c
@@ -0,0 +1,18 @@
+typedef struct {
+    unsigned done;
+} foo_t;
+
+unsigned foo(foo_t* f) {
+    if (f->done) {
+        return f->done;
+    }
+    f->done = 1;
+    return foo(f); /* { dg-bogus "infinite recursion" } */
+}
+
+int main() {
+    foo_t f = (foo_t){
+        .done = 0,
+    };
+    foo(&f);
+}