Cleanup and improve canonical type construction in LTO

[Jan Hubicka <hubicka at ucw dot cz>]

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.

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). 

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)
 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. 

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.

    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.

    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.
 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
    - 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.
    - 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.
  

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.  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.

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

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));
 }