[Bug tree-optimization/103603] New: [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[Bug tree-optimization/103603] New: [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[kito at gcc dot gnu.org]

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

            Bug ID: 103603
           Summary: [11 Regression] stack overflow on ranger for huge
                    program, but OK for legacy
           Product: gcc
           Version: 11.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kito at gcc dot gnu.org
                CC: aldyh at gcc dot gnu.org
  Target Milestone: ---

ranger taking too deep recursive checking on program with lots of expression,
but fixed on trunk via pr103254, however the patch-set is not easy to backport
to GCC 11 since gimple-range-path.cc isn't exist at GCC 11.

Testcase:
```
#define STMT \
    t += 1; \
    t *= 2; \
    t -= 1; \
    t &= 0xfff00fff; \
    t ^= 0x14022; \
    t %= 0xffffff3; \
    t += 6; \
    t *= 10; \

#define STMT2 STMT STMT
#define STMT4 STMT2 STMT2
#define STMT8 STMT4 STMT4
#define STMT16 STMT8 STMT8
#define STMT32 STMT16 STMT16
#define STMT64 STMT32 STMT32
#define STMT128 STMT64 STMT64
#define STMT256 STMT128 STMT128


int foo(int init) {
  int t = init,i,iter;
  for(iter=0; iter < 2; ++iter) {
      STMT256 STMT256 STMT256
  }
  return t;
}
```

How to reproduce:
$ gcc-11 xred.c -O2 # OK with --param=evrp-mode=legacy
gcc-11: internal compiler error: Segmentation fault signal terminated program
cc1
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-11/README.Bugs> for instructions.

Backtrace:
Program received signal SIGSEGV, Segmentation fault.
0x000000000141550f in gimple_ranger::range_of_range_op(irange&, gimple*) ()
(gdb) bt
#0  0x000000000141550f in gimple_ranger::range_of_range_op(irange&, gimple*) ()
#1  0x0000000001417b9b in gimple_ranger::calc_stmt(irange&, gimple*,
tree_node*) ()
#2  0x0000000001418152 in gimple_ranger::range_of_stmt(irange&, gimple*,
tree_node*) ()
#3  0x0000000001413ce1 in gimple_ranger::range_of_expr(irange&, tree_node*,
gimple*) ()
#4  0x0000000001415604 in gimple_ranger::range_of_range_op(irange&, gimple*) ()
#5  0x0000000001417b9b in gimple_ranger::calc_stmt(irange&, gimple*,
tree_node*) ()
#6  0x0000000001418152 in gimple_ranger::range_of_stmt(irange&, gimple*,
tree_node*) ()
#7  0x0000000001413ce1 in gimple_ranger::range_of_expr(irange&, tree_node*,
gimple*) ()
#8  0x0000000001415604 in gimple_ranger::range_of_range_op(irange&, gimple*) ()
#9  0x0000000001417b9b in gimple_ranger::calc_stmt(irange&, gimple*,
tree_node*) ()

Note:
GCC 11 with--param=evrp-mode=legacy and GCC-12 (after
g:d1c1919ef8a18eea9d5c1741f8c9adaabf5571f2) are work without stack overflow
even more statement like that:
```
#define STMT \
    t += 1; \
    t *= 2; \
    t -= 1; \
    t &= 0xfff00fff; \
    t ^= 0x14022; \
    t %= 0xffffff3; \
    t += 6; \
    t *= 10; \

#define STMT2 STMT STMT
#define STMT4 STMT2 STMT2
#define STMT8 STMT4 STMT4
#define STMT16 STMT8 STMT8
#define STMT32 STMT16 STMT16
#define STMT64 STMT32 STMT32
#define STMT128 STMT64 STMT64
#define STMT256 STMT128 STMT128


int foo(int init) {
  int t = init,i,iter;
  for(iter=0; iter < 2; ++iter) {
      STMT256 STMT256 STMT256 STMT256 STMT256 STMT256 STMT256 STMT256 STMT256
STMT256 STMT256
  }
  return t;
}
```

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.3

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.3                        |---

--- Comment #1 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
The changes by Andrew in pr103254 should fix this without any need for the
gimple range path changes. Are these changes portable to GCC11?

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-12-07
                 CC|                            |amacleod at redhat dot com,
                   |                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[kito at gcc dot gnu.org]

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

--- Comment #2 from Kito Cheng <kito at gcc dot gnu.org> ---
Oh, apologize for misleading, it should fixed via pr103231 rather than
pr103254.

it work after g:5deacf6058d1bc7261a75c9fd1f116c4442e9e60, no new file, but it's
not trivial backport-able.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 51944
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51944&action=edit
Ported patch

See if this works. I'll run it through testing, but this should be a port of
the patches from PR 103231 and the followup PR 103464  
There are some minor differences, but nothing too major.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[kito at gcc dot gnu.org]

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

--- Comment #4 from Kito Cheng <kito at gcc dot gnu.org> ---
Hi Andrew:

Thanks for your quick response! the patch is work to me for the testcase,
but...I got seg fault when I built x86 GCC.

Here is a reduced case from gcov, and this testcase also take longer
compilation time than expect (>15s to compile and ICE, but ~0.01s w/o patch):
```
struct gcov_ctr_info {
  int values;
};
struct gcov_fn_info {
  struct gcov_ctr_info ctrs[1];
};
struct gcov_info {
  struct gcov_fn_info **functions;
};
void __gcov_dump_one() {
  {
    struct gcov_info gi_ptr;
    int gi_ptr_1;
    struct gcov_info gi_ptr_0;
    int run_max ;
    for (; ; )
      for (unsigned f_ix ; gi_ptr_1; f_ix) {
        struct gcov_ctr_info *cinfo = gi_ptr.functions[0];
        int cinfo_0;
        for (unsigned i ; cinfo_0; i) {
          run_max < &cinfo;
          run_max = cinfo->values;
        }
      }
    for (; &gi_ptr; )
      ;
  }
}

```
Backtrace:
during GIMPLE pass: evrp
gcov.c:28:1: internal compiler error: Segmentation fault
   28 | }
      | ^
0xba283f crash_signal
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/toplev.c:327
0x1488666 vec<tree_node*, va_heap, vl_embed>::quick_push(tree_node* const&)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/vec.h:1023
0x1488666 vec<tree_node*, va_heap, vl_ptr>::quick_push(tree_node* const&)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/vec.h:1875
0x1488666 vec<tree_node*, va_heap, vl_ptr>::safe_push(tree_node* const&)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/vec.h:1888
0x1488666 gimple_ranger::prefill_stmt_dependencies(tree_node*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/gimple-range.cc:1177
0x14892de gimple_ranger::range_of_stmt(irange&, gimple*, tree_node*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/gimple-range.cc:1089
0x1482b45 gimple_ranger::range_of_expr(irange&, tree_node*, gimple*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/gimple-range.cc:982
0xe46670 range_query::value_of_expr(tree_node*, gimple*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/value-query.cc:86
0x14960e0 hybrid_folder::value_of_expr(tree_node*, gimple*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/gimple-ssa-evrp.c:235
0xd1575b substitute_and_fold_dom_walker::before_dom_children(basic_block_def*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/tree-ssa-propagate.c:1072
0x145cb34 dom_walker::walk(basic_block_def*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/domwalk.c:309
0xd14d85 substitute_and_fold_engine::substitute_and_fold(basic_block_def*)
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/tree-ssa-propagate.c:1283
0x1495c34 execute_early_vrp
        ../../../riscv-gnu-toolchain/riscv-gcc/gcc/gimple-ssa-evrp.c:349
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
Yes, there is an updated patch that bootstraps posted here for approval:

https://gcc.gnu.org/pipermail/gcc-patches/2021-December/586351.html

Give it a go.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.3
      Known to work|                            |10.3.0, 12.0
      Known to fail|                            |11.1.0, 11.2.0

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[kito at gcc dot gnu.org]

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

--- Comment #6 from Kito Cheng <kito at gcc dot gnu.org> ---
Reported testcase is OK and I test that patch on riscv64-elf and riscv64-linux
with full gcc testsuite run, both are no regression.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Andrew Macleod
<amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:3760d9d7b5410f16236ed15d02ec1d8a7d16fddb

commit r11-9452-g3760d9d7b5410f16236ed15d02ec1d8a7d16fddb
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Tue Dec 7 12:09:33 2021 -0500

    Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464)

    All ranger API entries eventually call range_of_stmt to ensure there is an
    initial global value to work with.  This can cause very deep call chains
when
    satisfied via the normal API.  Instead, push any dependencies onto a stack
    and evaluate them in a depth first manner, mirroring what would have
happened
    via the normal API calls.

            PR tree-optimization/103603
            gcc/
            * gimple-range.cc (gimple_ranger::gimple_ranger): Create stmt
stack.
            (gimple_ranger::~gimple_ranger): New.
            (gimple_ranger::range_of_stmt): Process dependencies if they have
no
            global cache entry.
            (gimple_ranger::prefill_name): New.
            (gimple_ranger::prefill_stmt_dependencies): New.
            * gimple-range.h (class gimple_ranger): Add prototypes.

[Bug tree-optimization/103603] [11 Regression] stack overflow on ranger for huge program, but OK for legacy

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
fixed