Re: Enable pointer TBAA for LTO

[Richard Biener <rguenther@suse.de>]

On Sun, 8 Nov 2015, Jan Hubicka wrote:

> Hi,
> this patch adds basic TBAA for pointers to LTO.  The basic scheme is simple;
> because TYPE_CANONICAL is not really needed by get_alias_set, we completely
> drop the caluclation of these (which also saves about 50% canonical type hash
> searches) and update get_alias_set to not punt on pointers with
> TYPE_STRUCTURAL_EQUALITY.
> 
> The patch makes quite nice improvements (32%) on number of disambiguations on
> dealII (that is my random C++ testbed):
> 
> Before:
> [WPA] GIMPLE canonical type table: size 16381, 817 elements, 35453 searches, 91 collisions (ratio: 0.002567)
> [WPA] GIMPLE canonical type pointer-map: 817 elements, 15570 searches           
> 
> after:
> [WPA] GIMPLE canonical type table: size 16381, 822 elements, 14863 searches, 114 collisions (ratio: 0.007670)
> [WPA] GIMPLE canonical type pointer-map: 822 elements, 12663 searches           
> 
> The number of disambiguations goes 1713472->2331078 (32%)
> and number of queries goes 3387753->3669698 (8%)
> We get code size growth 677527->701782 (3%)
> 
> Also a query is disambiguated 63% of the time instead of 50% we had before.
> 
> Clearly there are many areas for improvements (since functions are
> TYPE_STRUCTURAL_EQUALITY in LTO we ptr_type_node alias set on them), but that
> M
> can wait for next stage1.
> 
> lto-bootstrapped/regtested x86_64-linux and also used it in my tree for quite
> a while, so the patch was tested on Firefox and other applications.
> 
> OK?
> Honza
> 
> 	* alias.c (get_alias_set): Do structural equality for pointer types;
> 	drop LTO specific path.
> 	* lto.c (iterative_hash_canonical_type): Do not compute TYPE_CANONICAL
> 	for pointer types.
> 	(gimple_register_canonical_type_1): Likewise.
> 	(gimple_register_canonical_type): Likewise.
> 	(lto_register_canonical_types): Do not clear canonical types of pointer
> 	types.
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 229968)
> +++ lto/lto.c	(working copy)
> @@ -396,8 +396,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 becuase 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);
> @@ -445,7 +450,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)
> +		       && TREE_CODE (t) != POINTER_TYPE);

POINTER_TYPE_P

>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -478,7 +485,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.  */
> @@ -498,14 +505,13 @@ static void
>  lto_register_canonical_types (tree node, bool first_p)
>  {
>    if (!node
> -      || !TYPE_P (node))
> +      || !TYPE_P (node) || POINTER_TYPE_P (node))
>      return;
>  
>    if (first_p)
>      TYPE_CANONICAL (node) = NULL_TREE;
>  
> -  if (POINTER_TYPE_P (node)
> -      || TREE_CODE (node) == COMPLEX_TYPE
> +  if (TREE_CODE (node) == COMPLEX_TYPE
>        || TREE_CODE (node) == ARRAY_TYPE)
>      lto_register_canonical_types (TREE_TYPE (node), first_p);

Hmm, here we'll miss registering canoncial types for the
pointed-to type.  I believe this will miss FILE for example but also
some va_list types?  Please drop this change.

> Index: tree.c
> ===================================================================
> --- tree.c	(revision 229968)
> +++ tree.c	(working copy)
> @@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
>    /* If the types have been previously registered and found equal
>       they still are.  */
>    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
> +      && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)

But TYPE_CANONICAL (t1) should be NULL_TREE for POINTER_TYPE_P?

>        && trust_type_canonical)
>      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
>  
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 229968)
> +++ alias.c	(working copy)
> @@ -869,13 +874,19 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      return 0;
> +      /* LTO frontend does not assign canonical types to pointers (which we
> +	 ignore anyway) and we compute them.  The following path may be
> +	 probably enabled for non-LTO, too, and it may improve TBAA for
> +	 pointers to types with structural equality.  */
> +      if (!in_lto_p || !POINTER_TYPE_P (t))
> +        return 0;

No new LTO paths please, do the suggested change immediately.

> +    }
> +  else
> +    {
> +      t = TYPE_CANONICAL (t);
> +      /* The canonical type should not require structural equality checks.  */
> +      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 +963,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);
>  	}
> @@ -998,9 +1012,23 @@ get_alias_set (tree t)
>  		p = build_reference_type (p);
>  	      else
>  		p = build_pointer_type (p);
> -	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
> +	      p = TYPE_MAIN_VARIANT (p);
> +	      /* Normally all pointer types are built by
> + 		 build_pointer_type_for_mode which ensures they have canonical
> +		 type unless they point to type with structural equality.
> +		 LTO frontend produce pointer types without TYPE_CANONICAL
> +		 that are then added to TYPE_POINTER_TO lists and 
> +		 build_pointer_type_for_mode will end up picking one for us.
> +		 Declare it the canonical one.  This is the same as
> +		 build_pointer_type_for_mode would do. */
> +	      if (!TYPE_CANONICAL (p))
> +		{
> +		  TYPE_CANONICAL (p) = p;
> +		  gcc_checking_assert (in_lto_p);
> +		}
> +	      else
> +	        gcc_checking_assert (p == TYPE_CANONICAL (p));

The assert can trigger as
build_pointer_type_for_mode builds SET_TYPE_STRUCTURAL_EQUALITY pointer
types for SET_TYPE_STRUCTURAL_EQUALITY pointed-to types.  Ah,
looking up more context reveals

      if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
        set = get_alias_set (ptr_type_node);

Not sure why you adjust TYPE_CANONICAL here at all either.

Otherwise looks ok.

RIchard.


>  	    }
> -          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 +1043,6 @@ 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));
>  
>    /* Otherwise make a new alias set for this type.  */
>    else
> 
> 

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