* 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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@202258 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 258 insertions, 14 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0b51fa2971e..2d2c7319a8d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2013-09-04  Jan Hubicka  <jh@suse.cz>
+
+	* 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.
+
 2013-09-04  Dodji Seketeli  <dodji@redhat.com>
 
 	* tree.h (DECL_BUILT_IN, DECL_IS_BUILTIN): Add more comments
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f0ee2d27294..87a09ba4d00 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2963,7 +2963,8 @@ ipa-profile.o : ipa-profile.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRA
    ipa-inline.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-inline.h ipa-utils.h $(TREE_PRETTY_PRINT_H)
+   $(IPA_UTILS_H) $(HASH_TABLE_H) ipa-inline.h ipa-utils.h $(TREE_PRETTY_PRINT_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) \
diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c
index f9a5ae3f7a1..743f30ca5ee 100644
--- a/gcc/ipa-devirt.c
+++ b/gcc/ipa-devirt.c
@@ -119,6 +119,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "ipa-utils.h"
 #include "gimple.h"
 #include "ipa-inline.h"
+#include "diagnostic.h"
 
 /* Pointer set of all call targets appearing in the cache.  */
 static pointer_set_t *cached_polymorphic_call_targets;
@@ -136,6 +137,11 @@ struct GTY(()) odr_type_d
   /* 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? */
@@ -185,6 +191,26 @@ hash_type_name (tree t)
   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 ();
 }
@@ -220,6 +246,8 @@ 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);
 }
 
@@ -235,6 +263,132 @@ static odr_hash_type odr_hash;
 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.  */
+
+static 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 violates one definition rule  ",
+			     type))
+	    inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
+		    "a type with the same name but different layout is "
+		    "defined in another translation 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 violates one definition rule  ",
+			  type))
+	    inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
+		    "a type with the same name but different bases is "
+		    "defined in another translation 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.  */
 
@@ -257,11 +411,10 @@ get_odr_type (tree type, bool insert)
     {
       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 ();
+      /* With LTO we need to support multiple tree representation of
+	 the same ODR type.  */
+      if (val->type != type)
+        add_type_duplicate (val, type);
     }
   else
     {
@@ -340,6 +493,28 @@ dump_type_inheritance_graph (FILE *f)
       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.
diff --git a/gcc/ipa.c b/gcc/ipa.c
index b1759ae876c..37b6629b206 100644
--- a/gcc/ipa.c
+++ b/gcc/ipa.c
@@ -218,6 +218,8 @@ symtab_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 #ifdef ENABLE_CHECKING
   verify_symtab ();
 #endif
+  if (optimize && flag_devirtualize)
+    build_type_inheritance_graph ();
   if (file)
     fprintf (file, "\nReclaiming functions:");
 #ifdef ENABLE_CHECKING
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index dfcd1357179..f27f2fd9aff 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -124,8 +124,11 @@ output_type_ref (struct output_block *ob, tree node)
 static bool
 tree_is_indexable (tree t)
 {
+  /* Parameters and return values of functions of variably modified types
+     must go to global stream, because they may be used in the type
+     definition.  */
   if (TREE_CODE (t) == PARM_DECL || TREE_CODE (t) == RESULT_DECL)
-    return false;
+    return variably_modified_type_p (TREE_TYPE (DECL_CONTEXT (t)), NULL_TREE);
   else if (TREE_CODE (t) == VAR_DECL && decl_function_context (t)
 	   && !TREE_STATIC (t))
     return false;
diff --git a/gcc/predict.c b/gcc/predict.c
index 06da1cdf22e..ddf72d2d14a 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -232,8 +232,22 @@ bool
 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
 {
   gcc_checking_assert (fun);
-  if (profile_info && flag_branch_probabilities)
-    return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
+  if (profile_status_for_function (fun) == PROFILE_READ)
+    {
+      if ((bb->count * 4 + profile_info->runs / 2) / profile_info->runs > 0)
+	return false;
+      if (!bb->frequency)
+	return true;
+      if (!ENTRY_BLOCK_PTR->frequency)
+	return false;
+      if (ENTRY_BLOCK_PTR->count && ENTRY_BLOCK_PTR->count < REG_BR_PROB_BASE)
+	{
+	  return (RDIV (bb->frequency * ENTRY_BLOCK_PTR->count,
+		        ENTRY_BLOCK_PTR->frequency)
+		  < REG_BR_PROB_BASE / 4);
+	}
+      return true;
+    }
   if ((!profile_info || !flag_branch_probabilities)
       && (cgraph_get_node (fun->decl)->frequency
 	  == NODE_FREQUENCY_UNLIKELY_EXECUTED))
diff --git a/gcc/tree.c b/gcc/tree.c
index b469b97c867..7e44b402c96 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -11853,11 +11853,6 @@ types_same_for_odr (tree type1, tree type2)
   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;
@@ -11868,7 +11863,46 @@ types_same_for_odr (tree type1, tree type2)
   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.  */
+  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);
+    }
+
+  /* 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 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)))