Re: [PATCH][LTO] Fix type merging error

[Richard Guenther <rguenther at suse dot de>]

On Thu, 25 Nov 2010, Richard Guenther wrote:

> 
> This fixes a problem with SCC based type-merging which causes us to
> merge types that are not equal if they are part of an SCC even though
> the entry to the SCC is computed as unequal.
> 
> The issue is how we treat members of the SCC - we basically have to
> start with the assumtion of equality (to the SCC we compare to) and
> then drop to unequal once SCCs reachable from the SCC become
> unequal.  We failed to do that properly.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu, lto-bootstrapped
> and SPEC 2k6 tested.

Committed as rev. 167183.

Richard.

> 2010-11-25  Richard Guenther  <rguenther@suse.de>
> 
> 	PR lto/46648
> 	* gimple.c (gtc_visit): Do not return true for members of an
> 	SCC still being processed but the current lattice value of
> 	the member.  Treat SCC members comparison state as lattice,
> 	starting at equal, eventually dropping to unequal.
> 	(gimple_types_compatible_p_1): Likewise.
> 
> Index: gcc/gimple.c
> ===================================================================
> *** gcc/gimple.c	(revision 167142)
> --- gcc/gimple.c	(working copy)
> *************** gtc_visit (tree t1, tree t2, enum gtc_mo
> *** 3515,3541 ****
>   
>     if ((slot = pointer_map_contains (sccstate, p)) != NULL)
>       cstate = (struct sccs *)*slot;
>     if (!cstate)
>       {
> !       bool res;
> !       /* Not yet visited.  DFS recurse.  */
> !       res = gimple_types_compatible_p_1 (t1, t2, mode, p,
> ! 					 sccstack, sccstate, sccstate_obstack);
> !       if (!cstate)
> ! 	cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
>         state->low = MIN (state->low, cstate->low);
> -       /* If the type is no longer on the SCC stack and thus is not part
> - 	 of the parents SCC, return its state.  Otherwise we will
> - 	 ignore this pair and assume equality.  */
> -       if (!cstate->on_sccstack)
> - 	return res;
>       }
>     if (cstate->dfsnum < state->dfsnum
>         && cstate->on_sccstack)
>       state->low = MIN (cstate->dfsnum, state->low);
>   
> !   /* We are part of our parents SCC, skip this entry and return true.  */
> !   return true;
>   }
>   
>   /* Worker for gimple_types_compatible.
> --- 3515,3537 ----
>   
>     if ((slot = pointer_map_contains (sccstate, p)) != NULL)
>       cstate = (struct sccs *)*slot;
> +   /* Not yet visited.  DFS recurse.  */
>     if (!cstate)
>       {
> !       gimple_types_compatible_p_1 (t1, t2, mode, p,
> ! 				   sccstack, sccstate, sccstate_obstack);
> !       cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
>         state->low = MIN (state->low, cstate->low);
>       }
> +   /* If the type is still on the SCC stack adjust the parents low.  */
>     if (cstate->dfsnum < state->dfsnum
>         && cstate->on_sccstack)
>       state->low = MIN (cstate->dfsnum, state->low);
>   
> !   /* Return the current lattice value.  We start with an equality
> !      assumption so types part of a SCC will be optimistically
> !      treated equal unless proven otherwise.  */
> !   return cstate->u.same_p;
>   }
>   
>   /* Worker for gimple_types_compatible.
> *************** gimple_types_compatible_p_1 (tree t1, tr
> *** 3559,3564 ****
> --- 3555,3563 ----
>     state->dfsnum = gtc_next_dfs_num++;
>     state->low = state->dfsnum;
>     state->on_sccstack = true;
> +   /* Start with an equality assumption.  As we DFS recurse into child
> +      SCCs this assumption may get revisited.  */
> +   state->u.same_p = 1;
>   
>     /* If their attributes are not the same they can't be the same type.  */
>     if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
> *************** different_types:
> *** 3822,3843 ****
>   
>     /* Common exit path for types that are compatible.  */
>   same_types:
> !   state->u.same_p = 1;
> !   goto pop;
>   
>   pop:
>     if (state->low == state->dfsnum)
>       {
>         type_pair_t x;
>   
> !       /* Pop off the SCC and set its cache values.  */
>         do
>   	{
>   	  struct sccs *cstate;
>   	  x = VEC_pop (type_pair_t, *sccstack);
>   	  cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
>   	  cstate->on_sccstack = false;
> ! 	  x->same_p[mode] = cstate->u.same_p;
>   	}
>         while (x != p);
>       }
> --- 3821,3842 ----
>   
>     /* Common exit path for types that are compatible.  */
>   same_types:
> !   gcc_assert (state->u.same_p == 1);
>   
>   pop:
>     if (state->low == state->dfsnum)
>       {
>         type_pair_t x;
>   
> !       /* Pop off the SCC and set its cache values to the final
> !          comparison result.  */
>         do
>   	{
>   	  struct sccs *cstate;
>   	  x = VEC_pop (type_pair_t, *sccstack);
>   	  cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
>   	  cstate->on_sccstack = false;
> ! 	  x->same_p[mode] = state->u.same_p;
>   	}
>         while (x != p);
>       }
> Index: gcc/testsuite/gcc.dg/lto/20101125-1_0.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/lto/20101125-1_0.c	(revision 0)
> --- gcc/testsuite/gcc.dg/lto/20101125-1_0.c	(revision 0)
> ***************
> *** 0 ****
> --- 1,24 ----
> + /* { dg-lto-do link } */
> + 
> + struct X {
> +   int i;
> + };
> + 
> + struct W {
> +   struct U *p;
> +   struct X *q;
> + };
> + 
> + struct U {
> +   struct W a[1];
> + };
> + 
> + void foo(struct U *ptr)
> + {
> +   ptr->a[0].p = 0;
> + }
> + 
> + int main(void)
> + {
> +   return 0;
> + }
> Index: gcc/testsuite/gcc.dg/lto/20101125-1_1.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/lto/20101125-1_1.c	(revision 0)
> --- gcc/testsuite/gcc.dg/lto/20101125-1_1.c	(revision 0)
> ***************
> *** 0 ****
> --- 1,17 ----
> + struct X {
> +   char i;
> + };
> + 
> + struct W {
> +   struct U *p;
> +   struct X *q;
> + };
> + 
> + struct U {
> +   struct W a[1];
> + };
> + 
> + void bar(struct U *ptr)
> + {
> +   ptr->a[0].p = 0;
> + }
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex