public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
@ 2009-05-07 16:07 rguenth at gcc dot gnu dot org
2009-05-07 16:08 ` [Bug tree-optimization/40062] " rguenth at gcc dot gnu dot org
` (10 more replies)
0 siblings, 11 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-07 16:07 UTC (permalink / raw)
To: gcc-bugs
Needs more than 2GB of ram at -O3.
--
Summary: [4.3/4.4/4.5 Regression] high memory usage and compile
time in SCEV cprop with -O3
Product: gcc
Version: 4.4.1
Status: UNCONFIRMED
Keywords: memory-hog, compile-time-hog
Severity: normal
Priority: P3
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: rguenth at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
@ 2009-05-07 16:08 ` rguenth at gcc dot gnu dot org
2009-05-08 9:48 ` rguenth at gcc dot gnu dot org
` (9 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-07 16:08 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from rguenth at gcc dot gnu dot org 2009-05-07 16:08 -------
Created an attachment (id=17823)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=17823&action=view)
unincluded testcase
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
2009-05-07 16:08 ` [Bug tree-optimization/40062] " rguenth at gcc dot gnu dot org
@ 2009-05-08 9:48 ` rguenth at gcc dot gnu dot org
2009-05-08 9:52 ` rguenth at gcc dot gnu dot org
` (8 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 9:48 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from rguenth at gcc dot gnu dot org 2009-05-08 09:47 -------
The issue is that with follow_ssa_edge_in_condition_phi we end up with
exponential time and space complexity because we have several PHI nodes
in our chain that have a large number of PHI arguments.
The following fixes it
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c (revision 147237)
+++ tree-scalar-evolution.c (working copy)
@@ -1320,10 +1320,12 @@ follow_ssa_edge_in_condition_phi (struct
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
+ /* If the phi node is just a copy, do not increase the limit, otherwise
+ increase it by the number of PHI arguments to avoid exponential
+ complexity. */
n = gimple_phi_num_args (condition_phi);
- if (n > 1)
- limit++;
+ limit += n - 1;
+
for (i = 1; i < n; i++)
{
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |spop at gcc dot gnu dot org
Target Milestone|--- |4.3.4
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
2009-05-07 16:08 ` [Bug tree-optimization/40062] " rguenth at gcc dot gnu dot org
2009-05-08 9:48 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 9:52 ` rguenth at gcc dot gnu dot org
2009-05-08 12:12 ` Sebastian Pop
2009-05-08 10:10 ` rguenth at gcc dot gnu dot org
` (7 subsequent siblings)
10 siblings, 1 reply; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 9:52 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from rguenth at gcc dot gnu dot org 2009-05-08 09:52 -------
Or rather
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c (revision 147237)
+++ tree-scalar-evolution.c (working copy)
@@ -1320,11 +1320,7 @@ follow_ssa_edge_in_condition_phi (struct
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
n = gimple_phi_num_args (condition_phi);
- if (n > 1)
- limit++;
-
for (i = 1; i < n; i++)
{
/* Quickly give up when the evolution of one of the branches is
@@ -1332,10 +1328,12 @@ follow_ssa_edge_in_condition_phi (struct
if (*evolution_of_loop == chrec_dont_know)
return t_true;
+ /* Increase the limit by the PHI argument number to avoid exponential
+ time and memory complexity. */
res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
- init, limit);
+ init, limit + i);
if (res == t_false || res == t_dont_know)
return res;
which more follows the logic of using the original limit for the walk
of argument zero.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (2 preceding siblings ...)
2009-05-08 9:52 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 10:10 ` rguenth at gcc dot gnu dot org
2009-05-08 12:12 ` sebpop at gmail dot com
` (6 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 10:10 UTC (permalink / raw)
To: gcc-bugs
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |rguenth at gcc dot gnu dot
|dot org |org
Status|UNCONFIRMED |ASSIGNED
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2009-05-08 10:10:19
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (3 preceding siblings ...)
2009-05-08 10:10 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 12:12 ` sebpop at gmail dot com
2009-05-08 12:25 ` rguenth at gcc dot gnu dot org
` (5 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: sebpop at gmail dot com @ 2009-05-08 12:12 UTC (permalink / raw)
To: gcc-bugs
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 425 bytes --]
------- Comment #4 from sebpop at gmail dot com 2009-05-08 12:12 -------
Subject: Re: [4.3/4.4/4.5 Regression] high
memory usage and compile time in SCEV cprop with -O3
> + Â Â Â /* Increase the limit by the PHI argument number to avoid exponential
> + Â Â Â Â time and memory complexity. Â */
This looks good.
Thanks,
Sebastian
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-08 9:52 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 12:12 ` Sebastian Pop
0 siblings, 0 replies; 13+ messages in thread
From: Sebastian Pop @ 2009-05-08 12:12 UTC (permalink / raw)
To: gcc-bugzilla; +Cc: gcc-bugs
> + /* Increase the limit by the PHI argument number to avoid exponential
> + time and memory complexity. */
This looks good.
Thanks,
Sebastian
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (4 preceding siblings ...)
2009-05-08 12:12 ` sebpop at gmail dot com
@ 2009-05-08 12:25 ` rguenth at gcc dot gnu dot org
2009-05-08 12:28 ` rguenth at gcc dot gnu dot org
` (4 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 12:25 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from rguenth at gcc dot gnu dot org 2009-05-08 12:24 -------
Subject: Bug 40062
Author: rguenth
Date: Fri May 8 12:24:22 2009
New Revision: 147283
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=147283
Log:
2009-05-08 Richard Guenther <rguenther@suse.de>
PR tree-optimization/40062
* tree-scalar-evolution.c (follow_ssa_edge_in_condition_phi):
Avoid exponential behavior.
Modified:
trunk/gcc/ChangeLog
trunk/gcc/tree-scalar-evolution.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (5 preceding siblings ...)
2009-05-08 12:25 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 12:28 ` rguenth at gcc dot gnu dot org
2009-05-08 12:39 ` [Bug tree-optimization/40062] [4.3 " rguenth at gcc dot gnu dot org
` (3 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 12:28 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from rguenth at gcc dot gnu dot org 2009-05-08 12:28 -------
Subject: Bug 40062
Author: rguenth
Date: Fri May 8 12:28:01 2009
New Revision: 147284
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=147284
Log:
2009-05-08 Richard Guenther <rguenther@suse.de>
PR tree-optimization/40062
* tree-scalar-evolution.c (follow_ssa_edge_in_condition_phi):
Avoid exponential behavior.
Modified:
branches/gcc-4_4-branch/gcc/ChangeLog
branches/gcc-4_4-branch/gcc/tree-scalar-evolution.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (6 preceding siblings ...)
2009-05-08 12:28 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 12:39 ` rguenth at gcc dot gnu dot org
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
` (2 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 12:39 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from rguenth at gcc dot gnu dot org 2009-05-08 12:39 -------
Fixed on trunk and for 4.4.1 sofar.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to fail| |4.3.3 4.4.0
Known to work| |4.4.1 4.5.0
Summary|[4.3/4.4/4.5 Regression] |[4.3 Regression] high memory
|high memory usage and |usage and compile time in
|compile time in SCEV cprop |SCEV cprop with -O3
|with -O3 |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (7 preceding siblings ...)
2009-05-08 12:39 ` [Bug tree-optimization/40062] [4.3 " rguenth at gcc dot gnu dot org
@ 2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
2009-09-08 13:44 ` rguenth at gcc dot gnu dot org
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 14:14 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from rguenth at gcc dot gnu dot org 2009-05-08 14:14 -------
Fixed.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (8 preceding siblings ...)
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
@ 2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
2009-09-08 13:44 ` rguenth at gcc dot gnu dot org
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-05-08 14:14 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from rguenth at gcc dot gnu dot org 2009-05-08 14:14 -------
Subject: Bug 40062
Author: rguenth
Date: Fri May 8 14:14:25 2009
New Revision: 147288
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=147288
Log:
2009-05-08 Richard Guenther <rguenther@suse.de>
PR tree-optimization/40062
* tree-scalar-evolution.c (follow_ssa_edge_in_condition_phi):
Avoid exponential behavior.
Modified:
branches/gcc-4_3-branch/gcc/ChangeLog
branches/gcc-4_3-branch/gcc/tree-scalar-evolution.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
` (9 preceding siblings ...)
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
@ 2009-09-08 13:44 ` rguenth at gcc dot gnu dot org
10 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-09-08 13:44 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from rguenth at gcc dot gnu dot org 2009-09-08 13:43 -------
*** Bug 41306 has been marked as a duplicate of this bug. ***
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |m dot hermes at uu dot nl
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2009-09-08 13:44 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-05-07 16:07 [Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3 rguenth at gcc dot gnu dot org
2009-05-07 16:08 ` [Bug tree-optimization/40062] " rguenth at gcc dot gnu dot org
2009-05-08 9:48 ` rguenth at gcc dot gnu dot org
2009-05-08 9:52 ` rguenth at gcc dot gnu dot org
2009-05-08 12:12 ` Sebastian Pop
2009-05-08 10:10 ` rguenth at gcc dot gnu dot org
2009-05-08 12:12 ` sebpop at gmail dot com
2009-05-08 12:25 ` rguenth at gcc dot gnu dot org
2009-05-08 12:28 ` rguenth at gcc dot gnu dot org
2009-05-08 12:39 ` [Bug tree-optimization/40062] [4.3 " rguenth at gcc dot gnu dot org
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
2009-05-08 14:14 ` rguenth at gcc dot gnu dot org
2009-09-08 13:44 ` rguenth 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).