Re: Simplify enumerate and array types

[Richard Biener <rguenther at suse dot de>]

On Sun, 11 Nov 2018, Jan Hubicka wrote:

> Hi,
> this patch should be last patch for type simplification (modulo possible bits
> that needs clearing I still notice).  It does the following
>  1) enables the patch to simplify aggregates also for enums.
>     While this does not affect C++, in C we want pointers to incomplete
>     and complete variant of enums the same.
>  2) turns arrays to arrays of incomplete type. This is used for pointers
>     to arrays
>  3) turns arrays to arrays of simplified type. This is used for arrays of
>     pointers to agreggates.
> 
> The patch extends fld_type_variant_equal_p and fld_type_variant to live with
> fact that arrays may have different TREE_TYPE within the TYPE_NEXT_VARIANT
> lists and also introduced simplified_type_hash that holds the simplified arrays.
> If build_array_type_1 was able to share arrays with TYPELESS_STORAGE flag
> this hash would not be necessary. But I am unsure why that is done in there.
> 
> With this there are cca 9k types in Firefox (out of 80k) with duplicates and
> 20k type duplicates overall.  I inspected manually some of them and the reasons
> can be tracked down to differences in VAR_DECL flags for vtables and
> inherently by referring such types by TYPE_CONTEXT or as a field.
> I will try to cleanup visibilities next stage1, but I think practically this
> is quite non-critical as it would be very hard to make number of copies to
> explide (there is never more than 3 types in the duplicate chain for Firefox
> and we used to have more than 4k duplicates of single type before the changes)
> 
> Bootstrapped/regtested x86_64-linux.
> OK?
> 
> Honza
> 	* ipa-devirt.c (add_type_duplicate): Do not ICE on incomplete enums.
> 	* tree.c (build_array_type_1): Forward declare.
> 	(fld_type_variant_equal_p): Add INNER_TYPE parameter.
> 	(fld_type_variant): Likewise.
> 	(fld_simplified_types): New hash.
> 	(fld_incomplete_type_of): Handle array and enumeration types.
> 	(fld_simplified_type): Handle simplification of arrays.
> 	(free_lang_data): Allocate and free simplified types hash.
> Index: ipa-devirt.c
> ===================================================================
> --- ipa-devirt.c	(revision 266011)
> +++ ipa-devirt.c	(working copy)
> @@ -1705,7 +1705,8 @@ add_type_duplicate (odr_type val, tree t
>    else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
>      {
>        prevail = true;
> -      build_bases = TYPE_BINFO (type);
> +      if (TREE_CODE (type) == RECORD_TYPE)
> +        build_bases = TYPE_BINFO (type);
>      }
>    else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
>      ;
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 266011)
> +++ tree.c	(working copy)
> @@ -265,6 +265,8 @@ static void print_type_hash_statistics (
>  static void print_debug_expr_statistics (void);
>  static void print_value_expr_statistics (void);
>  
> +static tree build_array_type_1 (tree, tree, bool, bool);
> +
>  tree global_trees[TI_MAX];
>  tree integer_types[itk_none];
>  
> @@ -5108,10 +5110,11 @@ fld_simplified_type_name (tree type)
>  
>  /* Do same comparsion as check_qualified_type skipping lang part of type
>     and be more permissive about type names: we only care that names are
> -   same (for diagnostics) and that ODR names are the same.  */
> +   same (for diagnostics) and that ODR names are the same.
> +   If INNER_TYPE is non-NULL, be sure that TREE_TYPE match it.  */
>  
>  static bool
> -fld_type_variant_equal_p (tree t, tree v)
> +fld_type_variant_equal_p (tree t, tree v, tree inner_type)
>  {
>    if (TYPE_QUALS (t) != TYPE_QUALS (v)
>        /* We want to match incomplete variants with complete types.
> @@ -5121,21 +5124,24 @@ fld_type_variant_equal_p (tree t, tree v
>  	      || TYPE_USER_ALIGN (t) != TYPE_USER_ALIGN (v)))
>        || fld_simplified_type_name (t) != fld_simplified_type_name (v)
>        || !attribute_list_equal (TYPE_ATTRIBUTES (t),
> -			        TYPE_ATTRIBUTES (v)))
> +			        TYPE_ATTRIBUTES (v))
> +      || (inner_type && TREE_TYPE (v) != inner_type))
>      return false;
> - 
> +
>    return true;
>  }
>  
> -/* Find variant of FIRST that match T and create new one if necessary.  */
> +/* Find variant of FIRST that match T and create new one if necessary.
> +   Set TREE_TYPE to INNER_TYPE if non-NULL.  */
>  
>  static tree
> -fld_type_variant (tree first, tree t, struct free_lang_data_d *fld)
> +fld_type_variant (tree first, tree t, struct free_lang_data_d *fld,
> +		  tree inner_type = NULL)
>  {
>    if (first == TYPE_MAIN_VARIANT (t))
>      return t;
>    for (tree v = first; v; v = TYPE_NEXT_VARIANT (v))
> -    if (fld_type_variant_equal_p (t, v))
> +    if (fld_type_variant_equal_p (t, v, inner_type))
>        return v;
>    tree v = build_variant_type_copy (first);
>    TYPE_READONLY (v) = TYPE_READONLY (t);
> @@ -5153,7 +5159,9 @@ fld_type_variant (tree first, tree t, st
>        SET_TYPE_ALIGN (v, TYPE_ALIGN (t));
>        TYPE_USER_ALIGN (v) = TYPE_USER_ALIGN (t);
>      }
> -  gcc_checking_assert (fld_type_variant_equal_p (t,v));
> +  if (inner_type)
> +    TREE_TYPE (v) = inner_type;
> +  gcc_checking_assert (fld_type_variant_equal_p (t,v, inner_type));
>    add_tree_to_fld_list (v, fld);
>    return v;
>  }
> @@ -5162,6 +5170,9 @@ fld_type_variant (tree first, tree t, st
>  
>  static hash_map<tree, tree> *fld_incomplete_types;
>  
> +/* Map types to simplified types.  */
> +static hash_map<tree, tree> *fld_simplified_types;
> +
>  /* For T being aggregate type try to turn it into a incomplete variant.
>     Return T if no simplification is possible.  */
>  
> @@ -5189,7 +5200,32 @@ fld_incomplete_type_of (tree t, struct f
>  	}
>        return t;
>      }
> -  if (!RECORD_OR_UNION_TYPE_P (t) || !COMPLETE_TYPE_P (t))
> +  if (TREE_CODE (t) == ARRAY_TYPE)
> +    {
> +      tree incomplete = fld_incomplete_type_of (TREE_TYPE (t), fld);
> +
> +      if (TREE_TYPE (t) == incomplete)
> +	return t;
> +
> +      if (TYPE_MAIN_VARIANT (t) != t)
> +	return fld_type_variant
> +		 (fld_incomplete_type_of (TYPE_MAIN_VARIANT (t), fld),
> +		  t, fld, incomplete);

Somehow do this first, otherwise 'incomplete' above is useless
work?

> +      bool existed;
> +      tree &array
> +	 = fld_incomplete_types->get_or_insert (t, &existed);
> +      if (!existed)
> +	{
> +          array = build_array_type_1 (incomplete, TYPE_DOMAIN (t),
> +				      TYPE_TYPELESS_STORAGE (t), false);
> +	  TYPE_CANONICAL (array) = TYPE_CANONICAL (t);
> +          add_tree_to_fld_list (array, fld);
> +	}
> +      return array;
> +    }
> +  if ((!RECORD_OR_UNION_TYPE_P (t) && TREE_CODE (t) != ENUMERAL_TYPE)
> +      || !COMPLETE_TYPE_P (t))
>      return t;
>    if (TYPE_MAIN_VARIANT (t) == t)
>      {
> @@ -5201,18 +5237,18 @@ fld_incomplete_type_of (tree t, struct f
>  	{
>  	  copy = build_distinct_type_copy (t);
>  
> -	  /* It is possible type was not seen by free_lang_data yet.  */
> +	  /* It is possible that type was not seen by free_lang_data yet.  */
>  	  add_tree_to_fld_list (copy, fld);
>  	  TYPE_SIZE (copy) = NULL;
> -	  SET_TYPE_MODE (copy, VOIDmode);
> -	  SET_TYPE_ALIGN (copy, BITS_PER_UNIT);
>  	  TYPE_USER_ALIGN (copy) = 0;
>  	  TYPE_SIZE_UNIT (copy) = NULL;
>  	  TYPE_CANONICAL (copy) = TYPE_CANONICAL (t);
> -	  TYPE_TYPELESS_STORAGE (copy) = 0;
>  	  TREE_ADDRESSABLE (copy) = 0;
>  	  if (AGGREGATE_TYPE_P (t))
>  	    {
> +	      SET_TYPE_MODE (copy, VOIDmode);
> +	      SET_TYPE_ALIGN (copy, BITS_PER_UNIT);
> +	      TYPE_TYPELESS_STORAGE (copy) = 0;
>  	      TYPE_FIELDS (copy) = NULL;
>  	      TYPE_BINFO (copy) = NULL;
>  	    }
> @@ -5231,8 +5267,34 @@ fld_incomplete_type_of (tree t, struct f
>  static tree
>  fld_simplified_type (tree t, struct free_lang_data_d *fld)
>  {
> -  if (t && POINTER_TYPE_P (t))
> +  if (!t)
> +    return t;
> +  if (POINTER_TYPE_P (t))
>      return fld_incomplete_type_of (t, fld);
> +  if (TREE_CODE (t) == ARRAY_TYPE)
> +    {
> +      tree simplified = fld_simplified_type (TREE_TYPE (t), fld);

This looks like almost a duplicate - sth we can factor out please?

We do not fixup "toplevel" aggregates - why fixup toplevel arrays here?
Is that really necessary?

Richard.

> +      if (TREE_TYPE (t) == simplified)
> +	return t;
> +
> +      if (TYPE_MAIN_VARIANT (t) != t)
> +	return fld_type_variant
> +		 (fld_simplified_type (TYPE_MAIN_VARIANT (t), fld),
> +		  t, fld, simplified);
> +
> +      bool existed;
> +      tree &array
> +	 = fld_simplified_types->get_or_insert (t, &existed);
> +      if (!existed)
> +	{
> +          array = build_array_type_1 (simplified, TYPE_DOMAIN (t),
> +				      TYPE_TYPELESS_STORAGE (t), false);
> +	  TYPE_CANONICAL (array) = TYPE_CANONICAL (t);
> +          add_tree_to_fld_list (array, fld);
> +	}
> +      return array;
> +    }
>    return t;
>  }
>  
> @@ -6067,6 +6129,7 @@ free_lang_data (void)
>      return 0;
>  
>    fld_incomplete_types = new hash_map<tree, tree>;
> +  fld_simplified_types = new hash_map<tree, tree>;
>  
>    /* Provide a dummy TRANSLATION_UNIT_DECL if the FE failed to provide one.  */
>    if (vec_safe_is_empty (all_translation_units))
> @@ -6114,6 +6177,7 @@ free_lang_data (void)
>    rebuild_type_inheritance_graph ();
>  
>    delete fld_incomplete_types;
> +  delete fld_simplified_types;
>  
>    return 0;
>  }
> 
> 

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