[PATCH][?/n] LTO type merging cleanup

[PATCH][?/n] LTO type merging cleanup

[Richard Guenther]

This fixes an oversight in the new SCC hash mixing code - we of course
need to return the adjusted hash of our type, not the purely local one.

There's still something weird going on, hash values somehow depend
on the order we feed it types ...

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2011-05-17  Richard Guenther  <rguenther@suse.de>

	* gimple.c (iterative_hash_gimple_type): Simplify singleton
	case some more, fix final hash value of the non-singleton case.

Index: gcc/gimple.c
===================================================================
--- gcc/gimple.c	(revision 173827)
+++ gcc/gimple.c	(working copy)
@@ -4213,25 +4213,24 @@ iterative_hash_gimple_type (tree type, h
   if (state->low == state->dfsnum)
     {
       tree x;
-      struct sccs *cstate;
       struct tree_int_map *m;
 
       /* Pop off the SCC and set its hash values.  */
       x = VEC_pop (tree, *sccstack);
-      cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
-      cstate->on_sccstack = false;
       /* Optimize SCC size one.  */
       if (x == type)
 	{
+	  state->on_sccstack = false;
 	  m = ggc_alloc_cleared_tree_int_map ();
 	  m->base.from = x;
-	  m->to = cstate->u.hash;
+	  m->to = v;
 	  slot = htab_find_slot (type_hash_cache, m, INSERT);
 	  gcc_assert (!*slot);
 	  *slot = (void *) m;
 	}
       else
 	{
+	  struct sccs *cstate;
 	  unsigned first, i, size, j;
 	  struct type_hash_pair *pairs;
 	  /* Pop off the SCC and build an array of type, hash pairs.  */
@@ -4241,6 +4240,8 @@ iterative_hash_gimple_type (tree type, h
 	  size = VEC_length (tree, *sccstack) - first + 1;
 	  pairs = XALLOCAVEC (struct type_hash_pair, size);
 	  i = 0;
+	  cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
+	  cstate->on_sccstack = false;
 	  pairs[i].type = x;
 	  pairs[i].hash = cstate->u.hash;
 	  do
@@ -4275,6 +4276,8 @@ iterative_hash_gimple_type (tree type, h
 	      for (j = 0; pairs[j].hash != pairs[i].hash; ++j)
 		hash = iterative_hash_hashval_t (pairs[j].hash, hash);
 	      m->to = hash;
+	      if (pairs[i].type == type)
+		v = hash;
 	      slot = htab_find_slot (type_hash_cache, m, INSERT);
 	      gcc_assert (!*slot);
 	      *slot = (void *) m;

[PATCH][?/n] LTO type merging cleanup

[Richard Guenther]

This fixes a bug with the previous recursion inhibit of 
gimple_register_type.  It also re-introduces the patch that
makes us compare names not of the main-variant but of the type itself.
And finally it makes us produce more stable hashes by hashing
the types in the tree SCC as it was read in original and not eventually
of some intermediate fixuped state.

LTO bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2011-05-19  Richard Guenther  <rguenther@suse.de>

	* gimple.c (gimple_types_compatible_p_1): Compare names of
	the types themselves.
	(iterative_hash_gimple_type): And hash them that way.
	(gimple_register_type_1): If we register a main variant properly
	initialize the leader to ourselves.

	lto/
	* lto.c (uniquify_nodes): First register all types before
	fixing up the tree SCC.

Index: gcc/gimple.c
===================================================================
*** gcc/gimple.c	(revision 173894)
--- gcc/gimple.c	(working copy)
*************** gimple_types_compatible_p_1 (tree t1, tr
*** 3824,3831 ****
  	tree f1, f2;
  
  	/* The struct tags shall compare equal.  */
! 	if (!compare_type_names_p (TYPE_MAIN_VARIANT (t1),
! 				   TYPE_MAIN_VARIANT (t2), false))
  	  goto different_types;
  
  	/* For aggregate types, all the fields must be the same.  */
--- 3824,3830 ----
  	tree f1, f2;
  
  	/* The struct tags shall compare equal.  */
! 	if (!compare_type_names_p (t1, t2, false))
  	  goto different_types;
  
  	/* For aggregate types, all the fields must be the same.  */
*************** iterative_hash_gimple_type (tree type, h
*** 4202,4208 ****
        unsigned nf;
        tree f;
  
!       v = iterative_hash_name (TYPE_NAME (TYPE_MAIN_VARIANT (type)), v);
  
        for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
  	{
--- 4201,4207 ----
        unsigned nf;
        tree f;
  
!       v = iterative_hash_name (TYPE_NAME (type), v);
  
        for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
  	{
*************** gimple_register_type_1 (tree t, bool reg
*** 4503,4509 ****
  {
    void **slot;
    gimple_type_leader_entry *leader;
!   tree mv_leader = NULL_TREE;
  
    /* If we registered this type before return the cached result.  */
    leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
--- 4502,4508 ----
  {
    void **slot;
    gimple_type_leader_entry *leader;
!   tree mv_leader;
  
    /* If we registered this type before return the cached result.  */
    leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
*************** gimple_register_type_1 (tree t, bool reg
*** 4516,4525 ****
       It also makes sure that main variants will be merged to main variants.
       As we are operating on a possibly partially fixed up type graph
       do not bother to recurse more than once, otherwise we may end up
!      walking in circles.  */
    if (!registering_mv
        && TYPE_MAIN_VARIANT (t) != t)
      mv_leader = gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
  
    slot = htab_find_slot (gimple_types, t, INSERT);
    if (*slot
--- 4515,4529 ----
       It also makes sure that main variants will be merged to main variants.
       As we are operating on a possibly partially fixed up type graph
       do not bother to recurse more than once, otherwise we may end up
!      walking in circles.
!      If we are registering a main variant it will either remain its
!      own main variant or it will be merged to something else in which
!      case we do not care for the main variant leader.  */
    if (!registering_mv
        && TYPE_MAIN_VARIANT (t) != t)
      mv_leader = gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
+   else
+     mv_leader = t;
  
    slot = htab_find_slot (gimple_types, t, INSERT);
    if (*slot
Index: gcc/lto/lto.c
===================================================================
*** gcc/lto/lto.c	(revision 173894)
--- gcc/lto/lto.c	(working copy)
*************** uniquify_nodes (struct data_in *data_in,
*** 605,610 ****
--- 605,624 ----
    struct lto_streamer_cache_d *cache = data_in->reader_cache;
    unsigned len = VEC_length (tree, cache->nodes);
    unsigned i;
+ 
+   /* Go backwards because childs streamed for the first time come
+      as part of their parents, and hence are created after them.  */
+   for (i = len; i-- > from;)
+     {
+       tree t = VEC_index (tree, cache->nodes, i);
+       if (!t)
+ 	continue;
+ 
+       /* Now try to find a canonical variant of T itself.  */
+       if (TYPE_P (t))
+ 	gimple_register_type (t);
+     }
+ 
    /* Go backwards because childs streamed for the first time come
       as part of their parents, and hence are created after them.  */
    for (i = len; i-- > from;)

Re: [PATCH][?/n] LTO type merging cleanup

[Richard Guenther]

On Wed, May 18, 2011 at 7:20 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> We can end up with an infinite recursion as gimple_register_type
>> tries to register TYPE_MAIN_VARIANT first.  This is because we
>> are being called from the LTO type-fixup code which walks the
>> type graph and adjusts types to their leaders.  So we can
>> be called for type SCCs that are only partially fixed up yet
>> which means TYPE_MAIN_VARIANT might temporarily not honor
>> the invariant that the main variant of a main variant is itself.
>> Thus, simply avoid recursing more than once - we are sure that
>> we will be reaching at most type duplicates in further recursion.
>>
>> Bootstrap & regtest pending on x86_64-unknown-linux-gnu.
>
> With this funcion WPA stage passes with some improvements I repported to mozilla metabug.
>
> We now get ICE in ltrans:
> #0  gimple_register_type (t=0x0) at ../../gcc/gimple.c:4616
> #1  0x00000000005a0fc9 in gimple_register_canonical_type (t=0x7fffe851f498) at ../../gcc/gimple.c:4890
> #2  0x000000000048f14d in lto_ft_type (t=0x7fffe851f498) at ../../gcc/lto/lto.c:401
> #3  lto_fixup_types (t=0x7fffe851f498) at ../../gcc/lto/lto.c:581
> #4  0x000000000048f4a0 in uniquify_nodes (node=Unhandled dwarf expression opcode 0xf3
>
> TYPE_MAIN_VARIANT is NULL.
> (gdb) up
> #1  0x00000000005a0fc9 in gimple_register_canonical_type (t=0x7fffe851f498) at ../../gcc/gimple.c:4890
> 4890      t = gimple_register_type (TYPE_MAIN_VARIANT (t));
> (gdb) p debug_generic_stmt (t)
> struct _ffi_type
>
> $1 = void
> (gdb) p debug_tree (t)
>  <record_type 0x7fffe851f498 _ffi_type BLK
>    size <integer_cst 0x7ffff7ecf680 type <integer_type 0x7ffff7eca0a8 bit_size_type> constant 192>
>    unit size <integer_cst 0x7ffff7ecf640 type <integer_type 0x7ffff7eca000> constant 24>
>    align 64 symtab 0 alias set -1 structural equality
>    fields <field_decl 0x7fffe87684c0 size
>        type <integer_type 0x7ffff7eca690 long unsigned int public unsigned DI
>            size <integer_cst 0x7ffff7ecf1e0 constant 64>
>            unit size <integer_cst 0x7ffff7ecf200 constant 8>
>            align 64 symtab 0 alias set -1 canonical type 0x7ffff7eca690 precision 64 min <integer_cst 0x7ffff7ecf220 0> max <integer_cst 0x7ffff7ecf1c0 18446744073709551615>
>            pointer_to_this <pointer_type 0x7ffff5336150> reference_to_this <reference_type 0x7ffff0aba000>>
>        used unsigned nonlocal DI file ctypes/libffi/include/ffi.h line 109 col 0 size <integer_cst 0x7ffff7ecf1e0 64> unit size <integer_cst 0x7ffff7ecf200 8>
>        align 64 offset_align 128
>        offset <integer_cst 0x7ffff7ebaf00 constant 0>
>        bit offset <integer_cst 0x7ffff7ecf420 constant 0> context <record_type 0x7fffe851f2a0 _ffi_type>
>        chain <field_decl 0x7fffe8768558 alignment type <integer_type 0x7ffff7eca3f0 short unsigned int>
>            used unsigned nonlocal HI file ctypes/libffi/include/ffi.h line 110 col 0
>            size <integer_cst 0x7ffff7ecf080 constant 16>
>            unit size <integer_cst 0x7ffff7ecf0a0 constant 2>
>            align 16 offset_align 128 offset <integer_cst 0x7ffff7ebaf00 0> bit offset <integer_cst 0x7ffff7ecf1e0 64> context <record_type 0x7fffe851f2a0 _ffi_type> chain <field_decl 0x7fffe87685f0 type>>>
>    chain <type_decl 0x7fffe8966ac8 _ffi_type>>
> $2 = void
>
> Let me know if there is anything easy I could work out ;)
> I think the bug may be in the recursion guard.  When you have cycle of length
> greater than 2 of MVs, you won't walk them all.

That doesn't matter.  MVs are acyclic initially (in fact the chain has
length 1), only during
fixup we can temporarily create larger chains or cycles.  MVs also
never are NULL, so it
would be interesting to see what clears it ...

Richard.

> Honza
>

Re: [PATCH][?/n] LTO type merging cleanup

[Jan Hubicka]

> 
> We can end up with an infinite recursion as gimple_register_type
> tries to register TYPE_MAIN_VARIANT first.  This is because we
> are being called from the LTO type-fixup code which walks the
> type graph and adjusts types to their leaders.  So we can
> be called for type SCCs that are only partially fixed up yet
> which means TYPE_MAIN_VARIANT might temporarily not honor
> the invariant that the main variant of a main variant is itself.
> Thus, simply avoid recursing more than once - we are sure that
> we will be reaching at most type duplicates in further recursion.
> 
> Bootstrap & regtest pending on x86_64-unknown-linux-gnu.

With this funcion WPA stage passes with some improvements I repported to mozilla metabug.

We now get ICE in ltrans:
#0  gimple_register_type (t=0x0) at ../../gcc/gimple.c:4616
#1  0x00000000005a0fc9 in gimple_register_canonical_type (t=0x7fffe851f498) at ../../gcc/gimple.c:4890
#2  0x000000000048f14d in lto_ft_type (t=0x7fffe851f498) at ../../gcc/lto/lto.c:401
#3  lto_fixup_types (t=0x7fffe851f498) at ../../gcc/lto/lto.c:581
#4  0x000000000048f4a0 in uniquify_nodes (node=Unhandled dwarf expression opcode 0xf3

TYPE_MAIN_VARIANT is NULL.
(gdb) up
#1  0x00000000005a0fc9 in gimple_register_canonical_type (t=0x7fffe851f498) at ../../gcc/gimple.c:4890
4890      t = gimple_register_type (TYPE_MAIN_VARIANT (t));
(gdb) p debug_generic_stmt (t)
struct _ffi_type

$1 = void
(gdb) p debug_tree (t)
 <record_type 0x7fffe851f498 _ffi_type BLK
    size <integer_cst 0x7ffff7ecf680 type <integer_type 0x7ffff7eca0a8 bit_size_type> constant 192>
    unit size <integer_cst 0x7ffff7ecf640 type <integer_type 0x7ffff7eca000> constant 24>
    align 64 symtab 0 alias set -1 structural equality
    fields <field_decl 0x7fffe87684c0 size
        type <integer_type 0x7ffff7eca690 long unsigned int public unsigned DI
            size <integer_cst 0x7ffff7ecf1e0 constant 64>
            unit size <integer_cst 0x7ffff7ecf200 constant 8>
            align 64 symtab 0 alias set -1 canonical type 0x7ffff7eca690 precision 64 min <integer_cst 0x7ffff7ecf220 0> max <integer_cst 0x7ffff7ecf1c0 18446744073709551615>
            pointer_to_this <pointer_type 0x7ffff5336150> reference_to_this <reference_type 0x7ffff0aba000>>
        used unsigned nonlocal DI file ctypes/libffi/include/ffi.h line 109 col 0 size <integer_cst 0x7ffff7ecf1e0 64> unit size <integer_cst 0x7ffff7ecf200 8>
        align 64 offset_align 128
        offset <integer_cst 0x7ffff7ebaf00 constant 0>
        bit offset <integer_cst 0x7ffff7ecf420 constant 0> context <record_type 0x7fffe851f2a0 _ffi_type>
        chain <field_decl 0x7fffe8768558 alignment type <integer_type 0x7ffff7eca3f0 short unsigned int>
            used unsigned nonlocal HI file ctypes/libffi/include/ffi.h line 110 col 0
            size <integer_cst 0x7ffff7ecf080 constant 16>
            unit size <integer_cst 0x7ffff7ecf0a0 constant 2>
            align 16 offset_align 128 offset <integer_cst 0x7ffff7ebaf00 0> bit offset <integer_cst 0x7ffff7ecf1e0 64> context <record_type 0x7fffe851f2a0 _ffi_type> chain <field_decl 0x7fffe87685f0 type>>>
    chain <type_decl 0x7fffe8966ac8 _ffi_type>>
$2 = void

Let me know if there is anything easy I could work out ;)
I think the bug may be in the recursion guard.  When you have cycle of length
greater than 2 of MVs, you won't walk them all.

Honza

[PATCH][?/n] LTO type merging cleanup

[Richard Guenther]

We can end up with an infinite recursion as gimple_register_type
tries to register TYPE_MAIN_VARIANT first.  This is because we
are being called from the LTO type-fixup code which walks the
type graph and adjusts types to their leaders.  So we can
be called for type SCCs that are only partially fixed up yet
which means TYPE_MAIN_VARIANT might temporarily not honor
the invariant that the main variant of a main variant is itself.
Thus, simply avoid recursing more than once - we are sure that
we will be reaching at most type duplicates in further recursion.

Bootstrap & regtest pending on x86_64-unknown-linux-gnu.

Richard.

2011-05-18  Richard Guenther  <rguenther@suse.de>

	* gimple.c (gimple_register_type_1): New function, split out from ...
	(gimple_register_type): ... here.  Avoid infinite recursion.

Index: gcc/gimple.c
===================================================================
--- gcc/gimple.c	(revision 173852)
+++ gcc/gimple.c	(working copy)
@@ -4487,23 +4509,17 @@ gimple_type_eq (const void *p1, const vo
 }
 
 
-/* Register type T in the global type table gimple_types.
-   If another type T', compatible with T, already existed in
-   gimple_types then return T', otherwise return T.  This is used by
-   LTO to merge identical types read from different TUs.  */
+/* Worker for gimple_register_type.
+   Register type T in the global type table gimple_types.
+   When REGISTERING_MV is false first recurse for the main variant of T.  */
 
-tree
-gimple_register_type (tree t)
+static tree
+gimple_register_type_1 (tree t, bool registering_mv)
 {
   void **slot;
   gimple_type_leader_entry *leader;
   tree mv_leader = NULL_TREE;
 
-  gcc_assert (TYPE_P (t));
-
-  if (!gimple_type_leader)
-    gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
-				(GIMPLE_TYPE_LEADER_SIZE);
   /* If we registered this type before return the cached result.  */
   leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
   if (leader->type == t)
@@ -4511,12 +4527,14 @@ gimple_register_type (tree t)
 
   /* Always register the main variant first.  This is important so we
      pick up the non-typedef variants as canonical, otherwise we'll end
-     up taking typedef ids for structure tags during comparison.  */
-  if (TYPE_MAIN_VARIANT (t) != t)
-    mv_leader = gimple_register_type (TYPE_MAIN_VARIANT (t));
-
-  if (gimple_types == NULL)
-    gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
+     up taking typedef ids for structure tags during comparison.
+     It also makes sure that main variants will be merged to main variants.
+     As we are operating on a possibly partially fixed up type graph
+     do not bother to recurse more than once, otherwise we may end up
+     walking in circles.  */
+  if (!registering_mv
+      && TYPE_MAIN_VARIANT (t) != t)
+    mv_leader = gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
 
   slot = htab_find_slot (gimple_types, t, INSERT);
   if (*slot
@@ -4602,6 +4620,25 @@ gimple_register_type (tree t)
   return t;
 }
 
+/* Register type T in the global type table gimple_types.
+   If another type T', compatible with T, already existed in
+   gimple_types then return T', otherwise return T.  This is used by
+   LTO to merge identical types read from different TUs.  */
+
+tree
+gimple_register_type (tree t)
+{
+  gcc_assert (TYPE_P (t));
+
+  if (!gimple_type_leader)
+    gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
+				(GIMPLE_TYPE_LEADER_SIZE);
+
+  if (gimple_types == NULL)
+    gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
+
+  return gimple_register_type_1 (t, false);
+}
 
 /* The TYPE_CANONICAL merging machinery.  It should closely resemble
    the middle-end types_compatible_p function.  It needs to avoid

[PATCH][?/n] LTO type merging cleanup

[Richard Guenther]

This avoids the odd cases where gimple_register_canonical_type could
end up running in cycles.  I was able to reproduce this issue
with an intermediate tree and LTO bootstrap.  While the following
patch is not the "real" fix (that one runs into a known cache-preloading
issue again ...) it certainly makes a lot of sense and avoids
the issue by design.

LTO bootstrapped on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2011-05-17  Richard Guenther  <rguenther@suse.de>

	* gimple.c (gimple_register_canonical_type): Use the main-variant
	leader for computing the canonical type.

Index: gcc/gimple.c
===================================================================
*** gcc/gimple.c	(revision 173825)
--- gcc/gimple.c	(working copy)
*************** gimple_register_canonical_type (tree t)
*** 4856,4874 ****
    if (TYPE_CANONICAL (t))
      return TYPE_CANONICAL (t);
  
!   /* Always register the type itself first so that if it turns out
!      to be the canonical type it will be the one we merge to as well.  */
!   t = gimple_register_type (t);
  
    if (TYPE_CANONICAL (t))
      return TYPE_CANONICAL (t);
  
-   /* Always register the main variant first.  This is important so we
-      pick up the non-typedef variants as canonical, otherwise we'll end
-      up taking typedef ids for structure tags during comparison.  */
-   if (TYPE_MAIN_VARIANT (t) != t)
-     gimple_register_canonical_type (TYPE_MAIN_VARIANT (t));
- 
    if (gimple_canonical_types == NULL)
      gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
  					      gimple_canonical_type_eq, 0);
--- 4856,4869 ----
    if (TYPE_CANONICAL (t))
      return TYPE_CANONICAL (t);
  
!   /* Use the leader of our main variant for determining our canonical
!      type.  The main variant leader is a type that will always
!      prevail.  */
!   t = gimple_register_type (TYPE_MAIN_VARIANT (t));
  
    if (TYPE_CANONICAL (t))
      return TYPE_CANONICAL (t);
  
    if (gimple_canonical_types == NULL)
      gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
  					      gimple_canonical_type_eq, 0);