Re: [PATCH, PR69169] Fix infinite recursion in create_variable_info_for_1

[Richard Biener <rguenther at suse dot de>]

On Wed, 13 Jan 2016, Tom de Vries wrote:

> On 13/01/16 09:40, Richard Biener wrote:
> > On Wed, 13 Jan 2016, Tom de Vries wrote:
> > 
> > > Hi,
> > > 
> > > Consider testcase test.c:
> > > ...
> > > struct pgm_slist_t
> > > {
> > >    struct pgm_slist_t *__restrict next;
> > > };
> > > 
> > > void
> > > fn1 (struct pgm_slist_t p1)
> > > {
> > > 
> > > }
> > > ...
> > > 
> > > The compilation of the testcase enters into infinite recursion, due to the
> > > more aggressive restrict support added recently.
> > > 
> > > The patch fixes this by:-
> > > - tracking which structs are being traversed when following restrict
> > >    pointers in create_variable_info_for_1, and
> > > - not following restrict pointers that point to already tracked structs.
> > > 
> > > Bootstrapped and reg-tested on x86_64.
> > > 
> > > OK for trunk?
> > 
> > > Fix infinite recursion in create_variable_info_for_1
> > > 
> > > 	PR tree-optimization/69169
> > > 	* tree-ssa-structalias.c (handled_struct_type): New hash set.
> > > 	(create_variable_info_for_1): Use handled_struct_type to keep track
> > > 	of structs recursed by following restrict pointers.
> > > 	(intra_create_variable_infos): Allocate and cleanup
> > > 	handled_struct_type.
> > > 
> > > 	* gcc.dg/pr69169.c: New test.
> > > 
> > > ---
> > >   gcc/testsuite/gcc.dg/pr69169.c | 13 +++++++++++++
> > >   gcc/tree-ssa-structalias.c     | 19 ++++++++++++++++---
> > >   2 files changed, 29 insertions(+), 3 deletions(-)
> > > 
> > > diff --git a/gcc/testsuite/gcc.dg/pr69169.c
> > > b/gcc/testsuite/gcc.dg/pr69169.c
> > > new file mode 100644
> > > index 0000000..ecf847c
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/pr69169.c
> > > @@ -0,0 +1,13 @@
> > > +/* { dg-do compile } */
> > > +/* { dg-options "-O2" } */
> > > +
> > > +struct pgm_slist_t
> > > +{
> > > +  struct pgm_slist_t *__restrict next;
> > > +};
> > > +
> > > +void
> > > +fn1 (struct pgm_slist_t p1)
> > > +{
> > > +
> > > +}
> > > diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c
> > > index fd98352..72bef07 100644
> > > --- a/gcc/tree-ssa-structalias.c
> > > +++ b/gcc/tree-ssa-structalias.c
> > > @@ -5767,6 +5767,12 @@ check_for_overlaps (vec<fieldoff_s> fieldstack)
> > >     return false;
> > >   }
> > > 
> > > +/* Hash set used to register structs traversed in
> > > create_variable_info_for_1
> > > +   by following restrict pointers.  This is needed to prevent infinite
> > > +   recursion.  */
> > > +
> > > +hash_set<tree> *handled_struct_type = NULL;
> > > +
> > 
> > A bitmap indexed by TYPE_UID would be cheaper I guess?
> 
> Done.
> 
> > Maybe not.
> > At least a hash_set<unsigned> would be ;)
> > 
> 
> A hash_set<unsigned> doesn't seem to work. So I use a bitmap now.
> 
> > Plase make the above static and GTY((skip)), no need to put it in
> > GC memory.
> 
> I've made a param out of handled_struct_type, so there's no global decl
> anymore.
> 
> > >   /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
> > >      This will also create any varinfo structures necessary for fields
> > >      of DECL.  DECL is a function parameter if HANDLE_PARAM is set.  */
> > > @@ -5851,7 +5857,8 @@ create_variable_info_for_1 (tree decl, const char
> > > *name, bool add_id,
> > >   	vi->only_restrict_pointers = 1;
> > >         if (vi->only_restrict_pointers
> > >   	  && !type_contains_placeholder_p (TREE_TYPE (decl_type))
> > > -	  && handle_param)
> > > +	  && handle_param
> > > +	  && !handled_struct_type->contains (TREE_TYPE (decl_type)))
> > >   	{
> > >   	  varinfo_t rvi;
> > >   	  tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type));
> > 
> > This path misses to add/remove decl_type to the set.  Thus
> > struct X { struct X * restrict p; } *; would still recurse infinitely?
> 
> I tried that out, but no.
> 
> > > 
> > > @@ -5871,6 +5878,8 @@ create_variable_info_for_1 (tree decl, const char
> > > *name, bool add_id,
> > >     vi->fullsize = tree_to_uhwi (declsize);
> > >     if (fieldstack.length () == 1)
> > >       vi->is_full_var = true;
> > > +  if (handle_param)
> > > +    handled_struct_type->add (decl_type);
> > 
> > while here we add it to the set even if in the end we won't create
> > a fake var decl (and recurse).  I think we should add to the set only
> > if we actually recurse.
> 
> Done.
> 
> > >     for (i = 0, newvi = vi;
> > >          fieldstack.iterate (i, &fo);
> > >          ++i, newvi = vi_next (newvi))
> > > @@ -5902,7 +5911,8 @@ create_variable_info_for_1 (tree decl, const char
> > > *name, bool add_id,
> > >         newvi->only_restrict_pointers = fo->only_restrict_pointers;
> > >         if (handle_param
> > >   	  && newvi->only_restrict_pointers
> > > -	  && !type_contains_placeholder_p (fo->restrict_pointed_type))
> > > +	  && !type_contains_placeholder_p (fo->restrict_pointed_type)
> > > +	  && !handled_struct_type->contains (fo->restrict_pointed_type))
> > >   	{
> > >   	  varinfo_t rvi;
> > >   	  tree heapvar = build_fake_var_decl (fo->restrict_pointed_type);
> > > @@ -5921,6 +5931,8 @@ create_variable_info_for_1 (tree decl, const char
> > > *name, bool add_id,
> > >   	  tem->head = vi->id;
> > >   	}
> > >       }
> > > +  if (handle_param)
> > > +    handled_struct_type->remove (decl_type);
> > > 
> > >     return vi;
> > >   }
> > > @@ -6065,10 +6077,11 @@ intra_create_variable_infos (struct function *fn)
> > >        passed-by-reference argument.  */
> > >     for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
> > >       {
> > > +      handled_struct_type = hash_set<tree>::create_ggc (4);
> > > 
> > As said, please put it in heap memory and eventually just pass it down
> > as argument to create_variable_info_for_1 avoiding the global variable
> > (it's just three callers as far as I can see).
> 
> Done.
> 
> Retesting patch below (copy-pasted as plain text).

Ok if successful.

Thanks,
Richard.

> Thanks,
> - Tom
> 
> --
> 
> Fix infinite recursion in create_variable_info_for_1
> 
> 	PR tree-optimization/69169
> 	* tree-ssa-structalias.c (create_variable_info_for_1): Add and handle
> 	handled_struct_type param.
> 	(create_variable_info_for, intra_create_variable_infos): Call
> 	create_variable_info_for_1 with extra arg.
> 
> 	* gcc.dg/pr69169.c: New test.
> 
> ---
>  gcc/testsuite/gcc.dg/pr69169.c | 13 +++++++++++++
>  gcc/tree-ssa-structalias.c     | 42
> ++++++++++++++++++++++++++++++++++--------
>  2 files changed, 47 insertions(+), 8 deletions(-)
> 
> diff --git a/gcc/testsuite/gcc.dg/pr69169.c b/gcc/testsuite/gcc.dg/pr69169.c
> new file mode 100644
> index 0000000..ecf847c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr69169.c
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +struct pgm_slist_t
> +{
> +  struct pgm_slist_t *__restrict next;
> +};
> +
> +void
> +fn1 (struct pgm_slist_t p1)
> +{
> +
> +}
> diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c
> index fd98352..e7d0797 100644
> --- a/gcc/tree-ssa-structalias.c
> +++ b/gcc/tree-ssa-structalias.c
> @@ -5769,11 +5769,13 @@ check_for_overlaps (vec<fieldoff_s> fieldstack)
> 
>  /* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
>     This will also create any varinfo structures necessary for fields
> -   of DECL.  DECL is a function parameter if HANDLE_PARAM is set.  */
> +   of DECL.  DECL is a function parameter if HANDLE_PARAM is set.
> +   HANDLED_STRUCT_TYPE is used to register struct types reached by following
> +   restrict pointers.  This is needed to prevent infinite recursion.  */
> 
>  static varinfo_t
>  create_variable_info_for_1 (tree decl, const char *name, bool add_id,
> -			    bool handle_param)
> +			    bool handle_param, bitmap handled_struct_type)
>  {
>    varinfo_t vi, newvi;
>    tree decl_type = TREE_TYPE (decl);
> @@ -5851,13 +5853,21 @@ create_variable_info_for_1 (tree decl, const char
> *name, bool add_id,
>  	vi->only_restrict_pointers = 1;
>        if (vi->only_restrict_pointers
>  	  && !type_contains_placeholder_p (TREE_TYPE (decl_type))
> -	  && handle_param)
> +	  && handle_param
> +	  && !bitmap_bit_p (handled_struct_type,
> +			    TYPE_UID (TREE_TYPE (decl_type))))
>  	{
>  	  varinfo_t rvi;
>  	  tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type));
>  	  DECL_EXTERNAL (heapvar) = 1;
> +	  if (var_can_have_subvars (heapvar))
> +	    bitmap_set_bit (handled_struct_type,
> +			    TYPE_UID (TREE_TYPE (decl_type)));
>  	  rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
> -					    true);
> +					    true, handled_struct_type);
> +	  if (var_can_have_subvars (heapvar))
> +	    bitmap_clear_bit (handled_struct_type,
> +			      TYPE_UID (TREE_TYPE (decl_type)));
>  	  rvi->is_restrict_var = 1;
>  	  insert_vi_for_tree (heapvar, rvi);
>  	  make_constraint_from (vi, rvi->id);
> @@ -5902,13 +5912,21 @@ create_variable_info_for_1 (tree decl, const char
> *name, bool add_id,
>        newvi->only_restrict_pointers = fo->only_restrict_pointers;
>        if (handle_param
>  	  && newvi->only_restrict_pointers
> -	  && !type_contains_placeholder_p (fo->restrict_pointed_type))
> +	  && !type_contains_placeholder_p (fo->restrict_pointed_type)
> +	  && !bitmap_bit_p (handled_struct_type,
> +			    TYPE_UID (fo->restrict_pointed_type)))
>  	{
>  	  varinfo_t rvi;
>  	  tree heapvar = build_fake_var_decl (fo->restrict_pointed_type);
>  	  DECL_EXTERNAL (heapvar) = 1;
> +	  if (var_can_have_subvars (heapvar))
> +	    bitmap_set_bit (handled_struct_type,
> +			    TYPE_UID (fo->restrict_pointed_type));
>  	  rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true,
> -					    true);
> +					    true, handled_struct_type);
> +	  if (var_can_have_subvars (heapvar))
> +	    bitmap_clear_bit (handled_struct_type,
> +			      TYPE_UID (fo->restrict_pointed_type));
>  	  rvi->is_restrict_var = 1;
>  	  insert_vi_for_tree (heapvar, rvi);
>  	  make_constraint_from (newvi, rvi->id);
> @@ -5928,7 +5946,7 @@ create_variable_info_for_1 (tree decl, const char *name,
> bool add_id,
>  static unsigned int
>  create_variable_info_for (tree decl, const char *name, bool add_id)
>  {
> -  varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false);
> +  varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false,
> NULL);
>    unsigned int id = vi->id;
> 
>    insert_vi_for_tree (decl, vi);
> @@ -6059,19 +6077,27 @@ static void
>  intra_create_variable_infos (struct function *fn)
>  {
>    tree t;
> +  bitmap handled_struct_type = NULL;
> 
>    /* For each incoming pointer argument arg, create the constraint ARG
>       = NONLOCAL or a dummy variable if it is a restrict qualified
>       passed-by-reference argument.  */
>    for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
>      {
> +      if (handled_struct_type == NULL)
> +	handled_struct_type = BITMAP_ALLOC (NULL);
> +
>        varinfo_t p
> -	= create_variable_info_for_1 (t, alias_get_name (t), false, true);
> +	= create_variable_info_for_1 (t, alias_get_name (t), false, true,
> +				      handled_struct_type);
>        insert_vi_for_tree (t, p);
> 
>        make_param_constraints (p);
>      }
> 
> +  if (handled_struct_type != NULL)
> +    BITMAP_FREE (handled_struct_type);
> +
>    /* Add a constraint for a result decl that is passed by reference.  */
>    if (DECL_RESULT (fn->decl)
>        && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)