Re: Enable pointer TBAA for LTO

[Richard Biener <rguenther@suse.de>]

On Mon, 23 Nov 2015, Jan Hubicka wrote:

> Hi,
> here is updated patch which I finally comitted today.  It addresses all the comments
> and also fixes one nasty bug that really cost me a lot of time to understand. 
> 
> +	  /* LTO type merging does not make any difference between 
> +	     component pointer types.  We may have
> +
> +	     struct foo {int *a;};
> +
> +	     as TYPE_CANONICAL of 
> +
> +	     struct bar {float *a;};
> +
> +	     Because accesses to int * and float * do not alias, we would get
> +	     false negative when accessing the same memory location by
> +	     float ** and bar *. We thus record the canonical type as:
> +
> +	     struct {void *a;};
> +
> +	     void * is special cased and works as a universal pointer type.
> +	     Accesses to it conflicts with accesses to any other pointer
> +	     type.  */
> 
> This problem manifested itself only as a lto-bootstrap miscompare on 32bit
> build and I spent a lot of time localizing the wrong code since it reproduces
> only in quite large programs where we get conficts in canonical type merging
> like this.
> 
> The patch thus updates record_component_aliases to substitute 
> void_ptr_type for all pointer types. I re-did the stats.  Now the 
> improvement on dealII is 14% that is quite a bit lower than earlier, but 
> still substantial.  Since we have voidptr globing counter, I know that 
> the number of disambiguations would go at least 19% up if we did not do 
> it.

Please in future leave patches for review again if you do such
big changes before committing...

I don't understand why we need this (testcase?) because get_alias_set ()
is supposed to do the alias-set of pointer globbing for us.

Thanks,
Richard.

> THere is a lot of low hanging fruit in that area now, but the real 
> solution is to track types that needs to be merge by fortran rules and 
> don't do all this fancy globing for C/C++ types.  I will open branch for 
> IPA work and try to prepare this for next stage 1.
> 
> bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux
> and also on some bigger apps, committed
> 
> Note that we still have bootstrap miscompare with LTO build and --disable-checking,
> I am looking for that now.  Additoinally after fixing the ICEs preventing us to build
> the gnat1 binary, gnat1 aborts. Both these are independent of the patch.
> 
> Honza
> 	* lto.c (iterative_hash_canonical_type): Always recurse for pointers.
> 	(gimple_register_canonical_type_1): Check that pointers do not get
> 	canonical types.
> 	(gimple_register_canonical_type): Do not register pointers.
> 
> 	* tree.c (build_pointer_type_for_mode,build_reference_type_for_mode):
> 	In LTO we do not compute TYPE_CANONICAL of pointers.
> 	(gimple_canonical_types_compatible_p): Improve coments; sanity check
> 	that pointers do not have canonical type that would make us believe
> 	they are different.
> 	* alias.c (get_alias_set): Do structural type equality on pointers;
> 	enable pointer path for LTO; also glob pointer to vector with pointer
> 	to vector element; glob pointers and references for LTO; do more strict
> 	sanity checking about build_pointer_type returning the canonical type
> 	which is also the main variant.
> 	(record_component_aliases): When component type is pointer and we
> 	do LTO; record void_type_node alias set.
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 230714)
> +++ tree.c	(working copy)
> @@ -7919,7 +7919,8 @@ build_pointer_type_for_mode (tree to_typ
>    TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
>    TYPE_POINTER_TO (to_type) = t;
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
> +  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
> +  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
>      TYPE_CANONICAL (t)
> @@ -7987,7 +7988,8 @@ build_reference_type_for_mode (tree to_t
>    TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
>    TYPE_REFERENCE_TO (to_type) = t;
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
> +  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
> +  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
>      TYPE_CANONICAL (t)
> @@ -13224,7 +13226,9 @@ type_with_interoperable_signedness (cons
>     TBAA is concerned.  
>     This function is used both by lto.c canonical type merging and by the
>     verifier.  If TRUST_TYPE_CANONICAL we do not look into structure of types
> -   that have TYPE_CANONICAL defined and assume them equivalent.  */
> +   that have TYPE_CANONICAL defined and assume them equivalent.  This is useful
> +   only for LTO because only in these cases TYPE_CANONICAL equivalence
> +   correspond to one defined by gimple_canonical_types_compatible_p.  */
>  
>  bool
>  gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
> @@ -13265,9 +13269,19 @@ gimple_canonical_types_compatible_p (con
>  	      || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2)));
>    /* If the types have been previously registered and found equal
>       they still are.  */
> +
>    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
>        && trust_type_canonical)
> -    return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> +    {
> +      /* Do not use TYPE_CANONICAL of pointer types.  For LTO streamed types
> +	 they are always NULL, but they are set to non-NULL for types
> +	 constructed by build_pointer_type and variants.  In this case the
> +	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
> +	 all pointers are considered equal.  Be sure to not return false
> +	 negatives.  */
> +      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
> +      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> +    }
>  
>    /* Can't be the same type if the types don't have the same code.  */
>    enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1));
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 230714)
> +++ lto/lto.c	(working copy)
> @@ -388,8 +388,13 @@ iterative_hash_canonical_type (tree type
>  
>    /* All type variants have same TYPE_CANONICAL.  */
>    type = TYPE_MAIN_VARIANT (type);
> +
> +  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
> +     code never use it anyway.  */
> +  if (POINTER_TYPE_P (type))
> +    v = hash_canonical_type (type);
>    /* An already processed type.  */
> -  if (TYPE_CANONICAL (type))
> +  else if (TYPE_CANONICAL (type))
>      {
>        type = TYPE_CANONICAL (type);
>        v = gimple_canonical_type_hash (type);
> @@ -437,7 +442,9 @@ gimple_register_canonical_type_1 (tree t
>  {
>    void **slot;
>  
> -  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
> +  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
> +		       && type_with_alias_set_p (t)
> +		       && !POINTER_TYPE_P (t));
>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -470,7 +477,7 @@ gimple_register_canonical_type_1 (tree t
>  static void
>  gimple_register_canonical_type (tree t)
>  {
> -  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
> +  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
>      return;
>  
>    /* Canonical types are same among all complete variants.  */
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 230714)
> +++ alias.c	(working copy)
> @@ -869,13 +869,23 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      return 0;
> +      /* Handle structure type equality for pointer types.  This is easy
> +	 to do, because the code bellow ignore canonical types on these anyway.
> +	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> +	 be meaningfuly computed by the frotnend.  */
> +      if (!POINTER_TYPE_P (t))
> +	{
> +	  /* In LTO we set canonical types for all types where it makes
> +	     sense to do so.  Double check we did not miss some type.  */
> +	  gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> +          return 0;
> +	}
> +    }
> +  else
> +    {
> +      t = TYPE_CANONICAL (t);
> +      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>      }
> -
> -  t = TYPE_CANONICAL (t);
> -
> -  /* The canonical type should not require structural equality checks.  */
> -  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>  
>    /* If this is a type with a known alias set, return it.  */
>    if (TYPE_ALIAS_SET_KNOWN_P (t))
> @@ -952,20 +962,23 @@ get_alias_set (tree t)
>       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)
> +  else if (POINTER_TYPE_P (t) && t != ptr_type_node)
>      {
>        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.  */
> +	 We also want to make pointer to array/vector equivalent to pointer to
> +	 its element (see the reasoning above). Skip all those types, too.  */
>        for (p = t; POINTER_TYPE_P (p)
> -	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
> +	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
> +	   || TREE_CODE (p) == VECTOR_TYPE;
>  	   p = TREE_TYPE (p))
>  	{
>  	  if (TREE_CODE (p) == REFERENCE_TYPE)
> -	    reference.safe_push (true);
> +	    /* In LTO we want languages that use references to be compatible
> + 	       with languages that use pointers.  */
> +	    reference.safe_push (true && !in_lto_p);
>  	  if (TREE_CODE (p) == POINTER_TYPE)
>  	    reference.safe_push (false);
>  	}
> @@ -981,7 +994,7 @@ get_alias_set (tree t)
>  	set = get_alias_set (ptr_type_node);
>        else
>  	{
> -	  /* Rebuild pointer type from starting from canonical types using
> +	  /* Rebuild pointer type 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.
> @@ -998,9 +1011,15 @@ get_alias_set (tree t)
>  		p = build_reference_type (p);
>  	      else
>  		p = build_pointer_type (p);
> -	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
> +	      gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
> +	      /* build_pointer_type should always return the canonical type.
> +		 For LTO TYPE_CANOINCAL may be NULL, because we do not compute
> +		 them.  Be sure that frontends do not glob canonical types of
> +		 pointers in unexpected way and that p == TYPE_CANONICAL (p)
> +		 in all other cases.  */
> +	      gcc_checking_assert (!TYPE_CANONICAL (p)
> +				   || p == TYPE_CANONICAL (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
> @@ -1015,11 +1034,12 @@ get_alias_set (tree t)
>  	    }
>  	}
>      }
> -  /* In LTO the rules above needs to be part of canonical type machinery.
> -     For now just punt.  */
> -  else if (POINTER_TYPE_P (t)
> -	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
> -    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
> +  /* Alias set of ptr_type_node is special and serve as universal pointer which
> +     is TBAA compatible with every other pointer type.  Be sure we have the
> +     alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
> +     of pointer types NULL.  */
> +  else if (t == ptr_type_node)
> +    set = new_alias_set ();
>  
>    /* Otherwise make a new alias set for this type.  */
>    else
> @@ -1155,7 +1175,42 @@ record_component_aliases (tree type)
>      case QUAL_UNION_TYPE:
>        for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
>  	if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
> -	  record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
> +	  {
> +	    /* LTO type merging does not make any difference between 
> +	       component pointer types.  We may have
> +
> +	       struct foo {int *a;};
> +
> +	       as TYPE_CANONICAL of 
> +
> +	       struct bar {float *a;};
> +
> +	       Because accesses to int * and float * do not alias, we would get
> +	       false negative when accessing the same memory location by
> +	       float ** and bar *. We thus record the canonical type as:
> +
> +	       struct {void *a;};
> +
> +	       void * is special cased and works as a universal pointer type.
> +	       Accesses to it conflicts with accesses to any other pointer
> +	       type.  */
> +	    tree t = TREE_TYPE (field);
> +	    if (in_lto_p)
> +	      {
> +		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
> +		   element type and that type has to be normalized to void *,
> +		   too, in the case it is a pointer. */
> +		while ((TREE_CODE (t) == ARRAY_TYPE
> +			&& (!COMPLETE_TYPE_P (t)
> +			    || TYPE_NONALIASED_COMPONENT (t)))
> +		       || TREE_CODE (t) == VECTOR_TYPE)
> +		  t = TREE_TYPE (t);
> +		if (POINTER_TYPE_P (t))
> +		  t = ptr_type_node;
> +	      }
> +	   
> +	    record_alias_subset (superset, get_alias_set (t));
> +	  }
>        break;
>  
>      case COMPLEX_TYPE:
> 
> 

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