[Bug ipa/106809] New: [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[Bug ipa/106809] New: [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[andres at anarazel dot de]

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

            Bug ID: 106809
           Summary: [12 regression] large bison grammars compilation got a
                    lot slower, mainly due to -Wuninitialized
           Product: gcc
           Version: 12.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: ipa
          Assignee: unassigned at gcc dot gnu.org
          Reporter: andres at anarazel dot de
                CC: marxin at gcc dot gnu.org
  Target Milestone: ---

Created attachment 53529
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53529&action=edit
preprocessed input file showing slowdown

Hi,

I noticed that building the .c output from bison got a lot slower in 12,
compared to 11.

$ gcc-12 --version
gcc-12 (Debian 12.2.0-1) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ gcc-12 preproc.i -c -Wuninitialized

real    0m3.558s
user    0m3.475s
sys     0m0.083s

$ time gcc-11 preproc.i -c -Wuninitialized

real    0m1.232s
user    0m1.150s
sys     0m0.082s

This is a pretty egregious case, for saner grammars the performance difference
is smaller.

There's also a performance difference without -Wuninitialized, but it's much
smaller (1.090s -> 1.314s)

Looking at -ftime-report, there's a very clear difference in how much time is
spent in "uninit var analysis"
11: uninit var analysis                :   0.01 (  1%)   0.00 (  0%)   0.00 ( 
0%)    10k (  0%)

12: uninit var analysis                :   2.24 ( 63%)   0.00 (  0%)   2.26 (
55%)   393k (  1%)

Regards,

andres

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Target Milestone|---                         |12.3
                 CC|                            |rguenth at gcc dot gnu.org
           Keywords|                            |needs-bisection
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-09-02

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12 regression] large bison |[12/13 regression] large
                   |grammars compilation got a  |bison grammars compilation
                   |lot slower, mainly due to   |got a lot slower, mainly
                   |-Wuninitialized             |due to -Wuninitialized
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
           Keywords|needs-bisection             |
             Status|NEW                         |ASSIGNED

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Also with GCC 13.  The obvious candidate would be the VN run done now to
identify unreachable code and reduce false positives.  I'll refactor timevars
to better track that.

OK, so callgrind points at dominated_by_p_w_unex, called from
rpo_elim::eliminate_avail.  Looks like we manage to run into a
degenerate case of a value with a very large avail set.  The
most avail queries are from

      if (eliminate && ! iterate)
        ...
      else
        /* If not eliminating, make all not already available defs
           available.  */
        FOR_EACH_SSA_TREE_OPERAND (op, gsi_stmt (gsi), i, SSA_OP_DEF)
          if (! avail.eliminate_avail (bb, op))
            avail.eliminate_push_avail (bb, op);

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, we're seeing up to 1420 AVAIL entries for a single value (_11574),
the value corresponding to yyvsp_11649->str.  Looking at the source I
can easily see how this happens.

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[marxin at gcc dot gnu.org]

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

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
I see the change since r12-4726-g9a27acc30a34b785 which goes from 2.2s to 6.3s
(checking enabled).

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
A testcase for this corner case is the following.  At -O0 it is
-Wuninitialized, at -O1 it is FRE:

 tree FRE                           :   5.55 ( 70%)   0.00 (  0%)   5.56 ( 67%)
   16k (  0%)

and at -O2 PRE will finally make use of the value numbers, hoisting the
load and optimizing the function to a single conditional.

 tree PRE                           :   2.80 ( 27%)   0.02 (  6%)   2.82 ( 26%)
   17k (  0%)
 tree FRE                           :   5.56 ( 54%)   0.01 (  3%)   5.57 ( 52%)
   16k (  0%)

The -On behavior would be a regression from GCC 9 where the new VN was
introduced.

int foo (int x, int *val)
{
  switch (x)
    {
#define C(n) \
    case n + 0: return *val; \
    case n + 1: return *val; \
    case n + 2: return *val; \
    case n + 3: return *val; \
    case n + 4: return *val; \
    case n + 5: return *val; \
    case n + 6: return *val; \
    case n + 7: return *val; \
    case n + 8: return *val; \
    case n + 9: return *val;
#define C1(n) \
    C(n+00) C(n+10) C(n+20) C(n+30) C(n+40) \
    C(n+50) C(n+60) C(n+70) C(n+80) C(n+90)
#define C10(n) \
    C1(n+000) C1(n+100) C1(n+200) C1(n+300) C1(n+400) \
    C1(n+500) C1(n+600) C1(n+700) C1(n+800) C1(n+900)
    C10(1000)
    }
  return 0;
}

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #4)
> I see the change since r12-4726-g9a27acc30a34b785 which goes from 2.2s to
> 6.3s (checking enabled).

I would have said it's r12-7175-g0f58ba4dd6b25b

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Oh, and the dominated_by_p_w_unex issue is that we do

  if (succe && EDGE_COUNT (succe->dest->preds) == 1)
    {
      /* Verify the reached block is only reached through succe.
         If there is only one edge we can spare us the dominator
         check and iterate directly.  */
      if (EDGE_COUNT (succe->dest->preds) > 1)
        {
          FOR_EACH_EDGE (e, ei, succe->dest->preds)
            if (e != succe
                && ((e->flags & EDGE_EXECUTABLE)
                    || (!allow_back && (e->flags & EDGE_DFS_BACK))))
              {
                succe = NULL;
                break;
              }

where this is problematic because in the testcase with the switch stmt we have 
1000s of incoming edges into succe->dest.  I'm testing an easy workaround for
the testcase and the original case from bison.  A more general fix requires
some more work.

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
A real speed improvement to dominated_by_w_unex would record the single known
executable predecessor and successor of each block, for example in rpo_state,
but that's released before PRE eventually calls into it again via
eliminate_with_rpo_vn.  Some less hackish plumbing to manage lifetime is
necessary here.

[Bug tree-optimization/106809] [12/13 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:be1b42de9c151d46c89f9a8f82d4c5839a19ea94

commit r13-2375-gbe1b42de9c151d46c89f9a8f82d4c5839a19ea94
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 2 13:36:13 2022 +0200

    tree-optimization/106809 - compile time hog in VN

    The dominated_by_p_w_unex function is prone to high compile time.
    With GCC 12 we introduced a VN run for uninit diagnostics which now
    runs into a degenerate case with bison generated code.  Fortunately
    this case is easy to fix with a simple extra check - a more
    general fix needs more work.

            PR tree-optimization/106809
            * tree-ssa-sccvn.cc (dominaged_by_p_w_unex): Check we have
            more than one successor before doing extra work.

            * gcc.dg/torture/pr106809.c: New testcase.

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12/13 regression] large    |[12 regression] large bison
                   |bison grammars compilation  |grammars compilation got a
                   |got a lot slower, mainly    |lot slower, mainly due to
                   |due to -Wuninitialized      |-Wuninitialized
      Known to work|                            |13.0

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:e08dd36f90e74cd5be615b1ca82a38896434d48c

commit r12-8751-ge08dd36f90e74cd5be615b1ca82a38896434d48c
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 2 13:36:13 2022 +0200

    tree-optimization/106809 - compile time hog in VN

    The dominated_by_p_w_unex function is prone to high compile time.
    With GCC 12 we introduced a VN run for uninit diagnostics which now
    runs into a degenerate case with bison generated code.  Fortunately
    this case is easy to fix with a simple extra check - a more
    general fix needs more work.

            PR tree-optimization/106809
            * tree-ssa-sccvn.cc (dominaged_by_p_w_unex): Check we have
            more than one successor before doing extra work.

            * gcc.dg/torture/pr106809.c: New testcase.

    (cherry picked from commit be1b42de9c151d46c89f9a8f82d4c5839a19ea94)

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |12.2.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to work|                            |12.2.1

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:5125737077adc2110b9f17f06141e8f76ccab9b9

commit r11-10510-g5125737077adc2110b9f17f06141e8f76ccab9b9
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 2 13:36:13 2022 +0200

    tree-optimization/106809 - compile time hog in VN

    The dominated_by_p_w_unex function is prone to high compile time.
    With GCC 12 we introduced a VN run for uninit diagnostics which now
    runs into a degenerate case with bison generated code.  Fortunately
    this case is easy to fix with a simple extra check - a more
    general fix needs more work.

            PR tree-optimization/106809
            * tree-ssa-sccvn.c (dominaged_by_p_w_unex): Check we have
            more than one successor before doing extra work.

            * gcc.dg/torture/pr106809.c: New testcase.

    (cherry picked from commit be1b42de9c151d46c89f9a8f82d4c5839a19ea94)

[Bug tree-optimization/106809] [12 regression] large bison grammars compilation got a lot slower, mainly due to -Wuninitialized

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:051f78a5c1d6994c10ee7c35453ff0ccee94e5c6

commit r10-11201-g051f78a5c1d6994c10ee7c35453ff0ccee94e5c6
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 2 13:36:13 2022 +0200

    tree-optimization/106809 - compile time hog in VN

    The dominated_by_p_w_unex function is prone to high compile time.
    With GCC 12 we introduced a VN run for uninit diagnostics which now
    runs into a degenerate case with bison generated code.  Fortunately
    this case is easy to fix with a simple extra check - a more
    general fix needs more work.

            PR tree-optimization/106809
            * tree-ssa-sccvn.c (dominaged_by_p_w_unex): Check we have
            more than one successor before doing extra work.

            * gcc.dg/torture/pr106809.c: New testcase.

    (cherry picked from commit be1b42de9c151d46c89f9a8f82d4c5839a19ea94)