[RFC] Using One Definition Rule for types during LTO devirtualizatoin?

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
during LTO we seem to give up on many valid devirtualization cases because
the types are not merged by type merging machinery. This is i.e. because their
declarations are different; one unit define a function, while in the other
unit it is just an external declaration.

It is my understanding that C++ standard enforces one definition rule for
types, too (to enable sane mangling?) and that we can basically match types
by their name and contextes (namespaces/outer classes)>  Does the attaches
patch make sense?

It enables a lot more devirtualization to happen during Firefox build.

Honza
Index: gimple-fold.c
===================================================================
*** gimple-fold.c	(revision 200063)
--- gimple-fold.c	(working copy)
*************** gimple_extract_devirt_binfo_from_cst (tr
*** 1038,1044 ****
        HOST_WIDE_INT pos, size;
        tree fld;
  
!       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
  	break;
        if (offset < 0)
  	return NULL_TREE;
--- 1038,1044 ----
        HOST_WIDE_INT pos, size;
        tree fld;
  
!       if (types_same_for_odr (type, expected_type))
  	break;
        if (offset < 0)
  	return NULL_TREE;
Index: tree.c
===================================================================
*** tree.c	(revision 200063)
--- tree.c	(working copy)
*************** lhd_gcc_personality (void)
*** 11618,11623 ****
--- 11618,11695 ----
    return gcc_eh_personality_decl;
  }
  
+ /* For languages with One Definition Rule, work out if
+    decls are actually the same even if the tree representation
+    differs.  This handles only decls appearing in TYPE_NAME
+    and TYPE_CONTEXT.  That is NAMESPACE_DECL, TYPE_DECL,
+    RECORD_TYPE and IDENTIFIER_NODE.  */
+ 
+ static bool
+ decls_same_for_odr (tree decl1, tree decl2)
+ {
+   if (decl1 && TREE_CODE (decl1) == TYPE_DECL
+       && DECL_ORIGINAL_TYPE (decl1))
+     decl1 = DECL_ORIGINAL_TYPE (decl1);
+   if (decl2 && TREE_CODE (decl2) == TYPE_DECL
+       && DECL_ORIGINAL_TYPE (decl2))
+     decl2 = DECL_ORIGINAL_TYPE (decl2);
+   if (decl1 == decl2)
+     return true;
+   if (!decl1 || !decl2)
+     return false;
+   if (TREE_CODE (decl1) != TREE_CODE (decl2))
+     return false;
+   if (TREE_CODE (decl1) == TRANSLATION_UNIT_DECL)
+     return true;
+   if (TREE_CODE (decl1) != NAMESPACE_DECL
+       && TREE_CODE (decl1) != RECORD_TYPE
+       && TREE_CODE (decl1) != TYPE_DECL)
+     return false;
+   if (!DECL_NAME (decl1))
+     return false;
+   if (!decls_same_for_odr (DECL_NAME (decl1), DECL_NAME (decl2)))
+     return false;
+   return decls_same_for_odr (DECL_CONTEXT (decl1),
+ 		             DECL_CONTEXT (decl2));
+ }
+ 
+ /* For languages with One Definition Rule, work out if
+    types are same even if the tree representation differs. 
+    This is non-trivial for LTO where minnor differences in
+    the type representation may have prevented type merging
+    to merge two copies of otherwise equivalent type.  */
+ 
+ bool
+ types_same_for_odr (tree type1, tree type2)
+ {
+   type1 = TYPE_MAIN_VARIANT (type1);
+   type2 = TYPE_MAIN_VARIANT (type2);
+   if (type1 == type2)
+     return true;
+   if (!type1 || !type2)
+     return false;
+ 
+   /* If types are not structuraly same, do not bother to contnue.
+      Match in the remainder of code would mean ODR violation.  */
+   if (!types_compatible_p (type1, type2))
+     return false;
+ 
+ #ifndef ENABLE_CHECKING
+   if (!in_lto_p)
+     return false;
+ #endif
+ 
+   if (!TYPE_NAME (type1))
+     return false;
+   if (!decls_same_for_odr (TYPE_NAME (type1), TYPE_NAME (type2)))
+     return false;
+   if (!decls_same_for_odr (TYPE_CONTEXT (type1), TYPE_CONTEXT (type2)))
+     return false;
+   gcc_assert (in_lto_p);
+     
+   return true;
+ }
+ 
  /* Try to find a base info of BINFO that would have its field decl at offset
     OFFSET within the BINFO type and which is of EXPECTED_TYPE.  If it can be
     found, return, otherwise return NULL_TREE.  */
*************** get_binfo_at_offset (tree binfo, HOST_WI
*** 11633,11639 ****
        tree fld;
        int i;
  
!       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
  	  return binfo;
        if (offset < 0)
  	return NULL_TREE;
--- 11705,11711 ----
        tree fld;
        int i;
  
!       if (types_same_for_odr (type, expected_type))
  	  return binfo;
        if (offset < 0)
  	return NULL_TREE;
*************** get_binfo_at_offset (tree binfo, HOST_WI
*** 11663,11669 ****
  	{
  	  tree base_binfo, found_binfo = NULL_TREE;
  	  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
! 	    if (TREE_TYPE (base_binfo) == TREE_TYPE (fld))
  	      {
  		found_binfo = base_binfo;
  		break;
--- 11735,11741 ----
  	{
  	  tree base_binfo, found_binfo = NULL_TREE;
  	  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
! 	    if (types_same_for_odr (TREE_TYPE (base_binfo), TREE_TYPE (fld)))
  	      {
  		found_binfo = base_binfo;
  		break;
Index: tree.h
===================================================================
*** tree.h	(revision 200063)
--- tree.h	(working copy)
*************** extern location_t tree_nonartificial_loc
*** 5973,5978 ****
--- 5973,5979 ----
  extern tree block_ultimate_origin (const_tree);
  
  extern tree get_binfo_at_offset (tree, HOST_WIDE_INT, tree);
+ extern bool types_same_for_odr (tree, tree);
  extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *,
  				     HOST_WIDE_INT *, HOST_WIDE_INT *);
  extern bool contains_bitfld_component_ref_p (const_tree);