[Bug tree-optimization/109143] New: PTA compile-time hog with many calls

[Bug tree-optimization/109143] New: PTA compile-time hog with many calls

[rguenth at gcc dot gnu.org]

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

            Bug ID: 109143
           Summary: PTA compile-time hog with many calls
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

Here's another testcase that made me produce r13-6584-g413ec1d12c50f8 but which
is still slow in PTA.

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Last reconfirmed|                            |2023-03-15

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

Here's the testcase unincluded, it can at least build with GCC 12 and 13.

The main issue is the ESCAPED set leaking into many sets, but not directly
but rather sets getting bigger and eventually also get ESCAPED but common
members are not pruned, so ESCAPED isn't optimally used as representative
for its contents.

GCC 12.2.1 shows

 tree PTA                           : 227.39 ( 93%)   0.40 ( 23%) 227.78 ( 92%)
 7617k (  1%)
 TOTAL                              : 245.51          1.72        247.33       
 1128M

while recent trunk is improved to around 70s for tree PTA.  Forcefully
pruning ESCAPED bits from sets containing ESCAPED gets it down to 3s.

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[cvs-commit at gcc dot gnu.org]

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

--- Comment #2 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:95e5c38a98cc64a797b1d766a20f8c0d0c807a74

commit r14-1429-g95e5c38a98cc64a797b1d766a20f8c0d0c807a74
Author: Richard Biener <rguenther@suse.de>
Date:   Wed May 31 12:07:42 2023 +0200

    ipa/109983 - (IPA) PTA speedup

    This improves the edge avoidance heuristic by re-ordering the
    topological sort of the graph to make sure the component with
    the ESCAPED node is processed first.  This improves the number
    of created edges which directly correlates with the number
    of bitmap_ior_into calls from 141447426 to 239596 and the
    compile-time from 1083s to 3s.  It also improves the compile-time
    for the related PR109143 from 81s to 27s.

    I've modernized the topological sorting API on the way as well.

            PR ipa/109983
            PR tree-optimization/109143
            * tree-ssa-structalias.cc (struct topo_info): Remove.
            (init_topo_info): Likewise.
            (free_topo_info): Likewise.
            (compute_topo_order): Simplify API, put the component
            with ESCAPED last so it's processed first.
            (topo_visit): Adjust.
            (solve_graph): Likewise.

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's now at 27s on trunk.

 callgraph ipa passes               :   6.04 ( 22%)   0.24 ( 16%)   6.28 ( 22%)
  184M ( 17%)
 tree PTA                           :  10.28 ( 37%)   0.16 ( 11%)  10.38 ( 36%)
   10M (  1%)
 integrated RA                      :   1.34 (  5%)   0.00 (  0%)   1.29 (  4%)
   37M (  3%)
 TOTAL                              :  27.65          1.49         29.15       
 1084M


Samples: 115K of event 'cycles:u', Event count (approx.): 148070760732          
Overhead       Samples  Command  Shared Object       Symbol                     
  10.03%         11250  cc1plus  cc1plus             [.] bitmap_set_bit
   9.38%         10648  cc1plus  cc1plus             [.] solve_constraints
   6.12%          6847  cc1plus  cc1plus             [.]
find_what_var_points_to
   4.52%          5092  cc1plus  cc1plus             [.] bitmap_bit_p
   2.27%          2520  cc1plus  cc1plus             [.] bitmap_ior_into
   2.14%          2429  cc1plus  cc1plus             [.] solution_set_expand


from bitmap_set_bit the worst bitmaps are (searches vs. walk steps)

tree-ssa-structalias.cc:6798 (find_what_var_poin        13M:  0.9%       13M   
 1056k:  0.9%        137k        222k      heap

it's by far the most bit-operated on bitmap and the order bits are set
are somewhat random.  solve_constraints () re-orders vars to make
bitmaps less sparse but it fails to order them according to DECL_UID.

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:21bf2b2fd99d7a94049610fc2f82db77f725d025

commit r14-1561-g21bf2b2fd99d7a94049610fc2f82db77f725d025
Author: Richard Biener <rguenther@suse.de>
Date:   Wed May 31 14:28:37 2023 +0200

    tree-optimization/109143 - improve PTA compile time

    The following improves solution_set_expand to require one less
    iteration over the bitmap and avoid changing the bitmap we iterate
    over.  Plus we handle adjacent subvars in the ID space (the common case)
    and use bitmap_set_range.  This cuts a bit less than 10% off the PTA
    time from the testcase in the PR.

            PR tree-optimization/109143
            * tree-ssa-structalias.cc (solution_set_expand): Avoid
            one bitmap iteration and optimize bit range setting.

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r13-7466-ga737da4885b7038fdd7d6646deaa1644efff2257
Author: Richard Biener <rguenther@suse.de>
Date:   Wed May 31 12:07:42 2023 +0200

    ipa/109983 - (IPA) PTA speedup

    This improves the edge avoidance heuristic by re-ordering the
    topological sort of the graph to make sure the component with
    the ESCAPED node is processed first.  This improves the number
    of created edges which directly correlates with the number
    of bitmap_ior_into calls from 141447426 to 239596 and the
    compile-time from 1083s to 3s.  It also improves the compile-time
    for the related PR109143 from 81s to 27s.

    I've modernized the topological sorting API on the way as well.

            PR ipa/109983
            PR tree-optimization/109143
            * tree-ssa-structalias.cc (struct topo_info): Remove.
            (init_topo_info): Likewise.
            (free_topo_info): Likewise.
            (compute_topo_order): Simplify API, put the component
            with ESCAPED last so it's processed first.
            (topo_visit): Adjust.
            (solve_graph): Likewise.

    (cherry picked from commit 95e5c38a98cc64a797b1d766a20f8c0d0c807a74)

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from GCC 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:5a381334e2b0faac75c059504155aa4a8f8809ac

commit r12-10005-g5a381334e2b0faac75c059504155aa4a8f8809ac
Author: Richard Biener <rguenther@suse.de>
Date:   Wed May 31 12:07:42 2023 +0200

    ipa/109983 - (IPA) PTA speedup

    This improves the edge avoidance heuristic by re-ordering the
    topological sort of the graph to make sure the component with
    the ESCAPED node is processed first.  This improves the number
    of created edges which directly correlates with the number
    of bitmap_ior_into calls from 141447426 to 239596 and the
    compile-time from 1083s to 3s.  It also improves the compile-time
    for the related PR109143 from 81s to 27s.

    I've modernized the topological sorting API on the way as well.

            PR ipa/109983
            PR tree-optimization/109143
            * tree-ssa-structalias.cc (struct topo_info): Remove.
            (init_topo_info): Likewise.
            (free_topo_info): Likewise.
            (compute_topo_order): Simplify API, put the component
            with ESCAPED last so it's processed first.
            (topo_visit): Adjust.
            (solve_graph): Likewise.

    (cherry picked from commit 95e5c38a98cc64a797b1d766a20f8c0d0c807a74)

[Bug tree-optimization/109143] PTA compile-time hog with many calls

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2023-03-15 00:00:00         |2024-2-19

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
With GCC 14 at -O1:

 template instantiation             :   0.90 (  8%)
 tree PTA                           :   0.51 (  5%)
 TOTAL                              :  11.14 

and with -O2:

 callgraph ipa passes               :   5.76 ( 19%)
 tree PTA                           :   9.42 ( 31%)
 integrated RA                      :   1.79 (  6%)
 TOTAL                              :  30.72