[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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
[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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
[Bug tree-optimization/40062] [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 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|-00-00 00:00:00 |2009-05-08 10:10:19 date|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062
Re: [Bug tree-optimization/40062] [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
[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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
[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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=gccview=revrev=147283 Log: 2009-05-08 Richard Guenther rguent...@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
[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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=gccview=revrev=147284 Log: 2009-05-08 Richard Guenther rguent...@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
[Bug tree-optimization/40062] [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3
--- 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=17823action=view) unincluded testcase -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40062