[Bug ipa/104203] New: [12 Regressions] huge IPA compile-time regression

[Bug ipa/104203] New: [12 Regressions] huge IPA compile-time regression

[rguenth at gcc dot gnu.org]

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

            Bug ID: 104203
           Summary: [12 Regressions] huge IPA compile-time regression
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: ipa
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
                CC: marxin at gcc dot gnu.org
  Target Milestone: ---

https://gcc.opensuse.org/gcc-old/c++bench-czerny/random/

shows huge IPA regressions at -O0+ for the PR63155-[12].c and PR91257.c
testcases

 callgraph optimization             :  60.42 ( 85%)   0.01 (  3%)  60.43 ( 85%)
   15k (  0%)
 callgraph ipa passes               :  64.10 ( 90%)   0.12 ( 36%)  64.23 ( 90%)
  695M ( 97%)

just like the above.

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52275
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52275&action=edit
testcase

Happened during the outage that lasted through most of the holidays.  I've
attached the smallest of the three testcases.

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |12.0

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11 takes ~10s to compile this at -O0 while trunk takes ~60s for me.

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression since r12-6606-g9d6a0f388eb048f8

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-01-24
            Summary|[12 Regressions] huge IPA   |[12 Regressions] huge IPA
                   |compile-time regression     |compile-time regression
                   |                            |since
                   |                            |r12-6606-g9d6a0f388eb048f8
                 CC|                            |msebor at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r12-6606-g9d6a0f388eb048f8.

Re: [Bug ipa/104203] [12 Regressions] huge IPA compile-time regression since r12-6606-g9d6a0f388eb048f8

[Jan Hubicka]

So I assume that this is due to new pass_waccess which was added into
early optimizations.  I think this is not really ipa component but
tree-optimize.

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression since r12-6606-g9d6a0f388eb048f8

[hubicka at kam dot mff.cuni.cz]

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

--- Comment #4 from hubicka at kam dot mff.cuni.cz ---
So I assume that this is due to new pass_waccess which was added into
early optimizations.  I think this is not really ipa component but
tree-optimize.

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression since r12-6606-g9d6a0f388eb048f8

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
I guess TV_NONE is unlucky in picking whatever is there (the wrapping IPA
pass).

Martin, can you add a new timevar to timevar.def and use that in
pass_data_waccess please?

Note with -w the compile-time regression is _not_ fixed.  We have

bool
pass_waccess::gate (function *)
{
  return (warn_free_nonheap_object
          || warn_mismatched_alloc
          || warn_mismatched_new_delete);
}

but it seems -w doesn't disable those?  Only -Wno-free-nonheap-object works
here :/  (I guess there might be a bug about -w not disabling warnings enabled
by default)

[Bug ipa/104203] [12 Regressions] huge IPA compile-time regression since r12-6606-g9d6a0f388eb048f8

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
I suspect it's PHI handling where we branch off arguments but do not appear to
have caching on visited items so when the CFG merges again we process the merge
point N times which quickly grows to exponential behavior.

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression since r12-6606-g9d6a0f388eb048f8

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |msebor at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression since r12-6606-g9d6a0f388eb048f8

[msebor at gcc dot gnu.org]

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

--- Comment #7 from Martin Sebor <msebor at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
...
> Martin, can you add a new timevar to timevar.def and use that in
> pass_data_waccess please?

Will do.  The bottleneck is the PHI handling in the access warning pass:

 access analysis                    : 242.88 ( 75%)   0.02 (  7%) 243.12 ( 75%)
   29k (  0%)

There are thousands of basic blocks each with thousands of PHI nodes that all
reference each other like this:

  <bb 5> [local count: 354193067]:
  # v0_3233(ab) = PHI <v0_1065754(D)(ab)(4), v0_3234(ab)(6)>
  # v1_4045(ab) = PHI <v1_1065755(D)(ab)(4), v1_4046(ab)(6)>
  # v2_4857(ab) = PHI <v2_1065756(D)(ab)(4), v2_4858(ab)(6)>
  ...
  <bb 6> [local count: 177676792]:
  # v0_3234(ab) = PHI <v0_1065754(D)(ab)(3), v0_3233(ab)(5), v0_3233(ab)(8),
..., v0_4044(ab)(5251), v0_4044(ab)(5252), v0_4044(ab)(5253)> 
  # v1_4046(ab) = PHI <v1_1065755(D)(ab)(3), v1_4045(ab)(5), v1_4045(ab)(8),
..., v1_4856(ab)(5251), v1_4856(ab)(5252), v1_4856(ab)(5253)>
  ...

The access pass has a limit on recursive PHIs but none on this sort of thing. 
Let me see what might be a good way to detect this pattern and limit the
processing.

> 
> Note with -w the compile-time regression is _not_ fixed.  We have
> 
> bool
> pass_waccess::gate (function *)
> {
>   return (warn_free_nonheap_object
>           || warn_mismatched_alloc
>           || warn_mismatched_new_delete);
> }
> 
> but it seems -w doesn't disable those?  Only -Wno-free-nonheap-object works
> here :/  (I guess there might be a bug about -w not disabling warnings
> enabled by default)

Since the pass issues a bunch other warnings (e.g., -Wstringop-overflow,
-Wuse-after-free, etc.) the gate doesn't seem right.  But since #pragma GCC
diagnostic can re-enable warnings disabled by -w (or turn them into errors) any
gate that considers the global option setting will also interfere with that.

Re: [Bug tree-optimization/104203] [12 Regressions] huge compile-time regression since r12-6606-g9d6a0f388eb048f8

[Jan Hubicka]

> > bool
> Since the pass issues a bunch other warnings (e.g., -Wstringop-overflow,
> -Wuse-after-free, etc.) the gate doesn't seem right.  But since #pragma GCC
> diagnostic can re-enable warnings disabled by -w (or turn them into errors) any
> gate that considers the global option setting will also interfere with that.

What the gate is executed the flags are set according to cfun, so you
can just combine all warning options for warnings issued by the pass
into the gate.

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression since r12-6606-g9d6a0f388eb048f8

[hubicka at kam dot mff.cuni.cz]

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

--- Comment #8 from hubicka at kam dot mff.cuni.cz ---
> > bool
> Since the pass issues a bunch other warnings (e.g., -Wstringop-overflow,
> -Wuse-after-free, etc.) the gate doesn't seem right.  But since #pragma GCC
> diagnostic can re-enable warnings disabled by -w (or turn them into errors) any
> gate that considers the global option setting will also interfere with that.

What the gate is executed the flags are set according to cfun, so you
can just combine all warning options for warnings issued by the pass
into the gate.

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression since r12-6606-g9d6a0f388eb048f8

[msebor at gcc dot gnu.org]

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

--- Comment #9 from Martin Sebor <msebor at gcc dot gnu.org> ---
The underlying problem is that when the pointer_query class fails to determine
the pointer provenance for an SSA variable it doesn't update the cache, matter
how laborious the computation was.  The next time the same SSA variable is
seen, the query goes through the same computation only to eventually fail
again.  Caching a permissive result instead of failing short-circuits this
process and avoids the bottleneck.

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression in pointer_query since r12-6606-g9d6a0f388eb048f8

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12 Regressions] huge       |[12 Regressions] huge
                   |compile-time regression     |compile-time regression in
                   |since                       |pointer_query since
                   |r12-6606-g9d6a0f388eb048f8  |r12-6606-g9d6a0f388eb048f8
           Keywords|                            |patch

--- Comment #10 from Martin Sebor <msebor at gcc dot gnu.org> ---
Patch: https://gcc.gnu.org/pipermail/gcc-patches/2022-January/589199.html

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression in pointer_query since r12-6606-g9d6a0f388eb048f8

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Martin Sebor <msebor@gcc.gnu.org>:

https://gcc.gnu.org/g:58ec0964b1d2f2ab197916cd661728f6a7a1736b

commit r12-6869-g58ec0964b1d2f2ab197916cd661728f6a7a1736b
Author: Martin Sebor <msebor@redhat.com>
Date:   Tue Jan 25 14:20:51 2022 -0700

    Avoid recomputing PHI results after failure (PR104203).

    Resolves:
    PR tree-optimization/104203 - huge compile-time regression in pointer_query

    gcc/ChangeLog:

            PR tree-optimization/104203
            * gimple-ssa-warn-access.cc (pass_data pass_data_waccess): Use
            TV_WARN_ACCESS.
            * pointer-query.cc (access_ref::merge_ref): Change return type.
            Convert failure to a conservative success.
            (access_ref::get_ref): Adjust to the change above.  Short-circuit
            PHI evaluation after first failure turned into conservative
success.
            * pointer-query.h (access_ref::merge_ref): Change return type.
            * timevar.def (TV_WARN_ACCESS): New timer variable.

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression in pointer_query since r12-6606-g9d6a0f388eb048f8

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

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

--- Comment #12 from Martin Sebor <msebor at gcc dot gnu.org> ---
(In reply to hubicka from comment #8)
>
> What the gate is executed the flags are set according to cfun, so you
> can just combine all warning options for warnings issued by the pass
> into the gate.

Thanks, let me look into it.

r12-6869 should resolve the compile-time regression by bringing the timings
from:

 access analysis                    : 242.88 ( 75%)   0.02 (  7%) 243.12 ( 75%)
   29k (  0%)

to:

 access analysis                    :   2.71 (  3%)   0.04 ( 10%)   2.76 (  3%)
   29k (  0%)

[Bug tree-optimization/104203] [12 Regressions] huge compile-time regression in pointer_query since r12-6606-g9d6a0f388eb048f8

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
I can confirm the issue is fixed for all three cases I saw it.  Thanks for the
quick fix.