[Bug tree-optimization/40062] New: [4.3/4.4/4.5 Regression] high memory usage and compile time in SCEV cprop with -O3

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

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

[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=17823&action=view)
unincluded testcase


-- 


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 #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|0000-00-00 00:00:00         |2009-05-08 10:10:19
               date|                            |


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

[sebpop at gmail dot com]

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

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

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

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

[Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/40062] [4.3 Regression] high memory usage and compile time in SCEV cprop with -O3

[rguenth at gcc dot gnu dot org]

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