[PATCH][LTO] Remove type completion during merging

[Richard Guenther <rguenther at suse dot de>]

This removes type completion during type merging which made
the type merging outcome depend on the order of registering
types and caused problems when there are type ODR violations
across modules.  The cost of not completing types is less
type merging done (thus possibly more memory use), and a
split brain of gimple_types_compatible_p which needs to
ignore complete/incomplete differences for diagnostics.

To not barf up in the type verifier later we also need to
use the comparison predicates in useless_type_conversion_p
(huh, that change truly feels backward and obviously also
affects non-LTO operation).

When building SPEC 2k6 this patch removes one ICE.

I'm currently re-bootstrapping for all languages due to
the tree-ssa.c change but it already survived bootstrap
and test on x86_64-unknown-linux-gnu w/o that change.

Ok?

Thanks,
Richard.

2010-07-15  Richard Guenther  <rguenther@suse.de>

	* lto-symtab.c (lto_symtab_merge): Use gimple_types_compatible_p.
	(lto_symtab_merge_decls_2): Likewise.
	* gimple.h (gimple_types_compatible_p): Declare.
	* gimple.c (gimple_queue_type_fixup): Remove.
	(gimple_fixup_complete_and_incomplete_subtype_p): Likewise.
	(gimple_compatible_complete_and_incomplete_type_p): New
	function.
	(gimple_types_compatible_p): Adjust.
	(gimple_register_type): Remove type fixup code.
	(print_gimple_types_stats): Adjust.
	(free_gimple_type_tables): Likewise.
	* lto-streamer-in.c (input_gimple_stmt): Use gimple_types_compatible_p.
	* tree-ssa.c (useless_type_conversion_p): Likewise.

Index: gcc/lto-symtab.c
===================================================================
*** gcc/lto-symtab.c	(revision 162181)
--- gcc/lto-symtab.c	(working copy)
*************** lto_symtab_merge (lto_symtab_entry_t pre
*** 348,354 ****
  
    if (TREE_CODE (decl) == FUNCTION_DECL)
      {
!       if (TREE_TYPE (prevailing_decl) != TREE_TYPE (decl))
  	/* If we don't have a merged type yet...sigh.  The linker
  	   wouldn't complain if the types were mismatched, so we
  	   probably shouldn't either.  Just use the type from
--- 348,355 ----
  
    if (TREE_CODE (decl) == FUNCTION_DECL)
      {
!       if (!gimple_types_compatible_p (TREE_TYPE (prevailing_decl),
! 				      TREE_TYPE (decl), false))
  	/* If we don't have a merged type yet...sigh.  The linker
  	   wouldn't complain if the types were mismatched, so we
  	   probably shouldn't either.  Just use the type from
*************** lto_symtab_merge (lto_symtab_entry_t pre
*** 381,387 ****
       fixup process didn't yet run.  */
    prevailing_type = gimple_register_type (prevailing_type);
    type = gimple_register_type (type);
!   if (prevailing_type != type)
      {
        if (COMPLETE_TYPE_P (type))
  	return false;
--- 382,388 ----
       fixup process didn't yet run.  */
    prevailing_type = gimple_register_type (prevailing_type);
    type = gimple_register_type (type);
!   if (!gimple_types_compatible_p (prevailing_type, type, false))
      {
        if (COMPLETE_TYPE_P (type))
  	return false;
*************** lto_symtab_merge (lto_symtab_entry_t pre
*** 406,412 ****
  	  if (TREE_CODE (tem1) != TREE_CODE (tem2))
  	    return false;
  
! 	  if (gimple_register_type (tem1) != gimple_register_type (tem2))
  	    return false;
  	}
  
--- 407,414 ----
  	  if (TREE_CODE (tem1) != TREE_CODE (tem2))
  	    return false;
  
! 	  if (!gimple_types_compatible_p (gimple_register_type (tem1),
! 					  gimple_register_type (tem2), false))
  	    return false;
  	}
  
*************** lto_symtab_merge_decls_2 (void **slot)
*** 606,612 ****
    /* Diagnose all mismatched re-declarations.  */
    for (i = 0; VEC_iterate (tree, mismatches, i, decl); ++i)
      {
!       if (TREE_TYPE (prevailing->decl) != TREE_TYPE (decl))
  	diagnosed_p |= warning_at (DECL_SOURCE_LOCATION (decl), 0,
  				   "type of %qD does not match original "
  				   "declaration", decl);
--- 608,615 ----
    /* Diagnose all mismatched re-declarations.  */
    for (i = 0; VEC_iterate (tree, mismatches, i, decl); ++i)
      {
!       if (!gimple_types_compatible_p (TREE_TYPE (prevailing->decl),
! 				      TREE_TYPE (decl), false))
  	diagnosed_p |= warning_at (DECL_SOURCE_LOCATION (decl), 0,
  				   "type of %qD does not match original "
  				   "declaration", decl);
Index: gcc/gimple.h
===================================================================
*** gcc/gimple.h	(revision 162181)
--- gcc/gimple.h	(working copy)
*************** extern tree get_call_expr_in (tree t);
*** 956,961 ****
--- 956,962 ----
  extern void recalculate_side_effects (tree);
  extern bool gimple_compare_field_offset (tree, tree);
  extern tree gimple_register_type (tree);
+ extern bool gimple_types_compatible_p (tree, tree, bool);
  extern void print_gimple_types_stats (void);
  extern void free_gimple_type_tables (void);
  extern tree gimple_unsigned_type (tree);
Index: gcc/gimple.c
===================================================================
*** gcc/gimple.c	(revision 162209)
--- gcc/gimple.c	(working copy)
*************** static struct pointer_map_t *type_hash_c
*** 47,52 ****
--- 47,54 ----
  /* Global type comparison cache.  */
  static htab_t gtc_visited;
  static struct obstack gtc_ob;
+ static htab_t gtc_visited2;
+ static struct obstack gtc_ob2;
  
  /* All the tuples have their operand vector (if present) at the very bottom
     of the structure.  Therefore, the offset required to find the
*************** gimple_compare_field_offset (tree f1, tr
*** 3323,3359 ****
    return false;
  }
  
! typedef struct type_fixup_s {
!     tree context;
!     tree *incomplete;
!     tree complete;
! } type_fixup;
! DEF_VEC_O(type_fixup);
! DEF_VEC_ALLOC_O(type_fixup,heap);
! 
! static VEC(type_fixup, heap) *gimple_register_type_fixups = NULL;
! 
! static void
! gimple_queue_type_fixup (tree context, tree *incomplete, tree complete)
! {
!   type_fixup f;
!   f.context = context;
!   f.incomplete = incomplete;
!   f.complete = complete;
!   VEC_safe_push (type_fixup, heap, gimple_register_type_fixups, &f);
! }
! 
! /* If the type *T1P and the type *T2P are a complete and an incomplete
!    variant of the same type return true and queue a fixup for the
!    incomplete one and its CONTEXT.  Return false otherwise.  */
  
  static bool
! gimple_fixup_complete_and_incomplete_subtype_p (tree context1, tree *t1p,
! 						tree context2, tree *t2p)
  {
-   tree t1 = *t1p;
-   tree t2 = *t2p;
- 
    /* If one pointer points to an incomplete type variant of
       the other pointed-to type they are the same.  */
    if (TREE_CODE (t1) == TREE_CODE (t2)
--- 3325,3336 ----
    return false;
  }
  
! /* If the type T1 and the type T2 are a complete and an incomplete
!    variant of the same type return true.  */
  
  static bool
! gimple_compatible_complete_and_incomplete_subtype_p (tree t1, tree t2)
  {
    /* If one pointer points to an incomplete type variant of
       the other pointed-to type they are the same.  */
    if (TREE_CODE (t1) == TREE_CODE (t2)
*************** gimple_fixup_complete_and_incomplete_sub
*** 3363,3392 ****
        && TYPE_QUALS (t1) == TYPE_QUALS (t2)
        && compare_type_names_p (TYPE_MAIN_VARIANT (t1),
  			       TYPE_MAIN_VARIANT (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 (t2))
! 	gimple_queue_type_fixup (context1, t1p, t2);
!       else
! 	gimple_queue_type_fixup (context2, t2p, t1);
!       return true;
!     }
    return false;
  }
  
  /* Return 1 iff T1 and T2 are structurally identical.
     Otherwise, return 0.  */
  
! static int
! gimple_types_compatible_p (tree t1, tree t2)
  {
    type_pair_t p = NULL;
  
--- 3340,3354 ----
        && TYPE_QUALS (t1) == TYPE_QUALS (t2)
        && compare_type_names_p (TYPE_MAIN_VARIANT (t1),
  			       TYPE_MAIN_VARIANT (t2), true))
!     return true;
    return false;
  }
  
  /* Return 1 iff T1 and T2 are structurally identical.
     Otherwise, return 0.  */
  
! bool
! gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p)
  {
    type_pair_t p = NULL;
  
*************** gimple_types_compatible_p (tree t1, tree
*** 3439,3445 ****
        /* Perform cheap tail-recursion for vector and complex types.  */
        if (TREE_CODE (t1) == VECTOR_TYPE
  	  || TREE_CODE (t1) == COMPLEX_TYPE)
! 	return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2));
  
        /* For integral types fall thru to more complex checks.  */
      }
--- 3401,3408 ----
        /* Perform cheap tail-recursion for vector and complex types.  */
        if (TREE_CODE (t1) == VECTOR_TYPE
  	  || TREE_CODE (t1) == COMPLEX_TYPE)
! 	return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
! 					  for_merging_p);
  
        /* For integral types fall thru to more complex checks.  */
      }
*************** gimple_types_compatible_p (tree t1, tree
*** 3460,3466 ****
  
    /* If we've visited this type pair before (in the case of aggregates
       with self-referential types), and we made a decision, return it.  */
!   p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
    if (p->same_p == 0 || p->same_p == 1)
      {
        /* We have already decided whether T1 and T2 are the
--- 3423,3431 ----
  
    /* If we've visited this type pair before (in the case of aggregates
       with self-referential types), and we made a decision, return it.  */
!   p = lookup_type_pair (t1, t2,
! 			for_merging_p ? &gtc_visited : &gtc_visited2,
! 			for_merging_p ? &gtc_ob : &gtc_ob2);
    if (p->same_p == 0 || p->same_p == 1)
      {
        /* We have already decided whether T1 and T2 are the
*************** gimple_types_compatible_p (tree t1, tree
*** 3489,3495 ****
      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_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))
  	goto different_types;
--- 3454,3461 ----
      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_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
! 				      for_merging_p)
  	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
  	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
  	goto different_types;
*************** gimple_types_compatible_p (tree t1, tree
*** 3538,3544 ****
      case METHOD_TYPE:
        /* Method types should belong to the same class.  */
        if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
! 				 TYPE_METHOD_BASETYPE (t2)))
  	goto different_types;
  
        /* Fallthru  */
--- 3504,3510 ----
      case METHOD_TYPE:
        /* Method types should belong to the same class.  */
        if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
! 				      TYPE_METHOD_BASETYPE (t2), for_merging_p))
  	goto different_types;
  
        /* Fallthru  */
*************** gimple_types_compatible_p (tree t1, tree
*** 3546,3554 ****
      case FUNCTION_TYPE:
        /* Function types are the same if the return type and arguments types
  	 are the same.  */
!       if (!gimple_fixup_complete_and_incomplete_subtype_p
! 	     (t1, &TREE_TYPE (t1), t2, &TREE_TYPE (t2))
! 	  && !gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
  	goto different_types;
  
        if (!targetm.comp_type_attributes (t1, t2))
--- 3512,3522 ----
      case FUNCTION_TYPE:
        /* Function types are the same if the return type and arguments types
  	 are the same.  */
!       if ((for_merging_p
! 	   || !gimple_compatible_complete_and_incomplete_subtype_p
! 	         (TREE_TYPE (t1), TREE_TYPE (t2)))
! 	  && !gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
! 					 for_merging_p))
  	goto different_types;
  
        if (!targetm.comp_type_attributes (t1, t2))
*************** gimple_types_compatible_p (tree t1, tree
*** 3564,3573 ****
  	       parms1 && parms2;
  	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
  	    {
! 	      if (!gimple_fixup_complete_and_incomplete_subtype_p
! 		    (t1, &TREE_VALUE (parms1), t2, &TREE_VALUE (parms2))
  		  && !gimple_types_compatible_p (TREE_VALUE (parms1),
! 						 TREE_VALUE (parms2)))
  		goto different_types;
  	    }
  
--- 3532,3543 ----
  	       parms1 && parms2;
  	       parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
  	    {
! 	      if ((for_merging_p
! 		   || !gimple_compatible_complete_and_incomplete_subtype_p
! 		         (TREE_VALUE (parms1), TREE_VALUE (parms2)))
  		  && !gimple_types_compatible_p (TREE_VALUE (parms1),
! 						 TREE_VALUE (parms2),
! 						 for_merging_p))
  		goto different_types;
  	    }
  
*************** gimple_types_compatible_p (tree t1, tree
*** 3579,3587 ****
  
      case OFFSET_TYPE:
        {
! 	if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
  	    || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1),
! 					   TYPE_OFFSET_BASETYPE (t2)))
  	  goto different_types;
  
  	goto same_types;
--- 3549,3559 ----
  
      case OFFSET_TYPE:
        {
! 	if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
! 					for_merging_p)
  	    || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1),
! 					   TYPE_OFFSET_BASETYPE (t2),
! 					   for_merging_p))
  	  goto different_types;
  
  	goto same_types;
*************** gimple_types_compatible_p (tree t1, tree
*** 3597,3609 ****
  
  	/* If one pointer points to an incomplete type variant of
  	   the other pointed-to type they are the same.  */
! 	if (gimple_fixup_complete_and_incomplete_subtype_p
! 	      (t1, &TREE_TYPE (t1), t2, &TREE_TYPE (t2)))
  	  goto same_types;
  
  	/* Otherwise, pointer and reference types are the same if the
  	   pointed-to types are the same.  */
! 	if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
  	  goto same_types;
  
  	goto different_types;
--- 3569,3583 ----
  
  	/* If one pointer points to an incomplete type variant of
  	   the other pointed-to type they are the same.  */
! 	if (!for_merging_p
! 	    && gimple_compatible_complete_and_incomplete_subtype_p
! 	         (TREE_TYPE (t1), TREE_TYPE (t2)))
  	  goto same_types;
  
  	/* Otherwise, pointer and reference types are the same if the
  	   pointed-to types are the same.  */
! 	if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
! 				       for_merging_p))
  	  goto same_types;
  
  	goto different_types;
*************** gimple_types_compatible_p (tree t1, tree
*** 3699,3705 ****
  		|| DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
  		|| !gimple_compare_field_offset (f1, f2)
  		|| !gimple_types_compatible_p (TREE_TYPE (f1),
! 					       TREE_TYPE (f2)))
  	      goto different_types;
  	  }
  
--- 3673,3679 ----
  		|| DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
  		|| !gimple_compare_field_offset (f1, f2)
  		|| !gimple_types_compatible_p (TREE_TYPE (f1),
! 					       TREE_TYPE (f2), for_merging_p))
  	      goto different_types;
  	  }
  
*************** gimple_type_eq (const void *p1, const vo
*** 4040,4046 ****
  {
    const_tree t1 = (const_tree) p1;
    const_tree t2 = (const_tree) p2;
!   return gimple_types_compatible_p (CONST_CAST_TREE (t1), CONST_CAST_TREE (t2));
  }
  
  
--- 4014,4021 ----
  {
    const_tree t1 = (const_tree) p1;
    const_tree t2 = (const_tree) p2;
!   return gimple_types_compatible_p (CONST_CAST_TREE (t1),
! 				    CONST_CAST_TREE (t2), true);
  }
  
  
*************** gimple_register_type (tree t)
*** 4070,4083 ****
    if (gimple_types == NULL)
      gimple_types = htab_create (16381, gimple_type_hash, gimple_type_eq, 0);
  
-   gcc_assert (VEC_empty (type_fixup, gimple_register_type_fixups));
    slot = htab_find_slot (gimple_types, t, INSERT);
    if (*slot
        && *(tree *)slot != t)
      {
        tree new_type = (tree) *((tree *) slot);
-       unsigned i;
-       type_fixup *f;
  
        /* Do not merge types with different addressability.  */
        gcc_assert (TREE_ADDRESSABLE (t) == TREE_ADDRESSABLE (new_type));
--- 4045,4055 ----
*************** gimple_register_type (tree t)
*** 4129,4139 ****
  
        TYPE_CANONICAL (t) = new_type;
        t = new_type;
- 
-       for (i = 0;
- 	   VEC_iterate (type_fixup, gimple_register_type_fixups, i, f); ++i)
- 	if (f->context == t)
- 	  *(f->incomplete) = f->complete;
      }
    else
      {
--- 4101,4106 ----
*************** gimple_register_type (tree t)
*** 4141,4147 ****
        *slot = (void *) t;
      }
  
-   VEC_truncate (type_fixup, gimple_register_type_fixups, 0);
    return t;
  }
  
--- 4108,4113 ----
*************** print_gimple_types_stats (void)
*** 4162,4168 ****
    else
      fprintf (stderr, "GIMPLE type table is empty\n");
    if (gtc_visited)
!     fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
  	     "elements, %ld searches, %ld collisions (ratio: %f)\n",
  	     (long) htab_size (gtc_visited),
  	     (long) htab_elements (gtc_visited),
--- 4128,4134 ----
    else
      fprintf (stderr, "GIMPLE type table is empty\n");
    if (gtc_visited)
!     fprintf (stderr, "GIMPLE type merging comparison table: size %ld, %ld "
  	     "elements, %ld searches, %ld collisions (ratio: %f)\n",
  	     (long) htab_size (gtc_visited),
  	     (long) htab_elements (gtc_visited),
*************** print_gimple_types_stats (void)
*** 4170,4175 ****
--- 4136,4151 ----
  	     (long) gtc_visited->collisions,
  	     htab_collisions (gtc_visited));
    else
+     fprintf (stderr, "GIMPLE type merging comparison table is empty\n");
+   if (gtc_visited2)
+     fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
+ 	     "elements, %ld searches, %ld collisions (ratio: %f)\n",
+ 	     (long) htab_size (gtc_visited2),
+ 	     (long) htab_elements (gtc_visited2),
+ 	     (long) gtc_visited2->searches,
+ 	     (long) gtc_visited2->collisions,
+ 	     htab_collisions (gtc_visited2));
+   else
      fprintf (stderr, "GIMPLE type comparison table is empty\n");
  }
  
*************** free_gimple_type_tables (void)
*** 4198,4203 ****
--- 4174,4185 ----
        obstack_free (&gtc_ob, NULL);
        gtc_visited = NULL;
      }
+   if (gtc_visited2)
+     {
+       htab_delete (gtc_visited2);
+       obstack_free (&gtc_ob2, NULL);
+       gtc_visited2 = NULL;
+     }
  }
  
  
Index: gcc/lto-streamer-in.c
===================================================================
*** gcc/lto-streamer-in.c	(revision 162209)
--- gcc/lto-streamer-in.c	(working copy)
*************** input_gimple_stmt (struct lto_input_bloc
*** 960,966 ****
  		  for (tem = TYPE_FIELDS (type); tem; tem = TREE_CHAIN (tem))
  		    {
  		      if (tem == field
! 			  || (TREE_TYPE (tem) == TREE_TYPE (field)
  			      && DECL_NONADDRESSABLE_P (tem)
  				 == DECL_NONADDRESSABLE_P (field)
  			      && gimple_compare_field_offset (tem, field)))
--- 960,968 ----
  		  for (tem = TYPE_FIELDS (type); tem; tem = TREE_CHAIN (tem))
  		    {
  		      if (tem == field
! 			  || (gimple_types_compatible_p (TREE_TYPE (tem),
! 							 TREE_TYPE (field),
! 							 false)
  			      && DECL_NONADDRESSABLE_P (tem)
  				 == DECL_NONADDRESSABLE_P (field)
  			      && gimple_compare_field_offset (tem, field)))
Index: gcc/tree-ssa.c
===================================================================
*** gcc/tree-ssa.c	(revision 162215)
--- gcc/tree-ssa.c	(working copy)
*************** useless_type_conversion_p (tree outer_ty
*** 1426,1432 ****
       compared types.  */
    else if (AGGREGATE_TYPE_P (inner_type)
  	   && TREE_CODE (inner_type) == TREE_CODE (outer_type))
!     return false;
  
    return false;
  }
--- 1426,1432 ----
       compared types.  */
    else if (AGGREGATE_TYPE_P (inner_type)
  	   && TREE_CODE (inner_type) == TREE_CODE (outer_type))
!     return gimple_types_compatible_p (outer_type, inner_type, false);
  
    return false;
  }