public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time
@ 2014-08-28 13:08 rguenth at gcc dot gnu.org
2014-08-29 11:02 ` [Bug tree-optimization/62291] " steven at gcc dot gnu.org
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-08-28 13:08 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
Bug ID: 62291
Summary: PRE uses too much memory and compile-time
Product: gcc
Version: 4.9.1
Status: UNCONFIRMED
Keywords: compile-time-hog, memory-hog
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: rguenth at gcc dot gnu.org
Blocks: 47344
Created attachment 33409
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33409&action=edit
preprocessed testcase
For the attached testcase (from GHC) PRE blows up memory and compile-time wise
at -O2, -O2 -fno-tree-pre and -O1 are fine.
Usual suspect is AVAIL_OUT which was only eliminated for FRE.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/62291] PRE uses too much memory and compile-time
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
@ 2014-08-29 11:02 ` steven at gcc dot gnu.org
2014-08-29 12:40 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: steven at gcc dot gnu.org @ 2014-08-29 11:02 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
Steven Bosscher <steven at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Last reconfirmed| |2014-08-29
Ever confirmed|0 |1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/62291] PRE uses too much memory and compile-time
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
2014-08-29 11:02 ` [Bug tree-optimization/62291] " steven at gcc dot gnu.org
@ 2014-08-29 12:40 ` rguenth at gcc dot gnu.org
2014-08-29 12:51 ` rguenth at gcc dot gnu.org
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-08-29 12:40 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Aug 29 12:39:50 2014
New Revision: 214727
URL: https://gcc.gnu.org/viewcvs?rev=214727&root=gcc&view=rev
Log:
2014-08-29 Richard Biener <rguenther@suse.de>
PR tree-optimization/62291
* tree-ssa-pre.c (sorted_array_from_bitmap_set): Reserve
exactly the vector size needed and use quick_push.
(phi_translate_1): Adjust comment.
(valid_in_sets): Remove block argument and remove pointless
checking of NAMEs.
(dependent_clean): Adjust for removal of block argument.
(clean): Likewise.
(compute_antic_aux): Likewise.
(compute_partial_antic_aux): Likewise.
Modified:
trunk/gcc/ChangeLog
trunk/gcc/tree-ssa-pre.c
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/62291] PRE uses too much memory and compile-time
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
2014-08-29 11:02 ` [Bug tree-optimization/62291] " steven at gcc dot gnu.org
2014-08-29 12:40 ` rguenth at gcc dot gnu.org
@ 2014-08-29 12:51 ` rguenth at gcc dot gnu.org
2014-09-01 13:31 ` rguenth at gcc dot gnu.org
2023-09-28 7:29 ` [Bug tree-optimization/62291] tree " rguenth at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-08-29 12:51 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
As said in the mail for the just applied patch:
"The second patch (once done) will refactor insertion phase
to do a dominator walk similar to what elimination does
computing AVAIL_OUT on-the-fly (and only keeping it live
for a single block). It's a bit more complicated than
for elimination as insertion looks at a block and all its
predecessors, it's also a bit more costly as we iterate
insertion. It's also more costly because computing
AVAIL_OUT on-the-fly requires looking at all statements
which insertion currently doesn't do at all.
So I've not yet settled on a final idea how to best re-factor it,
eventually insertion and elimination can be merged (and then
still iterate(?)).
Ideas welcome ;)"
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/62291] PRE uses too much memory and compile-time
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
` (2 preceding siblings ...)
2014-08-29 12:51 ` rguenth at gcc dot gnu.org
@ 2014-09-01 13:31 ` rguenth at gcc dot gnu.org
2023-09-28 7:29 ` [Bug tree-optimization/62291] tree " rguenth at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2014-09-01 13:31 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So what remains is insertion computing whether a value is available on some
predecessor (partial redundancy) or all (full redundancy) which needs AVAIL_OUT
for the predecessors and the immediate dominator.
Then the actual insertion code needs to lookup leaders for expression operands
it wants to insert. I think this part can be easily delayed until eliminate
if we store all necessary information in some new data structure.
The first part is harder - especially as it is that what needs to be iterated
(with taking into account newly inserted stuff). One could imagine
iterating over sucessors of a block (and immediate dominated-bys) and compute
"candidate" sets, both pruning and extending it during the iteration.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/62291] tree PRE uses too much memory and compile-time
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
` (3 preceding siblings ...)
2014-09-01 13:31 ` rguenth at gcc dot gnu.org
@ 2023-09-28 7:29 ` rguenth at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-28 7:29 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Summary|PRE uses too much memory |tree PRE uses too much
|and compile-time |memory and compile-time
Known to work| |10.1.0, 11.1.0, 12.1.0,
| |13.1.0
--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
On a Ryzen 9 7900X I get with GCC 13.2
-O0 1.4s 430MB
-O1 17.4s 640MB
-O2 26.9s 822MB
-O2 -fdisable-tree-pre 22.3s 690MB
-O3 26.9s 824MB
it's now far from blowing up (in PRE). GCC 5.5 needs 3.5GB of memory, GCC 7
needs 5.5GB. I can't really reproduce high compile-time even with 4.9.5.
The problem that AVAIL_OUT compute requires quadratic memory isn't solved.
-ftime-report with GCC 13.2 shows
alias stmt walking : 8.42 ( 31%) 0.17 ( 18%) 8.29 ( 29%)
4743k ( 1%)
tree PTA : 7.74 ( 28%) 0.20 ( 22%) 7.95 ( 28%)
2706k ( 1%)
tree PRE : 0.29 ( 1%) 0.01 ( 1%) 0.31 ( 1%)
23M ( 4%)
and with -details
tree PRE : 0.29 ( 1%) 0.00 ( 0%) 0.34 ( 1%)
23M ( 4%)
`- tree tail merge : 0.02 ( 0%) 0.00 ( 0%) 0.03 ( 0%)
0 ( 0%)
`- loop init : 0.01 ( 0%) 0.00 ( 0%) 0.00 ( 0%)
0 ( 0%)
`- tree PTA : 2.64 ( 10%) 0.05 ( 6%) 2.69 ( 9%)
604k ( 0%)
`- alias stmt walking : 2.02 ( 7%) 0.04 ( 5%) 2.01 ( 7%)
1185k ( 0%)
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2023-09-28 7:29 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-08-28 13:08 [Bug tree-optimization/62291] New: PRE uses too much memory and compile-time rguenth at gcc dot gnu.org
2014-08-29 11:02 ` [Bug tree-optimization/62291] " steven at gcc dot gnu.org
2014-08-29 12:40 ` rguenth at gcc dot gnu.org
2014-08-29 12:51 ` rguenth at gcc dot gnu.org
2014-09-01 13:31 ` rguenth at gcc dot gnu.org
2023-09-28 7:29 ` [Bug tree-optimization/62291] tree " rguenth at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).