[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]

--- 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

[rguenth at gcc dot gnu dot org]

--- 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]

-- 

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

[Sebastian Pop]

 +      /* 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

[sebpop at gmail dot com]

--- 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

[rguenth at gcc dot gnu dot org]

--- 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

[rguenth at gcc dot gnu dot org]

--- 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

[rguenth at gcc dot gnu dot org]

--- 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