public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/18594] New: PHI insertion is slow
@ 2004-11-21 14:58 pinskia at gcc dot gnu dot org
2004-11-24 11:16 ` [Bug tree-optimization/18594] " steven at gcc dot gnu dot org
` (3 more replies)
0 siblings, 4 replies; 5+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-11-21 14:58 UTC (permalink / raw)
To: gcc-bugs
Using the program in PR 10060, to generate 1000 and 2000, I see that "PHI insertion" goes from:
tree PHI insertion : 4.44 (34%) usr 0.03 ( 1%) sys 5.46 (28%) wall
to
tree PHI insertion : 24.92 (48%) usr 1.78 (30%) sys 29.65 (49%) wall
which looks like PHI insertion does not scale.
--
Summary: PHI insertion is slow
Product: gcc
Version: 4.0.0
Status: UNCONFIRMED
Keywords: compile-time-hog
Severity: minor
Priority: P2
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: pinskia at gcc dot gnu dot org
CC: gcc-bugs at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18594
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/18594] PHI insertion is slow
2004-11-21 14:58 [Bug tree-optimization/18594] New: PHI insertion is slow pinskia at gcc dot gnu dot org
@ 2004-11-24 11:16 ` steven at gcc dot gnu dot org
2004-11-29 15:50 ` pinskia at gcc dot gnu dot org
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-11-24 11:16 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-11-24 11:16 -------
I think part of the problem is that PHI insertion is just
not a linear algorithm (iirc it's Nlog(N)).
--
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2004-11-24 11:16:37
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18594
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/18594] PHI insertion is slow
2004-11-21 14:58 [Bug tree-optimization/18594] New: PHI insertion is slow pinskia at gcc dot gnu dot org
2004-11-24 11:16 ` [Bug tree-optimization/18594] " steven at gcc dot gnu dot org
@ 2004-11-29 15:50 ` pinskia at gcc dot gnu dot org
2005-07-25 4:41 ` pinskia at gcc dot gnu dot org
2005-08-05 16:43 ` pinskia at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-11-29 15:50 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-11-29 15:50 -------
40% of the whole time is spent in compute_global_livein.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18594
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/18594] PHI insertion is slow
2004-11-21 14:58 [Bug tree-optimization/18594] New: PHI insertion is slow pinskia at gcc dot gnu dot org
2004-11-24 11:16 ` [Bug tree-optimization/18594] " steven at gcc dot gnu dot org
2004-11-29 15:50 ` pinskia at gcc dot gnu dot org
@ 2005-07-25 4:41 ` pinskia at gcc dot gnu dot org
2005-08-05 16:43 ` pinskia at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-25 4:41 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-25 04:28 -------
branch prediction : 4.63 (17%) usr 0.78 (16%) sys 5.57 (16%) wall 187672 kB (61%) ggc
Memory usage here is a big problem.
fold-const.c:2981 (invert_truthvalue) 36146592:15.8% 0: 0.0% 0: 0.0% 0:
0.0% 1004072
fold-const.c:10456 (fold_build2) 90093096:39.5% 0: 0.0% 0: 0.0% 0: 0.0%
2502586
tree-ssa-dom.c:1435 (build_and_record_new_cond) 685080: 0.3% 0: 0.0% 0: 0.0%
0: 0.0% 19030
tree-ssa-propagate.c:246 (add_ssa_edge) 0: 0.0% 89488: 0.3% 0: 0.0% 24464:
0.3% 28
tree-ssa-propagate.c:248 (add_ssa_edge) 0: 0.0% 5820032:22.3% 0: 0.0%
1577088:17.3% 36
Hmm, why is varying_ssa_edges in GC memory? Likewise for interesting_ssa_edges?
Unless someone wants tree-ssa-propagate.c to be able to call ggc_collect while propagating.
--
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |memory-hog
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18594
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug tree-optimization/18594] PHI insertion is slow
2004-11-21 14:58 [Bug tree-optimization/18594] New: PHI insertion is slow pinskia at gcc dot gnu dot org
` (2 preceding siblings ...)
2005-07-25 4:41 ` pinskia at gcc dot gnu dot org
@ 2005-08-05 16:43 ` pinskia at gcc dot gnu dot org
3 siblings, 0 replies; 5+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-08-05 16:43 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-08-05 16:43 -------
cfg.c:135 (alloc_block) 5933016: 0.5% 0: 0.0% 0: 0.0% 1561320: 0.6%
39033
bitmap.c:137 (bitmap_element_allocate) 35842644: 2.8% 0: 0.0% 0: 0.0%
3982516: 1.6% 995629
tree-ssa.c:68 (ssa_redirect_edge) 40800040: 3.1% 0: 0.0% 0: 0.0% 8160008:
3.3% 1020001
tree-ssanames.c:147 (make_ssa_name) 78280836: 6.0% 0: 0.0% 0: 0.0%
12360132: 5.1% 1030011
tree-ssa-loop-niter.c:653 (expand_simple_operati 119940000: 9.2% 0: 0.0% 0: 0.0%
23988000: 9.8% 1999000
tree-ssa-loop-niter.c:781 (tree_simplify_using_c 119940000: 9.2% 0: 0.0% 0: 0.0%
23988000: 9.8% 1999000
tree-ssa-loop-niter.c:786 (tree_simplify_using_c 119940000: 9.2% 0: 0.0% 0: 0.0%
23988000: 9.8% 1999000
fold-const.c:8993 (fold_binary) 120059940: 9.3% 0: 0.0% 0: 0.0% 24011988:
9.9% 2000999
tree-phinodes.c:156 (allocate_phi_node) 130048384:10.0% 0: 0.0% 0: 0.0% 0:
0.0% 1016003
fold-const.c:6517 (fold_to_nonsharp_ineq_using_b 239880000:18.5% 0: 0.0% 0: 0.0%
47976000:19.7% 3998000
fold-const.c:2980 (invert_truthvalue_1) 240484320:18.5% 0: 0.0% 0: 0.0%
48096864:19.7% 4008072
I wonder if we have an early loop optimization which removes empty loops there too.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18594
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2005-08-05 16:43 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-11-21 14:58 [Bug tree-optimization/18594] New: PHI insertion is slow pinskia at gcc dot gnu dot org
2004-11-24 11:16 ` [Bug tree-optimization/18594] " steven at gcc dot gnu dot org
2004-11-29 15:50 ` pinskia at gcc dot gnu dot org
2005-07-25 4:41 ` pinskia at gcc dot gnu dot org
2005-08-05 16:43 ` pinskia at gcc dot gnu dot 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).