* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
@ 2023-03-15 12:44 ` rguenth at gcc dot gnu.org
2023-05-31 11:27 ` cvs-commit at gcc dot gnu.org
` (5 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-03-15 12:44 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
2023-03-15 12:44 ` [Bug tree-optimization/109143] " rguenth at gcc dot gnu.org
@ 2023-05-31 11:27 ` cvs-commit at gcc dot gnu.org
2023-05-31 12:33 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2023-05-31 11:27 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
2023-03-15 12:44 ` [Bug tree-optimization/109143] " rguenth at gcc dot gnu.org
2023-05-31 11:27 ` cvs-commit at gcc dot gnu.org
@ 2023-05-31 12:33 ` rguenth at gcc dot gnu.org
2023-06-06 8:30 ` cvs-commit at gcc dot gnu.org
` (3 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-05-31 12:33 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
` (2 preceding siblings ...)
2023-05-31 12:33 ` rguenth at gcc dot gnu.org
@ 2023-06-06 8:30 ` cvs-commit at gcc dot gnu.org
2023-06-23 10:29 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2023-06-06 8:30 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
` (3 preceding siblings ...)
2023-06-06 8:30 ` cvs-commit at gcc dot gnu.org
@ 2023-06-23 10:29 ` cvs-commit at gcc dot gnu.org
2023-11-27 11:34 ` cvs-commit at gcc dot gnu.org
2024-02-19 13:51 ` rguenth at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2023-06-23 10:29 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
` (4 preceding siblings ...)
2023-06-23 10:29 ` cvs-commit at gcc dot gnu.org
@ 2023-11-27 11:34 ` cvs-commit at gcc dot gnu.org
2024-02-19 13:51 ` rguenth at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2023-11-27 11:34 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 8+ messages in thread* [Bug tree-optimization/109143] PTA compile-time hog with many calls
2023-03-15 12:39 [Bug tree-optimization/109143] New: PTA compile-time hog with many calls rguenth at gcc dot gnu.org
` (5 preceding siblings ...)
2023-11-27 11:34 ` cvs-commit at gcc dot gnu.org
@ 2024-02-19 13:51 ` rguenth at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2024-02-19 13:51 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 8+ messages in thread