[Bug analyzer/109027] New: [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer

[Bug analyzer/109027] New: [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer

[zsojka at seznam dot cz]

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

            Bug ID: 109027
           Summary: [13 Regression] ICE: SIGSEGV (infinite recursion in
                    ana::constraint_manager::eval_condition /
                    ana::constraint_manager::impossible_derived_conditions
                    _p) with -fanalyzer
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: zsojka at seznam dot cz
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu

Created attachment 54587
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54587&action=edit
auto-reduced testcase

Compiler output:
$ x86_64-pc-linux-gnu-gcc -fanalyzer testcase.C -wrapper gdb,--args
...
Program received signal SIGSEGV, Segmentation fault.
0x000000000114d104 in ggc_internal_alloc (size=size@entry=32, f=f@entry=0x0,
s=s@entry=0, n=n@entry=1) at /repo/gcc-trunk/gcc/ggc-page.cc:1278
1278    {
(gdb) bt
#0  0x000000000114d104 in ggc_internal_alloc (size=size@entry=32,
f=f@entry=0x0, s=s@entry=0, n=n@entry=1)
    at /repo/gcc-trunk/gcc/ggc-page.cc:1278
#1  0x0000000001349489 in ggc_internal_cleared_alloc (size=size@entry=32,
f=f@entry=0x0, s=s@entry=0, n=n@entry=1)
    at /repo/gcc-trunk/gcc/ggc-common.cc:114
...
#19 0x00000000028f2826 in ana::constraint_manager::eval_condition
(this=0x4041780, lhs=0x39d8160, op=EQ_EXPR, rhs=0x3ac1c10)
    at /repo/gcc-trunk/gcc/analyzer/constraint-manager.cc:2591
#20 0x00000000028f5025 in
ana::constraint_manager::impossible_derived_conditions_p (this=0x4041780,
lhs=0x3ac7600, 
    rhs=0x3a2b5a0) at /repo/gcc-trunk/gcc/analyzer/constraint-manager.cc:2525
#21 0x00000000028f2826 in ana::constraint_manager::eval_condition
(this=0x4041780, lhs=0x3ac7600, op=EQ_EXPR, rhs=0x3a2b5a0)
    at /repo/gcc-trunk/gcc/analyzer/constraint-manager.cc:2591
...

$ x86_64-pc-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/repo/gcc-trunk/binary-latest-amd64/bin/x86_64-pc-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/repo/gcc-trunk/binary-trunk-r13-6471-20230304015539-g53940eee089-checking-yes-rtl-df-extra-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/13.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /repo/gcc-trunk//configure --enable-languages=c,c++
--enable-valgrind-annotations --disable-nls --enable-checking=yes,rtl,df,extra
--with-cloog --with-ppl --with-isl --build=x86_64-pc-linux-gnu
--host=x86_64-pc-linux-gnu --target=x86_64-pc-linux-gnu
--with-ld=/usr/bin/x86_64-pc-linux-gnu-ld
--with-as=/usr/bin/x86_64-pc-linux-gnu-as --disable-libstdcxx-pch
--prefix=/repo/gcc-trunk//binary-trunk-r13-6471-20230304015539-g53940eee089-checking-yes-rtl-df-extra-amd64
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.0.1 20230304 (experimental) (GCC)

[Bug analyzer/109027] [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0

[Bug analyzer/109027] [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-03-07
     Ever confirmed|0                           |1
            Summary|[13 Regression] ICE:        |[13 Regression] ICE:
                   |SIGSEGV (infinite recursion |SIGSEGV (infinite recursion
                   |in                          |in
                   |ana::constraint_manager::ev |ana::constraint_manager::ev
                   |al_condition /              |al_condition /
                   |ana::constraint_manager::im |ana::constraint_manager::im
                   |possible_derived_conditions |possible_derived_conditions
                   |_p) with -fanalyzer         |_p) with -fanalyzer since
                   |                            |r13-6101-g4d3b7be281e73ecd
             Status|UNCONFIRMED                 |NEW
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r13-6101-g4d3b7be281e73ecd.

[Bug analyzer/109027] [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
                 CC|                            |law at gcc dot gnu.org

[Bug analyzer/109027] [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[StevenSun2021 at hotmail dot com]

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

Steven Sun <StevenSun2021 at hotmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |StevenSun2021 at hotmail dot com

--- Comment #2 from Steven Sun <StevenSun2021 at hotmail dot com> ---
Created attachment 54862
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54862&action=edit
new test case

New logic introduced in r13-6101-g4d3b7be281e73ecd causes infinite recursions.
Specifically, `impossible_derived_conditions_p` will fail to escape this
recursion.

In this situation, for some `a`, `b`, we have `a+4` and `b-4` exist in
different equivalent classes (of the `m_equiv_classes`).


Then we try to compare `a == b-4`, `impossible_derived_conditions_p` then bring
us to

to check            `a == b-4`,
we'll look at       `b == a+4`,
since `a+4` is already in some equivalent class, we must know something about
it.


to check          `b == a+4`,
we'll look at     `a == b-4`,
since `b-4` is already in some equivalent class, we must know something about
it.

Then, it continues infinitely. We should bail this out. Also, it seems that the
analyzer cannot recognize some template patterns, failing to enter any exit
paths.

This code path executes very rarely.

------------------

While trying to simplify the original test case, I discovered my new test case
is another infinite recursion but in a different code path.

[Bug analyzer/109027] [13 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[StevenSun2021 at hotmail dot com]

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

--- Comment #3 from Steven Sun <StevenSun2021 at hotmail dot com> ---
Oh, my reduced test case has the same infinite recursion occurring, where

the `a+4` is

binop_svalue (pointer_plus_expr, unaryop_svalue (nop_expr, conjured_svalue (,
_iterator::_iterator (&__position, 0);,
decl_region(frame_region(‘Vector::Filter’, index: 2, depth: 3), ‘struct
iterator’, ‘iterator __position’))), constant_svalue(‘long unsigned int’, 4))

the `b-4` is

binop_svalue (pointer_plus_expr, sub_svalue (, conjured_svalue (,
_iterator::_iterator (&__position, 0);, decl_region(globals, ‘struct Vector’,
‘Vector vec’)), field_region(decl_region(globals, ‘struct Vector’, ‘Vector
vec’), ‘int *’, ‘int* Vector::_M_finish’)), constant_svalue(‘sizetype’,
18446744073709551612))



Current m_equiv_classes dump:

---------------- new equiv_class ----------------
region_svalue(‘struct Vector *’, decl_region(globals, ‘struct Vector’, ‘Vector
vec’))

---------------- new equiv_class ----------------
constant_svalue(‘void *’, 0B)

---------------- new equiv_class ----------------
region_svalue(‘struct _iterator *’, decl_region(frame_region(‘Vector::Filter’,
index: 2, depth: 3), ‘struct _iterator’, ‘<anonymous>’))

---------------- new equiv_class ----------------
region_svalue(‘int * *’, field_region(decl_region(globals, ‘struct Vector’,
‘Vector vec’), ‘int *’, ‘int* Vector::_M_finish’))

---------------- new equiv_class ----------------
region_svalue(‘struct _iterator *’, decl_region(frame_region(‘Vector::Filter’,
index: 2, depth: 3), ‘struct _iterator’, ‘_iterator it’))

---------------- new equiv_class ----------------
sub_svalue (, conjured_svalue (, it = Vector::begin (this_10(D));,
decl_region(frame_region(‘Vector::Filter’, index: 2, depth: 3), ‘struct
_iterator’, ‘_iterator it’)),
field_region(decl_region(frame_region(‘Vector::Filter’, index: 2, depth: 3),
‘struct _iterator’, ‘_iterator it’), ‘int *’, ‘int* _iterator::_M_current’))

---------------- new equiv_class ----------------
sub_svalue (, conjured_svalue (, it = Vector::begin (this_10(D));,
decl_region(globals, ‘struct Vector’, ‘Vector vec’)),
cast_region(field_region(decl_region(globals, ‘struct Vector’, ‘Vector vec’),
‘int *’, ‘int* Vector::_M_finish’), ‘int * const’))

---------------- new equiv_class ----------------
region_svalue(‘struct _iterator *’, decl_region(frame_region(‘Vector::Filter’,
index: 2, depth: 3), ‘struct _iterator’, ‘<anonymous>’))

---------------- new equiv_class ----------------
region_svalue(‘struct iterator *’, decl_region(frame_region(‘Vector::Filter’,
index: 2, depth: 3), ‘struct iterator’, ‘iterator __position’))

---------------- new equiv_class ----------------
region_svalue(‘struct _iterator *’,
decl_region(frame_region(‘_iterator::operator+’, index: 3, depth: 4), ‘struct
_iterator’, ‘<anonymous>’))

---------------- new equiv_class ----------------
region_svalue(‘int * const *’, decl_region(frame_region(‘_iterator::operator+’,
index: 3, depth: 4), ‘int * const’, ‘<anonymous>’))

---------------- new equiv_class ----------------
region_svalue(‘struct _iterator *’, decl_region(frame_region(‘Vector::Filter’,
index: 2, depth: 3), ‘struct _iterator’, ‘<anonymous>’))

---------------- new equiv_class ----------------
binop_svalue (pointer_plus_expr, unaryop_svalue (nop_expr, conjured_svalue (,
_iterator::_iterator (&__position, 0);,
decl_region(frame_region(‘Vector::Filter’, index: 2, depth: 3), ‘struct
iterator’, ‘iterator __position’))), constant_svalue(‘long unsigned int’, 4))

---------------- new equiv_class ----------------
sub_svalue (, conjured_svalue (, _iterator::_iterator (&__position, 0);,
decl_region(globals, ‘struct Vector’, ‘Vector vec’)),
cast_region(field_region(decl_region(globals, ‘struct Vector’, ‘Vector vec’),
‘int *’, ‘int* Vector::_M_finish’), ‘int * const’))

---------------- new equiv_class ----------------
binop_svalue (pointer_plus_expr, sub_svalue (, conjured_svalue (,
_iterator::_iterator (&__position, 0);, decl_region(globals, ‘struct Vector’,
‘Vector vec’)), field_region(decl_region(globals, ‘struct Vector’, ‘Vector
vec’), ‘int *’, ‘int* Vector::_M_finish’)), constant_svalue(‘sizetype’,
18446744073709551612))

[Bug analyzer/109027] [13/14 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.0                        |13.2

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.1 is being released, retargeting bugs to GCC 13.2.

[Bug analyzer/109027] [13/14 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.2                        |13.3

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.2 is being released, retargeting bugs to GCC 13.3.

[Bug analyzer/109027] [13/14 Regression] ICE: SIGSEGV (infinite recursion in ana::constraint_manager::eval_condition / ana::constraint_manager::impossible_derived_conditions_p) with -fanalyzer since r13-6101-g4d3b7be281e73ecd

[dmalcolm at gcc dot gnu.org]

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

--- Comment #6 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Bug 111099 is possibly a duplicate of this.