Re: [RFA] Type inheritance graph analysis & speculative devirtualization, part 4/7, ODR at LTO time

[Jan Hubicka <hubicka at ucw dot cz>]

Richard, Jason,
I would apprechiate your opinion on this patch.  It blocks all the code that makes
use of ipa-devirt post LTO streaming.

The main part that I would like to know your opinion on is the ODR rule implementation
by vtable comparsion (it looks obvious but I got it wrong once already) and the idea
of choosing type leader out of all (presumably equivalent) ODR types and killing the
other BINFOs.

I will also gather statistics on size of the ODR query cache size on the bigger
beasts Martin or me can build and will set up some linear limit on it.  For
firefox it takes approximately (num_methods+num_differet_obj_type_refs)*1.3.  I
am thinking about seeting limit to cca 100 instead of 1.3 and simply start
loosing devirtualization oppurtunities if it is met. I do not think sane
sourcebases will ever hit it.

Thank you,
Honza
> Hi,
> this patch makes inheritance graph builder to work on LTO.  Nothing but
> ODR violation warnings and dump file is produced, yet.
> 
> The main change is to make types_same_for_odr and ODR hasher to use
> assembler name of virtual tables of the type (if present) to establish type
> equality. This is result of discussion with Jason at 
> http://gcc.gnu.org/ml/gcc-patches/2013-08/msg00826.html
> Jason, does the implemenetation seem sane?  
> 
> Multiple tree types can now be representations of single ODR type.  There is
> new add_type_duplicate that output warnings on obvious mismatches and records
> variant in odr_type->types array.  Those are used for debug output (it may
> be interesting to get more of the unified by Richard's merging).
> 
> Trickier part is the code that merges BINFOs of ODR equivalent types.  This is
> important since we do not want to keep external vtables around when internal
> exists (external version may refer to external static methods that are internal
> to our LTO unit). With ODR violations it may lead to wrong devirtualization,
> but that is the case previously anyway.
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* Makefile.in (ipa-devirt.o): Add dependency on diagnostic.h
> 	* ipa-devirt.c: Include diganostic.h
> 	(odr_type_d): Add types and types_set.
> 	(hash_type_name): Work for types with vtables during LTO.
> 	(odr_hasher::remove): Fix comment; destroy types_set.
> 	(add_type_duplicate): New function,
> 	(get_odr_type): Use it.
> 	(dump_type_inheritance_graph): Dump type duplicates.
> 	* ipa.c (symtab_remove_unreachable_nodes): Build type inheritance
> 	graph.
> 	* tree.c (types_same_for_odr): Give exact answers on types with
> 	virtual tables.

> Index: Makefile.in
> ===================================================================
> *** Makefile.in	(revision 201836)
> --- Makefile.in	(working copy)
> *************** ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) co
> *** 2948,2954 ****
>      $(LTO_STREAMER_H) $(DATA_STREAMER_H)
>   ipa-devirt.o : ipa-devirt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
>      $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \
> !    $(IPA_UTILS_H) $(HASH_TABLE_H) 
>   ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
>      langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
>      $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \
> --- 2948,2954 ----
>      $(LTO_STREAMER_H) $(DATA_STREAMER_H)
>   ipa-devirt.o : ipa-devirt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
>      $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \
> !    $(IPA_UTILS_H) $(HASH_TABLE_H) $(DIAGNOSTIC_H)
>   ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
>      langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
>      $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \
> Index: ipa-devirt.c
> ===================================================================
> *** ipa-devirt.c	(revision 201836)
> --- ipa-devirt.c	(working copy)
> *************** along with GCC; see the file COPYING3.
> *** 116,121 ****
> --- 116,122 ----
>   #include "tree-pretty-print.h"
>   #include "ipa-utils.h"
>   #include "gimple.h"
> + #include "diagnostic.h"
>   
>   /* The node of type inheritance graph.  For each type unique in
>      One Defintion Rule (ODR) sense, we produce one node linking all 
> *************** along with GCC; see the file COPYING3.
> *** 123,136 ****
>   
>   struct GTY(()) odr_type_d
>   {
> -   /* Unique ID indexing the type in odr_types array.  */
> -   int id;
>     /* leader type.  */
>     tree type;
>     /* All bases.  */
>     vec<odr_type> GTY((skip)) bases;
>     /* All derrived types with virtual methods seen in unit.  */
>     vec<odr_type> GTY((skip)) derived_types;
>     /* Is it in anonymous namespace? */
>     bool anonymous_namespace;
>   };
> --- 124,143 ----
>   
>   struct GTY(()) odr_type_d
>   {
>     /* leader type.  */
>     tree type;
>     /* All bases.  */
>     vec<odr_type> GTY((skip)) bases;
>     /* All derrived types with virtual methods seen in unit.  */
>     vec<odr_type> GTY((skip)) derived_types;
> + 
> +   /* All equivalent types, if more than one.  */
> +   vec<tree, va_gc> *types;
> +   /* Set of all equivalent types, if NON-NULL.  */
> +   pointer_set_t * GTY((skip)) types_set;
> + 
> +   /* Unique ID indexing the type in odr_types array.  */
> +   int id;
>     /* Is it in anonymous namespace? */
>     bool anonymous_namespace;
>   };
> *************** hash_type_name (tree t)
> *** 172,177 ****
> --- 179,204 ----
>     if (type_in_anonymous_namespace_p (t))
>       return htab_hash_pointer (t);
>   
> +   /* For polymorphic types, we can simply hash the virtual table.  */
> +   if (TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)))
> +     {
> +       tree v = BINFO_VTABLE (TYPE_BINFO (t));
> +       hashval_t hash = 0;
> + 
> +       if (TREE_CODE (v) == POINTER_PLUS_EXPR)
> + 	{
> + 	  hash = TREE_INT_CST_LOW (TREE_OPERAND (v, 1));
> + 	  v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
> + 	}
> + 
> +       v = DECL_ASSEMBLER_NAME (v);
> + #ifdef ENABLE_CHECKING
> +       gcc_assert (!strchr (IDENTIFIER_POINTER (v), '.'));
> + #endif
> +       hash = iterative_hash_hashval_t (hash, htab_hash_pointer (v));
> +       return hash;
> +     }
> + 
>     /* Rest is not implemented yet.  */
>     gcc_unreachable ();
>   }
> *************** odr_hasher::hash (const value_type *odr_
> *** 184,190 ****
>     return hash_type_name (odr_type->type);
>   }
>   
> ! /* Compare types operations T1 and T2 and return true if they are
>      equivalent.  */
>   
>   inline bool
> --- 211,217 ----
>     return hash_type_name (odr_type->type);
>   }
>   
> ! /* Compare types T1 and T2 and return true if they are
>      equivalent.  */
>   
>   inline bool
> *************** odr_hasher::equal (const value_type *t1,
> *** 200,212 ****
>     return types_same_for_odr (t1->type, t2);
>   }
>   
> ! /* Free a phi operation structure VP.  */
>   
>   inline void
>   odr_hasher::remove (value_type *v)
>   {
>     v->bases.release ();
>     v->derived_types.release ();
>     ggc_free (v);
>   }
>   
> --- 227,241 ----
>     return types_same_for_odr (t1->type, t2);
>   }
>   
> ! /* Free ODR type V.  */
>   
>   inline void
>   odr_hasher::remove (value_type *v)
>   {
>     v->bases.release ();
>     v->derived_types.release ();
> +   if (v->types_set)
> +     pointer_set_destroy (v->types_set);
>     ggc_free (v);
>   }
>   
> *************** static odr_hash_type odr_hash;
> *** 222,227 ****
> --- 251,382 ----
>   static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
>   #define odr_types (*odr_types_ptr)
>   
> + /* TYPE is equivalent to VAL by ODR, but its tree representation differs
> +    from VAL->type.  This may happen in LTO where tree merging did not merge
> +    all variants of the same type.  It may or may not mean the ODR violation.
> +    Add it to the list of duplicates and warn on some violations.  */
> + 
> + void
> + add_type_duplicate (odr_type val, tree type)
> + {
> +   if (!val->types_set)
> +     val->types_set = pointer_set_create ();
> + 
> +   /* See if this duplicate is new.  */
> +   if (!pointer_set_insert (val->types_set, type))
> +     {
> +       bool merge = true;
> +       bool base_mismatch = false;
> +       gcc_assert (in_lto_p);
> +       vec_safe_push (val->types, type);
> +       unsigned int i,j;
> + 
> +       /* First we compare memory layout.  */
> +       if (!types_compatible_p (val->type, type))
> + 	{
> + 	  merge = false;
> + 	  if (BINFO_VTABLE (TYPE_BINFO (val->type))
> + 	      && warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type)), 0,
> + 			     "type %qD violate one definition rule  ",
> + 			     type))
> + 	    inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
> + 		    "the type of same name with different memory layout "
> + 		    "defined in other compilation unit");
> + 	    debug_tree (BINFO_VTABLE (TYPE_BINFO (type)));
> + 	    debug_tree (BINFO_VTABLE (TYPE_BINFO (val->type)));
> + 	  if (cgraph_dump_file)
> + 	    {
> + 	      fprintf (cgraph_dump_file, "ODR violation or merging or ODR type bug?\n");
> + 	    
> + 	      print_node (cgraph_dump_file, "", val->type, 0);
> + 	      putc ('\n',cgraph_dump_file);
> + 	      print_node (cgraph_dump_file, "", type, 0);
> + 	      putc ('\n',cgraph_dump_file);
> + 	    }
> + 	}
> + 
> +       /* Next sanity check that bases are the same.  If not, we will end
> + 	 up producing wrong answers.  */
> +       for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
> + 	if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (TYPE_BINFO (type), i)))
> + 	  {
> + 	    odr_type base = get_odr_type
> + 			       (BINFO_TYPE
> + 				  (BINFO_BASE_BINFO (TYPE_BINFO (type),
> + 						     i)),
> + 				true);
> + 	    if (val->bases.length () <= j || val->bases[j] != base)
> + 	      base_mismatch = true;
> + 	    j++;
> + 	  }
> +       if (base_mismatch)
> + 	{
> + 	  merge = false;
> + 
> + 	  if (warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type)), 0,
> + 			  "type %qD violate one definition rule  ",
> + 			  type))
> + 	    inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
> + 		    "the inconsistent type of same name with different bases"
> + 		    " (defined in other compilation unit)");
> + 	  if (cgraph_dump_file)
> + 	    {
> + 	      fprintf (cgraph_dump_file, "ODR bse violation or merging bug?\n");
> + 	    
> + 	      print_node (cgraph_dump_file, "", val->type, 0);
> + 	      putc ('\n',cgraph_dump_file);
> + 	      print_node (cgraph_dump_file, "", type, 0);
> + 	      putc ('\n',cgraph_dump_file);
> + 	    }
> + 	}
> + 
> +       /* Regularize things a little.  During LTO same types may come with
> + 	 different BINFOs.  Either because their virtual table was
> + 	 not merged by tree merging and only later at decl merging or
> + 	 because one type comes with external vtable, while other
> + 	 with internal.  We want to merge equivalent binfos to conserve
> + 	 memory and streaming overhead.
> + 
> + 	 The external vtables are more harmful: they contain references
> + 	 to external declarations of methods that may be defined in the
> + 	 merged LTO unit.  For this reason we absolutely need to remove
> + 	 them and replace by internal variants. Not doing so will lead
> +          to incomplete answers from possible_polymorphic_call_targets.  */
> +       if (!flag_ltrans && merge)
> + 	{
> + 	  tree master_binfo = TYPE_BINFO (val->type);
> + 	  tree v1 = BINFO_VTABLE (master_binfo);
> + 	  tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
> + 
> + 	  if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
> + 	    {
> + 	      gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
> + 			  && operand_equal_p (TREE_OPERAND (v1, 1),
> + 					      TREE_OPERAND (v2, 1), 0));
> + 	      v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
> + 	      v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
> + 	    }
> + 	  gcc_assert (DECL_ASSEMBLER_NAME (v1)
> + 		      == DECL_ASSEMBLER_NAME (v2));
> + 
> + 	  if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
> + 	    {
> + 	      unsigned int i;
> + 
> + 	      TYPE_BINFO (val->type) = TYPE_BINFO (type);
> + 	      for (i = 0; i < val->types->length(); i++)
> + 		{
> + 		  if (TYPE_BINFO ((*val->types)[i])
> + 		      == master_binfo)
> + 		    TYPE_BINFO ((*val->types)[i]) = TYPE_BINFO (type);
> + 		}
> + 	    }
> + 	  else
> + 	    TYPE_BINFO (type) = master_binfo;
> + 	}
> +     }
> + }
> + 
>   /* Get ODR type hash entry for TYPE.  If INSERT is true, create
>      possibly new entry.  */
>   
> *************** get_odr_type (tree type, bool insert)
> *** 244,254 ****
>       {
>         val = *slot;
>   
> !       /* With LTO we will need to support multiple tree representation of
> ! 	 the same ODR type.  For now we ignore this.  */
> !       if (val->type == type)
> ! 	return val;
> !       gcc_unreachable ();
>       }
>     else
>       {
> --- 399,408 ----
>       {
>         val = *slot;
>   
> !       /* With LTO we need to support multiple tree representation of
> ! 	 the same ODR type.  */
> !       if (val->type != type)
> !         add_type_duplicate (val, type);
>       }
>     else
>       {
> *************** dump_type_inheritance_graph (FILE *f)
> *** 324,329 ****
> --- 478,505 ----
>         if (odr_types[i]->bases.length() == 0)
>   	dump_odr_type (f, odr_types[i]);
>       }
> +   for (i = 0; i < odr_types.length(); i++)
> +     {
> +       if (odr_types[i]->types && odr_types[i]->types->length())
> + 	{
> + 	  unsigned int j;
> + 	  fprintf (f, "Duplicate tree types for odr type %i\n", i);
> + 	  print_node (f, "", odr_types[i]->type, 0);
> + 	  for (j = 0; j < odr_types[i]->types->length(); j++)
> + 	    {
> + 	      tree t;
> + 	      fprintf (f, "duplicate #%i\n", j);
> + 	      print_node (f, "", (*odr_types[i]->types)[j], 0);
> + 	      t = (*odr_types[i]->types)[j];
> + 	      while (TYPE_P (t) && TYPE_CONTEXT (t))
> + 		{
> + 		  t = TYPE_CONTEXT (t);
> + 	          print_node (f, "", t, 0);
> + 		}
> + 	      putc ('\n',f);
> + 	    }
> + 	}
> +     }
>   }
>   
>   /* Given method type T, return type of class it belongs to.
> Index: ipa.c
> ===================================================================
> *** ipa.c	(revision 201835)
> --- ipa.c	(working copy)
> *************** symtab_remove_unreachable_nodes (bool be
> *** 223,228 ****
> --- 223,230 ----
>   #ifdef ENABLE_CHECKING
>     verify_symtab ();
>   #endif
> +   if (optimize && flag_devirtualize)
> +     build_type_inheritance_graph ();
>     if (file)
>       fprintf (file, "\nReclaiming functions:");
>   #ifdef ENABLE_CHECKING
> Index: tree.c
> ===================================================================
> *** tree.c	(revision 201836)
> --- tree.c	(working copy)
> *************** types_same_for_odr (tree type1, tree typ
> *** 11833,11843 ****
>     if (type1 == type2)
>       return true;
>   
> -   /* 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;
> --- 11833,11838 ----
> *************** types_same_for_odr (tree type1, tree typ
> *** 11848,11854 ****
> --- 11843,11887 ----
>     if (type_in_anonymous_namespace_p (type1)
>         || type_in_anonymous_namespace_p (type2))
>       return false;
> +   /* When assembler name of virtual table is available, it is
> +      easy to compare types for equivalence.
> +      FIXME: the code comparing type names consider all instantiations of the
> +      same template to have same name.  This is because we have no access
> +      to template parameters.  For types with no virtual method tables
> +      we thus can return false positives.  At the moment we do not need
> +      to compare types in other scenarios than devirtualization.  */
> +   if (TYPE_BINFO (type1) && TYPE_BINFO (type2)
> +       && BINFO_VTABLE (TYPE_BINFO (type1))
> +       && BINFO_VTABLE (TYPE_BINFO (type2)))
> +     {
> +       tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
> +       tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
>   
> +       if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
> + 	{
> + 	  if (TREE_CODE (v2) != POINTER_PLUS_EXPR
> + 	      || !operand_equal_p (TREE_OPERAND (v1, 1),
> + 			     TREE_OPERAND (v2, 1), 0))
> + 	    return false;
> + 	  v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
> + 	  v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
> + 	}
> +       v1 = DECL_ASSEMBLER_NAME (v1);
> +       v2 = DECL_ASSEMBLER_NAME (v2);
> +       /* If we ever start adding random .blah suffixes after
> + 	 assembler names, we need to compare for match ignoring
> + 	 these (and update odr_type_hash, too).  */
> + #ifdef ENABLE_CHECKING
> +       gcc_assert (!strchr (IDENTIFIER_POINTER (v1), '.')
> + 		  && !strchr (IDENTIFIER_POINTER (v2), '.'));
> + #endif
> +       return (v1 == v2);
> +     }
> + 
> +   /* 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;
>     if (!TYPE_NAME (type1))
>       return false;
>     if (!decls_same_for_odr (TYPE_NAME (type1), TYPE_NAME (type2)))