Check canonical types in verify_type

Check canonical types in verify_type

[Jan Hubicka]

Hi,
this patch adds basic checking of TYPE_CANOINCAL. It checkes TYPE_CANONICAL
forms a tree and it moves lto's gimple_canonical_types_compatible_p back to
middle-end and uses it to check that TYPE_CANONICAL is compatible and thus none
of the FEs produce types sharing TYPE_CANONICAL that would be considered
different by LTO's TBAA.

I added trust_type_canonical argument and changed:

-  /* If the types have been previously registered and found equal
-     they still are.  */
-  if (TYPE_CANONICAL (t1)
-      && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
-    return true;

to:

+  /* 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);

(notice that I blocked the recursion when TYPE_CANONICAL is known to be
different).

The patch originally triggered an ICE in testsuite becuase C++ FE builds
FUNCTION_TYPE type variant with different attributes but same TYPE_CANONICAL.
I think C++ FE is correct and we may want to drop:

+      if (!comp_type_attributes (t1, t2))
+	return false;

Because I think the TBAA does not care about attribute lists.  I suppose this
is kind-of harmless because of:

+      /* 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)))
+	    return false;
+
+	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
+	    return false;
+	}

Is the reason for not making differences between differnt pointer types
really just lazyness to not deal with SCCs?  For that it is easy to add
set of visited type pairs, just like odr_types_equivalent_p does.

Because we now stream in SCC order anyway, most of time we won't even
need to populate it.  Shall I implement this?

Other issue I run into is that for Ada bootstrap we have variadic type whose
canonical types are having different temporary set as size.  I think this is
valid and perhaps gimple_canonical_types_compatible_p should consider
variadic arrays to be compatible with any array of compatible type?

I am not quite convinced we get variadic types right at LTO time, because
they bypass canonical type calculation anyway and their canonical type
is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
is not safe.  I will look for a testcase.

I also added check that TYPE_CANONICAL agrees for type variants.  I think it
should because few times in the middle-end uses TYPE_MAIN_VARIANT and seem to
expect this to happen:

static inline int                                                               
same_type_for_tbaa (tree type1, tree type2)                                     
{                                                                               
  type1 = TYPE_MAIN_VARIANT (type1);                                            
  type2 = TYPE_MAIN_VARIANT (type2);                                            
                                                                                
  /* If we would have to do structural comparison bail out.  */                 
  if (TYPE_STRUCTURAL_EQUALITY_P (type1)                                        
      || TYPE_STRUCTURAL_EQUALITY_P (type2))                                    
    return -1;                                                                  
                                                                                
  /* Compare the canonical types.  */                                           
  if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))                         
    return 1;                                                                   

and some places where we look for TYPE_MAIN_VARIANT to discard qualifiers.
This check triggers for Ada, but I will look into it separately.

Bootstrapped/regtested ppc64-linux, LTO bootstrap in progress. OK?

Honza

	* lto/lto.c (gimple_canonical_types_compatible_p): Move to tree.c
	* tree.c (verify_type_variant): Fix #undef.
	(gimple_canonical_types_compatible_p): Move here from lto.c
	(verify_type): Verify TYPE_CANONICAL compatibility.
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 223260)
+++ lto/lto.c	(working copy)
@@ -441,208 +441,6 @@ gimple_canonical_type_hash (const void *
 }
 
 
-/* The TYPE_CANONICAL merging machinery.  It should closely resemble
-   the middle-end types_compatible_p function.  It needs to avoid
-   claiming types are different for types that should be treated
-   the same with respect to TBAA.  Canonical types are also used
-   for IL consistency checks via the useless_type_conversion_p
-   predicate which does not handle all type kinds itself but falls
-   back to pointer-comparison of TYPE_CANONICAL for aggregates
-   for example.  */
-
-/* Return true iff T1 and T2 are structurally identical for what
-   TBAA is concerned.  */
-
-static bool
-gimple_canonical_types_compatible_p (tree t1, tree t2)
-{
-  /* Before starting to set up the SCC machinery handle simple cases.  */
-
-  /* Check first for the obvious case of pointer identity.  */
-  if (t1 == t2)
-    return true;
-
-  /* Check that we have two types to compare.  */
-  if (t1 == NULL_TREE || t2 == NULL_TREE)
-    return false;
-
-  /* If the types have been previously registered and found equal
-     they still are.  */
-  if (TYPE_CANONICAL (t1)
-      && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
-    return true;
-
-  /* Can't be the same type if the types don't have the same code.  */
-  if (TREE_CODE (t1) != TREE_CODE (t2))
-    return false;
-
-  /* Qualifiers do not matter for canonical type comparison purposes.  */
-
-  /* Void types and nullptr types are always the same.  */
-  if (TREE_CODE (t1) == VOID_TYPE
-      || 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))
-    return false;
-
-  /* Non-aggregate types can be handled cheaply.  */
-  if (INTEGRAL_TYPE_P (t1)
-      || SCALAR_FLOAT_TYPE_P (t1)
-      || FIXED_POINT_TYPE_P (t1)
-      || TREE_CODE (t1) == VECTOR_TYPE
-      || TREE_CODE (t1) == COMPLEX_TYPE
-      || TREE_CODE (t1) == OFFSET_TYPE
-      || POINTER_TYPE_P (t1))
-    {
-      /* Can't be the same type if they have different sign or precision.  */
-      if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
-	  || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
-	return false;
-
-      if (TREE_CODE (t1) == INTEGER_TYPE
-	  && 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)))
-	    return false;
-
-	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
-	    return false;
-	}
-
-      /* Tail-recurse to components.  */
-      if (TREE_CODE (t1) == VECTOR_TYPE
-	  || TREE_CODE (t1) == COMPLEX_TYPE)
-	return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
-						    TREE_TYPE (t2));
-
-      return true;
-    }
-
-  /* Do type-specific comparisons.  */
-  switch (TREE_CODE (t1))
-    {
-    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))
-	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
-	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
-	return false;
-      else
-	{
-	  tree i1 = TYPE_DOMAIN (t1);
-	  tree i2 = TYPE_DOMAIN (t2);
-
-	  /* For an incomplete external array, the type domain can be
- 	     NULL_TREE.  Check this condition also.  */
-	  if (i1 == NULL_TREE && i2 == NULL_TREE)
-	    return true;
-	  else if (i1 == NULL_TREE || i2 == NULL_TREE)
-	    return false;
-	  else
-	    {
-	      tree min1 = TYPE_MIN_VALUE (i1);
-	      tree min2 = TYPE_MIN_VALUE (i2);
-	      tree max1 = TYPE_MAX_VALUE (i1);
-	      tree max2 = TYPE_MAX_VALUE (i2);
-
-	      /* The minimum/maximum values have to be the same.  */
-	      if ((min1 == min2
-		   || (min1 && min2
-		       && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
-			    && TREE_CODE (min2) == PLACEHOLDER_EXPR)
-		           || operand_equal_p (min1, min2, 0))))
-		  && (max1 == max2
-		      || (max1 && max2
-			  && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
-			       && TREE_CODE (max2) == PLACEHOLDER_EXPR)
-			      || operand_equal_p (max1, max2, 0)))))
-		return true;
-	      else
-		return false;
-	    }
-	}
-
-    case METHOD_TYPE:
-    case FUNCTION_TYPE:
-      /* Function types are the same if the return type and arguments types
-	 are the same.  */
-      if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
-	return false;
-
-      if (!comp_type_attributes (t1, t2))
-	return false;
-
-      if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
-	return true;
-      else
-	{
-	  tree parms1, parms2;
-
-	  for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
-	       parms1 && parms2;
-	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
-	    {
-	      if (!gimple_canonical_types_compatible_p
-		     (TREE_VALUE (parms1), TREE_VALUE (parms2)))
-		return false;
-	    }
-
-	  if (parms1 || parms2)
-	    return false;
-
-	  return true;
-	}
-
-    case RECORD_TYPE:
-    case UNION_TYPE:
-    case QUAL_UNION_TYPE:
-      {
-	tree f1, f2;
-
-	/* For aggregate types, all the fields must be the same.  */
-	for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
-	     f1 || f2;
-	     f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
-	  {
-	    /* Skip non-fields.  */
-	    while (f1 && TREE_CODE (f1) != FIELD_DECL)
-	      f1 = TREE_CHAIN (f1);
-	    while (f2 && TREE_CODE (f2) != FIELD_DECL)
-	      f2 = TREE_CHAIN (f2);
-	    if (!f1 || !f2)
-	      break;
-	    /* The fields must have the same name, offset and type.  */
-	    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)))
-	      return false;
-	  }
-
-	/* If one aggregate has more fields than the other, they
-	   are not the same.  */
-	if (f1 || f2)
-	  return false;
-
-	return true;
-      }
-
-    default:
-      gcc_unreachable ();
-    }
-}
-
 
 /* Returns nonzero if P1 and P2 are equal.  */
 
Index: tree.c
===================================================================
--- tree.c	(revision 223260)
+++ tree.c	(working copy)
@@ -12687,10 +12687,222 @@ verify_type_variant (const_tree t, tree
       return false;
     }
   return true;
-#undef verify_type_variant
+#undef verify_variant_match
 }
 
 
+/* The TYPE_CANONICAL merging machinery.  It should closely resemble
+   the middle-end types_compatible_p function.  It needs to avoid
+   claiming types are different for types that should be treated
+   the same with respect to TBAA.  Canonical types are also used
+   for IL consistency checks via the useless_type_conversion_p
+   predicate which does not handle all type kinds itself but falls
+   back to pointer-comparison of TYPE_CANONICAL for aggregates
+   for example.  */
+
+/* Return true iff T1 and T2 are structurally identical for what
+   TBAA is concerned.  */
+
+bool
+gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
+				     bool trust_type_canonical)
+{
+  /* Before starting to set up the SCC machinery handle simple cases.  */
+
+  /* Check first for the obvious case of pointer identity.  */
+  if (t1 == t2)
+    return true;
+
+  /* Check that we have two types to compare.  */
+  if (t1 == NULL_TREE || t2 == NULL_TREE)
+    return false;
+
+  /* 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);
+
+  /* Can't be the same type if the types don't have the same code.  */
+  if (TREE_CODE (t1) != TREE_CODE (t2))
+    return false;
+
+  /* Qualifiers do not matter for canonical type comparison purposes.  */
+
+  /* Void types and nullptr types are always the same.  */
+  if (TREE_CODE (t1) == VOID_TYPE
+      || 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))
+    return false;
+
+  /* Non-aggregate types can be handled cheaply.  */
+  if (INTEGRAL_TYPE_P (t1)
+      || SCALAR_FLOAT_TYPE_P (t1)
+      || FIXED_POINT_TYPE_P (t1)
+      || TREE_CODE (t1) == VECTOR_TYPE
+      || TREE_CODE (t1) == COMPLEX_TYPE
+      || TREE_CODE (t1) == OFFSET_TYPE
+      || POINTER_TYPE_P (t1))
+    {
+      /* Can't be the same type if they have different sign or precision.  */
+      if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
+	  || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
+	return false;
+
+      if (TREE_CODE (t1) == INTEGER_TYPE
+	  && 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)))
+	    return false;
+
+	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
+	    return false;
+	}
+
+      /* Tail-recurse to components.  */
+      if (TREE_CODE (t1) == VECTOR_TYPE
+	  || TREE_CODE (t1) == COMPLEX_TYPE)
+	return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
+						    TREE_TYPE (t2),
+						    trust_type_canonical);
+
+      return true;
+    }
+
+  /* Do type-specific comparisons.  */
+  switch (TREE_CODE (t1))
+    {
+    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)
+	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
+	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
+	return false;
+      else
+	{
+	  tree i1 = TYPE_DOMAIN (t1);
+	  tree i2 = TYPE_DOMAIN (t2);
+
+	  /* For an incomplete external array, the type domain can be
+ 	     NULL_TREE.  Check this condition also.  */
+	  if (i1 == NULL_TREE && i2 == NULL_TREE)
+	    return true;
+	  else if (i1 == NULL_TREE || i2 == NULL_TREE)
+	    return false;
+	  else
+	    {
+	      tree min1 = TYPE_MIN_VALUE (i1);
+	      tree min2 = TYPE_MIN_VALUE (i2);
+	      tree max1 = TYPE_MAX_VALUE (i1);
+	      tree max2 = TYPE_MAX_VALUE (i2);
+
+	      /* The minimum/maximum values have to be the same.  */
+	      if ((min1 == min2
+		   || (min1 && min2
+		       && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
+			    && TREE_CODE (min2) == PLACEHOLDER_EXPR)
+		           || operand_equal_p (min1, min2, 0))))
+		  && (max1 == max2
+		      || (max1 && max2
+			  && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
+			       && TREE_CODE (max2) == PLACEHOLDER_EXPR)
+			      || operand_equal_p (max1, max2, 0)))))
+		return true;
+	      else
+		return false;
+	    }
+	}
+
+    case METHOD_TYPE:
+    case FUNCTION_TYPE:
+      /* Function types are the same if the return type and arguments types
+	 are the same.  */
+      if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
+						trust_type_canonical))
+	return false;
+
+      if (!comp_type_attributes (t1, t2))
+	return false;
+
+      if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
+	return true;
+      else
+	{
+	  tree parms1, parms2;
+
+	  for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
+	       parms1 && parms2;
+	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
+	    {
+	      if (!gimple_canonical_types_compatible_p
+		     (TREE_VALUE (parms1), TREE_VALUE (parms2),
+		      trust_type_canonical))
+		return false;
+	    }
+
+	  if (parms1 || parms2)
+	    return false;
+
+	  return true;
+	}
+
+    case RECORD_TYPE:
+    case UNION_TYPE:
+    case QUAL_UNION_TYPE:
+      {
+	tree f1, f2;
+
+	/* For aggregate types, all the fields must be the same.  */
+	for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
+	     f1 || f2;
+	     f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
+	  {
+	    /* Skip non-fields.  */
+	    while (f1 && TREE_CODE (f1) != FIELD_DECL)
+	      f1 = TREE_CHAIN (f1);
+	    while (f2 && TREE_CODE (f2) != FIELD_DECL)
+	      f2 = TREE_CHAIN (f2);
+	    if (!f1 || !f2)
+	      break;
+	    /* The fields must have the same name, offset and type.  */
+	    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))
+	      return false;
+	  }
+
+	/* If one aggregate has more fields than the other, they
+	   are not the same.  */
+	if (f1 || f2)
+	  return false;
+
+	return true;
+      }
+
+    default:
+      /* Consider all types with language specific trees in them mutually
+	 compatible.  This is executed only from verify_type and false
+         positives can be tolerated.  */
+      gcc_assert (!in_lto_p);
+      return true;
+    }
+}
+
 /* Verify type T.  */
 
 void
@@ -12712,6 +12924,35 @@ verify_type (const_tree t)
   else if (t != mv && !verify_type_variant (t, mv))
     error_found = true;
 
+  tree ct = TYPE_CANONICAL (t);
+  if (!ct)
+    ;
+  else if (TYPE_CANONICAL (t) != ct)
+    {
+      error ("TYPE_CANONICAL has different TYPE_CANONICAL");
+      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)
+    ;
+  else if (t != ct && !gimple_canonical_types_compatible_p (t, ct, false)
+	   /* 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))
+    {
+      error ("TYPE_CANONICAL is not compatible");
+      debug_tree (ct);
+      error_found = true;
+    }
+
+
   /* Check various uses of TYPE_MINVAL.  */
   if (RECORD_OR_UNION_TYPE_P (t))
     {
Index: tree.h
===================================================================
--- tree.h	(revision 223260)
+++ tree.h	(working copy)
@@ -4564,6 +4564,8 @@ 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);
 
 #define tree_map_eq tree_map_base_eq
 extern unsigned int tree_map_hash (const void *);

Re: Check canonical types in verify_type

[Richard Biener]

On Mon, 18 May 2015, Jan Hubicka wrote:

> Hi,
> this patch adds basic checking of TYPE_CANOINCAL. It checkes TYPE_CANONICAL
> forms a tree and it moves lto's gimple_canonical_types_compatible_p back to
> middle-end and uses it to check that TYPE_CANONICAL is compatible and thus none
> of the FEs produce types sharing TYPE_CANONICAL that would be considered
> different by LTO's TBAA.
> 
> I added trust_type_canonical argument and changed:
> 
> -  /* If the types have been previously registered and found equal
> -     they still are.  */
> -  if (TYPE_CANONICAL (t1)
> -      && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
> -    return true;
> 
> to:
> 
> +  /* 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);
> 
> (notice that I blocked the recursion when TYPE_CANONICAL is known to be
> different).
> 
> The patch originally triggered an ICE in testsuite becuase C++ FE builds
> FUNCTION_TYPE type variant with different attributes but same TYPE_CANONICAL.
> I think C++ FE is correct and we may want to drop:
> 
> +      if (!comp_type_attributes (t1, t2))
> +	return false;
> 
> Because I think the TBAA does not care about attribute lists.  I suppose this
> is kind-of harmless because of:

I think that was about attributes like 'packed', but those should have
their effects applied at stor-layout time.  So yes, I think this can be
dropped.

> +      /* 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)))
> +	    return false;
> +
> +	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> +	    return false;
> +	}
> 
> Is the reason for not making differences between differnt pointer types
> really just lazyness to not deal with SCCs?  For that it is easy to add
> set of visited type pairs, just like odr_types_equivalent_p does.

Well - TBAA doesn't care about pointed-to types.  See get_alias_set

  else if (POINTER_TYPE_P (t)
           && t != ptr_type_node)
    set = get_alias_set (ptr_type_node);

so the above would at most matter for pointer-type fields of aggregates.
And no, we don't want to deal with SCCs - I doubt it would bring any 
benefit and the issue here is that I am worried about SCCs being present
dependent on the order of streaming (well, the code pre-dates SCC
streaming).

> Because we now stream in SCC order anyway, most of time we won't even
> need to populate it.  Shall I implement this?

You can certainly try - but I think for cross-language interoperability
we want to treat

  struct X { void *p; }
  struct Y { void *p; }

and

  struct X { Y *p; }
  struct Y { X *q; } 

as compatible so I don't think we can use SCCs to partition alias sets
further (that is, we _do_ have to treat pointers conservatively).  The
current code is as far as we can get IMHO (well, even the current code
is too strict in making struct { void *p } and struct { int *p } not
have the same alias-set.

> Other issue I run into is that for Ada bootstrap we have variadic type whose
> canonical types are having different temporary set as size.  I think this is
> valid and perhaps gimple_canonical_types_compatible_p should consider
> variadic arrays to be compatible with any array of compatible type?

Those are all local types and thus the strict equality compare should be
ok?  Not sure if we can do in C sth like

void foo (int n)
{
  struct { int i; int a[n]; } a;
  struct { int i; int a[n]; } b;
}

and if we'd have to assign the same alias-sets to 'a' and 'b'.

> I am not quite convinced we get variadic types right at LTO time, because
> they bypass canonical type calculation anyway and their canonical type
> is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
> is not safe.  I will look for a testcase.

That is because if they are streamed locally they do not enter type
merging, but they still go via gimple_register_canonical_type, so I'm not
sure where you see they always get their main variant as canonical type.

> I also added check that TYPE_CANONICAL agrees for type variants.  I think it
> should because few times in the middle-end uses TYPE_MAIN_VARIANT and seem to
> expect this to happen:

Yes.  Otherwise we'd run in circles for code that does

 type = TYPE_CANONICAL (TYPE_MAIN_VARIANT (type));

because the result might not be a main variant.  That's something to
verify (both TYPE_CANONICAL and TYPE_MAIN_VARIANT should form a tree). 

> static inline int                                                               
> same_type_for_tbaa (tree type1, tree type2)                                     
> {                                                                               
>   type1 = TYPE_MAIN_VARIANT (type1);                                            
>   type2 = TYPE_MAIN_VARIANT (type2);                                            
>                                                                                 
>   /* If we would have to do structural comparison bail out.  */                 
>   if (TYPE_STRUCTURAL_EQUALITY_P (type1)                                        
>       || TYPE_STRUCTURAL_EQUALITY_P (type2))                                    
>     return -1;                                                                  
>                                                                                 
>   /* Compare the canonical types.  */                                           
>   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))                         
>     return 1;                                                                   
> 
> and some places where we look for TYPE_MAIN_VARIANT to discard qualifiers.
> This check triggers for Ada, but I will look into it separately.
> 
> Bootstrapped/regtested ppc64-linux, LTO bootstrap in progress. OK?
> 
> Honza
> 
> 	* lto/lto.c (gimple_canonical_types_compatible_p): Move to tree.c
> 	* tree.c (verify_type_variant): Fix #undef.
> 	(gimple_canonical_types_compatible_p): Move here from lto.c
> 	(verify_type): Verify TYPE_CANONICAL compatibility.

tree.h change is missing.

> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 223260)
> +++ lto/lto.c	(working copy)
> @@ -441,208 +441,6 @@ gimple_canonical_type_hash (const void *
>  }
>  
>  
> -/* The TYPE_CANONICAL merging machinery.  It should closely resemble
> -   the middle-end types_compatible_p function.  It needs to avoid
> -   claiming types are different for types that should be treated
> -   the same with respect to TBAA.  Canonical types are also used
> -   for IL consistency checks via the useless_type_conversion_p
> -   predicate which does not handle all type kinds itself but falls
> -   back to pointer-comparison of TYPE_CANONICAL for aggregates
> -   for example.  */
> -
> -/* Return true iff T1 and T2 are structurally identical for what
> -   TBAA is concerned.  */
> -
> -static bool
> -gimple_canonical_types_compatible_p (tree t1, tree t2)
> -{
> -  /* Before starting to set up the SCC machinery handle simple cases.  */
> -
> -  /* Check first for the obvious case of pointer identity.  */
> -  if (t1 == t2)
> -    return true;
> -
> -  /* Check that we have two types to compare.  */
> -  if (t1 == NULL_TREE || t2 == NULL_TREE)
> -    return false;
> -
> -  /* If the types have been previously registered and found equal
> -     they still are.  */
> -  if (TYPE_CANONICAL (t1)
> -      && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
> -    return true;
> -
> -  /* Can't be the same type if the types don't have the same code.  */
> -  if (TREE_CODE (t1) != TREE_CODE (t2))
> -    return false;
> -
> -  /* Qualifiers do not matter for canonical type comparison purposes.  */
> -
> -  /* Void types and nullptr types are always the same.  */
> -  if (TREE_CODE (t1) == VOID_TYPE
> -      || 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))
> -    return false;
> -
> -  /* Non-aggregate types can be handled cheaply.  */
> -  if (INTEGRAL_TYPE_P (t1)
> -      || SCALAR_FLOAT_TYPE_P (t1)
> -      || FIXED_POINT_TYPE_P (t1)
> -      || TREE_CODE (t1) == VECTOR_TYPE
> -      || TREE_CODE (t1) == COMPLEX_TYPE
> -      || TREE_CODE (t1) == OFFSET_TYPE
> -      || POINTER_TYPE_P (t1))
> -    {
> -      /* Can't be the same type if they have different sign or precision.  */
> -      if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
> -	  || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
> -	return false;
> -
> -      if (TREE_CODE (t1) == INTEGER_TYPE
> -	  && 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)))
> -	    return false;
> -
> -	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> -	    return false;
> -	}
> -
> -      /* Tail-recurse to components.  */
> -      if (TREE_CODE (t1) == VECTOR_TYPE
> -	  || TREE_CODE (t1) == COMPLEX_TYPE)
> -	return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
> -						    TREE_TYPE (t2));
> -
> -      return true;
> -    }
> -
> -  /* Do type-specific comparisons.  */
> -  switch (TREE_CODE (t1))
> -    {
> -    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))
> -	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
> -	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
> -	return false;
> -      else
> -	{
> -	  tree i1 = TYPE_DOMAIN (t1);
> -	  tree i2 = TYPE_DOMAIN (t2);
> -
> -	  /* For an incomplete external array, the type domain can be
> - 	     NULL_TREE.  Check this condition also.  */
> -	  if (i1 == NULL_TREE && i2 == NULL_TREE)
> -	    return true;
> -	  else if (i1 == NULL_TREE || i2 == NULL_TREE)
> -	    return false;
> -	  else
> -	    {
> -	      tree min1 = TYPE_MIN_VALUE (i1);
> -	      tree min2 = TYPE_MIN_VALUE (i2);
> -	      tree max1 = TYPE_MAX_VALUE (i1);
> -	      tree max2 = TYPE_MAX_VALUE (i2);
> -
> -	      /* The minimum/maximum values have to be the same.  */
> -	      if ((min1 == min2
> -		   || (min1 && min2
> -		       && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
> -			    && TREE_CODE (min2) == PLACEHOLDER_EXPR)
> -		           || operand_equal_p (min1, min2, 0))))
> -		  && (max1 == max2
> -		      || (max1 && max2
> -			  && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
> -			       && TREE_CODE (max2) == PLACEHOLDER_EXPR)
> -			      || operand_equal_p (max1, max2, 0)))))
> -		return true;
> -	      else
> -		return false;
> -	    }
> -	}
> -
> -    case METHOD_TYPE:
> -    case FUNCTION_TYPE:
> -      /* Function types are the same if the return type and arguments types
> -	 are the same.  */
> -      if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
> -	return false;
> -
> -      if (!comp_type_attributes (t1, t2))
> -	return false;
> -
> -      if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
> -	return true;
> -      else
> -	{
> -	  tree parms1, parms2;
> -
> -	  for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
> -	       parms1 && parms2;
> -	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
> -	    {
> -	      if (!gimple_canonical_types_compatible_p
> -		     (TREE_VALUE (parms1), TREE_VALUE (parms2)))
> -		return false;
> -	    }
> -
> -	  if (parms1 || parms2)
> -	    return false;
> -
> -	  return true;
> -	}
> -
> -    case RECORD_TYPE:
> -    case UNION_TYPE:
> -    case QUAL_UNION_TYPE:
> -      {
> -	tree f1, f2;
> -
> -	/* For aggregate types, all the fields must be the same.  */
> -	for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
> -	     f1 || f2;
> -	     f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
> -	  {
> -	    /* Skip non-fields.  */
> -	    while (f1 && TREE_CODE (f1) != FIELD_DECL)
> -	      f1 = TREE_CHAIN (f1);
> -	    while (f2 && TREE_CODE (f2) != FIELD_DECL)
> -	      f2 = TREE_CHAIN (f2);
> -	    if (!f1 || !f2)
> -	      break;
> -	    /* The fields must have the same name, offset and type.  */
> -	    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)))
> -	      return false;
> -	  }
> -
> -	/* If one aggregate has more fields than the other, they
> -	   are not the same.  */
> -	if (f1 || f2)
> -	  return false;
> -
> -	return true;
> -      }
> -
> -    default:
> -      gcc_unreachable ();
> -    }
> -}
> -
>  
>  /* Returns nonzero if P1 and P2 are equal.  */
>  
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 223260)
> +++ tree.c	(working copy)
> @@ -12687,10 +12687,222 @@ verify_type_variant (const_tree t, tree
>        return false;
>      }
>    return true;
> -#undef verify_type_variant
> +#undef verify_variant_match
>  }
>  
>  
> +/* The TYPE_CANONICAL merging machinery.  It should closely resemble
> +   the middle-end types_compatible_p function.  It needs to avoid
> +   claiming types are different for types that should be treated
> +   the same with respect to TBAA.  Canonical types are also used
> +   for IL consistency checks via the useless_type_conversion_p
> +   predicate which does not handle all type kinds itself but falls
> +   back to pointer-comparison of TYPE_CANONICAL for aggregates
> +   for example.  */
> +
> +/* Return true iff T1 and T2 are structurally identical for what
> +   TBAA is concerned.  */
> +
> +bool
> +gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
> +				     bool trust_type_canonical)
> +{
> +  /* Before starting to set up the SCC machinery handle simple cases.  */
> +
> +  /* Check first for the obvious case of pointer identity.  */
> +  if (t1 == t2)
> +    return true;
> +
> +  /* Check that we have two types to compare.  */
> +  if (t1 == NULL_TREE || t2 == NULL_TREE)
> +    return false;
> +
> +  /* 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);
> +
> +  /* Can't be the same type if the types don't have the same code.  */
> +  if (TREE_CODE (t1) != TREE_CODE (t2))
> +    return false;
> +
> +  /* Qualifiers do not matter for canonical type comparison purposes.  */
> +
> +  /* Void types and nullptr types are always the same.  */
> +  if (TREE_CODE (t1) == VOID_TYPE
> +      || 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))
> +    return false;
> +
> +  /* Non-aggregate types can be handled cheaply.  */
> +  if (INTEGRAL_TYPE_P (t1)
> +      || SCALAR_FLOAT_TYPE_P (t1)
> +      || FIXED_POINT_TYPE_P (t1)
> +      || TREE_CODE (t1) == VECTOR_TYPE
> +      || TREE_CODE (t1) == COMPLEX_TYPE
> +      || TREE_CODE (t1) == OFFSET_TYPE
> +      || POINTER_TYPE_P (t1))
> +    {
> +      /* Can't be the same type if they have different sign or precision.  */
> +      if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
> +	  || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
> +	return false;
> +
> +      if (TREE_CODE (t1) == INTEGER_TYPE
> +	  && 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)))
> +	    return false;
> +
> +	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> +	    return false;
> +	}
> +
> +      /* Tail-recurse to components.  */
> +      if (TREE_CODE (t1) == VECTOR_TYPE
> +	  || TREE_CODE (t1) == COMPLEX_TYPE)
> +	return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
> +						    TREE_TYPE (t2),
> +						    trust_type_canonical);
> +
> +      return true;
> +    }
> +
> +  /* Do type-specific comparisons.  */
> +  switch (TREE_CODE (t1))
> +    {
> +    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)
> +	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
> +	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
> +	return false;
> +      else
> +	{
> +	  tree i1 = TYPE_DOMAIN (t1);
> +	  tree i2 = TYPE_DOMAIN (t2);
> +
> +	  /* For an incomplete external array, the type domain can be
> + 	     NULL_TREE.  Check this condition also.  */
> +	  if (i1 == NULL_TREE && i2 == NULL_TREE)
> +	    return true;
> +	  else if (i1 == NULL_TREE || i2 == NULL_TREE)
> +	    return false;
> +	  else
> +	    {
> +	      tree min1 = TYPE_MIN_VALUE (i1);
> +	      tree min2 = TYPE_MIN_VALUE (i2);
> +	      tree max1 = TYPE_MAX_VALUE (i1);
> +	      tree max2 = TYPE_MAX_VALUE (i2);
> +
> +	      /* The minimum/maximum values have to be the same.  */
> +	      if ((min1 == min2
> +		   || (min1 && min2
> +		       && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
> +			    && TREE_CODE (min2) == PLACEHOLDER_EXPR)
> +		           || operand_equal_p (min1, min2, 0))))
> +		  && (max1 == max2
> +		      || (max1 && max2
> +			  && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
> +			       && TREE_CODE (max2) == PLACEHOLDER_EXPR)
> +			      || operand_equal_p (max1, max2, 0)))))
> +		return true;
> +	      else
> +		return false;
> +	    }
> +	}
> +
> +    case METHOD_TYPE:
> +    case FUNCTION_TYPE:
> +      /* Function types are the same if the return type and arguments types
> +	 are the same.  */
> +      if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
> +						trust_type_canonical))
> +	return false;
> +
> +      if (!comp_type_attributes (t1, t2))
> +	return false;
> +
> +      if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
> +	return true;
> +      else
> +	{
> +	  tree parms1, parms2;
> +
> +	  for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
> +	       parms1 && parms2;
> +	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
> +	    {
> +	      if (!gimple_canonical_types_compatible_p
> +		     (TREE_VALUE (parms1), TREE_VALUE (parms2),
> +		      trust_type_canonical))
> +		return false;
> +	    }
> +
> +	  if (parms1 || parms2)
> +	    return false;
> +
> +	  return true;
> +	}
> +
> +    case RECORD_TYPE:
> +    case UNION_TYPE:
> +    case QUAL_UNION_TYPE:
> +      {
> +	tree f1, f2;
> +
> +	/* For aggregate types, all the fields must be the same.  */
> +	for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
> +	     f1 || f2;
> +	     f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
> +	  {
> +	    /* Skip non-fields.  */
> +	    while (f1 && TREE_CODE (f1) != FIELD_DECL)
> +	      f1 = TREE_CHAIN (f1);
> +	    while (f2 && TREE_CODE (f2) != FIELD_DECL)
> +	      f2 = TREE_CHAIN (f2);
> +	    if (!f1 || !f2)
> +	      break;
> +	    /* The fields must have the same name, offset and type.  */
> +	    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))
> +	      return false;
> +	  }
> +
> +	/* If one aggregate has more fields than the other, they
> +	   are not the same.  */
> +	if (f1 || f2)
> +	  return false;
> +
> +	return true;
> +      }
> +
> +    default:
> +      /* Consider all types with language specific trees in them mutually
> +	 compatible.  This is executed only from verify_type and false
> +         positives can be tolerated.  */
> +      gcc_assert (!in_lto_p);
> +      return true;
> +    }
> +}
> +
>  /* Verify type T.  */
>  
>  void
> @@ -12712,6 +12924,35 @@ verify_type (const_tree t)
>    else if (t != mv && !verify_type_variant (t, mv))
>      error_found = true;
>  
> +  tree ct = TYPE_CANONICAL (t);
> +  if (!ct)
> +    ;
> +  else if (TYPE_CANONICAL (t) != ct)
> +    {
> +      error ("TYPE_CANONICAL has different TYPE_CANONICAL");
> +      debug_tree (ct);
> +      error_found = true;
> +    }

So here you'd verify that

    TYPE_MAIN_VARIANT (ct) == ct
    && TYPE_CANONICAL (TYPE_MAIN_VARIANT (t)) == ct

> +  /* 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)
> +    ;
> +  else if (t != ct && !gimple_canonical_types_compatible_p (t, ct, false)
> +	   /* 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))

So with LTO this check should never trigger.  I'd probably check
!variably_modified_type_p (ct, NULL) first.

Ok with that changes.

Thanks,
Richard.

> +    {
> +      error ("TYPE_CANONICAL is not compatible");
> +      debug_tree (ct);
> +      error_found = true;
> +    }
> +
> +
>    /* Check various uses of TYPE_MINVAL.  */
>    if (RECORD_OR_UNION_TYPE_P (t))
>      {
> Index: tree.h
> ===================================================================
> --- tree.h	(revision 223260)
> +++ tree.h	(working copy)
> @@ -4564,6 +4564,8 @@ 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);
>  
>  #define tree_map_eq tree_map_base_eq
>  extern unsigned int tree_map_hash (const void *);
> 
> 

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

Re: Check canonical types in verify_type

[Jan Hubicka]

> > +      if (!comp_type_attributes (t1, t2))
> > +	return false;
> > 
> > Because I think the TBAA does not care about attribute lists.  I suppose this
> > is kind-of harmless because of:
> 
> I think that was about attributes like 'packed', but those should have
> their effects applied at stor-layout time.  So yes, I think this can be
> dropped.

It does test the attribute list for functions only.  I think packed should
be detected from memory layout, so I will test patch dropping this.
> 
> > +      /* 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)))
> > +	    return false;
> > +
> > +	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> > +	    return false;
> > +	}
> > 
> > Is the reason for not making differences between differnt pointer types
> > really just lazyness to not deal with SCCs?  For that it is easy to add
> > set of visited type pairs, just like odr_types_equivalent_p does.
> 
> Well - TBAA doesn't care about pointed-to types.  See get_alias_set
> 
>   else if (POINTER_TYPE_P (t)
>            && t != ptr_type_node)
>     set = get_alias_set (ptr_type_node);

Hmm, I see, interesting hack.  For the first part of comment, I see that
qualifiers needs to be ignored, but I do not see why we put
short * and int * pointers to same class.

The complete/incomplete type fun with LTO can be solved for C++ but indeed I
see why pointer to incomplete type needs to be considered compatible with every
other pointer to structure.  Can't this be dealt with by adding correct edges
into the aliasing dag?
> 
> so the above would at most matter for pointer-type fields of aggregates.
> And no, we don't want to deal with SCCs - I doubt it would bring any 
> benefit and the issue here is that I am worried about SCCs being present
> dependent on the order of streaming (well, the code pre-dates SCC
> streaming).
> 
> > Because we now stream in SCC order anyway, most of time we won't even
> > need to populate it.  Shall I implement this?
> 
> You can certainly try - but I think for cross-language interoperability
> we want to treat
> 
>   struct X { void *p; }
>   struct Y { void *p; }
> 
> and
> 
>   struct X { Y *p; }
>   struct Y { X *q; } 
> 
> as compatible so I don't think we can use SCCs to partition alias sets
> further (that is, we _do_ have to treat pointers conservatively).  The
> current code is as far as we can get IMHO (well, even the current code
> is too strict in making struct { void *p } and struct { int *p } not
> have the same alias-set.

I will give it a try.  Do you have some examples where the above matters
for cross-language TBAA?
> 
> > Other issue I run into is that for Ada bootstrap we have variadic type whose
> > canonical types are having different temporary set as size.  I think this is
> > valid and perhaps gimple_canonical_types_compatible_p should consider
> > variadic arrays to be compatible with any array of compatible type?
> 
> Those are all local types and thus the strict equality compare should be
> ok?  Not sure if we can do in C sth like
> 
> void foo (int n)
> {
>   struct { int i; int a[n]; } a;
>   struct { int i; int a[n]; } b;
> }
> 
> and if we'd have to assign the same alias-sets to 'a' and 'b'.

No idea here either. I wonder if the types are intedned to be TBAA compatible
across two calls of the function.  In that case we may introduce multiple copies
of body by early inlining already that may be a problem.
> 
> > I am not quite convinced we get variadic types right at LTO time, because
> > they bypass canonical type calculation anyway and their canonical type
> > is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
> > is not safe.  I will look for a testcase.
> 
> That is because if they are streamed locally they do not enter type
> merging, but they still go via gimple_register_canonical_type, so I'm not
> sure where you see they always get their main variant as canonical type.

I tought these are handled by:
      /* And fixup types we streamed locally.  */
        {
          struct streamer_tree_cache_d *cache = data_in->reader_cache;
          unsigned len = cache->nodes.length ();
          unsigned i;
          for (i = len; i-- > from;)
            {
              tree t = streamer_tree_cache_get_tree (cache, i);
              if (t == NULL_TREE)
                continue;

              if (TYPE_P (t))
                {
                  gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
                  TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
                  if (TYPE_MAIN_VARIANT (t) != t)
                    {
                      gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
                      TYPE_NEXT_VARIANT (t)
                        = TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t));
                      TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t)) = t;
                    }
                }
            }
        }

which does not do registering.
> 
> > I also added check that TYPE_CANONICAL agrees for type variants.  I think it
> > should because few times in the middle-end uses TYPE_MAIN_VARIANT and seem to
> > expect this to happen:
> 
> Yes.  Otherwise we'd run in circles for code that does
> 
>  type = TYPE_CANONICAL (TYPE_MAIN_VARIANT (type));
> 
> because the result might not be a main variant.  That's something to
> verify (both TYPE_CANONICAL and TYPE_MAIN_VARIANT should form a tree). 
> 
> So here you'd verify that
> 
>     TYPE_MAIN_VARIANT (ct) == ct
>     && TYPE_CANONICAL (TYPE_MAIN_VARIANT (t)) == ct

OK will do that incrementally and debug the issues. 
I believe I tried the second test and it failed with Ada.
> 
> > +  /* 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)
> > +    ;
> > +  else if (t != ct && !gimple_canonical_types_compatible_p (t, ct, false)
> > +	   /* 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))
> 
> So with LTO this check should never trigger.  I'd probably check
> !variably_modified_type_p (ct, NULL) first.

It does - we eventually stream in the bodies and the variably modified types
and call verifier on that.

Thanks!
Honza

Re: Check canonical types in verify_type

[Richard Biener]

On Mon, 18 May 2015, Jan Hubicka wrote:

> > > +      if (!comp_type_attributes (t1, t2))
> > > +	return false;
> > > 
> > > Because I think the TBAA does not care about attribute lists.  I suppose this
> > > is kind-of harmless because of:
> > 
> > I think that was about attributes like 'packed', but those should have
> > their effects applied at stor-layout time.  So yes, I think this can be
> > dropped.
> 
> It does test the attribute list for functions only.  I think packed should
> be detected from memory layout, so I will test patch dropping this.
> > 
> > > +      /* 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)))
> > > +	    return false;
> > > +
> > > +	  if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
> > > +	    return false;
> > > +	}
> > > 
> > > Is the reason for not making differences between differnt pointer types
> > > really just lazyness to not deal with SCCs?  For that it is easy to add
> > > set of visited type pairs, just like odr_types_equivalent_p does.
> > 
> > Well - TBAA doesn't care about pointed-to types.  See get_alias_set
> > 
> >   else if (POINTER_TYPE_P (t)
> >            && t != ptr_type_node)
> >     set = get_alias_set (ptr_type_node);
> 
> Hmm, I see, interesting hack.  For the first part of comment, I see that
> qualifiers needs to be ignored, but I do not see why we put
> short * and int * pointers to same class.

For the reason that people are very lazy.  For example GCC has code
punning void ** and void * and void * to Type * (and vice versa).  People
just don't expect pointers to be in different alias sets (and there is
little gained with doing that).

> The complete/incomplete type fun with LTO can be solved for C++ but indeed I
> see why pointer to incomplete type needs to be considered compatible with every
> other pointer to structure.  Can't this be dealt with by adding correct edges
> into the aliasing dag?

I don't think so, without the dag degenerating.  We've had this mess
before (complete vs. incomplete structs and so).  It didn't work very 
well.

> > 
> > so the above would at most matter for pointer-type fields of aggregates.
> > And no, we don't want to deal with SCCs - I doubt it would bring any 
> > benefit and the issue here is that I am worried about SCCs being present
> > dependent on the order of streaming (well, the code pre-dates SCC
> > streaming).
> > 
> > > Because we now stream in SCC order anyway, most of time we won't even
> > > need to populate it.  Shall I implement this?
> > 
> > You can certainly try - but I think for cross-language interoperability
> > we want to treat
> > 
> >   struct X { void *p; }
> >   struct Y { void *p; }
> > 
> > and
> > 
> >   struct X { Y *p; }
> >   struct Y { X *q; } 
> > 
> > as compatible so I don't think we can use SCCs to partition alias sets
> > further (that is, we _do_ have to treat pointers conservatively).  The
> > current code is as far as we can get IMHO (well, even the current code
> > is too strict in making struct { void *p } and struct { int *p } not
> > have the same alias-set.
> 
> I will give it a try.  Do you have some examples where the above matters
> for cross-language TBAA?

I don't remember if I added a testcase, so no.  It's just very clear to me
that the look of pointer members may be very different (consider 
reference vs. pointer or pointer to array vs pointer to element).

> > > Other issue I run into is that for Ada bootstrap we have variadic type whose
> > > canonical types are having different temporary set as size.  I think this is
> > > valid and perhaps gimple_canonical_types_compatible_p should consider
> > > variadic arrays to be compatible with any array of compatible type?
> > 
> > Those are all local types and thus the strict equality compare should be
> > ok?  Not sure if we can do in C sth like
> > 
> > void foo (int n)
> > {
> >   struct { int i; int a[n]; } a;
> >   struct { int i; int a[n]; } b;
> > }
> > 
> > and if we'd have to assign the same alias-sets to 'a' and 'b'.
> 
> No idea here either. I wonder if the types are intedned to be TBAA compatible
> across two calls of the function.  In that case we may introduce multiple copies
> of body by early inlining already that may be a problem.

No idea.  Well, the canonical type machinery was supposed to be 
conservative but here we're obviously not 100% conservative.

> > > I am not quite convinced we get variadic types right at LTO time, because
> > > they bypass canonical type calculation anyway and their canonical type
> > > is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
> > > is not safe.  I will look for a testcase.
> > 
> > That is because if they are streamed locally they do not enter type
> > merging, but they still go via gimple_register_canonical_type, so I'm not
> > sure where you see they always get their main variant as canonical type.
> 
> I tought these are handled by:
>       /* And fixup types we streamed locally.  */
>         {
>           struct streamer_tree_cache_d *cache = data_in->reader_cache;
>           unsigned len = cache->nodes.length ();
>           unsigned i;
>           for (i = len; i-- > from;)
>             {
>               tree t = streamer_tree_cache_get_tree (cache, i);
>               if (t == NULL_TREE)
>                 continue;
> 
>               if (TYPE_P (t))
>                 {
>                   gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
>                   TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
>                   if (TYPE_MAIN_VARIANT (t) != t)
>                     {
>                       gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
>                       TYPE_NEXT_VARIANT (t)
>                         = TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t));
>                       TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t)) = t;
>                     }
>                 }
>             }
>         }
> 
> which does not do registering.

That's your code, not mine - but yes, it looks like local types are
streamed when we stream the trees refering to them.  And the canonical
type hash is probably teared down at this point.  The code should
probably call lto_fixup_prevailing_type to also fix 
pointer-to/reference-to chains (and it will deal with main variants
as well).  IMHO the canonical type setting here is ok (during inlining
when we copy variable-length types we should end up sharing TYPE_CANONICAL
IMHO).  AFAICS we do, via copy_node which doesn't reset TYPE_CANONICAL.

Richard.

> > 
> > > I also added check that TYPE_CANONICAL agrees for type variants.  I think it
> > > should because few times in the middle-end uses TYPE_MAIN_VARIANT and seem to
> > > expect this to happen:
> > 
> > Yes.  Otherwise we'd run in circles for code that does
> > 
> >  type = TYPE_CANONICAL (TYPE_MAIN_VARIANT (type));
> > 
> > because the result might not be a main variant.  That's something to
> > verify (both TYPE_CANONICAL and TYPE_MAIN_VARIANT should form a tree). 
> > 
> > So here you'd verify that
> > 
> >     TYPE_MAIN_VARIANT (ct) == ct
> >     && TYPE_CANONICAL (TYPE_MAIN_VARIANT (t)) == ct
> 
> OK will do that incrementally and debug the issues. 
> I believe I tried the second test and it failed with Ada.
> > 
> > > +  /* 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)
> > > +    ;
> > > +  else if (t != ct && !gimple_canonical_types_compatible_p (t, ct, false)
> > > +	   /* 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))
> > 
> > So with LTO this check should never trigger.  I'd probably check
> > !variably_modified_type_p (ct, NULL) first.
> 
> It does - we eventually stream in the bodies and the variably modified types
> and call verifier on that.
> 
> Thanks!
> Honza
> 
> 

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

Re: Check canonical types in verify_type

[Jan Hubicka]

> > Hmm, I see, interesting hack.  For the first part of comment, I see that
> > qualifiers needs to be ignored, but I do not see why we put
> > short * and int * pointers to same class.
> 
> For the reason that people are very lazy.  For example GCC has code
> punning void ** and void * and void * to Type * (and vice versa).  People
> just don't expect pointers to be in different alias sets (and there is
> little gained with doing that).

I think this observation may be out of date.  Removing that code (punting all
pointer to ptr_type_node) increase number of TBAA disambiguations for firefox
by 20%. It also drops number of queries so in reality the number is higher.

So it seems that it may be worth to track this in more sensible way.  This was
tested on LTO where most pointer alias sets are te same anyway, so the increase
should be bigger in non-LTO build. I will gather some stats.

The issue is that modern C++ code packs everything into instances, puts pointers
to instances everywhere and as wel inline everything into one glob, we could
track down a lot of data if we did not get lost in pointers.

We may want to have flag disabling that and we may want to throw away some
precision without throwing away all.

I tried to just trhow away the qualifier from pointer (i.e. make pointer to
qualified type to be globbed to pointer to unqualified type). This seems to
work in a way bootstrapping GCC with one bug (in ipa-icf) and passing
testsuite.
> 
> > The complete/incomplete type fun with LTO can be solved for C++ but indeed I
> > see why pointer to incomplete type needs to be considered compatible with every
> > other pointer to structure.  Can't this be dealt with by adding correct edges
> > into the aliasing dag?
> 
> I don't think so, without the dag degenerating.  We've had this mess
> before (complete vs. incomplete structs and so).  It didn't work very 
> well.

Can you point me to the code/issues, please?
> 
> I don't remember if I added a testcase, so no.  It's just very clear to me
> that the look of pointer members may be very different (consider 
> reference vs. pointer or pointer to array vs pointer to element).

Yep, depending on how much of cross-lanugage datastructures we want to permit.
We could definitely unpeel those differences just like I did with qualifiers.
However this trick is kind of weird because it does not propagate up to aggregates
buildt from these.

In a way some of this sould probably better be handled at canonical type
calculation time if we really want to permit mixing up aggregates with those
differences.

For example I think it would make sense to look throught ARRAY_TYPEs when
handling determining pointer canonical type (so pointer to array and pointer to
element are the same).  We also may ignore TREE_CODE match for POINTER_TYPE_P
if we really do have languages that mixes that.

reference types are used by Ada and Fortran (not Java), so it depends on how
these interface to C. I suppose you are right that these ought to be compatible
with C pointers.  I will dig into respective language standards.
> 
> > > > Other issue I run into is that for Ada bootstrap we have variadic type whose
> > > > canonical types are having different temporary set as size.  I think this is
> > > > valid and perhaps gimple_canonical_types_compatible_p should consider
> > > > variadic arrays to be compatible with any array of compatible type?
> > > 
> > > Those are all local types and thus the strict equality compare should be
> > > ok?  Not sure if we can do in C sth like
> > > 
> > > void foo (int n)
> > > {
> > >   struct { int i; int a[n]; } a;
> > >   struct { int i; int a[n]; } b;
> > > }
> > > 
> > > and if we'd have to assign the same alias-sets to 'a' and 'b'.
> > 
> > No idea here either. I wonder if the types are intedned to be TBAA compatible
> > across two calls of the function.  In that case we may introduce multiple copies
> > of body by early inlining already that may be a problem.
> 
> No idea.  Well, the canonical type machinery was supposed to be 
> conservative but here we're obviously not 100% conservative.

I will look into producing a testcases and lets see.
> 
> > > > I am not quite convinced we get variadic types right at LTO time, because
> > > > they bypass canonical type calculation anyway and their canonical type
> > > > is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
> > > > is not safe.  I will look for a testcase.
> > > 
> > > That is because if they are streamed locally they do not enter type
> > > merging, but they still go via gimple_register_canonical_type, so I'm not
> > > sure where you see they always get their main variant as canonical type.
> > 
> > I tought these are handled by:
> >       /* And fixup types we streamed locally.  */
> >         {
> >           struct streamer_tree_cache_d *cache = data_in->reader_cache;
> >           unsigned len = cache->nodes.length ();
> >           unsigned i;
> >           for (i = len; i-- > from;)
> >             {
> >               tree t = streamer_tree_cache_get_tree (cache, i);
> >               if (t == NULL_TREE)
> >                 continue;
> > 
> >               if (TYPE_P (t))
> >                 {
> >                   gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
> >                   TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
> >                   if (TYPE_MAIN_VARIANT (t) != t)
> >                     {
> >                       gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
> >                       TYPE_NEXT_VARIANT (t)
> >                         = TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t));
> >                       TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t)) = t;
> >                     }
> >                 }
> >             }
> >         }
> > 
> > which does not do registering.
> 
> That's your code, not mine - but yes, it looks like local types are
> streamed when we stream the trees refering to them.  And the canonical

No, it is not mine ;) I only added the code copying fields to variants
and then reverted it per your request, so i suppose SVN blame me :).
 Probably the code comes from original LTO branch.

> type hash is probably teared down at this point.  The code should

Yep, but we can also keep it and just add the types - it is incremental
in its nature.

> probably call lto_fixup_prevailing_type to also fix 
> pointer-to/reference-to chains (and it will deal with main variants
> as well).  IMHO the canonical type setting here is ok (during inlining
> when we copy variable-length types we should end up sharing TYPE_CANONICAL
> IMHO).  AFAICS we do, via copy_node which doesn't reset TYPE_CANONICAL.

Yep, I think canonical types of arrays are merged by C FE if their TREE_TYPE
and TYPE_DOMAIN match and then they are just copied by inliner.
So variable length arrays from different copies of an inline functions are
considered compatible without LTO, while with LTO it depends on early
inliing... 
I am also bit worried about canonical types for C++ where these are
not always defined by their TYPE_MAIN_VARIANTs. I will look into this
in detail.

Honza

Re: Check canonical types in verify_type

[Richard Biener]

On Thu, 21 May 2015, Jan Hubicka wrote:

> > > Hmm, I see, interesting hack.  For the first part of comment, I see that
> > > qualifiers needs to be ignored, but I do not see why we put
> > > short * and int * pointers to same class.
> > 
> > For the reason that people are very lazy.  For example GCC has code
> > punning void ** and void * and void * to Type * (and vice versa).  People
> > just don't expect pointers to be in different alias sets (and there is
> > little gained with doing that).
> 
> I think this observation may be out of date.  Removing that code (punting all
> pointer to ptr_type_node) increase number of TBAA disambiguations for firefox
> by 20%. It also drops number of queries so in reality the number is higher.
> 
> So it seems that it may be worth to track this in more sensible way.  This was
> tested on LTO where most pointer alias sets are te same anyway, so the increase
> should be bigger in non-LTO build. I will gather some stats.
> 
> The issue is that modern C++ code packs everything into instances, puts pointers
> to instances everywhere and as wel inline everything into one glob, we could
> track down a lot of data if we did not get lost in pointers.
> 
> We may want to have flag disabling that and we may want to throw away some
> precision without throwing away all.
> 
> I tried to just trhow away the qualifier from pointer (i.e. make pointer to
> qualified type to be globbed to pointer to unqualified type). This seems to
> work in a way bootstrapping GCC with one bug (in ipa-icf) and passing
> testsuite.

Well, see the big comment before the alias.c pointer type handling.
This is what the C family frontends did before in its get_alias_set
langhook:

      t1 = build_type_no_quals (t);
      if (t1 != t)
        return get_alias_set (t1);

where build_type_no_quals strips qualifiers recursively from t and
pointed-to-types.

> > > The complete/incomplete type fun with LTO can be solved for C++ but indeed I
> > > see why pointer to incomplete type needs to be considered compatible with every
> > > other pointer to structure.  Can't this be dealt with by adding correct edges
> > > into the aliasing dag?
> > 
> > I don't think so, without the dag degenerating.  We've had this mess
> > before (complete vs. incomplete structs and so).  It didn't work very 
> > well.
> 
> Can you point me to the code/issues, please?

It was the old type merging code.  I can spot it in the 4.5 code,
gimple.c:gimple_types_compatible_p where in the POINTER_TYPE
case it does

            && compare_type_names_p (TYPE_MAIN_VARIANT (TREE_TYPE (t1)),
                                     TYPE_MAIN_VARIANT (TREE_TYPE (t2)), 
true))
          {
            /* Replace the pointed-to incomplete type with the
               complete one.
               ???  This simple name-based merging causes at least some
               of the ICEs in canonicalizing FIELD_DECLs during stmt
               read.  For example in GCC we have two different struct deps
               and we mismatch the use in struct cpp_reader in sched-int.h
               vs. mkdeps.c.  Of course the whole exercise is for TBAA
               with structs which contain pointers to incomplete types
               in one unit and to complete ones in another.  So we
               probably should merge these types only with more context.  
*/
            if (COMPLETE_TYPE_P (TREE_TYPE (t2)))
              TREE_TYPE (t1) = TREE_TYPE (t2);
            else
              TREE_TYPE (t2) = TREE_TYPE (t1);

where that of course wrecks the tree graph quite a bit (and it is
dependent on the order of TUs).  Luckily we now have SCC based
streaming and merging, not trying to "complete" types to get more
merging done.

> > 
> > I don't remember if I added a testcase, so no.  It's just very clear to me
> > that the look of pointer members may be very different (consider 
> > reference vs. pointer or pointer to array vs pointer to element).
> 
> Yep, depending on how much of cross-lanugage datastructures we want to permit.
> We could definitely unpeel those differences just like I did with qualifiers.
> However this trick is kind of weird because it does not propagate up to aggregates
> buildt from these.
> 
> In a way some of this sould probably better be handled at canonical type
> calculation time if we really want to permit mixing up aggregates with those
> differences.
> 
> For example I think it would make sense to look throught ARRAY_TYPEs when
> handling determining pointer canonical type (so pointer to array and pointer to
> element are the same).  We also may ignore TREE_CODE match for POINTER_TYPE_P
> if we really do have languages that mixes that.

Another case (I've seen this in fortran vs. C) is:

 int i;

vs.

 common/i/a(1)

thus inter-operability of int[1] and int.  A similar issue (with alias
sets used for accesses) is

struct X { int trailing[1]; };

and code doing

 struct X *p;
 int (*a[16]) = p->trailing;

and

 (*a)[i] vs. p->trailing[i]

(or in the middle-end with frontends that can emit array assignments).

> reference types are used by Ada and Fortran (not Java), so it depends on how
> these interface to C. I suppose you are right that these ought to be compatible
> with C pointers.  I will dig into respective language standards.

It's not so much about language standards but existing practice - few
language standards define interoperability and even if they do not
very many follow the well-defined ways (see fortran which has bind_c
but also tons of existing code that doesn't care and just adapts to
mangling used by various fortran compilers - see SPEC CPU2006 code)

> > 
> > > > > Other issue I run into is that for Ada bootstrap we have variadic type whose
> > > > > canonical types are having different temporary set as size.  I think this is
> > > > > valid and perhaps gimple_canonical_types_compatible_p should consider
> > > > > variadic arrays to be compatible with any array of compatible type?
> > > > 
> > > > Those are all local types and thus the strict equality compare should be
> > > > ok?  Not sure if we can do in C sth like
> > > > 
> > > > void foo (int n)
> > > > {
> > > >   struct { int i; int a[n]; } a;
> > > >   struct { int i; int a[n]; } b;
> > > > }
> > > > 
> > > > and if we'd have to assign the same alias-sets to 'a' and 'b'.
> > > 
> > > No idea here either. I wonder if the types are intedned to be TBAA compatible
> > > across two calls of the function.  In that case we may introduce multiple copies
> > > of body by early inlining already that may be a problem.
> > 
> > No idea.  Well, the canonical type machinery was supposed to be 
> > conservative but here we're obviously not 100% conservative.
> 
> I will look into producing a testcases and lets see.

I'd say that only aggregate assignments might be a problem (component
assignment should pun down to field alias-sets), and you should already
get GIMPLE verifier fails if we ever end up with aggregate assignments
where TYPE_CANONICAL doesn't match.

> > > > > I am not quite convinced we get variadic types right at LTO time, because
> > > > > they bypass canonical type calculation anyway and their canonical type
> > > > > is set by TYPE_MAIN_VARIANT in lto_read_body_or_constructor which I think
> > > > > is not safe.  I will look for a testcase.
> > > > 
> > > > That is because if they are streamed locally they do not enter type
> > > > merging, but they still go via gimple_register_canonical_type, so I'm not
> > > > sure where you see they always get their main variant as canonical type.
> > > 
> > > I tought these are handled by:
> > >       /* And fixup types we streamed locally.  */
> > >         {
> > >           struct streamer_tree_cache_d *cache = data_in->reader_cache;
> > >           unsigned len = cache->nodes.length ();
> > >           unsigned i;
> > >           for (i = len; i-- > from;)
> > >             {
> > >               tree t = streamer_tree_cache_get_tree (cache, i);
> > >               if (t == NULL_TREE)
> > >                 continue;
> > > 
> > >               if (TYPE_P (t))
> > >                 {
> > >                   gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
> > >                   TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
> > >                   if (TYPE_MAIN_VARIANT (t) != t)
> > >                     {
> > >                       gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
> > >                       TYPE_NEXT_VARIANT (t)
> > >                         = TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t));
> > >                       TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (t)) = t;
> > >                     }
> > >                 }
> > >             }
> > >         }
> > > 
> > > which does not do registering.
> > 
> > That's your code, not mine - but yes, it looks like local types are
> > streamed when we stream the trees refering to them.  And the canonical
> 
> No, it is not mine ;) I only added the code copying fields to variants
> and then reverted it per your request, so i suppose SVN blame me :).
>  Probably the code comes from original LTO branch.

;)

> > type hash is probably teared down at this point.  The code should
> 
> Yep, but we can also keep it and just add the types - it is incremental
> in its nature.

Sure.  But local types are usually variadic for which the canonical
merging is somewhat broken (as you noticed).

> > probably call lto_fixup_prevailing_type to also fix 
> > pointer-to/reference-to chains (and it will deal with main variants
> > as well).  IMHO the canonical type setting here is ok (during inlining
> > when we copy variable-length types we should end up sharing TYPE_CANONICAL
> > IMHO).  AFAICS we do, via copy_node which doesn't reset TYPE_CANONICAL.
> 
> Yep, I think canonical types of arrays are merged by C FE if their TREE_TYPE
> and TYPE_DOMAIN match and then they are just copied by inliner.
> So variable length arrays from different copies of an inline functions are
> considered compatible without LTO, while with LTO it depends on early
> inliing... 

Hmm, true.

> I am also bit worried about canonical types for C++ where these are
> not always defined by their TYPE_MAIN_VARIANTs. I will look into this
> in detail.

Yeah - but your type verifier should now catch these, correct?

Richard.