Needs more than 2GB of ram at -O3.
Created attachment 17823 [details] unincluded testcase
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++) {
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.
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
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
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
Fixed on trunk and for 4.4.1 sofar.
Fixed.
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
*** Bug 41306 has been marked as a duplicate of this bug. ***