[Bug analyzer/108935] New: Incorrect warning for infinite recursion

[Bug analyzer/108935] New: Incorrect warning for infinite recursion

[zach-gcc at cs dot stanford.edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108935

            Bug ID: 108935
           Summary: Incorrect warning for infinite recursion
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: zach-gcc at cs dot stanford.edu
  Target Milestone: ---

The following code does not have infinite recursion:

```
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);
}
```

but -fanalyzer reports infinite recursion (called with `gcc -fanalyzer -c
test.c`). The function always makes progress towards f->idx reaching 512, which
is the termination condition. It is bounded to at most 512 recursive calls. I
can even add `f->idx += 1000` and the warning is still reported.

I've also noticed the following example causes a similar warning, but only when
`foo` is also invoked.

```
typedef struct {
    unsigned done;
} foo_t;

unsigned foo(foo_t* f) {
    if (f->done) {
        return f->done;
    }
    f->done = 1;
    return foo(f);
}

int main() {
    foo_t f = (foo_t){
        .done = 0,
    };
    // must be called to cause warning
    foo(&f);
}
```

Tested on version GCC 13 20230203 (commit hash a37a0cb303d). Thanks.

[Bug analyzer/108935] Incorrect warning for infinite recursion

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108935

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-02-27
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #1 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Thanks for filing this bug.  Confirmed; am investigating.

[Bug analyzer/108935] Incorrect warning for infinite recursion

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108935

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:

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>

[Bug analyzer/108935] Incorrect warning for infinite recursion

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108935

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Should be fixed by the above commit; marking this as resolved.