[Bug lto/48978] New: excessive hash table allocation for large lto build

[Bug lto/48978] New: excessive hash table allocation for large lto build

[andi-gcc at firstfloor dot org]

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

           Summary: excessive hash table allocation for large lto build
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: lto
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: andi-gcc@firstfloor.org


I tried a large LTO build with gcc version 4.7.0 20110511 (experimental) (GCC) 
on a 18GB machine. It ended with

lto1: out of memory allocating 8589934312 bytes after a total of 6827421696
bytes

Since a 7+GB single malloc seems somewhat excessive I put a break point 
on xmalloc_failed. It looks like the hash tables are growing
too aggressively?


#0  xmalloc_failed (size=8589934312) at ../../gcc/libiberty/xmalloc.c:118
#1  0x0000000000b1b8a8 in xcalloc (nelem=1073741789, elsize=8)
    at ../../gcc/libiberty/xmalloc.c:164
#2  0x0000000000b16696 in htab_expand (htab=0x11949c0)
    at ../../gcc/libiberty/hashtab.c:558
#3  0x0000000000b16faa in htab_find_slot_with_hash (htab=0x11949c0,
    element=0x7fff64c7d0c0, hash=2685589897, insert=INSERT)
    at ../../gcc/libiberty/hashtab.c:653
#4  0x00000000005a9701 in lookup_type_pair (ob_p=0x1022380,
    visited_p=0x1022370, t1=<value optimized out>, t2=<value optimized out>)
    at ../../gcc/gcc/gimple.c:3284
#5  0x00000000005b1235 in gtc_visit (sccstate_obstack=Unhandled dwarf
expression opcode 0xf3
)
    at ../../gcc/gcc/gimple.c:3557
#6  gtc_visit (sccstate_obstack=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3473
#7  0x00000000005b0d69 in gimple_types_compatible_p_1 (t1=0x2aff61dc3b28,
    t2=0x2affd032b150, p=0x197c33a70, sccstack=0x7fff64c7d188,
    sccstate=0x9817ee40, sccstate_obstack=0x7fff64c7d190)
    at ../../gcc/gcc/gimple.c:3717
#8  0x00000000005af31e in gimple_types_compatible_p (t2=0x2affd032b150,
    t1=0x2aff61dc3b28) at ../../gcc/gcc/gimple.c:3987
#9  gimple_type_eq (t2=0x2affd032b150, t1=0x2aff61dc3b28)
    at ../../gcc/gcc/gimple.c:4444
#10 0x0000000000b16f1e in htab_find_slot_with_hash (htab=0x2aff56172a10,
    element=0x2affd032b150, hash=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/libiberty/hashtab.c:687
#11 0x00000000005af4cd in gimple_register_type (t=0x2affd032b150)
    at ../../gcc/gcc/gimple.c:4480
#12 0x000000000049c670 in lto_ft_common (t=0x2affd032aab0)
    at ../../gcc/gcc/lto/lto.c:296
#13 0x000000000049c6b9 in lto_ft_decl_minimal (t=0x2affd032aab0)
    at ../../gcc/gcc/lto/lto.c:309
#14 lto_ft_decl_common (t=0x2affd032aab0) at ../../gcc/gcc/lto/lto.c:319
---Type <return> to continue, or q <return> to quit---
#15 0x000000000049d25d in lto_ft_field_decl (t=0x2affd032aab0)
    at ../../gcc/gcc/lto/lto.c:364
#16 lto_fixup_types (t=0x2affd032aab0) at ../../gcc/gcc/lto/lto.c:542
#17 0x000000000049ddd0 in uniquify_nodes (from=671,
    data_in=<value optimized out>) at ../../gcc/gcc/lto/lto.c:618
#18 lto_read_decls (from=671, data_in=<value optimized out>)
    at ../../gcc/gcc/lto/lto.c:697
#19 lto_file_finalize (from=671, data_in=<value optimized out>)
    at ../../gcc/gcc/lto/lto.c:921
#20 lto_create_files_from_ids (from=671, data_in=<value optimized out>)
    at ../../gcc/gcc/lto/lto.c:939
#21 0x0000000000b1b6cf in splay_tree_foreach_helper (data=0x7fff64c7d520,
    fn=0x49dca0 <lto_create_files_from_ids>, node=0x825f6550)
    at ../../gcc/libiberty/splay-tree.c:242
#22 splay_tree_foreach (data=0x7fff64c7d520,
    fn=0x49dca0 <lto_create_files_from_ids>, node=0x825f6550)
    at ../../gcc/libiberty/splay-tree.c:566
#23 0x000000000049f53c in lto_file_read (count=0x7fff64c7d4f0,
    resolution_file=0x15b8ed0, file=0x23d9eac0) at ../../gcc/gcc/lto/lto.c:979
#24 read_cgraph_and_symbols (count=0x7fff64c7d4f0, resolution_file=0x15b8ed0,
    file=0x23d9eac0) at ../../gcc/gcc/lto/lto.c:2321
#25 lto_main (count=0x7fff64c7d4f0, resolution_file=0x15b8ed0, file=0x23d9eac0)
    at ../../gcc/gcc/lto/lto.c:2621
#26 0x00000000006cf4aa in compile_file () at ../../gcc/gcc/toplev.c:570
#27 do_compile () at ../../gcc/gcc/toplev.c:1905
#28 toplev_main () at ../../gcc/gcc/toplev.c:1977
#29 0x00002aff56c32a7d in __libc_start_main () from /lib64/libc.so.6
#30 0x0000000000486c49 in _start () at ../sysdeps/x86_64/elf/start.S:113

Re: [Bug lto/48978] New: excessive hash table allocation for large lto build

[Jan Hubicka]

> I tried a large LTO build with gcc version 4.7.0 20110511 (experimental) (GCC) 
> on a 18GB machine. It ended with
> 
> lto1: out of memory allocating 8589934312 bytes after a total of 6827421696
> bytes
> 
> Since a 7+GB single malloc seems somewhat excessive I put a break point 
> on xmalloc_failed. It looks like the hash tables are growing
> too aggressively?

I think the problem was introduced by Richi's last commit:
2011-05-12  Richard Guenther  <rguenther@suse.de>

        * gimple.c (gtc_visit): Compare TREE_ADDRESSABLE, handle
        NULLPTR_TYPE similar to VOID_TYPE.  Defer type-leader lookup
        until after simple checks.
        (gimple_types_compatible_p): Likewise.
        (iterative_hash_gimple_type): Always hash pointer targets
        and function return and argument types.
        (iterative_hash_canonical_type): Do not hash TYPE_QUALS,
        hash TYPE_ALIGN.  Do not hash TYPE_MIN/MAX_VALUE.
        (gimple_canonical_types_compatible_p): Compare TREE_ADDRESSABLE,
        handle NULLPTR_TYPE similar to VOID_TYPE.  Handle non-aggregates
        completely in the simple compare section.
        (gimple_register_canonical_type): Query the cache again after
        registering.
So reverting this patch might get you past the problem.  Ysterday I was able
to build your testcase with 3GB of ram, today it got out of memory, too.

The hashtable is not expanding too irrationally, but it saves O(n^2) information.
I would like to see it die for sure ;)

Honza

[Bug lto/48978] excessive hash table allocation for large lto build

[hubicka at ucw dot cz]

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

--- Comment #1 from Jan Hubicka <hubicka at ucw dot cz> 2011-05-12 15:29:42 UTC ---
> I tried a large LTO build with gcc version 4.7.0 20110511 (experimental) (GCC) 
> on a 18GB machine. It ended with
> 
> lto1: out of memory allocating 8589934312 bytes after a total of 6827421696
> bytes
> 
> Since a 7+GB single malloc seems somewhat excessive I put a break point 
> on xmalloc_failed. It looks like the hash tables are growing
> too aggressively?

I think the problem was introduced by Richi's last commit:
2011-05-12  Richard Guenther  <rguenther@suse.de>

        * gimple.c (gtc_visit): Compare TREE_ADDRESSABLE, handle
        NULLPTR_TYPE similar to VOID_TYPE.  Defer type-leader lookup
        until after simple checks.
        (gimple_types_compatible_p): Likewise.
        (iterative_hash_gimple_type): Always hash pointer targets
        and function return and argument types.
        (iterative_hash_canonical_type): Do not hash TYPE_QUALS,
        hash TYPE_ALIGN.  Do not hash TYPE_MIN/MAX_VALUE.
        (gimple_canonical_types_compatible_p): Compare TREE_ADDRESSABLE,
        handle NULLPTR_TYPE similar to VOID_TYPE.  Handle non-aggregates
        completely in the simple compare section.
        (gimple_register_canonical_type): Query the cache again after
        registering.
So reverting this patch might get you past the problem.  Ysterday I was able
to build your testcase with 3GB of ram, today it got out of memory, too.

The hashtable is not expanding too irrationally, but it saves O(n^2)
information.
I would like to see it die for sure ;)

Honza

[Bug lto/48978] excessive hash table allocation for large lto build

[andi-gcc at firstfloor dot org]

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

--- Comment #2 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-05-12 16:16:19 UTC ---
I will try.

BTW this was a much larger test case (allyesconfig), the tarball I sent you
is a much more limited config.

Normally noone uses allyesconfig kernels (they barely boot), but they
are a good stress tester for the compiler.

Still I suspect the hash table expansion algorithms are not optimal.
If you're already in the GB range you shouldn't be doubling anymore...

[Bug lto/48978] excessive hash table allocation for large lto build

[andi-gcc at firstfloor dot org]

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

--- Comment #3 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-05-12 16:22:30 UTC ---
looks like the revert is really needed, i just ran out of memory
even on the small config on the large memory system.

[Bug lto/48978] excessive hash table allocation for large lto build

[hubicka at ucw dot cz]

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

--- Comment #4 from Jan Hubicka <hubicka at ucw dot cz> 2011-05-12 22:53:39 UTC ---
> looks like the revert is really needed, i just ran out of memory
> even on the small config on the large memory system.
Yep, it is something with the last Richi's patch. Things has worked reosnably
well for me prveiously (through not quite sanely - 94% of WPA time went into
type merging.  Good news is that we could hope for really huge speedup fixing
this relatively small part of compiler)
I will try to revert it too and look into inliner dumps on kernel just if I can
spot
something obvious.

Honza

[Bug lto/48978] excessive hash table allocation for large lto build

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-13 11:02:40 UTC ---
Fixed.

[Bug lto/48978] excessive hash table allocation for large lto build

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-13 11:02:32 UTC ---
Author: rguenth
Date: Fri May 13 11:02:28 2011
New Revision: 173730

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173730
Log:
2011-05-13  Richard Guenther  <rguenther@suse.de>

    PR lto/48978
    * gimple.c (iterative_hash_gimple_type): Revert change in
    pointer target and function result and argument hashing.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple.c

[Bug lto/48978] excessive hash table allocation for large lto build

[andi-gcc at firstfloor dot org]

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

Andi Kleen <andi-gcc at firstfloor dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|FIXED                       |

--- Comment #7 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-05-13 17:09:24 UTC ---
Sorry the problem is still there even with your revert and current trunk,
triggerable with the large config build. Just the small config works
now.

Breakpoint 1, xmalloc_failed (size=8589934312) at
../../gcc/libiberty/xmalloc.c:118
118     {
(gdb) bt
#0  xmalloc_failed (size=8589934312) at ../../gcc/libiberty/xmalloc.c:118
#1  0x0000000000b1b428 in xcalloc (nelem=1073741789, elsize=8) at
../../gcc/libiberty/xmalloc.c:164
#2  0x0000000000b16216 in htab_expand (htab=0x15bfba0) at
../../gcc/libiberty/hashtab.c:558
#3  0x0000000000b16b2a in htab_find_slot_with_hash (htab=0x15bfba0,
element=0x7fffb0473140, hash=4078607638, 
    insert=INSERT) at ../../gcc/libiberty/hashtab.c:653
#4  0x00000000005b0584 in lookup_type_pair (ob_p=0x1022380,
visited_p=0x1022370, t1=<value optimized out>, 
    t2=<value optimized out>) at ../../gcc/gcc/gimple.c:3284
#5  0x00000000005b0ea1 in gtc_visit (sccstate_obstack=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3556
#6  gtc_visit (sccstate_obstack=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3473
#7  0x00000000005b09d4 in gimple_types_compatible_p_1 (t1=0x2b6db95d1930,
t2=0x2b6e244635e8, p=0x1983bda30, 
    sccstack=0x7fffb0473568, sccstate=0x197a0cbb0,
sccstate_obstack=0x7fffb0473570) at ../../gcc/gcc/gimple.c:3716
#8  0x00000000005b0edd in gtc_visit (sccstate_obstack=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3569
#9  gtc_visit (sccstate_obstack=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3473
#10 0x00000000005b0b86 in gimple_types_compatible_p_1 (t1=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3833
#11 0x00000000005b0edd in gtc_visit (sccstate_obstack=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3569
#12 gtc_visit (sccstate_obstack=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3473
#13 0x00000000005b09d4 in gimple_types_compatible_p_1 (t1=0x2b6db95d17e0,
t2=0x2b6e24463498, p=0x1983bda10, 
    sccstack=0x7fffb0473568, sccstate=0x197a0cbb0,
sccstate_obstack=0x7fffb0473570) at ../../gcc/gcc/gimple.c:3716
#14 0x00000000005b0edd in gtc_visit (sccstate_obstack=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3569
#15 gtc_visit (sccstate_obstack=Unhandled dwarf expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3473
#16 0x00000000005b0b86 in gimple_types_compatible_p_1 (t1=Unhandled dwarf
expression opcode 0xf3
) at ../../gcc/gcc/gimple.c:3833

[Bug lto/48978] excessive hash table allocation for large lto build

[andi-gcc at firstfloor dot org]

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

Andi Kleen <andi-gcc at firstfloor dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED

--- Comment #8 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-06-06 11:05:47 UTC ---
With the latest tree it's bearable, but still very slow.
But at least I don't run regularly out of memory anymore.