[PATCH][LTO] More type merging fixes

Richard Guenther rguenther@suse.de
Tue Jul 20 14:40:00 GMT 2010


We are still merging too many things (incompatible things even).  It
turns out our clever caching of gimple_types_compatible_p results
clashes with the optimistic handling of recursion in the type graph.

A full solution would cache results for edges, not for nodes
(thus, based on where we come from for the gimple_types_compatible_p
call).  But that would explode the comparison table even more.
So the following implements a simpler solution not caching positive
outcomes of comparisons that include cycle knowledge.  That possibly
has the biggest compile-time impact (we only have to avoid recording
positive outcome inside SCCs, but for that we'd have to build those).

Bootstrapped and tested on x86_64-unknown-linux-gnu, I am checking
SPEC 2k6 for problems (including excessive compile-time) right now.

Ok?

Thanks,
Richard.

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

	PR lto/42451
	* gimple.c (saw_cycle): New global variable.
	(gimple_types_compatible_p_1): Rename from ...
	(gimple_types_compatible_p): ... this.  New wrapper
	resetting saw_cycle.
	(gimple_types_compatible_p_1): Record if we run into
	a cycle and do not record equivalence from such a case.

	* gcc.dg/lto/20100720-3_0.c: New testcase.
	* gcc.dg/lto/20100720-3_1.c: Likewise.

Index: gcc/gimple.c
===================================================================
*** gcc/gimple.c	(revision 162337)
--- gcc/gimple.c	(working copy)
*************** gimple_compatible_complete_and_incomplet
*** 3344,3354 ****
    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;
  
--- 3344,3356 ----
    return false;
  }
  
+ static bool saw_cycle;
+ 
  /* Return 1 iff T1 and T2 are structurally identical.
     Otherwise, return 0.  */
  
! static bool
! gimple_types_compatible_p_1 (tree t1, tree t2, bool for_merging_p)
  {
    type_pair_t p = NULL;
  
*************** gimple_types_compatible_p (tree t1, tree
*** 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.  */
      }
--- 3403,3410 ----
        /* 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_1 (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
*** 3436,3441 ****
--- 3438,3444 ----
      {
        /* We are currently comparing this pair of types, assume
  	 that they are the same and let the caller decide.  */
+       saw_cycle = true;
        return 1;
      }
  
*************** gimple_types_compatible_p (tree t1, tree
*** 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;
--- 3457,3464 ----
      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_1 (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
*** 3503,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  */
--- 3506,3514 ----
  
      case METHOD_TYPE:
        /* Method types should belong to the same class.  */
!       if (!gimple_types_compatible_p_1 (TYPE_METHOD_BASETYPE (t1),
! 					TYPE_METHOD_BASETYPE (t2),
! 					for_merging_p))
  	goto different_types;
  
        /* Fallthru  */
*************** gimple_types_compatible_p (tree t1, tree
*** 3515,3522 ****
        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))
--- 3519,3526 ----
        if ((for_merging_p
  	   || !gimple_compatible_complete_and_incomplete_subtype_p
  	         (TREE_TYPE (t1), TREE_TYPE (t2)))
! 	  && !gimple_types_compatible_p_1 (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
*** 3535,3543 ****
  	      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;
  	    }
  
--- 3539,3547 ----
  	      if ((for_merging_p
  		   || !gimple_compatible_complete_and_incomplete_subtype_p
  		         (TREE_VALUE (parms1), TREE_VALUE (parms2)))
! 		  && !gimple_types_compatible_p_1 (TREE_VALUE (parms1),
! 						   TREE_VALUE (parms2),
! 						   for_merging_p))
  		goto different_types;
  	    }
  
*************** gimple_types_compatible_p (tree t1, tree
*** 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;
--- 3553,3563 ----
  
      case OFFSET_TYPE:
        {
! 	if (!gimple_types_compatible_p_1 (TREE_TYPE (t1), TREE_TYPE (t2),
! 					  for_merging_p)
! 	    || !gimple_types_compatible_p_1 (TYPE_OFFSET_BASETYPE (t1),
! 					     TYPE_OFFSET_BASETYPE (t2),
! 					     for_merging_p))
  	  goto different_types;
  
  	goto same_types;
*************** gimple_types_compatible_p (tree t1, tree
*** 3576,3583 ****
  
  	/* 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;
--- 3580,3587 ----
  
  	/* Otherwise, pointer and reference types are the same if the
  	   pointed-to types are the same.  */
! 	if (gimple_types_compatible_p_1 (TREE_TYPE (t1), TREE_TYPE (t2),
! 					 for_merging_p))
  	  goto same_types;
  
  	goto different_types;
*************** gimple_types_compatible_p (tree t1, tree
*** 3672,3679 ****
  	    if (DECL_NAME (f1) != DECL_NAME (f2)
  		|| 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;
  	  }
  
--- 3676,3683 ----
  	    if (DECL_NAME (f1) != DECL_NAME (f2)
  		|| DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
  		|| !gimple_compare_field_offset (f1, f2)
! 		|| !gimple_types_compatible_p_1 (TREE_TYPE (f1),
! 						 TREE_TYPE (f2), for_merging_p))
  	      goto different_types;
  	  }
  
*************** different_types:
*** 3696,3706 ****
  
    /* Common exit path for types that are compatible.  */
  same_types:
!   p->same_p = 1;
    return 1;
  }
  
! 
  
  
  /* Per pointer state for the SCC finding.  The on_sccstack flag
--- 3700,3715 ----
  
    /* Common exit path for types that are compatible.  */
  same_types:
!   p->same_p = saw_cycle ? -2 : 1;
    return 1;
  }
  
! bool
! gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p)
! {
!   saw_cycle = false;
!   return gimple_types_compatible_p_1 (t1, t2, for_merging_p);
! }
  
  
  /* Per pointer state for the SCC finding.  The on_sccstack flag
Index: gcc/testsuite/gcc.dg/lto/20100720-3_0.c
===================================================================
*** gcc/testsuite/gcc.dg/lto/20100720-3_0.c	(revision 0)
--- gcc/testsuite/gcc.dg/lto/20100720-3_0.c	(revision 0)
***************
*** 0 ****
--- 1,24 ----
+ /* { dg-lto-do run } */
+ 
+ struct X {
+   int a;
+ };
+ 
+ struct link {
+   struct list_node *next;
+ };
+ 
+ struct list_node {
+   struct link lnk;
+   struct X *value;
+ };
+ 
+ void f(struct list_node *lst)
+ {
+   lst->lnk.next = 0;
+ }
+ 
+ int main(void)
+ {
+   return 0;
+ }
Index: gcc/testsuite/gcc.dg/lto/20100720-3_1.c
===================================================================
*** gcc/testsuite/gcc.dg/lto/20100720-3_1.c	(revision 0)
--- gcc/testsuite/gcc.dg/lto/20100720-3_1.c	(revision 0)
***************
*** 0 ****
--- 1,17 ----
+ struct X {
+   int b;
+ };
+ 
+ struct link {
+   struct list_node *next;
+ };
+ 
+ struct list_node {
+   struct link lnk;
+   struct X *value;
+ };
+ 
+ void g(struct list_node *lst)
+ {
+   lst->lnk.next = 0;
+ }



More information about the Gcc-patches mailing list