[Bug rtl-optimization/40761] New: IRA memory hog for insanely nested loops

[Bug rtl-optimization/40761] New: IRA memory hog for insanely nested loops

[bonzini at gnu dot org]

#define ONE     while (b())
#define TEN     ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE
#define HUN     TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOU    HUN HUN HUN HUN HUN HUN HUN HUN HUN HUN

void foo()
{
  /* 11,000 nested whiles.  */
  THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU
  a();
}

shows IRA taking 82% of compile-time wall time (25 seconds here at -O0) and
needing 1 GB of memory.  The reason why I'm reporting this, is that it seems to
be quadratic or at least well superlinear.  Changing it to 5500 loops requires
only 300 MB.

Not that it's the most important bug.


-- 
           Summary: IRA memory hog for insanely nested loops
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Keywords: memory-hog
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bonzini at gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[steven at gcc dot gnu dot org]

------- Comment #1 from steven at gcc dot gnu dot org  2009-07-15 07:21 -------
Ack.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-07-15 07:21:07
               date|                            |
            Summary|IRA memory hog for insanely |[4.4/4.5 Regression] IRA
                   |nested loops                |memory hog for insanely
                   |                            |nested loops


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[steven at gcc dot gnu dot org]

-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.5.0
      Known to work|                            |4.3.0
   Target Milestone|---                         |4.5.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-07-15 09:56 -------
Is it the nesting of loops or really the number of function calls that is
important?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |4.5.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[bonzini at gnu dot org]

------- Comment #3 from bonzini at gnu dot org  2009-07-15 11:11 -------
do while does not have the same behavior, so the loop "shape" is important. 
the following is as bad and does not have function calls.

#define ONE     while (x-- > y)
#define TEN     ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE
#define HUN     TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOU    HUN HUN HUN HUN HUN HUN HUN HUN HUN HUN

void foo(int x, int y)
{
  /* 11,000 nested whiles.  */
  THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU
  y++;
}


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[jsm28 at gcc dot gnu dot org]

-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[tkoenig at gcc dot gnu dot org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2152 bytes --]



------- Comment #4 from tkoenig at gcc dot gnu dot org  2010-03-01 19:27 -------
This now causes an ICE:

ig25@linux-fd1f:/tmp> cat haha.c
#define ONE     while (b())
#define TEN     ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE
#define HUN     TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOU    HUN HUN HUN HUN HUN HUN HUN HUN HUN HUN

void foo()
{
  /* 1,000 nested whiles.  */
  THOU
  a();
}
ig25@linux-fd1f:/tmp> gcc -O3 haha.c
haha.c: In Funktion »foo«:
haha.c:6:6: interner Compiler-Fehler: in compute_antic, bei tree-ssa-pre.c:2557
Bitte senden Sie einen vollständigen Fehlerbericht auf Englisch ein;
bearbeiten Sie die Quellen zunächst mit einem Präprozessor, wenn es
dienlich ist.
Fehler in der deutschen Übersetzung sind an
translation-team-de@lists.sourceforge.net zu melden.

Gehen Sie gemäß den Hinweisen in <http://gcc.gnu.org/bugs.html> vor.

Backtrace:

Breakpoint 1, fancy_abort (file=0xd791f0 "../../trunk/gcc/tree-ssa-pre.c",
line=2557,
    function=0xd799ed "compute_antic") at ../../trunk/gcc/diagnostic.c:728
728     {
(gdb) up
#1  0x00000000008ab23c in compute_antic () at
../../trunk/gcc/tree-ssa-pre.c:2557
2557          gcc_assert (num_iterations < 500);

The gcc_assert appears to be triggered for this case was introduced
by jakub:

118169    dberlin       }
137036      jakub #ifdef ENABLE_CHECKING
118821    dberlin       /* Theoretically possible, but *highly* unlikely.  */
137036      jakub       gcc_assert (num_iterations < 500);
137036      jakub #endif
 81764   dnovillo     }


Resetting to P3 for new triage, as this is now ice-on-valid-code.


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu dot
                   |                            |org, tkoenig at gcc dot gnu
                   |                            |dot org
           Keywords|                            |ice-on-valid-code
           Priority|P2                          |P3


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2010-03-03 15:42 -------
We shouldn't have deferred BB31 in the first iteration (with just TEN):

<bb 2>:
  goto <bb 13>;

...
<bb 31>:

<bb 13>:
  D.2759_1 = b ();
  if (D.2759_1 != 0)
    goto <bb 32>;
  else
    goto <bb 14>;

<bb 32>:
  goto <bb 12>;

<bb 14>:
  return;

Starting iteration 0
...
Block 31 was deferred for a future iteration.
ANTIC_OUT[14] := {  }
ANTIC_IN[14] := {  }
S[14] := {  }
ANTIC_OUT[13] := {  }
ANTIC_IN[13] := {  }
S[13] := {  }
ANTIC_OUT[2] := {  }
ANTIC_IN[2] := {  }
S[2] := {  }
Starting iteration 1

which means we are iterating in non-optimal order - which is postorder.
It looks like post_order_compute computes BS.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2010-03-03 15:59 -------
Mine.


-- 

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|NEW                         |ASSIGNED
   Last reconfirmed|2009-07-15 07:21:07         |2010-03-03 15:59:09
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2010-03-04 13:25 -------
Subject: Bug 40761

Author: rguenth
Date: Thu Mar  4 13:25:27 2010
New Revision: 157225

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157225
Log:
2010-03-04  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/40761
        * tree-ssa-pre.c (compute_antic): Walk reverse postorder
        in reverse order.
        (my_rev_post_order_compute): New function.
        (init_pre): Call it.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-pre.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2010-03-04 13:25 -------
PRE issue fixed for 4.5, still latent on the 4.4 branch.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[tkoenig at gcc dot gnu dot org]

------- Comment #9 from tkoenig at gcc dot gnu dot org  2010-03-04 19:40 -------
Should we also commit the test case from #4 ?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2010-03-05 10:17 -------
(In reply to comment #9)
> Should we also commit the test case from #4 ?

No.  It's too slow.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2010-04-06 11:20 -------
GCC 4.5.0 is being released.  Deferring to 4.5.1.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.0                       |4.5.1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761

[Bug rtl-optimization/40761] [4.4/4.5/4.6 Regression] IRA memory hog for insanely nested loops

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2010-07-31 09:29 -------
GCC 4.5.1 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.1                       |4.5.2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40761