[Bug c/35608] imit-structnest.c fails due to O(n^2) memory usage in record_component_alias

[bonzini at gnu dot org]

------- Comment #8 from bonzini at gnu dot org  2009-11-03 12:18 -------
Memory allocation is O(n^2) in the nesting of the structures: when changing
LIM4 from 6 to 7 invocations of the lower-level, memory goes from 583976 KB to
798116 KB (which is 1.366 times more, almost exactly a factor of (7/6)^2).

The culprit is record_component_aliases which creates a subset relationship
from each structure to each containing structure.  Maybe we could reuse the
et-forest here since these subset relationships form a forest (do all of them
have this property? would we pessimize a lot by enforcing that even when it is
conservative?)

I suppose the bug has always been there since alias.c was introduced, it's just
that previously an unused struct did not call record_component_aliases.


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |compile-time-hog, memory-hog
   Last reconfirmed|0000-00-00 00:00:00         |2009-11-03 12:18:41
               date|                            |
            Summary|gcc.c-                      |imit-structnest.c fails due
                   |torture/compile/limits-     |to O(n^2) memory usage in
                   |structnest.c fails -O2 -Os  |record_component_alias


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