This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Cleanup and improve canonical type construction in LTO


On Wed, 20 May 2015, Jan Hubicka wrote:

> Richard,
> this is my attempt to make sense of TYPE_CANONICAL at LTO.  My undrestanding is
> that gimple_canonical_types_compatible_p needs to return true for all pairs of
> types that are considered compatible across compilation unit for any of
> languages we support (and in a sane way for cross language, too) and moreover
> it needs to form an equivalence so it can be used to do canonical type merging.
> 
> Now C definition of type compatibility ignores type names and only boils down
> to structural compare (which we get wrong for unions, but I will look into that
> incrementally, also C explicitely require fields names to match, which we don't)
> and it of course says that incompete type can match complete.

field-names are difficult to match cross-language.

> This is bit generous on structures and unions, because every incomplete
> RECORD_TYPE is compatible with every RECORD_TYPE in program and similarly
> incomplete UNION_TYPE is compatible with every UNION_TYPE in program.
> 
> Now from the fact that gimple_canonical_types_compatible_p must be equivalence
> (and thus transitive) we immmediately get that there is no way to make
> difference between two RECORD_TYPEs (or UNION_TYPEs) at all: there always may
> be incomplete that forces them equivalent.
> 
> This is not how the code works. gimple_canonical_types_compatible_p will not
> match complete type with incomplete and this is not a prolblem only because
> TYPE_CANONICAL matters for complete types only. TBAA machinery never needs
> alias sets of an incomplete type (modulo bugs). 

Correct.

> More precisely we have two equivalences:
>  1) full structural equivalence matching fields, array sizes and function
>     parameters, where pointer types are however recursively matched only with 2)

Not sure about function parameters (well, function types at all - they
don't play a role in TBAA) - function "members" are always pointers, so 
see 2)

>  2) structural equivalence ignoring any info from complete types:
>     here all RECORD_TYPEs are equal, so are UNION_TYPEs, for functions we
>     can only match return value (because of existence of non-prototypes),
>     for arrays only TREE_TYPE.
>     In this equivalence we also can't match TYPE_MODE of aggregates/arrays
>     because it may not be set for incomplete ones.
> 
> Now our implementation somehow compute only 1) and 2) is approximated by
> matching TREE_CODE of the pointer-to type.  This is unnecesarily pesimistic.
> Pointer to pointer to int does not need to match pointer to pointer to
> structure. 

Note that you have (a lot of!) pointer members that point to structures
in various state of completeness.  A pointer to an incomplete type
needs to match all other pointer types (well, the current code tries
to make the exception that a pointer to an aggregate stays a pointer
to an aggregate - thus the matching of pointed-to type - sorry to
only remember now the connection to incompleteness ...)

> The patch bellow changes it in the following way:
> 
>  a) it adds MATCH_INCOMPLETE_TYPES parameter to
>     gimple_canonical_types_compatible_p and gimple_canonical_type_hash
>     to determine whether we compute equivalence 1) or 2).
> 
>     The way we handle pointers is updated so we set MATCH_INCOMPLETE_TYPES
>     when recursing down to pointer type.  This makes it possible for
>     complete structure referring incomplete pointer type to be equivalent with
>     a complete structure referring complete pointer type.

But does this really end up getting more equivalence classes than the
crude approach matching TREE_CODE?

>     I believe that in this definition we do best possible equivalence
>     passing the rules above and we do not need to care about SCC - the
>     only way how type can reffer itself is via pointer and that will make us
>     to drop to MATCH_INCOMPLETE_TYPES.
>  b) it disables TYPE_CANONICAL calculation for incomplete types and functions
>     types. It makes it clear that TYPE_CANONICAL is always 1) which is not
>     defined on these.

Sounds good (please split up the patch - I'm actually not looking at
it right now).

>     This seems to reduce number of canonical types computed to 1/3.
>     We get bit more recursion in gimple_canonical_types_compatible_p
>     and gimple_canonical_type_hash but only in MATCH_INCOMPLETE_TYPES mode
>     that converges quite quickly.
> 
>     I know that it is not how other FEs works, but it is because they
>     do have type equivalence notion that include TYPE_NAME so it is possible
>     to determine TYPE_CANONICAL uniquely before the type is completed.

The code was never intended to be "generic" it was LTO specific and
middle-end specific (for TBAA and useless_type_conversion_p).  Frontends
(well, the C++ frontend) use TYPE_CANONICAL for their own idea of
"canonicalness".

>  c) adds sanity checking
> 
>     - I can check that canonical_type_hash is not used for incomplete types
>       (modulo ARRAY_TYPE that may appear as a field of complete structure)
>       so the definition of cases we flip from complete to incomplete is 
>       catching everything

Sounds good.

>     - I can check that alias is never used on types we do not define
>       TYPE_CANONICAL for. This actually catch a case in ipa-icf-gimple that
>       tires to compare alias classes of voidtypes.

How do you verify that?  (just using NULL TYPE_CANONICAL will end up
using alias-set zero I think)

>     - I added check that we do not have prototypes of method types since
>       I make difference between methods and functions (this is useful so
>       we also match the BASETYPE argument)

?

>  d) drops TYPE_METHOD_BASETYPE hashing since it is not tested by
>     gimple_canonical_types_compatible_p
>     it also drops matching function type attributes that seems wrong as discused
>     earlier.

Sounds good.

> 
> On Firefox the canonical table changes from:
> [WPA] GIMPLE canonical type table: size 262139, 110992 elements, 2153232 searches, 808238 collisions (ratio: 0.375360)
> [WPA] GIMPLE canonical type pointer-map: 110992 elements, 4723435 searches
> to:
> [WPA] GIMPLE canonical type table: size 65521, 32676 elements, 1634147 searches, 474609 collisions (ratio: 0.290432)
> [WPA] GIMPLE canonical type pointer-map: 32676 elements, 2302719 searches
>
> I also checked that before throwing away all the functions/method types, the
> number of canonical types grown up to about 135k, so we seem to have 20-30%
> increase in precision.

Can you highlight some cases please?  I'd be interested to compare just
the change to add following pointers (so that part should be split out
of the patch at least).

>  Code quality does not seem to be affected too much,
> which I suppose is partly thanks to that tree-ssa-alias.c pointer hack.  My
> main point was to cleanup the hack about comparing only TYPE_CODE of
> pointer_type and make more sense of the whole machinery.

Well, TYPE_CODE was supposed to mimic what you do explicitely now.  I'm
curious when the recursion determines incompatibility but the TYPE_CODE
is equal.  What cases are those?

How do you handle void * vs. any other pointer type?  For cross-language
LTO I think we need to treat those compatible.  At least void * is
equal to struct Foo * (with incomplete Foo).

> Bootstrapped/regtested x86_64-linux with LTO and also tested on Firefox. ppc64
> build in progress. OK?

Not looking at the patch - please split it up into small pieces so we
can bisect in case of problems.  This is a tricky area, esp. considering
cross-language LTO.  We might be not conservative enough with
canonical types (given the get_alias_set pointer handling).

Richard.

> Honza
> 
> 	* tree.h (prototype_p): Constify.
> 	(gimple_canonical_types_compatible_flags): New flags.
> 	(gimple_canonical_types_compatible_p): UPdate prototype.
> 	* tree.c (prototype_p): Constify.
> 	(gimple_canonical_types_compatible_p): Turn trust_type_canonical into
> 	flags; support MATCH_WITH_INCOMPLETE_TYPE; drop comparsion of
> 	attributes.
> 	(verify_type): Remove FIXME for METHOD_TYPE; update FIXME on
> 	FUNCITON_TYPE; add check that METHOD_TYPE is never !prototype_p.
> 	* alias.c (get_alias_set): Check that in LTO no types
> 	are TYPE_STRUCTURAL_EQUALITY_P.
> 	* tree-ssa-alias.c (same_type_for_tbaa): Likewise.
> 	* ipa-icf-gimple.c (func_checker::compatible_types_p): VOID_TYPE
> 	is always compatible.
> 
> 	* lto.c (iterative_hash_canonical_type): Add MATCH_INCOMPLTE
> 	paramter.
> 	(hash_canonical_type): Likewise.
> 
> Index: tree.h
> ===================================================================
> --- tree.h	(revision 223409)
> +++ tree.h	(working copy)
> @@ -4375,7 +4375,7 @@ extern int operand_equal_for_phi_arg_p (
>  extern tree create_artificial_label (location_t);
>  extern const char *get_name (tree);
>  extern bool stdarg_p (const_tree);
> -extern bool prototype_p (tree);
> +extern bool prototype_p (const_tree);
>  extern bool is_typedef_decl (tree x);
>  extern bool typedef_variant_p (tree);
>  extern bool auto_var_in_fn_p (const_tree, const_tree);
> @@ -4569,8 +4569,20 @@ extern int tree_map_base_eq (const void
>  extern unsigned int tree_map_base_hash (const void *);
>  extern int tree_map_base_marked_p (const void *);
>  extern void DEBUG_FUNCTION verify_type (const_tree t);
> -extern bool gimple_canonical_types_compatible_p (const_tree, const_tree,
> -						 bool trust_type_canonical = true);
> +
> +/* Flags used by gimple_canonical_types_compatible_p.  */
> +enum gimple_canonical_types_compatible_flags
> +  {
> +    /* Asume that TYPE_CANONICAL is set in a way that two types have
> +       the same canonical type if and only if
> +       gimple_canonical_types_compatible_p (t1,t2, 0) is true.  */
> +    MATCH_TYPE_CANONICAL = 1,
> +    /* Match all types as if they were incomplete.  */
> +    MATCH_WITH_INCOMPLETE_TYPE = 2
> +  };
> +extern bool gimple_canonical_types_compatible_p
> +    (const_tree, const_tree,
> +     unsigned int flags = MATCH_TYPE_CANONICAL);
>  
>  #define tree_map_eq tree_map_base_eq
>  extern unsigned int tree_map_hash (const void *);
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 223409)
> +++ tree.c	(working copy)
> @@ -11579,7 +11579,7 @@ stdarg_p (const_tree fntype)
>  /* Return true if TYPE has a prototype.  */
>  
>  bool
> -prototype_p (tree fntype)
> +prototype_p (const_tree fntype)
>  {
>    tree t;
>  
> @@ -12707,8 +12707,9 @@ verify_type_variant (const_tree t, tree
>     that have TYPE_CANONICAL defined and assume them equivalent.  */
>  
>  bool
> -gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
> -				     bool trust_type_canonical)
> +gimple_canonical_types_compatible_p
> +	 (const_tree t1, const_tree t2,
> +          unsigned int flags)
>  {
>    /* Before starting to set up the SCC machinery handle simple cases.  */
>  
> @@ -12723,8 +12724,15 @@ 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)
> -      && trust_type_canonical)
> -    return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> +      && (flags & MATCH_TYPE_CANONICAL))
> +    {
> +      if (TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
> +	return true;
> +      /* TYPE_CANONICAL is always computed with an assumption that the type
> +	 is complete.  */
> +      if (!(flags & MATCH_WITH_INCOMPLETE_TYPE))
> +	return false;
> +    }
>  
>    /* Can't be the same type if the types don't have the same code.  */
>    if (TREE_CODE (t1) != TREE_CODE (t2))
> @@ -12737,8 +12745,12 @@ gimple_canonical_types_compatible_p (con
>        || TREE_CODE (t1) == NULLPTR_TYPE)
>      return true;
>  
> -  /* Can't be the same type if they have different mode.  */
> -  if (TYPE_MODE (t1) != TYPE_MODE (t2))
> +  /* Can't be the same type if they have different mode.
> +     Incomplete arrays and aggregates do not have TYPE_MODE defined.  */
> +  if ((!(flags & MATCH_WITH_INCOMPLETE_TYPE)
> +       || (TREE_CODE (t1) != ARRAY_TYPE
> +           && !AGGREGATE_TYPE_P (t1)))
> +      && TYPE_MODE (t1) != TYPE_MODE (t2))
>      return false;
>  
>    /* Non-aggregate types can be handled cheaply.  */
> @@ -12759,18 +12771,18 @@ gimple_canonical_types_compatible_p (con
>  	  && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
>  	return false;
>  
> -      /* For canonical type comparisons we do not want to build SCCs
> -	 so we cannot compare pointed-to types.  But we can, for now,
> -	 require the same pointed-to type kind and match what
> -	 useless_type_conversion_p would do.  */
>        if (POINTER_TYPE_P (t1))
>  	{
> -	  if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
> -	      != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
> +	  tree pt1 = TREE_TYPE (t1), pt2 = TREE_TYPE(t2);
> +	  if (TYPE_ADDR_SPACE (pt1) != TYPE_ADDR_SPACE (pt2))
>  	    return false;
>  
> -	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> +	  if (TREE_CODE (pt1) != TREE_CODE (pt2))
>  	    return false;
> +
> +	  /* Tail-recurse to pointed-to type.  */
> +	  return gimple_canonical_types_compatible_p
> +		 (pt1, pt2, flags | MATCH_WITH_INCOMPLETE_TYPE);
>  	}
>  
>        /* Tail-recurse to components.  */
> @@ -12778,7 +12790,7 @@ gimple_canonical_types_compatible_p (con
>  	  || TREE_CODE (t1) == COMPLEX_TYPE)
>  	return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
>  						    TREE_TYPE (t2),
> -						    trust_type_canonical);
> +						    flags);
>  
>        return true;
>      }
> @@ -12788,12 +12800,20 @@ gimple_canonical_types_compatible_p (con
>      {
>      case ARRAY_TYPE:
>        /* Array types are the same if the element types are the same and
> -	 the number of elements are the same.  */
> -      if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
> -						trust_type_canonical)
> +	 the number of elements are the same.
> +
> +	 When MATCH_WITH_INCOMPLETE_TYPE is set, bypass the check
> +	 on number of elements.
> +	 When recursing, clear MATCH_WITH_INCOMPLETE_TYPE because there is
> +	 no way to make incomplete array of array.  */
> +      if (!gimple_canonical_types_compatible_p
> +	     (TREE_TYPE (t1), TREE_TYPE (t2),
> +	      flags & ~MATCH_WITH_INCOMPLETE_TYPE)
>  	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
>  	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
>  	return false;
> +      else if (flags & MATCH_WITH_INCOMPLETE_TYPE)
> +	return true;
>        else
>  	{
>  	  tree i1 = TYPE_DOMAIN (t1);
> @@ -12832,14 +12852,19 @@ gimple_canonical_types_compatible_p (con
>      case METHOD_TYPE:
>      case FUNCTION_TYPE:
>        /* Function types are the same if the return type and arguments types
> -	 are the same.  */
> +	 are the same.
> +	 It is possible that function pointers have return values and parameters
> +	 of incomplete types; permit that by not clearing
> +	 MATCH_WITH_INCOMPLETE_TYPE  */
>        if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
> -						trust_type_canonical))
> -	return false;
> -
> -      if (!comp_type_attributes (t1, t2))
> +						flags))
>  	return false;
>  
> +      /* We must permit a match between !prototype_p and prototype_p for
> +	 functions; methods are never !prototype_p.  */
> +      if ((flags & MATCH_WITH_INCOMPLETE_TYPE)
> +	  && TREE_CODE (t1) == FUNCTION_TYPE)
> +	return true;
>        if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
>  	return true;
>        else
> @@ -12851,8 +12876,7 @@ gimple_canonical_types_compatible_p (con
>  	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
>  	    {
>  	      if (!gimple_canonical_types_compatible_p
> -		     (TREE_VALUE (parms1), TREE_VALUE (parms2),
> -		      trust_type_canonical))
> +		     (TREE_VALUE (parms1), TREE_VALUE (parms2), flags))
>  		return false;
>  	    }
>  
> @@ -12868,6 +12892,15 @@ gimple_canonical_types_compatible_p (con
>        {
>  	tree f1, f2;
>  
> +	/* C standrad require incomplete structures and unions to be
> +	   considered compatible with complete ones regardless their TYPE_NAME
> +	   when they come from different translation units.
> +	   We must consider transitive closure here, so 
> +	   every structure/union is equivalent to each other.  */
> +	   
> +	if (flags & MATCH_WITH_INCOMPLETE_TYPE)
> +	  return true;
> +
>  	/* For aggregate types, all the fields must be the same.  */
>  	for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
>  	     f1 || f2;
> @@ -12884,8 +12917,7 @@ gimple_canonical_types_compatible_p (con
>  	    if (DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
>  		|| !gimple_compare_field_offset (f1, f2)
>  		|| !gimple_canonical_types_compatible_p
> -		      (TREE_TYPE (f1), TREE_TYPE (f2),
> -		       trust_type_canonical))
> +		      (TREE_TYPE (f1), TREE_TYPE (f2), flags))
>  	      return false;
>  	  }
>  
> @@ -12936,20 +12968,16 @@ verify_type (const_tree t)
>        debug_tree (ct);
>        error_found = true;
>      }
> -  /* Method and function types can not be used to address memory and thus
> -     TYPE_CANONICAL really matters only for determining useless conversions.
> -
> -     FIXME: C++ FE does not agree with gimple_canonical_types_compatible_p
> -     here.  gimple_canonical_types_compatible_p calls comp_type_attributes
> -     while for C++ FE the attributes does not make difference.  */
> -  else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
> +  /* FIXME: For builtin function types C++ FE sometimes links TYPE_CANONICAL
> +     that is not compatible.  */
> +  else if (TREE_CODE (t) == FUNCTION_TYPE)
>      ;
>    else if (t != ct
>  	   /* FIXME: gimple_canonical_types_compatible_p can not compare types
>  	      with variably sized arrays because their sizes possibly
>  	      gimplified to different variables.  */
>  	   && !variably_modified_type_p (ct, NULL)
> -	   && !gimple_canonical_types_compatible_p (t, ct, false))
> +	   && !gimple_canonical_types_compatible_p (t, ct, 0))
>      {
>        error ("TYPE_CANONICAL is not compatible");
>        debug_tree (ct);
> @@ -13249,6 +13277,13 @@ verify_type (const_tree t)
>  	}
>      }
>    
> +  /* None of languages we support has prototypes on methods.  This is used
> +     by the gimple_canonical_types_compatible_p to improve quality of TBAA.  */
> +  if (TREE_CODE (t) == METHOD_TYPE && !prototype_p (t))
> +    {
> +      error ("METHOD_TYPE that is not a prototype.");
> +      error_found = true;
> +    }
>  
>  
>    if (error_found)
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 223409)
> +++ alias.c	(working copy)
> @@ -785,6 +785,8 @@ get_alias_set (tree t)
>       use alias set zero.  */
>    if (TYPE_STRUCTURAL_EQUALITY_P (t))
>      {
> +      /* LTO should fill canonical types of all relevant types.  */
> +      gcc_checking_assert (!in_lto_p);
>        /* Allow the language to specify another alias set for this
>  	 type.  */
>        set = lang_hooks.get_alias_set (t);
> Index: ipa-icf-gimple.c
> ===================================================================
> --- ipa-icf-gimple.c	(revision 223409)
> +++ ipa-icf-gimple.c	(working copy)
> @@ -271,6 +271,9 @@ func_checker::compatible_types_p (tree t
>    if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
>      return return_false_with_msg ("restrict flags are different");
>  
> +  if (TREE_CODE (t1) == VOID_TYPE)
> +    return true;
> +
>    if (!types_compatible_p (t1, t2))
>      return return_false_with_msg ("types are not compatible");
>  
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 223409)
> +++ tree-ssa-alias.c	(working copy)
> @@ -685,7 +685,12 @@ same_type_for_tbaa (tree type1, tree typ
>    /* If we would have to do structural comparison bail out.  */
>    if (TYPE_STRUCTURAL_EQUALITY_P (type1)
>        || TYPE_STRUCTURAL_EQUALITY_P (type2))
> -    return -1;
> +    {
> +      /* The way LTO produces canonical types makes sure that everything
> +         that matters has TYPE_CANONICAL set.  */
> +      gcc_assert (!in_lto_p);
> +      return -1;
> +    }
>  
>    /* Compare the canonical types.  */
>    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 223409)
> +++ lto/lto.c	(working copy)
> @@ -295,26 +295,42 @@ static hash_map<const_tree, hashval_t> *
>  static unsigned long num_canonical_type_hash_entries;
>  static unsigned long num_canonical_type_hash_queries;
>  
> -static void iterative_hash_canonical_type (tree type, inchash::hash &hstate);
> +static void iterative_hash_canonical_type (tree type, inchash::hash &hstate,
> +					   bool match_incomplete = false);
>  static hashval_t gimple_canonical_type_hash (const void *p);
>  static void gimple_register_canonical_type_1 (tree t, hashval_t hash);
>  
>  /* Returning a hash value for gimple type TYPE.
>  
>     The hash value returned is equal for types considered compatible
> -   by gimple_canonical_types_compatible_p.  */
> +   by gimple_canonical_types_compatible_p.  If MATCH_INCOMPLETE, then the
> +   hash is computed in a way that complete and incomplete types have the
> +   same value.  */
>  
>  static hashval_t
> -hash_canonical_type (tree type)
> +hash_canonical_type (tree type, bool match_incomplete = false)
>  {
>    inchash::hash hstate;
>  
> +  /* Check that types are complete when we disallow match between incomplete
> +     and complete types.  Exception are the arrays.  Incomplete arrays may
> +     appear as last field of structure and int that case we do want to
> +     only match incomplete array to incomplete array so it makes sense for
> +     MATCH_INCOMPLETE to be true.  */
> +  gcc_checking_assert (match_incomplete || COMPLETE_TYPE_P (type)
> +		       || TREE_CODE (type) == ARRAY_TYPE);
> +
>    /* Combine a few common features of types so that types are grouped into
>       smaller sets; when searching for existing matching types to merge,
>       only existing types having the same features as the new type will be
>       checked.  */
>    hstate.add_int (TREE_CODE (type));
> -  hstate.add_int (TYPE_MODE (type));
> +
> +  /* Incomplete arrays and aggregates do not have TYPE_MODE defined.  */
> +  if (!match_incomplete
> +      || (TREE_CODE (type) != ARRAY_TYPE
> +	  && !AGGREGATE_TYPE_P (type)))
> +    hstate.add_int (TYPE_MODE (type));
>  
>    /* Incorporate common features of numerical types.  */
>    if (INTEGRAL_TYPE_P (type)
> @@ -336,12 +352,12 @@ hash_canonical_type (tree type)
>    if (TREE_CODE (type) == COMPLEX_TYPE)
>      hstate.add_int (TYPE_UNSIGNED (type));
>  
> -  /* For pointer and reference types, fold in information about the type
> -     pointed to but do not recurse to the pointed-to type.  */
> +  /* The hash must produce same hash value for pointer to complete and
> +     incomplete type.  Recurse with MATCH_INCOMPLETE=true.  */
>    if (POINTER_TYPE_P (type))
>      {
>        hstate.add_int (TYPE_ADDR_SPACE (TREE_TYPE (type)));
> -      hstate.add_int (TREE_CODE (TREE_TYPE (type)));
> +      iterative_hash_canonical_type (TREE_TYPE (type), hstate, true);
>      }
>  
>    /* For integer types hash only the string flag.  */
> @@ -349,7 +365,8 @@ hash_canonical_type (tree type)
>      hstate.add_int (TYPE_STRING_FLAG (type));
>  
>    /* For array types hash the domain bounds and the string flag.  */
> -  if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type))
> +  if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type)
> +      && !match_incomplete)
>      {
>        hstate.add_int (TYPE_STRING_FLAG (type));
>        /* OMP lowering can introduce error_mark_node in place of
> @@ -360,34 +377,35 @@ hash_canonical_type (tree type)
>  	inchash::add_expr (TYPE_MAX_VALUE (TYPE_DOMAIN (type)), hstate);
>      }
>  
> -  /* Recurse for aggregates with a single element type.  */
> +  /* Recurse for aggregates with a single element type.
> +     We are safe to drop MATCH_INCOMPLETE.  There is no way to build
> +     an array of incomplete types.   */
>    if (TREE_CODE (type) == ARRAY_TYPE
>        || TREE_CODE (type) == COMPLEX_TYPE
>        || TREE_CODE (type) == VECTOR_TYPE)
> -    iterative_hash_canonical_type (TREE_TYPE (type), hstate);
> +    iterative_hash_canonical_type (TREE_TYPE (type), hstate, false);
>  
>    /* Incorporate function return and argument types.  */
>    if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
>      {
> -      unsigned na;
> -      tree p;
> -
> -      /* For method types also incorporate their parent class.  */
> -      if (TREE_CODE (type) == METHOD_TYPE)
> -	iterative_hash_canonical_type (TYPE_METHOD_BASETYPE (type), hstate);
> -
> -      iterative_hash_canonical_type (TREE_TYPE (type), hstate);
> +      iterative_hash_canonical_type (TREE_TYPE (type), hstate,
> +				     match_incomplete);
>  
> -      for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
> +      if (!match_incomplete || TREE_CODE (type) == METHOD_TYPE)
>  	{
> -	  iterative_hash_canonical_type (TREE_VALUE (p), hstate);
> -	  na++;
> +	  unsigned na;
> +	  tree p;
> +	  for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
> +	    {
> +	      iterative_hash_canonical_type (TREE_VALUE (p), hstate,
> +					     match_incomplete);
> +	      na++;
> +	    }
> +	  hstate.add_int (na);
>  	}
> -
> -      hstate.add_int (na);
>      }
>  
> -  if (RECORD_OR_UNION_TYPE_P (type))
> +  if (RECORD_OR_UNION_TYPE_P (type) && !match_incomplete)
>      {
>        unsigned nf;
>        tree f;
> @@ -395,7 +413,7 @@ hash_canonical_type (tree type)
>        for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
>  	if (TREE_CODE (f) == FIELD_DECL)
>  	  {
> -	    iterative_hash_canonical_type (TREE_TYPE (f), hstate);
> +	    iterative_hash_canonical_type (TREE_TYPE (f), hstate, false);
>  	    nf++;
>  	  }
>  
> @@ -408,11 +426,18 @@ hash_canonical_type (tree type)
>  /* Returning a hash value for gimple type TYPE combined with VAL.  */
>  
>  static void
> -iterative_hash_canonical_type (tree type, inchash::hash &hstate)
> +iterative_hash_canonical_type (tree type, inchash::hash &hstate,
> +			       bool match_incomplete)
>  {
>    hashval_t v;
> +
> +  /* TYPE_CANONICAL reflects equivalence classes with
> +     MATCH_INCOMPLETE = false.   If we are matching incomplete types,
> +     then we need to recurse.  */
> +  if (match_incomplete)
> +    v = hash_canonical_type (type, true);
>    /* An already processed type.  */
> -  if (TYPE_CANONICAL (type))
> +  else if (TYPE_CANONICAL (type))
>      {
>        type = TYPE_CANONICAL (type);
>        v = gimple_canonical_type_hash (type);
> @@ -423,7 +448,7 @@ iterative_hash_canonical_type (tree type
>  	 recursion is just because we do not register canonical types in
>  	 optimal order.  To avoid quadratic behavior also register the
>  	 type here.  */
> -      v = hash_canonical_type (type);
> +      v = hash_canonical_type (type, false);
>        gimple_register_canonical_type_1 (type, v);
>      }
>    hstate.add_int (v);
> @@ -495,6 +520,14 @@ gimple_register_canonical_type (tree t)
>  {
>    if (TYPE_CANONICAL (t))
>      return;
> +  /* Only types that can be stored/read need canonical types.
> +     Function and methods are never accessed. Also we do not need canonical
> +     types for incomplete types with exception of arrays - structures may end
> +     with incomplete arrays that may be referenced.  */
> +  if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE
> +      || (!COMPLETE_TYPE_P (t)
> +	  && (TREE_CODE (t) != ARRAY_TYPE || !COMPLETE_TYPE_P (TREE_TYPE (t)))))
> +    return;
>  
>    gimple_register_canonical_type_1 (t, hash_canonical_type (t));
>  }
> 
> 

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]