[Bug c/109192] New: timeout with -g -O3 -fno-var-tracking ?

[Bug c/109192] New: timeout with -g -O3 -fno-var-tracking ?

[dcb314 at hotmail dot com]

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

            Bug ID: 109192
           Summary: timeout with -g -O3 -fno-var-tracking ?
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dcb314 at hotmail dot com
  Target Milestone: ---

Created attachment 54705
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54705&action=edit
C source code

The attached C code can't be compiled in ten minutes, when -O3
-fno-var-tracking is used:

$ (ulimit -t 600; time /home/dcb36/gcc/results/bin/gcc  -w -c -O3
-fno-var-tracking  bug898.c)
gcc: fatal error: Killed signal terminated program cc1
compilation terminated.

real    10m6.003s
user    9m59.649s
sys     0m0.103s

It is fine when -O3 is replaced by -O2:

$ (ulimit -t 600; time /home/dcb36/gcc/results/bin/gcc  -w -c -O2
-fno-var-tracking  bug898.c)

real    0m0.453s
user    0m0.434s
sys     0m0.014s

The bug first seems to occur sometime between 20230101 and 20230221.

$ for i in ~/gcc/results.20230*/bin/gcc; do echo $i; (ulimit -t 60; time $i -c
-w -O3 -fno-var-tracking bug898.c); done
/home/dcb36/gcc/results.20230101/bin/gcc

real    0m1.140s
user    0m0.678s
sys     0m0.021s
/home/dcb36/gcc/results.20230221.asan.ubsan/bin/gcc
gcc: fatal error: Killed signal terminated program cc1
compilation terminated.

real    1m0.606s
user    0m59.990s
sys     0m0.016s

Git hashes are g:4f1314f547f69d3a2b1f16ce301267e3bfb4e427 and
g:a804419c89db9e1c, a range of some 1,800 commits.

[Bug middle-end/109192] timeout with -O3 -fno-var-tracking ?

[dcb314 at hotmail dot com]

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

--- Comment #1 from David Binderman <dcb314 at hotmail dot com> ---
Current git range seems to be g:af22b54af53c0f2a .. g:f3b1af49702a3d19,
which is 75 commits.

[Bug middle-end/109192] timeout with -O3 -fno-var-tracking ?

[dcb314 at hotmail dot com]

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

--- Comment #2 from David Binderman <dcb314 at hotmail dot com> ---
Range now downto g:a0c2ea3ee6e47f40 .. g:2db1fd76ebaa6da8, which is 19 commits.

[Bug middle-end/109192] timeout with -O3 -fno-var-tracking ?

[dcb314 at hotmail dot com]

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

David Binderman <dcb314 at hotmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #3 from David Binderman <dcb314 at hotmail dot com> ---
$ git bisect good 809d661aff99ae02
1626ec53e8c1b9c245572417d380e3ed84990cff is the first bad commit
commit 1626ec53e8c1b9c245572417d380e3ed84990cff
Author: Andrew MacLeod <amacleod@redhat.com>

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 -fno-var-tracking since r13-5579

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|timeout with -O3            |[13 Regression] timeout
                   |-fno-var-tracking ?         |with -O3 -fno-var-tracking
                   |                            |since r13-5579
           Keywords|needs-bisection             |
          Component|middle-end                  |tree-optimization
   Target Milestone|---                         |13.0

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to David Binderman from comment #3)
> $ git bisect good 809d661aff99ae02
> 1626ec53e8c1b9c245572417d380e3ed84990cff is the first bad commit
> commit 1626ec53e8c1b9c245572417d380e3ed84990cff
> Author: Andrew MacLeod <amacleod@redhat.com>

r13-5579-g1626ec53e8c1b9

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-03-20
            Summary|[13 Regression] timeout     |[13 Regression] timeout
                   |with -O3 -fno-var-tracking  |with -O3 since r13-5579
                   |since r13-5579              |
           Priority|P3                          |P1

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed - this has nothing to do with -fno-var-tracking btw but reproduces
with just -O3 vs -O2.  An interrupted (after a minute) perf profile shows

+   55.46%     0.66%          1769  cc1      cc1                 [.]
operator_cast::op1_range                          #
+   48.68%     0.05%           141  cc1      cc1                 [.]
operator_cast::fold_range                         #
+   48.63%     3.06%          8238  cc1      cc1                 [.]
operator_cast::fold_range                         #
+   27.27%     1.18%          3160  cc1      cc1                 [.]
irange::set_nonzero_bits                          #
+   25.39%     1.68%          4512  cc1      cc1                 [.]
irange::set_range_from_nonzero_bits               #
+   21.08%     0.74%          1998  cc1      cc1                 [.]
irange::get_nonzero_bits                          #
+   20.34%    14.24%         38289  cc1      cc1                 [.]
irange::get_nonzero_bits_from_range               

and we're in the 'thread'(200) pass

      NEXT_PASS (pass_fre, false /* may_iterate */);
      /* After late FRE we rewrite no longer addressed locals into SSA
         form if possible.  */
      NEXT_PASS (pass_thread_jumps, /*first=*/false);
      NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */);
      NEXT_PASS (pass_strlen);

interrupting gives a backtrace like

#2  0x000000000196ec95 in gori_compute::compute_operand_range (
    this=this@entry=0x47bd5e0, r=..., stmt=<gimple_assign 0x7f9b81bbe5f0>, 
    lhs=..., name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, src=..., 
    rel=<optimized out>)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:700
...
#211 0x000000000196f37b in gori_compute::compute_operand_range (
    this=this@entry=0x47bd5e0, r=..., 
    stmt=stmt@entry=<gimple_cond 0x7f9b81bac5a0>, lhs=..., 
    name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, src=..., 
    rel=<optimized out>)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:702
#212 0x0000000001970ec9 in gori_compute::outgoing_edge_range_p (
    this=this@entry=0x47bd5e0, r=..., 
    e=e@entry=<edge 0x7f9b81dddba0 (122 -> 126)>, 

    name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, q=...)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:1358
#213 0x0000000000e4aa79 in path_range_query::compute_ranges_in_block (
    this=this@entry=0x7fff9c936a40, 
    bb=bb@entry=<basic_block 0x7f9b81ba7ba0 (122)>)
    at /space/rguenther/src/gcc/gcc/gimple-range-path.cc:454

so 200 frames worth of recursion (just luck from some random gdb attach).
There are just 201 BBs in the function (func_36.constprop) and 1525
SSA names, so this seems to be quadraticness / missed caching.

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
On a fast machine compile eventually finishes and a time-report looks like

 dominator optimization             : 156.84 ( 52%)   0.00 (  0%) 156.86 ( 52%)
  112k (  1%)
 backwards jump threading           : 145.15 ( 48%)   0.00 (  0%) 145.15 ( 48%)
   70k (  0%)
 TOTAL                              : 302.15          0.02        302.19       
   16M

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[amacleod at redhat dot com]

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

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

This is due to the latter part of the specified patch.  We normally terminate
outgoing range calculations once the LHS has reverted to VARYING as we won't
learn anything new.

The original patch modified this such that if there was a relation present, we
continued calculating as the relation may provide new information, as per the
original PR.

The problem exposed in this PR is that the presence of a relation doesn't mean
that relation can actually affect the range.  This PR shows many relations,
none of which are relevant, and with the quadratic nature of the path query, it
makes things quite bad.

The attached patch is in testing.  It adds a check to determine if the relation
can affect the outgoing range or not by checking if the operands are used in
the calculation or not.  If they are not in the definition chain, they can have
no impact, and we stop the attempt.

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #7)
> Created attachment 54716 [details]
> proposed patch
> 
> This is due to the latter part of the specified patch.  We normally
> terminate outgoing range calculations once the LHS has reverted to VARYING
> as we won't learn anything new.
> 
> The original patch modified this such that if there was a relation present,
> we continued calculating as the relation may provide new information, as per
> the original PR.
> 
> The problem exposed in this PR is that the presence of a relation doesn't
> mean that relation can actually affect the range.  This PR shows many
> relations, none of which are relevant, and with the quadratic nature of the
> path query, it makes things quite bad.
> 
> The attached patch is in testing.  It adds a check to determine if the
> relation can affect the outgoing range or not by checking if the operands
> are used in the calculation or not.  If they are not in the definition
> chain, they can have no impact, and we stop the attempt.

Sounds reasonable without knowing all the details in the implementation.
How does it affect compile-times on the testcase?

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:0963cb5fde158cce986523a90fa9edc51c881f31

commit r13-6787-g0963cb5fde158cce986523a90fa9edc51c881f31
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Mar 20 16:11:12 2023 -0400

    Terminate GORI calculations if a relation is not relevant.

    We currently allow VARYING lhs GORI calculations to continue if there is
    a relation present in the hope it will eventually better refine a result.
    This adds a check that the relation is relevant to the outgoing range
    calculation first.  If it is not relevant, stop calculating.

            PR tree-optimization/109192
            * gimple-range-gori.cc (gori_compute::compute_operand_range):
            Terminate gori calculations if a relation is not relevant.
            * value-relation.h (value_relation::set_relation): Allow
            equality between op1 and op2 if they are the same.

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

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

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #6)
> On a fast machine compile eventually finishes and a time-report looks like
> 
>  dominator optimization             : 156.84 ( 52%)   0.00 (  0%) 156.86 (
> 52%)   112k (  1%)
>  backwards jump threading           : 145.15 ( 48%)   0.00 (  0%) 145.15 (
> 48%)    70k (  0%)
>  TOTAL                              : 302.15          0.02        302.19    
> 16M

With the fix in it's now

 dominator optimization             :   0.01 (  4%)   0.00 (  0%)   0.00 (  0%)
  112k (  1%)
 backwards jump threading           :   0.00 (  0%)   0.00 (  0%)   0.04 ( 13%)
   70k (  0%)

Thanks a lot (for reporting and for fixing)

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[chenglulu at loongson dot cn]

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

chenglulu <chenglulu at loongson dot cn> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chenglulu at loongson dot cn

--- Comment #12 from chenglulu <chenglulu at loongson dot cn> ---
Created attachment 54776
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54776&action=edit
zheev.fppized.f

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[chenglulu at loongson dot cn]

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

--- Comment #13 from chenglulu <chenglulu at loongson dot cn> ---
(In reply to CVS Commits from comment #9)
> The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:
> 
> https://gcc.gnu.org/g:0963cb5fde158cce986523a90fa9edc51c881f31
> 
> commit r13-6787-g0963cb5fde158cce986523a90fa9edc51c881f31
> Author: Andrew MacLeod <amacleod@redhat.com>
> Date:   Mon Mar 20 16:11:12 2023 -0400
> 
>     Terminate GORI calculations if a relation is not relevant.
>     
>     We currently allow VARYING lhs GORI calculations to continue if there is
>     a relation present in the hope it will eventually better refine a result.
>     This adds a check that the relation is relevant to the outgoing range
>     calculation first.  If it is not relevant, stop calculating.
>     
>             PR tree-optimization/109192
>             * gimple-range-gori.cc (gori_compute::compute_operand_range):
>             Terminate gori calculations if a relation is not relevant.
>             * value-relation.h (value_relation::set_relation): Allow
>             equality between op1 and op2 if they are the same.

After applying this patch, the zheev.fppized.f file in the compilation
attachment under the LoongArch and riscv64 architecture will report ICE. The
error message is as follows:

$ riscv64-linux-gnu-gfortran -c -o zheev.fppized.o -O3
-fno-aggressive-loop-optimizations -std=legacy zheev.fppized.f

during GIMPLE pass: dom
zheev.fppized.f:4968:23:

 4968 |       SUBROUTINE DLAMC2( BETA, T, RND, EPS, EMIN, RMIN, EMAX, RMAX )
      |                       ^
internal compiler error: in in_chain_p, at gimple-range-gori.cc:119
0x25683f3 range_def_chain::in_chain_p(tree_node*, tree_node*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:119
0x2569e66 gori_compute::compute_operand_range(vrange&, gimple*, vrange const&,
tree_node*, fur_source&, value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:667
0x256bfd4 gori_compute::compute_operand1_range(vrange&,
gimple_range_op_handler&, vrange const&, tree_node*, fur_source&,
value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:1174
0x256a408 gori_compute::compute_operand_range(vrange&, gimple*, vrange const&,
tree_node*, fur_source&, value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:726
0x256c648 gori_compute::compute_operand2_range(vrange&,
gimple_range_op_handler&, vrange const&, tree_node*, fur_source&,
value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:1254
0x256c744 gori_compute::compute_operand1_and_operand2_range(vrange&,
gimple_range_op_handler&, vrange const&, tree_node*, fur_source&,
value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:1274
0x256a3b7 gori_compute::compute_operand_range(vrange&, gimple*, vrange const&,
tree_node*, fur_source&, value_relation*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:723
0x256ccfc gori_compute::outgoing_edge_range_p(vrange&, edge_def*, tree_node*,
range_query&)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:1384
0x255e2dc ranger_cache::edge_range(vrange&, edge_def*, tree_node*,
ranger_cache::rfd_mode)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-cache.cc:964
0x255e465 ranger_cache::range_on_edge(vrange&, edge_def*, tree_node*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-cache.cc:1001
0x2563ba9 fur_edge::get_operand(vrange&, tree_node*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-fold.cc:131
0x25652a5 fold_using_range::range_of_range_op(vrange&,
gimple_range_op_handler&, fur_source&)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-fold.cc:558
0x2564cf8 fold_using_range::fold_stmt(vrange&, gimple*, fur_source&,
tree_node*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-fold.cc:489
0x256420c fold_range(vrange&, gimple*, edge_def*, range_query*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-fold.cc:326
0x256cf5f gori_compute::outgoing_edge_range_p(vrange&, edge_def*, tree_node*,
range_query&)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-gori.cc:1411
0x2560449 ranger_cache::range_from_dom(vrange&, tree_node*, basic_block_def*,
ranger_cache::rfd_mode)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-cache.cc:1524
0x255f069 ranger_cache::fill_block_cache(tree_node*, basic_block_def*,
basic_block_def*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-cache.cc:1212
0x255e5c7 ranger_cache::block_range(vrange&, basic_block_def*, tree_node*,
bool)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range-cache.cc:1039
0x2558761 gimple_ranger::range_on_entry(vrange&, basic_block_def*, tree_node*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range.cc:156
0x2558588 gimple_ranger::range_of_expr(vrange&, tree_node*, gimple*)
       
/home/chenglulu/work/loongisa-toolchain/gcc-upstream/gcc/gimple-range.cc:130
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

I chased the code and found that the error was caused by the fact that
vrel_ptr->op1() or vrel_ptr->op2() was empty.
So I think the following modification should be done:

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 2f8d4704ea4..5c25f1635f8 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -658,7 +658,7 @@ gori_compute::compute_operand_range (vrange &r, gimple
*stmt,
   // the result.
   if (lhs.varying_p ())
     {
-      if (!vrel_ptr)
+      if (!vrel_ptr || (!vrel_ptr->op1 () || !vrel_ptr->op2 ()))
        return false;
       // If there is a relation (ie: x != y) , it can only be relevant if
       // a) both elements are in the defchain

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[amacleod at redhat dot com]

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

--- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
The upcoming patch for 109274 should resolve this.

[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

[chenglulu at loongson dot cn]

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

--- Comment #15 from chenglulu <chenglulu at loongson dot cn> ---
(In reply to Andrew Macleod from comment #14)
> The upcoming patch for 109274 should resolve this.

The problem has been solved. Thanks!