Re: Do less generous pointer globbing in alias.c

[Richard Biener <rguenther at suse dot de>]

On Thu, 28 May 2015, Jan Hubicka wrote:

> Hi,
> here is updated version of patch.  It makes alias_set_subset_of to be symmetric for 
> ptr_type_node and other pointer type and moves the logic of creating subsets
> to get_alias_set.
> 
> I tested that perlbmk works when built at -O3 x86_64
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* alias.c (alias_set_entry_d): Add is_pointer.
> 	(alias_set_subset_of): Special case pointers.
> 	(init_alias_set_entry): Break out from ...
> 	(record_alias_subset): ... here.
> 	(get_alias_set): Do less generous pointer globbing.
> 	* gcc.dg/alias-8.c: Do not xfail.
> 	* gcc.dg/pr62167.c: Prevent FRE.
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 223772)
> +++ alias.c	(working copy)
> @@ -183,10 +184,6 @@ struct GTY(()) alias_set_entry_d {
>    /* The alias set number, as stored in MEM_ALIAS_SET.  */
>    alias_set_type alias_set;
>  
> -  /* Nonzero if would have a child of zero: this effectively makes this
> -     alias set the same as alias set zero.  */
> -  int has_zero_child;
> -
>    /* The children of the alias set.  These are not just the immediate
>       children, but, in fact, all descendants.  So, if we have:
>  
> @@ -195,6 +192,15 @@ struct GTY(()) alias_set_entry_d {
>       continuing our example above, the children here will be all of
>       `int', `double', `float', and `struct S'.  */
>    hash_map<int, int, alias_set_traits> *children;
> +
> +  /* Nonzero if would have a child of zero: this effectively makes this
> +     alias set the same as alias set zero.  */
> +  bool has_zero_child;
> +  /* Nonzero if alias set corresponds to pointer type itself (i.e. not to
> +     aggregate contaiing pointer.
> +     This is used for a special case where we need an universal pointer type
> +     compatible with all other pointer types.  */
> +  bool is_pointer;
>  };
>  typedef struct alias_set_entry_d *alias_set_entry;
>  
> @@ -460,12 +466,33 @@ alias_set_subset_of (alias_set_type set1
>    if (set2 == 0)
>      return true;
>  
> -  /* Otherwise, check if set1 is a subset of set2.  */
> +  /* Check if set1 is a subset of set2.  */
>    ase = get_alias_set_entry (set2);
>    if (ase != 0
>        && (ase->has_zero_child
>  	  || ase->children->get (set1)))
>      return true;
> +
> +  /* As a special case we consider alias set of "void *" to be both subset
> +     and superset of every alias set of a pointer.  This extra symmetry does
> +     not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
> +     to return true on the following testcase:
> +
> +     void *ptr;
> +     char **ptr2=(char **)&ptr;
> +     *ptr2 = ...
> +
> +     This makes void * truly universal pointer type.  See pointer handling in
> +     get_alias_set for more details.  */
> +  if (ase && ase->is_pointer)
> +    {
> +      alias_set_entry ase1 = get_alias_set_entry (set1);
> +
> +      if (ase1 && ase1->is_pointer
> +	  && (set1 == TYPE_ALIAS_SET (ptr_type_node)
> +	      || set2 == TYPE_ALIAS_SET (ptr_type_node)))
> +	return true;
> +    }
>    return false;
>  }
>  
> @@ -764,6 +791,21 @@ alias_ptr_types_compatible_p (tree t1, t
>  	  == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
>  }
>  
> +/* Create emptry alias set entry.  */
> +
> +alias_set_entry
> +init_alias_set_entry (alias_set_type set)
> +{
> +  alias_set_entry ase = ggc_cleared_alloc<alias_set_entry_d> ();

no need to use cleared_alloc if you also init ->is_pointer to false.

> +  ase->alias_set = set;
> +  ase->children
> +    = hash_map<int, int, alias_set_traits>::create_ggc (64);

that seems a bit excessive, esp. for pointers which won't end
up with any children?  So better make children lazily allocated
in record_alias_subset.

> +  ase->has_zero_child = 0;
> +  gcc_checking_assert (!get_alias_set_entry (set));
> +  (*alias_sets)[set] = ase;
> +  return ase;
> +}
> +
>  /* Return the alias set for T, which may be either a type or an
>     expression.  Call language-specific routine for help, if needed.  */
>  
> @@ -903,35 +945,92 @@ get_alias_set (tree t)
>       the pointed-to types.  This issue has been reported to the
>       C++ committee.
>  
> -     In addition to the above canonicalization issue, with LTO
> -     we should also canonicalize `T (*)[]' to `T *' avoiding
> -     alias issues with pointer-to element types and pointer-to
> -     array types.
> -
> -     Likewise we need to deal with the situation of incomplete
> -     pointed-to types and make `*(struct X **)&a' and
> -     `*(struct X {} **)&a' alias.  Otherwise we will have to
> -     guarantee that all pointer-to incomplete type variants
> -     will be replaced by pointer-to complete type variants if
> -     they are available.
> -
> -     With LTO the convenient situation of using `void *' to
> -     access and store any pointer type will also become
> -     more apparent (and `void *' is just another pointer-to
> -     incomplete type).  Assigning alias-set zero to `void *'
> -     and all pointer-to incomplete types is a not appealing
> -     solution.  Assigning an effective alias-set zero only
> -     affecting pointers might be - by recording proper subset
> -     relationships of all pointer alias-sets.
> -
> -     Pointer-to function types are another grey area which
> -     needs caution.  Globbing them all into one alias-set
> -     or the above effective zero set would work.
> -
> -     For now just assign the same alias-set to all pointers.
> -     That's simple and avoids all the above problems.  */
> -  else if (POINTER_TYPE_P (t)
> -	   && t != ptr_type_node)
> +     For this reason go to canonical type of the unqalified pointer type.
> +     Until GCC 6 this code set all pointers sets to have alias set of
> +     ptr_type_node but that is a bad idea, because it prevents disabiguations
> +     in between pointers.  For Firefox this accounts about 20% of all
> +     disambiguations in the program.  */
> +  else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p)
> +    {
> +      tree p;
> +      auto_vec <bool, 8> reference;
> +
> +      /* Unnest all pointers and references.
> +         We also want to make pointer to array equivalent to pointer to its
> +         element. So skip all array types, too.  */
> +      for (p = t; POINTER_TYPE_P (p)
> +	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
> +	   p = TREE_TYPE (p))
> +	{
> +	  if (TREE_CODE (p) == REFERENCE_TYPE)
> +	    reference.safe_push (true);
> +	  if (TREE_CODE (p) == POINTER_TYPE)
> +	    reference.safe_push (false);
> +	}
> +      p = TYPE_MAIN_VARIANT (p);
> +
> +      /* Make void * compatible with char * and also void **.
> +	 Programs are commonly violating TBAA by this.
> +
> +	 We also make void * to conflict with every pointer
> +	 (see record_component_aliases) and thus it is safe it to use it for
> +	 pointers to types with TYPE_STRUCTURAL_EQUALITY_P.  */
> +      if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
> +	set = get_alias_set (ptr_type_node);
> +      else
> +	{
> +	  /* Rebuild pointer type from starting from canonical types using
> +	     unqualified pointers and references only.  This way all such
> +	     pointers will have the same alias set and will conflict with
> +	     each other.
> +
> +	     Most of time we already have pointers or references of a given type.
> +	     If not we build new one just to be sure that if someone later
> +	     (probably only middle-end can, as we should assign all alias
> +	     classes only after finishing translation unit) builds the pointer
> +	     type, the canonical type will match.  */
> +	  p = TYPE_CANONICAL (p);
> +	  while (!reference.is_empty ())
> +	    {
> +	      if (reference.pop ())
> +		p = build_reference_type (p);
> +	      else
> +		p = build_pointer_type (p);
> +	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
> +	    }
> +          gcc_checking_assert (TYPE_CANONICAL (p) == p);
> +
> +	  /* Assign the alias set to both p and t.
> +	     We can not call get_alias_set (p) here as that would trigger
> +	     infinite recursion when p == t.  In other cases it would just
> +	     trigger unnecesary legwork of rebuilding the pointer again.  */
> +	  if (TYPE_ALIAS_SET_KNOWN_P (p))
> +	    set = TYPE_ALIAS_SET (p);
> +	  else
> +	    {
> +	      set = new_alias_set ();
> +	      TYPE_ALIAS_SET (p) = set;
> +	      /* We want void * to be compatible with any other pointer without
> +		 really dropping it to alias set 0. Doing so would make it
> +	         compatible with all non-pointer types too.
> +
> +		 We make ptr_type_node to be a component of every pointer
> +		 type.  Thus memory operations of type "void *" conflict with
> +		 operations of type "T *" without impossing a conflict with
> +		 memory operations of type "Q *" in case T and Q do not conflict.
> + 
> +		 This is not strictly necessary by the C/C++ language
> +		 standards, but avoids common type punning mistakes.  In
> +		 addition to that, we need the existence of such universal
> +		 pointer to implement Fortran's C_PTR type (which is defined as
> +		 type compatible with all C pointers).  */
> +	      record_alias_subset (set, get_alias_set (ptr_type_node));

I still wonder why you do this instead of changing alias_sets_conflict
in the same way you changed alias_set_subset_of.

Patch looks ok otherwise but please leave the patch for others to
comment on for a while.

Thanks,
Richard.

> +	    }
> +	}
> +    }
> +  /* In LTO the rules above needs to be part of canonical type machinery.
> +     For now just punt.  */
> +  else if (POINTER_TYPE_P (t) && t != ptr_type_node && in_lto_p)
>      set = get_alias_set (ptr_type_node);
>  
>    /* Otherwise make a new alias set for this type.  */
> @@ -953,6 +1052,15 @@ get_alias_set (tree t)
>    if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
>      record_component_aliases (t);
>  
> +  /* We treat pointer types specially in alias_set_subset_of.  */
> +  if (POINTER_TYPE_P (t) && set)
> +    {
> +      alias_set_entry ase = get_alias_set_entry (set);
> +      if (!ase)
> +	ase = init_alias_set_entry (set);
> +      ase->is_pointer = true;
> +    }
> +
>    return set;
>  }
>  
> @@ -1003,12 +1111,7 @@ record_alias_subset (alias_set_type supe
>      {
>        /* Create an entry for the SUPERSET, so that we have a place to
>  	 attach the SUBSET.  */
> -      superset_entry = ggc_cleared_alloc<alias_set_entry_d> ();
> -      superset_entry->alias_set = superset;
> -      superset_entry->children
> -	= hash_map<int, int, alias_set_traits>::create_ggc (64);
> -      superset_entry->has_zero_child = 0;
> -      (*alias_sets)[superset] = superset_entry;
> +      superset_entry = init_alias_set_entry (superset);
>      }
>  
>    if (subset == 0)
> Index: testsuite/gcc.dg/alias-8.c
> ===================================================================
> --- testsuite/gcc.dg/alias-8.c	(revision 223772)
> +++ testsuite/gcc.dg/alias-8.c	(working copy)
> @@ -8,5 +8,5 @@ struct s {
>  void
>  func(struct s *ptr)
>  {
> -  *(void **)&ptr->p = 0; /* { dg-warning "type-punned pointer" "" { xfail *-*-* } } */
> +  *(void **)&ptr->p = 0; /* { dg-warning "type-punned pointer" "" { } } */
>  }
> Index: testsuite/gcc.dg/pr62167.c
> ===================================================================
> --- testsuite/gcc.dg/pr62167.c	(revision 223772)
> +++ testsuite/gcc.dg/pr62167.c	(working copy)
> @@ -29,6 +29,8 @@ main ()
>  
>    node.prev = (void *)head;
>  
> +  asm("":"=m"(node.prev));
> +
>    head->first = &node;
>  
>    struct node *n = head->first;
> 
> 

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